## poker? i barely even- (mental poker)

> Let's play some mental poker.

it's another crypto challenge !

let's look at the source

```python
class PRNG:
	def __init__(self, seed = int(os.urandom(8).hex(),16)):
		self.seed = seed
		self.state = [self.seed]
		self.index = 64
		for i in range(63):
			self.state.append((3 * (self.state[i] ^ (self.state[i-1] >> 4)) + i+1)%64)
	
	def __str__(self):
		return f"{self.state}"
	
	def getnum(self):
		if self.index >= 64:
			for i in range(64):
				y = (self.state[i] & 0x20) + (self.state[(i+1)%64] & 0x1f)
				val = y >> 1
				val = val ^ self.state[(i+42)%64]
				if y & 1:
					val = val ^ 37
				self.state[i] = val
			self.index = 0
		seed = self.state[self.index]
		self.index += 1
		return (seed*15 + 17)%(2**6)
```

this implements a Mersenne Twister PRNG, seeded with `os.urandom`. the output is limited to 6 bits,
and seemingly it uses 64 bits of randomness to initialize the PRNG

then we have a fairly uninteresting implementation of poker which i'm going to skip over. there
isn't anything particularly wrong with it

```python
def shuffle(deck):
	new_deck = []
	for i in range(len(deck)):
		x = rng.getnum()
		if deck[x] not in new_deck:
			new_deck.append(deck[x])
		elif deck[i] not in new_deck:
			new_deck.append(deck[i])
		else:
			for card in deck:
				if card not in new_deck:
					new_deck.append(card)
					break
	return new_deck
```

this shuffles the deck based on the PRNG above

ok and now for the weird stuff

```python
p = getPrime(300)
q = getPrime(300)
phi = (p-1)*(q-1)
N = p*q
print(f"Let's play some mental poker!\nIf you win 10 consecutive times, I'll give you a prize!\nHere are the primes we will use to generate our RSA public and private exponents --> {p}, {q}")
```

we get an RSA *private key* just like, for free. then (not shown here), we're prompted for a public
and private exponent for RSA, and the computer also comes up with its own public and private
exponent like this

```python
while computer_e < 2 or computer_d < 1:
    e_array = []
    for _ in range(6):
        e_array.append(str(rng.getnum()))
    computer_e = int(''.join(e_array))
    if gcd(computer_e, phi) == 1:
        computer_d = pow(computer_e,-1,phi)
```

interestingly, the card shuffling for the first round is done before the computer's exponents are
generated

then, on each round, we get an encrypted deck -- that's encrypted with our public exponent as well
as the computer's

```python
enc_deck = []
for card in deck:
    enc_deck.append(pow(pow(bytes_to_long(str(card).encode()),computer_e,N),player_e,N))
assert len(set(enc_deck)) == len(deck_str)
print(f"Here is the shuffled encrypted deck --> {enc_deck}")
```

we are tasked with shuffling the deck and returning it, still in encrypted form. then, the computer
decrypts the deck and runs the poker algorithm to determine a winner

if you win 10 rounds, you get the (encrypted) flag

### the bug

the flaw in this happens in the PRNG. since this is used to generate the computer's private
exponent, if we can guess PRNG outputs then we can recover enough info to be able to decrypt the
deck fully

but first, there's a kind of pointless but convenient bug in the way your exponent is inputted. the
only checks done on your input are

```python
if gcd(player_e, phi) == 1:
    # accept

if (player_e*player_d)%phi == 1:
    # accept
```

therefore, we can provide a `player_e` and `player_d` that are both `1`. this makes the logic to
decrypt the cards slightly easier

the issue with the PRNG is that despite at first glance looking like it is seeded with 8 bytes of
`urandom`, it's actually only seeded with 10 real bits of randomness

in the constructor, the state array is initialized with

```python
for i in range(63):
    self.state.append((3 * (self.state[i] ^ (self.state[i-1] >> 4)) + i+1)%64)
```

`state[0]` initially contains the full seed, but according to this code we can see only the lower 6
bits (due to the modulo) combined with 4 more bits (due to the bit shift) actually influence the
values of the other items in the state array. then, when the first call to `getnum` happens, the
twist operation is immediately performed, which normalizes all the values to be modulo 64, so
`state[0]` also ends up only dependent on the lower 6 bits of the seed value

we can verify this for ourselves

```python
[ins] In [1]: from server import PRNG

[ins] In [2]: PRNG(0x1337c00 | 420).getnum()
Out[2]: 35

[nav] In [3]: PRNG(420).getnum()
Out[3]: 35
```

so basically, we have an extremely bruteforceable search space of 10 bits. that's a lot better than
64!!

### it's pokin' time / poked all over the place

given some copying and pasting of server code as well as importing it directly from the server
module, the solution script can basically simulate the same thing the server is doing each round

```python
from server import PRNG, Card, card_str_to_Card, determine_winner

def sim_round(deck, rng, phi, computer_e, computer_d):
    deck = shuffle(rng, deck)
    print("local hacks 1", rng.seed, rng.index, rng.state)
    while computer_e < 2 or computer_d < 1:
        e_array = []
        for _ in range(6):
            e_array.append(str(rng.getnum()))
        computer_e = int(''.join(e_array))
        if gcd(computer_e, phi) == 1:
            computer_d = pow(computer_e,-1,phi)

    return computer_e, computer_d, deck

def shuffle(rng, deck):
    new_deck = []
    for i in range(len(deck)):
        x = rng.getnum()
        if deck[x] not in new_deck:
            new_deck.append(deck[x])
        elif deck[i] not in new_deck:
            new_deck.append(deck[i])
        else:
            for card in deck:
                if card not in new_deck:
                    new_deck.append(card)
                    break
    return new_deck
```

