SKILL: Hash Attack Techniques — Expert Cryptanalysis Playbook

AI LOAD INSTRUCTION: CTFおよびセキュリティ評価向けのエキスパート・ハッシュ攻撃テクニック。長さ拡張攻撃、MD5/SHA1衝突生成、ミート・イン・ザ・ミドル・ハッシュ攻撃、HMAC タイミング側チャネル、誕生日攻撃、および Proof-of-Work ソルビングを解説します。基本モデルは長さ拡張をHMACやSHA-3に誤適用したり、同一プレフィックス衝突と選択プレフィックス衝突を区別できないことがあります。

0. RELATED ROUTING

• rsa-attack-techniques ハッシュの弱さがRSA署名方式に影響する場合
• symmetric-cipher-attacks ハッシュが鍵導出に使われている場合
• classical-cipher-analysis 古典暗号におけるハッシュのような構成を分析する場合

クイック攻撃選択ガイド

シナリオ	攻撃	ツール
H(secret || msg) が既知、メッセージ拡張	長さ拡張	HashPump, hash_extender
同じMD5を持つ2つのファイルが必要	同一プレフィックス衝突	fastcoll
特定のMD5プレフィックスマッチが必要	選択プレフィックス衝突	hashclash
バイト単位のHMAC比較	タイミング攻撃	カスタムスクリプト
任意の衝突を見つける	誕生日攻撃	O(2^(n/2))
Proof of work: 先頭ゼロのハッシュを見つける	ブルートフォース	hashcat, Python

---

1. LENGTH EXTENSION ATTACK

1.1 脆弱性あり vs なし

ハッシュ	脆弱	理由
MD5	あり	Merkle-Damgard構成
SHA-1	あり	Merkle-Damgard構成
SHA-256	あり	Merkle-Damgard構成
SHA-512	あり	Merkle-Damgard構成
SHA-3 / Keccak	なし	スポンジ構成
HMAC-*	なし	ダブルハッシュが拡張を防止
SHA-256 truncated	なし(截断の場合)	内部状態ビット欠落
BLAKE2	なし	異なる構成

1.2 攻撃メカニズム

既知: MAC = H(secret || original_message)
既知: original_message, len(secret), MAC値
計算: H(secret || original_message || padding || extension)
      秘密を知らずに計算可能!

方法: MAC値は(secret || original_message || padding)処理後の
      内部ハッシュ状態です。
      この状態からハッシュを初期化し、拡張部分を続けてハッシュ化。

1.3 パディング計算 (MD5/SHA)

def md5_padding(message_len_bytes):
    """与えられたメッセージ長に対するMD5/SHAパディングを計算."""
    bit_len = message_len_bytes * 8

    # 0x80 + ゼロでパディング、長さが 56 (mod 64) になるまで
    padding = b'\x80'
    padding += b'\x00' * ((55 - message_len_bytes) % 64)

    # 元の長さを64ビット little-endian (MD5)
    # または big-endian (SHA) で追加
    padding += bit_len.to_bytes(8, 'little')  # MD5
    # padding += bit_len.to_bytes(8, 'big')    # SHA

    return padding

1.4 ツール使用方法

# HashPump
hashpump -s "known_mac_hex" \
         -d "original_data" \
         -k 16 \            # secret length
         -a "extension_data"

# 出力: new_mac, new_data (original + padding + extension)

# hash_extender
hash_extender --data "original" \
              --secret 16 \
              --append "extension" \
              --signature "known_mac_hex" \
              --format md5

1.5 Python実装

import struct

def md5_extend(original_mac, original_data_len, secret_len, extension):
    """
    MD5長さ拡張攻撃を実行.
    original_mac: H(secret || original_data) の16進文字列
    """
    # MACをMD5内部状態に解析 (4 × 32ビット word, little-endian)
    h = struct.unpack('<4I', bytes.fromhex(original_mac))

    # パディング後の全体の長さを計算
    total_original = secret_len + original_data_len
    padding = md5_padding(total_original)
    forged_len = total_original + len(padding) + len(extension)

    # 保存された状態から拡張でMD5を続行
    # (初期状態を受け入れるMD5実装が必要)
    from hashlib import md5
    # ほとんどの標準ライブラリ md5 は状態設定を公開しない
    # 使用: hlextend ライブラリまたはカスタム MD5

    import hlextend
    sha = hlextend.new('md5')
    new_hash = sha.extend(extension, original_data, secret_len,
                          original_mac)
    new_data = sha.payload  # original + padding + extension を含む

    return new_hash, new_data

