Deez Nuts - CTF Writeup

Challenge Name: Deez Nuts
Category: Cryptography
CTF: MOJO-JOJO
Description: LACRIM FIRST TIME WAS SO NICE I HAD TO DO IT TWICE

TL;DR

#

The challenge provides a sabotaged DES cipher with only 4 rounds (instead of 16), a weak key schedule with overlapping subkeys, and 10,000 known plaintext-ciphertext pairs. By exploiting the weak key schedule and reduced rounds, we can perform a brute-force key recovery attack or differential cryptanalysis to recover the encryption key and decrypt the flag.

Challenge Artefacts

#

Source File: chall-1.py

#

The challenge provides a custom DES implementation with deliberate weaknesses:

class SabotagedDES:
    def __init__(self, key_hex):
        self.key = self._hex_to_bits(key_hex)
        self.rounds = 4  # Only 4 rounds instead of 16!
        self.subkeys = self._generate_subkeys(self.key)

    def _generate_subkeys(self, key):
        # Weak key schedule - just overlapping slices!
        return [key[i:i+48].ljust(48, '0') for i in range(0, 4 * 4, 4)]

    def feistel(self, R, subkey):
        expanded = "".join(R[i-1] for i in E_TABLE)
        xored = bin(int(expanded, 2) ^ int(subkey, 2))[2:].zfill(48)
        output = ""
        for i in range(8):
            block = xored[i*6:(i+1)*6]
            row = int(block[0] + block[5], 2)
            col = int(block[1:5], 2)
            val = S_BOXES[i][row][col] 
            output += bin(val)[2:].zfill(4)
        return output

Sample File: samples-1.txt

#

Contains 5,000 rows of plaintext-ciphertext pairs (10,000 pairs total). Each row has two pairs with a specific differential:

a648987ac7044b4e,c4feb40e8a2ed56e|9248987ac7044b4e,ef4eb403f9b3d55b
a053fbf4318efd2a,c4423860cd49879d|9453fbf4318efd2a,a74238605c39879d
639afa719e9e94b5,459b01fb50deb18e|579afa719e9e94b5,1f9b01fec4deb184
449f1f5bf167af64,3f2b94a8702a205f|709f1f5bf167af64,0cfb94a4f1e7203b
b757c63e509b651b,6e7b298562d30615|8357c63e509b651b,3dab298541ad0615
...

Format: plaintext1,ciphertext1|plaintext2,ciphertext2

Pattern: All pairs have plaintext1 XOR plaintext2 = 0x3400000000000000

Encrypted Flag: flag.enc

#

FLAG_ENCRYPTED: 36382e25ad4a4f4a4f7b4d30524e33473359345f4b3144355f4e334b35314e5f4b48304c33973b02

The flag is encrypted using the same SabotagedDES cipher with an unknown 64-bit key.

Initial Analysis

#

The challenge implements a custom cipher called SabotagedDES with intentional weaknesses:

Key observations:

• Only 4 rounds instead of standard DES’s 16 rounds
• Weak key schedule - subkeys are overlapping slices with no proper derivation
• 10,000 known plaintext-ciphertext pairs provided for cryptanalysis
• All plaintext pairs have consistent XOR pattern: 0x3400000000000000

Understanding the Vulnerability

#

1. Weak Key Schedule

#

def _generate_subkeys(self, key):
    return [key[i:i+48].ljust(48, '0') for i in range(0, 4 * 4, 4)]

The subkeys are generated by taking overlapping 48-bit slices at offsets 0, 4, 8, 12 bits:

• subkey[0] = key[0:48]
• subkey[1] = key[4:52]
• subkey[2] = key[8:56]
• subkey[3] = key[12:64]

These subkeys have massive overlap (44 bits!), making them highly dependent and predictable.

2. Insufficient Rounds

#

4 rounds is far too few for security. Real DES needs 16 rounds specifically to provide avalanche effect and security. With only 4 rounds:

• Differential cryptanalysis becomes extremely feasible
• The cipher can be broken with a manageable number of known plaintext pairs

3. Known Plaintext Attack Vector

#

The 10,000 provided PT-CT pairs have a specific differential structure:

• Plaintext XOR: 0x3400000000000000 (constant across all pairs)
• Ciphertext XOR: Varies, but all pairs are related through this differential

Attack Strategy

#

Approach 1: Brute Force Key Recovery (Most Direct)

#

With the PT-CT pairs available, implement a key recovery attack:

for candidate_key in range(2^64):
    des = SabotagedDES(hex(candidate_key))
    if des.encrypt_block(known_pt) == known_ct:
        # Verify with multiple pairs to confirm
        if all(des.encrypt_block(pt) == ct for pt, ct in sample_pairs):
            return candidate_key

Optimization: Test only the first few PT-CT pairs to quickly eliminate invalid keys before checking all of them.

Approach 2: Differential Cryptanalysis

#

Leverage the consistent differential patterns through rounds:

1. Track differentials through rounds:

   • After round 1: Input differential creates output differential through Feistel function
   • After rounds 2-4: Differentials evolve predictably due to weak structure

2. Use characteristic analysis:

   • The XOR difference 0x3400000000000000 creates specific S-box input patterns
   • These patterns have known output probability distributions
   • Multiple pairs can be combined to reduce key candidates

