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

Groups > linux.kernel > #1541690 > unrolled thread

[PATCH v2 1/4] siphash: add cryptographically secure hashtable function

Back to article view | Back to linux.kernel

Contents

  [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

Page 3 of 3 — ← Prev page 1 2 [3]

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

Hey Tom,

On Wed, Dec 14, 2016 at 10:35 PM, Tom Herbert <tom@herbertland.com> wrote:
> Those look good, although I would probably just do 1,2,3 words and
> then have a function that takes n words like jhash. Might want to call
> these dword to distinguish from 32 bit words in jhash.

So actually jhash_Nwords makes no sense, since it takes dwords
(32-bits) not words (16-bits). The siphash analog should be called
siphash24_Nqwords.

I think what I'll do is change what I already have to:
siphash24_1qword
siphash24_2qword
siphash24_3qword
siphash24_4qword

And then add some static inline helpers to assist with smaller u32s
like ipv4 addresses called:

siphash24_2dword
siphash24_4dword
siphash24_6dword
siphash24_8dword

While we're having something new, might as well call it the right thing.


> Also, what is the significance of "24" in the function and constant
> names? Can we just drop that and call this siphash?

SipHash is actually a family of PRFs, differentiated by the number of
SIPROUNDs after each 64-bit input is processed and the number of
SIPROUNDs at the very end of the function. The best trade-off of speed
and security for kernel usage is 2 rounds after each 64-bit input and
4 rounds at the end of the function. This doesn't fall to any known
cryptanalysis and it's very fast.

[toc] | [prev] | [next] | [standalone]

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

Hey Tom,

On Thu, Dec 15, 2016 at 12:14 AM, Tom Herbert <tom@herbertland.com> wrote:
> I'm confused, doesn't 2dword == 1qword? Anyway, I think the qword
> functions are good enough. If someone needs to hash over some odd
> length they can either put them in a structure padded to 64 bits or
> call the hash function that takes a byte length.

Yes. Here's an example:

static inline u64 siphash24_2dwords(const u32 a, const u32 b, const u8
key[SIPHASH24_KEY_LEN])
{
       return siphash24_1qword(((u64)b << 32) | a, key);
}

This winds up being extremely useful and syntactically convenient in a
few places. Check out my git branch in about 10 minutes or wait for v4
to be posted tomorrow; these are nice helpers.

> I'd still drop the "24" unless you really think we're going to have
> multiple variants coming into the kernel.

Okay. I don't have a problem with this, unless anybody has some reason
to the contrary.

Jason

[toc] | [prev] | [next] | [standalone]

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

On Thu, 15 Dec 2016, Jason A. Donenfeld wrote:
> > I'd still drop the "24" unless you really think we're going to have
> > multiple variants coming into the kernel.
> 
> Okay. I don't have a problem with this, unless anybody has some reason
> to the contrary.

What if the 2/4-round version falls and we need more rounds to withstand 
future cryptoanalysis? We'd then have siphash_ and siphash48_ functions, 
no? My amateurish bike-shedding argument would be "let's keep the 24 then" :-)

C.
-- 
BOFH excuse #354:

Chewing gum on /dev/sd3c

[toc] | [prev] | [next] | [standalone]

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

On Wed, Dec 14, 2016 at 2:56 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> Hey Tom,
>
> On Wed, Dec 14, 2016 at 10:35 PM, Tom Herbert <tom@herbertland.com> wrote:
>> Those look good, although I would probably just do 1,2,3 words and
>> then have a function that takes n words like jhash. Might want to call
>> these dword to distinguish from 32 bit words in jhash.
>
> So actually jhash_Nwords makes no sense, since it takes dwords
> (32-bits) not words (16-bits). The siphash analog should be called
> siphash24_Nqwords.
>
Yeah, that's a "bug" with jhash function names.

> I think what I'll do is change what I already have to:
> siphash24_1qword
> siphash24_2qword
> siphash24_3qword
> siphash24_4qword
>
> And then add some static inline helpers to assist with smaller u32s
> like ipv4 addresses called:
>
> siphash24_2dword
> siphash24_4dword
> siphash24_6dword
> siphash24_8dword
>
> While we're having something new, might as well call it the right thing.
>
I'm confused, doesn't 2dword == 1qword? Anyway, I think the qword
functions are good enough. If someone needs to hash over some odd
length they can either put them in a structure padded to 64 bits or
call the hash function that takes a byte length.

>
>> Also, what is the significance of "24" in the function and constant
>> names? Can we just drop that and call this siphash?
>
> SipHash is actually a family of PRFs, differentiated by the number of
> SIPROUNDs after each 64-bit input is processed and the number of
> SIPROUNDs at the very end of the function. The best trade-off of speed
> and security for kernel usage is 2 rounds after each 64-bit input and
> 4 rounds at the end of the function. This doesn't fall to any known
> cryptanalysis and it's very fast.

I'd still drop the "24" unless you really think we're going to have
multiple variants coming into the kernel.

Tom

[toc] | [prev] | [next] | [standalone]

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

Hey Linus,

On Thu, Dec 15, 2016 at 12:30 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> No. The bug is talking about "words" in the first place.
>
> Depending on your background, a "word" can be generally be either 16
> bits or 32 bits (or, in some cases, 18 bits).
>
> In theory, a 64-bit entity can be a "word" too, but pretty much nobody
> uses that. Even architectures that started out with a 64-bit register
> size and never had any smaller historical baggage (eg alpha) tend to
> call 32-bit entities "words".
>
> So 16 bits can be a word, but some people/architectures will call it a
> "half-word".
>
> To make matters even more confusing, a "quadword" is generally always
> 64 bits, regardless of the size of "word".
>
> So please try to avoid the use of "word" entirely. It's too ambiguous,
> and it's not even helpful as a "size of the native register". It's
> almost purely random.
>
> For the kernel, we tend use
>
>  - uX for types that have specific sizes (X being the number of bits)
>
>  - "[unsigned] long" for native register size
>
> But never "word".

The voice of reason. Have a desired name for this function family?

siphash_3u64s
siphash_3u64
siphash_three_u64
siphash_3sixityfourbitintegers

Or does your reasonable dislike of "word" still allow for the use of
dword and qword, so that the current function names of:

siphash_3qwords
siphash_6dwords

are okay?

Jason

[toc] | [prev] | [next] | [standalone]

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

On Wed, Dec 14, 2016 at 3:34 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>
> Or does your reasonable dislike of "word" still allow for the use of
> dword and qword, so that the current function names of:

