linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH v5 0/4] The SipHash Patchset
@ 2016-12-15 20:29 Jason A. Donenfeld
  2016-12-15 20:30 ` [PATCH v5 1/4] siphash: add cryptographically secure PRF Jason A. Donenfeld
                   ` (4 more replies)
  0 siblings, 5 replies; 82+ messages in thread
From: Jason A. Donenfeld @ 2016-12-15 20:29 UTC (permalink / raw)
  To: Netdev, kernel-hardening, LKML, linux-crypto, David Laight,
	Ted Tso, Hannes Frederic Sowa, Linus Torvalds, Eric Biggers,
	Tom Herbert, George Spelvin, Vegard Nossum, ak, davem, luto
  Cc: Jason A. Donenfeld

Hey folks,

I think we're approaching the end of the review for this patchset and we're
getting somewhat close to being ready for it being queued up. At this point,
I've incorporated all of the extremely helpful and instructive suggestions
from the list.

For this v5, we now accept u64[2] as the key, so that alignment is taken
care of naturally. For other alignment issues, we have both the fast aligned
version and the unaligned version, depending on what's necessary. We've
worked out the issues for struct padding. The functions now take a void
pointer to avoid ugly casting, which also helps us shed the inline helper
functions which were not very pretty. The replacements of MD5 have been
benchmarked and show a big increase in speed. We've even come up with a
better naming scheme for dword/qword. All and all it's shaping up nicely.

So, if this series looks good to you, please send along your Reviewed-by,
so we can begin to get this completed. If there are still lingering issues,
let me know and I'll incorporated them into a v6 if necessary.

Thanks,
Jason

Jason A. Donenfeld (4):
  siphash: add cryptographically secure PRF
  siphash: add Nu{32,64} helpers
  secure_seq: use SipHash in place of MD5
  random: use SipHash in place of MD5

 drivers/char/random.c   |  32 +++----
 include/linux/siphash.h |  65 ++++++++++++++
 lib/Kconfig.debug       |   6 +-
 lib/Makefile            |   5 +-
 lib/siphash.c           | 223 ++++++++++++++++++++++++++++++++++++++++++++++++
 lib/test_siphash.c      | 101 ++++++++++++++++++++++
 net/core/secure_seq.c   | 133 +++++++++++------------------
 7 files changed, 460 insertions(+), 105 deletions(-)
 create mode 100644 include/linux/siphash.h
 create mode 100644 lib/siphash.c
 create mode 100644 lib/test_siphash.c

-- 
2.11.0

^ permalink raw reply	[flat|nested] 82+ messages in thread
[parent not found: <CAGiyFdfmiCMyHvAg=5sGh8KjBBrF0Wb4Qf=JLzJqUAx4yFSS3Q@mail.gmail.com>]
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
@ 2016-12-16 20:43 Jason A. Donenfeld
  0 siblings, 0 replies; 82+ messages in thread
From: Jason A. Donenfeld @ 2016-12-16 20:43 UTC (permalink / raw)
  To: George Spelvin
  Cc: Tom Herbert, Andi Kleen, David Miller, David Laight,
	Daniel J . Bernstein, Eric Biggers, Hannes Frederic Sowa,
	Jean-Philippe Aumasson, kernel-hardening,
	Linux Crypto Mailing List, LKML, Andy Lutomirski, Netdev,
	Linus Torvalds, Theodore Ts'o, Vegard Nossum

On Fri, Dec 16, 2016 at 9:41 PM, George Spelvin
<linux@sciencehorizons.net> wrote:
> What are you testing on?  And what input size?  And does "33% improvement"
> mean 4/3 the rate and 3/4 the time?  Or 2/3 the time and 3/2 the rate?

How that I've published my hsiphash implementation to my tree, it
should be possible to conduct the tests back to back with nearly
identical implementation strategies, to remove a potential source of
error.

