Sandy Harris
Sun, 1 Aug 1999 19:00:54 -0700
In an ealier message I wrote: > Conclusions I've reached that I hope there's agreement on: > > More analysis is needed, especially in the area of how > to estimate input entropy. > [SNIP] > > Yarrow's two-stage design, where the output from > hashing the pool seeds a pseudo-random number > generator based on a strong block cipher, offers > significant advantages over the one-stage design > in /dev/random which delivers hash results as > output. ... > [SNIP] > > /dev/random should become two-stage, ... > > I'll make a detailed proposal for that in > another post. So here I'll assume agreement on the above and outline the design I've come up with, more as a starting point for further discussion than in hopes I've got it right. I'll ignore questions of inputs to the pool here. /dev/random has working code for that, based on design assumptions that seem plausible. The question, then is how best to make it into a two-stage design. Mainly, choose a block cipher and modify the hashing to suit. The obvious cipher to chose would be one of the AES candidates with a 256-bit key. Offhand, I'd say Rijndael, but this needs detailed analysis, especially in the area of re-keying costs. Twofish, Serpent, and CAST-256 are all freely available as well. A 256-bit key would be nice, but the Yarrow paper says security is limited to min(k,m) for cipher keysize k and hash output size m. I think that can be fixed. Consider a large entropy pool, with N blocks of 512 bytes available for hashing. Yarrow and /dev/random each hash the whole thing every time, Yarrow to re-key and /dev/random to generate output. I doubt this is necessary when the pool contains plenty of entropy. In that case, you can safely produce output after every block, at least in a two-stage design where hashing outputs are never made directly visible to the attacker. With output after every block, the limit on delivered security becomes min(k,Nm) and we can use a 256-bit key with some hope of actually delivering 256-bit security. Only when the pool has m bits of entropy per block, of course. I'd like to use Tiger: http://www.cs.technion.ac.il/~biham/Reports/Tiger/ as the hash for the revised /dev/random. It is freely available, apparently secure, faster than MD5 or SHA-1 on at least some machines, and produces a 192-bit output. The one disadvantage of Tiger is that it uses 8K bytes of S-boxes, quite a lot for a kernel device driver. The /dev/random author says he limited the default pool to 512 bytes to save kernel memory. I'm not sure my suggestion, with Tiger plus a large pool, is plausible there. One way to reduce the load on kernel memory would be to find a way to make Tiger use the CAST-128 s-boxes. They're the right total size, though a different shape, and they'll be in some kernels anyway if we add CAST-128 to the FreeS/WAN code, which I think we should. The HMACs used in IPSEC use 128 or 160-bit hashes, but only 96 bits are actually sent and used for authentication. This makes an attack on the hashes harder. Currently, if I've understood right, Yarrow does not feed hash output back into the pool and /dev/random feeds back the same bytes it outputs. My suggestion, using Tiger: When you have plenty of entropy, use 128 bits of the hash for rekeying and stir the other 64 back into the pool. When entropy gets lower, reverse the numbers and produce only 64 bits of output per block hashed, stirring 128 back into the pool. This is intended both to make attacking the hash harder, since the attacker (even if he's broken the block cipher!) does not see all hash output, and to make iterative guessing attacks harder. Whether you're taking 128 or 64 bits per block, the minimum rekeying operation is to change 128 bits of the block cipher key. Treat a call to /dev/random as if it were a Yarrow explicit_reseed() followed by a call to /dev/urandom. Reseed before calculating any output and set a flag so that another reseed occurs shortly after.