SHAtteredとかいうやつ
リレーブログってやつです。はい。前回の方のブログはこちら。
今回のテーマはSHAtteredってやつです。
2022/5/9追記 打消線が引いてある部分は内容の正確性が微妙な部分です。詳しくは、追記の部分をご覧ください。
SHAttered?
Googleせんせー!初めて聞きました。何ですかそれは !?
しょうもないことを言っていますが前回の方がお題を出す時に簡単に教えてくれました(ありがたい)。
違うファイルなのにSHA-1ハッシュ値が同じになってしまうということのようです。ハッシュがハッシュしていない。
例えば、
この二つのファイルは青が基調のPDFと赤が基調のPDFで異なるものですが、同じハッシュ値になってしまうようです。これが攻撃成功の証拠として https://shattered.io/ にのっています。
ハッシュについて
ハッシュってなんでしょうということを簡単にまとめます。
あるメッセージ(ファイル)を受け取ったと考えます。そのメッセージをハッシュ関数を使ってハッシュ値を計算します。このハッシュ値はどんなサイズのメッセージに対しても固定のサイズを持ちます。また、メッセージが少しでも変わるとハッシュ値も変わるという性質を持っています。これで、受け取ったハッシュ値と受け取ったメッセージから計算したハッシュ値を比較すればファイルが正しいものか、改ざんされていないかということがわかるのです。これで大きなファイルを受け取った時にも簡単にそのファイルのチェックができます。ただ、ハッシュ値はメッセージよりも小さいということに注目してください。必ず複数のメッセージから同じハッシュ値が出てくるはずです。そこで、ハッシュ関数は一方向性を持っています。メッセージ→ハッシュ値は簡単にできるけど、ハッシュ値→メッセージは現実的に不可能ということです。これでハッシュ値がわかっても同じハッシュ値を持つメッセージを計算できなければ、メッセージを改竄したとしてもハッシュ値が変わるので改ざんを検出できます。しかし、今回は一方向性を計算量で殴れば破れちゃうじゃんという問題のようです。
じゃあどうなるの?
先ほども述べた通り、SHA-1のハッシュ値が異なるファイルなのに同一のものになってしまうというものです。契約書の金額を書き換えたりされてもわからないじゃん!という問題があります。しかし、2005年には理論的な攻撃発見されていたものの、この攻撃には9,223,372,036,854,775,808回のSHA-1計算が必要で、シングルCPUで6500年とシングルGPUで110年分の計算量です。「こんなに計算が必要な攻撃を誰がやるんだよ。」という現実的な問題もあるようです。また、この攻撃成功の前からもSHA-1は安全ではないという認識が広がっていて、SHA-256などへの移行が進んでいたということもあり、影響はあまりなかったようです。
追記
2022/5/9追記
5/8に公開してその後にいくつか指摘をもらったりしたのでそれについて書き足します。
そもそもの根本的な理解として、SHAtteredは任意のハッシュ値に対してそのハッシュ値になるPDFが作れると言うことではなく、用意したPDFに対して同じハッシュ値になるPDFを作れることがある、ということのようです。確かに、 https://shattered.io/ のFail tester適当なファイルを上げると、このファイルは安全ですよ!みたいな表示がでてくるので全てのファイルに対して同じハッシュ値になるファイルを作れるわけではないようです。このことから、ハッシュの一方向性が破られたと考えるのではなく、同じハッシュ値になる二つのファイルの組を作れちゃうと考えるべきなようですね。 はい、しかし、今回は一方向性を計算量で殴れば破れちゃうじゃんという問題のようです。 の部分はおかしいですね。(ただ、計算量のことに関しては後でふれます。) その点から昨日書いた ハッシュがハッシュしていない といっている部分ついて考えてみましょう。結論から述べると、ハッシュはハッシュしてそう というのが今の僕の理解です。昨日の時点での理解では「えっ!?任意のファイルと同じハッシュ値になる違うファイルを見つけられるの??ハッシュのアイデンティティ...」といったようなものでした。しかし、「任意のハッシュ値に対してそのハッシュ値になるファイルを作れると言うわけではない」と言うことからこのような結論に至りました。
もう一つ、計算量のことについて補足します。SHAttered攻撃の場合にはシングルGPUで110年分の計算量が必要です。これを長いと感じるかどうかはさておき、ブルートフォース攻撃を行う場合と比べてみましょう。ブルートフォース攻撃を完了するには12,000,000GPU年が必要で、あまりにも現実的ではありません。それに比べれば10万倍高速になり、お金をかけて並列で処理させたりすれば1年ぐらいで攻撃ができちゃうね(それでもそこまでしてやるか、とは思いますが)という意味で、計算量(と札束)で殴れば攻撃が現実味を帯びてきたというところでしょうか。
理解が薄いままに書いていたらなかなかに盛大な勘違いをしていましたね。ご指摘・アドバイスをくれた方、ありがとうございます!
まとめ
いつもどおりうっすい内容でしたが、今回はこの辺で。あと一日遅れてしましました。ごめんなさい!!!言い訳をすると昨日学校でぬるっと過ごしていたので存在を忘れていました。思い出したのは夜、、、そういうことです。
次回の方のブログはあちら。ではでは!
参考文献
https://shattered.io/ SHAttered attack (SHA-1コリジョン発見) – IIJ Security Diary 暗号技術入門 第3版(書籍) *リンクはAmazon(アフェリエイトではない)です。