ネットワーク WG
Request for Comments: 4270
分類: 情報提供

P. Hoffman
VPN Consortium
B. Schneier
Counterpane Internet Security
2005年11月

English

インターネットプロトコルにおける暗号技術的ハッシュ関数についての攻撃
(Attacks on Cryptographic Hashes in Internet Protocols)

このメモの位置づけ

このメモは、インターネットコミュニティに情報を提供するものです。これは、いかなるインターネット標準をも定めるものではありません。このメモの配布には制限はありません。

著作権表記

Copyright (C) The Internet Society (2005).

要旨

最近の、有名なハッシュアルゴリズムにおける予想以上の衝突攻撃の発表は、人々に「インターネットプロトコルは、変更される必要があるか否か?」、そして、その場合、「どのように?」という疑問をもたらしました。本書は、多くのプロトコルにおけるハッシュの利用法を要約し、「その衝突攻撃は、どのようにプロトコルに影響を与え、どのように影響を与えないか?」を検討し、「どのようにデジタル証明書についての既知の攻撃を防ぐか?」を示し、プロトコル設計者のために将来の方向性を検討します。

 

1.  はじめに English

2004年の夏に、研究者のチームは、「MD5 ハッシュアルゴリズムは、衝突攻撃の影響を受ける可能性がある」という具体的な証拠を示しました [MD5-attack]。2005年初頭に、同じチームは、SHA-1 [RFC3174] の派生ハッシュアルゴリズムについて、同様の攻撃を実証し、「通常、使われている SHA-1 も、大きな労力を費やせば影響を受ける(ただし、SHA-1 が正しく動作した場合、要求されるレベルにおいて。) [SHA-1-attack]」と予想しました。2005年初頭にも、研究者たちは、MD5 を署名するために [PKIX-MD5-construction] 使う具体的な PKIX 証明書 [RFC3280] の構成を示しました。そして、別の研究者が、MD5 衝突を発見するための、より速い手法(1.6 GHz のコンピュータ上で 8 時間)を示しました [MD5-faster]。

これらの発表によって、暗号技術者、プロトコル設計者および他の「このニュースについて(もし何かあれば)何をする必要があるか?」に関心ある人々による多くの議論がありました。残念ながら、これらの議論には、そのニュースと、「どのようにハッシュアルゴリズムがインターネットプロトコルにおいて使われているか?」の両方について誤った解釈に基づくものがありました。

ハッシュアルゴリズムは、暗号技術者によって、様々なセキュリティプロトコル中に、様々な目的でインターネットプロトコルスタックのすべてのレベルで使われています。それらは、2 つのセキュリティ属性をもつので使われています。: 「一方向」であることと、「衝突フリー」であることです。(次章に、これらの属性についての詳細があります。それらは、それらを破る観点から説明する方が容易です。)最近の攻撃は、「これらのセキュリティ属性のひとつは、真ではないこと」を実証しました。「破綻したセキュリティ属性は、多くの個別のインターネットプロトコルのセキュリティ全体には影響を与えない」可能性はあり、一見、有望でさえありますが、保守的なセキュリティアプローチは、ハッシュアルゴリズムを変更することです。インターネットプロトコルのコミュニティは、SHA-1 および MD5(特に MD5 )から段階的に、よりセキュアなハッシュアルゴリズムに移行する必要があります。

本書は、「何が現在、ハッシュアルゴリズムについて知られているか?」と、それらを使うインターネットプロトコルについて、要約します。本書は、「どのように、MD5 と SHA-1 について現在、知られている問題を避けるか?」と、「予想された攻撃が現実となった場合、何を考慮するか?」についても助言します。

現状を要約すると、下記のようになります。:

 

2.  ハッシュアルゴリズムとそれらに対する攻撃 English

「完璧な(perfect)」ハッシュアルゴリズムは、いくつかの基本的な属性をもちます。そのアルゴリズムは、あらゆる大きさのデータ(通常は、メッセージ)を固定長の結果に変換します。その結果の長さは、「ハッシュ長」と呼ばれ、しばしば、"L" と表記されます。ハッシュアルゴリズムを特定のデータに適用した結果は、そのデータについての「ハッシュ値」と呼ばれます。あらゆる大きさの 2 つの異なるメッセージも、メッセージ間の類似性の程度に関わらず、同一のハッシュ値となる可能性が極めて低い必要があります。

