ハッシュ関数はなぜ「元に戻せない」のか — MD5の崩壊からSHA-3まで

暗号学的ハッシュ関数 H が満たすべき要件は以下の3つです:

衝突耐性は第二原像耐性より弱い要件です。攻撃者が2つの入力を自由に選べるためです。n ビットのハッシュに対し、衝突を見つける計算量は誕生日のパラドックスにより 2^(n/2) まで下がります。128ビットの MD5 なら 2^64 回の計算で衝突が見つかる可能性がある — これが MD5 に対する最初の警鐘でした。

ハッシュ関数が元に戻せない理由は、大きく2つの設計原理から来ています:

1. 情報の不可逆な圧縮

SHA-256 は任意長の入力を 256 ビット（32バイト）に圧縮します。入力空間は無限、出力空間は 2^256 通りしかありません。鳩の巣原理から、同じハッシュ値になる入力は無限に存在します。つまり、ハッシュ値から「正しい」元データを一意に特定することは原理的に不可能です。

2. 雪崩効果（Avalanche Effect）

入力の1ビットを変えると、出力のビットの約半数が反転します。SHA-256の場合:

SHA-256("hello")  = 2cf24dba5fb0a30e...
SHA-256("hellp")  = 5f2c5900bcc10e1d...
                    (全く異なるハッシュ)

この性質は攻撃者が出力の変化から入力の変化を推測することを防ぐために意図的に設計されています。内部では、ビットシフト、XOR、モジュラー加算、非線形関数（論理AND/OR/NOT）が何十ラウンドも繰り返され、入力と出力の関係を徹底的に攪乱します。

ただし、ハッシュ関数の一方向性は数学的に証明されていません。P ≠ NP 予想と関連する未解決問題であり、「現時点で知られている攻撃手法では元に戻せない」というのが正確な表現です。

MD5（Message Digest Algorithm 5）は1991年に Ronald Rivest が設計した128ビットのハッシュ関数です。1990年代を通じて最も広く使われたハッシュ関数でしたが、2004年に中国・山東大学の王小雲（Wáng Xiǎoyún）のチームが衝突攻撃に成功し、その安全性は崩壊しました。

王のチームは CRYPTO 2004 で、MD5 の衝突ペアをわずか1時間で計算できることを示しました。つまり、H(x₁) = H(x₂) となる異なる2つの入力 x₁, x₂ を高速に生成できるのです。

この攻撃が現実に悪用された最も衝撃的な事例が、2008年の偽SSL証明書の生成です。研究チームは200台のPS3を使い、正規の認証局が発行した証明書と同じMD5ハッシュを持つ不正な中間CA証明書を作成しました。これにより、任意のWebサイトに対して正規の証明書チェーンを持つ偽証明書を発行できることが実証されました。

現在、MD5 の衝突生成は一般的なノートPCで数秒で可能です。IETF は2011年に RFC 6151 で MD5 を「セキュリティ用途に使ってはならない」と宣言しています。ただし、ファイルの破損チェック（非セキュリティ用途）では今でも使われています。

SHA-1（Secure Hash Algorithm 1）は1995年にNSAが設計した160ビットのハッシュ関数です。MD5の後継として広く採用されましたが、2017年にGoogleとCWI Amsterdamの共同チームがSHAttered 攻撃を成功させました。

SHAttered では、内容の異なる2つの PDF ファイルが同じ SHA-1 ハッシュ値を持つことが実証されました。計算量は 2^63.1 回の SHA-1 演算で、理論限界の 2^80 より大幅に少ない。Google のクラウドインフラで6,500 CPU年 + 110 GPU年相当の計算を要しましたが、これは大規模な組織にとっては現実的なコストです。

この攻撃を受けて:

• Git: SHA-1をコミットハッシュに使用。Git 2.29以降、SHA-256への移行オプションを提供開始
• ブラウザ: Chrome, Firefox, Edgeは2017年にSHA-1証明書のサポートを完全廃止
• CA/Browser Forum: 2016年以降、SHA-1によるSSL証明書の発行を禁止