^ permalink raw reply	[flat|nested] 82+ messages in thread
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
@ 2016-12-16 20:49 Jason A. Donenfeld
  2016-12-16 21:25 ` George Spelvin
  0 siblings, 1 reply; 82+ messages in thread
From: Jason A. Donenfeld @ 2016-12-16 20:49 UTC (permalink / raw)
  To: George Spelvin
  Cc: Andi Kleen, David Miller, David Laight, Daniel J . Bernstein,
	Eric Biggers, Hannes Frederic Sowa, Jean-Philippe Aumasson,
	kernel-hardening, Linux Crypto Mailing List, LKML,
	Andy Lutomirski, Netdev, Tom Herbert, Linus Torvalds,
	Theodore Ts'o, Vegard Nossum

On Fri, Dec 16, 2016 at 9:17 PM, George Spelvin
<linux@sciencehorizons.net> wrote:
> My (speaking enerally; I should walk through every hash table you've
> converted) opinion is that:
>
> - Hash tables, even network-facing ones, can all use hsiphash as long
>   as an attacker can only see collisions, i.e. ((H(x) ^ H(y)) & bits) ==
>   0, and the consequences of a successful attack is only more collisions
>   (timing).  While the attack is only 2x the cost (two hashes rather than
>   one to test a key), the knowledge of the collision is statistical,
>   especially for network attackers, which raises the cost of guessing
>   beyond an even more brute-force attack.
> - When the hash value directly visible (e.g. included in a network
>   packet), full SipHash should be the default.
> - Syncookies *could* use hsiphash, especially as there are
>   two keys in there.  Not sure if we need the performance.
> - For TCP ISNs, I'd prefer to use full SipHash.  I know this is
>   a very hot path, and if that's a performance bottleneck,
>   we can work harder on it.
>
> In particular, TCP ISNs *used* to rotate the key periodically,
> limiting the time available to an attacker to perform an
> attack before the secret goes stale and is useless.  commit
> 6e5714eaf77d79ae1c8b47e3e040ff5411b717ec upgraded to md5 and dropped
> the key rotation.

While I generally agree with this analysis for the most part, I do
think we should use SipHash and not HalfSipHash for syncookies.
Although the security risk is lower than with sequence numbers, it
previously used full MD5 for this, which means performance is not
generally a bottleneck and we'll get massive speedups no matter what,
whether using SipHash or HalfSipHash. In addition, using SipHash means
that the 128-bit key gives a larger margin and can be safe longterm.
So, I think we should err on the side of caution and stick with
SipHash in all cases in which we're upgrading from MD5.

In other words, only current jhash users should be potentially
eligible for hsiphash.


> Current code uses a 64 ns tick for the ISN, so it counts 2^24 per second.
> (32 bits wraps every 4.6 minutes.)  A 4-bit counter and 28-bit hash
> (or even 3+29) would work as long as the key is regenerated no more
> than once per minute.  (Just using the 4.6-minute ISN wrap time is the
> obvious simple implementation.)
>
> (Of course, I defer to DaveM's judgement on all network-related issues.)

I saw that jiffies addition in there and was wondering what it was all
about. It's currently added _after_ the siphash input, not before, to
keep with how the old algorithm worked. I'm not sure if this is
correct or if there's something wrong with that, as I haven't studied
how it works. If that jiffies should be part of the siphash input and
not added to the result, please tell me. Otherwise I'll keep things
how they are to avoid breaking something that seems to be working.

^ permalink raw reply	[flat|nested] 82+ messages in thread

end of thread, other threads:[~2016-12-22 19:50 UTC | newest]

Thread overview: 82+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-12-15 20:29 [PATCH v5 0/4] The SipHash Patchset Jason A. Donenfeld
2016-12-15 20:30 ` [PATCH v5 1/4] siphash: add cryptographically secure PRF Jason A. Donenfeld
2016-12-15 22:42   ` George Spelvin
2016-12-16  2:14   ` kbuild test robot
2016-12-17 14:55   ` Jeffrey Walton
2016-12-19 17:08     ` Jason A. Donenfeld
2016-12-15 20:30 ` [PATCH v5 2/4] siphash: add Nu{32,64} helpers Jason A. Donenfeld
2016-12-16 10:39   ` David Laight
2016-12-16 15:44     ` George Spelvin
2016-12-15 20:30 ` [PATCH v5 3/4] secure_seq: use SipHash in place of MD5 Jason A. Donenfeld
2016-12-16  9:59   ` David Laight
2016-12-16 15:57     ` Jason A. Donenfeld
2016-12-15 20:30 ` [PATCH v5 4/4] random: " Jason A. Donenfeld
2016-12-16  3:03 ` [PATCH v6 0/5] The SipHash Patchset Jason A. Donenfeld
2016-12-16  3:03   ` [PATCH v6 1/5] siphash: add cryptographically secure PRF Jason A. Donenfeld
2016-12-16  3:03   ` [PATCH v6 2/5] secure_seq: use SipHash in place of MD5 Jason A. Donenfeld
2016-12-16  3:03   ` [PATCH v6 3/5] random: " Jason A. Donenfeld
2016-12-16 21:31     ` Andy Lutomirski
2016-12-16  3:03   ` [PATCH v6 4/5] md5: remove from lib and only live in crypto Jason A. Donenfeld
2016-12-16  3:03   ` [PATCH v6 5/5] syncookies: use SipHash in place of SHA1 Jason A. Donenfeld
2016-12-21 23:02   ` [PATCH v7 0/6] The SipHash Patchset Jason A. Donenfeld
2016-12-21 23:02     ` [PATCH v7 1/6] siphash: add cryptographically secure PRF Jason A. Donenfeld
2016-12-22  1:40       ` Stephen Hemminger
2016-12-21 23:02     ` [PATCH v7 2/6] secure_seq: use SipHash in place of MD5 Jason A. Donenfeld
2016-12-21 23:02     ` [PATCH v7 3/6] random: " Jason A. Donenfeld
2016-12-21 23:13       ` Jason A. Donenfeld
2016-12-21 23:42       ` Andy Lutomirski
2016-12-22  2:07         ` Hannes Frederic Sowa
2016-12-22  2:09           ` Andy Lutomirski
2016-12-22  2:49           ` Jason A. Donenfeld
2016-12-22  3:12             ` Jason A. Donenfeld
2016-12-22  5:41             ` [kernel-hardening] " Theodore Ts'o
2016-12-22  6:03               ` Jason A. Donenfeld
2016-12-22 15:58                 ` Theodore Ts'o
2016-12-22 16:16                   ` Jason A. Donenfeld
2016-12-22 16:30                     ` Theodore Ts'o
2016-12-22 16:36                       ` Jason A. Donenfeld
2016-12-22 12:47               ` Hannes Frederic Sowa
2016-12-22 13:10                 ` Jason A. Donenfeld
2016-12-22 15:05                   ` Hannes Frederic Sowa
2016-12-22 15:12                     ` Jason A. Donenfeld
2016-12-22 15:29                       ` Jason A. Donenfeld
2016-12-22 15:33                         ` Hannes Frederic Sowa
2016-12-22 15:41                           ` Jason A. Donenfeld
2016-12-22 15:51                             ` Hannes Frederic Sowa
2016-12-22 15:53                               ` Jason A. Donenfeld
2016-12-22 15:54                   ` Theodore Ts'o
2016-12-22 18:08                     ` Hannes Frederic Sowa
2016-12-22 18:13                       ` Jason A. Donenfeld
2016-12-22 19:50                       ` Theodore Ts'o
2016-12-22  2:31         ` Jason A. Donenfeld
2016-12-21 23:02     ` [PATCH v7 4/6] md5: remove from lib and only live in crypto Jason A. Donenfeld
2016-12-21 23:02     ` [PATCH v7 5/6] syncookies: use SipHash in place of SHA1 Jason A. Donenfeld
2016-12-21 23:02     ` [PATCH v7 6/6] siphash: implement HalfSipHash1-3 for hash tables Jason A. Donenfeld
2016-12-22  0:46       ` Andi Kleen
     [not found] <CAGiyFdfmiCMyHvAg=5sGh8KjBBrF0Wb4Qf=JLzJqUAx4yFSS3Q@mail.gmail.com>
2016-12-15 23:28 ` [PATCH v5 1/4] siphash: add cryptographically secure PRF George Spelvin
2016-12-16 17:06   ` David Laight
2016-12-16 17:09     ` Jason A. Donenfeld
2016-12-16  3:46 ` George Spelvin
     [not found]   ` <CAGiyFdd6_LVzUUfFcaqMyub1c2WPvWUzAQDCH+Aza-_t6mvmXg@mail.gmail.com>
