Encrypting RNG output

Question

Under the following premise:

• I need to generate multiple symmetric keys;

• I cannot be sure about the quality of local system RNG;

• I already have a strong key K (generated by other means / elsewhere).

Does it make sense to encrypt the output of system RNG with K (or some derivation of it) with the purpose of strengthening generated keys. More generally, can I strengthen the output of the RNG using K?

Clarifications:

Length - let's say that the entropy of K is 128 bit. Number of keys - multiple, but not numerous (several or dozens, not more).

Second edit:

More clarifications and comment:

Persistent (and secure, as long as the whole system is not compromised) storage is available, so a sequential IV can be implemented.

I am starting to have doubts about the idea that RNG may be flaky while the system is still not compromised, but initially I assumed that RNG quality is not black and white and because it is easy to provide K, generated keys can be strengthened.

Apropos, I can deliver 256 bits K, so I can really just use it as seed for a PRNG and forget about all else. In any way, a compromise on the source of K is total falldown, so this starts to look like a straightforward option.

Answer 1

Don't even use the system RNG if you don't trust it but do trust K.

• Use K to seed a secure PRNG; then generate keys from that RNG instead. (For example, ChaCha. Not RC4, because it's obsolete and insecure, but other secure stream ciphers work.)
• Or use K with a key derivation function. If you don't need to follow standards then use HMAC with K for its key. Every time you need a symmetric key up to 512 bits long, increment a counter, HMAC the counter value, then take however many bits you need from the output.

---

Why?

You could encrypt the output of an RNG. Symmetric key encryption is supposed to produce ciphertext which is indistinguishable from a uniform random bit source. Encrypting a random or pseudorandom sequence isn't any better than encrypting some simple non-repeating sequence like a counter.

However, you could mess up the encryption by reusing nonces, using a block size that's too small, using a bad algorithm, or using a buggy implementation. I say don't use the system RNG if you don't trust it because encrypting its output is at best equal to the alternatives I listed.

If your system RNG is biased or isn't seeded with enough entropy, then you have the problem of nonce reuse if you encrypt with a (not sufficiently) random IV. If you can prevent nonce reuse with a deterministic algorithm, then you can also prevent nonce reuse with secure PRNG or maintain a counter for the HMAC construct I mentioned.

You should be able to trust your operating system's secure RNG. But if you don't have access to one or you know it wasn't seeded with enough energy then that is reason to use something else.

You can't really make a better unpredictable non-deterministic RNG than what the OS can provide you. Userland attempts at entropy-gathering (non-deterministic) RNG algorithms don't have a good track record.

If you have a high entropy key, a secure algorithm, and ability to prevent nonce reuse, then PRNG/KDF output will be good.

Answer 2

If implemented correctly, which is a strong assumption, this is safe. The result of encrypting something with a secret key is supposed to be indistinguishable from random. “Implemented correctly” includes side channel resistance. Using K for this increases the risk of leaking K through a side channel such as timing.

You will have a problem when encrypting, however: you'll need to generate an IV for your encryption scheme, and you don't trust the RNG. So CBC mode is out, for example (it requires a uniform IV). CTR mode is ok if you can ensure that the counter won't repeat (see below).

However, in most scenarios, you won't gain anything. It is rare for an attacker to be able to compromise the system RNG but not the rest of the system. If you fear that the system RNG has too little entropy, adding a secret key into the mix won't necessarily save you. The problem with K is that it is the same every time. If your application or device restarts during the key generation, will you know it when you restart? Are you sure that K won't be used on two different devices? If the answer to both questions is yes, then you can use K together with some value (not necessarily secret) that does not repeat even after a restart. This can be an RNG output, if you have rewritable storage (any decent OS will do that for you if you aren't on an embedded device where rewritable storage has limitations, so if you aren't on such embedded device, don't bother and just use the system RNG). If you don't have rewritable storage but you trust the time not to go backwards, you can use the clock together with K. If not, K won't necessarily save you, because it won't eliminate the risk of identical keys if your adversary manages to cause the RNG seed to repeat.

Rather than build your own construction, I recommend using K plus some fixed label (to avoid any accidental collisions with other uses of K) as extra inputs to the seeding function of a PRNG. Of course do seed the PRNG with the system RNG as well.

Once again, do this only if you have serious doubts about the security of the system RNG and you know that the way your application is used is not vulnerable to a repeat of the system RNG state after a restart or across multiple devices with the same K. With a decent system RNG, the risks of getting this wrong outweigh the benefits you might get.

Answer 3

Encrypting RNG output was an extremely common technique used in millions of Windows machines up to Vista. Microsoft's CryptGenRandom was basically SHA-1(RC4). So the hash function fortified the (now) broken RC4 algorithm. You can do the same if your local system RNG is poor, hashing a lengthy output sequence. The equivalent would be to use AES-128-ECB to encrypt groups of 16 bytes from the RNG, using K. It's difficult though to quantify how bad the RNG would have to be to negate this fortification technique. Clearly encrypting a simple linear congruential generator like RANDU would be foolish. It's internal state size is woefully inadequate against brute force attacks.

This is an alternative and safer construction:-

You ignore the RNG, and create your own cryptographic ally secure one based on AES-128-ECB. There is simply a state counter that you just increment per 128 bit output cycle.

Some will argue that you should use common library functions for such key production and there is some merit in this. However, the ECB style of AES is so simple that if you can code a 16 byte counter (about 5 lines of code), you can't go wrong(!) I'll regret this.

Note 1. This only creates pseudo random keys. They are very very good, but not as good as truly random ones. If K is compromised, all of K's children are compromised as per Kerckhoffs' principle.

Note 2. See Which PRNG security requirements do I need for key generation for further insight along similar lines.