Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1546131
| From | Andy Lutomirski <luto@amacapital.net> |
|---|---|
| Newsgroups | linux.kernel |
| Subject | Re: [PATCH v7 3/6] random: use SipHash in place of MD5 |
| Date | 2016-12-22 03:20 +0100 |
| Message-ID | <sR197-35j-1@gated-at.bofh.it> (permalink) |
| References | <sOR4e-5XG-5@gated-at.bofh.it> <sQYbf-1hM-1@gated-at.bofh.it> <sQYbg-1hM-43@gated-at.bofh.it> <sQYXD-1An-7@gated-at.bofh.it> <sR0Zr-32l-1@gated-at.bofh.it> |
| Organization | linux.* mail to news gateway |
On Wed, Dec 21, 2016 at 6:07 PM, Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
> On 22.12.2016 00:42, Andy Lutomirski wrote:
>> On Wed, Dec 21, 2016 at 3:02 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>>> unsigned int get_random_int(void)
>>> {
>>> - __u32 *hash;
>>> - unsigned int ret;
>>> -
>>> - if (arch_get_random_int(&ret))
>>> - return ret;
>>> -
>>> - hash = get_cpu_var(get_random_int_hash);
>>> -
>>> - hash[0] += current->pid + jiffies + random_get_entropy();
>>> - md5_transform(hash, random_int_secret);
>>> - ret = hash[0];
>>> - put_cpu_var(get_random_int_hash);
>>> -
>>> - return ret;
>>> + unsigned int arch_result;
>>> + u64 result;
>>> + struct random_int_secret *secret;
>>> +
>>> + if (arch_get_random_int(&arch_result))
>>> + return arch_result;
>>> +
>>> + secret = get_random_int_secret();
>>> + result = siphash_3u64(secret->chaining, jiffies,
>>> + (u64)random_get_entropy() + current->pid,
>>> + secret->secret);
>>> + secret->chaining += result;
>>> + put_cpu_var(secret);
>>> + return result;
>>> }
>>> EXPORT_SYMBOL(get_random_int);
>>
>> Hmm. I haven't tried to prove anything for real. But here goes (in
>> the random oracle model):
>>
>> Suppose I'm an attacker and I don't know the secret or the chaining
>> value. Then, regardless of what the entropy is, I can't predict the
>> numbers.
>>
>> Now suppose I do know the secret and the chaining value due to some
>> leak. If I want to deduce prior outputs, I think I'm stuck: I'd need
>> to find a value "result" such that prev_chaining + result = chaining
>> and result = H(prev_chaining, ..., secret);. I don't think this can
>> be done efficiently in the random oracle model regardless of what the
>> "..." is.
>>
>> But, if I know the secret and chaining value, I can predict the next
>> output assuming I can guess the entropy. What's worse is that, even
>> if I can't guess the entropy, if I *observe* the next output then I
>> can calculate the next chaining value.
>>
>> So this is probably good enough, and making it better is hard. Changing it to:
>>
>> u64 entropy = (u64)random_get_entropy() + current->pid;
>> result = siphash(..., entropy, ...);
>> secret->chaining += result + entropy;
>>
>> would reduce this problem by forcing an attacker to brute-force the
>> entropy on each iteration, which is probably an improvement.
>>
>> To fully fix it, something like "catastrophic reseeding" would be
>> needed, but that's hard to get right.
>
> I wonder if Ted's proposal was analyzed further in terms of performance
> if get_random_int should provide cprng alike properties?
>
> For reference: https://lkml.org/lkml/2016/12/14/351
>
> The proposal made sense to me and would completely solve the above
> mentioned problem on the cost of repeatedly reseeding from the crng.
>
Unless I've misunderstood it, Ted's proposal causes get_random_int()
to return bytes straight from urandom (effectively), which should make
it very strong. And if urandom is competitively fast now, I don't see
the problem. ChaCha20 is designed for speed, after all.
Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
[PATCH v5 0/4] The SipHash Patchset "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 21:40 +0100
[PATCH v5 4/4] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 21:40 +0100
[PATCH v5 3/4] secure_seq: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 21:40 +0100
RE: [PATCH v5 3/4] secure_seq: use SipHash in place of MD5 David Laight <David.Laight@ACULAB.COM> - 2016-12-16 11:10 +0100
Re: [PATCH v5 3/4] secure_seq: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-16 17:00 +0100
[PATCH v5 2/4] siphash: add Nu{32,64} helpers "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 21:50 +0100
RE: [PATCH v5 2/4] siphash: add Nu{32,64} helpers David Laight <David.Laight@ACULAB.COM> - 2016-12-16 11:50 +0100
RE: [PATCH v5 2/4] siphash: add Nu{32,64} helpers "George Spelvin" <linux@sciencehorizons.net> - 2016-12-16 16:50 +0100
[PATCH v6 4/5] md5: remove from lib and only live in crypto "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-16 04:10 +0100
[PATCH v6 2/5] secure_seq: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-16 04:10 +0100
[PATCH v6 5/5] syncookies: use SipHash in place of SHA1 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-16 04:10 +0100
[PATCH v6 0/5] The SipHash Patchset "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-16 04:10 +0100
[PATCH v6 3/5] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-16 04:10 +0100
Re: [PATCH v6 3/5] random: use SipHash in place of MD5 Andy Lutomirski <luto@amacapital.net> - 2016-12-16 22:40 +0100
[PATCH v6 1/5] siphash: add cryptographically secure PRF "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-16 04:10 +0100
[PATCH v7 0/6] The SipHash Patchset "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 00:10 +0100
[PATCH v7 6/6] siphash: implement HalfSipHash1-3 for hash tables "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 00:10 +0100
Re: [PATCH v7 6/6] siphash: implement HalfSipHash1-3 for hash tables Andi Kleen <ak@linux.intel.com> - 2016-12-22 01:50 +0100
[PATCH v7 5/6] syncookies: use SipHash in place of SHA1 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 00:10 +0100
[PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 00:10 +0100
Re: [PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 00:20 +0100
Re: [PATCH v7 3/6] random: use SipHash in place of MD5 Andy Lutomirski <luto@amacapital.net> - 2016-12-22 01:00 +0100
Re: [PATCH v7 3/6] random: use SipHash in place of MD5 Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-22 03:10 +0100
Re: [PATCH v7 3/6] random: use SipHash in place of MD5 Andy Lutomirski <luto@amacapital.net> - 2016-12-22 03:20 +0100
Re: [PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 03:50 +0100
Re: [PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 04:20 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 Theodore Ts'o <tytso@mit.edu> - 2016-12-22 06:50 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 07:10 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 Theodore Ts'o <tytso@mit.edu> - 2016-12-22 17:00 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 17:20 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 Theodore Ts'o <tytso@mit.edu> - 2016-12-22 17:40 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 17:40 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-22 13:50 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 14:20 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-22 16:10 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 16:20 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 16:30 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-22 16:40 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 16:50 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-22 17:00 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 17:00 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 Theodore Ts'o <tytso@mit.edu> - 2016-12-22 17:00 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-22 19:10 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 19:20 +0100
Re: [kernel-hardening] Re: [PATCH v7 3/6] random: use SipHash in place of MD5 Theodore Ts'o <tytso@mit.edu> - 2016-12-22 21:00 +0100
Re: [PATCH v7 3/6] random: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 03:40 +0100
[PATCH v7 4/6] md5: remove from lib and only live in crypto "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 00:10 +0100
[PATCH v7 2/6] secure_seq: use SipHash in place of MD5 "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 00:10 +0100
[PATCH v7 1/6] siphash: add cryptographically secure PRF "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-22 00:10 +0100
Re: [PATCH v7 1/6] siphash: add cryptographically secure PRF Stephen Hemminger <stephen@networkplumber.org> - 2016-12-22 02:50 +0100
csiph-web