dword really is confusing to people.

If you have a MIPS background, it means 64 bits. While to people with
Windows programming backgrounds it means 32 bits.

Please try to avoid using it.

As mentioned, I think almost everybody agrees on the "q" part being 64
bits, but that may just be me not having seen it in any other context.

And before anybody points it out - yes, we already have lots of uses
of "dword" in various places. But they tend to be mostly
hardware-specific - either architectures or drivers.

So I'd _prefer_ to try to keep "word" and "dword" away from generic
helper routines. But it's not like anything is really black and white.

           Linus

[toc] | [prev] | [next] | [standalone]

#1542622 — RE: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function

From: Linus Torvalds
> Sent: 15 December 2016 00:11
> On Wed, Dec 14, 2016 at 3:34 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> >
> > Or does your reasonable dislike of "word" still allow for the use of
> > dword and qword, so that the current function names of:
> 
> dword really is confusing to people.
>
> If you have a MIPS background, it means 64 bits. While to people with
> Windows programming backgrounds it means 32 bits.

Guess what a DWORD_PTR is on 64bit windows ...
(it is an integer type).

	David

[toc] | [prev] | [next] | [standalone]

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

On Wed, Dec 14, 2016 at 2:56 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>
> So actually jhash_Nwords makes no sense, since it takes dwords
> (32-bits) not words (16-bits). The siphash analog should be called
> siphash24_Nqwords.

No. The bug is talking about "words" in the first place.

Depending on your background, a "word" can be generally be either 16
bits or 32 bits (or, in some cases, 18 bits).

In theory, a 64-bit entity can be a "word" too, but pretty much nobody
uses that. Even architectures that started out with a 64-bit register
size and never had any smaller historical baggage (eg alpha) tend to
call 32-bit entities "words".

So 16 bits can be a word, but some people/architectures will call it a
"half-word".

To make matters even more confusing, a "quadword" is generally always
64 bits, regardless of the size of "word".

So please try to avoid the use of "word" entirely. It's too ambiguous,
and it's not even helpful as a "size of the native register". It's
almost purely random.

For the kernel, we tend use

 - uX for types that have specific sizes (X being the number of bits)

 - "[unsigned] long" for native register size

But never "word".

           Linus

[toc] | [prev] | [next] | [standalone]

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

[Multipart message — attachments visible in raw view] — view raw

Hi Jason,

[auto build test ERROR on linus/master]
[also build test ERROR on v4.9 next-20161214]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]

url:    https://github.com/0day-ci/linux/commits/Jason-A-Donenfeld/siphash-add-cryptographically-secure-hashtable-function/20161215-041458
config: i386-randconfig-i1-201650 (attached as .config)
compiler: gcc-4.8 (Debian 4.8.4-1) 4.8.4
reproduce:
        # save the attached .config to linux build tree
        make ARCH=i386 

All errors (new ones prefixed by >>):

   lib/test_siphash.c: In function 'siphash_test_init':
>> lib/test_siphash.c:49:2: error: requested alignment is not an integer constant
     u8 in[64] __aligned(SIPHASH24_ALIGNMENT);
     ^
   lib/test_siphash.c:50:2: error: requested alignment is not an integer constant
     u8 k[16] __aligned(SIPHASH24_ALIGNMENT);
     ^

