MD5

テンプレート:参照方法テンプレート:Infobox Encryption method MD5（エムディーファイブ、Message Digest Algorithm 5）とは、与えられた入力に対して128ビットのハッシュ値を出力するハッシュ関数である。MD5のハッシュキーの長さは、2¹²⁸（約 3.403×10³⁸ ＝ 340澗_（かん）＝ 340京の1京倍）通りのハッシュ値をとり、IPv6のアドレス空間と同じである。

概要

1991年に開発されたMD5は、前身であるMD4の安全性を向上させたものである。開発者はMD4と同じく、マサチューセッツ工科大学(MIT)教授でRSA暗号の開発者でもあるロナルド・リベスト (Ronald Linn Rivest)。

Linuxでは md5sum、FreeBSDでは md5 というコマンドが用意されており、これを用いてメッセージダイジェストを出力することが出来る。出力されるメッセージダイジェストは、

d41d8cd98f00b204e9800998ecf8427e （入力データ長が0バイトの場合）

の様に32個の16進数の数字が並んだテキスト形式で出力され、これをフィンガプリント（指紋）やハッシュ値、あるいは単にMD5値と呼ぶ。「MD5チェックサム」とも良く言われる。

用途

MD5は、電子署名を必要とするアプリケーション向けに開発された。RSAで署名を生成する際に、メッセージを直接対象として署名を生成するのではなく、メッセージのハッシュ値を生成し、ハッシュ値に対して署名を生成する。

ファイルを転送する際にそのファイルが破損していないことを確認するためにも用いられる。配布する側は、ファイル配布時にそのファイルのMD5ハッシュ値（いわゆるMD5チェックサム）も同時に配布する。受信したユーザは手元でファイルのMD5値を計算して、配布者の提示したMD5値と一致することを確認すれば良い。ファイル本体とハッシュ値の両方が破損して偶然一致する可能性もゼロではないが、現実的ではないので無視できる。このような目的にCRCを用いることもあるが、CRCは標準が複数存在するため現在ではあまり見られない。

またファイルが改竄されていないことを証明するためにも用いられる。これにより、作成者以外によるトロイの木馬やコンピュータウイルスなどの混入を防ぐことが出来る。しかし、この場合MD5値は手元で計算できるため、改竄済みのファイルのMD5値が同梱されている可能性がある。したがって、改竄の恐れがある場合には、ファイルに同封されているMD5値と比較するのではなく、MD5値だけは何かしら信頼できる方法で配布者から入手する必要がある。

実際の使用例

FreeBSDはインストール可能なCDイメージと、それのMD5値を同時に配布している。（MD5値の改変はないと仮定して）インストール可能なCDイメージが、途中で改変されていないことを確認してみる。

配布サイトから、ここでは 5.1-RELEASE-i386-miniinst.iso という最小構成のインストールイメージファイルと、CHECKSUM.MD5 というMD5値（いわゆるMD5チェックサム）の書かれたテキストファイルをダウンロードする。
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年8月、暗号の国際会議 CRYPTO （のランプセッション）にて、MD5のコリジョンを求めることができたという報告があった。理論的可能性として、MD5を用いて改竄されないことを確認する場合、あらかじめ正規のファイルと不正なファイルを用意しておき、正規のファイルを登録しておきながら、実際には同じMD5を持つ不正なファイルに摩り替える攻撃がありえることを意味する。また2007年11月、2つの全く異なる実行ファイルを元に、各々の末尾にデータブロックを付加し、その部分を変更しながら探索を行うことにより、同一のMD5を持たせることに成功したという報告があった。この攻撃方法は実証されたことになる。

アメリカ合衆国政府では、MD5ではなく、Secure Hash Algorithm (SHA)を標準のハッシュとして使用している。日本のCRYPTRECでは、MD5を政府推奨暗号リストから外し、SHA-256以上を推奨している。

ハッシュの衝突耐性について

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の脆弱性について警告した^[1]。これは電気通信大学の太田和夫（暗号理論）らが発見したもので^[2]、APOPのプロトコル上の弱点を利用して、MD5ハッシュから理論的に元のパスワードを求めることが出来るというものである。これの対策としては、SSLの利用が推奨されている。（総当たり攻撃法によるツールは既に公表されている）

Flame攻撃に関して

2012年4月に発覚した「Flame攻撃」（Microsoft Updateに対するなりすまし攻撃）において、一部のデジタル証明書の署名アルゴリズムにMD5が使われていたことから、MD5の衝突耐性に関する脆弱性をついて、デジタル証明書の偽造が行われたように一部媒体では報道されている^[3]。

しかし、米Sophos社の記事によると^[4]、マイクロソフトがコード署名に使用できるデジタル証明書であって、ターミナルサーバーライセンスインフラストラクチャ（中間Certificate Authenticity）上で使用できるものを、誤って発行していた事が原因とされている。またマイクロソフトは、Windows Vista以降のバージョンにおけるコード署名の検証を回避するためには攻撃者がMD5の衝突を利用して特定の拡張フィールドを削除する必要があったとしている^[5]。なお、Flameマルウェアが攻撃に使用したデジタル証明書が、前述のMD5で署名された証明書をクラックして偽造したものであるかどうかは、入手経路は明らかになっていないとしている。

