# Can it ever be impossible to invert a PRNG?

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

• If your state has an entropy of $n$ bits, you cannot uniquely determine it if you know less than $n$ bits. Aug 18 '15 at 6:32
• A constraint itself can have more or less effect. You cannot just use the number of constraints in an equation. Aug 18 '15 at 7:40
• @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.
– otus
Aug 18 '15 at 11:00
• @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. :) Aug 18 '15 at 13:18
• 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.
– tylo
Oct 19 '15 at 15:16