CSCG 2023 - Casino
Last modification on
Challenge
Making decisions is hard. Even for smart people like Diffie or Hellman. Maybe you can still win the lottery somehow 🤷.
main.py
from flag import FLAG
import random
rng = random.SystemRandom()
# Secure group from RFC 3526
prime = int("""
FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
15728E5A 8AACAA68 FFFFFFFF FFFFFFFF""".replace('\n', '').replace(' ', ''),
16)
generator = 11
def play():
challenge = rng.randint(0, 1)
a, b, z = rng.randint(1, prime-1), rng.randint(1, prime-1), rng.randint(1, prime-1)
A, B, C, Z = pow(generator, a, prime), pow(generator, b, prime), pow(generator, a*b, prime), pow(generator, z, prime)
print(f"""Guess the random bit I have coosen!
Commitment: {A}, {B}, {C if challenge == 1 else Z}""")
guess = int(input("> ").strip())
if guess == challenge:
print(f"""Correct! My challenge was {challenge}
Proof: {a}, {b}""")
return 1
else:
print(f"""Wrong! My challenge was {challenge}
Proof: {a}, {b}""")
return -1
def main():
balance = 100
print(f"""Welcome to the first casino with fully provable randomness using cryptographically hard problems!
It uses the Decisional Diffie-Hellman Problem to provide a commitment, which can be verified by the player after the answer has been given.
Your balance is {balance} €.
Aquire 200 € to get one of our premium flags
""")
while True:
balance += play()
if balance <= 0:
exit(0)
if balance >= 200:
print(FLAG)
exit(0)
print(f"Your current balance is {balance} €\n")
if __name__ == '__main__':
main()
Overview
We are presented with the source code of a Python servlet casino
in which users are presented with 3 cyclic group elements at each turn.
Depending on the value of a hidden decision bit, the third element output
is either produced as pow(g, a * b, n) from the first two elements
pow(g, a, n) and pow(g, b, n), or randomly generated.
Guessing the hidden decision bit correctly from the returned values awards the user a single unit of balance. Guessing incorrectly deducts a unit of balance. The goal is to increase the user balance from 100 to 200, at which point the flag is returned by the service.
Analysis
For some groups, it is non-trivial to distinguish pow(g, a * b, n) from
a random element in the cyclic group without knowing a and b. This
is known as the
Decisional Diffie-Hellman assumption.
DDH does not hold, however,
for multiplicative groups where n is prime, because the
Legendre Symbol may be
used to determine the parity of a and b, and such the parity of
a * b.
The Legendre symbol of an integer k in respect to an odd prime
number p can be calculated efficiently as pow(k, p // 2, p) and results
in 1 when the quadratic residue
of k in respect to n is non-zero, p - 1 when it is zero and 0 when k
is a multiple of n. This gives insight to the parity of the exponent,
since an element of a cyclic group pow(g, c, n) with an even exponent
c = 2 * c' may be expressed as a quadratic residue pow(pow(g, c', n), 2, n),
while an element with an odd exponent can not.
Solution
Comparing the Legendre symbol of the third element with the parity of a * b,
we may determine with a probability greater than 50% whether it corresponds
to pow(g, a * b, n) or was randomly generated: With 50% probability, the
third element is pow(g, a * b, n), and the prediction based on parity
is correct. In every other case, the third element is randomly generated
and its Legendre symbol matches the parity of pow(g, a * b, n) with
50% probability. This results in a total 75% probability that a prediction
based on the Legendre symbol is correct, enough bias to quickly net 100 wins
against the house.
solve.py
from pwn import *
from sympy.ntheory import legendre_symbol
import re
prime = int("""
FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
15728E5A 8AACAA68 FFFFFFFF FFFFFFFF""".replace('\n', '').replace(' ', ''),
16)
generator = 11
io = process("python3 main.py".split())
try:
while True:
out = io.readuntil(b"Commitment: ", timeout=1)
print(re.search(b"balance is ([0-9]+)", out).group(1))
A,B,U = [int(v.strip()) for v in io.readline().split(b",")]
a_even = legendre_symbol(A, prime) == -1
b_even = legendre_symbol(B, prime) == -1
u_even = legendre_symbol(U, prime) == -1
if u_even == a_even * b_even:
io.sendline(b"1")
else:
io.sendline(b"0")
except Exception as e:
print(e)
print(io.readall(timeout=1).decode().split("\n")[-1])
Addendum
Due to the properties of the
random walk
it is possible to win enough games predicting the same thing every round
to retrieve the flag. The expected number of steps until the random walk
first hits 0 or 200 may be calculated as the distance squared (10000 turns),
since the expected distance traveled after n steps is sqrt(n). This can be
optimized by restarting the random walk as soon as the balance falls below 100,
which may be viewed as a forced step in the positive direction,
effectively cutting the expected number of steps in half to 5000
(not counting the actual steps crossing over).