We implemented a random number generator. We’ve heard that rand()’s 32 bit seeds can be easily cracked, so we stayed on the safe side.
nc lucky.chall.polictf.it 31337
Summary: breaking truncated-to-MSB LCG with top-down bit-by-bit search.
In this challenge we have an LCG generator. We can query it up to 10 times and then we have to predict the correct value more than 100 times. So we have to recover the state from the 10 outputs.
self.a = 0x66e158441b6995 self.b = 0xB self.nbits = 85 # should be enough to prevent bruteforcing def nextint(self): self.state = ((self.a * self.state) + self.b) % (1 << self.nbits) return self.state >> (self.nbits - 32) |
Interesting that the modulus is $2^{85}$ and this is a weak point: the diffusion between different bits is limited. More precisely, high bits will never affect low bits. But the problem is that the LCG outputs $32$ highest bits, and these bits depend both on low and high bits.
At the beginning we have no information about the state at all. After one output we know $32$ bits of the state. So, it is better to start attacking the second output and the effective unknown state size is $53$ bits.
Let’s analyze how the two parts of the state interact. To do this, we represent states and coefficients in the form
$$s=2^{53}s_1+s_0, ~\text{where}~ s_0 < 2^{53}.$$ That is, $s_1$ are the $32$ highest bits of $s$, $s_0$ are the $53$ lowest bits of $s$. Consider the step: $$ \begin{align} s' &= (a \cdot s+b) \mod{2^{85}} = \\ &= \bigg((2^{53}a_1 + a_0) (2^{53}s_1 + s_0) + b\bigg) \mod {2^{85}} \\ &= 2^{53}\bigg(s_1a_0 + s_0a_1 + \bigg\lfloor \frac{s_0a_0+b}{2^{53}} \bigg\rfloor\bigg ) \mod{2^{85}} + (s_0a_0+b) \mod{2^{53}}. \end{align} $$ Note that we observe the high part: $$out = \bigg(s_1a_0 + s_0a_1 + \bigg\lfloor \frac{s_0a_0+b}{2^{53}} \bigg\rfloor \bigg) \mod{2^{32}}.$$ We know $s_1a_0$. Note that in the challenge $a=\mathtt{0x66e158441b6995}$ with $a_1=3, a_0=\mathtt{0x6e158441b6995}$. Due to small $a_1$, the highest bits of $s_0a_1$ do not depend strongly on the lowest bits of $s_0$. Moreover, this is true in the floored fraction as well. To analyze this properly, let's split $s_0$ as $$s_0 = 2^t h+l, ~\text{for}~ l < 2^t ~\text{and some}~ t.$$ From now on we consider everything $\mod{2^{32}}$. The idea is that $h$ are some highest bits of $s_0$. We guess them and then we will try to check our guess. $$out - s_1a_0 = (2^th+l)a_1 + \bigg\lfloor \frac{(2^th+l)a_0+b}{2^{53}} \bigg\rfloor.$$ Note that in the challenge $b=11$ and it very rarely affects the flooring, so we can omit it. We can also split the fraction into two summands and the result will decrease by at most one: $$out - s_1a_0 = 2^th\cdot a_1+l\cdot a_1 + \bigg\lfloor \frac{2^th\cdot a_0}{2^{53}} \bigg\rfloor + \bigg\lfloor \frac{l\cdot a_0}{2^{53}} \bigg\rfloor \stackrel{?}{+} 1.$$ $$out - s_1a_0 - 2^th\cdot a_1 - \bigg\lfloor \frac{2^th\cdot a_0}{2^{53}} \bigg\rfloor = l\cdot a_1 + \bigg\lfloor \frac{l\cdot a_0}{2^{53}} \bigg\rfloor \stackrel{?}{+} 1.$$ Note that $a_0 < 2^{53}$ and also recall that $a_1 = 3$: $$out - s_1a_0 - 2^th\cdot a_1 - \bigg\lfloor \frac{2^th\cdot a_0}{2^{53}} \bigg\rfloor \le l\cdot (a_1+1) < 2^t\cdot4.$$ Once we guess $h$ for small enough $t$, we can compute the left part of this inequality and check the bound. Note that we must be careful with modulo $2^{32}$. Since the right half is smaller than the modulus, we can compute the left half modulo $2^{32}$ and check the inequality.
What $t$ should we choose? Since the left half is bounded by $2^{32}$, we want the right half to be restrictive. For example, $t=29$ has filtering power of around $1/2$. To get to $t=29$ we need to bruteforce $53-29=24$ highest bits of $s_0$. After that the number of candidates will decrease quickly.
With $pypy$ this quite short solution works for ~2 minutes which is longer than allowed by the challenge, but if we try just a few times we have high chances to recover the state in the allowed timespan.
#-*- coding:utf-8 -*- import random class LinearCongruentialGenerator: def __init__(self, a, b, nbits): self.a = a self.b = b self.nbits = nbits self.state = random.randint(0, 1 << nbits) def nextint(self): self.state = ((self.a * self.state) + self.b) % (1 << self.nbits) return self.state >> (self.nbits - 32) def split(x): return ((x >> 53) % 2**32, x % 2**53 ) MASK32 = 2**32-1 MASK53 = 2**53-1 MASK85 = 2**85-1 a = 0x66e158441b6995 b = 0xB a1, a0 = split(a) generator = LinearCongruentialGenerator(a, b, 85) n1 = generator.nextint() SECRET_STATE1 = generator.state n2 = generator.nextint() n3 = generator.nextint() def recurse(h, t): if t == 0: # Final check of the candidate s = (s1 << 53) | h s = (a*s + b) & MASK85 if s >> 53 != n2: return s = (a*s + b) & MASK85 if s >> 53 != n3: return print "CORRECT!", h return h t -= 1 h <<= 1 for bit in xrange(2): h |= bit # delta = val - ( 2**t*h*a1 + 2**t*h*a0/2**53 ) % 2**32 delta = val - ( (h+h+h<<t) + ((h*a0<<t)>>53) ) delta &= MASK32 if delta < 4*2**t: res = recurse(h, t) if res: return res # s1, s0 = split(SECRET_STATE1) s1 = n1 out = n2 val = (out - s1*a0) % 2**32 for top in xrange(2**24): if top & 0xffff == 0: print hex(top) # top = s0 >> 29 s0 = recurse(top, 29) if s0: print "Found solution!", s0 break mygen = LinearCongruentialGenerator(a, b, 85) mygen.state = (s1 << 53) | s0 assert mygen.nextint() == n2 assert mygen.nextint() == n3 for i in xrange(1000): assert mygen.nextint() == generator.nextint() print "Outputs predicted correctly" |
The flag: flag{LCG_1s_m0re_brok3n_th4n_you_th!nk}
UPD: Thanks to Niklas for pointing out that this can be solved straightforwardly by Mathematica.
