From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755771AbcLNNKw (ORCPT ); Wed, 14 Dec 2016 08:10:52 -0500 Received: from frisell.zx2c4.com ([192.95.5.64]:33626 "EHLO frisell.zx2c4.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753305AbcLNNKu (ORCPT ); Wed, 14 Dec 2016 08:10:50 -0500 MIME-Version: 1.0 In-Reply-To: <516c5633-14c2-ee18-90e4-84d73870ba2c@stressinduktion.org> References: <20161214035927.30004-1-Jason@zx2c4.com> <516c5633-14c2-ee18-90e4-84d73870ba2c@stressinduktion.org> From: "Jason A. Donenfeld" Date: Wed, 14 Dec 2016 14:10:33 +0100 X-Gmail-Original-Message-ID: Message-ID: Subject: Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function To: Hannes Frederic Sowa Cc: Netdev , kernel-hardening@lists.openwall.com, LKML , Linux Crypto Mailing List , Jean-Philippe Aumasson , "Daniel J . Bernstein" , Linus Torvalds , Eric Biggers Content-Type: text/plain; charset=UTF-8 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hi Hannes, On Wed, Dec 14, 2016 at 12:21 PM, Hannes Frederic Sowa wrote: > Can you show or cite benchmarks in comparison with jhash? Last time I > looked, especially for short inputs, siphash didn't beat jhash (also on > all the 32 bit devices etc.). I assume that jhash is likely faster than siphash, but I wouldn't be surprised if with optimization we can make siphash at least pretty close on 64-bit platforms. (I'll do some tests though; maybe I'm wrong and jhash is already slower.) With that said, siphash is here to replace uses of jhash where hashtable poisoning vulnerabilities make it necessary. Where there's no significant security improvement, if there's no speed improvement either, then of course nothing's going to change. I should have mentioned md5_transform in this first message too, as two other patches in this series actually replace md5_transform usage with siphash. I think in this case, siphash is a clear performance winner (and security winner) over md5_transform. So if the push back against replacing jhash usages is just too high, at the very least it remains useful already for the md5_transform usage. > This pretty much depends on the linearity of the hash function? I don't > think a crypto secure hash function is needed for a hash table. Albeit I > agree that siphash certainly looks good to be used here. In order to prevent the aforementioned poisoning attacks, a PRF with perfect linearity is required, which is what's achieved when it's a cryptographically secure one. Check out section 7 of https://131002.net/siphash/siphash.pdf . > I am pretty sure that SipHash still needs a random key per hash table > also. So far it was only the choice of hash function you are questioning. Siphash needs a random secret key, yes. The point is that the hash function remains secure so long as the secret key is kept secret. Other functions can't make the same guarantee, and so nervous periodic key rotation is necessary, but in most cases nothing is done, and so things just leak over time. > Hmm, I tried to follow up with all the HashDoS work and so far didn't > see any HashDoS attacks against the Jenkins/SpookyHash family. > > If this is an issue we might need to also put those changes into stable. jhash just isn't secure; it's not a cryptographically secure PRF. If there hasn't already been an academic paper put out there about it this year, let's make this thread 1000 messages long to garner attention, and next year perhaps we'll see one. No doubt that motivated government organizations, defense contractors, criminals, and other netizens have already done research in private. Replacing insecure functions with secure functions is usually a good thing. Jason