Some say that 75% of rock paper scissor matches end up in a tie. We suggest a more interesting one.

This challenge looks like a fun little game at first: you pick one of five categories, the computer picks one too, and you win/lose based on a fixed set of rules.

But the real goal is:

Beat the computer 200 times in a row.

And for the first 100 rounds, the game tells you how your choice compares to the computer’s (win, lose, or tie). No punishment. Just “free practice”.

It’s bait.
These 100 practice rounds are our way in.

1 - Understanding the game rules

You can choose one of these:

Welcome to C.M.P.R.W. If you win against the computer 200 time in a row. You may claim our [SPECIAL] reward. Here, have some free trials as new-comer goodies. Choose one of 'crypto', 'misc', 'pwn', 'rev', 'web':

The computer also chooses one.
Some choices beat others, similar to rock-paper-scissors.

Imagine a circle: each category beats two others and loses to two others.

So if we know what the computer is going to choose, we can always pick the winning option.

This entire challenge becomes: Predict what the computer will choose next.

2 - The computer is not actually random

Inside the challenge code, we find how the computer decides its choice.

This is the key part:

choice = (state & 0xf) % 5

Here’s the idea:

• The computer keeps a big 64-bit number called state.
• To choose a move, it looks at the last 4 bits of this number.
• It turns that into one of the 5 categories.
• Then it updates the number using a fixed set of steps.

This means: The computer is not using real randomness. It is using a predictable pattern. This pattern is called an LFSR, a simple type of pseudo-random number generator.

The important part: If you know the state at any moment, you can know all future moves.

3 - The 100 practice rounds leak information

Every time we play, the server tells us:

• “tie” → the computer picked the same as us
• “win” → our choice beats the computer’s
• “lose” → the computer’s choice beats ours

This gives us constraints on the value of:

(state_t & 0xf) % 5

This doesn’t reveal the nibble directly but it tells us which subset of 0–4 it must belong to.

After 100 rounds, we have:

• 100 constraints
• on 100 successive RNG states

This is enough to reconstruct the initial 64-bit state.

4 - Recovering the Hidden RNG State

At this point, we know two things:

1. The computer’s choice each round is determined by the lowest nibble (4 bits) of a hidden 64-bit number (state).

2. We collected 100 rounds of feedback (“win / lose / tie”). These don’t tell us the exact nibble, but they do tell us which nibble mod 5 the computer must have had.

This means each round gives us a clue like:

(state_t & 0xF) % 5 ∈ {some subset of 0..4}

Now the challenge is: How do we reconstruct a 64-bit number knowing only 100 partial constraints on its lowest 4 bits across time, especially when the state changes every round via an LFSR?

A 64-bit number is simply:

N0 | N1 | N2 | ... | N15

where each Ni is a nibble (4 bits, value 0–15).

So instead of solving for one giant number, we solve for 16 tiny numbers, each between 0 and 15. This makes the search space manageable.

Here’s the key observation: During the first 16 rounds, the LFSR output nibble depends only on the nibble at the same position.

Why ? Because before the state gets mixed too much, each step of the LFSR shifts the state right, meaning:

• Round 0 output depends on N0
• Round 1 output depends on N1
• Round 2 output depends on N2
• …
• Round 15 output depends on N15

This gives us strong narrowing: For nibble Ni, only the values v ∈ [0..15] that satisfy:

(v % 5) ∈ allowed residues from round i

are possible.

Often, this shrinks each nibble’s possibilities to 2–4 values instead of 16. This is phase 1 of the reconstruction.

After 16 rounds, things get more complex: Because the LFSR shifts and mixes bits, each output nibble becomes a combination of several original nibbles.

Your script computes these dependencies in advance. Specifically, for each round t, you compute:

Which nibble positions {i, j, k, ...}  
in the original 64-bit state  
influence (state_t & 0xF)

This is done via the functions:

• step_deps()
• one_rng_step_deps()