この記述は、2 つの数学的結果をもたらします。同一のハッシュ値をもつメッセージのペア(M1 と M2)を発見することは、2^(L/2) の試行を要します。これは、あらゆる合理的なハッシュ長についても、解決不可能な問題です(衝突フリー)。また、メッセージ(M1)があるとき、M1 と同一のハッシュ値をもつ、何らかの他のメッセージ(M2)を発見するのには、2^L の試行を要します。これは、さらに解決困難な問題です(一方向)。

「これは、完璧なハッシュアルゴリズムについての記述であること」に注意してください。そのアルゴリズムが完璧ではない場合、攻撃者は、同一のハッシュ値をもつ 2 つのメッセージを発見するために、より少ない労力しか費やさないで済みます。

2 種類の攻撃があります。

「衝突フリー」属性に対する攻撃:

「一方向」属性に対する攻撃:

この 2 つのプリイメージ攻撃は、よく似ています。「第 1 プリイメージ攻撃」において、あなたは、ハッシュ値を知っていますが、その元となったメッセージは知らず、あなたは、既知のハッシュ値をもつ、あらゆるメッセージを発見することを望みます。「第 2 プリイメージ攻撃」において、あなたは、あるメッセージをもっており、あなたは、同一のハッシュをもつ 2 番目のメッセージを発見することを望むます。一方の種類のプリイメージを発見できる攻撃は、しばしば、他方のものも発見できます。

プロトコル中のハッシュアルゴリズムの利用を分析するとき、「2 つのハッシュの属性のどちらが重要か?」を識別することが重要です。特に今は、「衝突フリー属性は、現在、有名なハッシュアルゴリズムについて、弱くなりつつあること」が重要です。「どちらの主体が、ハッシュ化された素材を選択するか?」を判断することが確かに重要です。さらに、以前のいくつかの作業(特に、[PKIX-MD5-construction] )によって示されたように、「どの主体が、そのハッシュ化されたオブジェクトの先頭にある素材を予測できるか?」を考慮することも重要です。

2.1.  現時点において既知の攻撃 English

現在、知られている MD5 および SHA-1 に対する実際の攻撃(もしくは、ほぼ実際の攻撃)のすべては、「衝突攻撃」です。これは、幸いなことです。: ハッシュアルゴリズムに対する顕著な「第 1 プリイメージ攻撃」と「第 2 プリイメージ攻撃」は、本書の後方に書かれているように、現実世界において、「衝突攻撃」より破壊的なものとなります。

「現在の『衝突攻撃』は、少なくとも、2 つのメッセージの一方に『メッセージのビット中に一定の構造をもつこと』を要求すること」に注意することも重要です。これは、「『両者が同一のハッシュ値をもち』かつ『現実世界の攻撃において使える』ような 2 つのメッセージを発見することは、単に同一のハッシュ値をもつ 2 つのメッセージを発見することより困難であること」を意味します。

 

3.  インターネットプロトコルはどのようにハッシュアルゴリズムを使っているか? English

ハッシュアルゴリズムは、多くの方法でインターネット上で使われています。ハッシュアルゴリズムを使う大部分のプロトコルは、「衝突攻撃」による害に免疫をもつようにするやり方で使っています。これは、偶然ではありません。: 良いプロトコル設計者は、彼らのプロトコルを、可能な限り、基づいている暗号技術(その暗号アルゴリズム自体についての攻撃を含む)における多くの将来の変更に耐えられるように開発します。

ハッシュアルゴリズムの利用は、下記の事項を含みます。:

上記の手法の中で、最初の 2 つのみが、衝突攻撃によって影響を受けます。そして、このときでさえ、限られた状況においてです。これまで、「一般に、チャレンジ/レスポンス型プロトコルは、影響を受けない」と信じられています。なぜならば、その送信者は、既に受信者によって保管されている秘密を認証しているからです。「共有された秘密(shared secret)」によるメッセージ認証において、「その秘密は、両者に知られている」という事実も、あらゆる知覚しうる攻撃を防ぐと信じられています。IETF プロトコルにおけるすべての鍵配布機能は、両者から乱雑な入力を得ているので、その攻撃者には、そのハッシュ化されたメッセージを構成する方法がありません。

 

