CrateCTF 2025 Writeup: Fiats och Shamirs Skyltsmedja

The Challenge Overview

We are given a Python script running on a server. It implements a digital signature scheme based on the Fiat-Shamir heuristic.

The file provided in the chal (below):

The server gives us:

1. Public Parameters: Large numbers P (prime) and G (generator).
2. Public Key: y (where $y = G^x \mod P$). We do not know the private key x.
3. A Signing Oracle: A function that signs messages for us, but checks if b"flag" in msg and refuses to sign them.
4. A Verification Function: A function called get_flag that asks for a signature on the specific message: "Kund nr. {userid} får hämta flaggan" (Customer {userid} is allowed to get the flag).

If we can provide a valid signature for that message, the server gives us the flag.

The Tech Stuff: How the Signature Works

The code implements a Schnorr Identification Protocol made non-interactive. It runs 128 rounds to prove validity.

For every round i:

1. The signer generates a random number r and calculates a commitment c.
2. A challenge bit (0 or 1) is generated by hashing the message and the commitment.
3. Based on the challenge bit, the signer provides an answer ans:
   • If Challenge is 0: The verification checks if $G^{ans} = c \cdot y \mod P$.
   • If Challenge is 1: The verification checks if $G^{ans} = c \mod P$.

This is designed so that you can only pass all 128 rounds if you actually know the private key x... OR if you can predict the future.

The Vulnerability: The "Random" Oracle

The flaw lies in how the "challenge bit" is created. In a secure system, the challenge should be unpredictable until after we commit to a value c.

However, the code calculates the challenge like this:

h.update(c.to_bytes(...))
if f"{int(h.hexdigest(), 16):b}".count("1") % 2:
    # Challenge is 1
else:
    # Challenge is 0

Because the code runs locally on our side (or we can replicate the logic), the "random" challenge isn't actually random. It is deterministic.

If we pick a value for c, we can immediately calculate exactly what the challenge bit will be.

The Exploit: The Simulator Attack

Since we don't know the private key x, we cannot satisfy the condition where the challenge is 0 (which requires y). However, we can easily satisfy the condition where the challenge is 1 (which only requires basic math). We need to force the system to give us a challenge of 1 for every single one of the 128 rounds.

We use a technique called a Simulator Attack (or rewinding):

1. Guess: We assume the challenge for the current round will be 1.
2. Pick an Answer: We choose a random number for ans.
3. Calculate Backwards: We calculate what c must be to satisfy the equation $c = G^{ans} \mod P$.
4. Verify the Future: We hash this calculated c to see what the challenge bit actually becomes.
   • If it's 1: Great! We got lucky. We save this (c, ans) pair and move to the next round.
   • If it's 0: Our guess failed. We discard this attempt, pick a new random ans, and try again.

Since the challenge is a single bit (0 or 1), we have a 50% chance of success on every try. On average, we only need 2 attempts per round. For 128 rounds, the computer can solve this in seconds.

The Solver Script

Here is the Python script that performs the attack:

from pwn import remote
from hashlib import sha512
from secrets import randbelow
from tqdm import tqdm

def solve():
    r = remote("challs.crate.nu", 2457)

    r.recvuntil(b"kund nr. ")
    userid = int(r.recvuntil(b"!", drop=True).decode())
    
    r.recvuntil(b"P = ")
    P = int(r.recvline().decode().strip())
    
    r.recvuntil(b"G = ")
    G = int(r.recvline().decode().strip())
    
    r.recvuntil(b"y = ")
    y = int(r.recvline().decode().strip())
    
    print(f"[*] Target UserID: {userid}")

    msg = f"Kund nr. {userid} får hämta flaggan".encode("utf-8")
    
    bits = 1024
    byte_len = bits // 8
    h = sha512(msg)
    h.update(P.to_bytes(byte_len, 'big') + G.to_bytes(byte_len, 'big') + y.to_bytes(byte_len, 'big'))

    forged_signature = [y]

    print("[*] Forging signature (Time Travel in progress)...")
    for _ in tqdm(range(128)):
        h_state = h.copy() # Save state to rewind if we fail
        
        while True:
            ans_attempt = randbelow(P - 1)
            
            c_attempt = pow(G, ans_attempt, P)
            
            h_check = h_state.copy()
            h_check.update(c_attempt.to_bytes(byte_len, 'big'))
            
            h_val = int(h_check.hexdigest(), 16)
            challenge_bit = f"{h_val:b}".count("1") % 2

            if challenge_bit == 1:
                forged_signature.append(c_attempt)
                forged_signature.append(ans_attempt)
                
                h.update(c_attempt.to_bytes(byte_len, 'big'))
                h.update(ans_attempt.to_bytes(byte_len, 'big'))
                break
            

    hex_sig = "".join(f"{n:0{256}x}" for n in forged_signature)
    
    r.sendline(b"f") # Choose 'get flag'
    r.recvuntil(b"> ")
    r.sendline(msg)
    r.recvuntil(b"> ")
    r.sendline(hex_sig.encode())
    
    print(r.recvall().decode())

if __name__ == "__main__":
    solve()

Result

Running the script allows us to bypass the private key requirement entirely. We essentially faked the proof by finding inputs that satisfy the verification check.

Flag: cratectf{sicken timetraveller!}