Writeup - UMDCTF 2024: TripleDES
A crypto challenge by clam, solved by Trayshar and Euph0r14
Challenge
Before the Kwisatz Haderach, the Bene Gesserit used this oracle to predict the future.
We get a remote server to connect to, and it sends us the encrypted flag. The encryption used is a variation of TripleDES, with three nested DES encryptions with different keys each, in CBC-Mode. This is unusual, since Triple DES typically uses encryption-decryption-encryption (e-d-e). But using e-e-e doesn’t introduce any weakness into the cipher, e-d-e is only done for backwards compatibility. While Triple DES is no longer recommended, it still offers 112 bits of effective security, making a bruteforce attack impossible for us. Also, typical attacks require some known plaintext / ciphertext pairs, which we don’t have.
In addition, while the flag and keys are static, the IVs are chosen anew each time we make a connection, resulting in different ciphertext. But we can send ciphertext to the server to verify that it can be successfully decrypted.
1#!/usr/local/bin/python
2from os import urandom
3from Crypto.Cipher import DES
4from Crypto.Util.Padding import pad, unpad
5
6key = bytes.fromhex(open("key.txt", "r").read())
7keys = [key[i:i+8] for i in range(0, len(key), 8)]
8flag = open("flag.txt", "rb").read()
9
10enc = pad(flag, 8)
11for i in range(3):
12 cipher = DES.new(keys[i], DES.MODE_CBC)
13 enc = cipher.iv + cipher.encrypt(enc)
14print("Here's the encrypted flag:", enc.hex())
15
16while 1:
17 print("Give us an encrypted text and we'll tell you if it's valid!")
18 enc = input()
19 try: enc = bytes.fromhex(enc)
20 except:
21 print("no")
22 break
23 if len(enc) % 8 != 0 or len(enc) < 32:
24 print("no")
25 break
26 try:
27 for i in range(3):
28 iv, enc = enc[:8], enc[8:]
29 cipher = DES.new(keys[2-i], DES.MODE_CBC, iv=iv)
30 enc = cipher.decrypt(enc)
31 dec = unpad(enc, 8)
32 print("yes")
33 except:
34 print("no")
Server-side Decryption
The Ciphertext we get has a block size of 8 bytes. The first three blocks are the Initialization Vectors of the outer ($IV_3$), middle ($IV_2$), inner ($IV_1$) CBC-Mode encryption. The first Initialization Vector is unencrypted, since it is needed to perform the outer decryption.
After the first three blocks, the blocks encode the actual, still encrypted flag.
So how can we crack this challenge?
To approach this problem, I made a sketch of the decryption operation the server performs, which has helped me to reason about possible attacks.
Padding Oracle with Extra Steps
TripleDES? More like TripleCBC!
As the endpoint returns whether the ciphertext can be successfully decrypted, which includes valid padding, a Padding Oracle Attack seemed like the way to go. This link does a better job at explaining it than I could, so go read it.
But how would this work for nested encryption?
For padding oracle attacks, the IV is varied to force a specific padding in the last block of plaintext, which the oracle then verifies for us. Using this information, we can extract the plaintext byte by byte, no matter the strength of the actual encryption. This works because the IV (or the preceding ciphertext block) is directly XORed with the final plaintext during block decryption, with the IV (or ciphertext) being public knowledge.
In the diagram we can see that the first block of plaintext is indeed XORed with $IV_3$.
Although it is XORed with $D_{K3}(IV_2)$ and $D_{K2}(IV'_1)$ as well, this is of no concern, as both these values only depend on $IV_2, IV_1$ (and the keys), which we can fix.
Thus we can use the unencrypted $IV_3$ for a padding oracle attack, by sending a crafted $IV_3$, followed by the real $IV_2,IV_1,C_1$.
This yields us $D_{K1}({C''}_1)\oplus D_{K2}({IV'}_1)\oplus D_{K3}({IV}_2)$.
By XORing that with the actual $IV_3$, we compute the first 8 bytes of the flag: UMDCTF{p
This works for the second block as well. As we can see, it does not depend on $IV_3$ at all, but $IV_2$ is XORed into it just as $IV_3$ was before.
Note that we do not need to decrypt $IV_2$, as it is the ciphertext that is XORed.
Hence we can send the real $IV_3$, a crafted $IV_2$, followed by the real $IV_1,C_1,C_2$, and do a padding oracle attack again as before.
It is important that we send both $C_1$ and $C_2$, as the correct decryption of $C_2$ depends on a correct $C''_1$.
This way we get the second block: UMDCTF{p adding_o
This works for all consecutive blocks, in fact. If we want to crack block $i$, we have to craft block $i-3$ using a Padding Oracle, and send all blocks up to block $i$ (so block $i$ is the last one).
And thus, we got the flag: b'UMDCTF{padding_oracle_with_extra_steps?}\x08\x08\x08\x08\x08\x08\x08\x08'
Implementation
I re-wrote the server code to work locally, so I can test and prototype with minimal latency. Also, it made debugging issues much easier.
The remote server was a bit of a hassle because it closed the connection after a fixed timespan, which interrupted the attack (typically after 1-2 blocks). I fixed this by closing and reopening the connection after each decrypted block, which gave me plenty of time to query the oracle.
1#!/usr/bin/env python3
2
3########################
4# tripledes.py
5########################
6
7# Change the import to switch between remote/local version
8from tripledes_remote import queryOracle, reconnect
9# from tripledes_local import queryOracle, reconnect
10
11def xor(a: bytes, b: bytes):
12 assert len(a) == len(b)
13 return bytes(a_byte ^ b_byte for a_byte, b_byte in zip(a, b))
14
15# Outputs bytes as hex, with a space inserted each ${length} bytes
16def bout(a: bytes, length=16):
17 string = a.hex()
18 return ' '.join(string[i:i+length] for i in range(0,len(string),length))
19
20# Copied from https://research.nccgroup.com/2021/02/17/cryptopals-exploiting-cbc-padding-oracles/
21BLOCK_SIZE = 8
22def single_block_attack(block, oracle):
23 """Returns the decryption of the given ciphertext block"""
24
25 # zeroing_iv starts out nulled. each iteration of the main loop will add
26 # one byte to it, working from right to left, until it is fully populated,
27 # at which point it contains the result of DEC(ct_block)
28 zeroing_iv = [0] * BLOCK_SIZE
29
30 for pad_val in range(1, BLOCK_SIZE+1):
31 padding_iv = [pad_val ^ b for b in zeroing_iv]
32
33 for candidate in range(256):
34 padding_iv[-pad_val] = candidate
35 iv = bytes(padding_iv)
36 if oracle(iv, block):
37 if pad_val == 1:
38 # make sure the padding really is of length 1 by changing
39 # the penultimate block and querying the oracle again
40 padding_iv[-2] ^= 1
41 iv = bytes(padding_iv)
42 if not oracle(iv, block):
43 continue # false positive; keep searching
44 break
45 else:
46 raise Exception("no valid padding byte found (is the oracle working correctly?)")
47 zeroing_iv[-pad_val] = candidate ^ pad_val
48 return zeroing_iv
49
50def printDebug(data: bytes):
51 iv3 = data[0:BLOCK_SIZE]
52 iv2_enc = data[BLOCK_SIZE:BLOCK_SIZE*2]
53 iv1_enc = data[BLOCK_SIZE*2:BLOCK_SIZE*3]
54 flg_enc = data[BLOCK_SIZE*3:]
55 print(f"IV3 dec: {bout(iv3)}")
56 print(f"IV2 enc: {bout(iv2_enc)}")
57 print(f"IV1 enc: {bout(iv1_enc)}")
58 print(f"Flag enc: {bout(flg_enc)}")
59 print("")
60
61def main():
62 flag = b'' # If the script crashed, copy the incomplete flag here to resume operation
63 # For each block (we know the flag has 6 blocks)
64 for i in range(len(flag)//8, 6):
65 # Reconnect after each block, so the connection doesn't time out while decrypting a block
66 data = reconnect()
67 # printDebug(data)
68 assert len(data) % 8 == 0
69 # Split data into 8 byte chunks
70 data = [data[i:i+BLOCK_SIZE] for i in range(0, len(data), BLOCK_SIZE)]
71
72 def oracle(delta: bytes, block_num: int):
73 msg = b""
74 # Add IVs, and ${block_num+1} blocks
75 for i in range(3 + block_num + 1):
76 # Replace ${block_num}'th block with the value we're guessing
77 msg += (delta if i == block_num else data[i])
78 return queryOracle(msg)
79
80 flag += xor(bytes(single_block_attack(i, oracle)), data[i])
81 print("\nCurrent Flag: " + str(flag))
82
83 print("\nComplete Flag: " + str(flag))
84 exit(0)
85
86
87if __name__ == '__main__':
88 main()
1#!/usr/bin/env python3
2
3########################
4# tripledes_local.py
5########################
6
7from os import urandom
8from Crypto.Cipher import DES
9from Crypto.Util.Padding import pad, unpad
10
11# Outputs bytes as hex, with a space inserted each ${length} bytes
12def bout(a: bytes, length=16):
13 string = a.hex()
14 return ' '.join(string[i:i+length] for i in range(0,len(string),length))
15
16# Generate a local flag for testing purposes
17key = urandom(8*3)
18# print(f"Keys: {bout(key)}")
19keys = [key[i:i+8] for i in range(0, len(key), 8)]
20flag = b"UMDCTF{I_LOVE_TRASH_SO_FUCKING_MUCH_I_WANNA_EAT_A_CAN}"
21enc = pad(flag, 8)
22for i in range(3):
23 # print(f"Flag at {i}: {bout(enc)}")
24 cipher = DES.new(keys[i], DES.MODE_CBC)
25 enc = cipher.iv + cipher.encrypt(enc)
26# print(f"Flag at {3}: {bout(enc)}")
27
28# Get local encypted flag
29def reconnect():
30 return enc
31
32# Query local padding oracle
33def queryOracle(data: bytes):
34 enc = data
35 ret = False
36 if len(enc) % 8 != 0 or len(enc) < 32:
37 raise ValueError(f"Expected len <32 , got {len(enc)}")
38 try:
39 for i in range(3):
40 iv, enc = enc[:8], enc[8:]
41 cipher = DES.new(keys[2-i], DES.MODE_CBC, iv=iv)
42 enc = cipher.decrypt(enc)
43 dec = unpad(enc, 8)
44 ret = True
45 except:
46 pass
47 print(f"Query(b\"{bout(data)}\"): {ret}", end='\r')
48 return ret
1#!/usr/bin/env python3
2
3########################
4# tripledes_remote.py
5########################
6
7from pwn import *
8
9# Outputs bytes as hex, with a space inserted each ${length} bytes
10def bout(a: bytes, length=16):
11 string = a.hex()
12 return ' '.join(string[i:i+length] for i in range(0,len(string),length))
13
14conn = None
15# Query remote padding oracle
16def queryOracle(msg: bytes):
17 global conn
18 conn.send((msg.hex() + "\n").encode('ASCII'))
19 # Receive the response from the server
20 response = conn.recv()
21 print(f"Query(b\"{bout(msg)}\"): {response[:4]}", end='\r')
22 return response[:2] != b"no"
23
24# Connect to remote padding oracle
25def reconnect():
26 global conn
27 host = 'challs.umdctf.io'
28 port = 32333
29
30 if conn is not None:
31 conn.close()
32 # Connect to the host
33 conn = remote(host, port)
34 # Receive the response from the server
35 res = conn.recv()
36 print("Received:", res)
37
38 data = res[27:171]
39 data = data.decode("utf-8")
40 return bytes.fromhex(data)