
Date: Wed, 21 Dec 2016 18:09:53 0800 From: Andy Lutomirski <luto@...capital.net> To: Hannes Frederic Sowa <hannes@...essinduktion.org> Cc: "Jason A. Donenfeld" <Jason@...c4.com>, Netdev <netdev@...r.kernel.org>, "kernelhardening@...ts.openwall.com" <kernelhardening@...ts.openwall.com>, LKML <linuxkernel@...r.kernel.org>, Linux Crypto Mailing List <linuxcrypto@...r.kernel.org>, David Laight <David.Laight@...lab.com>, Ted Tso <tytso@....edu>, Eric Dumazet <edumazet@...gle.com>, Linus Torvalds <torvalds@...uxfoundation.org>, Eric Biggers <ebiggers3@...il.com>, Tom Herbert <tom@...bertland.com>, Andi Kleen <ak@...ux.intel.com>, "David S. Miller" <davem@...emloft.net>, JeanPhilippe Aumasson <jeanphilippe.aumasson@...il.com> Subject: Re: [PATCH v7 3/6] random: use SipHash in place of MD5 On Wed, Dec 21, 2016 at 6:07 PM, Hannes Frederic Sowa <hannes@...essinduktion.org> wrote: > On 22.12.2016 00:42, Andy Lutomirski wrote: >> On Wed, Dec 21, 2016 at 3:02 PM, Jason A. Donenfeld <Jason@...c4.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 bruteforce 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.
Powered by blists  more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.