DESBox

Full solution below. Spoilers ahead.

Task description

I tried to install a famous MS-DOS emulator, but ended up installing this program.

I don’t think this can run DOOM…

The handout was DESBox.py and a redacted secret.py holding a FLAG and a 24-byte MASK, and the service ran over TLS on a TCP port.

The service

DESBox.py is a DOSBox-themed shell with DIR, TYPE, KEYB, DOOM and EXIT. TYPE FLAG.BIN answers Access denied., so the only cryptographic surface is KEYB, the “keyboard layout loader”:

1. I submit two 24-byte 3DES keys, Key A and Key B, as hex.
2. The server prints FLAG.BIN encrypted under Key A (3DES in ECB mode).
3. The server then decrypts one ciphertext of my choice under Key B and prints the result as “Debug output”.

So KEYB is an encryption oracle under one key I influence and a decryption oracle under another. main also asserts len(FLAG) % 8 == 0, and DIR lists FLAG.BIN as 48 bytes, so the flag is exactly six DES blocks.

The key loader is the interesting part:

def permute(a):
    p = list(range(len(a)))
    RNG.shuffle(p)                       # fresh random byte permutation per call
    return bytes(a[i] for i in p)

def load_key(user_key):
    key = xor(permute(user_key), MASK)   # shuffle, then xor the secret MASK
    return DES3.adjust_key_parity(key)

permute reshuffles the 24 bytes on every call with a cryptographic RNG, and MASK is a fixed secret XORed into both keys. read_keys rejects the obvious ways to make the two keys related, using effective_bytes (b & 0xFE, which drops the low bit of each byte):

if key_a == key_b:                                        # identical keys
    exit()
if effective_bytes(key_a) == effective_bytes(key_b):      # same effective key, in order
    exit()
if sorted(effective_bytes(key_a)) == sorted(effective_bytes(key_b)):   # same multiset
    exit()
if is_effective_complement(key_a, key_b):                 # a is the ordered complement of b
    exit()

The author wanted to block the two shortcuts: identical keys, where decrypt_B(CT_A) is the flag directly, and exact complements.

The complementation property

DES has a published symmetry: DES_{~k}(~m) = ~DES_k(m), where ~ is the bitwise complement of every bit. It falls straight out of the algorithm. The round function XORs the subkey into the expanded right half before the S-boxes, and complementing both the key and the data leaves that XOR unchanged, so every S-box sees the same input and the only thing that propagates is the complement of the left/right halves.

3DES as used here is EDE: 3DES_k = E_{K1} D_{K2} E_{K3} over the three 8-byte thirds of the key. Complement all 24 key bytes and all three single-DES stages complement in lockstep, so the property carries over to the triple. One more detail matters: DES reads only 7 of the 8 bits in each key byte (the 8th is a parity bit it ignores), which is exactly what effective_bytes isolates with & 0xFE. Complementing a byte flips all 8 bits, including the 7 that count, so an “effective complement” is a real DES key complement.

I checked both halves of the claim against the library the service uses (pycryptodome DES3), over 2000 random keys and messages:

3DES_~k(~m) == ~3DES_k(m)        : 2000 / 2000
~D_~k( ~E_k(m) ) == m            : 2000 / 2000
flipping only parity bits changes the ciphertext? : False

The second line is the one I need. If the loaded Key B is the effective complement of the loaded Key A, then for CT_A = 3DES_A(FLAG):

decrypt_B(~CT_A) = ~FLAG

So I feed the complement of the flag ciphertext into the debug decryption and complement the output.

Getting past the checks

The checks look at my keys before loading, but the relation I need is between the loaded keys. Since the same MASK is XORed into both, and complement distributes over XOR:

loaded_B = ~loaded_A   <=>   perm_b(user_b) ^ MASK = ~(perm_a(user_a) ^ MASK)
                       <=>   perm_b(user_b) = ~perm_a(user_a)

MASK drops out entirely. What is left is a condition on the two independent random permutations: perm_b(user_b) has to equal the complement of perm_a(user_a). That depends only on the byte multisets of the two keys, never on the order I type them. The checks, on the other hand, only compare the user keys as given. So I pick keys that are complements as multisets but differ in order:

X, Y = 0x00, 0x02
user_a = bytes([Y]) + bytes([X]) * 23                              # 02 00 00 ... 00
user_b = bytes([X ^ 0xFF, Y ^ 0xFF]) + bytes([X ^ 0xFF]) * 22      # ff fd ff ... ff

Written out, that is:

KEY A = 020000000000000000000000000000000000000000000000
KEY B = fffdffffffffffffffffffffffffffffffffffffffffffff

Replaying the four guards on this pair confirms all of them pass while the complement relation stays reachable:

key_a == key_b                 -> False
effective(a) == effective(b)   -> False
sorted multisets equal         -> False
is_effective_complement(a, b)  -> False
multiset(B) == multiset(~A)    -> True        # the relation we need is achievable

user_b carries the multiset of ~user_a, so once the two shuffles line up the loaded keys are complements. The multisets of user_a and user_b differ (00s against ffs), so the sorted-multiset guard passes. And the odd byte sits at index 0 in A but the odd fd sits at index 1 in B, so the ordered equality and ordered complement guards both miss.

Using 23 identical bytes and one odd byte is what makes this tractable. After a shuffle the only thing that can vary is where the single odd byte lands, so the two loaded keys are effective complements exactly when both shuffles drop their odd byte into the same slot. That has probability 1/24 per KEYB round, instead of the 1/24! it would be for 24 distinct bytes. A fully constant key would make the permutation irrelevant, but then user_b would have to be the exact ordered complement of user_a, which the last guard rejects.

rounds           : 4000
loaded keys were effective complements : 184
stand-in flag recovered                : 184
rate             : 1 in 21.7

Solve

A round sends KEYB, submits both keys, reads CT_A, sends the complemented CT_A as the debug ciphertext, reads the output and complements it. A misaligned round returns garbage and a lucky one returns the flag, so I loop until the output starts with FortID{:

def one_keyb_round(t):
    t.read_until(b"C:\\> ");             t.sendline(b"KEYB")
    t.read_until(b"KEY A> ");            t.sendline(USER_A.encode())   # 02 00..00
    t.read_until(b"KEY B> ");            t.sendline(USER_B.encode())   # ff fd ff..ff
    ct_a = read_hex_line(t)                                            # 3DES_A(FLAG)
    t.read_until(b"Debug ciphertext> "); t.sendline(comp(ct_a).hex().encode())
    out = read_hex_line(t)                                             # decrypt_B(~CT_A)
    return comp(out)                                                   # FLAG when the shuffles align

The service had no solver in the handout, so I wrote this against DESBox.py directly. On the live run the first aligned round returned the flag. Its text, “compliments on exploiting complements”, confirms the intended path.

Takeaways

The guards inspected the raw user keys, while the complement relation lived in the post-permutation keys, so they protected a value that was no longer the one being used. The secret shuffle meant to defend the keys is exactly what let this pair through. Allowing a 23-plus-1 byte structure cut the permutation space from 24! down to 24, and a decryption oracle under an attacker-influenced key is what made the relation usable at all. A real system should never decrypt arbitrary attacker ciphertext under a key tied to a secret.