(6) SHA-1の強衝突耐性突破まで

crypto tech

本記事は 暗号学一人アドベントカレンダー 第6日目(相当)の記事です。

今回の内容はSHA-1が現実的に突破されたというSHAtteredの論文をもとに、SHA-0/SHA-1への攻撃がいかにして行われたかの概要と、何がまずかったか、を見ていきます。

簡単なSHA-1の仕組み

SHA-1, SHA-2はMerkle-Damgård構造という、固定の初期化ベクトルとメッセージに対して圧縮関数を繰り返し適用することで最終的な出力を得る方式を取ります。SHA-0/1/2はそれぞれこの圧縮関数が異なるため性質が異なっています。SHA-0の圧縮関数が脆弱であることが判明したため、SHA-1はこのSHA-0の圧縮関数にbitwise rotationが1個加わって現在の形になっています。SHA-2はこれらとは全く異なる圧縮関数を使用しています。

SHA-0に対する攻撃とSHA-1への応用

SHA-0に対する攻撃で、最終的なSHA-1の攻撃に影響が特に大きかったものとして、Differential Collisions in SHA-0 (Chabaud and Joux, 1998)で紹介されている差分解読法(Differential cryptanalysis) による衝突攻撃があります。大まかにいうと、入力の特定1バイトを変えたときに内部の状態ビット（圧縮関数にかけられる値の片方）がどのように変化するかを追跡し、それのパスが構築可能であることを見つけた、というものです。SHA-1はこれを解決するハズでしたが、実はこの問題は繰り返し現れることとなり、結果として差分解読に弱い圧縮関数を使ったことがSHA-1の衝突が見つかりやすい原因の一つになったといえるでしょう。また、この論文では、local collisionという内部状態が6サイクルで同じ値に戻る、という性質も明らかにしています。

SHAttered論文の4章の図

こういう背景を抑えた上で見ると4章のoverviewの図の意味が取りやすくなります。

  • SHA-1の圧縮関数は内部で16ラウンドごとに異なる関数を適用するため、最初の16ラウンドの内部状態までは操作がしやすいが、残りの64ラウンドは操作が困難である、というのが(1)で示してある部分。
  • 最終的な目的としては、1ブロック目で生み出したビットの差分(+)ã‚’2ブロック目で打ち消して(-)ゼロにする、ということを目指している(2)
    • さらっと書いてあるけど本来ランダムに見えるような出力を出すハズのものに対してこれをやるといってるのだから恐ろしいことです
  • そのために、"differential path"という、内部状態とメッセージの差分がどのように残りのステップで伝搬するかのパスを「都合のいいように」構築する"Non-Linear path"を作成する必要がある(3)
  • 最終的にはnear-collision block pair(4A, 4B)の形で解が得られる。
    • こういう組が2つ必要。
    • 結果、同一のPとSに対して、SHA-1(P+4A_1+4B_1+S) と SHA-1(P+4A_2+4B_2+S)の内部状態が同一になる。Mによって得られる内部状態が4A+4Bのブロックを経ることで打ち消されるため。

ちょっと消化不良気味ですがこんなところで、改めて読み込めたら書き直すかも。

過去記事の宣伝ですがSHA-2のfreestart collision attackというか圧縮関数の不動点が見つかったよという話について記事を書いてます。

次回はSHA-2の話すっ飛ばしてSHA-3(Keccak)などのMerkle-Damgårdでないハッシュの話の予定です。もしかしたら今日中。