Re: HalfSipHash Acceptable Usage

On Mon, Dec 19, 2016 at 6:32 PM Jason A. Donenfeld [off-list ref] 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.

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