hash-attack-techniques

スキル：ハッシュ攻撃手法 — 暗号解読エキスパート向けプレイブック

AI LOAD INSTRUCTION：CTF とセキュリティ評価向けのエキスパートレベルのハッシュ攻撃手法です。長さ拡張攻撃、MD5/SHA1 の衝突生成、ミートインザミドルハッシュ攻撃、HMAC のタイミングサイドチャネル、誕生日攻撃、プルーフ・オブ・ワークの解法を扱います。ベースモデルは、HMAC や SHA-3 に長さ拡張攻撃を誤って適用したり、同一プレフィックス衝突と選択プレフィックス衝突を区別できなかったりすることがよくあります。

0. 関連するルーティング

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

攻撃のクイック選択

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

---

1. 長さ拡張攻撃

1.1 脆弱な方式と脆弱でない方式

ハッシュ	脆弱性	理由
MD5	あり	Merkle-Damgard 構成
SHA-1	あり	Merkle-Damgard 構成
SHA-256	あり	Merkle-Damgard 構成
SHA-512	あり	Merkle-Damgard 構成
SHA-3 / Keccak	なし	スポンジ構成
HMAC-*	なし	二重ハッシュにより拡張を防止
SHA-256 の切り詰め	なし（切り詰められている場合）	内部状態のビットが欠落
BLAKE2	なし	異なる構成

1.2 攻撃の仕組み

Given:   MAC = H(secret || original_message)
Known:   original_message, len(secret), MAC value
Compute: H(secret || original_message || padding || extension)
         WITHOUT knowing the secret!

How: The MAC value IS the internal hash state after processing
     (secret || original_message || padding).
     Initialize hash with this state, continue hashing extension.

1.3 パディングの計算（MD5/SHA）

def md5_padding(message_len_bytes):
    """Calculate MD5/SHA padding for given message length."""
    bit_len = message_len_bytes * 8

    # Pad with 0x80 + zeros until length ≡ 56 (mod 64)
    padding = b'\x80'
    padding += b'\x00' * ((55 - message_len_bytes) % 64)

    # Append original length as 64-bit little-endian (MD5)
    # or 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"

# Output: 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):
    """
    Perform MD5 length extension attack.
    original_mac: hex string of H(secret || original_data)
    """
    # Parse MAC into MD5 internal state (4 × 32-bit words, little-endian)
    h = struct.unpack('<4I', bytes.fromhex(original_mac))

    # Calculate total length after padding
    total_original = secret_len + original_data_len
    padding = md5_padding(total_original)
    forged_len = total_original + len(padding) + len(extension)

    # Continue MD5 from saved state with extension
    # (requires MD5 implementation that accepts initial state)
    from hashlib import md5
    # Most stdlib md5 doesn't expose state setting
    # Use: hlextend library or custom MD5

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

    return new_hash, new_data

---

2. MD5 衝突攻撃

2.1 同一プレフィックス衝突（fastcoll）

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

# Generate collision pair
fastcoll -p prefix_file -o collision1.bin collision2.bin

# Result: MD5(collision1.bin) == MD5(collision2.bin)
# Files differ in exactly 128 bytes (two MD5 blocks)

2.2 選択プレフィックス衝突（hashclash）

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

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

# Result: MD5(prefix1 || suffix1) == MD5(prefix2 || suffix2)

2.3 UniColl（単一ブロックのニア衝突）

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

Application: forge two PDF/PE files with same MD5
  - File 1: benign content
  - File 2: malicious content
  - Same MD5 hash

2.4 衝突の用途

用途	手法	影響
証明書の偽造	選択プレフィックス	不正な CA 証明書（2008 年に実証）
バイナリの置き換え	同一プレフィックス＋条件付き	MD5 が同じで、動作が異なる 2 つの実行ファイル
PDF の衝突	UniColl	異なる内容を表示する 2 つの PDF
Git コミットの衝突	選択プレフィックス（SHA1 の SHAttered）	同じハッシュを持つ 2 つのコミット
CTF：MD5 チェックの回避	fastcoll	異なる 2 つの入力が同一として受け入れられる

2.5 CTF における MD5 衝突のテクニック

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

// Method 1: Array trick (not real collision)
?a[]=1&b[]=2  // md5(array) returns NULL, NULL == NULL

// Method 2: Real collision (fastcoll output, URL-encoded binary)
?a=<collision1_urlencoded>&b=<collision2_urlencoded>

// Method 3: 0e magic hashes (loose comparison ==)
// md5("240610708") = "0e462097431906509019562988736854"
// md5("QNKCDZO")   = "0e830400451993494058024219903391"
// PHP: "0e..." == "0e..." is TRUE (both evaluate to 0 as floats)

---

3. SHA-1 衝突

3.1 SHAttered 攻撃（2017 年）

実用的な SHA-1 衝突の初の実証例：同じ SHA-1 を持つ 2 つの PDF ファイルです。

• 計算量：約 2^63 回の SHA-1 計算
• コスト：GPU クラスターで約 11 万ドル（2017 年の価格）
• ツール：shattered.io で衝突する PDF を提供

3.2 SHA-1 の選択プレフィックス衝突（2020 年）

• 計算量：約 2^63.4 回の計算
• PGP/GnuPG キーサーバーへの攻撃に実用可能
• SHA-1 の衝突耐性が破られていることを実証

3.3 影響