---

2. MD5衝突攻撃

2.1 同一プレフィックス衝突 (fastcoll)

同じプレフィックスを持つが内容が異なる2つのメッセージが、同一のMD5を生成します。

# 衝突ペアを生成
fastcoll -p prefix_file -o collision1.bin collision2.bin

# 結果: MD5(collision1.bin) == MD5(collision2.bin)
# ファイルはちょうど128バイト (2つのMD5ブロック) で異なる

2.2 選択プレフィックス衝突 (hashclash)

異なる選択プレフィックスを持つ2つのメッセージに、計算されたサフィックスを追加して衝突させます。

# hashclash (Marc Stevens)
./hashclash prefix1.bin prefix2.bin

# 結果: MD5(prefix1 || suffix1) == MD5(prefix2 || suffix2)

2.3 UniColl (シングルブロック準衝突)

1つのMD5ブロック内のシングルバイトで異なる2つのメッセージを生成し、同じハッシュを持ちます。

応用: 2つのPDF/PEファイルを同一MD5で鍛造
  - ファイル1: 無害なコンテンツ
  - ファイル2: 悪意あるコンテンツ
  - 同じMD5ハッシュ

2.4 衝突の応用

応用	テクニック	影響
証明書鍛造	選択プレフィックス	不正なCA証明書 (2008年に実証)
バイナリ置換	同一プレフィックス + 条件付き	2つの実行ファイル、同じMD5、異なる動作
PDF衝突	UniColl	異なるコンテンツを表示する2つのPDF
Gitコミット衝突	選択プレフィックス (SHA1用 SHAttered)	同じハッシュの2つのコミット
CTF: MD5チェック回避	fastcoll	同じとして受け入れられる異なる入力

2.5 CTF MD5衝突トリック

// PHP: md5($_GET['a']) == md5($_GET['b']) && $_GET['a'] != $_GET['b']

// 方法1: 配列トリック (実際の衝突ではない)
?a[]=1&b[]=2  // md5(array) は NULL を返す、NULL == NULL

// 方法2: 実際の衝突 (fastcoll出力、URL エンコード済みバイナリ)
?a=<collision1_urlencoded>&b=<collision2_urlencoded>

// 方法3: 0e マジックハッシュ (緩い比較 ==)
// md5("240610708") = "0e462097431906509019562988736854"
// md5("QNKCDZO")   = "0e830400451993494058024219903391"
// PHP: "0e..." == "0e..." は TRUE (両方とも浮動小数点で0と評価)

---

3. SHA-1衝突

3.1 SHAttered攻撃 (2017年)

初の実用的なSHA-1衝突: 同じSHA-1を持つ2つのPDFファイル。

• 複雑性: ~2^63 SHA-1計算
• コスト: ~$110K (2017年GPU クラスター価格)
• ツール: shattered.io が衝突PDFを提供

3.2 SHA-1選択プレフィックス衝突 (2020年)

• 複雑性: ~2^63.4 計算
• PGP/GnuPG キーサーバー攻撃に実用的
• SHA-1が衝突耐性の観点で破られていることを実証

3.3 影響

SHA-1 は以下に使用すべきではありません:
  ✗ デジタル署名
  ✗ 証明書フィンガープリント
  ✗ Gitコミット整合性チェック (SHA-256への移行が進行中)
  ✗ ハッシュに基づく重複排除

SHA-1 は以下には適切です:
  ✓ HMAC-SHA1 (衝突耐性は不要)
  ✓ HKDF-SHA1 (PRF セキュリティで充分)
  ✓ 非対立的なチェックサム

---

4. 誕生日攻撃

4.1 汎用誕生日界

