5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ And how many keys are wanted? $\endgroup$ – Paul Uszak May 27 '18 at 20:40
  • $\begingroup$ Edited the question. $\endgroup$ – Petar Donchev May 27 '18 at 20:47
  • $\begingroup$ I actually developed a scheme for this exact scenario some time back, where the system RNG will provide entropy, but is assumed to be compromised, the output is encrypted, then hashed, in a specific manner $\endgroup$ – Richie Frame May 28 '18 at 6:18
  • $\begingroup$ Can some data be stored between generation of the keys, with at least integrity? If not, do we at least have a key index as input of the key generation process? If neither (e.g. in an unspecified VM that can be restored to an earlier state including system RNG), we can't guard against having all the generated keys identical. $\endgroup$ – fgrieu May 28 '18 at 9:12
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A nonce is "a number used only once". If you don't avoid reuse then your derived keys wouldn't necessarily be distinct. $\endgroup$ – Future Security May 27 '18 at 21:40
  • $\begingroup$ There is one detail I omitted. If you mostly trust the OS secure RNG and its entropy sources, then there is one advantage to combining K and its output. And that is if your key K is compromised then it doesn't also compromise derived keys. But if you don't trust that system RNG because it has low entropy or is predictable, then it won't help. You can HMAC a counter and a long string of bits from the system RNG with key K instead of just encrypting the system RNG. $\endgroup$ – Future Security May 27 '18 at 21:49
  • $\begingroup$ -1 because encrypting a data stream and generating a pseudorandom data stream are both equally likely to be done incorrectly. Simply generating a keystream with your assumed safe key and XORing it with the potentially unsafe system RNG is not only secure, it is as secure as the weakest of the two in the worst case scenario, and significantly stronger in the best. $\endgroup$ – forest May 28 '18 at 1:19
  • $\begingroup$ @forest What's the difference between a CSPRNG/DRBG and a keystream generator? I searched for DRBG implementations but I can't find whatever libraries I was thinking of. But my point was if one has an implementation on hand then use it. If the reader knows a DRBG and stream cipher are very closely related then I think they can figure out how to use other primitives like a PRNG. And if neither of those work (and I assumed, probably incorrectly, that high level non-password-based KDFs were at least as rare as PRNGs) then HMAC is easy. $\endgroup$ – Future Security May 28 '18 at 3:32
  • 2
    $\begingroup$ It is sound than an encryption key is used only for its intended purpose; this might even be enforced (that's often the case in HSMs, Java Card, security certification rules). That makes it impossible to directly "Use K to seed a secure PRNG"; the PRNG or its seeding must be built around encryption with K. $\endgroup$ – fgrieu May 28 '18 at 11:02
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I've voted this down as I could well see how encryption of a non-random stream may reveal information to an attacker. OK, the key may not be known, but if two equal blocks of data are encrypted using ECB then there clearly is a leak. And there are better options out there, as the other answers indicate. $\endgroup$ – Maarten Bodewes May 27 '18 at 23:32
  • $\begingroup$ @MaartenBodewes Using ECB is one of the many ways to implement this incorrectly. Hmmm, granted, it's not clear how you would encrypt something without an RNG: how do you get an IV? Mind you, repeated blocks are not a problem here in the sense that they don't make things worse. But anyway I do recommend a better option! $\endgroup$ – Gilles May 27 '18 at 23:36
  • $\begingroup$ @Gilles You can create the IV deterministically from the key, depending on the exact use case. $\endgroup$ – forest May 28 '18 at 1:17
  • $\begingroup$ @forest You can sometimes, but it's pretty dangerous: you need to make sure that you won't use that IV more than once, e.g. of you repeat the procedure after a transient failure. $\endgroup$ – Gilles May 28 '18 at 7:24
3
$\begingroup$

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:-

aes counter rng

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.

$\endgroup$
  • $\begingroup$ Are you sure Windows systems still use SHA1(RC4) as the RNG? According to Microsoft API docs, they stopped doing that in 2008 in favor of NIST 800-90 CTR_DRBG. $\endgroup$ – grawity May 28 '18 at 5:28

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.