vim +49 lib/test_siphash.c

    43		0x6ca4ecb15c5f91e1ULL, 0x9f626da15c9625f3ULL, 0xe51b38608ef25f57ULL,
    44		0x958a324ceb064572ULL
    45	};
    46	
    47	static int __init siphash_test_init(void)
    48	{
  > 49		u8 in[64] __aligned(SIPHASH24_ALIGNMENT);
    50		u8 k[16] __aligned(SIPHASH24_ALIGNMENT);
    51		u8 in_unaligned[65];
    52		u8 k_unaligned[65];

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

[toc] | [prev] | [next] | [standalone]

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

Interesting. Evidently gcc 4.8 doesn't like my use of:

enum siphash_lengths {
       SIPHASH24_KEY_LEN = 16,
       SIPHASH24_ALIGNMENT = 8
};

I'll convert this to the more boring:

#define SIPHASH24_KEY_LEN 16
#define SIPHASH24_ALIGNMENT 8

[toc] | [prev] | [next] | [standalone]

#1542434 — [PATCH v4 3/4] secure_seq: use siphash instead of md5_transform

This gives a clear speed and security improvement. Siphash is both
faster and is more solid crypto than the aging MD5.

Rather than manually filling MD5 buffers, for IPv6, we simply create
a layout by a simple anonymous struct, for which gcc generates
rather efficient code. For IPv4, we pass the values directly to the
short input convenience functions.

Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
Cc: Andi Kleen <ak@linux.intel.com>
Cc: David Miller <davem@davemloft.net>
Cc: David Laight <David.Laight@aculab.com>
Cc: Tom Herbert <tom@herbertland.com>
Cc: Hannes Frederic Sowa <hannes@stressinduktion.org>
---
Changes from v3->v4:

  - For the IPv4 cases, we can now use the Ndwords helper functions,
    which make the calculation simpler and faster.
  - For the IPv6 cases, which still use the struct, we no longer pack
    the struct and instead simply pad until the nearest 64-bit size, so
    that it also avoids the slow branch for left-overs in siphash().

 net/core/secure_seq.c | 133 ++++++++++++++++++++------------------------------
 1 file changed, 52 insertions(+), 81 deletions(-)

diff --git a/net/core/secure_seq.c b/net/core/secure_seq.c
index 88a8e429fc3e..8fed79932ec4 100644
--- a/net/core/secure_seq.c
+++ b/net/core/secure_seq.c
@@ -1,3 +1,5 @@
+/* Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. */
+
 #include <linux/kernel.h>
 #include <linux/init.h>
 #include <linux/cryptohash.h>
@@ -8,14 +10,14 @@
 #include <linux/ktime.h>
 #include <linux/string.h>
 #include <linux/net.h>
-
+#include <linux/siphash.h>
 #include <net/secure_seq.h>
 
 #if IS_ENABLED(CONFIG_IPV6) || IS_ENABLED(CONFIG_INET)
+#include <linux/in6.h>
 #include <net/tcp.h>
-#define NET_SECRET_SIZE (MD5_MESSAGE_BYTES / 4)
 
-static u32 net_secret[NET_SECRET_SIZE] ____cacheline_aligned;
+static u8 net_secret[SIPHASH_KEY_LEN] __aligned(SIPHASH_ALIGNMENT);
 
 static __always_inline void net_secret_init(void)
 {
@@ -44,44 +46,42 @@ static u32 seq_scale(u32 seq)
 u32 secure_tcpv6_sequence_number(const __be32 *saddr, const __be32 *daddr,
 				 __be16 sport, __be16 dport, u32 *tsoff)
 {
-	u32 secret[MD5_MESSAGE_BYTES / 4];
-	u32 hash[MD5_DIGEST_WORDS];
-	u32 i;
-
+	const struct {
+		struct in6_addr saddr;
+		struct in6_addr daddr;
+		__be16 sport;
+		__be16 dport;
+		u32 padding;
+	} __aligned(SIPHASH_ALIGNMENT) combined = {
+		.saddr = *(struct in6_addr *)saddr,
+		.daddr = *(struct in6_addr *)daddr,
+		.sport = sport,
+		.dport = dport
+	};
+	u64 hash;
 	net_secret_init();
-	memcpy(hash, saddr, 16);
-	for (i = 0; i < 4; i++)
-		secret[i] = net_secret[i] + (__force u32)daddr[i];
-	secret[4] = net_secret[4] +
-		(((__force u16)sport << 16) + (__force u16)dport);
-	for (i = 5; i < MD5_MESSAGE_BYTES / 4; i++)
-		secret[i] = net_secret[i];
-
-	md5_transform(hash, secret);
-
-	*tsoff = sysctl_tcp_timestamps == 1 ? hash[1] : 0;
-	return seq_scale(hash[0]);
+	hash = siphash((const u8 *)&combined, sizeof(combined), net_secret);
+	*tsoff = sysctl_tcp_timestamps == 1 ? (hash >> 32) : 0;
+	return seq_scale(hash);
 }
 EXPORT_SYMBOL(secure_tcpv6_sequence_number);
 
 u32 secure_ipv6_port_ephemeral(const __be32 *saddr, const __be32 *daddr,
 			       __be16 dport)
 {
-	u32 secret[MD5_MESSAGE_BYTES / 4];
-	u32 hash[MD5_DIGEST_WORDS];
-	u32 i;
-
+	const struct {
+		struct in6_addr saddr;
+		struct in6_addr daddr;
+		__be16 dport;
+		u16 padding1;
+		u32 padding2;
+	} __aligned(SIPHASH_ALIGNMENT) combined = {
+		.saddr = *(struct in6_addr *)saddr,
+		.daddr = *(struct in6_addr *)daddr,
+		.dport = dport
+	};
 	net_secret_init();
-	memcpy(hash, saddr, 16);
-	for (i = 0; i < 4; i++)
-		secret[i] = net_secret[i] + (__force u32) daddr[i];
-	secret[4] = net_secret[4] + (__force u32)dport;
-	for (i = 5; i < MD5_MESSAGE_BYTES / 4; i++)
-		secret[i] = net_secret[i];
-
-	md5_transform(hash, secret);
-
-	return hash[0];
+	return siphash((const u8 *)&combined, sizeof(combined), net_secret);
 }
 EXPORT_SYMBOL(secure_ipv6_port_ephemeral);
 #endif
@@ -91,33 +91,17 @@ EXPORT_SYMBOL(secure_ipv6_port_ephemeral);
 u32 secure_tcp_sequence_number(__be32 saddr, __be32 daddr,
 			       __be16 sport, __be16 dport, u32 *tsoff)
 {
-	u32 hash[MD5_DIGEST_WORDS];
-
+	u64 hash;
 	net_secret_init();
-	hash[0] = (__force u32)saddr;
-	hash[1] = (__force u32)daddr;
-	hash[2] = ((__force u16)sport << 16) + (__force u16)dport;
-	hash[3] = net_secret[15];
-
-	md5_transform(hash, net_secret);
-
-	*tsoff = sysctl_tcp_timestamps == 1 ? hash[1] : 0;
-	return seq_scale(hash[0]);
+	hash = siphash_4dwords(saddr, daddr, sport, dport, net_secret);
+	*tsoff = sysctl_tcp_timestamps == 1 ? (hash >> 32) : 0;
+	return seq_scale(hash);
 }
 
 u32 secure_ipv4_port_ephemeral(__be32 saddr, __be32 daddr, __be16 dport)
 {
-	u32 hash[MD5_DIGEST_WORDS];
-
 	net_secret_init();
-	hash[0] = (__force u32)saddr;
-	hash[1] = (__force u32)daddr;
-	hash[2] = (__force u32)dport ^ net_secret[14];
-	hash[3] = net_secret[15];
-
-	md5_transform(hash, net_secret);
-
-	return hash[0];
+	return siphash_4dwords(saddr, daddr, dport, 0, net_secret);
 }
 EXPORT_SYMBOL_GPL(secure_ipv4_port_ephemeral);
 #endif
@@ -126,21 +110,11 @@ EXPORT_SYMBOL_GPL(secure_ipv4_port_ephemeral);
 u64 secure_dccp_sequence_number(__be32 saddr, __be32 daddr,
 				__be16 sport, __be16 dport)
 {
-	u32 hash[MD5_DIGEST_WORDS];
 	u64 seq;
-
 	net_secret_init();
-	hash[0] = (__force u32)saddr;
-	hash[1] = (__force u32)daddr;
-	hash[2] = ((__force u16)sport << 16) + (__force u16)dport;
-	hash[3] = net_secret[15];
-
-	md5_transform(hash, net_secret);
-
-	seq = hash[0] | (((u64)hash[1]) << 32);
+	seq = siphash_4dwords(saddr, daddr, sport, dport, net_secret);
 	seq += ktime_get_real_ns();
 	seq &= (1ull << 48) - 1;
-
 	return seq;
 }
 EXPORT_SYMBOL(secure_dccp_sequence_number);
@@ -149,26 +123,23 @@ EXPORT_SYMBOL(secure_dccp_sequence_number);
 u64 secure_dccpv6_sequence_number(__be32 *saddr, __be32 *daddr,
 				  __be16 sport, __be16 dport)
 {
-	u32 secret[MD5_MESSAGE_BYTES / 4];
-	u32 hash[MD5_DIGEST_WORDS];
+	const struct {
+		struct in6_addr saddr;
+		struct in6_addr daddr;
+		__be16 sport;
+		__be16 dport;
+		u32 padding;
+	} __aligned(SIPHASH_ALIGNMENT) combined = {
+		.saddr = *(struct in6_addr *)saddr,
+		.daddr = *(struct in6_addr *)daddr,
+		.sport = sport,
+		.dport = dport
+	};
 	u64 seq;
-	u32 i;
-
 	net_secret_init();
-	memcpy(hash, saddr, 16);
-	for (i = 0; i < 4; i++)
-		secret[i] = net_secret[i] + (__force u32)daddr[i];
-	secret[4] = net_secret[4] +
-		(((__force u16)sport << 16) + (__force u16)dport);
-	for (i = 5; i < MD5_MESSAGE_BYTES / 4; i++)
-		secret[i] = net_secret[i];
-
-	md5_transform(hash, secret);
-
-	seq = hash[0] | (((u64)hash[1]) << 32);
+	seq = siphash((const u8 *)&combined, sizeof(combined), net_secret);
 	seq += ktime_get_real_ns();
 	seq &= (1ull << 48) - 1;
-
 	return seq;
 }
 EXPORT_SYMBOL(secure_dccpv6_sequence_number);
-- 
2.11.0

[toc] | [prev] | [next] | [standalone]

#1542436 — [PATCH v4 2/4] siphash: add N[qd]word helpers

These restore parity with the jhash interface by providing high
performance helpers for common input sizes.

Linus doesn't like the use of "qword" and "dword", but I haven't been
able to come up with another name for these that fits as well.

Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
Cc: Tom Herbert <tom@herbertland.com>
---
Changes from v2->v4:

  - Rather than just wrapping siphash(), we actually implement the
    fully optimized and manually unrolled version, so that lengths
    don't need to be checked and loops don't need to branch.
  - We now provide both 32-bit and 64-bit versions, both of which
    are quite useful for different circumstances.

 include/linux/siphash.h |  31 ++++++++++
 lib/siphash.c           | 161 ++++++++++++++++++++++++++++++++++++------------
 lib/test_siphash.c      |  18 ++++++
 3 files changed, 170 insertions(+), 40 deletions(-)

diff --git a/include/linux/siphash.h b/include/linux/siphash.h
index d0bcca7b992b..6e7c2a421bd9 100644
--- a/include/linux/siphash.h
+++ b/include/linux/siphash.h
@@ -27,4 +27,35 @@ static inline u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIP
 u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN]);
 #endif
 
