From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756478AbcLVCHi (ORCPT ); Wed, 21 Dec 2016 21:07:38 -0500 Received: from out3-smtp.messagingengine.com ([66.111.4.27]:36577 "EHLO out3-smtp.messagingengine.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752586AbcLVCHf (ORCPT ); Wed, 21 Dec 2016 21:07:35 -0500 X-ME-Sender: X-Sasl-enc: 4K3m9O8vyZZUc1v46mtZxSb4Uwd0EeD+BJAcSBxir6/s 1482372454 Subject: Re: [PATCH v7 3/6] random: use SipHash in place of MD5 To: Andy Lutomirski , "Jason A. Donenfeld" References: <20161216030328.11602-1-Jason@zx2c4.com> <20161221230216.25341-1-Jason@zx2c4.com> <20161221230216.25341-4-Jason@zx2c4.com> Cc: Netdev , "kernel-hardening@lists.openwall.com" , LKML , Linux Crypto Mailing List , David Laight , Ted Tso , Eric Dumazet , Linus Torvalds , Eric Biggers , Tom Herbert , Andi Kleen , "David S. Miller" , Jean-Philippe Aumasson From: Hannes Frederic Sowa Message-ID: <17bd0c70-d2c1-165b-f5b2-252dfca404e8@stressinduktion.org> Date: Thu, 22 Dec 2016 03:07:29 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.5.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 22.12.2016 00:42, Andy Lutomirski wrote: > On Wed, Dec 21, 2016 at 3:02 PM, Jason A. Donenfeld 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. Bye, Hannes