Re: HalfSipHash Acceptable Usage

Hi JP,

On Mon, Dec 19, 2016 at 9:49 PM, Jean-Philippe Aumasson
[off-list ref] wrote:

On Mon, Dec 19, 2016 at 6:32 PM Jason A. Donenfeld [off-list ref] wrote:

quoted

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.

quoted

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

quoted

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.

quoted

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