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

Groups > linux.kernel > #1542149

Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function

From "Jason A. Donenfeld" <Jason@zx2c4.com>
Newsgroups linux.kernel
Subject Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function
Date 2016-12-14 20:40 +0100
Message-ID <sOnzc-2MP-35@gated-at.bofh.it> (permalink)
References <sO93b-1Im-3@gated-at.bofh.it> <sOmMN-1X4-13@gated-at.bofh.it> <sOnfQ-2vz-19@gated-at.bofh.it>
Organization linux.* mail to news gateway

Show all headers | View raw

Hi Tom,

On Wed, Dec 14, 2016 at 8:18 PM, Tom Herbert <tom@herbertland.com> wrote:
> "super fast" is relative. My quick test shows that this faster than
> Toeplitz (good, but not exactly hard to achieve), but is about 4x
> slower than jhash.

Fast relative to other cryptographically secure PRFs.

>> SipHash isn't just some new trendy hash function. It's been around for a
>> while, and there really isn't anything that comes remotely close to
>> being useful in the way SipHash is. With that said, why do we need this?
> I don't think we need advertising nor a lesson on hashing. It would be
> much more useful if you just point us to the paper on siphash (which I
> assume I http://cr.yp.to/siphash/siphash-20120918.pdf ?).

Ugh. Sorry. It definitely wasn't my intention to give an uninvited
lesson or an annoying advert. For the former, I didn't want to make
any expectations about fields of knowledge, because I honest have no
idea. For the latter, I wrote that sentence to indicate that siphash
isn't just some newfangled hipster function, but something useful and
well established. I didn't mean it as a form of advertising. My
apologies if I've offended your sensibilities.

That cr.yp.to link is fine, or https://131002.net/siphash/siphash.pdf I believe.

> Key rotation is important anyway, without any key rotation even if the
> key is compromised in siphash by some external means we would have an
> insecure hash until the system reboots.

I'm a bit surprised to read this. I've never designed a system to be
secure even in the event of remote arbitrary kernel memory disclosure,
and I wasn't aware this was generally considered an architectural
requirement or Linux.

In any case, if you want this, I suppose you can have it with siphash too.

> Maybe so, but we need to do due diligence before considering adopting
> siphash as the primary hashing in the network stack. Consider that we
> may very well perform a hash over L4 tuples on _every_ packet. We've
> done a good job at limiting this to be at most one hash per packet,
> but nevertheless the performance of the hash function must be take
> into account.

I agree with you. It seems like each case is going to needed to be
measured on a case by case basis. In this series I make the first use
of siphash in the secure sequence generation and get_random_int/long,
where siphash replaces md5, so there's a pretty clear performance in.
But for the jhash replacements indeed things are going to need to be
individually evaluated.

> 1) My quick test shows siphash is about four times more expensive than
> jhash. On my test system, computing a hash over IPv4 tuple (two 32 bit
> addresses and 2 16 bit source ports) is 6.9 nsecs in Jenkins hash, 33
> nsecs with siphash. Given that we have eliminated most of the packet
> header hashes this might be tolerable, but still should be looking at
> ways to optimize.
> 2) I like moving to use u64 (quad words) in the hash, this is an
> improvement over Jenkins which is based on 32 bit words. If we put
> this in the kernel we probably want to have several variants of
> siphash for specific sizes (e.g. siphash1, siphash2, siphash2,
> siphashn for hash over one, two, three, or n sixty four bit words).

I think your suggestion for (2) will contribute to further
optimizations for (1). In v2, I had another patch in there adding
siphash_1word, siphash_2words, etc, like jhash, but I implemented it
by taking u32 variables and then just concatenating these into a
buffer and passing them to the main siphash function. I removed it
from v3 because I thought that these kind of missed the whole point.
In particular:

a) siphash24_1word, siphash24_2words, siphash24_3words, etc should
take u64, not u32, since that's what siphash operates on natively
b) Rather than concatenating them in a buffer, I should write
specializations of the siphash24 function _especially_ for these size
inputs to avoid the copy and to reduce the book keeping.

I'll add these functions to v4 implemented like that.

Thanks for the useful feedback and benchmarks!

Jason

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

Thread