n ビットハッシュの場合: ~2^(n/2) ハッシュ後に衝突が予期される

ハッシュ      ビット    誕生日界
MD5      128     2^64
SHA-1    160     2^80
SHA-256  256     2^128

CTF応用: ハッシュが k ビットに截断されている場合、
~2^(k/2) 回の試行で衝突が発生

4.2 誕生日攻撃実装

import hashlib
import os

def birthday_attack(hash_func, output_bits, max_attempts=2**28):
    """截断ハッシュの衝突を見つける."""
    mask = (1 << output_bits) - 1
    seen = {}

    for _ in range(max_attempts):
        msg = os.urandom(16)
        h = int(hash_func(msg).hexdigest(), 16) & mask

        if h in seen and seen[h] != msg:
            return seen[h], msg  # 衝突!
        seen[h] = msg

    return None

# 例: SHA-256の最初の32ビットの衝突を見つける
result = birthday_attack(hashlib.sha256, 32)

---

5. HMACタイミング攻撃

5.1 脆弱な比較

# 脆弱: 早期終了する文字列比較
def verify_hmac(received, expected):
    return received == expected  # Python == は左から右へ比較

# 比較は異なるバイトで短時間終了する可能性があり、
# タイミング情報が漏洩する

5.2 攻撃戦略

import requests
import time