+u64 siphash_1qword(const u64 a, const u8 key[SIPHASH_KEY_LEN]);
+u64 siphash_2qwords(const u64 a, const u64 b, const u8 key[SIPHASH_KEY_LEN]);
+u64 siphash_3qwords(const u64 a, const u64 b, const u64 c, const u8 key[SIPHASH_KEY_LEN]);
+u64 siphash_4qwords(const u64 a, const u64 b, const u64 c, const u64 d, const u8 key[SIPHASH_KEY_LEN]);
+
+static inline u64 siphash_2dwords(const u32 a, const u32 b, const u8 key[SIPHASH_KEY_LEN])
+{
+	return siphash_1qword((u64)b << 32 | a, key);
+}
+
+static inline u64 siphash_4dwords(const u32 a, const u32 b, const u32 c, const u32 d,
+				  const u8 key[SIPHASH_KEY_LEN])
+{
+	return siphash_2qwords((u64)b << 32 | a, (u64)d << 32 | c, key);
+}
+
+static inline u64 siphash_6dwords(const u32 a, const u32 b, const u32 c, const u32 d,
+				  const u32 e, const u32 f, const u8 key[SIPHASH_KEY_LEN])
+{
+	return siphash_3qwords((u64)b << 32 | a, (u64)d << 32 | c, (u64)f << 32 | e,
+			       key);
+}
+
+static inline u64 siphash_8dwords(const u32 a, const u32 b, const u32 c, const u32 d,
+				  const u32 e, const u32 f, const u32 g, const u32 h,
+				  const u8 key[SIPHASH_KEY_LEN])
+{
+	return siphash_4qwords((u64)b << 32 | a, (u64)d << 32 | c, (u64)f << 32 | e,
+			       (u64)h << 32 | g, key);
+}
+
 #endif /* _LINUX_SIPHASH_H */
diff --git a/lib/siphash.c b/lib/siphash.c
index b500231f61cd..c13d2b2bb76e 100644
--- a/lib/siphash.c
+++ b/lib/siphash.c
@@ -38,6 +38,31 @@ static inline u64 le64_to_cpuvp(const void *p)
 	v2 += v1; v1 = rol64(v1, 17); v1 ^= v2; v2 = rol64(v2, 32); \
 	} while(0)
 
+#define PREAMBLE(len) \
+	u64 v0 = 0x736f6d6570736575ULL; \
+	u64 v1 = 0x646f72616e646f6dULL; \
+	u64 v2 = 0x6c7967656e657261ULL; \
+	u64 v3 = 0x7465646279746573ULL; \
+	u64 b = ((u64)len) << 56; \
+	u64 k0 = le64_to_cpuvp(key); \
+	u64 k1 = le64_to_cpuvp(key + sizeof(u64)); \
+	v3 ^= k1; \
+	v2 ^= k0; \
+	v1 ^= k1; \
+	v0 ^= k0;
+
+#define POSTAMBLE \
+	v3 ^= b; \
+	SIPROUND; \
+	SIPROUND; \
+	v0 ^= b; \
+	v2 ^= 0xff; \
+	SIPROUND; \
+	SIPROUND; \
+	SIPROUND; \
+	SIPROUND; \
+	return (v0 ^ v1) ^ (v2 ^ v3);
+
 /**
  * siphash - compute 64-bit siphash PRF value
  * @data: buffer to hash, must be aligned to SIPHASH_ALIGNMENT
@@ -46,20 +71,10 @@ static inline u64 le64_to_cpuvp(const void *p)
  */
 u64 siphash(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN])
 {
-	u64 v0 = 0x736f6d6570736575ULL;
-	u64 v1 = 0x646f72616e646f6dULL;
-	u64 v2 = 0x6c7967656e657261ULL;
-	u64 v3 = 0x7465646279746573ULL;
-	u64 b = ((u64)len) << 56;
-	u64 k0 = le64_to_cpuvp(key);
-	u64 k1 = le64_to_cpuvp(key + sizeof(u64));
-	u64 m;
 	const u8 *end = data + len - (len % sizeof(u64));
 	const u8 left = len & (sizeof(u64) - 1);
-	v3 ^= k1;
-	v2 ^= k0;
-	v1 ^= k1;
-	v0 ^= k0;
+	u64 m;
+	PREAMBLE(len)
 	for (; data != end; data += sizeof(u64)) {
 		m = le64_to_cpuvp(data);
 		v3 ^= m;
@@ -81,16 +96,7 @@ u64 siphash(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN])
 	case 1: b |= data[0];
 	}
 #endif
