7
$\begingroup$

I've read about the possibility of inverting the Mersenne Twister after 624 numbers of output. 624 matches the state size of my implementation of the Twister. Coincidence? If the generator only output 623 numbers, i.e. less than the state size, might inversion still be possible with really clever maths? Or is this mathematically and logically impossible?

This leads me to think about a general case. I got this embryonic analogy from solving simultaneous equations. Consider each member within the state array as a degree of freedom. And consider each number output as a degree of freedom. And if (for some generator) there is a group operation over the whole state such as an addition of all of the elements, this acts as a constraint. Can the following be true?

Let,

$F_o$ = degrees of freedom output,
$F_s$ = degrees of freedom within state,
$C_n$ = number of constraints on the state.

Is the random number generator “impossible to uniquely invert” if $F_o < F_s - C_n$?

Improve this question
$\endgroup$
5
  • $\begingroup$ If your state has an entropy of $n$ bits, you cannot uniquely determine it if you know less than $n$ bits. $\endgroup$
    – Chris
    Commented Aug 18, 2015 at 6:32
  • $\begingroup$ A constraint itself can have more or less effect. You cannot just use the number of constraints in an equation. $\endgroup$
    – Maarten Bodewes ♦
    Commented Aug 18, 2015 at 7:40
  • $\begingroup$ @Chris, if the state has $n$ bits of entropy you can't determine every state from less than $n$ bits, but that doesn't rule out detecting some states from less. $\endgroup$
    – otus
    Commented Aug 18, 2015 at 11:00
  • $\begingroup$ @otus: In my comment 'bits' was intended to refer to 'bits of information'. The usual way to look at this, is that if you have $n$ bits of entropy (uncertainty) and you add $k<n$ bits of information, then you still have $n-k>0$ bits of entropy left, and thus you don't know the state. -- Your comment refers to source coding (aka compression), where some sequences of 'bits' (the other ones) carry more information than other sequences. :) $\endgroup$
    – Chris
    Commented Aug 18, 2015 at 13:18
  • $\begingroup$ The entire argument for "impossible to uniquely invert" is not relevant for the cryptographic strength with emphasis on "uniquely": If an attacker can exclude only a portion of the possible states, he might already be able to predict the next bit with a non-negligible probability, breaking the algorithm in the cryptographic sense. Finding out the exact internal state is not required for that. As a rule of thumb: CSPRNGs and PRNGs are very different things, and the similar name is very misleading. Don't mix them up, it doesn't work. $\endgroup$
    – tylo
    Commented Oct 19, 2015 at 15:16

1 Answer 1

Reset to default
7
$\begingroup$

I've read about the possibility of inverting the Mersenne Twister after 624 numbers of output. 624 matches the state size of my implementation of the Twister. Coincidence? If the generator only output 623 numbers, i.e. less than the state size, might inversion still be possible with really clever maths? Or is this mathematically and logically impossible?

No, it's not a coincidence. The period is related to the state size, and a smaller sample cannot allow unique inversion due to the fact that every shorter number sequence appears in the total output of MT (with equal frequency to boot).

In general the same does not have to be true. A PRNG can use its state "wastefully" in such a manner that not every state is possible and inversion can happen much earlier than state size. Or it can have correlations that break it even without inversion. Contrarily, an actual cryptographically secure PRNG is expected to produce much more output than the state size without ever being invertible.

So I doubt your equation holds without additional assumptions.

Improve this answer
$\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.