4.  ハッシュ衝突攻撃とデジタル署名の否認防止 English

デジタル署名プロトコル中に使われているハッシュアルゴリズムに対する衝突攻撃の背後にある基本的なアイディアは、「攻撃者は、同一のハッシュ値をもつ 2 つのメッセージを作成し、その片方に署名して、何らかの極悪非道な目的のために、他方のメッセージ上にその署名を使う」ということです。この攻撃の詳細部分は、使われているプロトコルと、「その署名されたメッセージが示されたとき、その被害者は、何をするか?」に依存します。

正当な例は、あなたが 2 つのメッセージを作成し、一方には、「私は、この仕事の対価として $10 払います」と書かれており、他方には、「私は、この仕事の対価として $10,000 払います」と書かれている、という場合です。あなたは、被害者となる者宛に最初のメッセージを提示し、それらに署名してもらってから、その仕事をし、2 番目のメッセージを署名された認可に入れ、置き換えられた署名のあるメッセージ(なおもその署名は検証されるもの)を示し、より高額な金額を要求します。その被害者が拒否する場合、あなたは、それらを法廷にもっていき、2 番目の署名されたメッセージを示します。

否認防止に対する大部分の攻撃は、署名したとされるメッセージの十分性を評価する人間に依存しています。ハッシュ衝突攻撃が行われた場合、署名をねつ造したメッセージの署名が有効であるとすると、元のメッセージ上の署名も有効です。その被害者は、元のメッセージを再作成し、自身が署名したものを示し、「その 2 つのハッシュ値は、同一であること」を示すことができます。この偶然による確率は、2^L 分の 1 であり、これは、MD5 と SHA-1 のどちらについても、極小です。

換言すれば、人間が署名されたメッセージを認可として使っている場合、否認防止プロトコルにおいて、ハッシュ衝突攻撃を防ぐために、その署名者は、自身が署名した元のメッセージのコピーを保持する必要があります。 同一のハッシュとなる他のメッセージをもつメッセージは、同一人物によって作成されなければならず、いかなる既知の可能性がある状況においても、偶然によって発生しません。「2 つのメッセージが同一のハッシュ値をもつ」という事実は、その署名の正当性の判断において、その人の心情に、この法的な攻撃を失敗させるのに十分な疑念をもたらすにちがいありません。(そして、その攻撃者に対する意図的な詐欺の訴追をもたらす可能性があります。)

自動化された否認防止プロトコルにおけるハッシュ衝突攻撃の阻止は、潜在的に、より困難です。なぜなら、それらには、「何が起きたか?」論じられるだけの十分な注意を払う人間が居ない可能性があるからです。例えば、EDI(Electronic Data Interchange)アプリケーションにおいて、通常、署名されたメッセージの認証(authentication)の後に自動的に処理されます。ハッシュ衝突の実際の影響を判定することは、そのプロトコルの詳細な評価を要します。

 

5.  ハッシュ衝突攻撃と TTP からのデジタル証明書 English

デジタル証明書は、デジタル署名の特別な場合です。 一般に、「証明書には、定型のフォーマットがある」という事実に起因して、TTP(Trusted Third Party)に対する否認防止についての攻撃は、ありません。デジタル証明書は、しばしば、インターネットプロトコルにおいて、鍵管理のためと、あなたの通信相手を本人認証するために、おそらく、ネットワークサービスへのアクセスを許可したり、クレジットカード情報のような個人情報について、その主体を信頼したりする前に使われています。

それゆえ、「その受け入れる主体が、『その証明書が正しく、その証明書によって識別される人もしくはシステムを識別すること』を信頼できること」が重要です。その攻撃者が、ただひとつの公開鍵を使って、2 つの異なる身元についての証明書を入手できる場合、その被害者は、「ある人物が、誰か別人である」と信じるように騙される可能性があります。

