1
$\begingroup$

Suppose we have a linear congruential generator defined by $X_{n+1} = (a X_n + c) \mod 2^n$ where $a, c, n$ are all known and we would like to determine the initial value $X_0$. However, if we can only see the $k$ high-order bits of each of the $X_i$ for $i \geq 0$, the best algorithm I know of is a brute force which tries $O(2^{n-2k})$ possibilities, and this is exponential in $n$.

Compare this to the Mersenne Twister, whose initial state can be computed in polynomial time given only the high-order bits of each output (it reduces to solving a system of $n$ equations in $n$ unknowns). Is there a better algorithm out there which can solve for the initial state of an LCG given only the high-order bits of each output, and if not, is LCG actually broken?

$\endgroup$
2
$\begingroup$

Yes, there are techniques based on lattice reduction that are faster than brute force. See, e.g., https://crypto.stackexchange.com/a/20714/351, especially the first 3 papers cited there.

One can also use meet-in-the-middle techniques to get the running time down to $O(2^{(n - k)/2})$ if $k \ge n/2$: see https://crypto.stackexchange.com/a/10609/351.

$\endgroup$
  • $\begingroup$ The meet in the middle attack is flawed in the case that $k < n/2$. The attack assumes that we can compute $X_0$ based on the high order bits of $X_0$ and $X_1$ only, but there are only $2k$ bits here, so we would be left with $2^{n - 2k}$ possibilities and there is no improvement. I do not understand how the lattice reduction techniques are relevant here, as far as I can tell they aim to solve the different problem where $a, c, n$ are unknown but where the full outputs are known. $\endgroup$ – Sam Fingeret Feb 16 '16 at 23:48
  • $\begingroup$ @SamFingeret, thanks for the feedback. I've updated my answer accordingly. On lattice reduction: I think you gave up too quickly. See the updated link, especially the 3 papers cited there. I think they do solve exactly your problem -- the papers are clear that they are talking about the case of observing truncated outputs (the full outputs are not known). For the meet-in-the-middle attack: I've revised my answer accordingly. Thank you for the correction and for spotting my error. It wouldn't surprise me if we could relax the $k \ge n/2$ condition, e.g., by considering $X_0,X_1,X_2$. $\endgroup$ – D.W. Feb 17 '16 at 2:18
  • $\begingroup$ For instance, would it help to write $X_1= c 2^{n-k} + 2^{(n-k)/2} d + e$ and then write $X_0 = \text{known} + \text{known} \times d + \text{known} \times e$ and $X_2 = \text{known} + \text{known} \times d + \text{known} \times e$? We could look for a match between the pair $(X_0 - \text{known} \times d, X_2 - \text{known} \times d)$ and the pair $(\text{known} + \text{known} \times e, \text{known} + \text{known} \times e)$. $\endgroup$ – D.W. Feb 17 '16 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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