COMpetition

Platform: gpn24 | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2024-05-30 | Status: Solved Techniques: non_binding_commitment_attack, per_round_nonce_uniqueness, substring_ambiguity_unveiling

Summary

Task: commit-then-reveal rock-paper-scissors where the commitment is verified as sha256(r1 || message || r2) with both r1 and r2 attacker-controlled; win 100/100 for the flag. Solution: exploit the non-binding commitment — a single preimage X containing 'rockpaperscissors' opens to any of the three moves via different (r1,r2) splits, so commit first then unveil to the winning move; use a per-round nonce so commitments stay unique (already_seen check) and pad both sides so r1/r2 are never empty.

COMpetition — GPN24 (KITCTF)

Description

This week's special: A chance to compete against our esteemed guest, the rock-paper-scissors grand master. If you manage to beat them 100 out of 100 times we will reward you with a flag specially made for you.

A tar.gz was provided with main.py, pyproject.toml, uv.lock, .python-version (Python 3.13, no external dependencies). The pyproject description reads: "A challenge about commitments".

Goal: connect over SSL/TLS and beat the server at rock-paper-scissors 100 times in a row. Each round you must commit to your move before the server reveals its move, then unveil your committed move with a valid proof.

Connection:

ncat --ssl glazed-onion-nestled-in-minced-curry-nlwf.gpn24.ctf.kitctf.de 443

Analysis

Server source (main.py)

 python read-only • copy allowed Copy
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"How can that be? Well, a deal is a deal. Here is your flag: {environ['FLAG']}")

Protocol flow per round

1. Player sends a commitment com (hex) before seeing the server's move.
2. Server picks my_choice via secrets.choice and reveals it.
3. Player sends your_choice (one of rock/paper/scissors).
4. Player sends proof (r1, r2) such that com == sha256(r1 + your_choice + r2).digest().
5. Player must win every round; one draw or loss ends the game. All 100 wins → flag.

Root cause: the commitment scheme is NOT binding

verify checks commitment == sha256(r1 + message + r2), where both r1 and r2 are attacker-controlled and the message is sandwiched between them. The deliberate flaw is signalled by the comment # two is better than one, right? — two randomizers r1, r2.

A secure commitment must be binding: it must be infeasible to open one commitment to two different messages. Here, a single SHA-256 preimage string X that contains all three move words as substrings opens to the same digest for any of those moves, because for each word there is a split X = r1 || word || r2 that reconstructs the identical byte string X.

The classic example: X = b"rockpaperscissors". The same commitment sha256(X) opens to:

• "rock" → r1 = b"", r2 = b"paperscissors"
• "paper" → r1 = b"rock", r2 = b"scissors"
• "scissors" → r1 = b"rockpaper", r2 = b""

So the player commits before seeing the server's move, then unveils to any winning move afterwards. The commit-before-reveal guarantee is worthless.

Winning move table (the move that beats the server's move):

Solution

The core idea: send a commitment of a preimage X that contains rockpaperscissors, see the server's move, then unveil to whichever move beats it by choosing the appropriate (r1, r2) split of X. Two subtleties must be handled.

Subtlety 1 — already_seen requires unique commitments

The server records already_seen[com] = your_choice and rejects a repeated commitment that is unveiled to a different choice:

 python read-only • copy allowed Copy
elif com in already_seen and already_seen[com] != your_choice:
    print("Something fishy is going on here. What are you doing?"); return

If we reused one fixed com across rounds, we would be locked into a single move for that commitment — and would lose whenever the server's move requires a different reply. Solution: embed a per-round nonce in X so com is unique every round, freeing us to pick the winning move each time.

Subtlety 2 — empty r1/r2 crashes the proof parsing

If the winning word lands at the absolute start or end of X, then r1 or r2 is empty. The proof is sent as f"{r1} {r2}", so an empty side yields e.g. " 7061...". On the server, input("Proof (hex): ").split() collapses leading/trailing whitespace and returns only one element, triggering ValueError: not enough values to unpack at r1, r2 = unveil_info. Fix: pad both sides of rockpaperscissors so neither r1 nor r2 is ever empty:

 python read-only • copy allowed Copy
X = b"X" + nonce + b"rockpaperscissors" + b"Y"

Now every move word is strictly interior, so both splits are non-empty hex strings.

Full exploit (solve.py)

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import sys
from hashlib import sha256
from pwn import remote, context

context.log_level = "info"
BEATS = {"rock": "paper", "paper": "scissors", "scissors": "rock"}

def make(n: bytes):
    # pad both sides so r1/r2 are never empty; nonce makes com unique per round
    X = b"X" + n + b"rockpaperscissors" + b"Y"
    return X, sha256(X).digest()

def proof(X: bytes, word: str):
    w = word.encode()
    i = X.find(w)
    return X[:i].hex(), X[i + len(w):].hex()

def main(host, port):
    io = remote(host, int(port), ssl=True)
    io.recvuntil(b"I want to play a game...")
    for rnd in range(100):
        X, com = make(rnd.to_bytes(4, "big"))
        io.recvuntil(b"Commitment (hex): ")
        io.sendline(com.hex().encode())
        io.recvuntil(b"I choose ")
        srv = io.recvuntil(b".", drop=True).decode().strip()
        my = BEATS[srv]
        io.recvuntil(b"What did you choose? ")
        io.sendline(my.encode())
        r1, r2 = proof(X, my)
        io.recvuntil(b"Proof (hex): ")
        io.sendline(f"{r1} {r2}".encode())
        print(f"[+] round {rnd+1}: server={srv}, we play={my}")
    print(io.recvall(timeout=10).decode())

if __name__ == "__main__":
    main(sys.argv[1], sys.argv[2])

Run:

python3 solve.py glazed-onion-nestled-in-minced-curry-nlwf.gpn24.ctf.kitctf.de 443

Result line:

How can that be? Well, a deal is a deal. Here is your flag: GPNCTF{REDACTED}

Lessons Learned / Mitigation

• A secure commitment scheme must be binding: opening one commitment to two different messages must be infeasible. The construction H(r1 || m || r2) with both r1 and r2 attacker-controlled is trivially non-binding whenever the candidate messages can appear as substrings of a single shared preimage (rockpaperscissors).
• The hint "two is better than one, right?" (two randomizers) is the deliberate flaw. A second free randomizer on the other side of the message destroys binding by letting the message slide to any position.
• Mitigation: use a fixed-position randomizer and an unambiguous encoding, e.g. H(r || len(m) || m) (length-prefix prevents the message from being reinterpreted as part of r), or simply H(r || m) with a single fixed-position randomizer — or, better, a vetted commitment construction. Never let the prover control bytes on both sides of the committed value.