Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758470AbcLVDMb (ORCPT ); Wed, 21 Dec 2016 22:12:31 -0500 Received: from frisell.zx2c4.com ([192.95.5.64]:39818 "EHLO frisell.zx2c4.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750833AbcLVDM3 (ORCPT ); Wed, 21 Dec 2016 22:12:29 -0500 MIME-Version: 1.0 In-Reply-To: References: <20161216030328.11602-1-Jason@zx2c4.com> <20161221230216.25341-1-Jason@zx2c4.com> <20161221230216.25341-4-Jason@zx2c4.com> <17bd0c70-d2c1-165b-f5b2-252dfca404e8@stressinduktion.org> From: "Jason A. Donenfeld" Date: Thu, 22 Dec 2016 04:12:23 +0100 X-Gmail-Original-Message-ID: Message-ID: Subject: Re: [PATCH v7 3/6] random: use SipHash in place of MD5 To: Hannes Frederic Sowa Cc: Andy Lutomirski , 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 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: 1861 Lines: 34 On Thu, Dec 22, 2016 at 3:49 AM, Jason A. Donenfeld wrote: > I did have two objections to this. The first was that my SipHash > construction is faster. But in any case, they're both faster than the > current MD5, so it's just extra rice. The second, and the more > important one, was that batching entropy up like this means that 32 > calls will be really fast, and then the 33rd will be slow, since it > has to do a whole ChaCha round, because get_random_bytes must be > called to refill the batch. Since get_random_long is called for every > process startup, I didn't really like there being inconsistent > performance on process startup. And I'm pretty sure that one ChaCha > whole block is slower than computing MD5, even though it lasts 32 > times as long, though I need to measure this. But maybe that's dumb in > the end? Are these concerns that should point us toward the > determinism (and speed) of SipHash? Are these concerns that don't > matter and so we should roll with the simplicity of reusing ChaCha? I ran some measurements in order to quantify what I'm talking about. Repeatedly running md5_transform is about 2.3 times faster than repeatedly running extract_crng. What does this mean? One call to extract_crng gives us 32 times as many longs as one call to md5_transform. This means that spread over 32 process creations, chacha will be 13.9 times faster. However, every 32nd process will take 2.3 times as long to generate its ASLR value as it would with the old md5_transform code. Personally, I don't think that 2.3 is a big deal. And I really like how much this simplifies the analysis. But if it's a big deal to you, then we can continue to discuss my SipHash construction, which gives faster and more consistent performance, at the cost of a more complicated and probably less impressive security analysis. Jason