13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – fgrieu Jul 8 '16 at 5:59
  • $\begingroup$ 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? $\endgroup$ – dcc310 Jul 8 '16 at 6:22
  • 2
    $\begingroup$ 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. $\endgroup$ – fgrieu Jul 8 '16 at 6:54
  • 1
    $\begingroup$ 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? $\endgroup$ – kodlu Jan 18 '18 at 17:06
  • $\begingroup$ @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? $\endgroup$ – dcc310 Jan 20 '18 at 18:56
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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