Radiation Leak Writeup

README.md

Radiation Leak

The problem gives us a bunch of consecutive leaked tokens generated by the function below. The goal is to find the next token in line. We can see the token generation is an LCG, meaning we can easily use the leaked tokens to recover the internal state (seed, state_1, state_2) of the generator.

seed = random.getrandbits(64 * 8)
mask = (1 << 64) - 1
state_1 = random.getrandbits(64)
state_2 = (state_1 + random.getrandbits(64)) & mask

def generate_token():
    global seed, state_1, state_2, mask
    result = seed & mask
    seed >>= 64
    inc = ((result * state_1 + state_2) ^ seed) & mask
    seed |= inc << (7 * 64)
    return result

Functionally, the seed is a queue of 8 64-bit integers (stored concatenated together with the low 64-bits being the top of the queue). Note that this means that we can already recover the seed (because the leaked tokens map 1 to 1 to these 64-bit integers).

Let state_1 be m (multiplier), and state_2 be c (constant increment). Let s_n be the nth integer in the queue. On call to generate tokens, we calculate s_{n+8} = ((s_n * m + c) ^ s_{n+1}) & mask, then add s_{n+8} to the back of the queue (top 8 bytes of seed), and returning s_n.

From this equation, we can calculate c if we know m. Note that and-ing by (1<<64)-1 is the same as modding by (1<<64).

s_{n+8} = (s_n * m + c) ^ s_{n+1}         % (mask+1)
c       = (s_{n+8} ^ s_{n+1}) - (s_n * m) % (mask+1)

Then, we just need to calculate m. We can do so by constructing a system of equations to cancel out c.

s_{n+8} = (s_n     * m + c) ^ s_{n+1} % (mask+1)
s_{n+9} = (s_{n+1} * m + c) ^ s_{n+2} % (mask+1)

(s_{n+9} ^ s_{n+2}) - (s_{n+8} ^ s_{n+1}) = (s_{n+1} * m + c) - (s_n * m + c) % (mask+1)
                                          = (s_{n+1} - s_n) * m               % (mask+1)

m = (s_{n+9} ^ s_{n+2}) - (s_{n+8} ^ s_{n+1}) / (s_{n+1} - s_n) % (mask+1)

Division is done by calculating the multiplictive inverse in the above finite field.

def crack_unknown_increment(states, modulus, multiplier):
    increment = ((states[8]^states[1]) - states[0]*multiplier) % modulus
    return modulus, multiplier, increment

def crack_unknown_multiplier(states, modulus):
    multiplier = (((states[9]^states[2]) - (states[8]^states[1])) * gmpy2.invert(states[1] - states[0], modulus)) % modulus
    return crack_unknown_increment(states, modulus, multiplier)

Then, we can simply set the LCG PRNG state to the values we calculated and generate the new token.

bip39.txt

See https://github.com/bitcoin/bips/blob/master/bip-0039/english.txt

exploit.py

import random
import gmpy2

seed = random.getrandbits(64 * 8)
mask = (1 << 64) - 1
state_1 = random.getrandbits(64)
state_2 = (state_1 + random.getrandbits(64)) & mask

with open("bip39.txt") as f:
    bip = [i for i in f.read().split("\n") if i]

def generate_token():
    global seed, state_1, state_2, mask
    result = seed & mask # lower 64 bit of mask
    seed >>= 64
    inc = ((result * state_1 + state_2) ^ seed) & mask
    seed |= inc << (7 * 64)
    return result

def convert_to_string(token):
    r = token
    n = []
    for i in range(6):
        n.append(token & 0x7FF)
        token >>= 11
    return "-".join([bip[i] for i in n])

def string_to_token(s):
    n = s.split('-')
    nums = []
    token = 0
    for x in n:
        nums.append(bip.index(x))

    for x in nums[::-1]:
        token |= x
        token <<= 11
    token >>= 11

    return token

# s8 = (s0*m + c)^s1
# c = (s8^s1)-(s0*m)
def crack_unknown_increment(states, modulus, multiplier):
    increment = ((states[8]^states[1]) - states[0]*multiplier) % modulus
    return modulus, multiplier, increment

# s8 = (s0*m + c)^s1
# s9 = (s1*m + c)^s2
# (s9^s2) - (s8^s1) = s1*m - s0*m
# m = (s9^s2 - s8^s1)/(s1-s0)
def crack_unknown_multiplier(states, modulus):
    multiplier = (((states[9]^states[2]) - (states[8]^states[1])) * gmpy2.invert(states[1] - states[0], modulus)) % modulus
    return crack_unknown_increment(states, modulus, multiplier)

# crack settings based on leaked tokens
tokens = []
with open('leaked_tokens.txt') as f:
    for line in f:
        tokens.append(string_to_token(line.strip()))
a,b,c = crack_unknown_multiplier(tokens, mask+1)

# set correct prng internal state
seed = 0 
for i in range(8):
    seed |= tokens[7-i]
    seed <<= 64
seed >>= 64
state_1 = b
state_2 = c

# leak the next correct token
x = [convert_to_string(generate_token()) for i in range(40)]
for s in x:
    print(s)

print('----')
print('next:', x[len(tokens)])
print('----')

leaked_tokens.txt

friend-border-cinnamon-laundry-shoot-chronic
fatigue-photo-result-season-spawn-common
van-service-similar-glory-east-brave
author-sibling-predict-theory-uphold-chuckle
budget-cradle-fatigue-dumb-verb-canvas
gas-token-salute-only-olympic-disorder
size-ankle-island-badge-improve-clean
lawsuit-goat-convince-flash-museum-clay
obtain-ball-force-jelly-odor-chapter
nothing-saddle-van-truck-kangaroo-aunt
number-carbon-film-math-olympic-brief
palm-laugh-garment-rotate-sauce-crop
festival-route-index-shy-trade-awful
fetch-wing-film-travel-wool-catch
cluster-toward-can-prize-lab-churn
travel-mixture-law-wealth-network-blame
valley-radar-brother-uphold-sense-clock
guide-unlock-proud-smooth-cream-abandon
machine-lake-album-amateur-country-control
leg-stuff-around-museum-mouse-deliver
mule-tiny-gym-scatter-leg-about
theme-body-luggage-benefit-mandate-barely
wrestle-match-tree-transfer-spirit-curtain
toilet-exhibit-replace-daring-bubble-cup
this-total-cabin-pill-indicate-crew
birth-isolate-shrug-together-cage-barrel
bar-virus-apology-juice-tell-among
forest-stereo-gadget-core-forest-detect
gather-volume-off-crisp-kick-claw
title-fringe-story-student-bulk-acoustic

token_generator.py

import random

seed = random.getrandbits(64 * 8)
mask = (1 << 64) - 1
state_1 = random.getrandbits(64)
state_2 = (state_1 + random.getrandbits(64)) & mask

with open("bip39.txt") as f:
    bip = [i for i in f.read().split("\n") if i]

def generate_token():
    global seed, state_1, state_2, mask
    result = seed & mask
    seed >>= 64
    inc = ((result * state_1 + state_2) ^ seed) & mask
    seed |= inc << (7 * 64)
    return result

def convert_to_string(token):
    r = token
    n = []
    for i in range(6):
        n.append(token & 0x7FF)
        token >>= 11
    return "-".join([bip[i] for i in n])

print("Tokens for the next month:")
print("\n".join(["  " + convert_to_string(generate_token()) for i in range(0, 31)]))