Cracking a PRNG by observing ranks within groups of its output

Suppose that I am generating random numbers with Python's random module, so that there is a known random number generator (Mersenne Twister in this case). I've read: "[...] observing a sufficient number of iterations (624 in the case of MT19937, since this is the size of the state vector from which future iterations are produced) allows one to predict all future iterations." This also got into how to actually crack it: Cracking Random Number Generators - Part 3

What if, instead of peeking at random numbers from the generator, you saw repeated rankings of the random numbers? As an example, the generator repeatedly produces vectors of 100 ranks for 100 uniform 0-1 numbers:

first 100: (47, 22, 1, 12, ...)
second 100: (18, 44, 99, 24, ...)

How much would this slow down the cracking process? I feel that this has a pretty precise answer, but I have no idea how one would even get started with the analysis/math.

• Hint: use an entropy argument, where you obtain a minimum expected number of rankings by dividing the amount of information wanted by the amount of information obtained from each ranking. Make it rigorous by noticing that the Mersenne Twister has a circular state. Notice that this does not tell if the attack is computationally feasible.
– fgrieu
Jul 8, 2016 at 5:59
• Thanks. I'm a little confused on what you mean with "minimum expected number". You mean this is a lower bound? Also, if the 624 random numbers mentioned in the question sum to X bytes, and each ranking contains Y bytes of info, does seeing X/Y rankings really give us the same "information"? It strikes me as information that might be the same in terms of entropy, but lesser in terms of usefulness. Or is it all the same in terms of reverse engineering the state? Jul 8, 2016 at 6:22
• Yes, the entropy argument will give you a lower bound for the expected number of rankings required to find the state of the RNG, for random distribution of that state (it won't rule out that, infrequently, the state can be found with less rankings). Exactly as you noticed, it does not tell you that the information obtained from the rankings is actually exploitable to find the RNG state: it might be computationally impossible to do so; the information obtained from a ranking could be less than estimated because the RNG makes some rankings impossible; or/and the rankings might be correlated.
– fgrieu
Jul 8, 2016 at 6:54
• What is your definition of "uniform 0-1 numbers"? Uniform binary strings of some length $L$? Do you then divide the output into these substrings and convert to integer? Jan 18, 2018 at 17:06
• @kodlu, I was supposing that we have an application that is generating floating point numbers between 0 and 1 for some "business" purpose. So I was wondering, if the app sometimes leaked not the numbers themselves, but ranks of the numbers, is that bad? Jan 20, 2018 at 18:56

1 Answer

Assuming $$w=32$$ (32-bit integers for internal state), $$624 * 32 = 19968$$ bits of information is found in the internal state. On the other hand, a maximum of $$\lfloor\log_2(100!)\rfloor=524$$ bits of information is revealed by each ranking of 100 outputs. $$\lceil19968/524\rceil=39$$ rankings of 100 outputs each would be the minimum information I would expect to need to identify the state. I do not, however, know of an algorithm to use the revealed ranking information to calculate the state.

You talk about "leaking" information and ask about a "cracking process". I hope you are not attempting to use a Mersenne Twister when a cryptographically secure pseudo-random number generator is needed.