Messages in this thread | | | Date | Mon, 23 Sep 2013 00:33:12 -0400 | From | Theodore Ts'o <> | Subject | Re: [PATCH, RFC 08/12] random: mix in architectural randomness earlier in extract_buf() |
| |
On Sun, Sep 22, 2013 at 09:11:58PM -0700, H. Peter Anvin wrote: > > This doesn't mix in across the entire width of the hash (my original > motivation for putting this at the end was to do it after the hash is > folded in half -- which is still believe is cryptographically dubious, > but please don't take my word for it, as I'm not a professional > cryptographer.) As such, this change should *probably* have > EXTRACT_SIZE changed to 2*EXTRACT_SIZE (or simply "20") both in the for > loop and in the declaration of the union.
Agreed, I'll make the change to "20" instead of EXTRACT_SIZE.
As far as whether or not folding the hash is cryptographically dubious, we're not using the hash as part of a digital signature, which is normally where cryptographers get antsy about truncating a cryptographic hash value (since it effectively halves the length of the hash, which thanks to the birthday paradox, makes it much easier to find collisions).
However, in this case, we are reducing the amount of information which is available to an attacker to infer the state of the pool. The "Linux Random Pool Revisited" paper had the following to say about it in section 4.3:
"In addition, the folding operation helps in avoiding recognizable patterns: the output of the hash function is not directly recognizable from the output data. For an optimal hash function, this step would not be necessary and could be replaced by a simple truncation."
If they had thought it was cryptographically dubious, they could have said so --- but they didn't.
It's true that if we know for sure that SHA-1 is a perfect one-way hash function (which is believed to be true, although there is no proof of this, and the recent work by Xiaoyun Wang, Yiquin Lisa Yin, and Hungbo Yu does not lead to any evidence for or against SHA-1's status as a one-way function), the folding operation wouldn't be necessary. But the folding operation shouldn't hurt (except for reducing the speed of generating random numbers, and it's currently not a bottleneck), and in the case where it might not be a perfect one-way function, it could help.
- Ted
| |