[Python] Applying lattice attack on Truncated Linear Conguential Generator efficiently?

I took interest on the project that someone was working on and in theory it should work but after putting it in code the results aren't as expected.

The equation:

k_i = (k_{i-1}+x_i)*const + 1 mod 0xFFFFFFFF

Is what i am describing as linear recurrence equation, where:

const = 0x08088405
x1, x2, x3, x4 = 0x0E, 0xEE, 0x42, 0x88
k0 =0x447B846F
k1 =0x12A20A72
k2 =0x4607B8E1
k3 =0x3AB4A9B0
k4 =0x5F0C3319


And if you apply above values with the above equation, you can see that its congruent,but here comes the problem. What if i only know LSBs of Ks.

Like this:


lk0, lk1, lk2, lk3, lk4 = 0x6F, 0x72, 0xE1, 0xB0, 0x19


k4 = (k0+x1)*(const**4) + (1+x2)*(const**3)+ (1+x3)*(const**2) + (1+x4)*const + 1
k3 = (k0+x1)*(const**3) + (1+x2)*(const**2)+ (1+x3)*const + 1
k2 = (k0+x1)*(const**2) + (1+x2)* const + 1
k1 = (k0+x1)*const + 1


I think this can be a lattice problem, but lattices are hard use for us beginners. Here is my setup which i dont know what i have done wrong:

from fpylll import IntegerMatrix, LLL

# Constants


c = 0x08088405
n = 2**32
x1, x2, x3, x4 = 0x0E, 0xEE, 0x42, 0x88
lk0, lk1, lk2, lk3, lk4 = 0x6F, 0x72, 0xE1, 0xB0, 0x19

# Derived constants
mod_small = 2**8
mod_large = 2**32
scale = 2**32 # corrected scale for proper embedding

# Linear combination constants (f_i corresponds to the linear combination of s = k0 + x1)
f1 = 1
f2 = (1 + x2)*c + 1
f3 = (1 + x2)*c**2 + (1 + x3)*c + 1
f4 = (1 + x2)*c**3 + (1 + x3)*c**2 + (1 + x4)*c + 1

# Right-hand side values (mod 256)
r1 = (lk1 - f1) % mod_small
r2 = (lk2 - f2) % mod_small
r3 = (lk3 - f3) % mod_small
r4 = (lk4 - f4) % mod_small

# Initialize 6x6 lattice
B = IntegerMatrix(6, 6)

# First four diagonal entries represent unknown 32-bit values (u1-u4)
for i in range(4):
B[i, i] = mod_large

# Row 5: linear relation for s = k0 + x1, using u_i's coefficients
B[4, 0] = c
B[4, 1] = c**2
B[4, 2] = c**3
B[4, 3] = c**4
B[4, 4] = 1 # Coefficient of s

# Row 6: target vector (error terms embedded)
B[5, 0] = r1 * scale
B[5, 1] = r2 * scale
B[5, 2] = r3 * scale
B[5, 3] = r4 * scale
B[5, 5] = scale

print("[*] Lattice basis before LLL:")
print(B)

# Run LLL reduction
print("[*] Running LLL...")
LLL.reduction(B)
print("===========================================================")
print("[*] Lattice basis after LLL:")
print(B)

# Search for candidate s = k0 + x1
print("[*] Looking for short vector giving correct k0 LSB...")
found = False
for row in B:
coeffs = list(row)
s_candidate = coeffs[4]
k0_candidate = (s_candidate - x1) % n
print(f" 0x{k0_candidate:08X}")


I am expecting to find any Ks using the above code but i found none and i couldn't understand what went wrong.

Continue reading...