MD5
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/11/02 13:44 UTC 版)
アルゴリズム
MD5は可変長の入力を処理して、128ビット固定長の値を出力する。入力メッセージは512ビット(32ビットのワードが16個)ごとに切り分けられるが、長さが512の倍数となるようにパディングが行われる。 パディングとしてはまずメッセージの最後に1ビットの1を足して、その後には長さが512で割って448余る(つまり、512の倍数に64足りない)長さになるようにひたすら0を付け足していく。そして、残った64ビットには元のメッセージの長さ(の下位64ビット)を入れることとなる。
MD5のメイン部分のアルゴリズムは32ビット×4ワード(それぞれのワードをA、B、C、Dと表す) = 128ビットの状態を持って進行していく。初期状態では、この4ワードは決まった定数で初期化されており、 512ビットのブロックを順次使ってこの状態を変化させていくのがMD5の中核となっている。1回の処理では非線形な関数F、232を法とした加算、左へのビットローテートが行われる。 そして、16回の操作を1ラウンドとして、512ビットの入力ブロックを処理するのに4ラウンドの処理が行われる。Fには4通りの関数があり、ラウンドごとに異なるものが使われる。
擬似コード
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 にある本来の式に代えて、以下のように計算するほうが効率的な場合がある(高級言語で書いている場合、コンパイラの最適化に任せるほうがよい。 NANDとANDが並行して計算できる環境であれば、並列演算のできない以下の式に比べて、元のままのほうが速いことも多々ある)。
( 0 ≦ i ≦ 15): F := D bitXor (B bitAnd (C bitXor D)) (16 ≦ i ≦ 31): F := C bitXor (D bitAnd (B bitXor C))
- ^ 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.
固有名詞の分類
- MD5のページへのリンク