next, we need to generate the deck

```python
deck = []
deck_str = []
for suit in ["Spades", "Hearts", "Diamonds", "Clubs"]:
    for i in range(16):
        deck.append(Card(suit, i))
        deck_str.append(str(deck[-1]))
deck_str = set(deck_str)

server_deck = list(deck)
```

`server_deck` will hold the copy of the deck that we think the server currently holds

we initialize the game by receiving `p` and `q` and sending `player_e` and `player_d`

```python
r = remote("crypto.csaw.io", 5001)

r.recvuntil(b"Here are")
r.recvuntil(b"--> ")

p, q = r.recvline().decode().strip().split(", ")
p = int(p)
q = int(q)
phi = (p-1)*(q-1)
N = p*q

print("p=", p)
print("q=", q)

player_e = 1
player_d = 1

print("player_e=", player_e)
print("player_d=", player_d)

r.recvuntil(b">>")
r.sendline(str(player_e).encode())
r.recvuntil(b">>")
r.sendline(str(player_d).encode())
```

next, we get the deck for the first round

```python
r.recvuntil(b"***")
print(r.recvuntil(b"--> "))
deck = r.recvline().strip().decode()
deck = ast.literal_eval(deck)
```

now, we do the brute force to guess what the server's PRNG was seeded with. this is done over the 10
bits of seed search space, and the offset to the beginning of the PRNG outputs that are used to
generate the exponent

```python
test_item = deck[0]
found_seed = None
for seed in tqdm.trange(2**10):
    prng = PRNG(seed)
    rand_values = []
    for i in range(256):
        rand_values.append(prng.getnum())

    found = False

    for offset in range(249):
        e_array = [str(x) for x in rand_values[offset:offset+6]]
        computer_e = int(''.join(e_array))
        if gcd(computer_e, phi) != 1:
            continue
        computer_d = pow(computer_e, -1, phi)

        test_card = long_to_bytes(pow(test_item, computer_d, N)).decode('iso-8859-1')
        if test_card in deck_str:
            print("found seed", test_card, seed)
            found = True
            found_seed = seed
            break

    if found:
        break
```

now we just play the game, simulating the server's steps as we go and decrypting the cards we
receive using the recovered keys

```python
prng = PRNG(found_seed)
computer_e, computer_d = -1, 0

for rndnum in range(10):
    if rndnum > 0:
        print(r.recvuntil(b"***"))
        roundline = r.recvline()
        print("roundline", roundline)
        print(r.recvuntil(b"--> "))
        deck = r.recvline().strip().decode()
        deck = ast.literal_eval(deck)
        # print("recv deck", deck)

    computer_e, computer_d, server_deck = sim_round(server_deck, prng, phi, computer_e, computer_d)
    print(computer_e, computer_d, prng.seed, prng.index, prng.state)

    dec_cards = []
    for enc_card in deck:
        dec_card = long_to_bytes(pow(enc_card, computer_d, N)).decode()
        dec_cards.append(card_str_to_Card(dec_card))

    print([str(c) for c in dec_cards])
    print([str(c) for c in server_deck])
```

since i don't actually know how to make a computer play poker, we simply ask the server functions
whether a deck would be favorable for us, and keep shuffling until it is

(i love some good ctf code cheese)

```python
    while True:
        random.shuffle(dec_cards)
        computer_cards, player_cards = dec_cards[0:5], dec_cards[5:10]
        computer_winner, player_winner = determine_winner(computer_cards, player_cards)
        if player_winner and not computer_winner:
            break
```

encrypt with the computer exponent and send our cooked deck order to the server

```python
    server_deck = list(dec_cards)

    enc_deck = []
    for card in dec_cards:
        enc_deck.append(pow(bytes_to_long(str(card).encode()),computer_e,N))

    for c in enc_deck:
        r.recvuntil(b">> ")
        r.sendline(str(c).encode())
```

and after 10 rounds we should have the flag, which we can decrypt with the same computer exponent as
we've been using

```python
r.recvuntil(b"HAHAHA")
r.recvline()

val = ast.literal_eval(r.recvline().decode())
print(long_to_bytes(pow(bytes_to_long(val),computer_d,N)))
```

let's run this locally,

```bash
ncat --exec "/usr/bin/python server.py" -lp 1337 &

python3 exploit.py

[+] Opening connection to localhost on port 1337: Done
p= 1272817120605235218138374468827494843305725876454046855144283728239720564668615378794696017
q= 1119723139502382006362751135685189913928207952277558814504020165396321544235726326572905597
player_e= 1
player_d= 1
roundline b'******* Round 1, current streak is 0 **********\n'
b'Here is the shuffled encrypted deck --> '
 28%|██████████████████                                               | 284/1024 [00:24<01:05, 11.37it/s]found seed One of Clubs 284
 28%|██████████████████                                               | 284/1024 [00:24<01:04, 11.43it/s]
[... lots of spam ...]
My hand is Seven of Hearts, Six of Diamonds, Four of Clubs, Two of Clubs, Zero of Clubs    -->    I have a High card
Your hand is Joker of Hearts, Ace of Diamonds, Ten of Clubs, Nine of Spades, Six of Spades    -->    You have a High card
b'csawctf{test_test_test_test}\n'
[*] Closed connection to localhost port 1337
```

full attack script:
<https://git.lain.faith/haskal/writeups/raw/branch/main/2023/csawq/attack_poker.py>