def hmac_timing_attack(url, data, hmac_len=32):
    """タイミングを使用したバイト単位のHMAC回復."""
    known = ""

    for pos in range(hmac_len * 2):  # 16進文字
        best_char = ""
        best_time = 0

        for c in "0123456789abcdef":
            candidate = known + c + "0" * (hmac_len * 2 - len(known) - 1)
            times = []

            for _ in range(50):  # 精度向上のため複数サンプル
                start = time.perf_counter_ns()
                requests.get(url, params={**data, "mac": candidate})
                elapsed = time.perf_counter_ns() - start
                times.append(elapsed)

            avg_time = sorted(times)[len(times)//2]  # 中央値
            if avg_time > best_time:
                best_time = avg_time
                best_char = c

        known += best_char
        print(f"Position {pos}: {known}")

    return known

5.3 定時間比較 (防御)

import hmac

# セキュア: 定時間比較
def verify_hmac_secure(received, expected):
    return hmac.compare_digest(received, expected)

---

6. ミート・イン・ザ・ミドル (HASH)

6.1 概念

ハッシュ計算を2つの半分に分割し、片方を事前計算し、もう片方とマッチさせます。

ハッシュ計算: H = f(g(x₁), h(x₂))

事前計算: table[g(x₁)] = x₁  for all x₁ in space₁
検索:     for each x₂ in space₂:
            if h(x₂) in table:
              見つかり! (x₁, x₂)

時間:  O(2^(n/2)) (O(2^n) の代わり)
空間: O(2^(n/2))

---

7. ハッシュ Proof-of-Work

7.1 一般的なCTF PoW形式

# 形式1: SHA256(prefix + x) が N 個の先頭ゼロビットで始まる x を見つける
import hashlib

def solve_pow_prefix(prefix, zero_bits):
    target = '0' * (zero_bits // 4)
    i = 0
    while True:
        candidate = prefix + str(i)
        h = hashlib.sha256(candidate.encode()).hexdigest()
        if h.startswith(target):
            return str(i)
        i += 1

# 形式2: SHA256(x) が特定のサフィックスで終わる x を見つける
def solve_pow_suffix(suffix_hex, hash_func=hashlib.sha256):
    i = 0
    while True:
        h = hash_func(str(i).encode()).hexdigest()
        if h.endswith(suffix_hex):
            return str(i)
        i += 1

7.2 GPU加速 PoW

# SHA256 PoW用 hashcat
hashcat -a 3 -m 1400 --hex-charset \
  "0000000000000000000000000000000000000000000000000000000000000000:prefix" \
  "?a?a?a?a?a?a?a?a"

---

8. レインボーテーブルとソルト

8.1 レインボーテーブル攻撃

事前計算チェーン: password → hash → reduce → password₂ → hash₂ → ...
ルックアップ: 与えられたハッシュ h について、任意のチェーンに h が現れるか確認
時間-メモリ トレードオフ: 完全なテーブルより少ないスペース、直接ルックアップより長い時間

8.2 ソルトはレインボーテーブルを無効化

ソルトなし: H(password) — 同じパスワードは常に同じハッシュを生成
ソルトあり: H(salt || password) — ユーザーごとに異なるソルト

レインボーテーブルはパスワード固有で、(salt+password)固有ではない
各ユニークソルトは個別のテーブルが必要 → 実現不可能

8.3 モダンパスワードハッシング

アルゴリズム	ソルト	イテレーション	メモリハード	推奨
MD5	なし	1	なし	絶対NG
SHA-256	なし	1	なし	パスワードには絶対NG
bcrypt	あり	設定可能	なし	あり
scrypt	あり	設定可能	あり	あり
Argon2	あり	設定可能	あり	最良選択肢
PBKDF2	あり	設定可能	なし	受け入れ可能

---

9. デシジョンツリー

ハッシュ関連チャレンジ — どのシナリオですか?
│
├─ H(secret || message)を持っており、拡張が必要ですか?
│  ├─ ハッシュはMD5/SHA1/SHA256/SHA512ですか?
│  │  └─ はい → 長さ拡張攻撃
│  │     └─ 必要: MAC値、元のメッセージ、秘密長
│  │        └─ ツール: HashPump または hash_extender
│  │
│  └─ ハッシュはSHA3/HMAC/BLAKE2ですか?
│     └─ 長さ拡張は機能しない
│        └─ 他の脆弱性を探す
│
├─ 同じハッシュを持つ2つの入力が必要ですか?
│  ├─ MD5ですか?
│  │  ├─ 同じプレフィックス → fastcoll (秒単位)
│  │  ├─ 異なるプレフィックス → hashclash (時間単位)
│  │  └─ CTF PHP緩い比較 → 0e マジックハッシュ
│  │
│  ├─ SHA-1ですか?
│  │  └─ SHAttered (高コスト、可能なら事前計算を使用)
│  │
│  └─ SHA-256+ですか?
│     └─ 実用的な衝突攻撃なし
│        └─ ロジックの欠陥を探す
│
├─ HMACを偽造する必要がありますか?
│  ├─ タイミング側チャネルが利用できますか?
│  │  └─ バイト単位のタイミング攻撃
│  │
│  ├─ 鍵が短い/弱いですか?
│  │  └─ hashcatで鍵をブルートフォース
│  │
│  └─ 弱点がないですか?
│     └─ HMACはセキュア — 他を探す
│
├─ ハッシュが截断されていますか (短い出力)?
│  └─ 誕生日攻撃 — 衝突は 2^(bits/2)
│
├─ Proof of work ですか?
│  └─ 並列計算でブルートフォース
│     ├─ < 28ビットならPython multiprocessing
│     ├─ > 28ビットなら hashcat/GPU
│     └─ 最適化: 文字列の事前インクリメント、再エンコーディング回避
│
└─ パスワードハッシュクラッキングですか?
   ├─ ソルトなし → レインボーテーブル (事前計算)
   ├─ 既知ソルト → hashcat / John the Ripper
   └─ メモリハード (Argon2/scrypt) → メモリで制限、遅いブルートフォース

---

10. ツール

ツール	目的	使用方法
HashPump	長さ拡張攻撃	hashpump -s MAC -d data -k secret_len -a extension
hash_extender	長さ拡張 (複数アルゴリズム)	hash_extender --data D --secret L --append E --sig MAC
fastcoll	MD5同一プレフィックス衝突	fastcoll -p prefix -o out1 out2
hashclash	MD5選択プレフィックス衝突	hashclash prefix1 prefix2
hashcat	パスワード/ハッシュクラッキング (GPU)	hashcat -m MODE -a ATTACK hash wordlist
John the Ripper	パスワードクラッキング (CPU/GPU)	john --wordlist=rockyou.txt hashes.txt
CyberChef	クイックハッシュ計算とエンコーディング	Webベース