SKILL: 対称暗号攻撃 — エキスパート暗号解析プレイブック

AI LOAD INSTRUCTION: CTF および認可されたテストにおける対称暗号化攻撃のエキスパート技法。CBC パディングオラクル、CBC ビット反転、ECB 検出と悪用、ストリーム暗号の鍵再利用、LFSR/LCG 状態復元、RC4 バイアス、中間一致攻撃をカバーしています。ベースモデルは ECB と CBC の攻撃戦略を混同したり、バイト単位の ECB 復号化をセットアップできなかったりすることがよくあります。

0. 関連ルーティング

• rsa-attack-techniques 対称暗号鍵が RSA で保護されている場合
• hash-attack-techniques HMAC またはハッシュベースの認証が関係する場合
• lattice-crypto-attacks ラティス法による LCG/LFSR 状態復元の場合

高度なリファレンス

以下が必要な場合は BLOCK_CIPHER_ATTACKS.md も読み込んでください:

• 完全な Python 実装を含む詳細な攻撃スクリプト
• バイト単位の ECB ウォークスルーのステップバイステップ解説
• PadBuster の使用方法とカスタムパディングオラクルスクリプト
• LCG/LFSR 復元の実装

クイック攻撃選択

観測される動作	想定される弱点	攻撃
同一平文 → 同一暗号文(ブロック境界)	ECB モード	カット・アンド・ペースト / バイト単位
パディングエラーが区別可能	CBC パディングオラクル	鍵なしで復号化
暗号文を変更可能、次ブロックに影響	CBC モード、整合性チェックなし	ビット反転
XOR/ストリーム暗号で鍵再利用	Two-time pad	暗号文同士を XOR
予測可能な PRNG 出力	LCG または LFSR	状態復元
二重暗号化を使用	2DES 類似	中間一致

---

1. パディングオラクル攻撃(CBC モード)

1.1 メカニズム

CBC 復号化: P_i = D_K(C_i) ⊕ C_{i-1}

