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.

Improve this question
$\endgroup$
5
  • 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, 2016 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, 2016 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, 2016 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, 2018 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, 2018 at 18:56

1 Answer 1

Reset to default
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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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