How can C rand() be exploited if a secure seed is used?

Question

I've just started doing a research project on CSPRNGs and I would like to know what kind of vulnerabilities a regular PRNG has with a secure seed. For example, if I generate a random number using LavaRnd to seed srand(), then generate some big key with rand(), what can an attacker do to resolve that key, or otherwise find critical information?

I have seen a lot of people with similar questions, but the answer usually boils down to "the result will not have enough randomness", then there is a lot of hand-waving about the specifics. But what does that mean for a real world implementation? What actual vulnerabilities or attacks can be mounted on an insecure pseudorandom number generator using a secure seed?

Answer 1

The ISO/IEC 9899:1990 edition of the C standard contains:

EXAMPLE     The following functions define a portable implementation of rand and srand.

static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}

The state of this generator is entirely characterized by the 31 low-order bits of variable next. If we "generate a random number using LavaRnd to seed srand(), then generate some big key with rand()" as in the question, then only $2^{31}=2147483648$ outcomes (at most) are possible for the "big key", determined entirely by the 31 low-order bits of input seed.

That then allows an attack that tries all these keys. If testing a key requires $2^{20}$ clock cycles (about a million) of a $2^3$-core CPU running at $2^{31}$ Hz, the attack is expected to last $2^{31+20-3-31-1}=2^{16}=65536$ seconds, that is less than a day.

Depending on what's done with the "big key", there might be much faster attacks. For example, that would be the case if rand() is also used to generate the Initialisation Vector, which customarily is at the start of enciphered messages. A simple attack can find the value of next from three consecutive values of rand(). That takes literally less than the blink of an eye, and allows finding effortlessly all past and future output of rand() not interrupted by srand().

On the other hand, perhaps the above $2^{20}$ cycles estimation is way too low (that could be the case for an RSA key). But by any measure, a 31-bit keyspace is farther waaaaay too low. Currently, the threshold of practical security is somewhere near 80-bit, give or take 20. 128 is considered fine till 2030, except if one believes in fairies or quantum computers becoming usable for cryptanalysis any time soon.

Answer 2

I once played this online game, it was an old-school MUD. You log in, chat, kill some goblins.

It had a casino. You go into the casino and you bet X gold, and there was a 40% chance you win double your bet. Obviously in the long run, the casino will always win, right?

But here's the thing. I knew the game was written in C++, and I knew the rand() algorithm.

So here's what I would do. I went into the casino, and bet 1 gold about 10 times in a row, as fast as possible. if I lost, I recorded a 0, if I won I recorded a 1.

Then I go and enter that data into a program I wrote. It goes through all of the random numbers in the rand() sequence, starting from seed 0. If it generated a number less than 0.4, that was a 0. If it was 0.4 through 1.0, then it was a 1. And I compared the sequence in the chain to the sequence I recorded in the casino. If all 10 bits match, bingo. I found the current seed that the game was using.

Of course, this took a minute or so to calculate, so as people were mucking about killing goblins, the game continued along for another few hundred seeds as it generated more numbers. So I did my test again, another 10 rapid-fire bets, another 10 gold down the drain. Enter my second sequence into the program, and this time it finds the current seed within microseconds (because we're starting from the seed we found the last time), and this time it prints out the next 30 or so bets, whether they're going to be winners or losers.

So what I do is I bet 1 if the next number is going to lose. Then I bet half my money if it's going to win. Blamo, instantly increased money by 150%. Repeat, repeat, repeat, I suddenly have an exponentially-growing bank account.

Now there's a few problems with this method. Number one, if the game generated a random number inbetween your initial "probes" of 10 bets, it wouldn't find a sequence. Not a big deal, just do it again. You'll find one eventually.

Second problem; if you're not fast, the game will generate a new random number somewhere else and throw off your sequence when you're betting for real. I lost a lot of money in some of those instances. So this is where macros in my telnet client really helped.

Third problem... The game used 32-bit ints to store money. After about 100 bets, you end up overflowing the counter. I surpassed 2 billion gold and found myself with negative 2 billion gold. And the game wasn't programmed to ever handle negative gold; but the number parsing system could.

So I went around and started giving people negative amounts of gold. Hey Zethryr, here's negative one million! Boom, his whole life savings wiped out in an instant.

It was pretty hilarious, but it highlights why pseudo-random numbers can be dangerous. If there's any way for the random numbers to be surfaced to the user on a regular basis (ie: the bet command), then they're going to be able to somewhat easily figure out where in the rand() seed chain your program currently is. And once they do that, they can gain an edge in your system by guessing what the next random number is.

Sometimes web developers will generate record ID's, salt strings, and temporary passwords based on a random number generator. If they use a pseudo-RNG, then an attacker can create a few accounts or records in a row and examine their ID number, probably encoded into the URL. Then they can guess the ID's of other people's accounts or records, or even their passwords. And that can be pretty dangerous.

Answer 3

Please check how the rand() is implemented as LCG. The int value effectively exposes most of the bits from the internal state.

Having two subsequent values (and a little brute-forcing) would completely recover the original seed and allow predicting future values.

There was a question on this forum about it already (in Java) and it was surprising for me as well how easy it was.

Answer 4

i published at this address Random number prediction a method to reduce the keyspace of attack of rand() generated sequence; there is also the possibility to guess the seed in a similar method.