TJCTF 2025: crypto/pseudo-secure

Can you predict the future? What about the past?

Author: tmm

We’re given source code running on a server:

import random
import base64
import sys
import select

class User:
    def __init__(self, username):
        self.username = username
        self.key = self.get_key()
        self.message = None

    def get_key(self):
        username = self.username
        num_bits = 8 * len(username)
        rand = random.getrandbits(num_bits)
        rand_bits = bin(rand)[2:].zfill(num_bits)
        username_bits = ''.join([bin(ord(char))[2:].zfill(8) for char in username])
        xor_bits = ''.join([str(int(rand_bits[i]) ^ int(username_bits[i])) for i in range(num_bits)])
        xor_result = int(xor_bits, 2)
        shifted = ((xor_result << 3) & (1 << (num_bits + 3)) - 1) ^ 0x5A
        byte_data = shifted.to_bytes((shifted.bit_length() + 7) // 8, 'big')
        key = base64.b64encode(byte_data).decode('utf-8')
        return key
    
    def set_message(self, message):
        self.message = message

def input_with_timeout(prompt="", timeout=10):
    sys.stdout.write(prompt)
    sys.stdout.flush()
    ready, _, _ = select.select([sys.stdin], [], [], timeout)
    if ready:
        return sys.stdin.buffer.readline().rstrip(b'\n')
    raise Exception
input = input_with_timeout

flag = open("flag.txt").read()

assert len(flag)%3 == 0
flag_part1 = flag[:len(flag)//3]
flag_part2 = flag[len(flag)//3:2*len(flag)//3]
flag_part3= flag[2*len(flag)//3:]

admin1 = User("Admin001")
admin2 = User("Admin002")
admin3 = User("Admin003")
admin1.set_message(flag_part1)
admin2.set_message(flag_part2)
admin3.set_message(flag_part3)
user_dict = {
    "Admin001": admin1,
    "Admin002": admin2,
    "Admin003": admin3
}

print("Welcome!")
logged_in = None
user_count = 3 
MAX_USERS = 200

while True:
    if logged_in is None:
        print("\n\n[1] Sign-In\n[2] Create Account\n[Q] Quit")
        inp = input().decode('utf-8').strip().lower()
        match inp:
            case "1":
                username = input("Enter your username:  ").decode('utf-8')
                if username in user_dict:
                    user = user_dict[username]
                    key = input("Enter your sign-in key: ").decode('utf-8')
                    if key == user.key:
                        logged_in = user
                        print(f"Logged in as {username}")
                    else:
                        print("Incorrect key. Please try again!")
                else:
                    print("Username not found. Please try again or create an account.")
            case "2":
                if user_count >= MAX_USERS:
                    print("Max number of users reached. Cannot create new account.")
                else:
                    username = input("Select username:  ").decode('utf-8')
                    if username in user_dict:
                        print(f"Username '{username}' is already taken!")
                    else:
                        user_dict[username] = User(username)
                        user_count += 1 
                        print(f"Account successfully created!\nYour sign-in key is: {user_dict[username].key}")
            case "q":
                sys.exit()
            case _:
                print("Invalid option. Please try again.")
    else:
        print(f"Welcome, {logged_in.username}!")
        print("\n\n[1] View Message\n[2] Set Message\n[L] Logout")
        inp = input().decode('utf-8').strip().lower()
        match inp:
            case "1":
                print(f"Your message: {logged_in.message}")
            case "2":
                new_message = input("Enter your new message: ").decode('utf-8')
                logged_in.set_message(new_message)
                print("Message updated successfully.")
            case "l":
                print(f"Logged out from {logged_in.username}.")
                logged_in = None
            case _:
                print("Invalid option. Please try again.")

Summary:

• We start out being able to create or log into an account.
• Logging into an account necessitates a “key”.
• Creating an account gives us the key for that new account.
• Keys are generated based on the username and Python’s standard library random.
• We can get a “message” for an account once we have logged into it.
• The flag is the message for the Admin accounts, created at startup.

The goal is then obvious: recover the key for the admin accounts to obtain the messages.

Python’s random PRNG is based on a Mersenne Twister, which we can recover the state of, if we obtain enough of its outputs. However, recovering the state is usually only useful to be able to predict future outputs of the PRNG, and the key for the Admin account is generated before any keys we might obtain.

This is alluded to in the description of the challenge: “Can you predict the future? What about the past?”

In fact, we absolutely can. Among the many implementations of Mersenne Twister which were made for the purpose of recovering its state from outputs, some allow the user to rewind. That is, we can take a PRNG state, and obtain the state that PRNG was in before generating the last output. I decided to use this implementation.

We can repeat the rewinding process as many times as necessary to go back to the initial state of the PRNG at startup, then run that PRNG forwards to obtain the randomness for the admin keys.

Enough theory, let’s apply.

First, we need to register a user with a username long enough to obtain the PRNG outputs to recover state from.

from pwn import *
from mersenne_twister import MT19937
import base64

r = remote("tjc.tf", 31400) # Connect to the challenge server

mt = MT19937()

# mt.n is the size of the PRNG state (which is also how many outputs we need to recover the state),
# with each part of the state being a 32 bit integer.
needbits = mt.n * 32
needbytes = needbits // 8
username = needbytes * b"A"

# Interact with the server to "[2] Create Account" with our desired username.
r.recv()
r.sendline(b"2")
r.recv()
r.sendline(username)
r.recvuntil(b"Your sign-in key is: ")

key = r.recvline().decode().strip()

We now need to reverse the key generation until we’re back at our raw random.getrandbits output. The way this process is written in the challenge server is quite annoying; we can do simpler.

In summary, get_key on the server:

• Generates as many bits as our username: random.getrandbits(num_bits)
• Converts the username and random bits to binary string
• Exclusive-ors those binary strings: ''.join([str(int(rand_bits[i]) ^ int(username_bits[i])) for i in range(num_bits)])
• Shift, masks, and exclusive-ors with a constant: ((xor_result << 3) & (1 << (num_bits + 3)) - 1) ^ 0x5A
• Converts the integer to bytes: shifted.to_bytes((shifted.bit_length() + 7) // 8, 'big')
• Base64-encodes those bytes: base64.b64encode(byte_data)

The conversion to binary is unnecessary, Python can xor arbitrarily large integers just fine. So is the mask operation at the end: we’re always generating a mask with all of the bits on.

Getting rid of those parts and going in reverse:

# Base64-decode
key_bytes = base64.b64decode(key)
# Those bytes came from an integer
key_int = int.from_bytes(key_bytes, 'big')
# Which was xor'd and shifted
unshifted = (key_int ^ 0x5A) >> 3
# Convert the username to integer too so we can xor with it
username_bits = int.from_bytes(username, 'big')
# And we've got our randomness!
rand = unshifted^username_bits

We can now finally clone the PRNG state, which is quite easy with the aforementioned library.

outputs = []
for _ in range(mt.n):
    outputs.append(rand & 0xffffffff)
    rand >>= 32

mt.clone_state_from_output_and_rewind(outputs)

Next, rewind till we’re back before the Admin accounts were created:

admin_names = ["Admin001", "Admin002", "Admin003"]
admin_bits = sum(8*len(s) for s in admin_names)
need_rewind = admin_bits//32

mt.rewind(rounds=need_rewind)

And now we do everything forward like the server did.

flag = ""

# For each admin
for name in admin_names:
    # Admin names are 8 bytes long, we need 2 32-bit outputs
    r1 = mt.get_next_random()
    r2 = mt.get_next_random()
    rand = r2<<32 | r1

    # Reconstructing the key: 1. xor with username
    xor_result = rand^int.from_bytes(name.encode(), 'big')
    # Reconstructing the key: 2. shift and constant xor
    shifted = (xor_result << 3) ^ 0x5A
    # Reconstructing the key: 3. convert to bytes
    byte_data = shifted.to_bytes((shifted.bit_length() + 7) // 8, 'big')
    # Reconstructing the key: 4. base64-encode
    key = base64.b64encode(byte_data).decode('utf-8')

    # Interact with the server: [1] Sign-In
    r.sendline(b"1")
    r.recv()
    # giving the server our username to log into...
    r.sendline(name.encode())
    r.recv()
    # and that user's key which we've just reconstructed
    r.sendline(key)
    r.recv()
    # Finally, [1] View Message to obtain the part of the flag
    r.sendline(b"1")
    r.recvuntil(b"Your message: ")
    message = r.recvline()

    flag += message.decode().strip()

    # Make sure we [L] Logout so that the next iteration of the loop can log
    # into the next admin account
    r.sendline(b"L")
    r.recv()

print(flag) # Win!

Flag: tjctf{1_gu3ss_h1nds1ght_15_20/20}