TFC CTF 2024 - SECRET MESSAGE

Description

Category: Misc

Help us encrypt this message. You don’t need to know it

Author: Hiumee

Attachment:

• secret_message.zip

Overview

In this challenge, we need to provide to the server six different seeds that will be used to generate random bytes.

Then those random bytes are shuffled and xored with the flag (for the first round) or the encrypted flag (for the following ).

Finally the server returns the encrypted flag.

Solution

1. Bad shuffle

def hide(string, seed, shuffle):
    random.seed(seed)
    byts = []
    for _ in range(len(string)):
        byts.append(random.randint(0, 255))

    random.seed(shuffle)
    for i in range(100):
        random.shuffle(byts)

    return bytes([a^b for a, b in zip(string, byts)])

In the hide function, random bytes generated with one of our six seeds are always shuffle in the same way because of the random.seed(shuffle) which reset the PRG to its initial state.

At the end, the successive calls of the function hide can be broken down to:

\[hide(hide(hide(flag, seed_1, shuffle), seed_2, shuffle), seed_3, shuffle) =\] \[flag \oplus shuffle(bytes_{seed_1}) \oplus shuffle(bytes_{seed_1}) \oplus shuffle(bytes_{seed_3})\]

In other words, the successive encryption process (which makes bruteforcing much harder) is simply a linear operation (much easier to bruteforce).

2. Bruteforce the shuffle

We provided the seeds used to generate the random bytes, so we can recover them easily.

However, to decrypt the flag we still need to know how those bytes have been shuffled so we can decrypt the flag like that:

\[flag[i] = encrypted[i] \oplus bytes_{seed_1}[i] \oplus bytes_{seed_2}[i] \oplus ... \oplus bytes_{seed_6}[i]\]

Or not?

Let’s $X[i] = bytes_{seed_1}[i] \oplus bytes_{seed_2}[i] \oplus … \oplus bytes_{seed_6}[i]$ (I’ll call it random bytes combination).

We can bruteforce the shuffle by xoring every possible random bytes combination to a single character of the encrypted flag.

What we will get is a set of possible decrypted character.

Because the shuffle is random each time we interact with the server, we will get a different set of possible decrypted character.

Since the real character is necessarily in this set, we can perform multiple set intersections until only the real character remains.

Solve script:

import random
from pwn import *

context.log_level = 'critical'

def get_hidden_flag():
    r = remote('challs.tfcctf.com', 30727)
    for seed in SEEDS:
        r.sendline(str(seed).encode())

    r.recvuntil(b'Here is your result: ')
    hidden_flag = eval(r.recvline())
    r.close()

    return hidden_flag

SEEDS = [1, 2, 3, 4, 5, 6]

len_flag = len(get_hidden_flag())
FLAG = [set(chr(i) for i in range(0xff)) for _ in range(len_flag)]

XORs = [0 for _ in range(len_flag)]

# Recover random bytes combination
for seed in SEEDS:
    random.seed(seed)
    for i in range(len_flag):
        XORs[i] ^= random.randint(0, 255)

while True:
    for i, c in enumerate(get_hidden_flag()):
        possible_char = set()
        # Get all possible character of flag[i]
        for j in range(len_flag):
            possible_char.add(chr(c ^ XORs[j]))
        # Intersection to eliminate random ones
        FLAG[i].intersection_update(possible_char)

    if all([len(charset)==1 for charset in FLAG]):
        break

print("".join([charset.pop() for charset in FLAG]))

Flag: TFCCTF{random_is_not_secur3}