MD5
 |
| 一般 | |
|---|---|
| 設計者 | ロナルド・リベスト |
| 初版発行日 | 1992年4月 |
| シリーズ | MD2, MD4, MD5, MD6 |
| 詳細 | |
| ダイジェスト長 | 128 bit |
| 構造 | Merkle-Damgård construction |
| ラウンド数 | 4 [1] |
| 最良の暗号解読法 | |
| 2009年にTao Xie、Dengguo Fengによって強衝突耐性が破られている (220.96 time)。通常のコンピュータで数秒で可能[2]。 | |
MD5（エムディーファイブ、英: message digest algorithm 5）は、暗号学的ハッシュ関数のひとつである。ハッシュ値は128ビット。
概要[編集]
MD4が前身であり、安全性を向上させたもの。1991年に開発された。開発者はMD4と同じくロナルド・リベスト。
d41d8cd98f00b204e9800998ecf8427e
のようなハッシュ値が得られる。
用途[編集]
一般的な暗号学的ハッシュ関数と同様に使用できる。ただし、後述の脆弱性があり強度が必要な場合には使ってはいけない。
実際の使用例[編集]
FreeBSDはインストール可能なCDイメージと、それのMD5値を同時に配布している。（MD5値の改変はないと仮定して）インストール可能なCDイメージが、途中で改変されていないことを確認してみる。
- 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とよばれるハッシュ関数には理論的な弱点が存在することが明らかとなっている[3][4]。
2004年8月、暗号の国際会議 CRYPTO （のランプセッション）にて、MD5のコリジョンを求めることができたという報告があった。理論的可能性として、MD5を用いて改竄されないことを確認する場合、あらかじめ正規のファイルと不正なファイルを用意しておき、正規のファイルを登録しておきながら、実際には同じMD5を持つ不正なファイルに摩り替える攻撃がありえることを意味する。また2007年11月、2つの全く異なる実行ファイルを元に、各々の末尾にデータブロックを付加し、その部分を変更しながら探索を行うことにより、同一のMD5を持たせることに成功したという報告があった。この攻撃方法は実証されたことになる。
アメリカ合衆国政府では、MD5ではなく、Secure Hash Algorithm (SHA)を標準のハッシュとして使用している。 日本のCRYPTRECでは、MD5を政府推奨暗号リストから外し、SHA-256 (SHA-2のバリエーション) 以上を推奨している。
ハッシュの衝突耐性について[編集]
MD5 のハッシュ値については、パソコンレベルでも数10分程度で、同一ハッシュ値の非ユニークなデータ列を生成できる実装が広まっている。すなわち、強衝突耐性は容易に突破されうる状態にある（SHA-0/SHA-1アルゴリズムについても、MD5ほど容易ではないが突破される脆弱性が発見されている）。
一方、任意に与えられたハッシュ値に対して、（何らかの別の）データを生成する実装が広まっているわけではない。すなわち、弱衝突耐性が容易に突破されうる訳ではない。また、任意に与えられたハッシュ値に対して、改竄者の意図どおりのデータ列を容易に生成できる訳でもない（もしそうならば、それは既に暗号ではない）。
強衝突耐性の突破とは例えば、同一のハッシュ値を持つ非ユニークな2つのデータ列D1とD2のペアを1つ発見できた、ということである。なお、この場合D1やD2が意味を持つデータであるかどうかは問われない。また、データ列D3のハッシュ値がHであったとして、この"特定の"ハッシュ値Hに対して、同一のハッシュ値を持つような他のデータ列D4を発見できたとしたら、それは弱衝突耐性を突破された事を意味する（即ち、D3とHの組み合わせで無改竄性を証明できなくなる）。
そのため、直ちにこれらのハッシュアルゴリズムを用いている暗号化通信が盗聴・改竄されたり、電子署名の有効性が無くなると言うわけではない。しかし、強衝突耐性が突破されたという事は、将来的には攻撃手法や計算能力の進化により、弱衝突耐性も突破されうるという事を暗示する。もし弱衝突耐性が突破されたとしたら、もはや暗号化通信や電子署名の無改竄性を証明できなくなり、その暗号化・署名システムは（半ば）死を意味する。
また、暗号化・署名システムのintegrity（例えば最良攻撃手法に対して十分に頑強であるという事）にハッシュ強衝突耐性の突破が困難であるという前提がもし有った場合には、そのシステムのintegrityも当然に失われる事になる。Integrityを要求されるシステムでは、その再検証が最低限必要となる。
APOPの脆弱性[編集]
2007年4月IPAはAPOPの脆弱性について警告した[5]。これは電気通信大学の太田和夫（暗号理論）らが発見したもので[6]、APOPのプロトコル上の弱点を利用して、MD5ハッシュから理論的に元のパスワードを求めることが出来るというものである。これの対策としては、SSLの利用が推奨されている。（総当たり攻撃法によるツールは既に公表されている）
Flame攻撃に関して[編集]
2012年4月に発覚した「Flame攻撃」（Microsoft Updateに対するなりすまし攻撃）において、一部のデジタル証明書の署名アルゴリズムにMD5が使われていたことから、MD5 の衝突耐性に関する脆弱性をついて、デジタル証明書の偽造が行われたように一部媒体では報道されている[7]。
しかし、米ソフォス (Sophos) 社の記事によると[8]、マイクロソフトがコード署名に使用できるデジタル証明書であって、ターミナルサーバーライセンスインフラストラクチャ（中間Certificate Authenticity）上で使用できるものを、誤って発行していた事が原因とされている。また、Flameマルウェアが攻撃に使用したデジタル証明書を入手した経路、また前述の MD5 で署名された証明書をクラックして偽造したものであるか否かは明らかになっていないとしている。一方マイクロソフトは、Windows Vista以降のバージョンにおけるコード署名の検証を回避するためには攻撃者が MD5 の衝突を利用して特定の拡張フィールドを削除する必要があったとしている[9]。
マイクロソフトは2012年6月5日に、問題となったターミナルサーバーライセンスインフラストラクチャの中間Certificate Authenticityを無効化するセキュリティアップデートを公開している[10]。
アルゴリズム[編集]
sは左へのsビットのローテーション操作であり、sは操作ごとに異なる。
は232を法とした加算である。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))
実装ライブラリ[編集]
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
| |||||||||||||||||||||||||||||
 カテゴリ | |||||||||||||||||||||||||||||