Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1544771

Re: HalfSipHash Acceptable Usage

Show all headers | View raw

Hi JP,

On Mon, Dec 19, 2016 at 9:49 PM, Jean-Philippe Aumasson
<jeanphilippe.aumasson@gmail.com> 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

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

HalfSipHash Acceptable Usage "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-19 18:40 +0100
  Re: HalfSipHash Acceptable Usage "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-19 22:10 +0100
  Re: HalfSipHash Acceptable Usage Theodore Ts'o <tytso@mit.edu> - 2016-12-20 22:40 +0100
    Re: HalfSipHash Acceptable Usage "George Spelvin" <linux@sciencehorizons.net> - 2016-12-21 00:10 +0100
    Re: HalfSipHash Acceptable Usage Eric Dumazet <eric.dumazet@gmail.com> - 2016-12-21 01:00 +0100
      Re: HalfSipHash Acceptable Usage "George Spelvin" <linux@sciencehorizons.net> - 2016-12-21 04:30 +0100
        Re: HalfSipHash Acceptable Usage Eric Dumazet <eric.dumazet@gmail.com> - 2016-12-21 06:30 +0100
          Re: HalfSipHash Acceptable Usage "George Spelvin" <linux@sciencehorizons.net> - 2016-12-21 07:40 +0100
            Re: HalfSipHash Acceptable Usage "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-21 15:30 +0100
              Re: HalfSipHash Acceptable Usage "George Spelvin" <linux@sciencehorizons.net> - 2016-12-21 17:00 +0100
                Re: HalfSipHash Acceptable Usage "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-21 17:40 +0100
                Re: [kernel-hardening] Re: HalfSipHash Acceptable Usage Rik van Riel <riel@redhat.com> - 2016-12-21 17:50 +0100
                Re: HalfSipHash Acceptable Usage Linus Torvalds <torvalds@linux-foundation.org> - 2016-12-21 18:30 +0100
                Re: HalfSipHash Acceptable Usage "George Spelvin" <linux@sciencehorizons.net> - 2016-12-21 19:10 +0100
                Re: HalfSipHash Acceptable Usage Andy Lutomirski <luto@amacapital.net> - 2016-12-22 03:10 +0100
          Re: HalfSipHash Acceptable Usage "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-21 15:50 +0100
            Re: HalfSipHash Acceptable Usage Eric Dumazet <eric.dumazet@gmail.com> - 2016-12-21 17:00 +0100
              Re: HalfSipHash Acceptable Usage "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-21 17:40 +0100
              Re: [kernel-hardening] Re: HalfSipHash Acceptable Usage Rik van Riel <riel@redhat.com> - 2016-12-21 17:40 +0100
                Re: [kernel-hardening] Re: HalfSipHash Acceptable Usage Eric Dumazet <eric.dumazet@gmail.com> - 2016-12-21 18:10 +0100
              Re: HalfSipHash Acceptable Usage "George Spelvin" <linux@sciencehorizons.net> - 2016-12-21 19:40 +0100
                Re: HalfSipHash Acceptable Usage "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-21 19:50 +0100
                Re: HalfSipHash Acceptable Usage Theodore Ts'o <tytso@mit.edu> - 2016-12-21 23:30 +0100
                Re: HalfSipHash Acceptable Usage "George Spelvin" <linux@sciencehorizons.net> - 2016-12-22 01:20 +0100
                Re: HalfSipHash Acceptable Usage "George Spelvin" <linux@sciencehorizons.net> - 2016-12-22 02:20 +0100

csiph-web