ハッシュ関数をわかりやすく解説
ソフトウェアをダウンロードしてチェックサムを照合するとき、パスワードでログインするとき、文書に署名するとき、ビットコイン にブロックを追加するとき、そこではハッシュ関数が働いています。ハッシュ関数は、どんな量のデータも、ハッシュ値(ダイジェスト)と呼ばれる固定長の短い指紋に変えます。しかもその変換は元に戻すことも偽造することもできません。考え方は単純ですが、良いハッシュ関数に求められる条件は厳しく、最も広く使われてきた MD5 と SHA-1 の2つは、その条件に耐えられませんでした。
データの指紋
ハッシュ関数は任意の長さの入力を受け取り、固定長のハッシュ値を返します。SHA-256 なら256ビットで、16進数64桁で書き表されます。同じ入力からは必ず同じハッシュ値が得られるので、ハッシュ値をデータの代わりとして扱えます。2つのファイルの SHA-256 ハッシュ値が同じなら、それらは同一だと確信できます。ダウンロードしたファイルの1ビットでも壊れていれば、そのハッシュ値は配布元が公開しているものと一致しなくなります。取りうる入力はハッシュ値よりはるかに多いため、どのハッシュ値にも多くの入力が対応しているはずです。良いハッシュ関数は、そのどれ1つとして見つけられないようにしているだけなのです。
3つの約束
暗号学的ハッシュ関数は3つのことを約束します。原像計算困難性:ハッシュ値が与えられても、それを生み出す入力は見つけられません。第2原像計算困難性:入力が与えられても、同じハッシュ値を持つ別の入力は見つけられません。衝突困難性:同じハッシュ値を持つ2つの入力は、どんな組み合わせでも見つけられません。n ビットの理想的なハッシュ関数に対する最善の攻撃は当てずっぽうで、原像には約2ⁿ回、衝突には約2ⁿᐟ²回の試行が必要です。それよりはるかに速い方法が見つかったとき、そのハッシュ関数は破られたと言われます。
アバランシェ効果
入力を1ビット変えると、ハッシュ値の各ビットは他のビットとは独立に、2分の1の確率で反転するはずです。そうであれば、メッセージの小さな変更からまったく無関係に見えるハッシュ値が生まれ、入力のどの部分が変わったのかもハッシュ値からはまったくわかりません。SHA-256 は、8つの32ビットワードを回転させ、足し合わせ、組み合わせるラウンドを64回繰り返すことでこれを実現しており、数ラウンドのうちにすべての入力ビットがすべてのワードに影響を与えます。これに対して単純なバイト和は、入力が変わった量とまったく同じだけ変わるので、すべてを明かしてしまいます。
SHA-256 の内部
SHA-256 はまずメッセージをパディングします。1のビット、いくつかの0、そしてメッセージの長さを付け加え、全体を512ビットの倍数にします。次にメッセージを512ビットずつ処理します。各ブロックは64個のワードに引き伸ばされ、8つの32ビットワードからなる状態に混ぜ込まれます。状態の初期値は固定で、最初の8つの素数の平方根から取られています。最後のブロックを処理した後の状態がハッシュ値です。Ralph Merkle と Ivan Damgård にちなんで名付けられたこの連鎖型の設計は、MD5、SHA-1、SHA-512 にも共通しています。2015年に標準化された新しい SHA-3 は、スポンジ構造と呼ばれる別の構成を使っています。
誕生日攻撃
23人のグループで誕生日が同じ2人がいる確率は、1年が365日あるにもかかわらず、2分の1をわずかに超えます。重要なのはペアの数で、それは人数の2乗に比例して増えるからです。ハッシュ関数の衝突も同じ法則に従います。取りうるハッシュ値が2ᵏ通りあるとき、衝突が起きるまでに必要なランダムな入力は約√(π/2 · 2ᵏ)個と見込まれます。32ビットなら約8万2000個で、一瞬で終わります。128ビットなら約2⁶⁴で、大規模な計算プロジェクトなら手が届きます。だからこそ MD5 の128ビットは決して余裕のあるものではなく、SHA-256 は長さを2倍にして128ビットの安全性を確保しているのです。
MD5 と SHA-1:破られたハッシュ関数
Ron Rivest が1991年に MD5 を設計し、NSA が設計した SHA-1 が1995年に公開されました。2004年、Xiaoyun Wang と共同研究者たちは MD5 の衝突をすばやく作る方法を示し、2008年には研究者たちがそれを使って、Web ブラウザーが信頼する証明書を偽造しました。2012年のスパイソフトウェア Flame は、MD5 の衝突を利用して Microsoft の更新プログラムになりすましました。SHA-1 が破られたのは2017年で、Google と CWI Amsterdam が約2⁶³回の計算の末、SHA-1 ハッシュ値が同じ2つの異なる PDF ファイルを公開しました。どちらも偶発的な誤りを見つけるには今でも十分ですが、攻撃者に狙われうる用途には使えません。
ハッシュ関数の使われ方
デジタル署名は、文書そのものではなく文書のハッシュ値に署名します。Git はすべてのファイルとコミットをハッシュ値で名付け、ビットコイン のマイナーは、SHA-256 を2回かけたハッシュ値が長い0の並びで始まるブロックヘッダーを探します。Web サイトはパスワードを決してそのまま保存せず、そのハッシュ値だけを保存すべきです。ただし人は短いパスワードを選びがちなので、そのハッシュは bcrypt、scrypt、Argon2 などの方法で低速かつソルト付きにし、推測にコストがかかるようにしなければなりません。ZIP ファイル、PNG 画像、Ethernet で使われる CRC-32 のようなチェックサムもハッシュ関数の一種ですが、攻撃者ではなくノイズを捕まえるために作られています。
試してみよう
ハッシュ関数ラボを開いて、SHA-256、SHA-512、SHA-1、MD5、CRC-32、おもちゃのバイト和で自分のテキストのハッシュ値を計算してみましょう。「1文字変える」を押して反転したビットを数え、「テストを実行」で1ビットの変更1000回にわたるアバランシェテストを行ってハッシュ値の半分を中心とする釣鐘型の曲線を確かめ、「衝突を探す」でハッシュ値の先頭8〜32ビットで本物の衝突を見つけて、誕生日攻撃の働きを見てみましょう。
よくある質問
ハッシュ化は暗号化と同じですか?
いいえ。暗号化は鍵を持つ人が元に戻せるように作られていますが、ハッシュ化には鍵がなく、誰にも元に戻せません。暗号化はメッセージを秘密にするためのもので、ハッシュ値は手元にあるメッセージを確かめるための指紋を与えるだけです。
SHA-256 の衝突を見つけるにはどれくらいかかりますか?
誕生日攻撃では約2¹²⁸回のハッシュ計算が必要で、これは39桁の数です。地球上のすべてのコンピューターがほかに何もせずに計算しても、宇宙の年齢よりはるかに長い時間がかかります。近道は知られていません。
同じテキストのハッシュ値が食い違うことがないのはなぜですか?
ハッシュ関数は決定的です。ランダム性も鍵もないので、同じバイト列からは必ず同じハッシュ値が得られます。ただし、末尾の空白、改行コードの違い、アクセント付き文字の別の Unicode 表現など、目に見えない小さな違いがあると、ハッシュ値は変わります。
ソルトとは何ですか?
パスワードのハッシュ値と一緒に保存され、ハッシュ計算に混ぜ込まれるランダムな値です。これにより、同じパスワードを使う2人のユーザーでもハッシュ値が異なり、攻撃者はよく使われるパスワードの計算済みの表1つをすべてのアカウントに使い回すことができなくなります。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
ハッシュ関数ラボを開く