1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Cargo cult voodoo. Doesn't accomplish anything meaningful. $\endgroup$
    – Squeamish Ossifrage
    Mar 18, 2018 at 3:47

2 Answers 2

Reset to default
2
$\begingroup$

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".

Improve this answer
$\endgroup$
2
  • $\begingroup$ So it's folding it in half, mixing the 160 bits back into the pool, and giving out the 80 bits? I see that the function outputs 80 bits, as EXTRACT_BUF is 10 (bytes). What I don't get is the "in case [...] recognizable outputs" part. If it's simply designed for feeding it back to prevent backtracking attacks, why not simply say that? Saying that "if" it has some recognizable output is misleading. $\endgroup$
    – forest ♦
    Mar 18, 2018 at 14:00
  • 1
    $\begingroup$ @forest, outputting less than mixed is for resistance. The folding (rather than truncation) is in case the hash is bad.... Which is not a good reason to do it (today at least). $\endgroup$
    – otus
    Mar 18, 2018 at 15:42
-1
$\begingroup$

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:-

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Collisions aren't relevant to the way it is used in a PRNG. Why would you do it yourself? What do you expect it could accomplish? And in what case would SHA-1 be broken, but not if it's folded with itself? $\endgroup$
    – forest ♦
    Mar 18, 2018 at 3:58
  • $\begingroup$ @forest Ah, that's not my text. It's a screen grab from somewhere. Your random.c fold isn't a PRNG, it's a TRNG in /dev/random which itself is a very weird TRNG as it has stirred pools (red flag!). I have no other explanation but Sun Corporation did the same. I'm not defending them. Do you have a better idea than Sun or Torvalds? $\endgroup$
    – Paul Uszak
    Mar 18, 2018 at 5:03
  • $\begingroup$ It's not a TRNG, it's a CSPRNG using interrupt timing intervals for entropy. I'm not sure why you say stirring the pool is a red flag though (it's obviously necessary if you don't want repeating output). And I believe the better idea would be to use the entire hash, not half of it folded. As for why Sun uses it, it could be to serve a different purpose (defeats length extension attacks, for example, as it makes it so the internal state is larger than the output). $\endgroup$
    – forest ♦
    Mar 18, 2018 at 5:07
  • $\begingroup$ I'm still interested to know what you mean by a stirred pool being a red flag. I suspect it is a communication issue (what I mean by "stirred pool" is an entropy pool that adds entropy by permuting it, e.g. with XOR, rotations, etc). $\endgroup$
    – forest ♦
    Mar 25, 2018 at 21:56
  • $\begingroup$ @forest Actually it's my communication issue. /dev/random is a weird creature in that it sits between a TRNG and a PRNG, but is widely regarded as a TRNG by those who do not take due regard of the input entropy rate. The fact that pools are even required is testament to this, hence the red flag thing. A gold standard TRNG has input entropy >> output entropy and has no need of stirring any pools. Similarly FORTUNA takes this to ridiculous degrees IMHO. Unfortunately /dev/random has no accurately measured input entropy rate, hence the fudge and hybrid designation. And flag. $\endgroup$
    – Paul Uszak
    Mar 25, 2018 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.