MD5 - standard

この文書では、MD5メッセージダイジェストアルゴリズムについて説明します。このアルゴリズムは、任意の長さのメッセージを入力として受け取り、128ビットの「フィンガープリント」または「メッセージダイジェスト」を出力します。同じメッセージダイジェストを持つ2つのメッセージを生成すること、あるいは特定のターゲットメッセージダイジェストを持つ任意のメッセージを生成することは、計算量的に不可能であると推測されています。MD5アルゴリズムは、RSAなどの公開鍵暗号システムを用いて秘密鍵で暗号化する前に、大容量ファイルを安全な方法で「圧縮」する必要があるデジタル署名アプリケーションを対象としています。

MD5アルゴリズムは、32ビットマシン上で非常に高速に動作するように設計されています。さらに、MD5アルゴリズムは大規模な置換テーブルを必要としないため、非常にコンパクトにコーディングできます。

MD5アルゴリズムは、MD4メッセージダイジェストアルゴリズム1,2の拡張版です。MD5はMD4よりもわずかに低速ですが、より「保守的」な設計となっています。 MD5は、MD4が既存の批判的なレビューで正当化されるよりも早く実用化されている可能性があると感じられたため、設計されました。MD4は非常に高速に設計されたため、暗号解読攻撃が成功するリスクという点で「限界」にありました。MD5は速度を少し犠牲にすることで、究極のセキュリティを実現する可能性を大幅に高めています。様々なレビュー担当者からの提案を取り入れ、追加の最適化も行われています。MD5アルゴリズムは、レビューと標準規格としての採用の可能性のためにパブリックドメインに公開されています。

OSIベースのアプリケーションの場合、MD5のオブジェクト識別子は

md5 OBJECT IDENTIFIER ::=

iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 5}

X.509型AlgorithmIdentifier 3において、MD5のパラメータはNULL型である必要があります。

2. 用語と表記

この文書では、「ワード」は32ビットの量、「バイト」は8ビットの量です。ビットのシーケンスは、バイトのシーケンスとして自然に解釈できます。この場合、連続する8ビットの各グループは、各バイトの上位（最上位）ビットを先頭に1バイトとして解釈されます。同様に、バイトのシーケンスは32ビットのワードのシーケンスとして解釈できます。この場合、連続する4バイトの各グループは、下位（最下位）バイトを先頭に1ワードとして解釈されます。

x_i は「x sub i」を表します。添字が式の場合は、x_{i+1} のように中括弧で囲みます。同様に、上付き文字（べき乗）には ^ を使用します。つまり、x^i は x の i 乗を表します。

記号「+」はワードの加算（つまり、2^32 を法とする加算）を表します。 X <<< s は、X を s ビット左に循環シフト（回転）して得られる 32 ビット値を表します。not(X) は X のビット補数を表し、X v Y は X と Y のビット OR を表します。X xor Y は X と Y のビット XOR を表し、XY は X と Y のビット AND を表します。

3. MD5アルゴリズムの説明

まず、bビットのメッセージを入力として持ち、そのメッセージダイジェストを求めたいとします。ここで、bは任意の非負整数です。bは0であってもよく、8の倍数である必要はなく、任意の大きさであっても構いません。メッセージのビットは以下のように記述されていると仮定します。

m_0 m_1 ... m_{b-1}

メッセージのメッセージダイジェストを計算するために、以下の5つの手順が実行されます。

3.1 ステップ 1. パディングビットの追加

メッセージは、その長さ（ビット数）が 448 を法として 512 を法として一致するように「パディング」（拡張）されます。つまり、メッセージは 512 ビットの倍数から 64 ビットだけ短いように拡張されます。メッセージの長さが既に 448 を法として 512 を法として一致している場合でも、パディングは常に実行されます。

パディングは次のように実行されます。メッセージに 1 ビットの「1」が追加され、その後に「0」ビットが追加され、パディングされたメッセージのビット数（ビット数）が 448 を法として 512 を法として一致するようになります。合計で、少なくとも 1 ビット、最大で 512 ビットが追加されます。

3.2 ステップ2. 長さの追加

b（パディングビットが追加される前のメッセージの長さ）の64ビット表現が、前のステップの結果に追加されます。万が一、bが2^64より大きい場合は、bの下位64ビットのみが使用されます。（これらのビットは2つの32ビットワードとして追加され、前述の規則に従って下位ワードから追加されます。）

