Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1761923AbcLPWOE (ORCPT ); Fri, 16 Dec 2016 17:14:04 -0500 Received: from mail-ua0-f171.google.com ([209.85.217.171]:35218 "EHLO mail-ua0-f171.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1758499AbcLPWNy (ORCPT ); Fri, 16 Dec 2016 17:13:54 -0500 MIME-Version: 1.0 In-Reply-To: References: From: Andy Lutomirski Date: Fri, 16 Dec 2016 14:13:32 -0800 Message-ID: Subject: Re: [PATCH v6 3/5] random: use SipHash in place of MD5 To: "Jason A. Donenfeld" Cc: Netdev , "kernel-hardening@lists.openwall.com" , LKML , Linux Crypto Mailing List , David Laight , Ted Tso , Hannes Frederic Sowa , Linus Torvalds , Eric Biggers , Tom Herbert , George Spelvin , Vegard Nossum , Andi Kleen , "David S. Miller" , Jean-Philippe Aumasson Content-Type: text/plain; charset=UTF-8 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3345 Lines: 84 On Fri, Dec 16, 2016 at 1:45 PM, Jason A. Donenfeld wrote: > Hi Andy, > > On Fri, Dec 16, 2016 at 10:31 PM, Andy Lutomirski wrote: >> I think it would be nice to try to strenghen the PRNG construction. >> FWIW, I'm not an expert in PRNGs, and there's fairly extensive >> literature, but I can at least try. > > In an effort to keep this patchset as initially as uncontroversial as > possible, I kept the same same construction as before and just swapped > out slow MD5 for fast Siphash. Additionally, the function > documentation says that it isn't cryptographically secure. But in the > end I certainly agree with you; we should most definitely improve > things, and seeing the eyeballs now on this series, I think we now > might have a mandate to do so. > >> 1. A one-time leak of memory contents doesn't ruin security until >> reboot. This is especially value across suspend and/or hibernation. > > Ted and I were discussing this in another thread, and it sounds like > he wants the same thing. I'll add re-generation of the secret every > once in a while. Perhaps time-based makes more sense than > counter-based for rekeying frequency? Counter may be faster -- you don't need to read a timer. Lots of CPUs are surprisingly slow at timing. OTOH jiffies are fast. > >> 2. An attack with a low work factor (2^64?) shouldn't break the scheme >> until reboot. > > It won't. The key is 128-bits. Whoops, I thought the key was 64-bit... > >> This is effectively doing: >> >> output = H(prev_output, weak "entropy", per-boot secret); >> >> One unfortunately downside is that, if used in a context where an >> attacker can see a single output, the attacker learns the chaining >> value. If the attacker can guess the entropy, then, with 2^64 work, >> they learn the secret, and they can predict future outputs. > > No, the secret is 128-bits, which isn't feasibly guessable. The secret > also isn't part of the hash, but rather is the generator of the hash > function. A keyed hash (a PRF) is a bit of a different construction > than just hashing a secret value into a hash function. I was thinking in the random oracle model, in which case the whole function is just a PRF that takes a few input parameters, one of which is a key. > >> Second, change the mode so that an attacker doesn't learn so much >> internal state. For example: >> >> output = H(old_chain, entropy, secret); >> new_chain = old_chain + entropy + output; > > Happy to make this change, with making the chaining value additive > rather than a replacement. > > However, I'm not sure adding entropy to the new_chain makes a > different. That entropy is basically just the cycle count plus the > jiffies count. If an attacker can already guess them, then adding them > again to the chaining value doesn't really add much. Agreed. A simpler contruction would be: chaining++; output = H(chaining, secret); And this looks a whole lot like Ted's ChaCha20 construction. The benefit of my construction is that (in the random oracle model, assuming my intuition is right), if an attacker misses ~128 samples and entropy has at least one bit of independent min-entropy per sample, then the attacker needs ~2^128 work to brute-force the chaining value even fi the attacker knew both the original chaining value and the secret. --Andy