Which PRNG security requirements do I need for key generation

Question

Do I need to worry about "predictability" an an allegedly secure CSPRNG if I am just using it to generate key material from time to time?

Suppose that for some odd reason, I am less trustful today than I was last week of SecRandomCopyBytes() in OS X and iOS and of CryptGenRandom() in Windows. If I am using this for occasional key generation instead of for the basis of a stream, can I get away with just de-biasing them?

What we're doing…

I have an application which occasionally needs to create AES keys, HMAC keys, and IVs for CBC mode. Most of the AES/HMAC key pairs are used for single records, and so a new set of keys need to be generated when a new record is created. When the database is first created a set of very high value master keys are created.

Extra measures for the very high value keys…

Currently, for the master key pairs, we already don't fully trust the operating system provided RNG, and so we actually request 256-bytes of data from that RNG and then hash that down to 512 bits using SHA512. (The first 256 bits are used as an AES key and the second 256 bits are for an HMAC key.)

The intent here is that if there is some unknown (to us) bias in OSs CSPRNG, then grabbing more of those bytes than we need and then hashing them down should wash away any bias that could be hidden in those. (Larger bias, we hope, would have already been detected.)

For all of the other keys, we just the OSs CSPRNG directly.

How many keys, how fast…

Under normal usage, two 32 byte keys will be generated at nearly the same time (AES and HMAC keys, along with a 16 byte IV and a 16 byte item identifier), when a single item is added to the database. But on data import or conversion a few thousand items may be created within a second.

And restating my question in light of the application…

Given the way that I'm using the outputs of that RNGs, do I need to take additional measures (such as XORing against an additional and independent RNG)? Or should I only be worrying about bias in the RNGs?

A second question is whether the de-biasing measure I've described makes sense.

Update: What passes for my threat model (tin-foil hat mode)

I am acknowledging the non-neglible possibility that 'CryptGenRandom()' and 'SecGetRandomBytes()' may have been "adjusted" by the NSA to be weaker in a way only known to the NSA. Certainly some of the users of our application may well consider that "non-neglible" (I no longer put much stock in my own intuitions about what they NSA would or wouldn't do given an opportunity.)

But I also assume that any such adjustment would have to be very subtle. And I imagine that such subtle mischief would have to be.

1. Biasing the output (e.g., making each 16 bytes actually be a hash of only 8 random bytes) of the CSPRNGs, or
2. Making their output easier to predict from other output (e.g., not reseeding as often as claimed and using a weakened PRNG internally)

Note, I am not considering a targeted attack against my application or an individual user of it. Just a generically tampered with CSPRNG to potentially weaken all crypto that has come to depend on those CSPRNGs.

Given my use of the CSPRNG (low volume, typically for an individual key at a time), I am asking whether I can ignore the second (prediction) kind of sabotage.

Update 2:

After doing a bit more homework, I see that my two distinct security properties actually follow from one property, and so my question isn't fully coherent, although I believe that it can be made coherent by defining bias as predictability based on zero prior output.

The accepted answer of "use a KDF" seems correct. The scheme we do use is a KDF, but one of our own devising. I'll be looking at better reviewed, developed KDFs. Note that I'm not looking for a password based KDF. I'm looking for entirely random keys that are not derived from user input.

Answer 1

Your idea is not bad, but not a magic bullet. Any serious vulnerability at the root CSPRNG as you describe is fatal for the system facing any serious attacker.

A serious vulnerability being that the attacker can at will force values or predict (partially) values generated in a particular timeframe.

A serious attacker is an attacker knowing your protocols and schemes - if you're worried about things like this and follow Kerckhoff's principle then you should assume you are indeed facing a serious attacker.

However, I doubt that things like CryptGenRandom face a serious vulnerability as described above. This does however not mean it's immune to things like related key attacks and biases. This is where your idea could potentially help.

If you're slightly distrustful of the underlying RNG and need high volumes, hash it and most potential biases/attacks should disappear.

If you don't require large volumes of seeding data, get a lot of output from the RNG and use a KDF to limit key space attacks.

If you want any kind of security that's worth it's salt get a hardware random number generator.