lkml.org 
[lkml]   [2013]   [Sep]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [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


\
 
 \ /
  Last update: 2013-09-23 06:41    [W:0.144 / U:0.068 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site