マイクロソフトは2012年6月5日に、問題となったターミナルサーバーライセンスインフラストラクチャの中間Certificate Authenticityを無効化するセキュリティアップデートを公開している^[6]。

アルゴリズム

ファイル:MD5.svg

図1:MD5計算の1段階。MD5はこのような操作を64回行うが、16回の操作を1ラウンドとして4ラウンド行う。Fは非線形な関数で、1ラウンドごとに1つの関数が使われる。M_iはメッセージの入力、K_iは操作ごとに異なる32ビットの定数である。left shift_sは左へのsビットのローテーション操作であり、sは操作ごとに異なる。Additionは2³²を法とした加算である。

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、2³²を法とした加算、左へのビットローテートが行われる。そして、16回の操作を1ラウンドとして、512ビットの入力ブロックを処理するのに4ラウンドの処理が行われる。Fには4通りの関数があり、ラウンドごとに異なるものが使われる。

<math>F(B,C,D) = (B\wedge{C}) \vee (\neg{B} \wedge{D})</math>

<math>G(B,C,D) = (B\wedge{D}) \vee (C \wedge \neg{D})</math>

<math>H(B,C,D) = B \oplus C \oplus D</math>

<math>I(B,C,D) = C \oplus (B \vee \neg{D})</math>

<math>\oplus, \wedge, \vee, \neg</math>はそれぞれXOR、AND、OR、NOT演算を意味する。

擬似コード

MD5ハッシュは、以下のようなアルゴリズムで算出される。値はすべてリトルエンディアンとする。

//注: すべての変数は符号なし32ビット値で、桁があふれた時は2^32を法として演算されるものとする。
var int[64] s, K

//ラウンドごとのローテート量 sを指定する
s[ 0..15] := { 7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22}
s[16..31] := { 5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20}
s[32..47] := { 4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23}
s[48..63] := { 6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21}

//整数ラジアンのときの三角関数からKの値を生成する
for i from 0 to 63
    K[i] := floor(abs(sin(i + 1)) × (2 pow 32))
end for
//（Kを事前に計算して、テーブルとしておくこともできる）
K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee }
K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 }
K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be }
K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 }
K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa }
K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 }
K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed }
K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a }
K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c }
K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 }
K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 }
K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 }
K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 }
K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 }
K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 }
K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }

//A、B、C、Dの初期値
var int a0 := 0x67452301   //A
var int b0 := 0xefcdab89   //B
var int c0 := 0x98badcfe   //C
var int d0 := 0x10325476   //D

//パディング処理: 1のビットを追加する
append "1" bit to message</span>    
/* 注: 入力のバイト値は、最高位ビットが先のビットである
  ビット列として解釈するものとする^[7]。*/
  

//パディング処理: 残りは0で埋める
append "0" bit until message length in bit ≡ 448 (mod 512)
append length mod (2 pow 64) to message
</span>

//入力を512バイトのブロックに切って、順次処理する
for each 512-bit chunk of message
    break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
//内部状態の初期化
    var int A := a0
    var int B := b0
    var int C := c0
    var int D := d0
//メインループ
    for i from 0 to 63
        if 0 ≦ i ≦ 15 then
            F := (B and C) or ((not B) and D)
            g := i
        else if 16 ≦ i ≦ 31
            F := (D and B) or ((not D) and C)
            g := (5×i + 1) mod 16
        else if 32 ≦ i ≦ 47
            F := B xor C xor D
            g := (3×i + 5) mod 16
        else if 48 ≦ i ≦ 63
            F := C xor (B or (not D))
            g := (7×i) mod 16
        dTemp := D
        D := C
        C := B
        B := B + leftrotate((A + F + K[i] + M[g]), s[i])
        A := dTemp
    end for
//今までの結果にこのブロックの結果を足す
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 //（リトルエンディアンでの出力）

//左ローテート関数
leftrotate (x, c)
    return (x << c) binary or (x >> (32-c));

なお、RFC 1321 にある本来の式に代えて、以下のように計算するほうが効率的な場合がある（高級言語で書いている場合、コンパイラの最適化に任せるほうがよい。 NANDとANDが並行して計算できる環境であれば、並列演算のできない以下の式に比べて、元のままのほうが速いことも多々ある）。

( 0 ≦ i ≦ 15): F := D xor (B and (C xor D))
(16 ≦ i ≦ 31): F := C xor (D and (B xor C))

参考文献

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]

脚注

↑ 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, 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)の実現可能性にの実証に関して
MD5 メッセージダイジェストアルゴリズム
Secure hash calculator

テンプレート:Cryptography navbox

[1] IPA:APOP におけるパスワード漏えいの脆弱性

[2] Software Integrity Checksum and Code Signing Vulnerability

[3] MS、Flameによる偽造証明書発生で多重対策を実施 - 証明書のルート分離やWUなど強化

[4] Flame malware used man-in-the-middle attack against Windows Update

[5] Flame malware collision attack explained

[6] マイクロソフトセキュリティアドバイザリ (2718704)

[7] RFC 1321, section 2, "Terminology and Notation", Page 2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

MD5

目次

概要

用途

実際の使用例

安全性

ハッシュの衝突耐性について

APOPの脆弱性

Flame攻撃に関して

アルゴリズム

擬似コード

参考文献

脚注

関連項目

外部リンク

案内メニュー

個人用ツール

名前空間

変種

表示

その他

検索

案内

ヘルプ

ツール