2005 年初頭に書かれた PKIX 証明書についての衝突攻撃は、攻撃者が、証明書の主部(body)が同一のハッシュ値をもつようにしてしまう 2 つの異なる公開鍵を作り出す能力に依存します。この攻撃ができるためには、その攻撃者は、「証明書が発行される前に、使われる身元を含む内容および構造」、「その証明書中に含められるシリアル番号」および「その証明書についての有効期間の開始日と終了日」を予測できる必要があります。

この攻撃の有効な結果は、「ひとつの身元を使っている人は、ひとつの公開鍵によって、ひとつのデジタル証明書を入手できるが、『それは、異なる公開鍵による(ただし、同一の身元と有効期限等をもつ)』ふりができること」です。その 2 つの証明書中の身元は、同一であるので、おそらく、このような攻撃が、その攻撃者を利するような現実世界の例は、ありません。せいぜい、誰かが、「その TTP が、同一の身元と、2 つの異なる公開鍵に基づくシリアル番号をもつ証明書を発行したことによって、過ちをおかした」と主張する可能性がある程度です。 これは、まさに、「取りすぎ(far-fetched)」です。

「衝突攻撃は、証明書上の(公開鍵のように)人間が読める情報が無い部分のみに影響を与えること」に注意することは、非常に重要です。人間が読める身元情報をもつ証明書を取得し、その証明書を別の人間が読める身元についても有効にするような攻撃は、単純な衝突攻撃より多くの努力を要します。

5.1.  PKIX 証明書に対するハッシュに基づく攻撃の可能性を低減する English

PKIX 証明書を発行する TTP が上記の攻撃を避けることを望む場合、彼らは、その攻撃によって得られる、いかなる優位性をも根絶するために、その証明書の他の署名された部分を十分に乱雑にすることによって、攻撃を防ぐことができます。示唆されたアイディアは、下記の事項を含みます。:

これらのメカニズムのいずれもが、その攻撃者が証明書の発行者を、この攻撃の影響を受ける証明書を生成するように騙すために必要とする作業量を増やします。


6.  将来の攻撃とその影響 English

セキュリティコミュニティにおいて、「今、何をすべきか?」について、意見の対立があります。本書のふたりの著者でさえ、「今、何をすべきか?」について対立しています。

我々の一方(Bruce)は、「すべての者が、MD5 と SHA-1 の両方において実証された弱点に起因して、今、SHA-256 [SHA-256] に移行し始める必要がある」と信じています。米国の NSA(National Security Agency)には、古い格言があります。: 「攻撃が上手になることはあっても、下手になることはない。」現在の MD5 に対する衝突攻撃は、1 台のコンピュータ上で容易に遂行できます。SHA-1 に対する衝突攻撃は、今日では、可能性からはほど遠い状況ですが、時間の経過で向上します。パニックになる前に(事後的ではなく)、新しいハッシュ標準に移行することが選好されます。ちょうど、我々が NSA 内部で発見された何らかの知られていない脆弱性に起因して、SHA-0 から SHA-1 に移行したように、我々は、これらの最近の攻撃に起因して、SHA-1 から SHA-256 に移行する必要があります。SHA-256 は、256 bit のハッシュ長をもちます。この長さは、新しい攻撃が発見された場合に、我々に、より大きなセキュリティの猶予を与えてくれます。それまでは、これからの数年間、暗号技術のコミュニティにおけるさらなる研究は、ハッシュアルゴリズム設計の向上と、潜在的には、さらにセキュアなハッシュアルゴリズムを指向する必要があります。

もうひとりの著者(Paul)は、「これは、2 つの理由で賢明ではない」と信じています。まず、現在のプロトコル衝突攻撃は、何ら認識可能な現実世界の影響をもつことが示していません。さらに、「いずれのより強いハッシュアルゴリズムが、長期的に良い選択であるのか?」は、まだ不明です。あるアルゴリズムから別のアルゴリズムに移行することは、典型的な暗号ユーザに不可避な相互運用可能性の欠如と、混乱をもたらします。(当然ながら、その暗号技術に基づくハッシュアルゴリズムの属性について、コミュニティの合意が形成さる前に、何らかの「現実的」な攻撃が定式化される場合、Paul は、彼の意見を「今、SHA-256 に移行する」に変えます。)

