11
$\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

Your Answer

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

Browse other questions tagged or ask your own question.