優れたハッシュ関数の特性

優れた暗号学的ハッシュ関数は、安全と見なされるためにいくつかの形式的特性を満たす必要があります。これらの特性を理解することで、特定のアルゴリズムが信頼される（SHA-256）一方で他が破られている（MD5）理由が説明でき、新しいハッシュ関数の評価にも役立ちます。

1. 決定的出力:

同じ入力は常に同じ出力を生成しなければなりません。ハッシュ計算にランダム性はありません。SHA-256("hello")が実行ごとに異なる値を返すなら、検証に使えません。ただし、これは異なる入力が常に異なる出力を生成するという意味ではありません（固定出力サイズの関数ではそれは不可能です）。

2. 原像耐性（一方向性）:

ハッシュ値hが与えられたとき、hash(m) = hとなる入力mを見つけることが計算上不可能であるべきです。nビットハッシュでは約2^n回の操作が必要です。SHA-256では原像の発見に約2^256回の操作が必要です。この特性により、ハッシュを見ても元の入力は明らかになりません。

3. 第二原像耐性:

入力m1が与えられたとき、hash(m1) = hash(m2)となる異なる入力m2を見つけることが不可能であるべきです。第二原像耐性はデジタル署名に不可欠です。攻撃者が第二原像を見つけられれば、署名された文書を同じハッシュを持つ別の文書に差し替えられます。

4. 衝突耐性:

hash(m1) = hash(m2)となる任意の2つの異なる入力m1とm2を見つけることが不可能であるべきです。誕生日のパラドックスにより、nビットハッシュでは約2^(n/2)回の操作が必要です。MD5とSHA-1はこの特性に失敗しています。SHA-256は2^128のセキュリティレベルで維持しています。

5. 雪崩効果:

入力の小さな変更が出力に劇的に異なる変化をもたらすべきです。入力の1ビットの反転で出力ビットの約50%が変化すべきです。この特性により、類似の入力が無関係なハッシュを生成し、攻撃者がハッシュの変化を観察して入力について何も学べないことを保証します。ハッシュ値の均一分布も保証し、ハッシュテーブルやデータ構造にとっても重要です。

補足：効率性:

セキュリティ特性ではありませんが、実用的なハッシュ関数は効率的に計算できなければなりません。SHA-256はソフトウェアで毎秒数百メガバイト、ハードウェアアクセラレーションで毎秒数ギガバイトを処理します。このセキュリティと速度のバランスが広範な展開を可能にしています。