白書9：SHA-1デバイスは今でも十分にセキュア(安全)か?

2005年10月03日

54.00K

要約

2005年、中国の研究者グループが、セキュアハッシュアルゴリズム(SHA-1)の強度に対して攻撃しました。この白書では、その攻撃について検討し、またセキュアハッシュアルゴリズムが以前に考えられていた衝突耐性よりも若干低いものの、マキシムが提供するSHA-1メモリデバイスのセキュリティには影響がないことを証明します。したがって、マキシムのSHA-1メモリデバイス(DS1963S、DS1961S、DS2460、DS28CN01、DS28E01-100、およびDS2432)は、アクセサリ/周辺機器の認証や耐タンパー性を備えた証明可能なメモリアプリケーションのための、低コストで効果的なソリューションとして引き続き提供されます。

はじめに

マキシムのSHA-1メモリデバイスは、アクセサリ/周辺機器の認証やタンパー耐性を備えた証明可能なメモリアプリケーションのための、低コストで極めて効果的なソリューションです。SHA-1デバイスを認証する機能は、大量消耗品、高価なハードウェア、ハードウェアのライセンス管理、ビルの入出管理、または自販機など、偽造者を寄せ付けないようにすることが要求されるアプリケーションで役立つ機能です。

根本的に、これらのデバイスの実用性は、米国立標準技術研究所(NIST)が｢Federal Information Processing Standards Publication 180-1 (FIPS PUB 180-1)｣と｢ISO/IEC 10118-3｣で規定しているとおり、セキュアハッシュアルゴリズムの頑強性とセキュリティに依存します。2005年、中国の研究者グループは、このアルゴリズムの強度に対していかに攻撃したのかを示す報告書を発表しました(注1を参照)。このアプリケーションノートでは、SHA-1を使用するアプリケーションによっては、提示されたセキュリティを見直すことが必要になる可能性はあるものの、マキシムのSHA-1メモリデバイスのセキュリティは、この研究の主張に脅かされることがないことを示します。

SHA-1のダイジェストに対する攻撃

｢FIPS PUB 180-1｣は、凝縮されたデータ内容をセキュアな方法で計算するための規格としてSHA-1を定義しています。このドキュメントで規定されているとおり、このアルゴリズムは2つの請求、｢(1)所定のメッセージダイジェストに対応するメッセージを見つけること、および(2)同じメッセージダイジェストを生成する2つの異なるメッセージを見つけることが、計算上、実行不可能である｣ので、セキュアであると考えられています。1つめの主張が意味することは、SHA-1の出力結果には、アルゴリズムに入力されたフルテキストを見つけられるほど十分な情報が含まれていないということ(つまり、このアルゴリズムが不可逆であるということ)、また、ダイジェスト(出力)が入手できたとしても、対応するメッセージ(入力)を見つけるには膨大なリソースと時間が必要になるということです。2つめの主張が意味することは、同じ出力を生成する2つの一意の入力を見つけるには、膨大なリソースと時間が必要となるということ(つまり、このアルゴリズムには衝突耐性があるということ)です。これらの想定は、同じダイジェストを持つ2つのメッセージが存在しないことを断言しているわけではなく、これらの2つのメッセージを見つけることが極めて困難であるということを意味しているだけです。

衝突(同じダイジェストを共有する2つのメッセージ)を見つけるのに必要なハッシュ演算の数の理論的な限界は、2⁸⁰です(注2を参照)。前述の研究者のSHA-1に対する攻撃は、この限界が2⁶⁹の演算にまで減るというものです。この主張は、｢計算上、実行不可能である特質｣が実質的に2¹¹だけ低減されるため、SHA-1の2つめの主張を弱体化することになります。ただし、｢同じメッセージダイジェストを生成する2つの異なるメッセージを見つけることが計算上、実行不可能｣ではなくなってしまうわけではなく、以前に考えられていたより少しだけ実行不可能の程度が低くなることを意味するにすぎません。さらに、研究者の主張は、｢所定のメッセージダイジェストに対応するメッセージを見つけることが計算上、実行不可能｣ではなくなってしまうことを意味するわけではありません。なぜなら、この新しい攻撃は、2つの入力メッセージを念入りに選択する能力に依存しているためです。所定のダイジェストに対応するメッセージ(ただし必ずしもそのメッセージとは限らない)を見つけるための、唯一のSHA-1のセキュリティ攻撃(証明済み)には、2¹⁶⁰回の演算を用いた総当りの検索を要します。

SHA-1アルゴリズムの2つめの主張は、中国の新しい研究によって弱体化されるものの、この研究が、SHA-1の1つめの主張に対する攻撃につながるという理由は一切ありません。要約すると、衝突耐性はおそらく若干低下していますが、SHA-1は依然として不可逆です。とはいえ、これは、タイムスタンピングやドキュメント公証など、ディジタル署名に依存するアプリケーションにとっては、憂慮すべき結果となり得ます。入力メッセージ内の情報の多くは各アプリケーションの状況に即したものであるため、アプリケーション固有の効果的な攻撃が中国の研究によってもたらされるかどうかは、現時点では依然として不明です。

メッセージ認証コード