[PATCH v2 1/4] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 05:10 +0100
  Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-14 12:40 +0100
    Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 14:20 +0100
      Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-14 16:20 +0100
        Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 20:50 +0100
      Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Herbert Xu <herbert@gondor.apana.org.au> - 2016-12-15 09:00 +0100
        Re: [kernel-hardening] Re: [PATCH v2 1/4] siphash: add  cryptographically secure hashtable function Daniel Micay <danielmicay@gmail.com> - 2016-12-15 09:20 +0100
  Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 13:50 +0100
    Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-14 23:10 +0100
      Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 00:40 +0100
        Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-15 09:40 +0100
      RE: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function David Laight <David.Laight@ACULAB.COM> - 2016-12-15 12:10 +0100
        RE: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function David Laight <David.Laight@ACULAB.COM> - 2016-12-15 13:30 +0100
          Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-15 14:00 +0100
            RE: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function David Laight <David.Laight@ACULAB.COM> - 2016-12-15 15:00 +0100
              Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-15 16:00 +0100
                RE: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function David Laight <David.Laight@ACULAB.COM> - 2016-12-15 16:50 +0100
                Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-15 17:00 +0100
                Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 20:00 +0100
                Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-15 21:40 +0100
                Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 21:50 +0100
                Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-15 22:20 +0100
                Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-15 22:20 +0100
                Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Peter Zijlstra <peterz@infradead.org> - 2016-12-15 23:10 +0100
                Re: [kernel-hardening] Re: [PATCH v2 1/4] siphash: add  cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 22:20 +0100
                Re: [kernel-hardening] Re: [PATCH v2 1/4] siphash: add  cryptographically secure hashtable function Linus Torvalds <torvalds@linux-foundation.org> - 2016-12-15 22:20 +0100
                Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Peter Zijlstra <peterz@infradead.org> - 2016-12-15 22:20 +0100
        Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-15 13:30 +0100
  [PATCH v3 2/3] secure_seq: use siphash24 instead of md5_transform "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 19:50 +0100
    Re: [PATCH v3 2/3] secure_seq: use siphash24 instead of md5_transform kbuild test robot <lkp@intel.com> - 2016-12-14 22:50 +0100
  [PATCH v3 1/3] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 19:50 +0100
    [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 19:50 +0100
      Re: [PATCH v3 3/3] random: use siphash24 instead of md5 for  get_random_int/long kbuild test robot <lkp@intel.com> - 2016-12-14 23:00 +0100
      Re: [PATCH v3 3/3] random: use siphash24 instead of md5 for  get_random_int/long kbuild test robot <lkp@intel.com> - 2016-12-14 23:10 +0100
      RE: [PATCH v3 3/3] random: use siphash24 instead of md5 for  get_random_int/long David Laight <David.Laight@ACULAB.COM> - 2016-12-15 11:20 +0100
        Re: [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 20:00 +0100
    Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function Tom Herbert <tom@herbertland.com> - 2016-12-14 20:20 +0100
      Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 20:40 +0100
        Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 22:00 +0100
          Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function Tom Herbert <tom@herbertland.com> - 2016-12-14 22:40 +0100
            Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 00:00 +0100
              Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 00:20 +0100
                Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable  function Christian Kujau <lists@nerdbynature.de> - 2016-12-18 01:10 +0100
              Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function Tom Herbert <tom@herbertland.com> - 2016-12-15 00:20 +0100
              Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 00:40 +0100
                Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function Linus Torvalds <torvalds@linux-foundation.org> - 2016-12-15 01:30 +0100
                RE: [PATCH v3 1/3] siphash: add cryptographically secure hashtable  function David Laight <David.Laight@ACULAB.COM> - 2016-12-15 11:30 +0100
              Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function Linus Torvalds <torvalds@linux-foundation.org> - 2016-12-15 00:40 +0100
    Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable  function kbuild test robot <lkp@intel.com> - 2016-12-14 22:20 +0100
      Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 22:30 +0100
    [PATCH v4 3/4] secure_seq: use siphash instead of md5_transform "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 02:50 +0100
    [PATCH v4 2/4] siphash: add N[qd]word helpers "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 02:50 +0100
    [PATCH v4 4/4] random: use siphash instead of MD5 for get_random_int/long "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 02:50 +0100
    [PATCH v4 1/4] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 02:50 +0100

csiph-web