MD5
 |
| ロナルド・リベスト | |
|
1992 | |
| シリーズ | MD2, MD4, MD5, MD6 |
| ダイジェスト | 128 bit |
| Merkle-Damgård construction | |
| ラウンド | 4 [1] |
| 2009 | |
MD5（エムディーファイブ、
概要
[MD4が
d41d8cd98f00b204e9800998ecf8427e
のようなハッシュ
用途
[実際 の使用 例
[FreeBSDはインストール
- md5 コマンドを、イメージファイルに
実行 する。- localhost% md5 5.1-RELEASE-i386-miniinst.iso
- MD5 (5.1-RELEASE-i386-miniinst.iso) = 646da9ae5d90e6b51b06ede01b9fed67
- CHECKSUM.MD5の
中身 を確認 し、一致 していれば破損 の可能 性 は極 めて低 いことが分 かる。- localhost% cat CHECKSUM.MD5
- MD5 (5.1-RELEASE-i386-disc1.iso) = 3b6619cffb5f96e1acfa578badae372f
- MD5 (5.1-RELEASE-i386-disc2.iso) = 2cfa746974210d68e96ee620bf842fb6
- MD5 (5.1-RELEASE-i386-miniinst.iso) = 646da9ae5d90e6b51b06ede01b9fed67
安全 性
[MD5、およびRIPEMDとよばれるハッシュ
2004
ハッシュの衝突 耐 性 について
[MD5 のハッシュ
そのため、
また、
APOPの脆弱 性
[2007
Flame攻撃 に関 して
[2012
しかし、
マイクロソフトは2012
アルゴリズム
[
sは
は232をMD5は
MD5のメイン
擬似 コード
[MD5ハッシュは、
function md5 (message : array[0..*] of bit) returns array[0..15] of unsignedInt8 is
//左 ローテート関数
function leftRotate (x : unsignedInt32, c : integer range 0..31) returns unsignedInt32 is
begin leftRotate := (x leftShift c) bitOr (x rightShift (32-c)) end ;
function makeK (i : integer range 0..63) returns unsignedIt32 is
begin makeK := floor(232×abs(sin(i + 1))) end ;
begin
//注 : すべての変数 は符号 なし32ビット値 で、桁 があふれた時 は232を法 として演算 されるものとする。
//ラウンドごとのローテート量 sを指定 する
const s : array[0..63] of unsignedInt32 :=
{
7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21
} ;
//整数 ラジアンのときの三角 関数 からKの値 を生成 する
const K : array[0..63] of unsignedInt32 := range 0..63 map makeK ;
//（Kを事前 に計算 して、テーブルとしておくこともできる）
//
//const K : array[0..63] of unsignedInt32 :=
// {
// D76AA478(16進数 ), E8C7B756(16進数 ), 242070DB(16進数 ), C1BDCEEE(16進数 ),
// F57C0FAF(16進数 ), 4787C62A(16進数 ), A8304613(16進数 ), FD469501(16進数 ),
// 698098D8(16進数 ), 8B44F7AF(16進数 ), FFFF5BB1(16進数 ), 895CD7BE(16進数 ),
// 6B901122(16進数 ), FD987193(16進数 ), A679438E(16進数 ), 49B40821(16進数 ),
// F61E2562(16進数 ), C040B340(16進数 ), 265E5A51(16進数 ), E9B6C7AA(16進数 ),
// D62F105D(16進数 ), 02441453(16進数 ), D8A1E681(16進数 ), E7D3FBC8(16進数 ),
// 21E1CDE6(16進数 ), C33707D6(16進数 ), F4D50D87(16進数 ), 455A14ED(16進数 ),
// A9E3E905(16進数 ), FCEFA3F8(16進数 ), 676F02D9(16進数 ), 8D2A4C8A(16進数 ),
// FFFA3942(16進数 ), 8771F681(16進数 ), 6D9D6122(16進数 ), FDE5380C(16進数 ),
// A4BEEA44(16進数 ), 4BDECFA9(16進数 ), F6BB4B60(16進数 ), BEBFBC70(16進数 ),
// 289B7EC6(16進数 ), EAA127FA(16進数 ), D4EF3085(16進数 ), 04881D05(16進数 ),
// D9D4D039(16進数 ), E6DB99E5(16進数 ), 1FA27CF8(16進数 ), C4AC5665(16進数 ),
// F4292244(16進数 ), 432AFF97(16進数 ), AB9423A7(16進数 ), FC93A039(16進数 ),
// 655B59C3(16進数 ), 8F0CCC92(16進数 ), FFEFF47D(16進数 ), 85845DD1(16進数 ),
// 6FA87E4F(16進数 ), FE2CE6E0(16進数 ), A3014314(16進数 ), 4E0811A1(16進数 ),
// F7537E82(16進数 ), BD3AF235(16進数 ), 2AD7D2BB(16進数 ), EB86D391(16進数 )
// } ;
//A、B、C、Dの初期 値
var a0 : unsignedInt32 := 67452301(16進数 ) ; // A
var b0 : unsignedInt32 := EFCDAB89(16進数 ) ; // B
var c0 : unsignedInt32 := 98BADCFE(16進数 ) ; // C
var d0 : unsignedInt32 := 10325476(16進数 ) ; // D
//パディング処理 : 1ビットのデータ「1」を追加 する
message[message.length] = (bit) 1 ;
//注 : 入力 のバイト値 は、最高 位 ビットが先 のビットであるビット列 として解釈 するものとする[11]。
const initial_message_length : integer := message.length ;
//パディング処理 : 残 りは「0」で埋 める
repeat
message[message.length] := (bit) 0
until (message.length mod 512) ＝ 448 ; //448 ＝ 512 － 64
message[message.length .. message.length+63] := split (initial_message_length mod 264, 1bit) ;
//入力 を512ビットのブロックに切 って、順次 処理 する
//chunk のバイトオーダーは message のバイトオーダーのままである
var chunk : bits512 ;
for each chunk of split (message, 512bit) do
var M : array [0..15] of unsignedInt32 := split (chunk, 32bit) ;
//内部 状態 の初期 化
var A : unsignedInt32 := a0 ;
var B : unsignedInt32 := b0 ;
var C : unsignedInt32 := c0 ;
var D : unsignedInt32 := d0 ;
//メインループ
var F : unsignedInt32 ;
var g : integer range 0..15 ;
for i from 0 to 63
switch
case 0 ≦ i ≦ 15 do
F := (B bitAnd C) bitOr ((bitNot B) bitAnd D) ;
g := i
end case
case 16 ≦ i ≦ 31 do
F := (D bitAnd B) bitOr ((bitNot D) bitAnd C) ;
g := (5×i + 1) mod 16
end case
case 32 ≦ i ≦ 47 do
F := (B bitXor C) bitXor D ;
g := (3×i + 5) mod 16
end case
case 48 ≦ i ≦ 63 do
F := C bitXor (B bitOr (bitNot D)) ;
g := (7×i) mod 16
end case
end switch
F := F + A + K[i] + M[g] ;
(D, C, A) := (C, B, D) ;
B := B + leftRotate(F, s[i]) ;
end for ;
//今 までの結果 にこのブロックの結果 を足 す
a0 := a0 + A ;
b0 := b0 + B ;
c0 := c0 + C ;
d0 := d0 + D
end for ;
//16個 の8ビット符号 なし整数 型 データ列 がMD5値 である。
//リトルエンディアンでの出力
md5[ 0.. 3] := split (a0, 8bit) ;
md5[ 4.. 7] := split (b0, 8bit) ;
md5[ 8..11] := split (c0, 8bit) ;
md5[12..15] := split (d0, 8bit) ;
end.
なお、RFC 1321 にある
( 0 ≦ i ≦ 15): F := D bitXor (B bitAnd (C bitXor D)) (16 ≦ i ≦ 31): F := C bitXor (D bitAnd (B bitXor C))
実装 ライブラリ
[MD5をサポートしているライブラリは
参考 文献
[- R. Rivest, "The MD5 Message-Digest Algorithm", RFC 1321, April 1992.
- Hans Dobbertin, "The Status of MD5 After a Recent Attack", CryptoBytes Volume 2, Number 2, pp.1,3-6, Summer 1996. [1]
- Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu, "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD", IACR ePrint #199, Augst 17 2004. [2]
脚注
[- ^ RFC 1321, section 3.4, "Step 4. Process Message in 16-Word Blocks", page 5.
- ^ Tao Xie and Dengguo Feng (30 May 2009). How To Find Weak Input Differences For MD5 Collision Attacks.
- ^ MD5の
安全 性 の限界 に関 する調査 研究 報告 書 - ^ Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu (17 August 2004). Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD.
- ^ IPA:APOP におけるパスワード
漏 えいの脆弱 性 - ^ Software Integrity Checksum and Code Signing Vulnerability
- ^ MS、Flameによる
偽造 証明 書 発生 で多重 対策 を実施 -証明 書 のルート分離 やWUなど強化 - ^ Flame malware used man-in-the-middle attack against Windows Update
- ^ Flame malware collision attack explained
- ^ マイクロソフト セキュリティ アドバイザリ (2718704)
- ^ RFC 1321, section 2, "Terminology and Notation", Page 2.
関連 項目
[- ハッシュ
関数 - MD2
- MD4
- Secure Hash Algorithm - SHA-1 - SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512) - SHA-3
- HMAC
- アメリカサイバー
軍 - エンブレムに任務 規定 のMD5ハッシュが描 かれている。
外部 リンク
[- RFC 1321
- RFC 6151: RFC 1321のsecurity considerationsについて
置 き換 えるものであると規定 している。 - MD2, MD4, MD5 Online Calculator Calculate file hashes using an on-line web form.
- Online MD5 crack – Rainbow Tables + big hash database (md5, md5(md5), sha1, mysql)
- MD5 cracking by RainbowTables
- Simple hash calculator
高速 にMD5ハッシュの元 の文字 を見 つけ出 すツール- Online MD5 Reverser | Hash cracker
- マイクロソフト セキュリティ アドバイザリ (961509):
研究 機関 によるMD5対 する衝突 攻撃 (collision attack)の実現 可能 性 にの実証 に関 して - Secure hash calculator
| |||||||||||||||||||||||||||||
 カテゴリ | |||||||||||||||||||||||||||||