The result is out_dep_nibbles[t]:

Round t depends on nibble indices { n1, n2, ..., nk }.

Think of it like arrows:

Nibble 0   → influences rounds: {0, 4, 7, 10, 13, ...}
Nibble 1   → influences rounds: {1, 5, 8, 11, 14, ...}
...
Nibble 15  → influences rounds: {15, 18, 23, ...}

This mapping is crucial.

Now the script performs a depth-first search over the 16 nibbles:

1. Pick N0 from its allowed values
2. Pick N1
3. Pick N2
4. …
5. Up to N15

After each assignment, the script asks: “Given the nibbles I’ve already chosen, are any of the early rounds guaranteed to be impossible ?”

To verify this, it:

• builds a partial 64-bit state
• simulates the LFSR forward
• checks all rounds where all dependencies are already known
• if any output contradicts constraints → prune the branch

This dramatically reduces the search space. Most incorrect states are eliminated before even trying to assign all 16 nibbles.

In practice:

• Instead of checking 16⁶⁴ possibilities
• You might only explore a few hundred valid partial states This finishes in under a second

When the DFS reaches nibble 15 and all constraints for all 100 rounds match your observations:

• the full 64-bit state has been successfully reconstructed
• this state reproduces exactly the outputs the server produced
• your local RNG is now perfectly in sync with the server

At that point:

• The RNG runs forward 100 rounds (to match server state)
• Then generates 200 predicted moves
• Each predicted move is countered with its winning option
• You win 200 rounds flawlessly

5 - Running the full exploit

This script:

1. Connects to the server
2. Plays 100 “crypto” moves to gather observations
3. Uses constraint solving to recover the 64-bit RNG state
4. Predicts the next 200 moves
5. Sends the winning move each time
6. Prints the final flag

#!/usr/bin/env python3

import socket

HOST = "challs.glacierctf.com"
PORT = 13375

TAGS = ["crypto", "misc", "pwn", "rev", "web"]

edges = []
for i in range(len(TAGS)):
    j1, j2 = (i + 1) % len(TAGS), (i + 3) % len(TAGS)
    edges.append((TAGS[i], TAGS[j1]))
    edges.append((TAGS[i], TAGS[j2]))

def result_idx(u_idx, c_idx):
    u, c = TAGS[u_idx], TAGS[c_idx]
    if u_idx == c_idx:
        return "tie"
    if (u, c) in edges:
        return "win"
    if (c, u) in edges:
        return "lose"
    raise RuntimeError("invalid result")

WIN_MOVE = {}
for c_idx in range(5):
    winners = []
    for u_idx in range(5):
        if result_idx(u_idx, c_idx) == "win":
            winners.append(u_idx)
    WIN_MOVE[c_idx] = winners[0]  


def rng_from_state(state):
    while True:
        yield state & 0xF
        for _ in range(4):
            bit = (state ^ (state >> 3) ^ (state >> 7)) & 1
            state = (state >> 1) | (bit << 63)



def step_deps(deps):
 
    new = [set() for _ in range(64)]
    tap = deps[0] ^ deps[3] ^ deps[7]   
    for i in range(63):
        new[i] = deps[i + 1].copy()
    new[63] = tap
    return new

def one_rng_step_deps(deps_state):
    
    out = deps_state[:4]
    for _ in range(4):
        deps_state = step_deps(deps_state)
    return out, deps_state


MAX_T = 200
deps_state = [ {i} for i in range(64) ]
out_dep_nibbles = []