マキシムのSHA-1メモリデバイスは、通信の両方向において、メッセージ認証コード(MAC)に依存しています。MACを計算するには、公開された入力文字列(メモリの内容、デバイスの一意のシリアル番号、およびランダムチャレンジで構成されている)を取得し、これを秘密鍵と組み合わせるだけです。これがSHA-1アルゴリズムの入力メッセージとなります。結果として得られるダイジェスト(すなわちハッシュ)をMACと呼びます。メッセージとともにMACを送信すると、送信者が秘密鍵を知っているということ、および送信中にデータの改竄が行われないことを証明するセキュアな手段が得られます。読み取り動作中、SHA-1メモリデバイスはMACで応答し、データが本物で、ホストがデータを正しく受け取ったことを証明します。書き込み動作中、ホストはMACを提供し、デバイスのメモリ内容に変更を加えることが許可されたこと、また、デバイスが新しいメモリ内容を正しく受け取ったことを証明します。

MACベースのセキュリティシステム上でアルゴリズムの攻撃に成功するには、秘密鍵を見つける必要があります。市販のほとんどのSHA-1メモリデバイスでは、この鍵は64ビットの書き込み専用の値になります(まもなく、より長い鍵を備えた最新デバイスが入手可能となります)。攻撃者は、デバイスに対してチャレンジを発行し、得られるMACを読み取った後、対応するMACが見つかるまで64ビットのすべての値を総当りで検索することが可能です。ただし、この作業には、2⁶⁴回のSHA-1演算が必要です。これは、64 CPU構成のCray X1スーパーコンピュータ上で、10年を超える計算時間を要することになります(注3を参照)。

所定の入力メッセージのダイジェストに対応するメッセージを見つけるには、2¹⁶⁰回の演算が必要です(秘密鍵を見つけるための2⁶⁴回をはるかに超える演算が必要です)。ここで説明する入力メッセージの長さは512ビットに固定されており、これらのビットのうち448ビットは、公開データとして知られているため、最も単刀直入な方法は、残りの64ビット(つまり、秘密鍵の値)の正しい値を見つけることです。｢所定のメッセージダイジェストに対応するメッセージを見つけることが、計算上、実行不可能である｣限り、秘密鍵の値を見つけるのに、総当りの検索以外に成功する攻撃はあり得ません。

ここで注意が必要ですが、秘密鍵を探すために必要な2⁶⁴回の演算の複雑さは、衝突する2つのメッセージを見つけるのに必要な2⁶⁹回の演算よりも少なくなりますが、攻撃の区分という観点からは比べものになりません。研究チームがSHA-1内の衝突を2⁵⁰回の演算で発見する方法を見出したとしても、秘密鍵の値を見つけるためには、依然として2⁶⁴回のSHA-1の演算が必要となります。この結果、2つの入力メッセージ間の衝突を見つけるための新しい攻撃を使用しても、特定の固定の入力メッセージに対する衝突を見つけることはできません。なぜなら、入力メッセージを慎重に選択する必要が生じるためです。

まとめ

SHA-1メモリデバイスに対する攻撃は詳細に記録されています。これらの攻撃は、デバイスが使用されているシステムに関連したものです(アプリケーションノート1098 ｢白書3：1-Wire SHA-1デバイスはなぜ安全なのか｣を参照)。ただし、公に読み取り可能なMACを使用して隠された秘密鍵を見つけるという攻撃は、選択したアルゴリズムの強度によって守られる唯一の既知の攻撃です。SHA-1の場合、衝突耐性と不可逆性という2つの異なる状態の強度でアルゴリズムが定義されていることがわかっています。2005年に中国の研究チームによって行われた攻撃によって、SHA-1アルゴリズムが、以前に考えられていたより若干衝突耐性が低いということがわかりましたが、マキシムが提供するSHA-1メモリデバイスのセキュリティにはこの攻撃による影響はありませんでした。

注

X. Wang、Y.L. Yin、H. Yu「Finding Collisions in the Full SHA-1」(Advances in Cryptology-Crypto'05)： http://www.infosec.sdu.edu.cn/paper/sha1-crypto-auth-new-2-yao.pdf (PDF, English only)
｢バースデイパラドックス｣があるため、SHA-1で衝突を検出する場合には、2⁸⁰の上限があります。基本的に、このパラドックスは、任意の2つの要素を出力のnビットに一致させようと試みるとき、非常に高確率で一致を見つけるのに、2⁽ⁿ⁾ではなく、2^(n/2)の要素を考慮するだけでよいということを意味しています。これは、すべてのハッシュについて、よく知られた暗号特性であり、出力内のビット数によってのみ決まります。
SHA-1アルゴリズムは、メッセージブロックの要素に対して、約1740の基本算術演算を実施します。余分な操作のために20%のオーバーヘッドを想定すると、アルゴリズム全体は、2100のクロックサイクルで動作することになります。819ギガフロップのピークパフォーマンスで動作する、64 CPU構成のCray X1スーパーコンピュータ(2005年時点におけるCrayの最大規模のシングルキャビネット構成)を使用しても、完全な参照テーブルを生成するのに12.4年の連続稼動が必要です。Crayが宣伝する64のキャビネットを備えた最大のX1システムでも2か月以上かかります。このように莫大な演算パワーを要するため、この種の攻撃は、桁違いのコストがかかることになります。