2016-12-16 12:39     ` Jason A. Donenfeld
2016-12-16 19:47       ` Tom Herbert
2016-12-16 20:41         ` George Spelvin
2016-12-16 20:57           ` Tom Herbert
2016-12-17 15:21         ` George Spelvin
2016-12-19 14:14           ` David Laight
2016-12-19 18:10             ` George Spelvin
     [not found]       ` <CAGiyFddB_HT3H2yhYQ5rprYZ487rJ4iCaH9uPJQD57hiPbn9ng@mail.gmail.com>
2016-12-16 15:51         ` Jason A. Donenfeld
2016-12-16 17:36           ` George Spelvin
2016-12-16 18:00             ` Jason A. Donenfeld
2016-12-16 20:17               ` George Spelvin
2016-12-16 20:43                 ` Theodore Ts'o
2016-12-16 22:13                   ` George Spelvin
2016-12-16 22:15                     ` Andy Lutomirski
2016-12-16 22:18                     ` Jason A. Donenfeld
2016-12-16 23:44                       ` George Spelvin
2016-12-17  1:39                         ` Jason A. Donenfeld
2016-12-17  2:15                           ` George Spelvin
2016-12-17 12:42           ` George Spelvin
2016-12-16 20:39         ` Jason A. Donenfeld
2016-12-16 20:43 Jason A. Donenfeld
2016-12-16 20:49 Jason A. Donenfeld
2016-12-16 21:25 ` George Spelvin

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).