第6日目(相当)の記事です。今回の内容はSHA-1が現実的に突破されたというSHAtteredの論文をもとに、SHA-0/SHA-1への攻撃がいかにして行われたかの概要と、何がまずかったか、を見ていきます。SHA-2はMerkle-Damgård構造という、固定の初期化ベクトルとメッセージに対して圧縮関数を繰り返し適用することで最終的な出力を得る方式を取ります。SHA-0/1/2はそれぞれこの圧縮関数が異なるため性質が異なっています。rotationが1個加わって現在の形になっています。SHA-2はこれらとは全く異なる圧縮関数を使用しています。よる衝突攻撃があります。大まかにいうと、入力の特定1バイトを変えたときに内部の状態ビット(圧縮関数にかけられる値の片方)がどのように変化するかを追跡し、それのパスが構築可能であることを見つけた、というものです。SHA-1はこれを解決するハズでしたが、実はこの問題は繰り返し現れることとなり、結果として差分解読に弱い圧縮関数を使ったことがSHA-1の衝突が見つかりやすい原因の一つになったといえるでしょう。collisionという内部状態が6サイクルで同じ値に戻る、という性質も明らかにしています。SHAttered論文の4章の図こういう背景を抑えた上で見ると4章のoverviewの図の意味が取りやすくなります。SHA-1の圧縮関数は内部で16ラウンドごとに異なる関数を適用するため、最初の16ラウンドの内部状態までは操作がしやすいが、残りの64ラウンドは操作が困難である、というのが(1)で示してある部分。4B)の形で解が得られる。SHA-1(P+4A_2+4B_2+S)の内部状態が同一になる。Mによって得られる内部状態が4A+4Bのブロックを経ることで打ち消されるため。消化不良気味ですがこんなところで、改めて読み込めたら書き直すかも。attackというか圧縮関数の不動点が見つかったよという話について記事を書いてます。次回はSHA-2の話すっ飛ばしてSHA-3(Keccak)などのMerkle-Damgårdでないハッシュの話の予定です。(4)月別アーカイブはてなブログをはじめよう!sylph01さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。