Symmetric Cipher Attacks

SKILL: Symmetric Cipher Attacks — Expert Cryptanalysis Playbook

AI LOAD INSTRUCTION: Expert techniques for attacking symmetric encryption in CTF and authorized testing. Covers CBC padding oracle, CBC bit flipping, ECB detection and exploitation, stream cipher key reuse, LFSR/LCG state recovery, RC4 biases, and meet-in-the-middle attacks. Base models often confuse ECB and CBC attack strategies or fail to set up byte-at-a-time ECB decryption correctly.

0. RELATED ROUTING

• rsa-attack-techniques when symmetric key is protected by RSA
• hash-attack-techniques when HMAC or hash-based authentication is involved
• lattice-crypto-attacks for LCG/LFSR state recovery via lattice methods

Advanced Reference

Also load BLOCK_CIPHER_ATTACKS.md when you need:

• Detailed attack scripts with full Python implementations
• Step-by-step byte-at-a-time ECB walkthrough
• PadBuster usage and custom padding oracle scripts
• LCG/LFSR recovery implementation

Quick attack selection

---

1. PADDING ORACLE ATTACK (CBC MODE)

1.1 Mechanism

CBC decryption: P_i = D_K(C_i) ⊕ C_{i-1}

If the server reveals whether padding is valid (PKCS#7), we can decrypt any block by manipulating the previous ciphertext block.

1.2 Attack Steps

Target: decrypt block C_i (with unknown plaintext P_i)

For byte position b = 15 down to 0 (last byte first):
  padding_value = 16 - b
  
  For guess = 0x00 to 0xFF:
    Construct modified C'_{i-1}:
      - Bytes 0..b-1: original C_{i-1} bytes
      - Byte b: guess
      - Bytes b+1..15: calculated to produce correct padding
    
    Send (C'_{i-1} || C_i) to oracle
    
    If oracle says "valid padding":
      intermediate_byte[b] = guess ⊕ padding_value
      plaintext_byte[b] = intermediate_byte[b] ⊕ original_C_{i-1}[b]

1.3 Python Implementation

def padding_oracle_attack(ciphertext, block_size, oracle):
    """
    oracle(ct) returns True if padding is valid, False otherwise.
    ciphertext includes IV as first block.
    """
    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:
                        # Verify it's not a false positive (padding 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 Tools

# 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 BIT FLIPPING

2.1 Concept

Flipping bit at position j in C_{i-1} flips the same bit at position j in P_i (and corrupts all of P_{i-1}).

Original:  P_i[j] = D_K(C_i)[j] ⊕ C_{i-1}[j]
Modified:  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 Practical Example

def cbc_bitflip(ciphertext, block_size, target_byte_pos, old_value, new_value):
    """
    Flip byte in plaintext block N+1 by modifying ciphertext block N.
    target_byte_pos: absolute position in plaintext (0-indexed)
    """
    ct = bytearray(ciphertext)
    block_num = target_byte_pos // block_size
    byte_in_block = target_byte_pos % block_size

    # Modify previous block (block_num - 1) to flip target byte
    modify_pos = (block_num - 1) * block_size + byte_in_block

    # XOR to cancel old value and set new value
    ct[modify_pos] ^= old_value ^ new_value
    return bytes(ct)

# Example: flip "admin=0" to "admin=1"
# If "admin=0" is at byte position 22 (block 1, byte 6):
modified_ct = cbc_bitflip(ciphertext, 16, 22, ord('0'), ord('1'))

---

3. ECB MODE ATTACKS

3.1 Detection

def detect_ecb(ciphertext, block_size=16):
    """ECB produces identical blocks for identical plaintext blocks."""
    blocks = [ciphertext[i:i+block_size] for i in range(0, len(ciphertext), block_size)]
    return len(blocks) != len(set(blocks))

# Force detection: send repeated plaintext
test_input = b"A" * 48  # at least 3 blocks of identical data
# If response has repeated blocks → ECB

3.2 ECB Cut-and-Paste

Reorder ciphertext blocks to create new valid plaintexts.

Original blocks:
  Block 0: "email=foo@bar.c"
  Block 1: "om&role=user&uid"
  Block 2: "=10\x0d\x0d\x0d..."

Attack: craft input so "admin" + padding lands in its own block,
then swap it in place of "user" block.

Step 1: Send email that aligns "admin" + PKCS7 to a block:
  email = "foo@bar.coadmin\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b"
  → Block 1 encrypts "admin\x0b\x0b..."  (save this block)

Step 2: Send email that puts "role=" at end of block:
  email = "foo@bar.co"
  → Block 2 = "=user&uid=10..."  (but we replace this)

Step 3: Replace last block with saved "admin\x0b..." block

3.3 Byte-at-a-Time ECB Decryption

Decrypt unknown appended secret one byte at a time.

def ecb_byte_at_a_time(encrypt_oracle, block_size=16):
    """
    encrypt_oracle(input_bytes) = AES_ECB(input || unknown_secret)
    Returns the 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

        # Build lookup table
        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. STREAM CIPHER ATTACKS

4.1 Known Plaintext / Key Reuse (Two-Time Pad)

def two_time_pad(c1, c2, known_crib=None):
    """
    c1 = m1 ⊕ K, c2 = m2 ⊕ K (same key K)
    c1 ⊕ c2 = m1 ⊕ m2 (key cancels)
    """
    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 Single-Byte XOR Brute Force

def single_byte_xor_crack(ciphertext):
    """Brute force single-byte XOR key using frequency analysis."""
    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 Repeating-Key XOR (Kasiski-like)

def repeating_xor_crack(ciphertext, max_keylen=40):
    """Crack repeating-key XOR using Hamming distance for key length."""
    def hamming(a, b):
        return sum(bin(x ^ y).count('1') for x, y in zip(a, b))

    # Find key length
    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]

    # Crack each position with single-byte 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 State Recovery (Berlekamp-Massey)

def berlekamp_massey_gf2(output_bits):
    """Recover LFSR feedback polynomial from output sequence over GF(2)."""
    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 Biases

---

5. MEET-IN-THE-MIDDLE

5.1 Double Encryption Attack

Double encryption: C = E_K2(E_K1(P))
Brute force: 2^(2n) expected
MITM:        2^(n+1) + storage for 2^n entries

Attack:
1. Encrypt P with all possible K1 → store (E_K1(P), K1) in table
2. Decrypt C with all possible K2 → check if D_K2(C) matches any entry
3. Match found → (K1, K2) recovered

from itertools import product

def meet_in_the_middle(encrypt, decrypt, plaintext, ciphertext, keyspace_bits):
    """MITM attack on double encryption."""
    # Phase 1: build encryption table
    enc_table = {}
    for k1 in range(2**keyspace_bits):
        intermediate = encrypt(plaintext, k1)
        enc_table[intermediate] = k1

    # Phase 2: decrypt and look up
    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. DECISION TREE

Symmetric cipher challenge — what can you observe?
│
├─ Can you detect the mode?
│  ├─ Repeated input → repeated output blocks?
│  │  └─ Yes → ECB mode
│  │     ├─ Can control prefix → byte-at-a-time decryption
│  │     ├─ Can reorder blocks → cut-and-paste
│  │     └─ Can detect block boundaries → block alignment oracle
│  │
│  ├─ Error message differs for bad padding?
│  │  └─ Yes → Padding oracle (CBC)
│  │     └─ PadBuster or custom script
│  │
│  └─ Can modify ciphertext and observe effect?
│     └─ Next-block plaintext changes → CBC bit flipping
│
├─ Stream cipher or XOR?
│  ├─ Key reused on different messages?
│  │  └─ XOR ciphertexts → crib drag
│  │
│  ├─ Known plaintext-ciphertext pair?
│  │  └─ Recover keystream directly
│  │
│  ├─ Single-byte XOR key?
│  │  └─ Brute force 256 keys with frequency analysis
│  │
│  ├─ Repeating-key XOR?
│  │  └─ Hamming distance → key length → per-position crack
│  │
│  └─ LFSR-based?
│     └─ Berlekamp-Massey for state/polynomial recovery
│
├─ PRNG-based cipher?
│  ├─ LCG → truncated output lattice attack
│  ├─ Mersenne Twister → 624 outputs → full state recovery
│  └─ Custom PRNG → analyze period and state size
│
├─ Double / triple encryption?
│  └─ Meet-in-the-middle
│
└─ RC4 specifically?
   ├─ Single encryption → initial byte bias
   ├─ Many encryptions same key → statistical attack
   └─ IV prepended to key → FMS attack (WEP-like)

---

7. TOOLS

Block Cipher Attacks — Detailed Scripts & Walkthrough

AI LOAD INSTRUCTION: Load this when you need full attack implementations, step-by-step walkthroughs, and edge-case handling for block cipher exploitation. Assumes the main SKILL.md is already loaded for attack selection and decision trees.

---

1. PADDING ORACLE — FULL WALKTHROUGH

1.1 PKCS#7 Padding Review

Block size: 16 bytes
Data "HELLO" (5 bytes) → padded to 16 bytes:
  48 45 4C 4C 4F 0B 0B 0B 0B 0B 0B 0B 0B 0B 0B 0B
  
Valid padding examples (last byte determines):
  ...01           → 1 byte of padding
  ...02 02        → 2 bytes of padding
  ...03 03 03     → 3 bytes of padding
  ...10 10 10 ... → 16 bytes (full block of padding)

Invalid:
  ...03 03 04     → last byte says 4, but 3rd-from-end ≠ 04
  ...00           → 0x00 is never valid PKCS#7

1.2 Attack Internals — Byte-by-Byte Decryption

Target: decrypt P[15] (last byte of target block)

CBC decryption internals:
  I[15] = AES_DEC(C_target)[15]    (intermediate value, unknown)
  P[15] = I[15] ⊕ C_prev[15]       (plaintext = intermediate ⊕ prev ciphertext)

Attack for padding 0x01 (valid when last plaintext byte = 0x01):
  We send: C'_prev || C_target
  Where C'_prev[15] = guess

  Server computes: P'[15] = I[15] ⊕ guess
  If P'[15] == 0x01, padding is valid!
  
  Therefore: I[15] = guess ⊕ 0x01
  And: P[15] = I[15] ⊕ original_C_prev[15]

Next: decrypt P[14] (need padding = 0x02 0x02):
  Set C'_prev[15] = I[15] ⊕ 0x02   (forces P'[15] = 0x02)
  Brute force C'_prev[14] until P'[14] = 0x02

Continue until all 16 bytes recovered.

1.3 Handling False Positives

def is_real_padding(oracle, modified_block, target_block, byte_pos, block_size):
    """
    When cracking the last byte, padding 0x02 0x02 can give false positive.
    Verify by flipping the penultimate byte — if still valid, it was 0x01.
    """
    if byte_pos != block_size - 1:
        return True

    check = bytearray(modified_block)
    check[byte_pos - 1] ^= 1  # flip adjacent byte
    return oracle(bytes(check) + target_block)

1.4 Encryption via Padding Oracle (CBC-R)

A padding oracle can also encrypt arbitrary plaintext without the key:

def padding_oracle_encrypt(plaintext, block_size, oracle):
    """Encrypt arbitrary plaintext using padding oracle (CBC-R technique)."""
    # Pad plaintext
    pad_len = block_size - (len(plaintext) % block_size)
    padded = plaintext + bytes([pad_len] * pad_len)
    pt_blocks = [padded[i:i+block_size] for i in range(0, len(padded), block_size)]

    # Start with random last ciphertext block
    import os
    ct_blocks = [os.urandom(block_size)]

    # Work backwards
    for pt_block in reversed(pt_blocks):
        # Use padding oracle to find intermediate values for ct_blocks[0]
        intermediate = decrypt_block_intermediate(ct_blocks[0], block_size, oracle)
        # Previous CT block = intermediate ⊕ desired plaintext
        prev_ct = bytes(i ^ p for i, p in zip(intermediate, pt_block))
        ct_blocks.insert(0, prev_ct)

    return b"".join(ct_blocks)  # first block is IV

---

2. CBC BIT FLIPPING — ADVANCED SCENARIOS

2.1 Multi-Byte Flip

def cbc_multibyte_flip(ciphertext, block_size, changes):
    """
    changes: list of (absolute_position, old_byte, new_byte)
    All changes must be in the SAME target block.
    """
    ct = bytearray(ciphertext)

    for pos, old, new in changes:
        target_block = pos // block_size
        byte_in_block = pos % block_size
        prev_block_pos = (target_block - 1) * block_size + byte_in_block
        ct[prev_block_pos] ^= old ^ new

    return bytes(ct)

# Example: change ";admin=false;" to ";admin=true;x"
changes = [
    (32 + 7, ord('f'), ord('t')),   # f → t
    (32 + 8, ord('a'), ord('r')),   # a → r
    (32 + 9, ord('l'), ord('u')),   # l → u
    (32 + 10, ord('s'), ord('e')),  # s → e
    (32 + 11, ord('e'), ord(';')),  # e → ;
    (32 + 12, ord(';'), ord('x')),  # ; → x (pad)
]

2.2 Dealing with Corrupted Block

The previous block gets corrupted. Strategies:

• If corrupted block is IV: server may not validate IV content
• If corrupted block is a "don't care" field: acceptable corruption
• Two-block technique: use padding oracle to fix the corrupted block

---

3. ECB BYTE-AT-A-TIME — COMPLETE WALKTHROUGH

Step-by-Step Example

Server: encrypt(user_input || secret)
Block size: 16
Secret: "FLAG{example}"

Round 1: Find block size
  Send "A", "AA", "AAA", ...
  Watch ciphertext length — when it jumps by 16, block size = 16

Round 2: Confirm ECB
  Send "A" * 32 → check for repeated blocks

Round 3: Decrypt byte 0
  Send "A" * 15 (pad to align secret[0] at end of block 0)
  
  Ciphertext block 0 = E("AAAAAAAAAAAAAAA" + secret[0])
  
  Build table:
    E("AAAAAAAAAAAAAAA" + chr(0))  → block_0_0
    E("AAAAAAAAAAAAAAA" + chr(1))  → block_0_1
    ...
    E("AAAAAAAAAAAAAAA" + "F")     → block_0_70  ← matches!
  
  secret[0] = "F"

Round 4: Decrypt byte 1
  Send "A" * 14
  
  Ciphertext block 0 = E("AAAAAAAAAAAAAA" + "F" + secret[1])
  
  Build table with known prefix "AAAAAAAAAAAAAAAF":
    E("AAAAAAAAAAAAAA" + "F" + chr(0))  → ...
    E("AAAAAAAAAAAAAA" + "F" + "L")     → matches!
  
  secret[1] = "L"

Continue until all bytes recovered.

3.1 Handling Prefix

If server adds unknown prefix: encrypt(prefix || user_input || secret)

def find_prefix_length(encrypt_oracle, block_size):
    """Determine length of unknown prefix."""
    # Find which block the prefix ends in
    base = encrypt_oracle(b"")
    for i in range(1, block_size + 1):
        test = encrypt_oracle(b"A" * i)
        # Find first block that differs from base
        for b in range(len(base) // block_size):
            base_block = base[b*block_size:(b+1)*block_size]
            test_block = test[b*block_size:(b+1)*block_size]
            if base_block != test_block:
                # Prefix ends in block b
                # Now find exact byte offset within block
                for j in range(1, block_size + 1):
                    t1 = encrypt_oracle(b"A" * j)
                    t2 = encrypt_oracle(b"B" * j)
                    if (t1[b*block_size:(b+1)*block_size] !=
                        t2[b*block_size:(b+1)*block_size]):
                        continue
                    return b * block_size + (block_size - j)
    return 0

---

4. LCG STATE RECOVERY

4.1 Known Outputs (Full)

def recover_lcg_full(outputs, modulus):
    """Recover LCG parameters a, b from full consecutive outputs.
    LCG: x_{n+1} = a * x_n + b (mod m)
    """
    # From three consecutive outputs x0, x1, x2:
    x0, x1, x2 = outputs[0], outputs[1], outputs[2]

    # x1 = a*x0 + b (mod m)
    # x2 = a*x1 + b (mod m)
    # x2 - x1 = a*(x1 - x0) (mod m)

    a = ((x2 - x1) * pow(x1 - x0, -1, modulus)) % modulus
    b = (x1 - a * x0) % modulus
    return a, b

4.2 Truncated Outputs (Lattice-Based)

When only upper bits of each output are known:

# SageMath
def recover_lcg_truncated(known_upper_bits, modulus, a, b, unknown_bits):
    """
    Recover full LCG state from truncated outputs.
    Uses CVP on a lattice.
    """
    n = len(known_upper_bits)
    B = 2^unknown_bits  # bound on unknown part

    # Build lattice
    M = matrix(ZZ, n+1, n+1)
    for i in range(n):
        M[i, i] = modulus
    # Last row encodes the recurrence
    for i in range(n):
        M[n, i] = (a^i) % modulus
    M[n, n] = B

    # LLL reduction
    L = M.LLL()
    # Extract short vector → recover unknown bits

---

5. MERSENNE TWISTER STATE RECOVERY

def untemper(y):
    """Reverse MT19937 tempering to recover internal state."""
    # Undo: y ^= y >> 18
    y ^= y >> 18

    # Undo: y ^= (y << 15) & 0xEFC60000
    y ^= (y << 15) & 0xEFC60000

    # Undo: y ^= (y << 7) & 0x9D2C5680 (need multiple steps)
    y ^= (y <<  7) & 0x9D2C5680
    y ^= (y << 14) & 0x9D2C5680
    y ^= (y << 21) & 0x9D2C5680
    y ^= (y << 28) & 0x9D2C5680

    # Undo: y ^= y >> 11 (need two steps)
    y ^= (y >> 11)
    y ^= (y >> 22)

    return y & 0xFFFFFFFF

def clone_mt(outputs_624):
    """Clone MT19937 state from 624 consecutive outputs."""
    assert len(outputs_624) == 624
    state = [untemper(o) for o in outputs_624]
    # Now state[] is the internal state array
    # Can predict all future outputs
    return state

---

6. AES KEY SCHEDULE WEAKNESS EXPLOITATION

6.1 Related-Key Attack Setup

from Crypto.Cipher import AES

def related_key_test(key1, key2, plaintext):
    """Demonstrate related-key distinguisher."""
    c1 = AES.new(key1, AES.MODE_ECB).encrypt(plaintext)
    c2 = AES.new(key2, AES.MODE_ECB).encrypt(plaintext)

    # In AES-256, related keys with specific XOR differences
    # can produce predictable ciphertext relationships
    return c1, c2

---

7. GCM NONCE REUSE

7.1 Authentication Key Recovery

When AES-GCM nonce is reused with two different messages:

Given: (C1, T1, AAD1) and (C2, T2, AAD2) under same (K, nonce)

The authentication tags are:
  T1 = GHASH_H(AAD1, C1) ⊕ E_K(nonce||1)
  T2 = GHASH_H(AAD2, C2) ⊕ E_K(nonce||1)

Therefore:
  T1 ⊕ T2 = GHASH_H(AAD1, C1) ⊕ GHASH_H(AAD2, C2)

GHASH is polynomial evaluation over GF(2^128):
  GHASH_H(A, C) = A_n * H^(n+1) + ... + C_m * H^2 + len_block * H

T1 ⊕ T2 gives a polynomial equation in H (the auth key).
Factor the polynomial over GF(2^128) to find H.
With H known: forge tags for arbitrary messages.

# SageMath
def gcm_nonce_reuse_recover_H(aad1, c1, t1, aad2, c2, t2):
    """Recover GHASH authentication key H from nonce reuse."""
    F.<a> = GF(2^128, modulus=x^128 + x^7 + x^2 + x + 1)

    def bytes_to_gf(b):
        return F(Integer(int.from_bytes(b, 'big')).bits())

    # Build GHASH polynomials and find roots of their difference
    # ... (polynomial construction in GF(2^128))
    # Factor to find H

---

8. PRACTICAL TIPS