この時点で、結果のメッセージ（ビットとbでパディングした後）の長さは512ビットの正確な倍数になります。つまり、このメッセージの長さは16（32ビット）ワードの正確な倍数になります。結果のメッセージのワード数をM0 ... N-1とします。ここで、Nは16の倍数です。

3.3 ステップ3. MDバッファの初期化

4ワードのバッファ（A、B、C、D）を使用してメッセージダイジェストを計算します。ここで、A、B、C、Dはそれぞれ32ビットのレジスタです。これらのレジスタは、下位バイトから順に以下の16進数の値に初期化されます。

word A: 01 23 45 67

word B: 89 ab cd ef

word C: fe dc ba 98

word D: 76 54 32 10

3.4 ステップ4. 16ワードブロックでメッセージを処理する

まず、3つの32ビットワードを入力として受け取り、1つの32ビットワードを出力する4つの補助関数を定義します。

F(X,Y,Z) = XY v not(X) Z

G(X,Y,Z) = XZ v Y not(Z)

H(X,Y,Z) = X xor Y xor Z

I(X,Y,Z) = Y xor (X v not(Z))

各ビット位置において、Fは条件文として機能します。if X then Y else Zです。XYとnot(X)Zは同じビット位置に1を持つことがないため、関数Fはvの代わりに+を使用して定義することもできます。X、Y、Zの各ビットが独立かつバイアスがない場合、F(X,Y,Z)の各ビットも独立かつバイアスがないという点は興味深い点です。

関数G、H、Iは関数Fと同様に、X、Y、Zのビットから「ビット単位の並列処理」で出力を生成します。つまり、X、Y、Zの対応するビットが独立かつバイアスがない場合、G(X,Y,Z)、H(X,Y,Z)、I(X,Y,Z)の各ビットも独立かつバイアスなしとなります。関数Hは、入力のビット単位の「排他的論理和」または「パリティ」関数であることに注意してください。

この手順では、正弦関数から構築された64要素のテーブルT[1 ... 64]を使用します。T[i]はテーブルのi番目の要素を表し、これは4294967296×abs(sin(i))の整数部に等しくなります（iはラジアン単位）。テーブルの要素は付録に記載されています。

以下を実行します。

code:Process

/* Process each 16-word block. */

For i = 0 to N/16-1 do

/* Copy block i into X. */

For j = 0 to 15 do

Set Xj to Mi*16+j.

end /* of loop on j */

/* Save A as AA, B as BB, C as CC, and D as DD. */

AA = A

BB = B

CC = C

DD = D

/* Round 1. */

/* Let abcd k s i denote the operation

a = b + ((a + F(b,c,d) + Xk + Ti) <<< s). */

/* Do the following 16 operations. */

ABCD 0 7 1 DABC 1 12 2 CDAB 2 17 3 BCDA 3 22 4

ABCD 4 7 5 DABC 5 12 6 CDAB 6 17 7 BCDA 7 22 8

ABCD 8 7 9 DABC 9 12 10 CDAB 10 17 11 BCDA 11 22 12

ABCD 12 7 13 DABC 13 12 14 CDAB 14 17 15 BCDA 15 22 16

/* Round 2. */

/* Let abcd k s i denote the operation

a = b + ((a + G(b,c,d) + Xk + Ti) <<< s). */

/* Do the following 16 operations. */

ABCD 1 5 17 DABC 6 9 18 CDAB 11 14 19 BCDA 0 20 20

ABCD 5 5 21 DABC 10 9 22 CDAB 15 14 23 BCDA 4 20 24

ABCD 9 5 25 DABC 14 9 26 CDAB 3 14 27 BCDA 8 20 28

ABCD 13 5 29 DABC 2 9 30 CDAB 7 14 31 BCDA 12 20 32

/* Round 3. */

/* Let abcd k s t denote the operation

a = b + ((a + H(b,c,d) + Xk + Ti) <<< s). */

/* Do the following 16 operations. */

ABCD 5 4 33 DABC 8 11 34 CDAB 11 16 35 BCDA 14 23 36

ABCD 1 4 37 DABC 4 11 38 CDAB 7 16 39 BCDA 10 23 40

