0
$\begingroup$

I am creating a web app that applies Python's random algorithm (Mersenne Twister) to generate random 12-bit integers. I am concerned as to how a user can predict future results by recording the needed number of sequence using API calls

import random
def rand12bits():
    return random.randint(0, 4095)

How many of these outputs do i need to predict the future sequence?

I am aware that with enough (624) observed outputs of 32 bit integers, it can be reversed. But in this case, the RNG is only giving off 12 bit integers. Am I missing something? Pardon me for my naivity I am new at this.

$\endgroup$
  • $\begingroup$ Welcome to Crytpo stack exchange ! I think poncho's answer here contains all the information you need crypto.stackexchange.com/questions/2231/… $\endgroup$ – Faulst May 26 at 9:13
  • $\begingroup$ Not quite. I know that with enough (624) observed outputs of 32 bit integers, it can be reversed. But in this case, the RNG is only giving off 12 bit integers. I am a novice at this. I am sorry if I sound naive. Thanks $\endgroup$ – Ozichukwu May 26 at 10:30
  • $\begingroup$ If you are creating something (new), why use the default Python's random rather than python's secrets, reportedly available since 3.6 and generating cryptographically strong random numbers? $\endgroup$ – fgrieu May 26 at 18:02
2
$\begingroup$

How many of these outputs do i need to predict the future sequence?

Well, to recover the RNG state, you need to observe 19968 bits of output (which translates into state); by seeing 12 bits at a time, you'll see enough after 1665 outputs.

One question you might have is: the 12 bits might not come from consecutive Mersenne Twister outputs, so we won't be able to trivial reconstruct the 624 word state. This is true; however Mersenne Twister is completely linear in GF(2); hence we can describe the 19968 bit initial state as a linear function of the observed output states, and (with enough linear equations), solve for the initial state. This is obviously more work than the trivial 'here's one intermediate 624-word state'; however it is practical.

The other thing to note is this estimate assumed that the initial state was completely unknown. If it is partially known (e.g. the initial state was 256 bits of unknown values, followed by a known pattern), this reduces the number of outputs that are needed (because those known initial state bits give us free equations)

| 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.