-	v3 ^= b;
-	SIPROUND;
-	SIPROUND;
-	v0 ^= b;
-	v2 ^= 0xff;
-	SIPROUND;
-	SIPROUND;
-	SIPROUND;
-	SIPROUND;
-	return (v0 ^ v1) ^ (v2 ^ v3);
+	POSTAMBLE
 }
 EXPORT_SYMBOL(siphash);
 
@@ -103,20 +109,10 @@ EXPORT_SYMBOL(siphash);
  */
 u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN])
 {
-	u64 v0 = 0x736f6d6570736575ULL;
-	u64 v1 = 0x646f72616e646f6dULL;
-	u64 v2 = 0x6c7967656e657261ULL;
-	u64 v3 = 0x7465646279746573ULL;
-	u64 b = ((u64)len) << 56;
-	u64 k0 = le64_to_cpuvp(key);
-	u64 k1 = le64_to_cpuvp(key + sizeof(u64));
-	u64 m;
 	const u8 *end = data + len - (len % sizeof(u64));
 	const u8 left = len & (sizeof(u64) - 1);
-	v3 ^= k1;
-	v2 ^= k0;
-	v1 ^= k1;
-	v0 ^= k0;
+	u64 m;
+	PREAMBLE(len)
 	for (; data != end; data += sizeof(u64)) {
 		m = get_unaligned_le64(data);
 		v3 ^= m;
@@ -138,16 +134,101 @@ u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN])
 	case 1: b |= data[0];
 	}
 #endif
-	v3 ^= b;
+	POSTAMBLE
+}
+EXPORT_SYMBOL(siphash_unaligned);
+#endif
+
+/**
+ * siphash_1qword - compute 64-bit siphash PRF value of 1 quad-word
+ * @first: first quadword
+ * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT
+ */
+u64 siphash_1qword(const u64 first, const u8 key[SIPHASH_KEY_LEN])
+{
+	PREAMBLE(8)
+	v3 ^= first;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= first;
+	POSTAMBLE
+}
+EXPORT_SYMBOL(siphash_1qword);
+
+/**
+ * siphash_2qwords - compute 64-bit siphash PRF value of 2 quad-words
+ * @first: first quadword
+ * @second: second quadword
+ * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT
+ */
+u64 siphash_2qwords(const u64 first, const u64 second, const u8 key[SIPHASH_KEY_LEN])
+{
+	PREAMBLE(16)
+	v3 ^= first;
 	SIPROUND;
 	SIPROUND;
-	v0 ^= b;
-	v2 ^= 0xff;
+	v0 ^= first;
+	v3 ^= second;
 	SIPROUND;
 	SIPROUND;
+	v0 ^= second;
+	POSTAMBLE
+}
+EXPORT_SYMBOL(siphash_2qwords);
+
+/**
+ * siphash_3qwords - compute 64-bit siphash PRF value of 3 quad-words
+ * @first: first quadword
+ * @second: second quadword
+ * @third: third quadword
+ * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT
+ */
+u64 siphash_3qwords(const u64 first, const u64 second, const u64 third, const u8 key[SIPHASH_KEY_LEN])
+{
+	PREAMBLE(24)
+	v3 ^= first;
 	SIPROUND;
 	SIPROUND;
-	return (v0 ^ v1) ^ (v2 ^ v3);
+	v0 ^= first;
+	v3 ^= second;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= second;
+	v3 ^= third;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= third;
+	POSTAMBLE
 }
-EXPORT_SYMBOL(siphash24_unaligned);
-#endif
+EXPORT_SYMBOL(siphash_3qwords);
+
+/**
+ * siphash_4qwords - compute 64-bit siphash PRF value of 4 quad-words
+ * @first: first quadword
+ * @second: second quadword
+ * @third: third quadword
+ * @forth: forth quadword
+ * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT
+ */
+u64 siphash_4qwords(const u64 first, const u64 second, const u64 third, const u64 forth, const u8 key[SIPHASH_KEY_LEN])
+{
+	PREAMBLE(32)
+	v3 ^= first;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= first;
+	v3 ^= second;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= second;
+	v3 ^= third;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= third;
+	v3 ^= forth;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= forth;
+	POSTAMBLE
+}
+EXPORT_SYMBOL(siphash_4qwords);
diff --git a/lib/test_siphash.c b/lib/test_siphash.c
index 444725c7834f..9925a325af35 100644
--- a/lib/test_siphash.c
+++ b/lib/test_siphash.c
@@ -68,6 +68,24 @@ static int __init siphash_test_init(void)
 			ret = -EINVAL;
 		}
 	}
+	if (siphash_1qword(0x0706050403020100ULL, k) != test_vectors[8]) {
+		pr_info("self-test 1qword: FAIL\n");
+		ret = -EINVAL;
+	}
+	if (siphash_2qwords(0x0706050403020100ULL, 0x0f0e0d0c0b0a0908ULL, k) != test_vectors[16]) {
+		pr_info("self-test 2qwords: FAIL\n");
+		ret = -EINVAL;
+	}
+	if (siphash_3qwords(0x0706050403020100ULL, 0x0f0e0d0c0b0a0908ULL,
+			    0x1716151413121110ULL, k) != test_vectors[24]) {
+		pr_info("self-test 3qwords: FAIL\n");
+		ret = -EINVAL;
+	}
+	if (siphash_4qwords(0x0706050403020100ULL, 0x0f0e0d0c0b0a0908ULL,
+			    0x1716151413121110ULL, 0x1f1e1d1c1b1a1918ULL, k) != test_vectors[32]) {
+		pr_info("self-test 4qwords: FAIL\n");
+		ret = -EINVAL;
+	}
 	if (!ret)
 		pr_info("self-tests: pass\n");
 	return ret;
-- 
2.11.0

[toc] | [prev] | [next] | [standalone]

#1542437 — [PATCH v4 4/4] random: use siphash instead of MD5 for get_random_int/long

