Double DES picoCTF 2021 Solution

Description

1. Step 1

   Double DES and meet-in-the-middle

   Observation

   I noticed the challenge name specifies 'Double DES' and offers a plaintext-ciphertext oracle, which are the exact conditions that make the meet-in-the-middle attack applicable and reduce the effective keyspace from 2^112 to 2^57.

   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: Each DES key is a 6-digit ASCII decimal string padded to 8 bytes with two trailing spaces (e.g., '123456 '), giving a keyspace of 10^6 per key rather than 2^56. This makes 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 2

   Collect two PT/CT pairs from the oracle

   Observation

   I noticed the service provides an encryption oracle, and that a single plaintext-ciphertext pair produces false positive key candidates during MITM; collecting two distinct pairs and verifying both eliminates those collisions before running the decryption.

   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!

   What didn't work first

   Tried: Sending raw bytes or a fixed string like 'test' as plaintext instead of a hex-encoded 8-byte block

   The oracle expects exactly 8 bytes of plaintext (one DES block). Sending a string like 'test' gives 4 bytes, which triggers a block-size error or garbled output from the server. You must send exactly 8 bytes, often hex-encoded depending on the server's framing, then decode the response to bytes before passing it to pycryptodome.

   Tried: Collecting only one plaintext-ciphertext pair and treating the first MITM match as the confirmed key

   With a 10^6 keyspace and 64-bit intermediate values, false positives are unlikely but not impossible. Collecting a second pair and verifying both eliminates any ambiguity. Without verification, a false-positive key pair will produce garbage when you attempt to decrypt the flag ciphertext, sending you chasing a decryption bug that does not exist.

   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 3

   Execute the meet-in-the-middle attack

   Observation

   I noticed the challenge reduces each DES key to a 6-digit decimal string, shrinking the keyspace to 10^6 per half, which makes building a full forward lookup table with pycryptodome DES feasible in memory and time for a CTF environment.

   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
   
   # 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')
   
   # Keys are 6-digit ASCII decimal strings padded to 8 bytes with spaces
   def make_key(k_int):
       return f'{k_int:06d}  '.encode()  # 6 digits + 2 trailing spaces = 8 bytes
   
   # Stage 1: encrypt P1 with every k1, record intermediate -> k1_int
   forward = {}
   for k1_int in range(10 ** 6):  # keyspace is 10^6, not 2^24
       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(10 ** 6):
       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!

   Expected output

   k1=XXXXX, k2=YYYYY
   Flag: picoCTF{cb120914...}

   What didn't work first

   Tried: Decrypting the flag as DES_k1^-1(DES_k2^-1(ciphertext)) - applying k1 first in the decryption order

   Encryption is C = DES_k2(DES_k1(P)), so decryption must reverse that order: P = DES_k1^-1(DES_k2^-1(C)). Applying k1 first during decryption mirrors the encryption order instead of reversing it and produces garbled output. The outer key in encryption (k2) must be the outer key in decryption as well.

   Tried: Building the forward table by encrypting P1 under every k2 instead of k1, then decrypting C1 under every k1

   The table direction is arbitrary as long as it is consistent - you can build forward from P under k1 or forward from C under k2 - but mixing the directions (table built with k2, probe with k2) causes every probe to match the table, giving 10^6 false positives instead of isolating the real key pair. Pick one direction and apply the opposite in the probe phase.

   Learn more

   This MITM implementation has time complexity O(K) and space complexity O(K) for a keyspace of size K. For the 10^6 keyspace in this challenge, the forward table uses roughly 8 MB of memory (1M entries x 8 bytes each), which completes quickly. 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.