|
ネットワーク WG Request for Comments： 4270 分類： 情報提供 |
P. Hoffman VPN Consortium B. Schneier Counterpane Internet Security 2005年11月 |
このメモは、インターネットコミュニティに情報を提供するものです。 これは、いかなるインターネット標準をも定めるものではありません。 このメモの配布には制限はありません。
Copyright (C) The Internet Society (2005).
最近の、有名なハッシュアルゴリズムにおける予想以上の衝突攻撃の発表は、 人々に「インターネットプロトコルは、 変更される必要があるか否か？」、そして、 その場合、「どのように？」という疑問をもたらしました。 本書は、多くのプロトコルにおけるハッシュの利用法を要約し、 「その衝突攻撃は、どのようにプロトコルに影響を与え、 どのように影響を与えないか？」を検討し、 「どのようにデジタル証明書についての既知の攻撃を防ぐか？」を示し、 プロトコル設計者のために将来の方向性を検討します。
2004年の夏に、研究者のチームは、 「MD5ハッシュアルゴリズムは、 衝突攻撃の影響を受ける可能性がある」という具体的な証拠を示しました [MD5-attack]。 2005年初頭に、同じチームは、SHA-1 [RFC3174] の派生ハッシュアルゴリズムについて、同様の攻撃を実証し、 「通常、使われているSHA-1も、 大きな労力を費やせば影響を受ける(ただし、SHA-1が正しく動作した場合、 要求されるレベルにおいて。) [SHA-1-attack]」と予想しました。 2005年初頭にも、研究者たちは、MD5を署名するために [PKIX-MD5-construction] を使う具体的なPKIX証明書 [RFC3280] の構成を示しました。 そして、別の研究者が、MD5衝突を発見するための、 より速い手法(1.6GHzのコンピュータ上で8時間)を示しました [MD5-faster]。
これらの発表によって、暗号技術者、 プロトコル設計者および他の「このニュースについて(もし何かあれば)何をする必要があるか？」に関心ある人々による多くの議論がありました。 残念ながら、これらの議論には、そのニュースと、 「どのようにハッシュアルゴリズムがインターネットプロトコルにおいて使われているか？」の両方について誤った解釈に基づくものがありました。
ハッシュアルゴリズムは、暗号技術者によって、 様々なセキュリティプロトコル中に、 様々な目的でインターネットプロトコルスタックのすべてのレベルで使われています。 それらは、2つのセキュリティ属性をもつので使われています。： 「一方向」であることと、「衝突フリー」であることです。 (次章に、これらの属性についての詳細があります。 それらは、それらを破る観点から説明する方が容易です。) 最近の攻撃は、「これらのセキュリティ属性のひとつは、 真ではないこと」を実証しました。 「破綻したセキュリティ属性は、 多くの個別のインターネットプロトコルのセキュリティ全体には影響を与えない」可能性はあり、 一見、有望でさえありますが、保守的なセキュリティアプローチは、 ハッシュアルゴリズムを変更することです。 インターネットプロトコルのコミュニティは、 SHA-1およびMD5(特にMD5)から段階的に、 よりセキュアなハッシュアルゴリズムに移行する必要があります。
本書は、「何が現在、ハッシュアルゴリズムについて知られているか？」と、 それらを使うインターネットプロトコルについて、要約します。 本書は、「どのように、MD5とSHA-1について現在、 知られている問題を避けるか？」と、 「予想された攻撃が現実となった場合、 何を考慮するか？」についても助言します。
現状を要約すると、下記のようになります。：
「完璧な(perfect)」ハッシュアルゴリズムは、 いくつかの基本的な属性をもちます。 そのアルゴリズムは、あらゆる大きさのデータ(通常は、 メッセージ)を固定長の結果に変換します。 その結果の長さは、「ハッシュ長」と呼ばれ、 しばしば、"L"と表記されます。 ハッシュアルゴリズムを特定のデータに適用した結果は、 そのデータについての「ハッシュ値」と呼ばれます。 あらゆる大きさの2つの異なるメッセージも、 メッセージ間の類似性の程度に関わらず、 同一のハッシュ値となる可能性が極めて低い必要があります。
この記述は、2つの数学的結果をもたらします。 同一のハッシュ値をもつメッセージのペア(M1とM2)を発見することは、 2L/2の試行を要します。 これは、あらゆる合理的なハッシュ長についても、 解決不可能な問題です(衝突フリー)。 また、メッセージ(M1)があるとき、M1と同一のハッシュ値をもつ、 何らかの他のメッセージ(M2)を発見するのには、 2Lの試行を要します。 これは、さらに解決困難な問題です(一方向)。
「これは、 完璧なハッシュアルゴリズムについての記述であること」に注意してください。 そのアルゴリズムが完璧ではない場合、攻撃者は、 同一のハッシュ値をもつ2つのメッセージを発見するために、 より少ない労力しか費やさないで済みます。
2種類の攻撃があります。
「衝突フリー」属性に対する攻撃：
「一方向」属性に対する攻撃：
この2つのプリイメージ攻撃は、よく似ています。 「第1プリイメージ攻撃」において、あなたは、 ハッシュ値を知っていますが、その元となったメッセージは知らず、 あなたは、既知のハッシュ値をもつ、 あらゆるメッセージを発見することを望みます。 「第2プリイメージ攻撃」において、あなたは、 あるメッセージをもっており、あなたは、 同一のハッシュをもつ2番目のメッセージを発見することを望むます。 一方の種類のプリイメージを発見できる攻撃は、 しばしば、他方のものも発見できます。
プロトコル中のハッシュアルゴリズムの利用を分析するとき、 「2つのハッシュの属性のどちらが重要か？」を識別することが重要です。 特に今は、「衝突フリー属性は、現在、 有名なハッシュアルゴリズムについて、 弱くなりつつあること」が重要です。 「どちらの主体が、 ハッシュ化された素材を選択するか？」を判断することが確かに重要です。 さらに、以前のいくつかの作業(特に、 [PKIX-MD5-construction] )によって示されたように、「どの主体が、 そのハッシュ化されたオブジェクトの先頭にある素材を予測できるか？」を考慮することも重要です。
現在、知られているMD5およびSHA-1に対する実際の攻撃(もしくは、 ほぼ実際の攻撃)のすべては、「衝突攻撃」です。 これは、幸いなことです。： ハッシュアルゴリズムに対する顕著な「第1プリイメージ攻撃」と「第2プリイメージ攻撃」は、 本書の後方に書かれているように、現実世界において、 「衝突攻撃」より破壊的なものとなります。
「現在の『衝突攻撃』は、少なくとも、 2つのメッセージの一方に『メッセージのビット中に一定の構造をもつこと』を要求すること」に注意することも重要です。 これは、「『両者が同一のハッシュ値をもち』かつ『現実世界の攻撃において使える』ような2つのメッセージを発見することは、 単に同一のハッシュ値をもつ2つのメッセージを発見することより困難であること」を意味します。
ハッシュアルゴリズムは、 多くの方法でインターネット上で使われています。 ハッシュアルゴリズムを使う大部分のプロトコルは、 「衝突攻撃」による害に免疫をもつようにするやり方で使っています。 これは、偶然ではありません。： 良いプロトコル設計者は、彼らのプロトコルを、可能な限り、 基づいている暗号技術(その暗号アルゴリズム自体についての攻撃を含む)における多くの将来の変更に耐えられるように開発します。
ハッシュアルゴリズムの利用は、下記の事項を含みます。：
上記の手法の中で、最初の2つのみが、 衝突攻撃によって影響を受けます。 そして、このときでさえ、限られた状況においてです。 これまで、「一般に、チャレンジ／レスポンス型プロトコルは、 影響を受けない」と信じられています。 なぜならば、その送信者は、 既に受信者によって保管されている秘密を認証しているからです。 「共有された秘密(shared secret)」によるメッセージ認証において、 「その秘密は、両者に知られている」という事実も、 あらゆる知覚しうる攻撃を防ぐと信じられています。 IETFプロトコルにおけるすべての鍵配布機能は、 両者から乱雑な入力を得ているので、その攻撃者には、 そのハッシュ化されたメッセージを構成する方法がありません。
デジタル署名プロトコル中に使われているハッシュアルゴリズムに対する衝突攻撃の背後にある基本的なアイディアは、 「攻撃者は、同一のハッシュ値をもつ2つのメッセージを作成し、 その片方に署名して、何らかの極悪非道な目的のために、 他方のメッセージ上にその署名を使う」ということです。 この攻撃の詳細部分は、使われているプロトコルと、 「その署名されたメッセージが示されたとき、その被害者は、 何をするか？」に依存します。
正当な例は、あなたが2つのメッセージを作成し、一方には、 「私は、この仕事の対価として$10払います」と書かれており、 他方には、「私は、 この仕事の対価として$10,000払います」と書かれている、という場合です。 あなたは、被害者となる者宛に最初のメッセージを提示し、 それらに署名してもらってから、その仕事をし、 2番目のメッセージを署名された認可に入れ、 置き換えられた署名のあるメッセージ(なおもその署名は検証されるもの)を示し、 より高額な金額を要求します。 その被害者が拒否する場合、あなたは、それらを法廷にもっていき、 2番目の署名されたメッセージを示します。
否認防止に対する大部分の攻撃は、 署名したとされるメッセージの十分性を評価する人間に依存しています。 ハッシュ衝突攻撃が行われた場合、 署名をねつ造したメッセージの署名が有効であるとすると、 元のメッセージ上の署名も有効です。 その被害者は、元のメッセージを再作成し、自身が署名したものを示し、 「その2つのハッシュ値は、同一であること」を示すことができます。 この偶然による確率は、2L分の1であり、これは、 MD5とSHA-1のどちらについても、極小です。
換言すれば、人間が署名されたメッセージを認可として使っている場合、 否認防止プロトコルにおいて、ハッシュ衝突攻撃を防ぐために、 その署名者は、 自身が署名した元のメッセージのコピーを保持する必要があります。 同一のハッシュとなる他のメッセージをもつメッセージは、 同一人物によって作成されなければならず、 いかなる既知の可能性がある状況においても、偶然によって発生しません。 「2つのメッセージが同一のハッシュ値をもつ」という事実は、 その署名の正当性の判断において、その人の心情に、 この法的な攻撃を失敗させるのに十分な疑念をもたらすにちがいありません。 (そして、 その攻撃者に対する意図的な詐欺の訴追をもたらす可能性があります。)
自動化された否認防止プロトコルにおけるハッシュ衝突攻撃の阻止は、 潜在的に、より困難です。 なぜなら、それらには、 「何が起きたか？」論じられるだけの十分な注意を払う人間が居ない可能性があるからです。 例えば、EDI (Electronic Data Interchange)アプリケーションにおいて、 通常、 署名されたメッセージの認証(authentication)の後に自動的に処理されます。 ハッシュ衝突の実際の影響を判定することは、 そのプロトコルの詳細な評価を要します。
デジタル証明書は、デジタル署名の特別な場合です。 一般に、「証明書には、 定型のフォーマットがある」という事実に起因して、 TTP (Trusted Third Party)に対する否認防止についての攻撃は、ありません。 デジタル証明書は、しばしば、インターネットプロトコルにおいて、 鍵管理のためと、あなたの通信相手を本人認証するために、 おそらく、ネットワークサービスへのアクセスを許可したり、 クレジットカード情報のような個人情報について、 その主体を信頼したりする前に使われています。
それゆえ、「その受け入れる主体が、『その証明書が正しく、 その証明書によって識別される人もしくはシステムを識別すること』を信頼できること」が重要です。 その攻撃者が、ただひとつの公開鍵を使って、 2つの異なる身元についての証明書を入手できる場合、その被害者は、 「ある人物が、誰か別人である」と信じるように騙される可能性があります。
2005年初頭に書かれたPKIX証明書についての衝突攻撃は、攻撃者が、 証明書の主部(body)が同一のハッシュ値をもつようにしてしまう2つの異なる公開鍵を作り出す能力に依存します。 この攻撃ができるためには、その攻撃者は、 「証明書が発行される前に、使われる身元を含む内容および構造」、 「その証明書中に含められるシリアル番号」および「その証明書についての有効期間の開始日と終了日」を予測できる必要があります。
この攻撃の有効な結果は、「ひとつの身元を使っている人は、 ひとつの公開鍵によって、ひとつのデジタル証明書を入手できるが、 『それは、異なる公開鍵による(ただし、 同一の身元と有効期限等をもつ)』ふりができること」です。 その2つの証明書中の身元は、同一であるので、おそらく、 このような攻撃が、その攻撃者を利するような現実世界の例は、ありません。 せいぜい、誰かが、「そのTTPが、同一の身元と、 2つの異なる公開鍵に基づくシリアル番号をもつ証明書を発行したことによって、 過ちをおかした」と主張する可能性がある程度です。 これは、まさに、「取りすぎ(far-fetched)」です。
「衝突攻撃は、 証明書上の(公開鍵のように)人間が読める情報が無い部分のみに影響を与えること」に注意することは、 非常に重要です。 人間が読める身元情報をもつ証明書を取得し、 その証明書を別の人間が読める身元についても有効にするような攻撃は、 単純な衝突攻撃より多くの努力を要します。
PKIX証明書を発行するTTPが上記の攻撃を避けることを望む場合、 彼らは、その攻撃によって得られる、 いかなる優位性をも根絶するために、 その証明書の他の署名された部分を十分に乱雑にすることによって、 攻撃を防ぐことができます。 示唆されたアイディアは、下記の事項を含みます。：
これらのメカニズムのいずれもが、その攻撃者が証明書の発行者を、 この攻撃の影響を受ける証明書を生成するように騙すために必要とする作業量を増やします。
セキュリティコミュニティにおいて、「今、何をすべきか？」について、 意見の対立があります。 本書のふたりの著者でさえ、「今、 何をすべきか？」について対立しています。
我々の一方(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は、256bitのハッシュ長をもちます。 この長さは、新しい攻撃が発見された場合に、我々に、 より大きなセキュリティの猶予を与えてくれます。 それまでは、これからの数年間、 暗号技術のコミュニティにおけるさらなる研究は、 ハッシュアルゴリズム設計の向上と、潜在的には、 さらにセキュアなハッシュアルゴリズムを指向する必要があります。
もうひとりの著者(Paul)は、「これは、 2つの理由で賢明ではない」と信じています。 まず、現在のプロトコル衝突攻撃は、 何ら認識可能な現実世界の影響をもつことが示していません。 さらに、「いずれのより強いハッシュアルゴリズムが、 長期的に良い選択であるのか？」は、まだ不明です。 あるアルゴリズムから別のアルゴリズムに移行することは、 典型的な暗号ユーザに不可避な相互運用可能性の欠如と、 混乱をもたらします。(当然ながら、 その暗号技術に基づくハッシュアルゴリズムの属性について、 コミュニティの合意が形成さる前に、 何らかの「現実的」な攻撃が定式化される場合、Paulは、 彼の意見を「今、SHA-256に移行する」に変えます。)
両著者は、「すべてのインターネットプロトコルが、 異なるハッシュアルゴリズムを、 より長いハッシュ値と共に使えるようにする作業が行われる必要があること」に合意しています。 幸い、今日の大部分のプロトコルは、既に、これが可能です。 不能なものは、すぐに修正される必要があります。
本書の著者陣は、開発中の新しいプロトコルについて、 同じように感じています。： Bruceは、「それらは、 最初からSHA-256を使い始める必要がある」と考えており、 Paulは、「それらは、 その新しいプロトコルが衝突攻撃の影響を受けないかぎり、 SHA-1を使う必要がある」と考えています。 あらゆる新しいプロトコルは、そのハッシュアルゴリズムのみならず、 そのすべての暗号アルゴリズムを変更することが可能でなければなりません。
本書の全体が、インターネットにおけるセキュリティを検討しています。
本書中の検討は、 「インターネットプロトコルに使われているハッシュアルゴリズムに対する唯一の攻撃は、 衝突攻撃である」と想定しています。 いくつかの顕著なプリイメージ攻撃 [Preimaging-attack] が既に発見されていますが、それらは、まだ現実的ではありません。 現実的(practical)なプリイメージ攻撃が発見された場合、これは、 劇的に多くのインターネットプロトコルに影響を与えます。 この場合、「現実的」とは、「それが、意味ある時間内に、 意味ある金額で攻撃者によって実行されうること」を意味します。 数兆ドルを費やし、ひとつの求めるハッシュ値、もしくは、 ひとつのメッセージに、数十年を要するプリイメージ攻撃は、 「現実的」ではありません。 数千ドルを費やし、数週間を要する攻撃は、 「現実的」である可能性が高いです。
| [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 2n 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月. |
両著者は、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.