両著者は、「すべてのインターネットプロトコルが、異なるハッシュアルゴリズムを、より長いハッシュ値と共に使えるようにする作業が行われる必要があること」に合意しています。幸い、今日の大部分のプロトコルは、既に、これが可能です。不能なものは、すぐに修正される必要があります。

本書の著者陣は、開発中の新しいプロトコルについて、同じように感じています。: Bruce は、「それらは、最初から SHA-256 を使い始める必要がある」と考えており、Paul は、「それらは、その新しいプロトコルが衝突攻撃の影響を受けないかぎり、SHA-1 を使う必要がある」と考えています。あらゆる新しいプロトコルは、そのハッシュアルゴリズムのみならず、そのすべての暗号アルゴリズムを変更することが可能でなければなりません。


7.  セキュリティについての考慮事項 English

本書の全体が、インターネットにおけるセキュリティを検討しています。

本書中の検討は、「インターネットプロトコルに使われているハッシュアルゴリズムに対する唯一の攻撃は、衝突攻撃である」と想定しています。いくつかの顕著なプリイメージ攻撃 [Preimaging-attack] が既に発見されていますが、それらは、まだ現実的ではありません。現実的(practical)なプリイメージ攻撃が発見された場合、これは、劇的に多くのインターネットプロトコルに影響を与えます。この場合、「現実的」とは、「それが、意味ある時間内に、意味ある金額で攻撃者によって実行されうること」を意味します。数兆ドルを費やし、ひとつの求めるハッシュ値、もしくは、ひとつのメッセージに、数十年を要するプリイメージ攻撃は、「現実的」ではありません。数千ドルを費やし、数週間を要する攻撃は、「現実的」である可能性が高いです。

 

8.  参考情報

[MD5-attack]

X. Wang, D. Feng, X. Lai, and H. Yu,

"Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD",

2004年 8月,
 <http://eprint.iacr.org/2004/199>.
 

[MD5-faster]

Vlastimil Klima,

"Finding MD5 Collisions - a Toy For a Notebook",

2005年 3月,
 <http://cryptography.hyperlink.cz/md5/MD5_collisions.pdf>.
 

[PKIX-MD5-construction]

Arjen Lenstra and Benne de Weger, "On the possibility of constructing meaningful hash collisions for public keys",

2005年 2月,
 <http://www.win.tue.nl/~bdeweger/CollidingCertificates/ddl-final.pdf>.
 

[Preimaging-attack]

John Kelsey and Bruce Schneier,

"Second Preimages on n-bit Hash Functions for Much Less than 2^n Work",

2004年11月,
 <http://eprint.iacr.org/2004/304>.
 

[RFC3174]  

Eastlake, D. and P. Jones,

"US Secure Hash Algorithm 1 (SHA1)",

RFC 3174, 2001年 9月.
 

[RFC3280] Housley, R., Polk, W., Ford, W., and D. Solo,
 "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile",
RFC 3280(English), 2002年 4月.
 
[SHA-1-attack]

Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu,

"Collision Search Attacks on SHA1",
2005年 2月,
 <http://theory.csail.mit.edu/~yiqun/shanote.pdf>.
 

[SHA-256]

NIST,

"Federal Information Processing Standards Publication (FIPS PUB) 180-2, Secure Hash Standard",

2002年 8月.

              

付録 A.  謝辞

両著者は、IETF コミュニティに、特に、貢献してくださった SAAG のメーリングリストにおいて活発な方々に感謝します。我々は、初版に収まった初期の素材をていきょうしてくださった Eric Rescorla と、本書の初版について特筆されるコメントをしてくださった Arjen Lenstra と Benne de Weger にも感謝します。

 

著者のアドレス

Paul Hoffman
VPN Consortium

EMail: paul.hoffman@vpnc.org

Bruce Schneier
Counterpane Internet Security

EMail: schneier@counterpane.com


翻訳者のアドレス


宮川 寧夫

独立行政法人 情報処理推進機構

セキュリティセンター

EMail: miyakawa@ipa.go.jp

 

著作権表記全文

Copyright (C) The Internet Society (2005).

This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.

This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

知的財産権

The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights.  Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.

Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.

The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard.  Please address the information to the IETF at ietf-ipr@ietf.org.

謝辞

Funding for the RFC Editor function is currently provided by the Internet Society.