0
$\begingroup$

I was reading this challenge, which proposes to clone (or recover) the internal state of the MT19937 just by applying the inverse process to each output (624 consecutively words).

Mersenne Twister's FAQ also says:

Mersenne Twister is not cryptographically secure. (MT is based on a linear recursion. Any pseudorandom number sequence generated by a linear recursion is insecure, since from sufficiently long subsequence of the outputs, one can predict the rest of the outputs.)

It's possible to reproduce this attack against MT19937 even if the output has been reduced by a modulo? E.g.:


Let $R_i\in \Bbb Z_{2^{32}}$ and $1 \le m \le R_i$ where $R_i$ is the MT19937 output.

$$R_i\ mod\ m$$


In case it is not possible to reproduce the attack, MT19937 (with modulo reduction) can still be considered cryptographically insecure?

$\endgroup$
5
  • $\begingroup$ Although, consider the interesting situation where you completely reseed after 560 consecutive outputs (for 32 bit MTs). You would have 256 bits of security against state recovery. $\endgroup$
    – Paul Uszak
    Jun 10, 2022 at 3:05
  • $\begingroup$ @PaulUszak quantified claims of security like that should be formally justified really, i.e. are only really appropriate for a comment if they are incredibly obvious. Your comment is not incredibly obvious to me at least. $\endgroup$
    – Mark Schultz-Wu
    Jun 10, 2022 at 6:07
  • $\begingroup$ @Mark Hiya. Err, isn't incredibly obvious if you're missing 8 no. 32 bit words from the sample set prior to inversion that you can't? The equations would be missing quite a lot of values. Don't over think this; it's really simply. P.S. This is comment, not answer. Why do I get into these messes? Are you familiar with edge play? $\endgroup$
    – Paul Uszak
    Jun 10, 2022 at 6:56
  • $\begingroup$ @PaulUszak I think any statement regarding an "incredibly obvious" property of a LCG in cryptography is highly suspect, given the incredibly bad record of LCGs in cryptography. $\endgroup$
    – Mark Schultz-Wu
    Jun 10, 2022 at 10:22
  • $\begingroup$ @Mark Yes, I totally agree with LCG insecurity. The point I'm making that that (my) point is that even so, without 624 words, you don't have enough simultaneous equations to solve completely. It becomes more and more mathematically impossible with less and less output values. Imagine if you only had one 32 bit word. That wouldn't really help... $\endgroup$
    – Paul Uszak
    Jun 10, 2022 at 12:51

1 Answer 1

1
$\begingroup$

First, note that MT is what is known as a linear congruential generator. This defines

  1. a modulus $m$
  2. a multiplier $a$,
  3. an increment $c$, and
  4. a seed $s$.

And then defines $X_0= s$, and $X_i \equiv (aX_{i-1}+c)\bmod m$. The PRNG sequence is $(X_0,X_1,\dots, X_n,\dots)$.

It seems that you suggest choosing another multiplier $m' < m$, and instead making public $Y_i \equiv X_i\bmod m'$.

Is it [sic] possible to reproduce this attack against MT19937 even if the output has been reduced by a modulo?

It highly depends on the specifics, but this is very likely. I'll summarize some discussion found in Predicting Truncated Multiple Recursive Generators with Unknown Paremeters.

In the case that only truncated elements of the sequence [of LCG outputs] are output, Knuth [15] observed that the low-order bits of the sequence generated by an LCG tend to appear much less random than the high-order bits.

This already suggests that seed extraction is the least of your worries --- the sequence itself may not be close to uniformly random, which is required for most applications.

Of course, if the low order bits are bad, what about the high order bits? A variety of authors have considered this setting (including Stern, Contini, Boyar, and Frieze --- see the introduction of the linked paper), and all of the results appear to be negative.

Small modifications of LCGs have an incredibly bad cryptographic history. By the aforementioned work of Knuth, it is likely your suggestion is not particularly close to uniformly random. By the work of others, the natural modification of your suggestion (that has better statistical properties) is not cryptographically secure. While properly you should formalize a particular proposal (and then see if the aforementioned work breaks it), really you should avoid LCGs for cryptography.

$\endgroup$

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.