Trust Games (lcg2)

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: key_byte_prediction, lcg_state_recovery, lll_reduction, refresh_block_alignment, truncated_lcg_lattice_attack

Summary

Walkthrough of the CUSTOM Crypto Trust Games (lcg2). Task: a 'prove your trust' game where plaintext, AES key and IV are consecutive byte streams from an LCG (a=0x1337deadbeef, b=0xb, m=2^48) that leaks only top 8 bits per state and reseeds every 16 cal

Description

"Let's play a game, Player <id>. If you can encrypt the plaintext that I will give you with my secret key, you will be worthy of my trust and a reward." Connect at socket.cryptohack.org 13396.

On get_a_challenge the server returns a plaintext and IV and expects you to send back AES-CBC(key, IV).encrypt(plaintext) for a secret key. Everything comes from one LCG.

Analysis

 python read-only • copy allowed Copy
class LCG:
    a=0x1337deadbeef; b=0xb; m=2**48
    def get_random_bits(self, k):
        if self.counter == 16: self.refresh()      # reseed every 16 calls
        self.counter += 1
        self.next_state()                           # state = (a*state+b) % 2^48
        return self.state >> (48 - k)               # top k bits of the NEW state
    # get_random_bytes(n) = n successive get_random_bits(8) (top byte of each state)

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Two facts make this breakable:

1. Small modulus + top-bit leak. m = 2^48 and we see the top 8 bits of every state, so each state hides only 40 low bits. With ≥6 byte samples from one block a truncated-LCG lattice pins the 48-bit seed exactly.
2. Refresh blocks. Every 16 calls the LCG reseeds with fresh urandom(6), so the output is partitioned into independent blocks of 16 states. State p within a block is state_p = a^p·seed + C_p (mod 2^48) with C_p = b·(a^{p-1}+…+a+1). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The call/refresh alignment (the crux)

The constructor burns calls (plaintext, key, IV, and the banner's get_random_bytes(8)), leaving the counter at 8. On get_a_challenge the next three 16-byte draws line up against the block boundaries like this:

plaintext = Block3[9..16] + Block4[1..8]      (we SEE all 16 plaintext bytes)
key       = Block4[9..16] + Block5[1..8]      (HIDDEN — must predict)
IV        = Block5[9..16] + Block6[1..8]      (we SEE all 16 IV bytes)

So the hidden key halves live in Block4 and Block5, the same blocks where leaked bytes appear: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

• plaintext[8:16] = top bytes of Block4 positions 1..8 → recover Block4's seed → predict key[0:8] = Block4 positions 9..16.
• IV[0:8] = top bytes of Block5 positions 9..16 → recover Block5's seed → predict key[8:16] = Block5 positions 1..8.

Truncated-LCG lattice

For samples (p_i, y_i) (y_i = top byte of state at position p_i, hidden part e_i ∈ [0,H), H=2^40), write e_i = a^{d_i}·e_0 + K_i (mod m) relative to the first sample, and reduce a lattice whose short vector recovers the e_i: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
# columns: a^{d_i} relations, m on the diagonals, the K_i offsets, and a weight W=H
B = IntegerMatrix(n+1, n+1)
B[0,0]=1
for j in range(1,n): B[0,j]=int(a_ds[j])
for i in range(1,n): B[i,i]=int(m)
for j in range(1,n): B[n,j]=int(Ks[j])
B[n,n]=int(W)
Br = LLL.reduction(B)   # short row with |row[n]|==W yields the hidden lows e_i -> seed

8 samples per block (overdetermined for 40 hidden bits) makes recovery deterministic.

Solution

 python read-only • copy allowed Copy
from recover import recover_seed, state_at, HID   # HID=40
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def solve_key(plaintext, IV):
    # Block4: plaintext[8:16] = top8 of positions 1..8 ; key[0:8] = positions 9..16
    seed4 = recover_seed([(p, plaintext[8+(p-1)]) for p in range(1,9)])
    key0  = bytes(state_at(seed4,p)>>HID for p in range(9,17))
    # Block5: IV[0:8] = top8 of positions 9..16 ; key[8:16] = positions 1..8
    seed5 = recover_seed([(p, IV[p-9]) for p in range(9,17)])
    key1  = bytes(state_at(seed5,p)>>HID for p in range(1,9))
    return key0 + key1

# one get_a_challenge call suffices:
key = solve_key(pt, iv)
ct  = AES.new(key, AES.MODE_CBC, iv).encrypt(pt)
send({"option":"validate", "ciphertext": ct.hex()})   # -> flag

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The recovery routine self-tests 100/100 offline before connecting (both Block4 and Block5 prediction directions), so a single live get_a_challenge wins. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering key_byte_prediction, lcg_state_recovery, lll_reduction, refresh_block_alignment, truncated_lcg_lattice_attack was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-06-24 • CUSTOM • Trust Games (lcg2) • Difficulty: Medium