Embrace the randomness
Cryptography · Харуул Занги U18: 2024 · Superior
Problem
This challenge involves reversing the encryption process to recover the original flag. The encryption uses bitwise operations that depend on randomly generated keys. Specifically:
The
encrypt
function creates a ciphertext by applying bitwise AND, OR, and NOT operations between the flag and a random key.A large number of ciphertexts (6240) are generated for different random keys.
The goal is to deduce the original flag using the fact that some bytes are missing from the ciphertext due to the encryption process.
import random
from secret import flag
def encrypt(a, b):
result = bytearray()
for i in range(len(a)):
result.append((a[i] & ~(b[i] % 0xff)) | (~a[i] & (b[i] % 0xff)))
return result
for _ in range(624 * 10):
key = [random.getrandbits(32) for _ in range(len(flag))]
ct = encrypt(flag, key)
print(ct.hex())
Solution
Analyze the Encryption:
Each byte of the ciphertext depends on the corresponding byte of the flag and key.
Certain flag bytes will not appear in the ciphertext for any key, due to the specific bitwise operations.
Leverage the Missing Byte Property:
For each position in the flag, identify the byte that does not appear in the corresponding position of all ciphertexts.
Use this "missing byte" and XOR it with
255
to derive the original flag byte.
Implement Flag Recovery:
Parse the ciphertexts from the output file.
Iterate through each position in the ciphertexts, collect all seen bytes, and find the missing one.
Recover the flag byte by byte using the above approach.
Output the Flag:
Decode the recovered flag and print it.
def recover_flag(ciphertexts, length):
flag = bytearray()
for i in range(length):
# Collect all possible bytes for this position
seen_bytes = set(ct[i] for ct in ciphertexts)
# Find the missing byte (the one that doesn't appear in the ciphertexts)
missing_byte = next(b for b in range(256) if b not in seen_bytes)
# XOR the missing byte with 255 to get the flag byte
flag.append(missing_byte ^ 255)
return flag
# Load ciphertexts from output.txt
ciphertexts = []
with open("output.txt", "r") as f:
for line in f:
ciphertexts.append(bytearray.fromhex(line.strip()))
# Recover the flag (assuming we know its length)
flag_length = len(ciphertexts[0]) # All ciphertexts are the same length
flag = recover_flag(ciphertexts, flag_length)
print("Recovered flag:", flag.decode())
Last updated