This is a short snippet to solve the LCG on Polictf’17. The basic idea is to reduce the problem 
The basic idea is to view the problem as the latter and correct the discrepancies (
then these values contain the implicit discrepancies. By performing correction of the values (subtracting 
So, now we can use LLL to solve the simpler problem. Once a solution is found, we use the discrepancies to correct it to the case
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 break_lcg(a,b,p,i,j,outputs):
deltas = [b % p, (a*b + b) % p, (a^2*b + a*b + b) % p, (a^3*b + a^2*b + a*b + b) % p]
Y = [((val << (i - j)) ) for val, delta in zip(outputs, deltas)]
L = matrix([
[p, 0, 0, 0 ],
[a^1, -1, 0, 0 ],
[a^2, 0, -1, 0 ],
[a^3, 0, 0, -1]
])
B = L.LLL()
Y = vector([x - y for x, y in zip(Y, deltas)])
target = vector([ round(RR(w) / p) * p - w for w in B * vector(Y) ])
states = list(B.solve_right(target))
return [x + y + z for x, y, z in zip(Y, states, deltas)]
# parameters
p = 2^85
a = 0x66e158441b6995
b = 0xb
n = 85
r = 32
sequence = [1310585136, 1634517111, 2548394614, 745784911]
# break the LCG
start_seed = break_lcg(a,b,p,n,r,sequence)
# run it to sample required values
lcg = LinearCongruentialGenerator(a, b, n)
lcg.state = start_seed[0]
for i in range(0, 104):
print lcg.nextint()
belongs to a centroid 
if 
for some radius 
). All points not belonging to a centroid will be penalized using some heuristic. This is basically the K-means clustering algorithm.
, this has a root 
. We could try to find this root using Coppersmith, but it turns out it not possible since the size of 
is larger than 
. However, due to a publication by Håstad, we can construct the following:
as![\phi_i = \frac{1}{N_i}\cdot \prod_k N_k \cdot [\prod_k N_k / N_i]^{-1}_{N_i}](https://s0.wp.com/latex.php?latex=%5Cphi_i+%3D+%5Cfrac%7B1%7D%7BN_i%7D%5Ccdot+%5Cprod_k+N_k+%5Ccdot+%5B%5Cprod_k+N_k+%2F+N_i%5D%5E%7B-1%7D_%7BN_i%7D&bg=ffffff&fg=000000&s=0 "\phi_i = \frac{1}{N_i}\cdot \prod_k N_k \cdot [\prod_k N_k / N_i]^{-1}_{N_i}")
also has a root 
(this is easy to check!). Since 
is strictly smaller than 
, the polynomial roots of 
, where 
. The density of primes (well, asymptotically) is 
, so we expect 
to be quite small.
. Now, we solve the following equation
. So, we may simply call 
on them and check if they divide 
. Note that we need to do this for different hypotheses (different 
).
. We cannot decrypt the message! If we look closely, we see that 
. Hmm… so, we can decrypt the message 
. And the message is the flag, which is constant. What if we sample two ciphertexts encrypting the same message but under different keys? Yes… so, basically, we have 
and 
. Then, we can combine it using CRT! This is easy!
. Because of this, the task is really trivial. We can simply compute the cubic root without taking any modulus into consideration. 
can solve this efficiently! This gives us:
, where 
. So, we have 
. The observant reader have noticed that if we remove 
, it will not wrap around 
, i.e., find 
. Now we are back in the scenario of previous challenge… so, we can use the method from before! Hence, 
. Finally, we get
. We can write this as 
. Now, we can eliminate the ordo term by taking 
. Assuming that 
, we can determine 
by simple division. So, 
. In Python, we have that
. If so, we have found a factor. Turns out two moduli have a common factor, so we can factor each of them and decrypt their traffic:
, which is a function from 4 bits to a byte. 
is an error (or pertubation) vector with only one bit set. This defines a map 
. So, each plaintext byte is two ciphertext bytes.
(compute the intersection between the Hamming ball of the ciperhext block and 
. An immediate conclusion is that we need to some kind of collision attack. But how? We cannot exploit any collision in the 
while keeping 
distinct?
, we need to perform some additional computations. Obviously, we could factor the modulus 
and compute 
and then obtain the signature as easy as 
… but factoring…
digits so not a good candidate for msieve or other factoring software… so what then? 
and 
both are prime? Then, we can easily recover the signature as 
! No need for time-consuming factoring! Embodied in Python, it could look like this:
. Then, the secret becomes 
. Notably, the first block 
contains the hash, but encrypted.
as username? Then, we have encrypted 
, but we want only 
. As mentioned before, the hash fits perfectly into a single block. So, by removing the 
, 
, which is all what we need.![\mathbb F_2[x]/P(x)](https://s0.wp.com/latex.php?latex=%5Cmathbb+F_2%5Bx%5D%2FP%28x%29&bg=ffffff&fg=000000&s=0 "\mathbb F_2[x]/P(x)")
with the mapping that, for instance, an integer 
is 
in binary, which corresponds to a polynomial 
. The code is doing 
in 
.
to be the key and 
the seed. Note that all elements are in 
is unknown.
and 
. The individual square roots exist and are unique.
with the exception that elements are in 
this time. We omitt the multiplication symbol from now on.
matrices (with elements in 
and 
.
.
via a square-and-multiply type algorithm. In python, it would be
is computed, it returns
. Adding this to the above yields
.
. Note that given two elements of the key stream, all these elements are known. Once determined, we compute the (dicrete) 
to find 
.
fixed to obtain the flag 
. Let us reorder the function as follows:
, since we can control 
. Equivalently, we can encrypt for different values of 
, where the trailing six bits will be the trailing six bits of 
.
time and space. This is done by putting about 
values of the encryption (or decryption) in a table. Then, we generate the decryptions (or encryptions, respectively) and look in the table.
