The Linux /dev/random driver (and its *BSD cousins) come up for
discussion periodically on various lists. Some old discussions
are archived at: http://www.openpgp.net/random/
Alternate designs also get discussed, mainly Counterpane's
Yarrow: http://www.counterpane.com/yarrow.html
I'm thinking of trying to improve the Linux code, using ideas
from Yarrow, and am seeking comment before implementing my
ideas.
The Linux driver has a large entropy pool (default 512 bytes,
but can be increased by changing a #define) and fairly clever
tricks to mix entropy into the pool effectively without much
overhead.
All output is generated by hashing the pool. Two devices are
supported.
/dev/random always gives top-grade random numbers. If
there is not enough entropy, it blocks until there is.
/dev/urandom always delivers without blocking. When there
is not enough entropy, it becomes an iterative hash.
Since both use the same entropy pool, heavy use of /dev/urandom
may deplete the pool and block /dev/random. This is the problem
I want to solve.
Of course, it is not a problem if every application that needs
lots of random values has its own good pseudo-random generator,
seeded from one of the above devices. Or even if someone writes
a randomness daemon along those lines and everyone uses it.
However, I feel the right place to solve this is in the driver.
Yarrow is different from the Linux driver in several ways, of
which these seem critical:
The entropy accumulation is much simpler and uses a far
smaller buffer, just two 160-bit hash contexts. 40 bytes
versus /dev/random's minimum of 512.
The output of the hash is not used directly, but rather
used to seed the key for a block cipher running in
counter mode. There is considerable analysis, both in
the Yarrow paper and elsewhere, tending to show that
this mode is secure.
The Yarrow paper suggests rules for re-keying, based
on an analysis of potential attacks.
One might argue that /dev/random should just be replaced with
some variant of Yarrow. I'm not inclined to do that; Yarrow
is relatively new and perhaps insufficiently analyzed. I'm
proposing a much less drastic change.
Keep all of the existing random driver except the parts that
generate output for /dev/urandom. Replace those with a block
cipher in counter mode, using Yarrow-ish rekeying rules.
That is, change /dev/urandom to a Yarrow-ish two-stage design
without changing /dev/random at all.
I'm inclined to use Rijndael as the block cipher.
Rijndael is more efficient with larger block sizes; it takes
10 rounds for a 128-bit block and only 14 for 256. This might
suggest we use a 256-bit block size. I'm not certain this is a
good plan, though. Analysis of Rijndael has focused on the
128-bit blocks used in AES. The cipher supports 256-bit blocks,
but the security of that is less clear.
I'm inclined to be conservative on this. Use the well-analyzed
128-bit block size.
The Yarrow paper suggests the overall security is the minimum
of the hash output size and the block cipher key size. I'd like
to go to the 192-bit Tiger hash:
http://www.cs.technion.ac.il/~biham/Reports/Tiger/
and use 192-bit Rijndael keys, but that is too many changes at
once. For now, I'll use 128-bit keys, and the MD5 or SHA hashes
in the existing driver.
I'm inclined to think all state within the generator should be
randomly initialized and never zeroed. e.g.
Initialize the counter randomly, not starting at one.
(Should we increment it by some number other than one
so more bits change on each round, or is this not worth
the trouble?)
Make re-keying XOR with the existing round keys rather
than overwriting them. Even if an attacker knows the key
used to re-key, he does not learn the new round keys.
Whatever the block size, we should not send all the cipher's output
bits to the user. Some should be used for feedback. whatever the
block size, I'd want to send at least 32 bits back into the
/dev/random pool every round and XOR another 32 into one of the
round keys.
