How insecure are non-cryptographic random number generators?

Question

I always hear that C rand() is not secure, but what how many calls would you need to know in order to predict the next value (or at least cut down the possibilities)? Would they have to be sequential? If there isn't good information about rand() I am interested in any other widely used random number generators.

Answer 1

It generally depends on the implementation. For the mostpart, you're going to be looking at Linear Congruence Generators, or Linear Feedback Shift Registers.

A common problem with these types of generators is that their period is generally quite short, and that their mathematical form implies deterministic generation. As such, you can (generally) break them in a few hundred calls or less. Sequential results do make breaking the algorithm easier, since you can make stronger correlations that way, but they're not necessary.

The largest flaw with "novel" generators is that the seed is insufficiently large. For example, if you have a generator with a 32-bit seed and know the first 20 values of the generator, it's trivial to brute force. Just generate a sequence for each seed from 0 to 2^32, and compare it. You can employ early-out optimisation to massively reduce the computational cost of this.

Pseudo code:

// the known values from the generator
byte[] knownValues = { 9, 55, 201, 50, 41, 111, 67, 44, 122, 66 };

for(seed = 0 to 2^32)
{
    srand(seed);

    bool found = true;
    for(n = 0 to len(knownValues))
    {
        if(rand() != knownValues[n])
        {
            found = false;
            break;
        }
    }

    if(found == true)
    {
        print "Found potential seed: " + seed + "\n";
    }
}

With a reasonably fast RNG and some decent hardware, this definitely becomes a plausible attack.

I recommend you read through the following for a thorough explanation:

• Random Number Generator Designs - Andreas Zeller, Stephan Neuhaus [pdf]
• Randomness in Cryptography - Erik Sonnleitner [pdf]
• Applied Cryptography - Bruce Schneier

Answer 2

I don't know the exact implementation used for rand() so I will instead answer a general case.

A popular non-cryptographic random generator is the Linear Congruence Generator. This can be predicted with less than 10 sequential calls*.

*: The upper bound is probably much lower but this was given as a first week assignment in an introductory course on cryptography which says something about how easy they are to break.

Answer 3

Implementations of rand() vary from system to system. I've looked at several of them, and the security varies from godawful to absolutely godawful. You definitely do not want to use rand() for anything cryptographic.

On some systems, one output from rand() is enough to recover the seed and predict all future outputs. On others, you need 2 outputs from rand(). On some systems, if you look at the sequence of outputs from rand()&1, you find that you always get the sequence 0,1,0,1,0,1,... -- in other words, the least significant bits of consecutive outputs from rand() alternate between 0 and 1 (i.e., the outputs from rand() alternate between odd and even).

How insecure is it? As insecure as you could possibly imagine.

Answer 4

CSPRNGs are a subset of PRNGs. A PRNG just needs to be statistically random. A CSPRNG needs to be statistically random and hold up against cryptanalysis to determine past or future values even when a good amount of information is known about initial and/or past values.

All PRNGs are secure enough when you simply need a value that is statistically random (like password salts or random user ids); however, a CSPRNG is necessary when the system that makes use of statistically random values needs to withstand cryptanalysis (use in cryptography).