Purpose of folding a digest in half

Question

The Linux kernel's random driver generates randomness by hashing an entropy pool using SHA-1. From the driver's source, the SHA-1 hash is apparently folded in half before being returned:

/*
 * In case the hash function has some recognizable output
 * pattern, we fold it in half. Thus, we always feed back
 * twice as much data as we output.
 */
hash.w[0] ^= hash.w[3];
hash.w[1] ^= hash.w[4];
hash.w[2] ^= rol32(hash.w[2], 16);

The reasoning in the comment strikes me as a bit odd. Why would there be any expectation that SHA-1 would have a pattern in output, much less one where folding the hash in half would solve the issue? It looks to me like the kernel developers are attempting to design a worthless "hash" to try to solve some supposed problem with SHA-1. This behavior even goes back to 2003 (and possibly before), in kernel 2.4. Is there any possible advantage to this behavior, or is it wholly unnecessary?

Answer 1

Look at the rest of the code around it. The hash value gets used twice: once to feed back into the pool and once as an output. Ideally those two would be independent, but the requirement is that an attacker who sees the output is not be able to tell what went into the pool.

Another option would be to halve the hash, throw half of it back in and the other half out. However, in that case the data being fed back would be just 80 bits - short enough for a brute force attack without knowing the output. Hence the comment earlier in the file: "By mixing at least a SHA1 worth of hash data back, we make brute-forcing the feedback as hard as brute-forcing the hash."

So basically the XOR is used as a cheap one way function. Is it any better than taking just the first half and throwing both back in the pool? SHA-1 would have to be pretty broken for that to make any difference.

Then again, this code to fold in half is actually from a time when using SHA-1 was an option and MD5 the default (early-mid 90s, not sure exactly when). So distrusting the hash was not nearly as paranoid as it seems today. Later patches have left it in because it's "harmless".

Answer 2

I think that it's a belt and braces approach to using SHA-1. You're right in that function has not yet been inverted directly, although collisions can now be made (with some effort).

There is also java.SecureRandom() though, which is Java's SUN CSPRNG implementation called SHA1PRNG. It's based on a seed + counter fed through SHA-1, and it too only outputs 64 bits from the available 160 due to unspecified security concerns which I read somewhere. They don't fold in this case, they chuck the rest away. I can't find that link now, but I have someone else's pseudo code of part of SHA1PRNG:-

I can't think of any other reason. But to be honest, I'd probably do exactly the same if I was forced to use a state or pool for a TRNG.