linux-kernel - Re: [PATCH, RFC 08/12] random: mix in architectural randomness earlier in extract

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20130923043312.GH7321@thunk.org>
Date:	Mon, 23 Sep 2013 00:33:12 -0400
From:	Theodore Ts'o <tytso@....edu>
To:	"H. Peter Anvin" <hpa@...or.com>
Cc:	Linux Kernel Developers List <linux-kernel@...r.kernel.org>,
	joern@...fs.org, macro@...ux-mips.org, ralf@...ux-mips.org,
	dave.taht@...il.com, blogic@...nwrt.org, andrewmcgr@...il.com,
	smueller@...onox.de, geert@...ux-m68k.org, tg@...bsd.de
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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/