Double DES picoCTF 2021 Solution

Description

1. Step 1Double DES and meet-in-the-middle
   Double DES encrypts a message twice with two independent 56-bit DES keys: C = DES_k2(DES_k1(P)). Naively this has 2^112 security, but the meet-in-the-middle attack reduces it to ~2^57.
   Learn more

   Meet-in-the-middle (MITM) attack: Given a plaintext-ciphertext pair (P, C):

   1. For every possible key k1 (2^56 keys): compute DES_k1(P) and store it in a hash table mapping value to k1.
   2. For every possible key k2 (2^56 keys): compute DES_k2^-1(C) (decrypt C with k2) and look it up in the hash table.
   3. When a match is found: DES_k1(P) == DES_k2^-1(C) means C = DES_k2(DES_k1(P)), so (k1, k2) is a candidate key pair.

   The total work is 2 × 2^56 = 2^57, not 2^112. This is why Double DES provides negligible security improvement over single DES and is not used in practice. Triple DES (3DES) was developed to avoid this attack.

   In this challenge: DES keys are likely reduced to fewer bits (e.g., 24 bits each) to make the challenge tractable within a CTF timeframe. The same MITM attack applies, just with a smaller keyspace.

   DES parity, briefly. A real DES key is 56 bits packed into 8 bytes - the LSB of each byte is a parity bit that the key schedule discards. If the challenge expects a parity-correct 8-byte key (pycryptodome enforces this), build the key by setting the top 7 bits of each byte from your 56-bit candidate and computing the LSB so the byte has odd parity. If the challenge skips parity entirely (common in CTFs with reduced key sizes), pad your candidate to 8 bytes and pycryptodome won't complain.

2. Step 2Collect two PT/CT pairs from the oracle
   Connect to the service and ask it to encrypt two distinct known plaintexts. Record (P1, C1) and (P2, C2). The MITM scan uses pair 1 to enumerate candidates and pair 2 to verify them.
   python

   python3 - <<'EOF'
   from pwn import *
   
   p = remote('mercury.picoctf.net', <PORT_FROM_INSTANCE>)
   p.recvuntil(b'')
   
   # Two distinct known plaintexts
   P1 = b'0' * 16   # 16 hex chars = 8 bytes
   P2 = b'1' * 16
   
   p.sendline(P1); C1 = p.recvline().strip()
   p.sendline(P2); C2 = p.recvline().strip()
   print('pair1:', P1, C1)
   print('pair2:', P2, C2)
   
   # Get the encrypted flag too
   p.sendline(b'get_flag_or_similar_command')
   flag_ciphertext = p.recvline()
   print('flag ct:', flag_ciphertext)
   EOF

   Copied!
   Learn more

   The service provides an encryption oracle: you send plaintext bytes and receive the Double-DES ciphertext. With one pair, the meet-in-the-middle scan returns false positives - multiple (k1, k2) candidates whose intermediate value collides for that specific P. With two pairs, you can eliminate them: the real key pair is the only one that satisfies both C1 = E_k2(E_k1(P1)) and C2 = E_k2(E_k1(P2)). The expected number of false positives drops from ~2^N / 2^64 to nearly zero.

3. Step 3Execute the meet-in-the-middle attack
   Implement MITM in Python using the pycryptodome DES implementation. Build the forward table from encrypting P with all possible k1 values, then for each k2 decrypt C and check for matches.
   python

   python3 - <<'EOF'
   from Crypto.Cipher import DES
   import struct
   
   # Two known pairs from the oracle (eliminates false positives)
   P1 = bytes.fromhex('PASTE_P1_HEX')
   C1 = bytes.fromhex('PASTE_C1_HEX')
   P2 = bytes.fromhex('PASTE_P2_HEX')
   C2 = bytes.fromhex('PASTE_C2_HEX')
   encrypted_flag = bytes.fromhex('PASTE_FLAG_CIPHERTEXT_HERE')
   
   # Reduced keyspace: assume 24-bit keys (adjust based on challenge)
   KEY_BITS = 24
   
   def make_key(k_int):
       return struct.pack('>Q', k_int)[:8].ljust(8, b'\x00')
   
   # Stage 1: encrypt P1 with every k1, record intermediate -> k1_int
   forward = {}
   for k1_int in range(2 ** KEY_BITS):
       k1 = make_key(k1_int)
       mid = DES.new(k1, DES.MODE_ECB).encrypt(P1)
       forward[mid] = k1_int
   
   # Stage 2: decrypt C1 with every k2, check membership, then verify on (P2, C2)
   for k2_int in range(2 ** KEY_BITS):
       k2 = make_key(k2_int)
       mid = DES.new(k2, DES.MODE_ECB).decrypt(C1)
       if mid not in forward:
           continue
       k1_int = forward[mid]
       k1 = make_key(k1_int)
       # Verify the candidate against the second pair to drop false positives
       if DES.new(k2, DES.MODE_ECB).encrypt(DES.new(k1, DES.MODE_ECB).encrypt(P2)) != C2:
           continue
       # Real key pair: decrypt the flag
       flag = DES.new(k1, DES.MODE_ECB).decrypt(
                DES.new(k2, DES.MODE_ECB).decrypt(encrypted_flag)
              )
       print(f"k1={k1_int}, k2={k2_int}")
       print(f"Flag: {flag}")
       break
   EOF

   Copied!
   Learn more

   This MITM implementation has time complexity O(2^N) and space complexity O(2^N) for an N-bit key. For N=24 (16 million keys), the forward table uses about 128 MB of memory (16M entries × 8 bytes each). For larger key sizes, use a sorted list approach (requires less memory but needs sorting) or a disk-based hash table.

   The pycryptodome library provides a pure-Python DES implementation. Install with pip install pycryptodome. Note: DES keys are 8 bytes, but the actual key is 56 bits (7 bytes); the 8th byte of each 7-bit group is a parity bit. The challenge may use simplified DES without parity, so adjust key packing accordingly. For more on block-cipher attack patterns and AES-shaped CTF problems (the same MITM ideas extend), see AES for CTF.

Flag

Double DES is broken by the meet-in-the-middle attack, which reduces effective security from 2^112 to 2^57 - build a forward lookup table for all possible first-half keys, then scan for matches in the backward direction.