2023-04-23-CSCG2023-casino.md

Casino

Category: Crypto

Difficulty: Medium

Hint: Making decisions is hard. Even for smart people like Diffie or Hellman. Maybe you can still win the lottery somehow 🤷.

Challenge overview

It is a casino game: The player starts with 100 Euro. Each turn the player is given three numbers and needs to guess a secret bit. If the player guesses correctly they gain 1 Euro, otherwise they lose 1 Euro. The goal of the game is to get 200 Euro to receive the flag.

$p$ is a 2048-bit prime. $a,b,z$ are random values between $1$ and $p-1$ Each turn a secret bit $s$ is chosen.

If $s = 1$, the game returns the following values:

$11^{a} \mod p, 11^{b} \mod p, 11^{a\cdot b} \mod p$

else it returns:

$11^{a} \mod p, 11^{b} \mod p, 11^{z} \mod p$

Solution

If I could calculate $11^{a\cdot b} \mod p$ from $11^{a} \mod p$ and $11^{b} \mod p$, I would be able to break the Diffie-Hellman protocol and break most of modern encryption. According to documentation the random generator rng = random.SystemRandom() "uses the os.urandom() function for generating random numbers ". As far as I know os.urandom is cryptographically secure and unpredictable.

I conclude that the only way is to determine whether we have one or two random numbers our exponent.

1. The product of two random numbers has a $75%$ chance to be even. A random number only has a $50%$ chance to be even.
2. A quadratic residue is $a$, in non-scientific terms, a number with a square root modulo $p$. There exists an integer x such that: $x \cdot x \mod p = a$
3. Since 11 is a generator, 11 is a non-quadratic residue. Therefore $11^{a}$ can only be a quadratic residue, if a is even.
4. With the legendre symbol function, we can easily determine whether a number is a quadatic residue. The function is simple:

def is_square(num):
    """Using Legendre Symbol to determine if number is square residue"""
    return pow(num, (prime-1)//2, prime) == 1

5. If the challenge sends a quadratic residue, it's more likely it was a product of two numbers. Therefore we guess $1$ else we guess $0$. This gives us an advantage and we can get the flag.

Solution code

from pwn import *
import re
def get_balance(out):
    return int(re.findall(rb'balance is (\d+)', out)[-1])
prime = 32317006071311007300338913926423828248817941241140239112842009751400741706634354222619689417363569347117901737909704191754605873209195028853758986185622153212175412514901774520270235796078236248884246189477587641105928646099411723245426622522193230540919037680524235519125679715870117001058055877651038861847280257976054903569732561526167081339361799541336476559160368317896729073178384589680639671900977202194168647225871031411336429319536193471636533209717077448227988588565369208645296636077250268955505928362751121174096972998068410554359584866583291642136218231078990999448652468262416972035911852507045361090559
def is_square(num):
    """Using Legendre Symbol to determine if number is square residue"""
    return pow(num, (prime-1)//2, prime) == 1

#io = process(["python3", "casino.py"])
io = remote("afbc4da85508b5272564bc42-casino.challenge.master.cscg.live", 31337, ssl = True)
while True:
    try:
        io.recvuntil(b'Your')
    except EOFError:
        break
    balance = get_balance(io.recvline())
    print(balance)
    io.recvuntil(b'Commitment:')
    C = int(io.recvline().split(b",")[-1])

    if is_square(C):
    # More likely that we have A*B, since they are more likely to be square
        io.sendline(b'1')
    else:
        io.sendline(b'0')

io.interactive()

Flag: CSCG{I_should_have_used_prime_order_groups_instead}