2
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Feb 16, 2016 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. ♦
    Commented Feb 17, 2016 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. ♦
    Commented Feb 17, 2016 at 2:22

Your Answer

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

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