[Ach] removed outdated info on Linux RNG / haveged

[Aaron Zauner]

* micah <micah at riseup.net> [07/05/2017 17:49:54] wrote:
> Aaron Zauner <azet at azet.org> writes:
> 
> > Also the use of `haveged` is recommended, which is a bad idea as this
> > daemon can create blocking situations during key generation
> > effectively creating a deadlock and thus security problems.
> 
> Can you detail what those blocking cases are? 

I've seen SSH and GPG key generation take up to 15 minutes by
hardcore users of haveged. I question the sanity in doing this. This
may be one of the few cases where I'm happy that OpenSSL uses it's
own weird RNG construction as blocking on key generation for e.g.
session keys would be fatal.

I would have to write benchmarks to demonstrate. But I really have
better things to do than to waste my time on haveged.

> I appreciate these reasons as valid to remove haveged. However, are
> there not any valid cases where haveged is useful, even if it is not
> perfect? If it is producing entropy, even not great entropy, that is
> then mixed into the entropy pool with other sources, isn't it
> essentially impossible to know the output? Even if you are able to know
> the bits that are delivered into the entropy pool, when it is mixed with
> bits you don't know, it can help calculate the result, but it would be
> far from easy.
> 
> I haven't kept up on the newer kernel pool changes, but lets say haveged
> is so bad that someone can pre-determine a predictable pattern matrix it
> will spit out (somehow, it still passes FIPS-140). You spit this data
> into /dev/random, that passes what it gets through
> drivers/char/random.c, which is passed through a SHA hash to then
> actually feeds the kernel entropy pool.

The random char device has been overhauled over the past year.
There've been significant changes, unfortunately the comments at the
top of the file do not reflect these, I recommend reading the actual
source and related LKML (and linux-crypto) discussions.

https://patchwork.kernel.org/patch/9173491/
https://patchwork.kernel.org/patch/9501595/
https://github.com/torvalds/linux/blob/master/drivers/char/random.c#L745

> However, if that data is mixed with other random data from the system,
> are we comfortable accepting that the SHA of that mixture is totally
> unpredictable? If an attacker knows the input to the hash, knows the
> hash function and thus could calculate what the hash output would be,
> they won’t know the beginning pool state, and so cannot know how their
> input affects it when it goes through the mixing method. So all they
> have done is add entropy.

See below.

> 
> The haveged daemon has not been audited, so could have some logic
> mistakes in it, or maybe it has been compromised entirely. But, "the
> fact that an intelligent attacker can construct inputs that will produce
> controlled alterations to the pool's state is not important because we
> don't consider such inputs to contribute any randomness.  The only
> property we need with respect to them is that the attacker can't
> increase his/her knowledge of the pool's state. Since all additions are
> reversible (knowing the final state and the input, you can reconstruct
> the initial state), if an attacker has any uncertainty about the initial
> state, he/she can only shuffle that uncertainty about, but never cause
> any collisions (which would decrease the uncertainty)." (comments from
> random.c).

Again these comments are ancient (like from the 90ties) and do not
reflect the current design. See below.

> Isn't a mixed entropy pool that isn't depleted better than a depleted
> pool that spits out weak results?

Well, unless you're constantly re-seeding your CSPRNG it doesn't
really matter what the current state of the entropy pool is, right?
That's also the reason why the proc interfaces for `poolsize` and
`entropy_avail` have been removed. These values are now hard-coded:

https://github.com/torvalds/linux/blob/master/drivers/char/random.c#L281-L284

There's another thing to consider: entropy attacks. In his blog djb
describes possible attacks which outline that "adding entropy" isn't
necessarily a good thing:

```
This is exactly the opposite of what people tend to do today, namely
adding new entropy all the time. The reason that new entropy is a
problem is that each addition of entropy is a new opportunity for a
malicious entropy source to control "random" outputs—breaking DSA,
leaking secret keys, etc. The conventional wisdom says that hash
outputs can't be controlled; the conventional wisdom is simply
wrong.
```
(via https://blog.cr.yp.to/20140205-entropy.html)

HTH,
Aaron
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: not available
URL: <http://lists.cert.at/pipermail/ach/attachments/20170508/b7361c8c/attachment-0001.sig>