From: Jean-Philippe Aumasson Subject: Re: HalfSipHash Acceptable Usage Date: Mon, 19 Dec 2016 20:49:21 +0000 Message-ID: References: Reply-To: kernel-hardening@lists.openwall.com Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=001a11401e848308690544090e36 Cc: "Theodore Ts'o" , Hannes Frederic Sowa , LKML , Eric Biggers , "Daniel J . Bernstein" , David Laight , David Miller , Andi Kleen , George Spelvin , kernel-hardening@lists.openwall.com, Andy Lutomirski , Linux Crypto Mailing List , Tom Herbert , Vegard Nossum , Netdev , Linus Torvalds To: "Jason A. Donenfeld" Return-path: List-Post: List-Help: List-Unsubscribe: List-Subscribe: In-Reply-To: List-Id: linux-crypto.vger.kernel.org --001a11401e848308690544090e36 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On Mon, Dec 19, 2016 at 6:32 PM Jason A. Donenfeld wrote: > Hi JP, > > With the threads getting confusing, I've been urged to try and keep > the topics and threads more closely constrained. Here's where we're > at, and here's the current pressing security concern. It'd be helpful > to have a definitive statement on what you think is best, so we can > just build on top of that, instead of getting lost in the chorus of > opinions. > > 1) Anything that requires actual long-term security will use > SipHash2-4, with the 64-bit output and the 128-bit key. This includes > things like TCP sequence numbers. This seems pretty uncontroversial to > me. Seem okay to you? > Right, since 2012 when we published SipHash many cryptanalysts attempted to break SipHash-2-4 with a 128-bit key, for various notions of "break", and nothing worth worrying was ever found. I'm totally confident that SipHash-2-4 will live up to its security promises. Don't use something weaker for things like TCP sequence numbers or RNGs. Use SipHash2-4 for those. That is the correct choice. > > 2) People seem to want something competitive, performance-wise, with > jhash if it's going to replace jhash. The kernel community > instinctively pushes back on anything that could harm performance, > especially in networking and in critical data structures, so there > have been some calls for something faster than SipHash. So, questions > regarding this: > > No free lunch I guess: either go with a cryptographically secure, time-proved keyed hash such as SipHash, or go with some simpler hash deemed secure cos its designer can't break it :) #DontRollYourOwnCrypto 2a) George thinks that HalfSipHash on 32-bit systems will have roughly > comparable speed as SipHash on 64-bit systems, so the idea would be to > use HalfSipHash on 32-bit systems' hash tables and SipHash on 64-bit > systems' hash tables. The big obvious question is: does HalfSipHash > have a sufficient security margin for hashtable usage and hashtable > attacks? I'm not wondering about the security margin for other usages, > but just of the hashtable usage. In your opinion, does HalfSipHash cut > it? > HalfSipHash takes its core function from Chaskey and uses the same construction as SipHash, so it *should* be secure. Nonetheless it hasn't received the same amount of attention as 64-bit SipHash did. So I'm less confident about its security than about SipHash's, but it obviously inspires a lot more confidence than non-crypto hashes. Too, HalfSipHash only has a 64-bit key, not a 128-bit key like SipHash, so only use this as a mitigation for hash-flooding attacks, where the output of the hash function is never directly shown to the caller. Do not use HalfSipHash for TCP sequence numbers or RNGs. > > 2b) While I certainly wouldn't consider making the use case in > question (1) employ a weaker function, for this question (2), there > has been some discussion about using HalfSipHash1-3 (or SipHash1-3 on > 64-bit) instead of 2-4. So, the same question is therefore posed: > would using HalfSipHash1-3 give a sufficient security margin for > hashtable usage and hashtable attacks? > My educated guess is that yes, it will, but that it may not withhold cryptanalysis as a pseudorandom function (PRF). For example I wouldn't be surprised if there were a "distinguishing attack" that detects non-random patterns in HalfSipHash-1-3's output. But most of the non-crypto hashes I've seen have obvious distinguishing attacks. So the upshot is that HSH will get you better security that AnyWeakHash even with 1 & 3 rounds. So, if you're willing to compromise on security, but still want something not completely unreasonable, you might be able to get away with using HalfSipHash1-3 as a replacement for jhash=E2=80=94in circumstances where th= e output of the hash function is kept secret=E2=80=94in order to mitigate hash-flood= ing attacks. > > My plan is essentially to implement things according to your security > recommendation. The thread started with me pushing a heavy duty > security solution -- SipHash2-4 -- for _everything_. I've received > understandable push back on that notion for certain use cases. So now > I'm trying to discover what the most acceptable compromise is. Your > answers on (2a) and (2b) will direct that compromise. > > Thanks again, > Jason > --001a11401e848308690544090e36 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

