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())

518KB

output.txt

Encrypted Flag

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())