How vulnerable is the C rand() in public cryptography protocols?

Question

I just learned about the basics of public cryptography a few weeks ago and I am curious as to why the C rand() function should not be used for crypto schemes. For example, say I want to generate a private key using the C rand() function, along with srand(). Lets say srand() generates a seed based on system time (as in example http://www.cplusplus.com/reference/cstdlib/rand/). Is rand() therefore not acceptably pseudo random because the system time is not random (what if I based the seed on something more random)?

If this is the case, then how does OpenSSL generate random private keys? Moreover, how could an attacker exploit an OpenSSL implementation that uses C rand() the way I specified above?

Thank you.

Answer 1

In the example you linked, the current time (specifically, a value representing the number of seconds elapsed since Jan 1, 1970 UTC) is used as the seed. If an attacker knows which year you generated your key, then that leaves only about 2^25 possible values for the seed --- and therefore only about 2^25 possible values for your key. At this point, he can guess your key pretty easily simply through brute force.

But let's say you find a better way to choose a seed, what then? Well, rand() will try to use this seed to generate a stream of random bits. But those bits won't be truly random, since they're based off a single seed value. So will they be close enough to random for cryptographic purposes? Probably not. Most PRNGs that aren't specifically designed to be cryptographically secure won't be good enough. They're designed for use in simulations and the like, not for times when there are smart and resourceful Bad Guys trying to do Bad Things.

OpenSSL seeds its PRNG using /dev/urandom (I'm not sure what it does on systems where this isn't available), and then uses its own PRNG to generate the random numbers. You can read a somewhat vague description here. (This is the first time I've looked up what OpenSSL is doing, and frankly, I find it a bit frightening --- it looks like someone is trying a roll-your-own-crypto, hash-functions-are-random-oracles approach. But I digress.)

Answer 2

rand() is bad because it's not a random function - not even a mediocre one. Every library, operating system, yahoo with a keyboard, can write his own rand and get away with it. The purpose of rand is to give output that looks random enough to be used in non-critical applications, usually with an LCG.

Once in a blue moon you might come across some library that uses a sound algorithm for rand but there's simply no guarantee that this will ever happen. Thus, you are much more likely to run into a 15-liner hack than a sophisticated CSPRNG - and that's OK. rand() was never meant to be crypto-grade.

Using a truly random seed means the adversary will have a problem figuring out the first output; from there on out the seed makes no difference.

Answer 3

As Steth stated before, using system time as seed in cryptographic implementations is terrible idea for any PRNG because this may be simply very predictable. There are better solutions based on noise generated by device drivers in the system (see man urandom)

What you want from PRNG in cryptography is to be uniform and unpredictable, so the entropy would be as much as possible and given any number of output, you could not, without knowing the seed, predict the next value (In theory that means the probability that you guess next bit will not be grater than 1/2 + e where e is negligible for any efficient algorithm).
With c rand() there is this thing, that this is not such uniform. I don't remember exact values, but I think that it started to give uniform data not straight away but after first few hundred bits, and then after few kb of data it started to bias again. Theoretically If you are aware of all nuances that may happen you could adopt c rand() to your purposes (for example skipping first few hundreds of bits and if you approach the number of data where they start to be non uniform, reseed), but it needs a deep knowledge of PRNGs to do this safe. This is why there are in crypto libraries Cryptographic Secure PRNGs that you can use and be sure that the data you get are suitable for cryptographic purposes.
Of course you can break them too for example using localtime to seed ;).