From: "Jason A. Donenfeld" <Jason@zx2c4.com> To: Jean-Philippe Aumasson <firstname.lastname@example.org> Cc: "Theodore Ts'o" <email@example.com>, Hannes Frederic Sowa <firstname.lastname@example.org>, LKML <email@example.com>, Eric Biggers <firstname.lastname@example.org>, "Daniel J . Bernstein" <email@example.com>, David Laight <David.Laight@aculab.com>, David Miller <firstname.lastname@example.org>, Andi Kleen <email@example.com>, George Spelvin <firstname.lastname@example.org>, email@example.com, Andy Lutomirski <firstname.lastname@example.org>, Linux Crypto Mailing List <email@example.com>, Tom Herbert <firstname.lastname@example.org>, Vegard Nossum <email@example.com>, Netdev <firstname.lastname@example.org>, Linus Torvalds <email@example.com> Subject: Re: HalfSipHash Acceptable Usage Date: Mon, 19 Dec 2016 22:00:40 +0100 [thread overview] Message-ID: <CAHmME9p3w5O+onO9GDmM9E1egKE2FdY3htLkCfSW2P2Lw5qJfQ@mail.gmail.com> (raw) In-Reply-To: <CAGiyFdduUNSGq24zfsk0ZU=hnOCmewAw8vw6XvDoS-3f+3UPKQ@mail.gmail.com> Hi JP, On Mon, Dec 19, 2016 at 9:49 PM, Jean-Philippe Aumasson <firstname.lastname@example.org> wrote: > > On Mon, Dec 19, 2016 at 6:32 PM Jason A. Donenfeld <Jason@zx2c4.com> 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—in circumstances where the output > of the hash function is kept secret—in order to mitigate hash-flooding > attacks. > Thanks for the detailed response. I will continue exactly how you've specified. 1. SipHash2-4 for TCP sequence numbers, syncookies, and RNG. IOW, the things that MD5 is used for now. 2. HalfSipHash1-3 for hash tables where the output is not revealed, for jhash replacements. On 64-bit this will alias to SipHash1-3. 3. I will write Documentation/siphash.txt detailing this. 4. I'll continue to discourage other kernel developers from rolling their own crypto or departing from the tried&true in substantial ways. Thanks again, Jason
next prev parent reply other threads:[~2016-12-19 21:00 UTC|newest] Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top 2016-12-19 17:32 Jason A. Donenfeld [not found] ` <CAGiyFdduUNSGq24zfsk0ZU=hnOCmewAw8vw6XvDoS-3f+3UPKQ@mail.gmail.com> 2016-12-19 21:00 ` Jason A. Donenfeld [this message] 2016-12-20 21:36 ` Theodore Ts'o 2016-12-20 23:07 ` George Spelvin 2016-12-20 23:55 ` Eric Dumazet 2016-12-21 3:28 ` George Spelvin 2016-12-21 5:29 ` Eric Dumazet 2016-12-21 6:34 ` George Spelvin 2016-12-21 14:24 ` Jason A. Donenfeld 2016-12-21 15:55 ` George Spelvin 2016-12-21 16:37 ` Jason A. Donenfeld 2016-12-21 16:41 ` [kernel-hardening] " Rik van Riel 2016-12-21 17:25 ` Linus Torvalds 2016-12-21 18:07 ` George Spelvin 2016-12-22 1:54 ` Andy Lutomirski 2016-12-21 14:42 ` Jason A. Donenfeld 2016-12-21 15:56 ` Eric Dumazet 2016-12-21 16:33 ` Jason A. Donenfeld 2016-12-21 16:39 ` [kernel-hardening] " Rik van Riel 2016-12-21 17:08 ` Eric Dumazet 2016-12-21 18:37 ` George Spelvin 2016-12-21 18:40 ` Jason A. Donenfeld 2016-12-21 22:27 ` Theodore Ts'o 2016-12-22 0:18 ` George Spelvin 2016-12-22 1:13 ` George Spelvin
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=CAHmME9p3w5O+onO9GDmM9E1egKE2FdY3htLkCfSW2P2Lw5qJfQ@mail.gmail.com \ --email@example.com \ --cc=David.Laight@aculab.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --subject='Re: HalfSipHash Acceptable Usage' \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).