11 KiB
poker? i barely even- (mental poker)
Let's play some mental poker.
it's another crypto challenge !
let's look at the source
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
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
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
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
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
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
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
[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
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
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
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
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
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
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)
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
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
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,
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