This duplicates the current algorithm for get_random_int/long, but uses
siphash instead. This comes with several benefits. It's certainly
faster and more cryptographically secure than MD5. This patch also
separates hashed fields into three values instead of one, in order to
increase diffusion.

The previous MD5 algorithm used a per-cpu MD5 state, which caused
successive calls to the function to chain upon each other. While it's
not entirely clear that this kind of chaining is absolutely necessary
when using a secure PRF like siphash, it can't hurt, and the timing of
the call chain does add a degree of natural entropy. So, in keeping with
this design, instead of the massive per-cpu 64-byte MD5 state, there is
instead a per-cpu previously returned value for chaining.

The speed benefits are substantial:

                | siphash | md5    | speedup |
		------------------------------
get_random_long | 137130  | 415983 | 3.03x   |
get_random_int  | 86384   | 343323 | 3.97x   |

Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
Cc: Ted Tso <tytso@mit.edu>
---
Changes from v3->v4:

  - Speedups by using the 3qwords function.

 drivers/char/random.c | 30 +++++++++++-------------------
 1 file changed, 11 insertions(+), 19 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d6876d506220..8e1d1cfface6 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -262,6 +262,7 @@
 #include <linux/syscalls.h>
 #include <linux/completion.h>
 #include <linux/uuid.h>
+#include <linux/siphash.h>
 #include <crypto/chacha20.h>
 
 #include <asm/processor.h>
@@ -2042,7 +2043,7 @@ struct ctl_table random_table[] = {
 };
 #endif 	/* CONFIG_SYSCTL */
 
-static u32 random_int_secret[MD5_MESSAGE_BYTES / 4] ____cacheline_aligned;
+static u8 random_int_secret[SIPHASH_KEY_LEN] __aligned(SIPHASH_ALIGNMENT);
 
 int random_int_secret_init(void)
 {
@@ -2050,8 +2051,7 @@ int random_int_secret_init(void)
 	return 0;
 }
 
-static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash)
-		__aligned(sizeof(unsigned long));
+static DEFINE_PER_CPU(u64, get_random_int_chaining);
 
 /*
  * Get a random word for internal kernel use only. Similar to urandom but
@@ -2061,19 +2061,15 @@ static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash)
  */
 unsigned int get_random_int(void)
 {
-	__u32 *hash;
 	unsigned int ret;
+	u64 *chaining;
 
 	if (arch_get_random_int(&ret))
 		return ret;
 
-	hash = get_cpu_var(get_random_int_hash);
-
-	hash[0] += current->pid + jiffies + random_get_entropy();
-	md5_transform(hash, random_int_secret);
-	ret = hash[0];
-	put_cpu_var(get_random_int_hash);
-
+	chaining = &get_cpu_var(get_random_int_chaining);
+	ret = *chaining = siphash_3qwords(*chaining, jiffies, random_get_entropy() + current->pid, random_int_secret);
+	put_cpu_var(get_random_int_chaining);
 	return ret;
 }
 EXPORT_SYMBOL(get_random_int);
@@ -2083,19 +2079,15 @@ EXPORT_SYMBOL(get_random_int);
  */
 unsigned long get_random_long(void)
 {
-	__u32 *hash;
 	unsigned long ret;
+	u64 *chaining;
 
 	if (arch_get_random_long(&ret))
 		return ret;
 
-	hash = get_cpu_var(get_random_int_hash);
-
-	hash[0] += current->pid + jiffies + random_get_entropy();
-	md5_transform(hash, random_int_secret);
-	ret = *(unsigned long *)hash;
-	put_cpu_var(get_random_int_hash);
-
+	chaining = &get_cpu_var(get_random_int_chaining);
+	ret = *chaining = siphash_3qwords(*chaining, jiffies, random_get_entropy() + current->pid, random_int_secret);
+	put_cpu_var(get_random_int_chaining);
 	return ret;
 }
 EXPORT_SYMBOL(get_random_long);
-- 
2.11.0

[toc] | [prev] | [next] | [standalone]

#1542438 — [PATCH v4 1/4] siphash: add cryptographically secure hashtable function

SipHash is a 64-bit keyed hash function that is actually a
cryptographically secure PRF, like HMAC. Except SipHash is super fast,
and is meant to be used as a hashtable keyed lookup function.

There are a variety of attacks known as "hashtable poisoning" in which an
attacker forms some data such that the hash of that data will be the
same, and then preceeds to fill up all entries of a hashbucket. This is
a realistic and well-known denial-of-service vector.

Linux developers already seem to be aware that this is an issue, and
various places that use hash tables in, say, a network context, use a
non-cryptographically secure function (usually jhash) and then try to
twiddle with the key on a time basis (or in many cases just do nothing
and hope that nobody notices). While this is an admirable attempt at
solving the problem, it doesn't actually fix it. SipHash fixes it.

(It fixes it in such a sound way that you could even build a stream
cipher out of SipHash that would resist the modern cryptanalysis.)

There are a modicum of places in the kernel that are vulnerable to
hashtable poisoning attacks, either via userspace vectors or network
vectors, and there's not a reliable mechanism inside the kernel at the
moment to fix it. The first step toward fixing these issues is actually
getting a secure primitive into the kernel for developers to use. Then
we can, bit by bit, port things over to it as deemed appropriate.

Secondly, a few places are using MD5 for creating secure sequence
numbers, port numbers, or fast random numbers. Siphash is a faster, more
fitting, and more secure replacement for MD5 in those situations.

Dozens of languages are already using this internally for their hash
tables. Some of the BSDs already use this in their kernels. SipHash is
a widely known high-speed solution to a widely known problem, and it's
time we catch-up.

Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
Cc: Daniel J. Bernstein <djb@cr.yp.to>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Eric Biggers <ebiggers3@gmail.com>
Cc: David Laight <David.Laight@aculab.com>
---
Changes from v3->v4:

  - Renamed from siphash24 to siphash.
  - Using macros instead of enums for old gcc.
  - Keys must now always be aligned, even for the unaligned data
    one, since generally these keys are just long term secrets
    which are easy to ensure are aligned anyway.

 include/linux/siphash.h |  30 ++++++++++
 lib/Kconfig.debug       |   6 +-
 lib/Makefile            |   5 +-
 lib/siphash.c           | 153 ++++++++++++++++++++++++++++++++++++++++++++++++
 lib/test_siphash.c      |  84 ++++++++++++++++++++++++++
 5 files changed, 273 insertions(+), 5 deletions(-)
 create mode 100644 include/linux/siphash.h
 create mode 100644 lib/siphash.c
 create mode 100644 lib/test_siphash.c

