原文：ftp://ftp.rfc-editor.org/in-notes/rfc1810.txt
サイト内関連リンク：RFC 1321 MD5
この文書はインターネットコミュニティの為の情報を提供する。この文書は如何なるインターネット標準も規定しない。この文書の配布は無制限である。
MD5は認証アルゴリズムであり、IPv6のデフォルト認証オプションとして提案されている。利用可能ならば、MD5アルゴリズムはヘッダを含むデータパケット全体を処理する。このRFCは、ソフトウェアやハードウェア上で高速なMDの実装方法と、現在利用可能なIP帯域幅をサポート出来るかどうかについて述べる。MD5は既存のハードウェア技術で256Mbps、ソフトウェアで87Mbpsで実装出来る。この速度では現在のIPの速度、例えば100MbpsのTCPや130MbpsのUDP over ATMをサポート出来ない。もしもMD5が既存技術を使ったネットワーク帯域幅をサポート出来ないのなら、将来のネットワークの速度増加に追いつけないだろう。このRFCはIPコミュニティにMD5のパフォーマンス限界に関する警告を発し、高速なIP実装上での利用の為に代替案を良く考えるよう示唆する事を意図している。
MD5は認証アルゴリズムであり、IPv6での認証オプション[1]のひとつとして提案されている。RFC1321はMD5アルゴリズムを説明し、実装の参考文献を示している[3]。利用可能ならば、MD5アルゴリズムは(揮発性のフィールドにはダミー値を使用して)ヘッダを含むデータパケット全体を処理する。このRFCでは、ソフトウェアやハードウェア上でどうすれば高速なMDの実装方法と、現在利用可能なIP帯域幅をサポート出来るかどうかについて述べる。
このRFCは、IPv6上での高速なチェックサム計算とセキュリティに関する一般的問題について考察する。IPv6はヘッダのチェックサムを持たない(IPv4は持つ[5])が、パケットの(揮発性フィールドがゼロ詰めされたヘッダも含め)本文全体を含む認証ダイジェストを提案している[1]。このRFCでは、特にその認証メカニズムのパフォーマンスに付いて述べる。
MD5のパフォーマンスが測定された。そのコードはRFCによるMD5実装の参考文献[3]の最適化されたバージョンであり、匿名FTPで利用可能[7]である。以下に示すのは、データブロックのオンチップキャッシュを防ぐように修正されたパフォーマンステスト"md5 -t"の結果である。
87 Mbps DEC Alpha (190 Mhz)
33 Mbps HP 9000/720
48 Mbps IBM RS/6000 7006 (PPC 601 @80 Mhz)
31 Mbps Intel i486/66 NetBSD
44 Mbps Intel Pentium/90 NeXTStep
52 Mbps SGI/IP-20 IRIX 5.2
37 Mbps Sun SPARC-10/51, SPARC-20/50 SunOS 4.1.3
57 Mbps Sun SPARC-20/71 SunOS 4.1.3
これらの速度は現在利用可能なIP帯域幅(例えば100MbpsのTCPや130MbpsのUDP、あるいはSun SPARC-20/71における UDP over a Fore SBA-200 ATMホストインターフェイス等)に追いついていない。
100Mbps相当の値がDEC Alpha (190 Mhz)上で報告されている。この値はオンチップのデータキャッシュの影響を反映している。インメモリ・オフチップキャッシュ・オンチップキャッシュのどのパフォーマンス対策が、よりIPパフォーマンスに影響があるのかは明らかではない。
MD5アルゴリズムはブロック連鎖のハッシュアルゴリズムである。最初のブロックは初期値でハッシュされ、ハッシュ値を生成する。そのハッシュ値はシード値と合計され、その結果が次のブロックのシード値となる。最後のブロックが計算された時、その"次のシード値"は、ストリーム全体のハッシュ値となる。このようにブロックのシード値は、そのハッシュ値とその前のブロックのシード値の両方に依存している。結果として、ブロックを並列にハッシュ処理する事は出来ない。
各々の16ワード(64バイト)ブロックは、4ワードの中間ハッシュを使用しながら64の基本ステップを踏んでハッシュされ、最後に中間ハッシュに折りたたまれる。64のステップは4ステップの16グループから成り、中間ハッシュワード毎に1ステップである。このRFCでは以下の表記法を使用する。(RFC-1321[3]より)
| A,B,C,D | 中間ハッシュワード |
| X[i] | 入力データブロック |
| T[i] | 正弦テーブル参照 |
| << i | iビットのローテイト |
| F | 3つの引数を取る論理関数 |
Xの添え字 I と << は各ステップで固定されている為、ここでは省略する。4種類の論理関数があるが、同じく省略する。各4ステップのグループは以下のようなものである。
A = B + ((A + F(B,C,D) + X[i] + T[i]) << i)
D = A + ((D + F(A,B,C) + X[i] + T[i]) << i)
C = D + ((C + F(D,A,B) + X[i] + T[i]) << i)
B = C + ((B + F(C,D,A) + X[i] + T[i]) << i)
これは以下に示すような一般的な表現形式を持つ事に注意して欲しい。関数'f'の複雑性の為、これらの等式をこれより小さい逐次形に変換する事は出来ない。
A = f(D); B = f(A); C = f(B); D = f(C)
各ステップは、二つのテーブル参照、ひとつのローテイト、3要素の論理演算、4つの加算から構成される。最高の並列化の候補では、前のステップの結果を可能な限り長く待ちながら、F(x,y,z)を最後のステップに任せる。結果ツリーは以下の通り。
(t0) B* C C D X T
| | | | | |
| | | | | |
\/ \/ \ /
t1 op op A + X T
\ / \ / | |
\ / \ / | |
\/ \/ \ /
t2 op + (t0) B* C C D A +
\ / | | | | \ /
\ / \ | | / \ /
\ / \\// \/
t3 + t1 op +
| \ /
| \ /
| \ /
t4 << B* t2 + B*
\ / \ /
\ / << /
\ / \ /
t5 + t3 +
| |
| |
| |
A** A**
二進木 最適化されたハードウェアツリー
この図は、それぞれの演算が1単位時間消費すると仮定している。ツリーでは、前のステップに依存する項目をB*として、次のステップが依存する項目をA**として示している。二進木の順序はオーバーラップ出来ないが、最適化されたハードウェアツリーでは(1単位時間だけ)可能である。
ブロック間の処理を無視すると、入力ワード毎に4ステップの処理が存在する。アルゴリズム全体の速度は、入力1ワードが処理される帯域幅に対し我々がどれだけ速くこれらの4ステップを処理できるかに依存する。
二進木ではアルゴリズムの各ステップ毎に5単位時間を消費し、最高で3-wayの並列化を可能にしている(時刻t1)。ソフトウェアにおいて、これはワード毎に 5 * 4 = 20 の命令を消費する事を意味する。M MIPSの能力の計算機は、M/20 * 32 Mbpsのデータ帯域幅をサポート出来る。つまり、ビット毎秒はMIPS値の1.6倍に等しい。したがって、100MIPS機は160Mbpsのストリームをサポート出来る。
並列ソフトウェアのMbps値 = 1.6 * MIPS
これはレジスタの読み書きが計算全体でオーバーラップすると仮定している。並列処理がなければステップ毎に8演算、ワード毎に4ステップが必要なので、ワード毎に32演算存在する事になる。すなわち、Mbps値はMIPS値と一致する。
直列ソフトウェアのMbps値 = MIPS
MIPS推定としてSpecInt92を使用した予測値は、評価速度と比較する事が出来る[2]。
| Spec-Int92 | 予測上限 | MD5評価 | マシン |
| 122 | 122-195 | 87 Mbps | DEC Alpha (190 Mhz) |
| 48 | 48- 77 | 33 Mbps | HP 9000/720 |
| 88 | 88-141 | 48 Mbps | IBM RS/6000 7006 (PPC 601 @80 Mhz) |
| 32 | 32- 51 | 31 Mbps | Intel i486/33 NetBSD |
| 90 | 90-144 | 44 Mbps | Intel Pentium/90 NeXTStep |
| 90 | 90-144 | 52 Mbps | SGI/IP-20 IRIX 5.2 |
| 65 | 65-104 | 37 Mbps | Sun SPARC-10/51 SunOS 4.1.3 |
| 126 | 126-202 | 57 Mbps | Sun SPARC-20/71 SunOS 4.1.3 |
ハードウェアの速度は、各ステップ毎に3単位時間、すなわち、1入力ワード毎に3 * 4 = 12単位時間となる。Nナノ秒に1処理(例えば32ビット加算)を行う能力のハードウェアは、32/12/N bps、すなわち 2/3N bps(訳注: 8/3N の誤りだと思うのですが……)のデータ帯域幅をサポート出来る。
ハードウェアのMbps値 = 8/3N * 1,000
CMOSでは、演算(レジスタの取得と保存を含む32ビット加算)は約5.2ナノ秒消費する[6]。最も高度に並列化された実装では6クロックかかり、32ビットワード毎に31.2ナノ秒、すなわち256Mbpsという結果になる[6]。これは、既存のハードウェアの速度(622Mbpsを越える回線速度(ATM))に追いていない。
なおIPv4はインターネットチェックサム[5]を使用するが、このチェックサムは32ビット幅単位において既存の低コストPLDでも1Gbpsを越えるパフォーマンスを出せる。その上このチェックサムは、部分的合計の計算と結果を小さくする事で並列化も可能である。
IPv6の認証メカニズムのパフォーマンスを向上させる幾つかの方法が存在する。ひとつはアルゴリズムを若干変更する事でハードウェア上のMD5のパフォーマンスを増す方法、もうひとつは代替アルゴリズムを提案する方法である。このRFCは、高速ハードウェア実装向けのMD5の修正について簡潔に議論する。MD5の3.5倍の速度を可能にする代替アルゴリズムが別の場所で議論されている[6]。
ブロック順序への感度を確実にする為に、MD5はブロック連鎖を使用する。ブロック連鎖は任意の並列化(これはユーザーに対しても、なりすましに対しても利益となり得る)を妨げる。MD5はより高い帯域幅を収容出来るように若干変更可能である。I番目のブロックが"I mod K"番目の連鎖の一部となるといった、独立したシード値から処理される事前定義の有限個のブロックがなくてはならない。結果のK桁はそれ自身をメッセージからダイジェスト化し、単一ブロックのアルゴリズムを使うMD5エンコードに出来る。このアイデアは著者とRSAのBurt Kaliskiにより、独立して提案された。
この目的は、なりすましに独断的な力を与える事なく、現在の処理速度に対し十分な帯域幅を提供する為の定型的並行処理をサポートする事である。十分なセキュリティ水準を提供する事を確実にする為に、さらなる分析が必要である。
現在の技術とネットワークの帯域幅にとっては4-wayの並列連鎖で十分、16-wayのチェインなら理想的だろう。CMOSハードウェアにおいては、4-wayで1Gbpsの帯域幅をサポートするだろう。この連鎖並列化は、完全なダイジェストのブロック（ダイジェスト毎に4ワード、ブロック毎に16ワード）を生成する為に、4-wayの倍数でなくてはならない。この変更は、現在のMD5アルゴリズムの実装が持つペナルティを防ぎながら、MD5の目的を達成すると信じられている。
この文書全体がIPv6でのセキュリティ提供のメカニズムについて述べている。MD5はIPv6トラフィックの為の選択可能な認証メカニズムのデフォルトである。このRFCは特に、利用可能なハードウェアで高帯域をサポート出来ないMD5のようなセキュリティメカニズムは、その展開、そして最終的にはそれが維持しようとしているシステムのセキュリティを危うくしてしまうかもしれない事を指摘している。
IPv6の要求文書は、IPv6の実装はIPv4に比較してパフォーマンスに妥協すべきではないと強調している。IPv6の増大した機能性にもかかわらず、である。IPv6の"要求される選択可能な"コンポーネントは、この同じ基準を維持するはずである。MD5はパフォーマンスを損なう為、IPv6で要求されるデフォルトオプションとしての使用は再検討されるべきである。
要求される認証オプションのデフォルトとしてMD5を使用する事は、広帯域のシステムではセキュリティを危うくするかもしれない。なぜならこのオプションを有効にする事はパフォーマンスの低下を引き起こし、IPv6オプションとしてこのオプションが含まれる事を挫折させ、結果としてこの認証オプションが全く無効にされてしまうかもしれない為である。
IPv6上で最初から代替メカニズムを利用可能にする事は、高パフォーマンスシステムでの認証利用にとって重要である。これには複数の"要求される"認証アルゴリズムの規約を必要とするだろう。ひとつは遅いが強力だと思われるもの、ひとつは速いが信頼性は劣るものである。
MD5は、現状の技術ではハードウェア上で256Mbps、ソフトウェア上で86Mbpsを越える速度で実装する事は出来ない。MD5はIPv6で提案されている認証オプションであり、IPv6は130MbpsUDPの能力を持つ既存のネットワーク技術をサポートすべきプロトコルである。
結果として、既存ネットワークの速度においてIP認証をサポートする為にMD5を使用する事は出来ない。将来MD5は技術の進歩によってより広帯域をサポートするかもしれないが、これは同じようなネットワーク技術の進歩に埋め合わせられるだろう。もしもMD5が既存技術を使用して既存のネットワーク帯域をサポート出来ないならば、それは将来のネットワーク速度の上昇に付いていく事も出来ないだろう。このRFCは、既存技術(CMOSハードウェア)が既存のネットワーク帯域(1Gbps)をサポート出来るように、16-wayブロックチェインをサポートするようにMD5を修正する事を推奨する。さらに、高速ネットワークで使用出来るMD5の代替え案について考察する事をそれ以上に推奨する。
著者はこの文書の内容のレビュー関して、BBN社のSteve Kent at BBN、RSA社のBurt Kaliski, Victor Chang, Steve Burnett、NRL社のRan Atkinson、ISI社のHPCC部門に感謝したい。Burtは、この文書で提案したブロック並列化の修正を独自に提案した。
[1] Atkinson, R., "IPv6 Authentication Header", Work in Progress, Naval Research Lab, February 1995.
[2] DiMarco, J., "Spec Benchmark table, V. 4.12",<ftp://ftp.cfd.toronto.edu/pub/spectable>.
[3] Rivest, R., "The MD5 Message-Digest Algorithm", RFC1321, MIT LCS & RSA Data Security, Inc., April 1992.
[4] Partridge, C., and F. Kastenholz, "Technical Criteria for Choosing IP The Next Generation (IPng)", RFC 1726, BBN Systems and Technologies, FTP Software, December 1994.
[5] Postel, J., "Internet Protocol - DARPA Internet Program Protocol Specification," STD 5, RFC 791, USC/Information Sciences Institute, September 1981.
[6] Touch, J., "Performance Analysis fo MD5," to appear in ACM Sigcomm '95, Boston.
[7] Touch, J., Optimized MD5 software, <ftp://ftp.isi.edu/pub/hpcc-papers/touch/md5-opt.tar>.
Joe Touch
Information Sciences Institute
University of Southern California
4676 Admiralty Way
Marina del Rey, CA 90292-6695
USA
Phone: +1 310-822-1511 x151
Fax: +1 310-823-6714
URL: ftp://ftp.isi.edu/pub/hpcc-papers/touch
EMail: touch@isi.edu