Lo-Hi Card Game

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$$M$, increment inc as $I$$I$, modulo as $N$$N$. We can easily retrieve $M,I$$M, I$ after obtaining three numbers from the LCG, denoted by $A,B,C$$A, B, C$. Indeed, we have:

$M$$M$ should be retrieved, as we know $A,B,C$$A, B, C$. With $M$$M$ figured out, $I$$I$ can be retrieved by $I=B-M\ast A\mathrm{mod}N$$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:

xxxxxxxxxx
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()