diff --git a/include/linux/siphash.h b/include/linux/siphash.h
new file mode 100644
index 000000000000..d0bcca7b992b
--- /dev/null
+++ b/include/linux/siphash.h
@@ -0,0 +1,30 @@
+/* Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
+ *
+ * This file is provided under a dual BSD/GPLv2 license.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ *
+ * This implementation is specifically for SipHash2-4.
+ */
+
+#ifndef _LINUX_SIPHASH_H
+#define _LINUX_SIPHASH_H
+
+#include <linux/types.h>
+
+#define SIPHASH_KEY_LEN 16
+#define SIPHASH_ALIGNMENT 8
+
+u64 siphash(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN]);
+
+#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
+static inline u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN])
+{
+	return siphash(data, len, key);
+}
+#else
+u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN]);
+#endif
+
+#endif /* _LINUX_SIPHASH_H */
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index e6327d102184..32bbf689fc46 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1843,9 +1843,9 @@ config TEST_HASH
 	tristate "Perform selftest on hash functions"
 	default n
 	help
-	  Enable this option to test the kernel's integer (<linux/hash,h>)
-	  and string (<linux/stringhash.h>) hash functions on boot
-	  (or module load).
+	  Enable this option to test the kernel's integer (<linux/hash.h>),
+	  string (<linux/stringhash.h>), and siphash (<linux/siphash.h>)
+	  hash functions on boot (or module load).
 
 	  This is intended to help people writing architecture-specific
 	  optimized versions.  If unsure, say N.
diff --git a/lib/Makefile b/lib/Makefile
index 50144a3aeebd..71d398b04a74 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -22,7 +22,8 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 sha1.o chacha20.o md5.o irq_regs.o argv_split.o \
 	 flex_proportions.o ratelimit.o show_mem.o \
 	 is_single_threaded.o plist.o decompress.o kobject_uevent.o \
-	 earlycpio.o seq_buf.o nmi_backtrace.o nodemask.o win_minmax.o
+	 earlycpio.o seq_buf.o siphash.o \
+	 nmi_backtrace.o nodemask.o win_minmax.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
@@ -44,7 +45,7 @@ obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
 obj-y += kstrtox.o
 obj-$(CONFIG_TEST_BPF) += test_bpf.o
 obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
-obj-$(CONFIG_TEST_HASH) += test_hash.o
+obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o
 obj-$(CONFIG_TEST_KASAN) += test_kasan.o
 obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
 obj-$(CONFIG_TEST_LKM) += test_module.o