for t in range(MAX_T):
    out_bits, deps_state = one_rng_step_deps(deps_state)
    nibbles = set()
    for bitset in out_bits:
        for b in bitset:
            nibbles.add(b // 4)
    out_dep_nibbles.append(nibbles)



def recover_state_from_observations(allowed_residues, max_t_use=100):

    T = min(max_t_use, len(allowed_residues))


    domains = []
    for i in range(16):
        R = allowed_residues[i]
        vals = [v for v in range(16) if (v % 5) in R]
        if not vals:
            raise RuntimeError("No values for nibble", i)
        domains.append(vals)

    partial = [None] * 16
    found_state = None
    depN = out_dep_nibbles

    def check_prefix(k):

        state = 0
        for i in range(k):
            state |= (partial[i] & 0xF) << (4 * i)

        rng_state = state
        assigned_set = set(range(k))

        for t in range(T):
            if depN[t].issubset(assigned_set):
                out_nib = rng_state & 0xF
                if (out_nib % 5) not in allowed_residues[t]:
                    return False

            for _ in range(4):
                bit = (rng_state ^ (rng_state >> 3) ^ (rng_state >> 7)) & 1
                rng_state = (rng_state >> 1) | (bit << 63)
        return True

    def dfs(i):
        nonlocal found_state
        if found_state is not None:
            return
        if i == 16:
 
            state = 0
            for j in range(16):
                state |= (partial[j] & 0xF) << (4 * j)
            rng_state = state
            for t in range(T):
                nib = rng_state & 0xF
                if (nib % 5) not in allowed_residues[t]:
                    return
                for _ in range(4):
                    bit = (rng_state ^ (rng_state >> 3) ^ (rng_state >> 7)) & 1
                    rng_state = (rng_state >> 1) | (bit << 63)
            found_state = state
            return

        for v in domains[i]:
            partial[i] = v
            if check_prefix(i + 1):
                dfs(i + 1)
                if found_state is not None:
                    return
        partial[i] = None

    dfs(0)
    if found_state is None:
        raise RuntimeError("State recovery failed")
    return found_state



def recv_until(sock, marker: bytes):
    data = b""
    while marker not in data:
        chunk = sock.recv(1)
        if not chunk:
            break
        data += chunk
    return data

def recv_line(sock):
    data = b""
    while not data.endswith(b"\n"):
        c = sock.recv(1)
        if not c:
            break
        data += c
    return data.decode(errors="ignore").strip()

def main():
    s = socket.create_connection((HOST, PORT))

    print(recv_line(s))
    print(recv_line(s))
    print(recv_line(s))

    allowed = []
    user_idx = 0  


    for t in range(100):

        recv_until(s, b": ")
 
        s.sendall(b"crypto\n")

        res = recv_line(s).strip()
        print(f"[FREE {t:03d}] result = {res}")

        if res == "tie":
            allowed.append({0})
        elif res == "win":
            allowed.append({1, 3})
        elif res == "lose":
            allowed.append({2, 4})
        else:
            raise RuntimeError("Unexpected response:", res)

 
    print("[*] Recovering RNG state...")
    state0 = recover_state_from_observations(allowed, max_t_use=100)
    print(f"[*] Recovered state0 = {state0:#018x}")


    rng = rng_from_state(state0)

    for _ in range(100):
        next(rng)


    for i in range(200):

        recv_until(s, b": ")


        choice_idx = next(rng) % 5
        my_idx = WIN_MOVE[choice_idx]
        my_tag = TAGS[my_idx]

        print(f"[REAL {i:03d}] computer={TAGS[choice_idx]}, playing={my_tag}")
        s.sendall((my_tag + "\n").encode())
        res = recv_line(s)
        print(f"   -> server says: {res}")
        if "lose" in res or "Sorry" in res:
            print("[-] Something went wrong, lost a real round.")
            return


    try:
        while True:
            line = recv_line(s)
            if not line:
                break
            print(line)
    finally:
        s.close()

if __name__ == "__main__":
    main()

The exploit wins all 200 rounds:

[+] Success! Won 200/200 rounds!
[FLAG] gctf{y0u_4r3_7H3_TrUE_rN635u5_n0W_7rY_j3N5H1n_1Mp4C7}

Game over.

By Roockbye