Hacker News Reader

Comment by colmmacc | Hacker News Reader

The IETF TLS working group has included a relevant suggestion in the TLS1.3 draft RFC:

https://github.com/tlswg/tls13-spec/commit/465de0e189b2b5909...

The idea is simple: use two different instances of a secure RNG. One for "public" material that can be seen on the wire, which would include server and client random data. Another for "secret" material such as the private parts of DH parameters. With that set up, it's hard to impossible for DUAL_EC style attacks to work. Even if the RNG is "broken", there's nothing public to go-on to hint at what the state might be.

We've been doing this in Amazon s2n since the first version, and I believe BouncyCastle does it too. Hopefully we'll see more implementations pick up the technique.

View on HN

> use two different instances of a secure RNG. One for "public" material that can be seen on the wire, which would include server and client random data. Another for "secret" material such as the private parts of DH parameters.

Wow that's an incredibly simple solution. I feel like that general approach (where possible split client facing vs internal states) could be applied to many other places as well.

Are there any problems with the additional initial entropy requirements to maintain separate RNGs (two per connection)? Or is it globally static, internal vs external?

RNG state entropy is not a resource that is exhausted by using the RNG.

But even if it were, and assuming entropy limitations are relevant in this context (which I'd argue they are not), the total entropy requirement would not change by merely deriving the same set of values in another way. You might only need more bytes (!= entropy) from your root RNG to seed two separate RNGs. In which case you could just stretch the same number of bytes you'd normally request using e.g. HKDF.

But again, it doesn't make much sense to think of entropy as something you can count or use up, really. There is no way to tell, and just a few bits (say 128) of entropy would be sufficient for almost anything...

That’s what I’m referring to, retrieving more entropy from the system source to juice the initial state of the RNG.

If you have a separate RNG per connection (or two per connection) that requires separate init, each connection would drain the system pool slightly. That’d be in constraint two having two static pools shared for all connections.

No, what they're saying is that the notion that you can "drain" the system pool is an urban legend created by a bad Linux man page. In reality, entropy isn't really ever "drained" from the system entropy pool.

Expanding on this, for anyone who wants to read more, http://www.2uo.de/myths-about-urandom/ is a good resource.

The pool's estimated isn't drained, but its "objective entropy" is reduced; ie. the amount of state leaked to the outside goes up. Of course, practically you can't recover that information within a usable timespan, so it's academic.

Actually, now I sort of wonder what would happen if you encrypted a quantum superposition so that to determine which branch was taken would require reversing an operation using, at the lower bound, more computation than is available in the universe. Would it hold, or collapse/decohere?

> RNG state entropy is not a resource that is exhausted by using the RNG.

I thought so too, but a couple of years ago I was writing a comment on LWN (https://lwn.net/Articles/642839/) and it suddenly clicked.

Entropy is a measure of unpredictability, that is, if you have 32 bits of entropy, there are 2^32 possible states. Suppose you generate an 8-bit value from that, assuming a function which uniformly mixes your state. For each of the possible 256 output values, on average 2^24 of the possible states would generate the same output value. Therefore, once you know the output value, you can discard the other 2^32 - 2^24 possibilities; only 2^24 possible states remain, so you now have only 24 bits of entropy left.

The reason this is not a problem in practice is that, since the output function is one-way, an attacker would have to enumerate all possible states to find which ones would generate the same outputs. This becomes unfeasible once you have enough entropy in your state (256 bits or more).

(The whole trick with Dual-EC was that, if you know the secret key, the output function is not one-way. Supposedly, either the key was discarded once generated, or the points were generated at random and not from a secret key, but nobody really believes that.)

In reality, all mainstream CSPRNGs are essentially just stream cipher keystreams (PRFs). Some of them run AES in CTR mode, some of them run HMAC. The commonality is that the "raw entropy" (from system timings and whatnot) is run through what is essentially a KDF and fed to the PRF.

To believe that tapping 128 bits of "entropy" from /dev/urandom is equivalent to "depleting" 128 bit of entropy from the "system entropy pool", you must also believe that encrypting 16 bytes with AES-CTR somehow materially weakens the key.

Obviously, that's not happening. We don't "run out of key" as we encrypt with a PRF. As Dan Bernstein puts it, securely expanding small secrets into very, very long secrets of one of the core functions of cryptography. Look at the key schedule of any block cipher for a very basic example. We reject ciphers in designs based on their inability to encrypt 2^64 blocks worth of data without potentially creating artifacts.

> To believe that tapping 128 bits of "entropy" from /dev/urandom is equivalent to "depleting" 128 bit of entropy from the "system entropy pool", you must also believe that encrypting 16 bytes with AES-CTR somehow materially weakens the key.

As long as none of the 128 bits of the plaintext is known, we're also adding 128 bits of unpredictability, so the net result is zero.

If some of the plaintext bits are known, in theory the unpredictability should decrease. For an extreme example: if all 128 bits of plaintext are known, and all 128 bits of ciphertext are also known, there should be a single 128 bit AES key that maps that input to that output, so the entropy left in the key would be zero.

However, there is no known way to find that single key other than through a brute force search through all the 2^128 keys, so it's still safe. That also applies to the CSPRNGs: even if the entropy has decreased to zero, as long as an attacker has to brute force through a large enough number of possible states to take advantage of that fact, it's safe. It doesn't change the fact that, when the entropy left is zero, there is a single state which could lead to the observed outputs.

Yes, this means that after the entropy in the CSPRNG has passed the point where brute force is no longer viable, the amount of entropy left on the pool becomes a useless measurement. What matters is how much work an attacker would have to do, not how much theoretical entropy is left.

I've had a couple beers and am having trouble holding all these paragraphs in my head.

But, at the risk of being repetitive, because maybe this simplifies things:

Generate a random 128 bit key by hashing something. This is what the Linux KRNG does with raw entropy.

Initialize AES-128 with that key and start running it in CTR mode. Encrypt a file with known contents, like /etc/ttys. That's ~1300 bytes of known plaintext.

Now, recover the AES-CTR keystream (just XOR /etc/ttys against the AES-CTR ciphertext).

Is it your contention that, having done that, you've placed yourself closer to guessing the underlying 128 bit AES key?

If not, you see also why drawing out 1300 bytes of Linux KRNG randomness doesn't help you predict future values. The randomness you read from /dev/urandom is fundamentally just PRF keystream.

If you could look at AES-CTR keystream and use it to make an advantaged guess at the underlying AES key, AES would be grievously broken.

> If some of the plaintext bits are known, in theory the unpredictability should decrease. For an extreme example: if all 128 bits of plaintext are known, and all 128 bits of ciphertext are also known, there should be a single 128 bit AES key that maps that input to that output, so the entropy left in the key would be zero.

This is correct if either:

1. the planet held enough energy to perform a brute-force attack on a 128-bit key (it doesn't: https://en.wikipedia.org/wiki/Landauer%27s_principle ) and such an attack could be performed while the protected information was still relevant. Or:

2. You have an algorithmic break on AES that allows the attack to be carried massively more efficiently, enough to make it practical.

Cryptographers refer to this situation as 'winning'.

> For an extreme example: if all 128 bits of plaintext are known, and all 128 bits of ciphertext are also known, there should be a single 128 bit AES key that maps that input to that output, so the entropy left in the key would be zero.

Abstracting away a little bit. What is a block cipher? A bijective mapping between identical sets uniquely identified by the key. This makes it a permutation; and a good cipher says (among other things), that every key yields a unique permutation.

This doesn't mean that the mapping of one value identifies the key (i.e. the permutation itself). If the mapping for each key were truly random, then it would be essentially impossibly unlikely to end up not sharing a number of individual plain->cipher mappings between different keys.

You can do this as a little experiment using a small block size, 4 bits or so.

Reply on news.ycombinator.com