SHA-1 should NOT be used for:
  ✗ Digital signatures
  ✗ Certificate fingerprints
  ✗ Git commit integrity (migration to SHA-256 in progress)
  ✗ Deduplication based on hash

SHA-1 is still OK for:
  ✓ HMAC-SHA1 (collision resistance not required)
  ✓ HKDF-SHA1 (PRF security suffices)
  ✓ Non-adversarial checksums

---

4. 誕生日攻撃

4.1 一般的な誕生日境界

For n-bit hash: expected collisions after ~2^(n/2) hashes

Hash     Bits    Birthday bound
MD5      128     2^64
SHA-1    160     2^80
SHA-256  256     2^128

CTF application: if hash is truncated to k bits,
collision in ~2^(k/2) attempts

4.2 誕生日攻撃の実装

import hashlib
import os

def birthday_attack(hash_func, output_bits, max_attempts=2**28):
    """Find collision for truncated hash."""
    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  # collision!
        seen[h] = msg

    return None

# Example: find collision for first 32 bits of SHA-256
result = birthday_attack(hashlib.sha256, 32)

---

5. HMAC タイミング攻撃

5.1 脆弱な比較

# VULNERABLE: early-exit string comparison
def verify_hmac(received, expected):
    return received == expected  # Python == compares left to right

# The comparison may short-circuit on first differing byte,
# leaking timing information

5.2 攻撃戦略

import requests
import time

def hmac_timing_attack(url, data, hmac_len=32):
    """Byte-by-byte HMAC recovery via timing."""
    known = ""

    for pos in range(hmac_len * 2):  # hex chars
        best_char = ""
        best_time = 0

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

            for _ in range(50):  # multiple samples for accuracy
                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]  # median
            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

# SECURE: constant-time comparison
def verify_hmac_secure(received, expected):
    return hmac.compare_digest(received, expected)

---

6. ミートインザミドル（ハッシュ）

6.1 概念

ハッシュ計算を 2 つに分割し、一方を事前計算して、もう一方と照合します。

Hash computation: H = f(g(x₁), h(x₂))

Precompute: table[g(x₁)] = x₁  for all x₁ in space₁
Search:     for each x₂ in space₂:
              if h(x₂) in table:
                found! (x₁, x₂)

Time:  O(2^(n/2)) instead of O(2^n)
Space: O(2^(n/2))

---

7. ハッシュのプルーフ・オブ・ワーク

7.1 一般的なCTF PoW形式

# Format 1: Find x such that SHA256(prefix + x) starts with N zero bits
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

# Format 2: Find x such that SHA256(x) ends with specific suffix
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

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

---

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

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

Precomputed chain: password → hash → reduce → password₂ → hash₂ → ...
Lookup: given hash h, check if h appears in any chain
Time-memory tradeoff: less space than full table, more time than direct lookup

8.2 ソルトでレインボーテーブルを無効化する

Without salt: H(password) — same password always produces same hash
With salt:    H(salt || password) — different salt per user

Rainbow tables are password-specific, not (salt+password)-specific
Each unique salt requires a separate table → infeasible

8.3 最新のパスワードハッシュ

アルゴリズム	ソルト	反復回数	メモリ負荷が高い	推奨
MD5	なし	1	いいえ	決して使わない
SHA-256	なし	1	いいえ	パスワードには決して使わない
bcrypt	あり	設定可能	いいえ	はい
scrypt	あり	設定可能	はい	はい
Argon2	あり	設定可能	はい	最適な選択肢
PBKDF2	あり	設定可能	いいえ	許容可能

---

9. 判断フローチャート

Hash-related challenge — what's the scenario?
│
├─ Have H(secret || message), need to extend?
│  ├─ Hash is MD5/SHA1/SHA256/SHA512?
│  │  └─ Yes → Length extension attack
│  │     └─ Need: MAC value, original message, secret length
│  │        └─ Tool: HashPump or hash_extender
│  │
│  └─ Hash is SHA3/HMAC/BLAKE2?
│     └─ Length extension doesn't work
│        └─ Look for other vulnerabilities
│
├─ Need two inputs with same hash?
│  ├─ MD5?
│  │  ├─ Same prefix → fastcoll (seconds)
│  │  ├─ Different prefixes → hashclash (hours)
│  │  └─ CTF PHP loose comparison → 0e magic hashes
│  │
│  ├─ SHA-1?
│  │  └─ SHAttered (expensive, use precomputed if possible)
│  │
│  └─ SHA-256+?
│     └─ No practical collision attack
│        └─ Look for logic flaws instead
│
├─ Need to forge HMAC?
│  ├─ Timing side channel available?
│  │  └─ Byte-by-byte timing attack
│  │
│  ├─ Key is short/weak?
│  │  └─ Brute force key with hashcat
│  │
│  └─ No weakness?
│     └─ HMAC is secure — look elsewhere
│
├─ Hash is truncated (short output)?
│  └─ Birthday attack — collision in 2^(bits/2)
│
├─ Proof of work?
│  └─ Brute force with parallel computation
│     ├─ Python multiprocessing for < 28 bits
│     ├─ hashcat/GPU for > 28 bits
│     └─ Optimize: pre-increment string, avoid re-encoding
│
└─ Password hash cracking?
   ├─ No salt → rainbow tables (pre-computed)
   ├─ Known salt → hashcat / John the Ripper
   └─ Memory-hard (Argon2/scrypt) → limited by memory, slow brute force

---

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	ハッシュのすばやい計算とエンコード	ウェブベース