Are random numbers a solved function?

Wednesday, March 7th, 2012 by Robert Cravotta

RNGs (Random number generators) have been used across a wide range of applications for many decades. They can be implemented in a variety of forms. Pure software algorithms enable using a specific sequence of “random” numbers at a later time, such as when performing simulation functions or debugging a system, by tracking the same seed value for the algorithm. Some processors include a hardware random number generator to provide as sequence of numbers that are as close to a true random sequence as possible.

However, the suitability of a sequence of random numbers can vary based on the context of the application that is using them. For example, devices that select random tracks of music to play have undergone an evolution from a true random sequence to one that strips out repetitive appearances of the same number that occur too close to one another in the sequence.

Are random number generators a solved function for system developers? Because not all RNGs are equal in their randomness, does that affect a porting effort when moving not just from one processor to another, but from one software development toolset to another? Have you been bitten by assumptions about an RNG that turned out to be horribly unsuitable to your application, or are RNGS mature enough that such horror stories are a thing of the past?

Tags: , ,

12 Responses to “Are random numbers a solved function?”

  1. J.K. @ LI says:

    There are good RNGs — both software implementations with good properties and hardware RNGs that approach real randomness. What’s amazing is that people still use provably bad ones all the time. Some write their own. Some use algorithms from old reference books that are well known to be broken. And some use good RNGs wrapped in larger pieces of bad code (my favorite example is shuffling a deck of cards, which many people still get wrong).

  2. J.V. @ LI says:

    I would be interested in recommendations on the use of PRNGs in deck shuffling.

  3. J.V. @ LI says:

    Sometimes I’ve put in a hook for using different PRNGs and compared them. If I’m getting very different behavior then how sensitive is the result to the assumptions I’m making? It could be that assuming completely random behavior is not a valid assumption. So I might try a very “good” PRNG, a fairly lousy PRNG that still has some good distribution qualities, and maybe also a custom-made PRNG that allows me to model some observed behavior that may or may not be typical. At least I might get a sense of how sensitive the simulation is to the model of randomness I’m using. The other things that could be done (and this may pose some other difficulties for embedded software) is to have the RNG wrapper pull from recorded data generated from a physical random source, instead of calculating the values… You can “replay” the run nondeterministically and still potentially have a run that is uncontaminated by the inherent order lurking in a PRNG. If there is a limit on how much recorded data that can be accessed, there may be some algorithmic ways of extending the period of a run based on recorded data.

  4. RVDW @ LI says:

    PRNGs are OK for things like filling memory or averaging the power direction of a communication line. I especially like to use a PRNG to “expand” true random numbers by using the true random numbers as a seed. PRNGs are usually much faster than the cheap hardware random number generators in SOCs.

    For encryption, even hardware RNGs are not random enough, because black-hats can bias power rails, apply UV or electric fields, etc. They need to be supplemented with XORed multiple sources using different methods.

  5. JSN @ LI says:

    Along the lines of what Ray is saying, RSA’s public stance is that their algorithm is “secure”, but a lot of implementations use weak RNGs…

  6. D.S. @ LI says:

    I’ve seen one of these PRNG algorithm that generates the number from the date stored in RTC as a salt. I don’t consider it safe and why would people do that. What do you think?

  7. J.K. @ LI says:

    Using the RTC has been a practice for a long time. It’s clearly not secure (some early online gaming sites that used it have been seriously cheated) but it’s a quick and lazy way to get different number sequences from different runs. Not secure, but sometimes useful.

  8. J.S. @ LI says:

    I don’t really understand why people still insist on using software PSEUDO random number generators, which are difficult to implement correctly,poorly understood and are at best poor sources of entropy, when you can simply use a real random source such as a reverse biased P-N junction followed by some form of hash function to produce a very good random number generator with very high entropy per bit.

  9. J.U. @ LI says:

    @Jeremy – I certainly wouldn’t use a pseudo-random number generator when security is the issue. However, for software verification/validation testing, repeating the exact input sequence which elicites a supposedly fixed bug can be useful.

  10. E.R. @ LI says:

    This is one of those meaningless questions without a better context. For most applications of ‘random’ the answer is they are more than good enough. Security is a system issue and seldom a problem with the RNG. A few people out on the edges of statistics need a H/W RNG.

  11. Mario says:

    Check out QRBG121 if you need a fast physical RNG not plagued by black cats or hats or whatever. Each bit has almost unity entropy, while PRNG has a constant, small entropy and you get none past number bits equal to that entropy. Even so, most of the entropy comes from the seed and if you do not have physical RNG to make the seed you are left with virtually no entropy. In cryptography, due to the Kerckhoffs principle entropy of any PRNG is at equal to the length of the seed and an enemy has only to gues the seed, not the whole “random” sequence. In pactice, due to the fact that all important classes of PRNG’s have been cryptanalyzed, given a small number of output bits one is able to calculate all parameters of a RNG and continue the sequence.

    Imagine this: you produce a lot of numbers applying a mathematical formula starting from a single number. So you know that al these numbers are connected by a simple math formula. Then suddenly you pretend you suffered amnesia and ask your self whether these are random. Then you test them and finding no flaws you conclude they are random. Isn’t that really a stupid game ? I know, people play other stupid games too. For example they buy a (worhtless) ticket and then all money is gathered and given to one lucky poor idiot somewhere in another state. And then they do it again ! There is roughly the same amount of intelligence and learning ability involved in both games….

    I believe that future is in abandoning PRNGs for any use. They have been serving us as a temporary solution (in absence of a better one) for far too long. It is clear that a PRNG is not random by definition and that too much human intellectual energy has been wasted on a futile topic already.

  12. C.L. @ LI says:

    @Ray – I agree mostly, but when it comes to manufacturing of devices and properly provisioning them for exclusive, protected use with services at a later time, the black-hat argument is moot. So I’m with Emilio – it’s all about context. In the wild, hackers will do their thing, but to sell a product that supports various DRM schemes, for instance, so you can make money on services later – an entropy register in an SoC will typically suffice as a starting point for a security model, and will definately be better than a PRNG. Please note I said a starting point. Proper provisioning and use of OTP fuses is also pretty vital.

    If your manufacturing line doesn’t have a V&I station at board level test to ensure that rails are properly biased and you can’t shell out the cash for proper enclosures to block out UV and EMI during manufacturing, you definately have not only a system security issue on your hands but a pretty severe OPS process issue and I would want to buy the product or sign up as a partner to deliver content on the device.

Leave a Reply to JSN @ LI