diff --git a/lib/siphash.c b/lib/siphash.c
new file mode 100644
index 000000000000..b500231f61cd
--- /dev/null
+++ b/lib/siphash.c
@@ -0,0 +1,153 @@
+/* Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
+ *
+ * This file is provided under a dual BSD/GPLv2 license.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ *
+ * This implementation is specifically for SipHash2-4.
+ */
+
+#include <linux/siphash.h>
+#include <linux/kernel.h>
+#include <asm/unaligned.h>
+
+#if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
+#include <linux/dcache.h>
+#include <asm/word-at-a-time.h>
+#endif
+
+static inline u16 le16_to_cpuvp(const void *p)
+{
+	return le16_to_cpup(p);
+}
+static inline u32 le32_to_cpuvp(const void *p)
+{
+	return le32_to_cpup(p);
+}
+static inline u64 le64_to_cpuvp(const void *p)
+{
+	return le64_to_cpup(p);
+}
+
+#define SIPROUND \
+	do { \
+	v0 += v1; v1 = rol64(v1, 13); v1 ^= v0; v0 = rol64(v0, 32); \
+	v2 += v3; v3 = rol64(v3, 16); v3 ^= v2; \
+	v0 += v3; v3 = rol64(v3, 21); v3 ^= v0; \
+	v2 += v1; v1 = rol64(v1, 17); v1 ^= v2; v2 = rol64(v2, 32); \
+	} while(0)
+
+/**
+ * siphash - compute 64-bit siphash PRF value
+ * @data: buffer to hash, must be aligned to SIPHASH_ALIGNMENT
+ * @size: size of @data
+ * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT
+ */
+u64 siphash(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN])
+{
+	u64 v0 = 0x736f6d6570736575ULL;
+	u64 v1 = 0x646f72616e646f6dULL;
+	u64 v2 = 0x6c7967656e657261ULL;
+	u64 v3 = 0x7465646279746573ULL;
+	u64 b = ((u64)len) << 56;
+	u64 k0 = le64_to_cpuvp(key);
+	u64 k1 = le64_to_cpuvp(key + sizeof(u64));
+	u64 m;
+	const u8 *end = data + len - (len % sizeof(u64));
+	const u8 left = len & (sizeof(u64) - 1);
+	v3 ^= k1;
+	v2 ^= k0;
+	v1 ^= k1;
+	v0 ^= k0;
+	for (; data != end; data += sizeof(u64)) {
+		m = le64_to_cpuvp(data);
+		v3 ^= m;
+		SIPROUND;
+		SIPROUND;
+		v0 ^= m;
+	}
+#if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
+	if (left)
+		b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) & bytemask_from_count(left)));
+#else
+	switch (left) {
+	case 7: b |= ((u64)data[6]) << 48;
+	case 6: b |= ((u64)data[5]) << 40;
+	case 5: b |= ((u64)data[4]) << 32;
+	case 4: b |= le32_to_cpuvp(data); break;
+	case 3: b |= ((u64)data[2]) << 16;
+	case 2: b |= le16_to_cpuvp(data); break;
+	case 1: b |= data[0];
+	}
+#endif
+	v3 ^= b;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= b;
+	v2 ^= 0xff;
+	SIPROUND;
+	SIPROUND;
+	SIPROUND;
+	SIPROUND;
+	return (v0 ^ v1) ^ (v2 ^ v3);
+}
+EXPORT_SYMBOL(siphash);
+
+#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
+/**
+ * siphash - compute 64-bit siphash PRF value, without alignment requirements
+ * @data: buffer to hash
+ * @size: size of @data
+ * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT
+ */
+u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN])
+{
+	u64 v0 = 0x736f6d6570736575ULL;
+	u64 v1 = 0x646f72616e646f6dULL;
+	u64 v2 = 0x6c7967656e657261ULL;
+	u64 v3 = 0x7465646279746573ULL;
+	u64 b = ((u64)len) << 56;
+	u64 k0 = le64_to_cpuvp(key);
+	u64 k1 = le64_to_cpuvp(key + sizeof(u64));
+	u64 m;
+	const u8 *end = data + len - (len % sizeof(u64));
+	const u8 left = len & (sizeof(u64) - 1);
+	v3 ^= k1;
+	v2 ^= k0;
+	v1 ^= k1;
+	v0 ^= k0;
+	for (; data != end; data += sizeof(u64)) {
+		m = get_unaligned_le64(data);
+		v3 ^= m;
+		SIPROUND;
+		SIPROUND;
+		v0 ^= m;
+	}
+#if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
+	if (left)
+		b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) & bytemask_from_count(left)));
+#else
+	switch (left) {
+	case 7: b |= ((u64)data[6]) << 48;
+	case 6: b |= ((u64)data[5]) << 40;
+	case 5: b |= ((u64)data[4]) << 32;
+	case 4: b |= get_unaligned_le32(data); break;
+	case 3: b |= ((u64)data[2]) << 16;
+	case 2: b |= get_unaligned_le16(data); break;
+	case 1: b |= data[0];
+	}
+#endif
+	v3 ^= b;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= b;
+	v2 ^= 0xff;
+	SIPROUND;
+	SIPROUND;
+	SIPROUND;
+	SIPROUND;
+	return (v0 ^ v1) ^ (v2 ^ v3);
+}
+EXPORT_SYMBOL(siphash24_unaligned);
+#endif
diff --git a/lib/test_siphash.c b/lib/test_siphash.c
new file mode 100644
index 000000000000..444725c7834f
--- /dev/null
+++ b/lib/test_siphash.c
@@ -0,0 +1,84 @@
+/* Test cases for siphash.c
+ *
+ * Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
+ *
+ * This file is provided under a dual BSD/GPLv2 license.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ *
+ * This implementation is specifically for SipHash2-4.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/siphash.h>
+#include <linux/kernel.h>
+#include <linux/string.h>
+#include <linux/errno.h>
+#include <linux/module.h>
+
+/* Test vectors taken from official reference source available at:
+ *     https://131002.net/siphash/siphash24.c
+ */
+static const u64 test_vectors[64] = {
+	0x726fdb47dd0e0e31ULL, 0x74f839c593dc67fdULL, 0x0d6c8009d9a94f5aULL,
+	0x85676696d7fb7e2dULL, 0xcf2794e0277187b7ULL, 0x18765564cd99a68dULL,
+	0xcbc9466e58fee3ceULL, 0xab0200f58b01d137ULL, 0x93f5f5799a932462ULL,
+	0x9e0082df0ba9e4b0ULL, 0x7a5dbbc594ddb9f3ULL, 0xf4b32f46226bada7ULL,
+	0x751e8fbc860ee5fbULL, 0x14ea5627c0843d90ULL, 0xf723ca908e7af2eeULL,
+	0xa129ca6149be45e5ULL, 0x3f2acc7f57c29bdbULL, 0x699ae9f52cbe4794ULL,
+	0x4bc1b3f0968dd39cULL, 0xbb6dc91da77961bdULL, 0xbed65cf21aa2ee98ULL,
+	0xd0f2cbb02e3b67c7ULL, 0x93536795e3a33e88ULL, 0xa80c038ccd5ccec8ULL,
+	0xb8ad50c6f649af94ULL, 0xbce192de8a85b8eaULL, 0x17d835b85bbb15f3ULL,
+	0x2f2e6163076bcfadULL, 0xde4daaaca71dc9a5ULL, 0xa6a2506687956571ULL,
+	0xad87a3535c49ef28ULL, 0x32d892fad841c342ULL, 0x7127512f72f27cceULL,
+	0xa7f32346f95978e3ULL, 0x12e0b01abb051238ULL, 0x15e034d40fa197aeULL,
+	0x314dffbe0815a3b4ULL, 0x027990f029623981ULL, 0xcadcd4e59ef40c4dULL,
+	0x9abfd8766a33735cULL, 0x0e3ea96b5304a7d0ULL, 0xad0c42d6fc585992ULL,
+	0x187306c89bc215a9ULL, 0xd4a60abcf3792b95ULL, 0xf935451de4f21df2ULL,
+	0xa9538f0419755787ULL, 0xdb9acddff56ca510ULL, 0xd06c98cd5c0975ebULL,
+	0xe612a3cb9ecba951ULL, 0xc766e62cfcadaf96ULL, 0xee64435a9752fe72ULL,
+	0xa192d576b245165aULL, 0x0a8787bf8ecb74b2ULL, 0x81b3e73d20b49b6fULL,
+	0x7fa8220ba3b2eceaULL, 0x245731c13ca42499ULL, 0xb78dbfaf3a8d83bdULL,
+	0xea1ad565322a1a0bULL, 0x60e61c23a3795013ULL, 0x6606d7e446282b93ULL,
+	0x6ca4ecb15c5f91e1ULL, 0x9f626da15c9625f3ULL, 0xe51b38608ef25f57ULL,
+	0x958a324ceb064572ULL
+};
+
+static int __init siphash_test_init(void)
+{
+	u8 in[64] __aligned(SIPHASH_ALIGNMENT);
+	u8 k[16] __aligned(SIPHASH_ALIGNMENT);
+	u8 in_unaligned[65];
+	u8 i;
+	int ret = 0;
+
+	for (i = 0; i < 16; ++i)
+		k[i] = i;
+	for (i = 0; i < 64; ++i) {
+		in[i] = i;
+		in_unaligned[i + 1] = i;
+		if (siphash(in, i, k) != test_vectors[i]) {
+			pr_info("self-test aligned %u: FAIL\n", i + 1);
+			ret = -EINVAL;
+		}
+		if (siphash_unaligned(in_unaligned + 1, i, k) != test_vectors[i]) {
+			pr_info("self-test unaligned %u: FAIL\n", i + 1);
+			ret = -EINVAL;
+		}
+	}
+	if (!ret)
+		pr_info("self-tests: pass\n");
+	return ret;
+}
+
+static void __exit siphash_test_exit(void)
+{
+}
+
+module_init(siphash_test_init);
+module_exit(siphash_test_exit);
+
+MODULE_AUTHOR("Jason A. Donenfeld <Jason@zx2c4.com>");
+MODULE_LICENSE("Dual BSD/GPL");
-- 
2.11.0

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

Back to top | Article view | linux.kernel

csiph-web