8

My understanding is that PRNG's work by using an input seed and an algorithm that converts it to a very unrelated output, so that the next generated number is as unpredictable as possible. But here's the problem I see with it:

Any pseudorandom number generator that I can imagine has to have a finite number of outcomes. Let's say that I'm using a random number generator that can generate any number between 0 and one hundred billion. If I call for an output one hundred billion and one times, I can be certain that one number has been output more than once. If the same seed will always give the same output when put through an algorithm, then I can be sure that the PRNG will begin a loop. Where is my logic flawed here?

In the case that I am correct, if you know the algorithm for a PRNG, and that PRNG is being used for cryptography, can not this approach be used (and are there any measures in place to prevent it?):

  • Use the PRNG to generate the entire looping set of numbers possible.
  • Know the timestamp of when a private key was generated, and know the time AND -output of the PRNG later on
  • Based on how long it takes to calculate, determine how many numbers are between the known output and the unknown one
  • Lookup in the pre-generated list to find the generated number
3
  • "Use the PRNG to generate the entire looping set of numbers possible". If you can wait for 10^100 years, sure, go ahead.
    – n. m.
    Aug 8, 2016 at 21:10
  • 9
    Remember that the state doesn't have to be the same size as the output. Even if you're only getting 32-bit outputs or 64-bit outputs, the state could be 256 bits, far too large to wait for it to loop. Aug 8, 2016 at 21:11
  • @user2357112 And rather than looping, the algorithm could just add a few more bits to the state, giving it a few more billion years at a billion outputs a second before it would risk repeating. Aug 8, 2016 at 22:27

4 Answers 4

8

You are absolutely right that in theory that approach can be used to break a PRNG, since, as you noted, given a sufficiently long sequence of outputs, you can start to predict what comes next.

The issue is that "sufficiently long" might be so long that this approach is completely impractical. For example, the Mersenne twister PRNG, which isn't designed for cryptographic use, has a period of 219,937 - 1, which is so long that it's completely infeasible to attempt the attack that you're describing.

Generally speaking, imagine that a pseudorandom generator uses n bits of internal storage. That gives 2n possible internal configurations of those bits, meaning that you may need to see 2n + 1 outputs before you're guaranteed to see a repeat. Given that most cryptographically secure PRNGs use at least 256 bits of internal storage, this makes your attack infeasible.

One detail worth noting is that there's a difference between "the PRNG repeats a number" and "from that point forward the numbers will always be the same." It's possible that a PRNG will repeat an output multiple times before moving on to output a different number next, provided that the internal state is different each time.

4

You are correct, a PRNG produces a long sequence of numbers and then repeats. For ordinary use this is usually sufficient. Not for cryptographic use, as you point out.

For ideal cryptographic numbers, we need to use a true RNG (TRNG), which generates random numbers from some source of entropy (= randomness in this context). Such a source may be a small piece of radioactive material on a card, thermal noise in a disconnected microphone circuit or other possibilities. A mixture of many different sources will be more resistant to attacks.

Commonly such sources of entropy do not produce enough random numbers to be used directly. That is where PRNGs are used to 'stretch' the real entropy to produce more pseudo random numbers from the smaller amount of entropy provided by the TRNG. The entropy is used to seed the PRNG and the PRNG produces more numbers based on that seed. The amount of stretching allowed is limited, so the attacker never gets a long enough string of pseudo-random numbers to do any worthwhile analysis. After the limit is reached, the PRNG must be reseeded from the TRNG.

Also, the PRNG should be reseeded anyway after every data request, no matter how small. There are various cryptographic primitives that can help with this, such as hashes. For example, after every data request, a further 128 bits of data could be generated, XOR'ed with any accumulated entropy available, hashed and the resulting hash output used to reseed the generator.

Cryptographic RNGs are slower than ordinary PRNGs because they use slow cryptographic primitives and because they take extra precautions against attacks.

For an example of a CSPRNG see Fortuona

2

It's possible to create truly random number generators on a PC because they are undeterministic machines.

Indeed, with the complexity of the hierarchical memory levels, the intricacy of the CPU pipelines, the coexistence of innumerable processes and threads activated at arbitrary moments and competing for resources, and the asynchronism of the I/O devices, there is no predictable relation between the number of operations performed and the elapsed time.

So looking at the system time every now and then is a perfect source randomness.

7
  • 2
    This is interesting, but does it actually answer the question here? Also, while I agree that you can definitely get a lot of entropy out of different sources from the computer, looking at the system time periodically seems like a very bad idea, since an attacker could easily guess what time window you were running in and brute-force attack all possible times in that range to guess which seed you used. Aug 8, 2016 at 21:44
  • 1
    @templatetypedef: good luck to crack a generator having 128 ordinary state bits plus 16 truly random ones obtained by probing the clock every billion operation (conservative figure).
    – user1196549
    Aug 8, 2016 at 21:49
  • It's possible that I misinterpreted your statement. It's generally considered a bad idea to use the system time for cryptographic applications, since if those are the only seed bits they can be brute forced relatively easily because there aren't that many different possible values (at least, compared against the space of possible keys). However, if you're just using them as one source of entropy in a general entropy accumulator, then yes, that's a totally reasonable way to go. (I still don't think that your answer actually answers the question, though.) Aug 8, 2016 at 21:52
  • @templatetypedef Not on a modern CPU with a TSC that runs at billions of ticks per second that you can check as often as you please. You have to know what you are doing, but truly random number generators can be constructed and often are. Aug 8, 2016 at 22:17
  • 1
    Using timer clicks is a valid source of a little entropy. It will not be enough on its own. It needs to be combined with other entropy sources, and the whole lot hashed together to provide a reasonably random input.
    – rossum
    Aug 9, 2016 at 0:13
0

Any pseudorandom number generator that I can imagine has to have a finite number of outcomes.

I don't see why that's true. Why can't it have gradually increasing state, failing when it runs out of memory?

Here's a trivial PRNG algorithm that never repeats:
1) Seed with any amount of data unknown to an attacker as the seed.
2) Compute the SHA512 hash of the data.
3) Output the first 256 bits of that hash.
4) Append the last byte of that hash to the data.
5) Go to step 2.

And, for practical purposes, this doesn't matter. With just 128 bits of state, you can generate a PRNG that won't repeat for 340282366920938463463374607431768211456 outputs. If you pull a billion outputs a second for a billion years, you won't get through a billionth of them.

5
  • Aren't there still a limited number of states? It seems impossible that it would literally never repeat. Even if it's a ridiculously long time, eventually the state would end up being the same thing and it'd loop. (I know that for all practical uses it doesn't matter, just wondering if it would in theory)
    – user4531029
    Aug 8, 2016 at 21:38
  • Since the state gets a byte longer each time, how can it ever repeat? Aug 8, 2016 at 22:17
  • Like you said, when you run out of memory it'll fail, and if you want it to keep generating numbers you'll have to start somewhere else. Eventually, won't you get around to the same value twice?
    – user4531029
    Aug 8, 2016 at 22:22
  • 1
    @Ekyl It will fail if it runs out of memory. But every algorithm has computational requirements and if a system doesn't meet its requirements, that algorithm will fail. But it will never repeat, so long as the hardware is sufficient for the algorithm. Aug 8, 2016 at 22:25
  • @Ekyl you are right, an infinite aperiodic sequence is not possible to produce with a finite computer. In practice this means very little though. We don't need aperiodic sequences, sequences with extremely long periods are quite enough for our purposes.
    – n. m.
    Aug 9, 2016 at 13:51

Your Answer

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