暗号学的ハッシュ関数

暗号学的ハッシュ関数は、任意の入力を短く固定長のダイジェストに圧縮する一方向性および衝突耐性を持つ関数であり、完全性、認証、および多くの高レベルプロトコルの基本的な構成要素として機能します。

Definition

暗号学的ハッシュ関数は、任意の長さの入力を固定長の出力（ダイジェスト）にマッピングする決定論的関数であり、原像、第二原像、または同じ出力を生成する2つの異なる入力を見つけることが計算上困難であるという特性を持ちます。

Scope

このトピックでは、ハッシュ関数のセキュリティ特性（原像耐性、第二原像耐性、衝突耐性）、その内部構造（Merkle-Damgaard、スポンジ構造）、標準化されたSHA-2およびSHA-3ファミリー、ならびに完全性検証、パスワード保存、コミットメント、プルーフ・オブ・ワークなどの応用について扱います。誕生日攻撃の限界やMD5およびSHA-1の破綻を含む暗号解読攻撃についても触れます。鍵付き認証コードはメッセージ認証コードの項目で扱われるため、ここでは除外しますが、多くのMACはハッシュ関数から構築されています。

Core questions

• 暗号学的ハッシュ関数と通常のチェックサムまたはハッシュテーブル関数を区別するものは何ですか？
• 原像耐性、第二原像耐性、および衝突耐性が異なるのはなぜですか、またそれらはどのように関連していますか？
• 誕生日パラドックスが衝突耐性をダイジェスト長の半分に制限するのはなぜですか？
• Merkle-Damgaard構造とスポンジ構造は、固定サイズの圧縮を任意の入力にどのように拡張しますか？
• ハッシュ関数は、データのコミット、完全性の検証、およびパスワードの保存にどのように使用されますか？

Key concepts

• メッセージダイジェスト
• 原像耐性
• 第二原像耐性
• 衝突耐性
• 誕生日攻撃
• Merkle-Damgaard構造
• スポンジ構造（Keccak）
• 長さ拡張攻撃
• プルーフ・オブ・ワーク

Key theories

衝突耐性と誕生日限界

誕生日パラドックスのため、nビットハッシュに対する一般的な衝突発見攻撃は、約2^(n/2)の作業で成功します。したがって、衝突耐性には、必要なセキュリティレベルの約2倍のダイジェスト（例：128ビットセキュリティには256ビット）が必要です。

反復構造とスポンジ構造

Merkle-Damgaardパラダイムは、メッセージブロックに対して固定入力圧縮関数を反復することで完全なハッシュを構築します。SHA-3（Keccak）で使用されるスポンジ構造は、大きな置換状態に入力を吸収し、そこから出力を絞り出すことで、長さ拡張の弱点を回避します。

Mechanisms

Merkle-Damgaardハッシュは、メッセージをパディングし、ブロックに分割し、各ブロックを実行中の連鎖値に混合する圧縮関数を繰り返し適用し、最終値をダイジェストとして出力します。SHA-3のスポンジ構造は、代わりにメッセージブロックをKeccak-f関数によって置換された大きな状態の一部にXORすることで吸収し、その後ダイジェストビットを絞り出します。これにより、プレーンなMerkle-Damgaardに固有の長さ拡張特性が回避されます。

Clinical relevance

ハッシュ関数は遍在しています。これらはソフトウェアダウンロードの完全性を検証し、デジタル署名（文書全体ではなくハッシュに署名する）を固定し、Gitやコンテンツ配信ネットワークでコンテンツをインデックス化し、遅い鍵導出関数（bcrypt、Argon2）を介してパスワード保存を保護し、ブロックチェーンの基盤となるプルーフ・オブ・ワークとマークルツリーを提供します。MD5とSHA-1の衝突耐性の実用的な破綻は、インターネット全体でのSHA-2への移行を余儀なくさせました。

Evidence & guidelines

SHA-2（SHA-256、SHA-512）はFIPS 180-4で、SHA-3はFIPS 202で規定されており、どちらもNISTによって承認されています。MD5とSHA-1は、実証された衝突攻撃（2017年のSHAttered SHA-1衝突は画期的な出来事でした）の後、セキュリティ用途では非推奨とされています。パスワード保存には、プレーンなハッシュ化ではなく、Argon2などのメモリハード関数が推奨されています。

History

MDファミリー（RivestのMD4およびMD5）とNSAが設計したSHA-0/SHA-1は、1990年代を席巻しました。Xiaoyun Wangによる衝突攻撃（2004-2005年）はMD5を破り、SHA-1を弱体化させ、NISTのオープンなSHA-3コンペティション（2007-2012年）を促しました。これはBertoni、Daemen、Peeters、およびVan AsscheによるKeccakスポンジ設計が勝利しました。SHA-1は2017年のSHAttered衝突によって実質的に破られました。

Key figures

• Ralph Merkle
• Ivan Damgaard
• Guido Bertoni
• Joan Daemen
• Xiaoyun Wang

Seminal works

• nist2015sha3
• katz2020
• menezes1996

Frequently asked questions

パスワードをハッシュ化してダイジェストを保存するだけではなぜいけないのですか？

プレーンな暗号学的ハッシュは高速であるため、攻撃者は盗まれたデータベースに対して毎秒数十億回の推測を試みることができます。パスワードの保存には、意図的に遅く、ソルト化され、メモリハードな関数（bcrypt、scrypt、Argon2）が使用され、各パスワードのブルートフォース攻撃が高価になるようにします。

SHA-1が破られた今、SHA-256も破られたのですか？

いいえ。SHA-1とSHA-256は異なるアルゴリズムであり、SHA-1に対する衝突攻撃はSHA-2には適用されません。SHA-256は破られておらず、SHA-3とともに推奨される汎用ハッシュとして残っています。