Google CTF 2024 Writeup
Desfunctional
The Complement Property of Triple Data Encryption Standard (3DES) with three 56-bit keys in CBC mode
Problem
The challenge has 3 functionality:
- Retrieve the secret encrypted with 3DES 192 bit key in CBC mode
- Submit any input (in hex string form) which will be decrypted using the same iv, but a corrupted key, and get the result. A maximum of 128 decryption requests can be made.
- Guess the plaintext of the encrypted secret to get the flag
The iv is not given. If there is no corruption on the key, the encrypted secret can just be submitted to API option 2, to get the plaintext. At a glance, the corruption seems to be random, in which different bit-positions of the key will be flipped.
The following source code is given below: chall.py
import signal
import os
import random
import sys
from Crypto.Cipher import DES3
class Desfunctional:
def __init__(self):
self.key = os.urandom(24)
self.iv = os.urandom(8)
self.flipped_bits = set(range(0, 192, 8))
self.challenge = os.urandom(64)
self.counter = 128
def get_flag(self, plain):
if plain == self.challenge:
with open("flag.txt", "rb") as f:
FLAG = f.read()
return FLAG
raise Exception("Not quite right")
def get_challenge(self):
cipher = DES3.new(self.key, mode=DES3.MODE_CBC, iv=self.iv)
return cipher.encrypt(self.challenge)
def corruption(self):
if len(self.flipped_bits) == 192:
self.flipped_bits = set(range(0, 192, 8))
remaining = list(set(range(192)) - self.flipped_bits)
num_flips = random.randint(1, len(remaining))
self.flipped_bits = self.flipped_bits.union(
random.choices(remaining, k=num_flips))
mask = int.to_bytes(sum(2**i for i in self.flipped_bits), 24)
return bytes(i ^ j for i, j in zip(self.key, mask))
def decrypt(self, text: bytes):
self.counter -= 1
if self.counter < 0:
raise Exception("Out of balance")
key = self.corruption()
if len(text) % 8 != 0:
return b''
cipher = DES3.new(key, mode=DES3.MODE_CBC, iv=self.iv)
return cipher.decrypt(text)
if __name__ == "__main__":
chall = Desfunctional()
PROMPT = ("Choose an API option\n"
"1. Get challenge\n"
"2. Decrypt\n"
"3. Get the flag\n")
signal.alarm(128)
while True:
try:
option = int(input(PROMPT))
if option == 1:
print(chall.get_challenge().hex())
elif option == 2:
ct = bytes.fromhex(input("(hex) ct: "))
print(chall.decrypt(ct).hex())
elif option == 3:
pt = bytes.fromhex(input("(hex) pt: "))
print(chall.get_flag(pt))
sys.exit(0)
except Exception as e:
print(e)
sys.exit(1)
Approach
The first main point that should be inferred from the code is that, the way the corruption is being impelemented, there will be a state in which every bits of the key will be flipped!
def corruption(self):
if len(self.flipped_bits) == 192:
self.flipped_bits = set(range(0, 192, 8))
remaining = list(set(range(192)) - self.flipped_bits)
num_flips = random.randint(1, len(remaining))
self.flipped_bits = self.flipped_bits.union(
random.choices(remaining, k=num_flips))
mask = int.to_bytes(sum(2**i for i in self.flipped_bits), 24)
return bytes(i ^ j for i, j in zip(self.key, mask))
The corruption function will do the following:
- Check if every bit-positions have already been flipped. If yes, reset to the initial state. Note that earlier, the initial state has been set to flip the bit at position 0, 8, 16, …, 184. Notice that for DES, those bits are parity bit which does not affect the decryption result even if those bits are changed.
- Randomly select the number of bits to be flipped
- Union the newly selected bits to be flipped with the bits that are already flipped, meaning no bit will be flipped twice
- Construct a mask which will facilitate the bit-flipping to the key
After several rounds of flipping, the number of remaining bits that have not been flipped decreases, until none of it left when all of the remaining unflipped bits have been selected to get flipped. At this state, the resulting mask will be b'\xff'*24, in other words, the input will be decrypted using a key which has all of its original bit flipped. So what’s the deal?
This state where every bits of the key is flipped will happen several times, due to the reset in step 1. That means, the round where every bits of the key is flipped can be known, since the decryption result will be the same each time the key has all of its original bit flipped. This feels like a special situation that could enable some exploitation.
This lead up to the next question, what is the relation between DES encryption/decryption using a normal key and the same key but all of its bit flipped? It turns out that DES has Complementation Property, in which encrypting a plaintext with the bitwise complement of the key, will result in the bitwise complement of the cipher encrypted with the same key.
source: https://en.wikipedia.org/wiki/Data_Encryption_Standard
This mean, the API option 2 can be used to obtain the secret plaintext, by inputting the bitwise complement of the encrypted secret obtained from option 1. The final thing to do is making the adjustment to take into account the triple key and CBC mode. Below is the steps for DES CBC decryption:
source: https://sectigostore.com/blog/what-is-des-encryption-a-look-at-the-des-algorithm/
-
Subsequent Blocks:
- Decrypt the ciphertext block with (K_3).
- Encrypt the result with (K_2).
- Decrypt the result with (K_1).
- XOR the result with the previous ciphertext block to get the plaintext block.
- Store the ciphertext block for use with the next block.
-
First Block:
- Decrypt the ciphertext block with (K_3).
- Encrypt the result with (K_2).
- Decrypt the result with (K_1).
- XOR the result with the IV to get the plaintext block.
- Store the ciphertext block as the IV for the next block.
For step 4, since the 2nd to 8th blocks would have been XOR-ed with previous ciphertext block (which is already the bitwise complement of the original ciphertext block), only the result for 1st block need to be flipped (since it is “only” being XOR-ed with the IV) to convert it into the 1st block of plaintext secret.
Solution
The solver will keep sending input to the Decryption function, until there is a decryption result that appears twice (this is the decryption result when the key being used is the bitwise complement of the original key). Before sending as input, the encrypted result will be XOR-ed with b'\xff'*64 to flip all of its bit. Due to the nature of CBC mode, only the 1st block of the decryption result needs to be flipped (XOR-ed with b'\xff'*8) to get the plaintext secret.
solver.py
from pwn import *
import time
# Connect to the server
conn = remote('desfunctional.2024.ctfcompetition.com', 1337, level='debug')
def get_challenge():
conn.sendline('1'.encode())
conn.recvuntil(b"flag\n")
challenge = conn.recvline().strip().decode()
return challenge
def decrypt_challenge(challenge):
conn.recvuntil(b"flag\n")
conn.sendline('2'.encode())
conn.recvuntil(b"ct: ")
conn.sendline(challenge)
response = conn.recvline().strip().decode()
return response
def get_flag(challenge):
conn.recvuntil(b"flag\n")
conn.sendline('3'.encode())
conn.recvuntil(b"pt: ")
conn.sendline(challenge)
response = conn.recvline().strip().decode()
return response
def main():
res=set()
challenge = get_challenge()
#print(f"Challenge: {challenge}")
while True:
try:
# Decrypt the challenge
flip_enc=xor(bytes.fromhex(challenge),b'\xff'*64).hex()
response = decrypt_challenge(flip_enc.encode())
if response in res:
secret=xor(bytes.fromhex(response),b'\xff'*8+b'\x00'*56).hex()
print(get_flag(secret.encode()))
break
else:
res.add(response)
except Exception as e:
print(f"Error: {e}")
break
if __name__ == "__main__":
main()
FLAG: CTF{y0u_m4y_NOT_g3t_th3_k3y_but_y0u_m4y_NOT_g3t_th3_c1ph3rt3xt_as_w3ll}