On Mon, De= c 19, 2016 at 6:32 PM Jason A. Donenfeld <Jason@zx2c4.com> wrote:
Hi JP,

W= ith the threads getting confusing, I've been urged to try and keep
the topics and threads more closely constrained. Here= 9;s where we're
at, and here's the current p= ressing security concern. It'd be helpful
to hav= e a definitive statement on what you think is best, so we can
just build on top of that, instead of getting lost in the chorus = of
opinions.

1) Anything that requires actual long-term security will use
SipHash2-4, with the 64-bit output and the 128-bit key. Th= is includes
things like TCP sequence numbers. This s= eems pretty uncontroversial to
me. Seem okay to you?=


Right, since 2012 when we publ= ished SipHash many cryptanalysts attempted to break SipHash-2-4 with a 128-= bit key, for various notions of "break", and nothing worth worryi= ng was ever found. I'm totally confident that SipHash-2-4 will live up = to its security promises.= =C2=A0

Don't use something weaker for things like TCP seq= uence numbers or RNGs. Use SipHash2-4 for those. That is the correct choice= .
=C2=A0

2) People seem to want something competitive, performance-= wise, with
jhash if it's going to replace jhash.= The kernel community
instinctively pushes back on a= nything that could harm performance,
especially in n= etworking and in critical data structures, so there
= have been some calls for something faster than SipHash. So, questions
regarding this:


No free lunch I guess: either go with a c= ryptographically secure, time-proved keyed hash such as SipHash, or go with= some simpler hash deemed secure cos its designer can't break it :) #Do= ntRollYourOwnCrypto

2a) George thinks that HalfSipHash on 32-bit systems will have r= oughly
comparable speed as SipHash on 64-bit systems= , so the idea would be to
use HalfSipHash on 32-bit = systems' hash tables and SipHash on 64-bit
syste= ms' hash tables. The big obvious question is: does HalfSipHash
have a sufficient security margin for hashtable usage and ha= shtable
attacks? I'm not wondering about the sec= urity margin for other usages,
but just of the hasht= able usage. In your opinion, does HalfSipHash cut
it= ?

HalfSipHash takes its = core function from Chaskey and uses the same construction as SipHash, so it= *should* be secure. Nonetheless it hasn't received the same amount of = attention as 64-bit SipHash did. So I'm less confident about its securi= ty than about SipHash's, but it obviously inspires a lot more confidenc= e than non-crypto hashes.= =C2=A0

Too, HalfSipHash only has a 64-bit key, not a 128-bit = key like SipHash, so only use this as a mitigation for hash-flooding attack= s, where the output of the hash function is never directly shown to the cal= ler. Do not use HalfSipHash for TCP sequence numbers or RNGs.

=C2=A0

2b) While I certainly wouldn't consider making the use= case in
question (1) employ a weaker function, for = this question (2), there
has been some discussion ab= out using HalfSipHash1-3 (or SipHash1-3 on
64-bit) i= nstead of 2-4. So, the same question is therefore posed:
would using HalfSipHash1-3 give a sufficient security margin for
hashtable usage and hashtable attacks?

My educated guess is that yes, i= t will, but that it may not withhold cryptanalysis as a pseudorandom functi= on (PRF). For example I wouldn't be surprised if there were a "dis= tinguishing attack" that detects non-random patterns in HalfSipHash-1-= 3's output. But most of the non-crypto hashes I've seen have obviou= s distinguishing attacks. So the upshot is that HSH will get you better sec= urity that AnyWeakHash even with 1 & 3 rounds.=C2=A0

So, if you're willing to compromise on security, but still want = something not completely unreasonable, you might be able to get away with u= sing HalfSipHash1-3 as a replacement for jhash=E2=80=94in circumstances whe= re the output of the hash function is kept secret=E2=80=94in order to mitig= ate hash-flooding attacks.

=C2=A0

My pla= n is essentially to implement things according to your security
recommendation. The thread started with me pushing a heavy duty=
security solution -- SipHash2-4 -- for _everything_= . I've received
understandable push back on that= notion for certain use cases. So now
I'm trying= to discover what the most acceptable compromise is. Your
answers on (2a) and (2b) will direct that compromise.

Thanks again,
Jason<= /blockquote>

--001a11401e848308690544090e36--