サーバーがパディング(PKCS#7)の妥当性を明かす場合、前のブロックの暗号文を操作することで、鍵を知らずに任意のブロックを復号化できます。

1.2 攻撃手順

対象: ブロック C_i を復号化(未知の平文 P_i)

バイト位置 b = 15 から 0 まで(最後のバイトから):
  padding_value = 16 - b
  
  推測値 = 0x00 から 0xFF:
    修正前ブロック C'_{i-1} を構築:
      - バイト 0..b-1: 元の C_{i-1} のバイト
      - バイト b: 推測値
      - バイト b+1..15: 正しいパディングを生成するよう計算
    
    (C'_{i-1} || C_i) をオラクルに送信
    
    オラクルが「パディング有効」と言った場合:
      中間バイト[b] = 推測値 ⊕ padding_value
      平文バイト[b] = 中間バイト[b] ⊕ 元の C_{i-1}[b]

1.3 Python 実装

def padding_oracle_attack(ciphertext, block_size, oracle):
    """
    oracle(ct) はパディングが有効な場合 True、そうでない場合 False を返します。
    ciphertext には IV が最初のブロックとして含まれます。
    """
    blocks = [ciphertext[i:i+block_size] for i in range(0, len(ciphertext), block_size)]
    plaintext = b""

    for block_idx in range(1, len(blocks)):
        prev_block = bytearray(blocks[block_idx - 1])
        curr_block = blocks[block_idx]
        intermediate = [0] * block_size
        decrypted = [0] * block_size

        for byte_pos in range(block_size - 1, -1, -1):
            padding_val = block_size - byte_pos

            for guess in range(256):
                modified = bytearray(block_size)
                modified[byte_pos] = guess

                for j in range(byte_pos + 1, block_size):
                    modified[j] = intermediate[j] ^ padding_val

                test_ct = bytes(modified) + curr_block
                if oracle(test_ct):
                    if byte_pos == block_size - 1:
                        # 誤検出を検証(パディング 0x02 0x02)
                        check = bytearray(modified)
                        check[byte_pos - 1] ^= 1
                        if not oracle(bytes(check) + curr_block):
                            continue

                    intermediate[byte_pos] = guess ^ padding_val
                    decrypted[byte_pos] = intermediate[byte_pos] ^ prev_block[byte_pos]
                    break

        plaintext += bytes(decrypted)

    return plaintext

1.4 ツール

# PadBuster
padbuster http://target/decrypt?ct= CIPHERTEXT_HEX 16 -encoding 0
padbuster http://target/decrypt?ct= CIPHERTEXT_HEX 16 -encoding 0 -plaintext "admin=true"

---

2. CBC ビット反転

2.1 概念

C_{i-1} の位置 j のビットを反転すると、P_i の位置 j の同じビットも反転します(ただし P_{i-1} は破損します)。

元の状態:   P_i[j] = D_K(C_i)[j] ⊕ C_{i-1}[j]
修正後:    P'_i[j] = D_K(C_i)[j] ⊕ C'_{i-1}[j]
                    = P_i[j] ⊕ (C_{i-1}[j] ⊕ C'_{i-1}[j])

2.2 実践例

def cbc_bitflip(ciphertext, block_size, target_byte_pos, old_value, new_value):
    """
    暗号文ブロック N を修正することで、平文ブロック N+1 のバイトを反転させます。
    target_byte_pos: 平文内の絶対位置(0 始まり)
    """
    ct = bytearray(ciphertext)
    block_num = target_byte_pos // block_size
    byte_in_block = target_byte_pos % block_size

    # 前のブロック(block_num - 1)を修正してターゲットバイトを反転
    modify_pos = (block_num - 1) * block_size + byte_in_block

    # XOR して古い値をキャンセルし、新しい値を設定
    ct[modify_pos] ^= old_value ^ new_value
    return bytes(ct)

# 例: "admin=0" を "admin=1" に反転
# "admin=0" がバイト位置 22(ブロック 1、バイト 6)にある場合:
modified_ct = cbc_bitflip(ciphertext, 16, 22, ord('0'), ord('1'))

---

3. ECB モード攻撃

3.1 検出

def detect_ecb(ciphertext, block_size=16):
    """ECB モードは同一の平文ブロックに対して同一の暗号文ブロックを生成します。"""
    blocks = [ciphertext[i:i+block_size] for i in range(0, len(ciphertext), block_size)]
    return len(blocks) != len(set(blocks))

# 強制検出: 繰り返される平文を送信
test_input = b"A" * 48  # 少なくとも 3 ブロックの同一データ
# レスポンスが繰り返されたブロックを含む場合 → ECB

3.2 ECB カット・アンド・ペースト

暗号文ブロックを並べ替えて、新しい有効な平文を作成します。

元のブロック:
  ブロック 0: "email=foo@bar.c"
  ブロック 1: "om&role=user&uid"
  ブロック 2: "=10\x0d\x0d\x0d..."

攻撃: "admin" + パディングが独自のブロックに着地するように入力を工夫し、
それを "user" ブロックの場所に入れ替えます。

ステップ 1: "admin" + PKCS7 がブロックに合致するメールを送信:
  email = "foo@bar.coadmin\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b"
  → ブロック 1 は "admin\x0b\x0b..." を暗号化(このブロックを保存)

ステップ 2: "role=" がブロック終端に来るメールを送信:
  email = "foo@bar.co"
  → ブロック 2 = "=user&uid=10..."(ただしこれを置換)

ステップ 3: 最後のブロックを保存した "admin\x0b..." ブロックで置換

3.3 バイト単位の ECB 復号化

不明なサフィックスを 1 バイトずつ復号化します。

def ecb_byte_at_a_time(encrypt_oracle, block_size=16):
    """
    encrypt_oracle(input_bytes) = AES_ECB(input || unknown_secret)
    unknown_secret を返します。
    """
    secret = b""
    secret_len = len(encrypt_oracle(b"")) 

    for i in range(secret_len):
        block_num = i // block_size
        pad_len = block_size - 1 - (i % block_size)
        padding = b"A" * pad_len

        # ルックアップテーブルを構築
        target_ct = encrypt_oracle(padding)
        target_block = target_ct[block_num * block_size:(block_num + 1) * block_size]

        for byte_val in range(256):
            test_input = padding + secret + bytes([byte_val])
            test_ct = encrypt_oracle(test_input)
            test_block = test_ct[block_num * block_size:(block_num + 1) * block_size]

            if test_block == target_block:
                secret += bytes([byte_val])
                break

    return secret

---

4. ストリーム暗号攻撃

4.1 既知平文 / 鍵再利用(Two-Time Pad)

def two_time_pad(c1, c2, known_crib=None):
    """
    c1 = m1 ⊕ K, c2 = m2 ⊕ K (同じ鍵 K)
    c1 ⊕ c2 = m1 ⊕ m2 (鍵がキャンセル)
    """
    xored = bytes(a ^ b for a, b in zip(c1, c2))

    if known_crib:
        results = []
        for offset in range(len(xored) - len(known_crib) + 1):
            candidate = bytes(
                xored[offset + i] ^ known_crib[i] for i in range(len(known_crib))
            )
            if all(0x20 <= b <= 0x7e for b in candidate):
                results.append((offset, candidate))
        return results
    return xored

4.2 単一バイト XOR ブルートフォース

def single_byte_xor_crack(ciphertext):
    """周波数分析を使用して、単一バイト XOR 鍵をブルートフォースします。"""
    english_freq = {
        'e': 12.7, 't': 9.1, 'a': 8.2, 'o': 7.5, 'i': 7.0,
        'n': 6.7, 's': 6.3, 'h': 6.1, 'r': 6.0, 'd': 4.3,
    }
    best_score, best_key, best_plaintext = 0, 0, b""

    for key in range(256):
        plaintext = bytes(b ^ key for b in ciphertext)
        score = sum(
            english_freq.get(chr(b).lower(), 0)
            for b in plaintext if 0x20 <= b <= 0x7e
        )
        if score > best_score:
            best_score = score
            best_key = key
            best_plaintext = plaintext

    return best_key, best_plaintext

4.3 繰り返しキー XOR(Kasiski 風)

def repeating_xor_crack(ciphertext, max_keylen=40):
    """ハミング距離を使用して繰り返しキー XOR をクラックしてキー長を求めます。"""
    def hamming(a, b):
        return sum(bin(x ^ y).count('1') for x, y in zip(a, b))

    # キー長を特定
    scores = []
    for kl in range(2, max_keylen + 1):
        blocks = [ciphertext[i:i+kl] for i in range(0, len(ciphertext) - kl, kl)]
        if len(blocks) < 4:
            continue
        dist = sum(hamming(blocks[i], blocks[i+1]) for i in range(min(3, len(blocks)-1)))
        normalized = dist / (min(3, len(blocks)-1) * kl)
        scores.append((normalized, kl))

    best_keylen = sorted(scores)[0][1]

    # 単一バイト XOR で各位置をクラック
    key = b""
    for i in range(best_keylen):
        column = bytes(ciphertext[j] for j in range(i, len(ciphertext), best_keylen))
        k, _ = single_byte_xor_crack(column)
        key += bytes([k])

    return key

4.4 LFSR 状態復元(Berlekamp-Massey)

def berlekamp_massey_gf2(output_bits):
    """出力シーケンスから GF(2) 上の LFSR フィードバック多項式を復元します。"""
    n = len(output_bits)
    C = [0] * (n + 1)
    B = [0] * (n + 1)
    C[0] = B[0] = 1
    L = 0
    m = 1
    b = 1

    for N in range(n):
        d = output_bits[N]
        for i in range(1, L + 1):
            d ^= C[i] & output_bits[N - i]

        if d == 0:
            m += 1
        elif 2 * L <= N:
            T = C[:]
            for i in range(m, n + 1):
                C[i] ^= B[i - m]
            L = N + 1 - L
            B = T
            b = d
            m = 1
        else:
            for i in range(m, n + 1):
                C[i] ^= B[i - m]
            m += 1

    return C[:L + 1], L

4.5 RC4 バイアス

バイアス	説明	悪用方法
初期バイトバイアス	P(K[0] = 0) ≈ 2/256(通常の 2 倍)	最初のバイトの統計的平文復元
Fluhrer-Mantin-Shamir	IV 付き弱い鍵スケジューリング	WEP 攻撃(歴史的)
NOMORE 攻撃	キーストリーム全体の長期バイアス	TLS/RC4 平文復元(2^24-2^26 暗号文)
不変性の弱点	キー依存のストリーム全体のバイアス	多くの暗号化への統計的攻撃

---

5. 中間一致

5.1 二重暗号化攻撃

二重暗号化: C = E_K2(E_K1(P))
ブルートフォース: 2^(2n) 予想
MITM:        2^(n+1) + 2^n エントリのストレージ

攻撃:
1. すべての K1 で P を暗号化 → テーブルに (E_K1(P), K1) を格納
2. すべての K2 で C を復号化 → D_K2(C) がエントリと一致するか確認
3. マッチ発見 → (K1, K2) 復元

from itertools import product

def meet_in_the_middle(encrypt, decrypt, plaintext, ciphertext, keyspace_bits):
    """二重暗号化への MITM 攻撃。"""
    # フェーズ 1: 暗号化テーブルを構築
    enc_table = {}
    for k1 in range(2**keyspace_bits):
        intermediate = encrypt(plaintext, k1)
        enc_table[intermediate] = k1

    # フェーズ 2: 復号化してルックアップ
    for k2 in range(2**keyspace_bits):
        intermediate = decrypt(ciphertext, k2)
        if intermediate in enc_table:
            k1 = enc_table[intermediate]
            return k1, k2

    return None

---

6. 決定ツリー

対称暗号チャレンジ — 何を観測できますか?
│
├─ モードを検出できますか?
│  ├─ 繰り返し入力 → 繰り返されたブロック出力?
│  │  └─ はい → ECB モード
│  │     ├─ プレフィックスを制御可能 → バイト単位の復号化
│  │     ├─ ブロックを並べ替え可能 → カット・アンド・ペースト
│  │     └─ ブロック境界を検出可能 → ブロック配置オラクル
│  │
│  ├─ パディング不正のエラーメッセージが異なる?
│  │  └─ はい → パディングオラクル(CBC)
│  │     └─ PadBuster またはカスタムスクリプト
│  │
│  └─ 暗号文を修正して効果を観測できる?
│     └─ 次ブロックの平文が変わる → CBC ビット反転
│
├─ ストリーム暗号または XOR?
│  ├─ 異なるメッセージで鍵が再利用される?
│  │  └─ 暗号文同士を XOR → crib drag
│  │
│  ├─ 既知の平文-暗号文ペアがある?
│  │  └─ キーストリームを直接復元
│  │
│  ├─ 単一バイト XOR 鍵?
│  │  └─ 周波数分析で 256 個の鍵をブルートフォース
│  │
│  ├─ 繰り返しキー XOR?
│  │  └─ ハミング距離 → キー長 → 位置ごとのクラック
│  │
│  └─ LFSR ベース?
│     └─ Berlekamp-Massey で状態/多項式復元
│
├─ PRNG ベースの暗号?
│  ├─ LCG → 切り詰めた出力ラティス攻撃
│  ├─ Mersenne Twister → 624 出力 → 完全な状態復元
│  └─ カスタム PRNG → 周期と状態サイズを分析
│
├─ 二重 / 三重暗号化?
│  └─ 中間一致
│
└─ RC4 の場合?
   ├─ 単一暗号化 → 初期バイトバイアス
   ├─ 多くの同一鍵暗号化 → 統計的攻撃
   └─ IV をキーにプリペンド → FMS 攻撃(WEP 類似)

---

7. ツール

ツール	用途
PadBuster	自動パディングオラクル悪用
xortool	繰り返しキー XOR 分析(キー長検出 + クラック)
CyberChef	クイック XOR、エンコーディング、ブロック暗号操作
SageMath	LFSR/LCG 分析、ラティスベースの復元
pycryptodome	テスト用の AES/DES 実装
hashcat	対称暗号鍵ブルートフォース(GPU 高速化)
カスタム Python	上記のすべての攻撃は純 Python で実装可能