For the challenge, we need to gain enough money (self.dollars >= 130), we should obtain the flag. Observing the PRNG, we can see that the PRNG is a Linear Congruential Generator, with properly randomized parameters.
Let’s first discuss how to break the LCG. Denote the multiplier mul as $M$, increment inc as $I$, modulo as $N$. We can easily retrieve $M, I$ after obtaining three numbers from the LCG, denoted by $A, B, C$. Indeed, we have:
$$
B = M * A + I \mod N
$$
$$
C = M * B + I \mod N
$$
$$
C - B = M * (B - A) \mod N
$$
$$
M = (C - B) * (B - A) ^ {-1} \mod N
$$
$M$ should be retrieved, as we know $A, B, C$. With $M$ figured out, $I$ can be retrieved by $I = B - M * A \mod N$
Now, the task is to retrieve 3 number from the LCG.
The “shuffle” is done using the rebase function, which essentially converts the state into a Base-52 representation. The cards are drawn with replacement. From local testing, we observe that every shuffled deck should have 11 cards in it, given the division of 52 every step, and 60 bits of randomly generated state.
Hence, we can recover a single RNG state by seeing all hands in a shuffle and interpreting them as base 52. Three states will take 33 tries (plus 1 for retrieving the last card of the third state). However, as we do not have any information on the next RNG state when we are in the process of retrieving the three states, we have to do the choices randomly, or based on some heuristics.
For a better guarantee that we will retrieve enough cards to reconstruct the three RNG states, I use the simple heuristics of picking the choice where there are more possibilities. This means, when we are holding “Four of Spades”, the choice will be “higher”, as there are more cards with higher values than “Four of Spades” than cards with lower values. Doing this keeps the casino balance above 0 after 34 rounds, which will provide enough information to retrieve three states.
Other than that, the challenge is just a matter of writing everything out and squash bugs. I would recommend local tests, for full information of the PRNG states and the shuffled deck, which would be very useful in debugging.
Python Implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
from functools import total_ordering
from Crypto.Random import random
from pwn import *
import json
io = remote('socket.cryptohack.org', 13383)
VALUES = ['Ace', 'Two', 'Three', 'Four', 'Five', 'Six',
'Seven', 'Eight', 'Nine', 'Ten', 'Jack', 'Queen', 'King']
SUITS = ['Clubs', 'Hearts', 'Diamonds', 'Spades']
@total_ordering
class Card:
def __init__(self, value, suit):
self.value = value
self.suit = suit
def __str__(self):
return f"{self.value} of {self.suit}"
def __eq__(self, other):
return self.value == other.value
def __gt__(self, other):
return VALUES.index(self.value) > VALUES.index(other.value)
# Perform a smarter (probabilistic) pick, basically pick the option where
# there are more possiblities
def smart_pick(hand, deck):
hand_idx = deck.index(hand)
value = hand_idx % 13
if value - 0 > 12 - value:
return 'l'
else:
return 'h'
# Reconstruct the RNG state from the value of the card returned
def reconstruct_rng_state(card_indexes):
state = 0
indexes = card_indexes
for index in indexes:
state *= 52
state += index
return state
# Collect the value of cards
def collect_cards():
deck = [Card(value, suit) for suit in SUITS for value in VALUES]
deck = list(map(lambda x: str(x), deck)) # string representation of deck
shuffle_states = []
current_shuffle = []
hand = None
for _ in range(34): # 34 because there is always 11 shuffles (in local testing)
if hand:
# If this is not the first pick, then do a smart pick
pick = smart_pick(hand, deck)
else:
# Otherwise just randomly pick
pick = random.choice(['l', 'h'])
# Result of the pick
if _ == 0:
result = json.loads(io.recvline().decode())
else:
io.sendline(json.dumps({'choice': pick}).encode())
result = json.loads(io.recvline().decode())
hand = result['hand']
msg = result['msg']
# If the deck is reshuffled, then append the current shuffle to the shuffle states
if "reshuffle" in msg:
if 'Welcome' not in msg:
current_shuffle.append(deck.index(hand))
shuffle_states.append(current_shuffle)
current_shuffle = []
continue
current_shuffle.append(deck.index(hand))
# Only three shuffled decks are needed
if len(shuffle_states) == 3:
return shuffle_states
# Recover the mul, inc of the PRNG
def recover_mul_inc(shuffle_states):
a, b, c = list(map(lambda x: reconstruct_rng_state(x), shuffle_states))
mod = 2 ** 61 - 1
temp1 = (c - b) % mod
temp2 = pow(b - a, -1, mod)
recover_mul = (temp1 * temp2) % mod
recover_inc = (b - recover_mul * a) % mod
return (recover_mul, recover_inc, c)
# Generate the value of the RNG
def rng(mul, inc, state):
mod = 2 ** 61 - 1
return (mul * state + inc) % mod
# Generate the shuffled deck
def rebase(n, b=52):
if n < b:
return [n]
else:
return [n % b] + rebase(n // b, b)
deck = [Card(value, suit) for suit in SUITS for value in VALUES]
deck = list(map(lambda x: str(x), deck)) # string representation of deck
# Recover the mul, inc from the 3 numbers retrieved from the cards
mul, inc, state = recover_mul_inc(collect_cards())
next_state = rng(mul, inc, state)
shuffled_deck = rebase(next_state)
current_card = shuffled_deck.pop()
for i in range(200 - 34):
current_card_value = current_card % 13
next_card = shuffled_deck.pop()
next_card_value = next_card % 13
print("Current card:", deck[current_card], end="")
print(" Next card:", deck[next_card])
if next_card_value < current_card_value:
io.sendline(json.dumps({'choice': 'l'}).encode())
else:
io.sendline(json.dumps({'choice': 'h'}).encode())
print(io.recvline().decode())
current_card = next_card
if len(shuffled_deck) == 0:
state = next_state
next_state = rng(mul, inc, next_state)
shuffled_deck = rebase(next_state)
io.sendline(json.dumps({'choice': 'l'}).encode())
io.interactive()
|