ABCD 13 4 41 DABC 0 11 42 CDAB 3 16 43 BCDA 6 23 44

ABCD 9 4 45 DABC 12 11 46 CDAB 15 16 47 BCDA 2 23 48

/* Round 4. */

/* Let abcd k s t denote the operation

a = b + ((a + I(b,c,d) + Xk + Ti) <<< s). */

/* Do the following 16 operations. */

ABCD 0 6 49 DABC 7 10 50 CDAB 14 15 51 BCDA 5 21 52

ABCD 12 6 53 DABC 3 10 54 CDAB 10 15 55 BCDA 1 21 56

ABCD 8 6 57 DABC 15 10 58 CDAB 6 15 59 BCDA 13 21 60

ABCD 4 6 61 DABC 11 10 62 CDAB 2 15 63 BCDA 9 21 64

/* Then perform the following additions. (That is increment each

of the four registers by the value it had before this block

was started.) */

A = A + AA

B = B + BB

C = C + CC

D = D + DD

end /* of loop on i */

3.5 ステップ5. 出力

出力として生成されるメッセージダイジェストは、A、B、C、Dです。つまり、Aの下位バイトから始まり、Dの上位バイトで終わります。

これでMD5の説明は完了です。C言語によるリファレンス実装は付録に記載されています。

4. 要約

MD5メッセージダイジェストアルゴリズムは実装が簡単で、任意の長さのメッセージの「指紋」、つまりメッセージダイジェストを提供します。同じメッセージダイジェストを持つ2つのメッセージを見つけるのに2^64回の演算が必要で、特定のメッセージダイジェストを持つ任意のメッセージを見つけるのに2^128回の演算が必要と推測されています。MD5アルゴリズムは、脆弱性について綿密に検証されてきました。しかしながら、これは比較的新しいアルゴリズムであり、この種の新しい提案の場合と同様に、更なるセキュリティ分析を行うことは当然のことです。

5. MD4とMD5の違い

MD4とMD5の違いは以下のとおりです。

1. 第4ラウンドが追加されました。

2. 各ステップに固有の加法定数が与えられます。

3. 第2ラウンドの関数gが(XY v XZ v YZ)から(XZ v Y not(Z))に変更され、gの対称性が弱まりました。

4. 各ステップで前のステップの結果を加算するようになりました。これにより、「アバランシェ効果」が高速化されます。

5. 第2ラウンドと第3ラウンドで入力ワードにアクセスする順序が変更され、これらのパターンの類似性が弱まりました。

6. 各ラウンドのシフト量が近似的に最適化され、「アバランシェ効果」が高速化されました。各ラウンドのシフト量はそれぞれ異なります。

参考文献

1 Rivest, R., "MD4 メッセージダイジェストアルゴリズム"、RFC 1320、MITおよびRSA Data Security, Inc.、1992年4月。

2 Rivest, R., "MD4 メッセージダイジェストアルゴリズム"、A.J. Menezes

およびS.A. Vanstone編、Advances in Cryptology - CRYPTO '90 Proceedings、303-311ページ、Springer-Verlag、1991年。

3 CCITT勧告X.509 (1988)、「ディレクトリ認証フレームワーク」

付録A - リファレンス実装

この付録には、RSAREF から抜粋した以下のファイルが含まれています。

プライバシー強化メール用暗号化ツールキット

global.h -- グローバルヘッダーファイル

md5.h -- MD5 用ヘッダーファイル

md5c.c -- MD5 用ソースコード

RSAREF の詳細については、<rsaref@rsa.com> までメールでお問い合わせください。

この付録には以下のファイルも含まれています。

mddriver.c -- MD2、MD4、および MD5 用テストドライバ

このドライバはデフォルトで MD5 用にコンパイルされますが、C コンパイラのコマンドラインでシンボル MD を 2 または 4 として定義すれば、MD2 または MD4 用にコンパイルできます。

この実装は移植性が高く、多くの異なるプラットフォームで動作するはずです。ただし、特定のプラットフォーム上で実装を最適化することは難しくありません。これは読者の責任で行ってください。たとえば、32ビットワードの最下位アドレスバイトが最下位バイトであり、アライメント制限がない「リトルエンディアン」プラットフォームでは、MD5Transform 内の Decode の呼び出しを型キャストに置き換えることができます。