I get the feeling from the discussion on /dev/random vs. alternatives
(in particular, Yarrow) that not all the commenters have looked at the
code for /dev/random.
Let's see...
1. Estimating entropy. Yes, that's the hard one. It's orthogonal
from everything else. /dev/random has a fairly simple approach;
Yarrow is more complex.
It's not clear which is better. If there's reason to worry about the
one in /dev/random, a good solution would be to include the one from
Yarrow and use the smaller of the two answers.
2. Pool size. /dev/random has a fairly small pool normally but can be
made to use a bigger one. Yarrow argues that it makes no sense to use
a pool larger than N bits if an N bit mixing function is used, so it
uses a 160 bit pool given that it uses SHA-1. I can see that this
argument makes sense. (That suggests that the notion of increasing
the /dev/random pool size is not really useful.)
3. /dev/random blocks after delivering as many bits of output as its
current entropy estimate.
Right. But /dev/urandom does not, and neither does Yarrow. In other
words, Yarrow is like /dev/urandom in that respect; if people feel
Yarrow is an example of a good generator, they can't very well use the
blocking behavior of /dev/random as additional ammo! Conversely, if
you believe some applications really require that blocking behavior,
it follows you would not want to use Yarrow in its current form.
Incidentally, if you adopt Scheier's comment that the entropy pool
size should be bounded by the hash value length, the blocking behavior
of /dev/random doesn't make much sense anymore.
Also, Scheier argues that a conservative upper bound on how many bits
to extract before reseeding is 2^(n/3), i.e., 2^53 bits in the SHA-1
case... although he doesn't prevent you from using smaller numbers.
4. Questions/concerns about the cryptographic primitives used. This
is where I wonder what people have looked at...
Yarrow uses SHA-1 as a mixing function. /dev/random uses either SHA-1
or MD5 as a mixing function. What's the issue again?
Note also that /dev/random doesn't give you the current hash state as
its output; instead it "folds" it (high half xor low half) on the
ultra-conservative principle that knowing a particular 160-bit SHA-1
output value might maybe give you some insight in what subsequent
iterations of SHA-1 would produce. I don't believe that's currently
thought to be the case, but even if it were, /dev/random doesn't
suffer from it. I don't remember what Yarrow does in this area.
5. "Catastrophic reseeding" to recover from state compromise.
It's been argued that this is a rather extravagant concern. I agree
to a point... if someone can read kernel memory, you probably have
other more immediate concerns.
On the other hand, it's a really good idea to have the property that
compromise at time T doesn't give the attacker a way in for time > T+n
for suitable (reasonably small) n. Also, note that the state
compromise is a passive attack, it may go unnoticed more readily than,
say, a trojan horse patch to the kernel.
So while this attack is a bit of a stretch, defending against it is
really easy. It's worth doing.
6. Inadequate entropy sources for certain classes of box.
This is common to both. On diskless UI-less boxes, neither Yarrow nor
/dev/random currently have any entropy inputs.
We've discussed this before; I've recommended adding fine grained (CPU
clock cycle few low order bits) network packet timing as a source.
There's been some scepticism expressed, rightly so; I've done
comparable things in the past and feel comfortable that this one will
work out, but I would definitely expect others to want to do their own
analysis. Having a Yarrow-style entropy analyzer might help here.
----------------
In summary:
I think (6) is the biggest issue. Items (1) and (5) suggests pieces
that could be adopted from Yarrow and put into /dev/random.
I see no valid argument that there is anything major wrong with the
current generator, nor that replacing it with Yarrow would be a good
thing at all. In particular, I disagree with Sandy's comment that
"Yarrow's two-stage design... offers significant advantages over the
one-stage design in /dev/random". Apart from the long shot (iterative
guessing attack) and possibly some nuances relating to entropy
estimates, I don't see any significant difference in strength between
the two.
paul
