A Different MITM - PicoCTF 2021 Double DES Writeup

  • Posted: April 7, 2021
  • Updated: July 8, 2023

Note: This post was originally going to go up on the 30th of March but PicoCTF requested writeups to be held on to until winners were verified.

As stated in my last post, a group of friends and I participated in the 2021 PicoCTF challenge. Having just come to an end, this year’s contest was certainly the most enjoyable one for me because of the truly awesome people I got to work with, leading us to a second place finish in Canada (7th globally). One of the most interesting, though not particularly challenging, cryptography problems I came across and solved was titled “Double DES.” It began with this description and hint:

I wanted an encryption service that’s more secure than regular DES, but not as slow as 3DES… The flag is not in standard format.

Hint: How large is the keyspace?

It contained the following Python code (modified to be shorter) which was also running on a remote server:

#!/usr/bin/python3 -u
from Crypto.Cipher import DES
import binascii, itertools, random, string

def pad(msg):
    block_len = 8
    over = len(msg) % block_len
    pad = block_len - over
    return (msg + " " * pad).encode()

def generate_key():
    return pad("".join(random.choice(string.digits) for _ in range(6)))

FLAG = open("flag").read().rstrip()
KEY1 = generate_key()
KEY2 = generate_key()

def get_input():
    return binascii.unhexlify(input("What data would you like to encrypt? ").rstrip()).decode()

def double_encrypt(m):
    msg = pad(m)

    cipher1 = DES.new(KEY1, DES.MODE_ECB)
    enc_msg = cipher1.encrypt(msg)
    cipher2 = DES.new(KEY2, DES.MODE_ECB)
    return binascii.hexlify(cipher2.encrypt(enc_msg)).decode()

print("Here is the flag:")
print(double_encrypt(FLAG))

while True:
    try:
        print(double_encrypt(get_input()))
    except:
        print("Invalid input.")

A quick look at the code makes it clear that two random keys made up of 6 digits each are generated and then used to encrypt the flag with DES which is provided to the user. From there, the user can input any plaintext and get the ciphertext using the same keys. This last part is important because it means the challenge is open to “known-plaintext attacks.”

A naive examination of the encryption would suggest that one could bruteforce the correct key out of the 1012 possible made up from every possible first key (106) for every possible second key (106). However, while certainly possible to do in the timespan of the competition, there exists a significantly better attack called Meet-in-the-Middle (MITM). To perform such an attack, we first choose a known plaintext, say “0123456789012345678”, and encrypt it with every possible first key:

def single_encrypt(k, m):
    msg = pad(m)
    cipher1 = DES.new(k, DES.MODE_ECB)
    return cipher1.encrypt(msg)

# The 'singles' file is a good save point since this first
# generation step can take a bit.
with open("singles", "w") as f:
    for i in range(1000000):
        ciphertext = single_encrypt(pad(str(i).zfill(6)), binascii.unhexlify('0123456701234567').decode())
        f.write(f"{i}: {ciphertext}\n")

Then, we can connect to the remote and receive the flag ciphertext (PASS) and our known plaintext ciphertext (GIVEN):

PASS = b"\x00\xbb\x8e\x0a\x5f\x56\x63\x21\xd3\x0f\xe2\x2f\xbc\xdd\xe0\x2d\x96\x71\x44\x82\x35\x72\x65\x67\xe2\x0a\x16\x2f\x25\x81\x24\x40\x13\x0f\x14\x8b\x12\x91\x01\x5a"
GIVEN = b"\xe0\xdd\xb8\x90\x74\xc3\x64\x8a\x13\x0f\x14\x8b\x12\x91\x01\x5a"

Finally, we can take the GIVEN ciphertext and decrypt it with every possible second key and check if it matches any of our single encrypted plaintexts. If it does, we’ve just found the correct first and second keys which we can use to decrypt the encrypted flag; wrap it with picoCTF{} and submit! So there you have it, an attack that only takes 2 × 106 (2N) tries instead of the naive 1012 (N2) attack and a reason not use Double DES.1 Full source code for my solution is provided below:

#!/usr/bin/python3 -u
from Crypto.Cipher import DES
import binascii


def pad(msg):
    block_len = 8
    over = len(msg) % block_len
    pad = block_len - over
    return (msg + " " * pad).encode()

def single_encrypt(k, m):
    msg = pad(m)
    cipher1 = DES.new(k, DES.MODE_ECB)
    return cipher1.encrypt(msg)

def single_decrypt(k, enc_msg):
    cipher1 = DES.new(k, DES.MODE_ECB)
    return cipher1.decrypt(enc_msg)


# Generates single encrypted versions of known plaintext
# The 'singles' file is a good save point since this first
# generation step takes a bit.
with open("singles", "w") as f:
    for i in range(1000000):
        if i % 10000 == 0:
            print(pad(str(i).zfill(6)))
        f.write(f"{i}: {single_encrypt(pad(str(i).zfill(6)), binascii.unhexlify('0123456701234567').decode())}\n")

KEYS = {}
with open("singles", "r") as f:
    lines = f.read().splitlines()
    for line in lines:
        key, enc = line.split(": ", 1)
        exec(f"enc={enc}")
        KEYS[enc] = pad(key)

# From challenge
PASS = b"\x00\xbb\x8e\x0a\x5f\x56\x63\x21\xd3\x0f\xe2\x2f\xbc\xdd\xe0\x2d\x96\x71\x44\x82\x35\x72\x65\x67\xe2\x0a\x16\x2f\x25\x81\x24\x40\x13\x0f\x14\x8b\x12\x91\x01\x5a"

# Encrypted known plaintext
PAIRS = []
GIVEN = b"\xe0\xdd\xb8\x90\x74\xc3\x64\x8a\x13\x0f\x14\x8b\x12\x91\x01\x5a"
for i in range(1000000):
    d = single_decrypt(pad(str(i).zfill(6)), GIVEN)
    if d in KEYS:
        PAIRS.append((KEYS[d], pad(str(i).zfill(6))))

# You will get many correct pairs, in this case all of them worked
for a, b in PAIRS:
    print(single_decrypt(a, single_decrypt(b, PASS)))

More writeups of other challenges coming soon.

  1. Not that you should use DES at all, nowadays. ↩︎