RE: [PATCH v5 1/4] siphash: add cryptographically secure PRF

David Laight wrote: > From: George Spelvin ... >> uint32_t >> hsiphash24(char const *in, size_t len, uint32_t const key[2]) >> { >> uint32_t c = key[0]; >> uint32_t d = key[1]; >> uint32_t a = 0x6c796765 ^ 0x736f6d65; >> uint32_t b = d ^ 0x74656462 ^ 0x646f7261; > I've not

Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

Hi Ted, On Sat, Dec 17, 2016 at 4:41 PM, Theodore Ts'o wrote: > On Fri, Dec 16, 2016 at 09:15:03PM -0500, George Spelvin wrote: >> >> - Ted, Andy Lutorminski and I will try to figure out a construction of >> >> get_random_long() that we all like. > > We don't have to find the

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

On Sat, Dec 17, 2016 at 3:55 PM, Jeffrey Walton wrote: > It may be prudent to include the endian reversal in the test to ensure > big endian machines produce expected results. Some closely related > testing on an old Apple PowerMac G5 revealed that result needed to be >

RE: [PATCH v5 1/4] siphash: add cryptographically secure PRF

From: George Spelvin > Sent: 17 December 2016 15:21 ... > uint32_t > hsiphash24(char const *in, size_t len, uint32_t const key[2]) > { > uint32_t c = key[0]; > uint32_t d = key[1]; > uint32_t a = 0x6c796765 ^ 0x736f6d65; > uint32_t b = d ^ 0x74656462 ^ 0x646f7261; I've

Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

> As far as half-siphash is concerned, it occurs to me that the main > problem will be those users who need to guarantee that output can't be > guessed over a long period of time. For example, if you have a > long-running process, then the output needs to remain unguessable over > potentially

Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

On Fri, Dec 16, 2016 at 09:15:03PM -0500, George Spelvin wrote: > >> - Ted, Andy Lutorminski and I will try to figure out a construction of > >> get_random_long() that we all like. We don't have to find the most optimal solution right away; we can approach this incrementally, after all. So

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

To follow up on my comments that your benchmark results were peculiar, here's my benchmark code. It just computes the hash of all n*(n+1)/2 possible non-empty substrings of a buffer of n (called "max" below) bytes. "cpb" is "cycles per byte". (The average length is (n+2)/3, c.f.

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

> diff --git a/lib/test_siphash.c b/lib/test_siphash.c > new file mode 100644 > index ..93549e4e22c5 > --- /dev/null > +++ b/lib/test_siphash.c > @@ -0,0 +1,83 @@ > +/* Test cases for siphash.c > + * > + * Copyright (C) 2016 Jason A. Donenfeld . All Rights > Reserved.

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

BTW, here's some SipHash code I wrote for Linux a while ago. My target application was ext4 directory hashing, resulting in different implementation choices, although I still think that a rolled-up implementation like this is reasonable. Reducing I-cache impact speeds up the calling code. One

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

> I already did this. Check my branch. Do you think it should return "u32" (as you currently have it) or "unsigned long"? I thought the latter, since it doesn't cost any more and makes more > I wonder if this could also lead to a similar aliasing > with arch_get_random_int, since I'm pretty

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

On Sat, Dec 17, 2016 at 12:44 AM, George Spelvin wrote: > Ths advice I'd give now is: > - Implement > unsigned long hsiphash(const void *data, size_t len, const unsigned long > key[2]) > .. as SipHash on 64-bit (maybe SipHash-1-3, still being discussed) and >

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

> 64-bit security for an RNG is not reasonable even with rekeying. No no > no. Considering we already have a massive speed-up here with the > secure version, there's zero reason to start weakening the security > because we're trigger happy with our benchmarks. No no no. Just to clarify, I was

Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

An idea I had which mght be useful: You could perhaps save two rounds in siphash_*u64. The final word with the length (called "b" in your implementation) only needs to be there if the input is variable-sized. If every use of a given key is of a fixed-size input, you don't need a length suffix.

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

On Fri, Dec 16, 2016 at 11:13 PM, George Spelvin wrote: > Remembering that on "real" machines it's full SipHash, then I'd say that > 64-bit security + rekeying seems reasonable. 64-bit security for an RNG is not reasonable even with rekeying. No no no. Considering we

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

On Fri, Dec 16, 2016 at 2:13 PM, George Spelvin wrote: >> What should we do with get_random_int() and get_random_long()? In >> some cases it's being used in performance sensitive areas, and where >> anti-DoS protection might be enough. In others, maybe not so much. >

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

> What should we do with get_random_int() and get_random_long()? In > some cases it's being used in performance sensitive areas, and where > anti-DoS protection might be enough. In others, maybe not so much. This is tricky. The entire get_random_int() structure is an abuse of the hash function

Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

Hi George, On Fri, Dec 16, 2016 at 10:25 PM, George Spelvin wrote: > But yes, the sequence number is supposed to be (random base) + (timestamp). > In the old days before Canter & Siegel when the internet was a nice place, > people just used a counter that started at

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

Jason A. Donenfeld wrote: > 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

Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

On Fri, Dec 16, 2016, at 22:01, Jason A. Donenfeld wrote: > Yes, on x86-64. But on i386 chacha20 incurs nearly the same kind of > slowdown as siphash, so I expect the comparison to be more or less > equal. There's another thing I really didn't like about your chacha20 > approach which is that it

Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

Hi Daniel, On Fri, Dec 16, 2016 at 9:44 PM, Daniel Micay wrote: > On Fri, 2016-12-16 at 11:47 -0800, Tom Herbert wrote: >> >> That's about 3x of jhash speed (7 nsecs). So that might closer >> to a more palatable replacement for jhash. Do we lose any security >> advantages

Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

Hi Ted, On Fri, Dec 16, 2016 at 9:43 PM, Theodore Ts'o wrote: > What should we do with get_random_int() and get_random_long()? In > some cases it's being used in performance sensitive areas, and where > anti-DoS protection might be enough. In others, maybe not so much. > > If we

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

On Fri, Dec 16, 2016 at 12:41 PM, George Spelvin wrote: > Tom Herbert wrote: >> Tested this. Distribution and avalanche effect are still good. Speed >> wise I see about a 33% improvement over siphash (20 nsecs/op versus 32 >> nsecs). That's about 3x of jhash speed (7

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

On Fri, Dec 16, 2016 at 9:17 PM, George Spelvin 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

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

Hi JP, On Fri, Dec 16, 2016 at 2:22 PM, Jean-Philippe Aumasson wrote: > It needs some basic security review, which I'll try do next week (check for > security margin, optimality of rotation counts, etc.). But after a lot of > experience with this kind of

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

On Fri, Dec 16, 2016 at 03:17:39PM -0500, George Spelvin wrote: > > That's a nice analysis. Might one conclude from that that hsiphash is > > not useful for our purposes? Or does it still remain useful for > > network facing code? > > I think for attacks where the threat is a DoS, it's usable.

Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

On Fri, 2016-12-16 at 11:47 -0800, Tom Herbert wrote: > > That's about 3x of jhash speed (7 nsecs). So that might closer > to a more palatable replacement for jhash. Do we lose any security > advantages with halfsiphash? Have you tested a lower round SipHash? Probably best to stick with the

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

On Fri, Dec 16, 2016 at 9:41 PM, George Spelvin 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,

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

Tom Herbert wrote: > Tested this. Distribution and avalanche effect are still good. Speed > wise I see about a 33% improvement over siphash (20 nsecs/op versus 32 > nsecs). That's about 3x of jhash speed (7 nsecs). So that might closer > to a more palatable replacement for jhash. Do we lose any

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

>> On a 64-bit machine, 64-bit SipHash is *always* faster than 32-bit, and >> should be used always. Don't even compile the 32-bit code, to prevent >> anyone accidentally using it, and make hsiphash an alias for siphash. > Fascinating! Okay. So I'll alias hsiphash to siphash on 64-bit then. I >

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

On Fri, Dec 16, 2016 at 4:39 AM, Jason A. Donenfeld wrote: > Hey JP, > > On Fri, Dec 16, 2016 at 9:08 AM, Jean-Philippe Aumasson > wrote: >> Here's a tentative HalfSipHash: >> https://github.com/veorq/SipHash/blob/halfsiphash/halfsiphash.c >> >>

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

Hi George, On Fri, Dec 16, 2016 at 6:36 PM, George Spelvin wrote: > A 128-bit output option was added to SipHash after the initial publication; > this is just the equivalent in 32-bit. > Personally, I'd put in a comment saying that "there's a 64-bit output > variant

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

> It appears that hsiphash can produce either 32-bit output or 64-bit > output, with the output length parameter as part of the hash algorithm > in there. When I code this for my kernel patchset, I very likely will > only implement one output length size. Right now I'm leaning toward > 32-bit. A

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

Hi David, On Fri, Dec 16, 2016 at 6:06 PM, David Laight wrote: > A 32bit hash would also remove all the issues about the alignment > of IP addresses (etc) on 64bit systems. The current replacements of md5_transform with siphash in the v6 patch series will continue to

RE: [PATCH v5 1/4] siphash: add cryptographically secure PRF

From: George Spelvin > Sent: 15 December 2016 23:29 > > If a halved version of SipHash can bring significant performance boost > > (with 32b words instead of 64b words) with an acceptable security level > > (64-bit enough?) then we may design such a version. > > I was thinking if the key could be

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

Hi JP & George, My function names: - SipHash -> siphash - HalfSipHash -> hsiphash It appears that hsiphash can produce either 32-bit output or 64-bit output, with the output length parameter as part of the hash algorithm in there. When I code this for my kernel patchset, I very likely will only

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

Hey JP, On Fri, Dec 16, 2016 at 9:08 AM, Jean-Philippe Aumasson wrote: > Here's a tentative HalfSipHash: > https://github.com/veorq/SipHash/blob/halfsiphash/halfsiphash.c > > Haven't computed the cycle count nor measured its speed. This is incredible. Really.

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

Jean-Philippe Aumasson wrote: > If a halved version of SipHash can bring significant performance boost > (with 32b words instead of 64b words) with an acceptable security level > (64-bit enough?) then we may design such a version. It would be fairly significant, a 2x speed benefit on a lot of

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

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

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

> If a halved version of SipHash can bring significant performance boost > (with 32b words instead of 64b words) with an acceptable security level > (64-bit enough?) then we may design such a version. I was thinking if the key could be pushed to 80 bits, that would be nice, but honestly 64 bits

Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF

> While SipHash is extremely fast for a cryptographically secure function, > it is likely a tiny bit slower than the insecure jhash, and so replacements > will be evaluated on a case-by-case basis based on whether or not the > difference in speed is negligible and whether or not the current jhash

[PATCH v5 1/4] siphash: add cryptographically secure PRF

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, or as a general PRF for short input use cases, such as sequence numbers or RNG chaining. For the first