COMpetition

Category: Crypto Flag: GPNCTF{WaIt, 17'5 NOT Ju5T lUCk? N3v3R HAS 83EN.}

"A challenge about commitments."

TL;DR

The challenge is a 100-round rock-paper-scissors game where you must commit to your move before the server reveals its own. A binding commitment scheme should make winning every round impossible. But the scheme here — sha256(r1 + message + r2) with attacker-controlled, variable-length nonces r1 and r2 — is not binding. A single commitment to the string "rockpaperscissors" can be opened to any of the three moves by sliding the split between r1 and r2. So we commit blindly, see the server's move, and reveal whatever beats it.

The Challenge

We're given a small Python service (main.py):

from hashlib import sha256
from os import environ
from secrets import choice

NUM_ROUNDS = 100

def verify(commitment: bytes, message: bytes, unveil_info: tuple[bytes, bytes]) -> bool:
    r1, r2 = unveil_info  # two is better than one, right?
    return commitment == sha256(r1 + message + r2).digest()

def main():
    print("I want to play a game...")
    already_seen = {}
    for _ in range(NUM_ROUNDS):
        com = bytes.fromhex(input("Commitment (hex): "))
        my_choice = choice(["rock", "paper", "scissors"])
        print(f"I choose {my_choice}.")
        your_choice = input("What did you choose? ")
        if your_choice not in {"rock", "paper", "scissors"}:
            print("*Your opponent just staress at you, seeming very confused*")
            return
        unveil_info = tuple(bytes.fromhex(x) for x in input("Proof (hex): ").split())
        if not verify(com, your_choice.encode("ascii"), unveil_info):
            print("Hey, no cheating! Do that again and I will eat all your flags")
            return
        elif my_choice == your_choice:
            print("Sorry, that was a draw. No flag for you")
            return
        elif (my_choice, your_choice) in {
            ("rock", "scissors"),
            ("scissors", "paper"),
            ("paper", "rock"),
        }:
            print("Sorry, you lose. No flag for you")
            return
        elif com in already_seen and already_seen[com] != your_choice:
            print("Something fishy is going on here. What are you doing?")
            return
        already_seen[com] = your_choice
    print(f"... Here is your flag: {environ['FLAG']}")

Protocol per round

1. You send a commitment com (hex).
2. Server picks my_choice uniformly at random and reveals it.
3. You send your_choice.
4. You send the unveil proof (r1, r2) (two hex strings, space-separated).
5. Server accepts only if all hold:
   • com == sha256(r1 + your_choice + r2) — the commitment opens correctly,
   • my_choice != your_choice — not a draw,
   • your_choice beats my_choice — you win the round,
   • the same com was never unveiled to a different choice (already_seen).

To get the flag you must win all 100 rounds.

Win condition

The "you lose" set is {(rock, scissors), (scissors, paper), (paper, rock)} and draws lose too. So to win, your_choice must beat my_choice:

The catch: you commit before seeing my_choice. With a sound commitment scheme you'd be locked into your move and could only win with probability 1/3 per round — (1/3)^100 overall. Hopeless... unless the commitment isn't actually binding.

The Vulnerability — a non-binding commitment

A commitment scheme needs two properties:

• Hiding — the commitment reveals nothing about the message.
• Binding — you can open the commitment to exactly one message.

Look closely at how this one is built:

com = sha256(r1 + message + r2)

The message is sandwiched between two attacker-chosen, arbitrary-length nonces. That's the bug. The unveil step never checks where the message sits or how long the nonces are — it just concatenates the three byte strings and hashes them.

So consider the single byte string:

S = b"rockpaperscissors"

and its commitment com = sha256(S). This one commitment opens to all three moves, because each word appears as a substring and we just choose r1/r2 to be the bytes before/after it:

All three produce the same S, hence the same com. The scheme is completely non-binding for any message contained in the committed string. No hash collision needed — it's a parsing ambiguity.

Quick local proof:

from hashlib import sha256
S = b"rockpaperscissors"
com = sha256(S).digest()
def split(word):
    i = S.index(word)
    return S[:i], S[i+len(word):]
for w in (b"rock", b"paper", b"scissors"):
    r1, r2 = split(w)
    assert com == sha256(r1 + w + r2).digest()
# all pass

Exploitation

The plan for each round:

1. Send com = sha256(S) for a string S that contains all three moves.
2. Read the server's my_choice.
3. Reveal your_choice = beats(my_choice).
4. Send the proof by splitting S around your_choice.

Two details that matter

1. The already_seen check. The server stores already_seen[com] = your_choice and rejects reusing the same com with a different choice. Across rounds the winning move changes (the server is random), so we can't reuse one commitment. Fix: make each round's string unique with a per-round prefix, e.g. S = f"{round}-rockpaperscissors-". Every com is then distinct and maps to exactly one revealed choice, so the check never trips.

2. Empty nonces break the wire format. The server parses the proof with:

tuple(bytes.fromhex(x) for x in input("Proof (hex): ").split())

If r2 is empty, we'd send "<r1hex> " — and "<r1hex> ".split() returns a single element, so r1, r2 = unveil_info raises ValueError: not enough values to unpack. This happens whenever the chosen move sits at the very start or end of S. Fix: pad both ends of the string so no move is ever at an edge:

S = b"0-rockpaperscissors-"
       ^                  ^
       rock has r1=b"0-"  scissors has r2=b"-"   → both nonces always non-empty

(This bit me on the first run — round 4 revealed scissors, which sat at the end of the unpadded "4rockpaperscissors", producing an empty r2 and crashing the server-side unpack.)

Solver

import socket, ssl, sys
from hashlib import sha256

HOST = "smoked-onion-atop-cured-curry-be9q.gpn24.ctf.kitctf.de"
PORT = 443
ROUNDS = 100
BEATS = {"rock": "paper", "paper": "scissors", "scissors": "rock"}  # server -> winning move

# ncat --ssl uses a self-signed cert, so disable verification (CTF endpoint only).
ctx = ssl.create_default_context()
ctx.check_hostname = False
ctx.verify_mode = ssl.CERT_NONE
s = ctx.wrap_socket(socket.create_connection((HOST, PORT)), server_hostname=HOST)

buf = b""
def recv_until(tok):
    global buf
    tok = tok.encode()
    while tok not in buf:
        d = s.recv(4096)
        if not d:
            raise EOFError(buf.decode(errors="replace"))
        buf += d
    i = buf.index(tok) + len(tok)
    out, buf = buf[:i], buf[i:]
    return out

def send_line(x):
    s.sendall((x + "\n").encode())

recv_until("game...")
for rnd in range(ROUNDS):
    recv_until("Commitment (hex): ")
    S = (str(rnd) + "-rockpaperscissors-").encode()   # unique + padded both ends
    send_line(sha256(S).hex())

    recv_until("I choose ")
    my = recv_until(".")[:-1].decode().strip()        # the server's move
    your = BEATS[my]

    recv_until("What did you choose? ")
    send_line(your)

    recv_until("Proof (hex): ")
    i = S.index(your.encode())
    r1, r2 = S[:i], S[i + len(your):]
    send_line(r1.hex() + " " + r2.hex())
    print(f"round {rnd}: they={my} me={your}", file=sys.stderr)

s.settimeout(5)
try:
    while True:
        d = s.recv(4096)
        if not d:
            break
        buf += d
except Exception:
    pass
print(buf.decode(errors="replace"))

Run

$ python solve.py
round 0: they=rock me=paper
round 1: they=rock me=paper
...
round 98: they=rock me=paper
round 99: they=paper me=scissors
How can that be? Well, a deal is a deal. Here is your flag:
GPNCTF{WaIt, 17'5 NOT Ju5T lUCk? N3v3R HAS 83EN.}

Root Cause & Fix

The flaw is treating r1 + message + r2 as if the split into (r1, message, r2) were unique. Concatenation is ambiguous: any committed string containing the message as a substring opens to that message. The scheme is not binding.

A correct hiding+binding commitment uses a single fixed-length randomizer and a fixed structure, e.g.:

com = sha256(nonce + message)        # nonce is fixed length, message has no ambiguity
# verify with the exact same layout; the opener supplies only `nonce`, not a free split

Even simpler, the binding break disappears if the unveil API doesn't let the prover choose two surrounding nonces. The challenge's own comment — "two is better than one, right?" — is the wink: the second nonce is exactly what turns the message into a freely-positionable substring and destroys binding.

The flag says it best: it was never just luck.