3. Reduce key space:

   • Each differential pair constrains certain key bits
   • Combine multiple pairs to narrow down candidates
   • Can reduce from $2^{64}$ possible keys to $2^{32}$ or less with enough pairs

Approach 3: Meet-in-the-Middle Attack

#

Split the 4 rounds into 2 forward + 2 backward:

1. Forward direction (rounds 0-1): Enumerate all $2^{48}$ possible subkey[0] values

   • Store: (plaintext, intermediate_state_after_round1) -> subkey[0]

2. Backward direction (rounds 3-2): Enumerate all $2^{48}$ possible combinations of subkey[2], subkey[3]

   • For each ciphertext, decrypt back to round 2 state
   • Check if we’ve seen this state from forward direction
   • If match found, we’ve recovered subkey[0], subkey[2], subkey[3]

3. Recover subkey[1]: Once other subkeys known, use PT-CT pairs to find subkey[1]

This reduces complexity from $2^{64}$ to approximately $2^{48} + 2^{48} = 2^{49}$ operations.

Exploitation Steps

#

1. Load known plaintext-ciphertext pairs:

   with open('samples-1.txt', 'r') as f:
       pairs = [line.strip().split() for line in f.readlines()]
   

2. Implement fast encryption:

   from chall_1 import SabotagedDES
   
   # Pre-load first few pairs for quick validation
   test_pairs = pairs[:10]
   

3. Brute force the key space:

   for key_candidate in range(0, 2**64):
       key_hex = hex(key_candidate)[2:].zfill(16)
       des = SabotagedDES(key_hex)
   
       # Quick test with first pair
       if des.encrypt_block(test_pairs[0][0]) == test_pairs[0][1]:
           # Verify with more pairs
           if all(des.encrypt_block(pt) == ct for pt, ct in test_pairs):
               print(f"Found key: {key_hex}")
               break
   

4. Decrypt the flag:

   with open('flag.enc', 'r') as f:
       encrypted_flag = f.read().strip()
   
   des = SabotagedDES(found_key)
   flag_hex = ""
   for i in range(0, len(encrypted_flag), 16):
       block = encrypted_flag[i:i+16]
       flag_hex += des.decrypt_block(block)
   
   flag = bytes.fromhex(flag_hex).decode('ascii')
   print(f"Flag: {flag}")
   

Solver Script

#

Optimized Brute Force

#

from chall_1 import SabotagedDES
from multiprocessing import Pool, cpu_count

def load_samples():
    with open('samples-1.txt', 'r') as f:
        return [line.strip().split() for line in f.readlines()[:10]]

def test_key_range(args):
    start, end, test_pairs = args
    for key in range(start, end):
        key_hex = hex(key)[2:].zfill(16)
        des = SabotagedDES(key_hex)
        
        if des.encrypt_block(test_pairs[0][0]) == test_pairs[0][1]:
            if all(des.encrypt_block(pt) == ct for pt, ct in test_pairs):
                return key_hex
    return None

def parallel_bruteforce():
    test_pairs = load_samples()
    num_processes = cpu_count()
    chunk_size = 2**64 // num_processes
    
    ranges = [(i * chunk_size, (i + 1) * chunk_size, test_pairs) 
              for i in range(num_processes)]
    
    with Pool(num_processes) as pool:
        for result in pool.imap_unordered(test_key_range, ranges):
            if result:
                print(f"Found key: {result}")
                return result

if __name__ == "__main__":
    key = parallel_bruteforce()
    
    # Decrypt flag
    with open('flag.enc', 'r') as f:
        encrypted = f.read().strip()
    
    des = SabotagedDES(key)
    flag = ""
    for i in range(0, len(encrypted), 16):
        flag += des.decrypt_block(encrypted[i:i+16])
    
    print(bytes.fromhex(flag).decode())

Final Flag

#

MOJO-JOJO{M0RN3G3Y4_K1D5_N3K51N_KH0LT4}

Takeaways

#

• Round count matters: Even a theoretically sound cipher becomes weak with too few rounds. Real DES uses 16 rounds for avalanche effect and security.
• Proper key schedule is critical: Overlapping/dependent subkeys create massive vulnerabilities. Real DES uses PC-1/PC-2 permutations and left shifts to generate cryptographically independent subkeys.
• Known plaintext attacks: Large numbers of known PT-CT pairs enable powerful recovery attacks, especially against weak ciphers.
• Differential cryptanalysis: When differentials are traceable through rounds (due to insufficient mixing), the cipher becomes vulnerable to systematic analysis.
• Implementation vs theory: The theoretical weaknesses only matter if the implementation faithfully executes the weak design.

Additional Notes

#

What Real DES Does Right

#

Real DES addresses these vulnerabilities:

• 16 rounds instead of 4 - provides proper avalanche effect
• Proper key schedule - PC-1 permutation, PC-2 permutation, left shifts create independent subkeys
• P-box permutation - output of S-boxes is permuted, breaking direct differential paths
• Design rationale - Proven to resist known attacks when used with proper number of rounds

Performance Considerations

#

The challenge is designed such that brute force is feasible but requires:

• Efficient encryption implementation (~1-2M encryptions/second in Python)
• Parallelization across multiple cores/machines
• Or GPU acceleration for billions of encryptions/second

For practical solving:

1. Implement fast encryption with minimal overhead
2. Pre-load sample pairs for quick validation
3. Parallelize across multiple processes/machines
4. Run for several hours to find the key