16
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The vulnerability does not lie with the entropy of the seed itself, so your characterisation of it as secure is moot for the following reasons... $\endgroup$ – Paul Uszak Oct 4 '17 at 11:40
  • 1
    $\begingroup$ If you know, can guess or somehow else recover (consecutive) outputs, there is a decent chance that you can recover the full state of the PRNG and that you can predict all future and past outputs. $\endgroup$ – SEJPM Oct 4 '17 at 11:47
  • 4
    $\begingroup$ from another perspective: here is an example of a potentially exploitable linux feature that allows someone to replace libc's rand with their own. (LD_PRELOAD) $\endgroup$ – Woodrow Barlow Oct 4 '17 at 17:12
  • $\begingroup$ a layman: a non-CSPRNG has output patterns that, while hard to find are 100% predictable if found. $\endgroup$ – dandavis Oct 5 '17 at 20:53
  • 1
    $\begingroup$ @WoodrowBarlow IIRC they can also use that to generate your makeKey function with their own so there's no point trying to defend against that. (Or they can replace your main function. Or they can just run their own program.) $\endgroup$ – immibis Oct 5 '17 at 23:26
34
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is exactly what I wanted, I wasn't thinking about the limited scope of the generator before. $\endgroup$ – Jacob H Oct 4 '17 at 12:19
  • 6
    $\begingroup$ I think the idea of the Standard is to make clear that code which intends to be portable shouldn't rely upon rand being anything better than that. From a conformance standpoint, I don't think the Standard would forbid an implementation which returned 42 for the first 5 calls after srand(8675309) nor one that would returned 42 for the first trillion calls regardless of the value given to srand, though the former might be regarded as being of dubious quality and the latter downright terrible. $\endgroup$ – supercat Oct 4 '17 at 17:08
  • 1
    $\begingroup$ If you give me just three consecutive outputs of this function, I can determine the seed on my Mac within a few minutes at most with close to zero effort and zero cleverness. Now consider that clever attacks might be possible, so changing it to 64 or 256 bit might not help at all. $\endgroup$ – gnasher729 Oct 5 '17 at 16:05
  • $\begingroup$ For this particular code, it's very easy to recover the internal state with only a few observations of the output as it amounts to breaking truncated Linear Congruential Generator and lattice methods are used there, see e.g. this answer: crypto.stackexchange.com/questions/37836/… $\endgroup$ – Krystian Oct 6 '17 at 9:22
8
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This is a great story! I'm not sure if it counts as an answer though :( $\endgroup$ – Almo Oct 5 '17 at 20:35
  • 1
    $\begingroup$ I think it shows that even if your seed was generated securely, the fact that rand() generates numbers on a consistent line of numbers means that any time random data is exposed to the user, they can find your seed, given enough information. Which means that the seed is not in fact secure any longer. This was just a real-world attack aimed at a system which had a secure seed. $\endgroup$ – Ron Penton Oct 5 '17 at 21:22
  • $\begingroup$ If it's written in C++ rather than C, Basic or Fortran, this is not true old-school MUD! Great anyway!!. $\endgroup$ – fgrieu Oct 6 '17 at 6:33
  • $\begingroup$ Could have been C. They both access rand.c and thus the same algo. $\endgroup$ – Ron Penton Oct 7 '17 at 22:58
  • $\begingroup$ That negative gold hack is hilarious. Awesome! $\endgroup$ – Justin Bailey Oct 10 '17 at 17:38
4
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ Actually, there is no mandated rand algorithm in C; there is an example algorithm in the C standard (which is a LCG), however that is not mandated; a particular compiler could use a stronger algorithm (although, it'll always be vulnerable to a brute force search of the srand() seeds...) $\endgroup$ – poncho Oct 4 '17 at 13:10
  • $\begingroup$ you mean a (c) library could implement a stronger algo, which is a separate thing from compilers. $\endgroup$ – Ahmed Masud Oct 5 '17 at 19:20
-1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Gabriele, a single link is not considered an answer on StackExchange. Please at least include a description of the information wihin the linked page for it to become a good answer. $\endgroup$ – Maarten Bodewes May 15 at 22:08

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.