Try   HackMD

janken vs yoshiking - zer0pts CTF 2021

tags: zer0pts CTF 2021 crypto

overview

You should beat yoshiking at the rock-paper-scissors over 100 times without defeat. He decides his hand and give us its commitment before you input your hand. The commitment is encrypted by ElGamal encryption scheme.

import random import signal from flag import flag from Crypto.Util.number import getStrongPrime, inverse HANDNAMES = { 1: "Rock", 2: "Scissors", 3: "Paper" } def commit(m, key): (g, p), (x, _) = key r = random.randint(2, p-1) c1 = pow(g, r, p) c2 = m * pow(g, r*x, p) % p return (c1, c2) def decrypt(c, key): c1, c2 = c _, (x, p)= key m = c2 * inverse(pow(c1, x, p), p) % p return m def keygen(size): p = getStrongPrime(size) g = random.randint(2, p-1) x = random.randint(2, p-1) return (g, p), (x, p) signal.alarm(3600) key = keygen(1024) (g, p), _ = key print("[yoshiking]: Hello! Let's play Janken(RPS)") print("[yoshiking]: Here is g: {}, and p: {}".format(g, p)) round = 0 wins = 0 while True: round += 1 print("[system]: ROUND {}".format(round)) yoshiking_hand = random.randint(1, 3) c = commit(yoshiking_hand, key) print("[yoshiking]: my commitment is={}".format(c)) hand = input("[system]: your hand(1-3): ") print("") try: hand = int(hand) if not (1 <= hand <= 3): raise ValueError() except ValueError: print("[yoshiking]: Ohhhhhhhhhhhhhhhh no! :(") exit() yoshiking_hand = decrypt(c, key) print("[yoshiking]: My hand is ... {}".format(HANDNAMES[yoshiking_hand])) print("[yoshiking]: Your hand is ... {}".format(HANDNAMES[hand])) result = (yoshiking_hand - hand + 3) % 3 if result == 0: print("[yoshiking]: Draw, draw, draw!!!") elif result == 1: print("[yoshiking]: Yo! You win!!! Ho!") wins += 1 print("[system]: wins: {}".format(wins)) if wins >= 100: break elif result == 2: print("[yoshiking]: Ahahahaha! I'm the winnnnnnner!!!!") print("[yoshiking]: You, good loser!") print("[system]: you can check that yoshiking doesn't cheat") print("[system]: here's the private key: {}".format(key[1][0])) exit() print("[yoshiking]: Wow! You are the king of roshambo!") print("[yoshiking]: suge- flag ageru") print(flag)

solution

It has better to focus on that the plaintext-space is quite small: 1 or 2 or 3. If we could see such like that the yoshiking's hand is even or not, or yoshiking's hand is quadratic residue or not.

The commitment is

(C1,C2)=(gx,mgxr)modp. When we assume
gxr
is quadratic residue,
C2
is quadratic residue when
m
is quadratic residue and
C2
is quadratic non-residue when
m
is quadratic non-residue.

1 is always quadratic residue. Weather 2, 3 are quadratic residue or not is decided by

p. For example, if we find a good
p
such that
2,3
are quadratic non-residue, we can distinguish yoshiking's hand is 1 or otherwise by his commitment.

Thus, we can choose our hand adaptively in response to yoshiking's hand. Then we don't lose against yoshiking.

exploit

from ptrlib import Socket import random import os HOST = os.getenv("HOST", "localhost") PORT = os.getenv("PORT", "9999") def legendre_symbol(a, p): ls = pow(a, (p - 1)//2, p) if ls == p - 1: return -1 return ls while True: sock = Socket(HOST, int(PORT)) g, p = sock.recvregex("g: ([0-9]+), and p: ([0-9]+)") g, p = int(g), int(p) # check parameter try: assert legendre_symbol(1, p) == 1 assert legendre_symbol(2, p) != 1 assert legendre_symbol(3, p) != 1 for _ in range(100): m = random.randint(1, 3) c = m * pow(g, random.randint(2, p-1), p) % p assert legendre_symbol(m, p) == legendre_symbol(c, p) except AssertionError: sock.close() continue break while True: c1, c2 = eval(sock.recvlineafter("=")) qr = legendre_symbol(c2, p) if qr == 1: sock.sendlineafter("(1-3): ", "3") else: sock.sendlineafter("(1-3): ", "2") sock.recvline() sock.recvline() sock.recvline() result = sock.recvline().decode() if "draw" in result: pass elif "ahaha" in result: print("[-] something wrong") exit() elif "win" in result: wins = int(sock.recvlineafter("wins: ")) print("wins: {}".format(wins)) if wins >= 100: break print(sock.recvuntil("}").decode())