SHA-1 は現時点で原像耐性は破られていない（ハッシュ値から元データを逆算する攻撃は未成功）ため、レガシーシステムでの署名検証には一定の安全性が残っていますが、新規利用は推奨されません。

SHA-256はSHA-2ファミリーの一つで、256ビットのハッシュを出力します。2001年にNIST（米国立標準技術研究所）がFIPS 180-2として標準化しました。2026年現在、実用上の安全性が保たれている最も広く使われるハッシュ関数です。

SHA-256はMerkle-Damgård構造に基づいています。これは入力メッセージを固定長ブロック（512ビット）に分割し、圧縮関数 f を連鎖的に適用する構造です:

H₀ = IV（初期値、仕様で固定）
H₁ = f(H₀, M₁)
H₂ = f(H₁, M₂)
...
ハッシュ値 = Hₙ = f(Hₙ₋₁, Mₙ)

圧縮関数 f の内部では64ラウンドの演算が行われます。各ラウンドで使われる主な操作は:

• Ch(E, F, G) = (E AND F) XOR (NOT E AND G) — 条件選択関数
• Maj(A, B, C) = (A AND B) XOR (A AND C) XOR (B AND C) — 多数決関数
• Σ₀, Σ₁: ビット回転とシフトの組み合わせ
• K₀...K₆₃: 64個の定数（最初の64個の素数の立方根の小数部分から導出）

SHA-256 の衝突耐性は 2^128（128ビット安全性）、原像耐性は 2^256 です。現在の最善の攻撃でもラウンド数削減版（46/64ラウンド）への衝突にとどまり、フルラウンドの SHA-256 は安全と見なされています。

2007年、NIST はSHA-2の後継を公募するSHA-3コンペティションを開始しました。SHA-2が破られたわけではなく、SHA-1の崩壊を受けて「SHA-2と異なる設計思想のバックアップ」を用意する予防的措置でした。

5年間の公開審査を経て、2012年にKeccak（ケチャック）が選出されました。設計者は Guido Bertoni、Joan Daemen（AESの共同設計者）、Michaël Peeters、Gilles Van Assche のベルギーチームです。

Keccak は SHA-2 とは根本的に異なるスポンジ構造を採用しています:

┌────────────────────────────────────┐
│          state (1600 bits)         │
│  ┌──────────┬───────────────────┐  │
│  │  r bits  │     c bits       │  │
│  │ (rate)   │   (capacity)     │  │
│  └──────────┴───────────────────┘  │
└────────────────────────────────────┘
吸収フェーズ: 入力ブロックを r ビットずつ XOR
搾出フェーズ: r ビットずつ出力を取り出す

• 吸収（absorb）: 入力を r ビットのブロックに分割し、状態の先頭 r ビットに XOR → 置換関数 f を適用、を繰り返す
• 搾出（squeeze）: 状態の先頭 r ビットを出力として取り出す。必要なら f を再適用して追加出力を得る

安全性の核は容量 c ビットにあります。SHA3-256 では c = 512 ビットで、衝突耐性 2^128、原像耐性 2^256 を確保しています。Merkle-Damgård にあった長さ拡張攻撃（length extension attack）に対して本質的に免疫があるのも大きな利点です。

SHA-3 は2015年に FIPS 202 として正式に標準化されました。SHA-2 が安全な現状では移行の緊急性は低いものの、新規プロトコルでの採用が増えています。

• 暗号学的ハッシュ関数の安全性は原像耐性・第二原像耐性・衝突耐性の3要件で評価される
• 一方向性の根拠は情報の不可逆な圧縮と雪崩効果。ただし数学的証明はない
• MD5（128bit）: 2004年に王小雲が衝突攻撃を実証。現在はノートPCで数秒で衝突生成可能
• SHA-1（160bit）: 2017年にGoogleがSHAttered攻撃で衝突を実証。6,500 CPU年の計算量
• SHA-256: Merkle-Damgård構造、64ラウンド圧縮関数。フルラウンドへの攻撃は未成功
• SHA-3（Keccak）: スポンジ構造を採用。長さ拡張攻撃に本質的に耐性がある
• MD5・SHA-1はセキュリティ用途に使ってはならない。新規開発ではSHA-256以上を選択する