From: "Theodore Ts'o" <tytso@mit.edu>
To: "H. Peter Anvin" <hpa@zytor.com>
Cc: Linux Kernel Developers List <linux-kernel@vger.kernel.org>,
joern@logfs.org, macro@linux-mips.org, ralf@linux-mips.org,
dave.taht@gmail.com, blogic@openwrt.org, andrewmcgr@gmail.com,
smueller@chronox.de, geert@linux-m68k.org, tg@mirbsd.de
Subject: Re: [PATCH, RFC 08/12] random: mix in architectural randomness earlier in extract_buf()
Date: Mon, 23 Sep 2013 00:33:12 -0400 [thread overview]
Message-ID: <20130923043312.GH7321@thunk.org> (raw)
In-Reply-To: <523FBF8E.3000600@zytor.com>
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
next prev parent reply other threads:[~2013-09-23 4:33 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-09-22 20:38 [PATCH, RFC 00/12] random driver changes Theodore Ts'o
2013-09-22 20:38 ` [PATCH, RFC 01/12] random: run random_int_secret_init() run after all late_initcalls Theodore Ts'o
2013-09-22 20:38 ` [PATCH, RFC 02/12] random: Statically compute poolbitshift, poolbytes, poolbits Theodore Ts'o
2013-09-22 20:38 ` [PATCH, RFC 03/12] random: Allow fractional bits to be tracked Theodore Ts'o
2013-09-23 4:01 ` Theodore Ts'o
2013-09-23 4:03 ` H. Peter Anvin
2013-09-22 20:38 ` [PATCH, RFC 04/12] random: Account for entropy loss due to overwrites Theodore Ts'o
2013-09-22 20:38 ` [PATCH, RFC 05/12] random: fix the tracepoint for get_random_bytes(_arch) Theodore Ts'o
2013-09-22 20:38 ` [PATCH, RFC 06/12] random: optimize spinlock use in add_device_randomness() Theodore Ts'o
2013-09-22 20:38 ` [PATCH, RFC 07/12] random: allow architectures to optionally define random_get_entropy() Theodore Ts'o
2013-09-23 10:38 ` Stephan Mueller
2013-09-23 11:05 ` Theodore Ts'o
2013-09-22 20:38 ` [PATCH, RFC 08/12] random: mix in architectural randomness earlier in extract_buf() Theodore Ts'o
2013-09-23 4:11 ` H. Peter Anvin
2013-09-23 4:33 ` Theodore Ts'o [this message]
2013-09-22 20:38 ` [PATCH, RFC 09/12] random: optimize the entropy_store structure Theodore Ts'o
2013-09-22 20:38 ` [PATCH, RFC 10/12] random: cap the rate which the /dev/urandom pool gets reseeded Theodore Ts'o
2013-09-22 21:21 ` H. Peter Anvin
2013-09-22 21:40 ` Theodore Ts'o
2013-09-22 22:45 ` H. Peter Anvin
2013-09-22 23:23 ` Theodore Ts'o
2013-09-23 0:26 ` H. Peter Anvin
2013-09-22 20:38 ` [PATCH, RFC 11/12] random: speed up the fast_mix function by a factor of four Theodore Ts'o
2013-09-22 20:38 ` [PATCH, RFC 12/12] random: adjust the generator polynomials in the mixing function slightly Theodore Ts'o
2013-09-25 10:51 ` Jörg-Volker Peetz
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20130923043312.GH7321@thunk.org \
--to=tytso@mit.edu \
--cc=andrewmcgr@gmail.com \
--cc=blogic@openwrt.org \
--cc=dave.taht@gmail.com \
--cc=geert@linux-m68k.org \
--cc=hpa@zytor.com \
--cc=joern@logfs.org \
--cc=linux-kernel@vger.kernel.org \
--cc=macro@linux-mips.org \
--cc=ralf@linux-mips.org \
--cc=smueller@chronox.de \
--cc=tg@mirbsd.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).