372 lines
11 KiB
Markdown
372 lines
11 KiB
Markdown
|
## 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>
|