9
$\begingroup$

I am struggling to apply Freize et al. paper to break a truncated LCG.

A truncated LCG is a pseudo random generator that outputs the $n$ leading bits $y_i$ of $x_i$, where $(x_i)$ is such that $x_{i+1} = \alpha \cdot x_i + \beta\mod M$, and $\alpha$ is an integer, coprime with $M$. The first state $x_1$ is unknown.

The objective is to break the LCG, ie, from one or several consecutive outputs, find the current state $x_i$. We suppose that $\alpha$ and $M$ are known, and $\beta = 0$ (and is known too).


The theory

The paper states (pages 5 and 6) that their method solves systems of modular equations of the form $\displaystyle\sum_{j=1}^k a_{ij}x_j \equiv c_i \mod M$, for all $i \in \{1, \dots, k\}$.

Deriving a lattice from the vectors $a_i$, the authors apply LLL to find a small basis, of vectors $w_1, \dots, w_k$.
By multiplying the matrix $\begin{pmatrix} w_1\\ \vdots\\ w_k \end{pmatrix}$ on the right by $x$, they derive a new set of equations: $\displaystyle\sum_{j=1}^k w_{ij}x_j \equiv c_i' \mod M$, for all $i \in \{1, \dots, k\}$.

Here, i guess that the $c_i'$ are just obtained from the $c_i$ by multiplying (on the left) by the same matrix that allowed us to go from our original basis to our reduced basis.

Now, if the $c_i'$ are small enough, the equalities actually hold on $\mathbb{Z}$ and we can solve them: we have effectively solved the system.


In practice

Now, the authors talk a bit more about their method for a LCG, part 3 (pages 11 and 12).

We have the relations $\alpha^{k-1} x_{1} - x_k = 0$ (edit: fixed typo), so I guess that it implies that all my $c_i$ are $0$.

Now, if I want to obtain my $c_i'$, I should multiply $c$ on the left by the same matrix as the one used to change the basis of the lattice. But, given that I have $c = 0$, I should have $c' = 0$ as well, so we don't need to compute this matrix.

Furthermore, my lattice is, as descibed by the paper, $$L = \begin{pmatrix} M & 0 && \dots & 0\\ \alpha & -1 &0& \dots & 0\\ \alpha^2 & 0 & -1 & \dots & 0\\ \vdots &&&\ddots & \vdots\\ \alpha^{k-1} & 0 & 0 & \dots & -1\\ \end{pmatrix}$$ which is trivially nonsingular, and as such, the only solution to $Lx = 0$ is $x = 0$, which is obviously wrong.

Even worse, this method does not use the $y_i$, but it obviously should at some point, so I guess I'm missing something.


My questions

(Most probably related)

  1. In my case, what are the $c_i$, and do I really obtain the $c_i'$ from them by the basis change?
  2. How are the $y_i$ supposed to take part in this method?
$\endgroup$
4
  • 1
    $\begingroup$ I am still analyzing the paper and at the moment I can't continue. But how the y_i take part is described on p.267 in the proof of case (i) of Corollary 2.3. So you have Lx=0 and plug in y+z for x (y is x(1) from the paper, z is x(2)) to get Lz=c. Now calculate c' according to (2.5) and now you can establish (2.6) and therefore the corresponding linear , nonmodular equation. This has one solution. $\endgroup$
    – miracle173
    Jul 20, 2016 at 9:56
  • 1
    $\begingroup$ instead of $\alpha^{k-1} x_{k} - x_1 = 0$ it should be $\alpha^{k-1} x_{1} - x_k = 0$ $\endgroup$
    – miracle173
    Jul 20, 2016 at 13:57
  • $\begingroup$ Oops, sorry for the typo. As for your first comment, I completely missed that in the paper, thanks! So c = Ly, and from that one gets that c' = L'y, where L' is the LLL-reduced matrix. Giving this system to Sage gave me an integer solution, but not the good one -- It appears that the c' I have are always above the bound given in the paper (M/2). (i.imgur.com/rPcYUJM.png). I'm investigating the case $\endgroup$
    – Mariuslp
    Jul 20, 2016 at 15:10
  • $\begingroup$ Update: when I remove the modulo from my last command in the Sage script I wrote (see image), the results get much closer to what they should be... with a -1 factor. i.imgur.com/jbd93Gb.png Also, in my previous comment I meant c = -Ly, and c'= -L'y. I guess this is where the -1 factor comes from. $\endgroup$
    – Mariuslp
    Jul 20, 2016 at 15:59

1 Answer 1

9
$\begingroup$

The lattice basis $L$ generates every point that is a solution to the congruence $a^{i-1} x_1 - x_i \equiv 0 \pmod{m}$. By definition, the reduced basis $B = \mathsf{LLL}(L)$ also generates the same solutions; it just has shorter vectors.

Now suppose we have a set of outputs $\mathbf{y} = y_i$ of the generator, which correspond to the most significant bits of the LCG multiplied by $2^s$, and we want to find $\mathbf{z} = z_i$ such that $\mathbf{y} + \mathbf{z} = \mathbf{x}$, where $\mathbf{x} = x_i$ is the reconstructed state. The key insight here is $$ \begin{align} & L \cdot \mathbf{x} \equiv 0 \pmod{m} \\ & B \cdot \mathbf{x} \equiv 0 \pmod{m} \\ & B \cdot \mathbf{x} = m \cdot \mathbf{k} \quad \mbox{(for some unknown $\mathbf{k}$)} \\ & B \cdot (\mathbf{y} + \mathbf{z}) = m \cdot \mathbf{k} \\ & B \cdot \mathbf{z} = m \cdot \mathbf{k} - B \cdot \mathbf{y} \end{align} $$

Now, because the coefficients in the reduced basis $B$ are small, we know that all the elements of $\mathbf{k} = k_i$ are small, and we can further deduce $k_i = \lfloor (B \cdot \mathbf{y})_i / m \rceil$, or in other words, $m \cdot k_i$ is the closest multiple of $m$ in relation to each element of $B \cdot \mathbf{y}$. Once we know $k_i$, this is a simple matter of linear algebra. Here's an example with Sage:

p = previous_prime(2^32)
a = randint(2, p)
s = randint(0, p)
X = [ a^(i+1) * s % p for i in range(4) ]
Y = [ x - x % 2^16 for x in X ] # high 16 bits
Z = [ x % 2^16 for x in X ] # low 16 bits (secret)

L = matrix([
    [  p,  0,  0,  0 ],
    [a^1, -1,  0,  0 ],
    [a^2,  0, -1,  0 ],
    [a^3,  0,  0, -1 ]
])

B = L.LLL()

W1 = B * vector(Y)
W2 = vector([ round(RR(w) / p) * p - w for w in W1 ])

Z_ = list(B.solve_right(W2))
print Z_
print Z
$\endgroup$
1
  • 2
    $\begingroup$ Oooooh, I get it! I assumed that the lattice reduction would automatically give $c_i'$s such that $\left|c_i'\right| < M/2$. Actually, we force the $c_i'$ to be in this range, so that the equalities $L'z = c'$ hold on Z. Great answer, thanks! $\endgroup$
    – Mariuslp
    Jul 21, 2016 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.