* Re: Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
@ 2016-12-16 21:01 Jason A. Donenfeld
2016-12-16 21:15 ` Hannes Frederic Sowa
0 siblings, 1 reply; 5+ messages in thread
From: Jason A. Donenfeld @ 2016-12-16 21:01 UTC (permalink / raw)
To: kernel-hardening, Theodore Ts'o, George Spelvin, Jason,
Andi Kleen, David Miller, David Laight, Daniel J . Bernstein,
Eric Biggers, Hannes Frederic Sowa, Jean-Philippe Aumasson,
Linux Crypto Mailing List, LKML, Andy Lutomirski, Netdev,
Tom Herbert, Linus Torvalds, Vegard Nossum
Hi Ted,
On Fri, Dec 16, 2016 at 9:43 PM, Theodore Ts'o <tytso@mit.edu> 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 rekeyed the secret used by get_random_int() and
> get_random_long() frequently (say, every minute or every 5 minutes),
> would that be sufficient for current and future users of these
> interfaces?
get_random_int() and get_random_long() should quite clearly use
SipHash with its secure 128-bit key and not HalfSipHash with its
64-bit key. HalfSipHash is absolutely insufficient for this use case.
Remember, we're already an order of magnitude or more faster than
md5...
With regard to periodic rekeying... since the secret is 128-bits, I
believe this is likely sufficient for _not_ rekeying. There's also the
chaining variable, to tie together invocations of the function. If
you'd prefer, instead of the chaining variable, we could use some
siphash output to mutate the original key, but I don't think this
approach is actually better and might introduce vulnerabilities. In my
opinion chaining+128bitkey is sufficient. On the other hand, rekeying
every X minutes is 3 or 4 lines of code. If you want (just say so),
I'll add this to my next revision.
You asked about the security requirements of these functions. The
comment says they're not cryptographically secure. And right now with
MD5 they're not. So the expectations are pretty low. Moving to siphash
adds some cryptographic security, certainly. Moving to siphash plus
rekeying adds a bit more. Of course, on recent x86, RDRAND is used
instead, so the cryptographic strength then depends on the thickness
of your tinfoil hat. So probably we shouldn't change what we advertise
these functions provide, even though we're certainly improving them
performance-wise and security-wise.
> P.S. I'll note that my performance figures when testing changes to
> get_random_int() were done on a 32-bit x86; Jason, I'm guessing your
> figures were using a 64-bit x86 system?. I haven't tried 32-bit ARM
> or smaller CPU's (e.g., mips, et. al.) that might be more likely to be
> used on IoT devices, but I'm worried about those too, of course.
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 uses the /dev/urandom pool, which means
various things need to kick in in the background to refill this.
Additionally, having to refill the buffered chacha output every 32 or
so longs isn't nice. These things together make for inconsistent and
hard to understand general operating system performance, because
get_random_long is called at every process startup for ASLR. So, in
the end, I believe there's another reason for going with the siphash
approach: deterministic performance.
Jason
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
2016-12-16 21:01 Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF Jason A. Donenfeld
@ 2016-12-16 21:15 ` Hannes Frederic Sowa
0 siblings, 0 replies; 5+ messages in thread
From: Hannes Frederic Sowa @ 2016-12-16 21:15 UTC (permalink / raw)
To: Jason A. Donenfeld, kernel-hardening, Theodore Ts'o,
George Spelvin, Andi Kleen, David Miller, David Laight,
Daniel J . Bernstein, Eric Biggers, Jean-Philippe Aumasson,
Linux Crypto Mailing List, LKML, Andy Lutomirski, Netdev,
Tom Herbert, Linus Torvalds, Vegard Nossum
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 uses the /dev/urandom pool, which means
> various things need to kick in in the background to refill this.
> Additionally, having to refill the buffered chacha output every 32 or
> so longs isn't nice. These things together make for inconsistent and
> hard to understand general operating system performance, because
> get_random_long is called at every process startup for ASLR. So, in
> the end, I believe there's another reason for going with the siphash
> approach: deterministic performance.
*Hust*, so from where do you generate your key for siphash if called
early from ASLR?
Bye,
Hannes
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
@ 2016-12-17 1:39 Jason A. Donenfeld
2016-12-17 2:15 ` George Spelvin
0 siblings, 1 reply; 5+ messages in thread
From: Jason A. Donenfeld @ 2016-12-17 1:39 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 Sat, Dec 17, 2016 at 12:44 AM, George Spelvin
<linux@sciencehorizons.net> 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
> HalfSipHash on 32-bit.
I already did this. Check my branch.
> - Document when it may or may not be used carefully.
Good idea. I'll write up some extensive documentation about all of
this, detailing use cases and our various conclusions.
> - #define get_random_int (unsigned)get_random_long
That's a good idea, since ultimately the other just casts in the
return value. I wonder if this could also lead to a similar aliasing
with arch_get_random_int, since I'm pretty sure all rdrand-like
instructions return native word size anyway.
> - Ted, Andy Lutorminski and I will try to figure out a construction of
> get_random_long() that we all like.
And me, I hope... No need to make this exclusive.
Jason
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
2016-12-17 1:39 Jason A. Donenfeld
@ 2016-12-17 2:15 ` George Spelvin
2016-12-17 15:41 ` Theodore Ts'o
0 siblings, 1 reply; 5+ messages in thread
From: George Spelvin @ 2016-12-17 2:15 UTC (permalink / raw)
To: Jason, linux
Cc: ak, davem, David.Laight, djb, ebiggers3, hannes,
jeanphilippe.aumasson, kernel-hardening, linux-crypto,
linux-kernel, luto, netdev, tom, torvalds, tytso, vegard.nossum
> 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 sure all rdrand-like
> instructions return native word size anyway.
Well, Intel's can return 16, 32 or 64 bits, and it makes a
small difference with reseed scheduling.
>> - Ted, Andy Lutorminski and I will try to figure out a construction of
>> get_random_long() that we all like.
> And me, I hope... No need to make this exclusive.
Gaah, engage brain before fingers. That was so obvious I didn't say
it, and the result came out sounding extremely rude.
A better (but longer) way to write it would be "I'm sorry that I, Ted,
and Andy are all arguing with you and each other about how to do this
and we can't finalize this part yet".
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
2016-12-17 2:15 ` George Spelvin
@ 2016-12-17 15:41 ` Theodore Ts'o
2016-12-17 16:14 ` Jeffrey Walton
0 siblings, 1 reply; 5+ messages in thread
From: Theodore Ts'o @ 2016-12-17 15:41 UTC (permalink / raw)
To: kernel-hardening
Cc: Jason, linux, ak, davem, David.Laight, djb, ebiggers3, hannes,
jeanphilippe.aumasson, linux-crypto, linux-kernel, luto, netdev,
tom, torvalds, vegard.nossum
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 long as we replace get_random_{long,int}() with something which is
(a) strictly better in terms of security given today's use of MD5, and
(b) which is strictly *faster* than the current construction on 32-bit
and 64-bit systems, we can do that, and can try to make it be faster
while maintaining some minimum level of security which is sufficient
for all current users of get_random_{long,int}() and which can be
clearly artificulated for future users of get_random_{long,int}().
The main worry at this point I have is benchmarking siphash on a
32-bit system. It may be that simply batching the chacha20 output so
that we're using the urandom construction more efficiently is the
better way to go, since that *does* meet the criteron of strictly more
secure and strictly faster than the current MD5 solution. I'm open to
using siphash, but I want to see the the 32-bit numbers first.
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 months or years, or else you might be weakening the ASLR
protections. If on the other hand, the hash table or the process will
be going away in a matter of seconds or minutes, the requirements with
respect to cryptographic strength go down significantly.
Now, maybe this doesn't matter that much if we can guarantee (or make
assumptions) that the attacker doesn't have unlimited access the
output stream of get_random_{long,int}(), or if it's being used in an
anti-DOS use case where it ultimately only needs to be harder than
alternate ways of attacking the system.
Rekeying every five minutes doesn't necessarily help the with respect
to ASLR, but it might reduce the amount of the output stream that
would be available to the attacker in order to be able to attack the
get_random_{long,int}() generator, and it also reduces the value of
doing that attack to only compromising the ASLR for those processes
started within that five minute window.
Cheers,
- Ted
P.S. I'm using ASLR as an example use case, above; of course we will
need to make similar eximainations of the other uses of
get_random_{long,int}().
P.P.S. We might also want to think about potentially defining
get_random_{long,int}() to be unambiguously strong, and then creating
a get_weak_random_{long,int}() which on platforms where performance
might be a consideration, it uses a weaker algorithm perhaps with some
kind of rekeying interval.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
2016-12-17 15:41 ` Theodore Ts'o
@ 2016-12-17 16:14 ` Jeffrey Walton
0 siblings, 0 replies; 5+ messages in thread
From: Jeffrey Walton @ 2016-12-17 16:14 UTC (permalink / raw)
To: Theodore Ts'o, kernel-hardening, Jason A. Donenfeld,
George Spelvin, ak, davem, David Laight, D. J. Bernstein,
Eric Biggers, Hannes Frederic Sowa, Jean-Philippe Aumasson,
linux-crypto, LKML, luto, Netdev, Tom Herbert, Linus Torvalds,
Vegard Nossum
> 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 months or years, or else you might be weakening the ASLR
> protections. If on the other hand, the hash table or the process will
> be going away in a matter of seconds or minutes, the requirements with
> respect to cryptographic strength go down significantly.
Perhaps SipHash-4-8 should be used instead of SipHash-2-4. I believe
SipHash-4-8 is recommended for the security conscious who want to be
more conservative in their security estimates.
SipHash-4-8 does not add much more processing. If you are clocking
SipHash-2-4 at 2.0 or 2.5 cpb, then SipHash-4-8 will run at 3.0 to
4.0. Both are well below MD5 times. (At least with the data sets I've
tested).
> Now, maybe this doesn't matter that much if we can guarantee (or make
> assumptions) that the attacker doesn't have unlimited access the
> output stream of get_random_{long,int}(), or if it's being used in an
> anti-DOS use case where it ultimately only needs to be harder than
> alternate ways of attacking the system.
>
> Rekeying every five minutes doesn't necessarily help the with respect
> to ASLR, but it might reduce the amount of the output stream that
> would be available to the attacker in order to be able to attack the
> get_random_{long,int}() generator, and it also reduces the value of
> doing that attack to only compromising the ASLR for those processes
> started within that five minute window.
Forgive my ignorance... I did not find reading on using the primitive
in a PRNG. Does anyone know what Aumasson or Bernstein have to say?
Aumasson's site does not seem to discuss the use case:
https://www.google.com/search?q=siphash+rng+site%3A131002.net. (And
their paper only mentions random-number once in a different context).
Making the leap from internal hash tables and short-lived network
packets to the rng case may leave something to be desired, especially
if the bits get used in unanticipated ways, like creating long term
private keys.
Jeff
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
@ 2016-12-15 23:00 Jean-Philippe Aumasson
2016-12-16 3:46 ` George Spelvin
0 siblings, 1 reply; 5+ messages in thread
From: Jean-Philippe Aumasson @ 2016-12-15 23:00 UTC (permalink / raw)
To: George Spelvin, ak, davem, David.Laight, ebiggers3, hannes,
Jason, kernel-hardening, linux-crypto, linux-kernel, luto,
netdev, tom, torvalds, tytso, vegard.nossum
Cc: djb
[-- Attachment #1: Type: text/plain, Size: 4109 bytes --]
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.
Regarding output size, are 64 bits sufficient?
On Thu, 15 Dec 2016 at 23:42, George Spelvin <linux@sciencehorizons.net>
wrote:
> > 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
> usage
> > poses a real security risk.
>
> To quantify that, jhash is 27 instructions per 12 bytes of input, with a
> dependency path length of 13 instructions. (24/12 in __jash_mix, plus
> 3/1 for adding the input to the state.) The final add + __jhash_final
> is 24 instructions with a path length of 15, which is close enough for
> this handwaving. Call it 18n instructions and 8n cycles for 8n bytes.
>
> SipHash (on a 64-bit machine) is 14 instructions with a dependency path
> length of 4 *per round*. Two rounds per 8 bytes, plus plus two adds
> and one cycle per input word, plus four rounds to finish makes 30n+46
> instructions and 9n+16 cycles for 8n bytes.
>
> So *if* you have a 64-bit 4-way superscalar machine, it's not that much
> slower once it gets going, but the four-round finalization is quite
> noticeable for short inputs.
>
> For typical kernel input lengths "within a factor of 2" is
> probably more accurate than "a tiny bit".
>
> You lose a factor of 2 if you machine is 2-way or non-superscalar,
> and a second factor of 2 if it's a 32-bit machine.
>
> I mention this because there are a lot of home routers and other netwoek
> appliances running Linux on 32-bit ARM and MIPS processors. For those,
> it's a factor of *eight*, which is a lot more than "a tiny bit".
>
> The real killer is if you don't have enough registers; SipHash performs
> horribly on i386 because it uses more state than i386 has registers.
>
> (If i386 performance is desired, you might ask Jean-Philippe for some
> rotate constants for a 32-bit variant with 64 bits of key. Note that
> SipHash's security proof requires that key length + input length is
> strictly less than the state size, so for a 4x32-bit variant, while
> you could stretch the key length a little, you'd have a hard limit at
> 95 bits.)
>
>
> A second point, the final XOR in SipHash is either a (very minor) design
> mistake, or an opportunity for optimization, depending on how you look
> at it. Look at the end of the function:
>
> >+ SIPROUND;
> >+ SIPROUND;
> >+ return (v0 ^ v1) ^ (v2 ^ v3);
>
> Expanding that out, you get:
> + 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);
> + return v0 ^ v1 ^ v2 ^ v3;
>
> Since the final XOR includes both v0 and v3, it's undoing the "v3 ^= v0"
> two lines earlier, so the value of v0 doesn't matter after its XOR into
> v1 on line one.
>
> The final SIPROUND and return can then be optimized to
>
> + v0 += v1; v1 = rol64(v1, 13); v1 ^= v0;
> + v2 += v3; v3 = rol64(v3, 16); v3 ^= v2;
> + v3 = rol64(v3, 21);
> + v2 += v1; v1 = rol64(v1, 17); v1 ^= v2; v2 = rol64(v2, 32);
> + return v1 ^ v2 ^ v3;
>
> A 32-bit implementation could further tweak the 4 instructions of
> v1 ^= v2; v2 = rol64(v2, 32); v1 ^= v2;
>
> gcc 6.2.1 -O3 compiles it to basically:
> v1.low ^= v2.low;
> v1.high ^= v2.high;
> v1.low ^= v2.high;
> v1.high ^= v2.low;
> but it could be written as:
> v2.low ^= v2.high;
> v1.low ^= v2.low;
> v1.high ^= v2.low;
>
> Alternatively, if it's for private use only (key not shared with other
> systems), a slightly stronger variant would "return v1 ^ v3;".
> (The final swap of v2 is dead code, but a compiler can spot that easily.)
>
[-- Attachment #2: Type: text/html, Size: 6336 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
2016-12-15 23:00 Jean-Philippe Aumasson
@ 2016-12-16 3:46 ` George Spelvin
2016-12-16 8:08 ` Jean-Philippe Aumasson
0 siblings, 1 reply; 5+ messages in thread
From: George Spelvin @ 2016-12-16 3:46 UTC (permalink / raw)
To: ak, davem, David.Laight, ebiggers3, hannes, Jason,
jeanphilippe.aumasson, kernel-hardening, linux-crypto,
linux-kernel, linux, luto, netdev, tom, torvalds, tytso,
vegard.nossum
Cc: djb
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 32-bit
machines.
First is the fact that a 64-bit SipHash round on a generic 32-bit machine
requires not twice as many instructions, but more than three.
Consider the core SipHash quarter-round operation:
a += b;
b = rotate_left(b, k)
b ^= a
The add and xor are equivalent between 32- and 64-bit rounds; twice the
instructions do twice the work. (There's a dependency via the carry
bit between the two halves of the add, but it ends up not being on the
critical path even in a superscalar implementation.)
The problem is the rotates. Although some particularly nice code is
possible on 32-bit ARM due to its support for shift-and-xor operations,
on a generic 32-bit CPU the rotate grows to 6 instructions with a 2-cycle
dependency chain (more in practice because barrel shifters are large and
even quad-issue CPUs can't do 4 shifts per cycle):
temp_lo = b_lo >> (32-k)
temp_hi = b_hi >> (32-k)
b_lo <<= k
b_hi <<= k
b_lo ^= temp_hi
b_hi ^= temp_lo
The resultant instruction counts and (assuming wide issue)
latencies are:
64-bit SipHash "Half" SipHash
Inst. Latency Inst. Latency
10 3 3 2 Quarter round
40 6 12 4 Full round
80 12 24 8 Two rounds
82 13 26 9 Mix in one word
82 13 52 18 Mix in 64 bits
166 26 61 18 Four round finalization + final XOR
248 39 113 36 Hash 64 bits
330 52 165 54 Hash 128 bits
412 65 217 72 Hash 192 bits
While the ideal latencies are actually better for the 64-bit algorithm,
that requires an unrealistic 6+-wide superscalar implementation that's
more than twice as wide as the 64-bit code requires (which is already
optimized for quad-issue). For a 1- or 2-wide processor, the instruction
counts dominate, and not only does the 64-bit algorithm take 60% more
time to mix in the same number of bytes, but the finalization rounds
bring the ratio to 2:1 for small inputs.
(And I haven't included the possible savings if the input size is an odd
number of 32-bit words, such as networking applications which include
the source/dest port numbers.)
Notes on particular processors:
- x86 can do a 64-bit rotate in 3 instructions and 2 cycles using
the SHLD/SHRD instructions instead:
movl %b_hi, %temp
shldl $k, %b_lo, %b_hi
shldl $k, %temp, %b_lo
... but as I mentioned the problem is registers. SipHash needs 8 32-bit
words plus at least one temporary, and 32-bit x86 has only 7 available.
(And compilers can rarely manage to keep more than 6 of them busy.)
- 64-bit SipHash is particularly efficient on 32-bit ARM due to its
support for shift-and-op instructions. The 64-bit shift and following
xor can be done in 4 instructions. So the only benefit is from the
reduced finalization.
- Double-width adds cost a little more on CPUs like MIPS and RISC-V without
condition codes.
- Certain particularly crappy uClinux processors with slow shifts
(68000, anyone?) really suffer from extra shifts.
One *weakly* requested feature: It might simplify some programming
interfaces if we could use the same key for multiple hash tables with a
1-word "tweak" (e.g. pointer to the hash table, so it could be assumed
non-zero if that helped) to make distinct functions. That would let us
more safely use a global key for multiple small hash tables without the
need to add code to generate and store key material for each place that
an unkeyed hash is replaced.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
2016-12-16 3:46 ` George Spelvin
@ 2016-12-16 8:08 ` Jean-Philippe Aumasson
2016-12-16 12:39 ` Jason A. Donenfeld
0 siblings, 1 reply; 5+ messages in thread
From: Jean-Philippe Aumasson @ 2016-12-16 8:08 UTC (permalink / raw)
To: George Spelvin, ak, davem, David.Laight, ebiggers3, hannes,
Jason, kernel-hardening, linux-crypto, linux-kernel, luto,
netdev, tom, torvalds, tytso, vegard.nossum
Cc: djb
[-- Attachment #1: Type: text/plain, Size: 4380 bytes --]
Here's a tentative HalfSipHash:
https://github.com/veorq/SipHash/blob/halfsiphash/halfsiphash.c
Haven't computed the cycle count nor measured its speed.
On Fri, Dec 16, 2016 at 4:46 AM George Spelvin <linux@sciencehorizons.net>
wrote:
> 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 32-bit
> machines.
>
> First is the fact that a 64-bit SipHash round on a generic 32-bit machine
> requires not twice as many instructions, but more than three.
>
> Consider the core SipHash quarter-round operation:
> a += b;
> b = rotate_left(b, k)
> b ^= a
>
> The add and xor are equivalent between 32- and 64-bit rounds; twice the
> instructions do twice the work. (There's a dependency via the carry
> bit between the two halves of the add, but it ends up not being on the
> critical path even in a superscalar implementation.)
>
> The problem is the rotates. Although some particularly nice code is
> possible on 32-bit ARM due to its support for shift-and-xor operations,
> on a generic 32-bit CPU the rotate grows to 6 instructions with a 2-cycle
> dependency chain (more in practice because barrel shifters are large and
> even quad-issue CPUs can't do 4 shifts per cycle):
>
> temp_lo = b_lo >> (32-k)
> temp_hi = b_hi >> (32-k)
> b_lo <<= k
> b_hi <<= k
> b_lo ^= temp_hi
> b_hi ^= temp_lo
>
> The resultant instruction counts and (assuming wide issue)
> latencies are:
>
> 64-bit SipHash "Half" SipHash
> Inst. Latency Inst. Latency
> 10 3 3 2 Quarter round
> 40 6 12 4 Full round
> 80 12 24 8 Two rounds
> 82 13 26 9 Mix in one word
> 82 13 52 18 Mix in 64 bits
> 166 26 61 18 Four round finalization + final XOR
> 248 39 113 36 Hash 64 bits
> 330 52 165 54 Hash 128 bits
> 412 65 217 72 Hash 192 bits
>
> While the ideal latencies are actually better for the 64-bit algorithm,
> that requires an unrealistic 6+-wide superscalar implementation that's
> more than twice as wide as the 64-bit code requires (which is already
> optimized for quad-issue). For a 1- or 2-wide processor, the instruction
> counts dominate, and not only does the 64-bit algorithm take 60% more
> time to mix in the same number of bytes, but the finalization rounds
> bring the ratio to 2:1 for small inputs.
>
> (And I haven't included the possible savings if the input size is an odd
> number of 32-bit words, such as networking applications which include
> the source/dest port numbers.)
>
>
> Notes on particular processors:
> - x86 can do a 64-bit rotate in 3 instructions and 2 cycles using
> the SHLD/SHRD instructions instead:
> movl %b_hi, %temp
> shldl $k, %b_lo, %b_hi
> shldl $k, %temp, %b_lo
> ... but as I mentioned the problem is registers. SipHash needs 8 32-bit
> words plus at least one temporary, and 32-bit x86 has only 7 available.
> (And compilers can rarely manage to keep more than 6 of them busy.)
> - 64-bit SipHash is particularly efficient on 32-bit ARM due to its
> support for shift-and-op instructions. The 64-bit shift and following
> xor can be done in 4 instructions. So the only benefit is from the
> reduced finalization.
> - Double-width adds cost a little more on CPUs like MIPS and RISC-V without
> condition codes.
> - Certain particularly crappy uClinux processors with slow shifts
> (68000, anyone?) really suffer from extra shifts.
>
> One *weakly* requested feature: It might simplify some programming
> interfaces if we could use the same key for multiple hash tables with a
> 1-word "tweak" (e.g. pointer to the hash table, so it could be assumed
> non-zero if that helped) to make distinct functions. That would let us
> more safely use a global key for multiple small hash tables without the
> need to add code to generate and store key material for each place that
> an unkeyed hash is replaced.
>
[-- Attachment #2: Type: text/html, Size: 6883 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
2016-12-16 8:08 ` Jean-Philippe Aumasson
@ 2016-12-16 12:39 ` Jason A. Donenfeld
2016-12-16 19:47 ` Tom Herbert
0 siblings, 1 reply; 5+ messages in thread
From: Jason A. Donenfeld @ 2016-12-16 12:39 UTC (permalink / raw)
To: Jean-Philippe Aumasson
Cc: George Spelvin, Andi Kleen, David Miller, David Laight,
Eric Biggers, Hannes Frederic Sowa, kernel-hardening,
Linux Crypto Mailing List, LKML, Andy Lutomirski, Netdev,
Tom Herbert, Linus Torvalds, Theodore Ts'o, vegard.nossum,
Daniel J . Bernstein
Hey JP,
On Fri, Dec 16, 2016 at 9:08 AM, Jean-Philippe Aumasson
<jeanphilippe.aumasson@gmail.com> 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. Wow!
I'll integrate this into my patchset and will write up some
documentation about when one should be used over the other.
Thanks again. Quite exciting.
Jason
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
2016-12-16 12:39 ` Jason A. Donenfeld
@ 2016-12-16 19:47 ` Tom Herbert
2016-12-16 20:44 ` Daniel Micay
0 siblings, 1 reply; 5+ messages in thread
From: Tom Herbert @ 2016-12-16 19:47 UTC (permalink / raw)
To: Jason A. Donenfeld
Cc: Jean-Philippe Aumasson, George Spelvin, Andi Kleen, David Miller,
David Laight, Eric Biggers, Hannes Frederic Sowa,
kernel-hardening, Linux Crypto Mailing List, LKML,
Andy Lutomirski, Netdev, Linus Torvalds, Theodore Ts'o,
vegard.nossum, Daniel J . Bernstein
On Fri, Dec 16, 2016 at 4:39 AM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> Hey JP,
>
> On Fri, Dec 16, 2016 at 9:08 AM, Jean-Philippe Aumasson
> <jeanphilippe.aumasson@gmail.com> 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.
>
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 security
advantages with halfsiphash?
Tom
> This is incredible. Really. Wow!
>
> I'll integrate this into my patchset and will write up some
> documentation about when one should be used over the other.
>
> Thanks again. Quite exciting.
>
> Jason
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
2016-12-16 19:47 ` Tom Herbert
@ 2016-12-16 20:44 ` Daniel Micay
0 siblings, 0 replies; 5+ messages in thread
From: Daniel Micay @ 2016-12-16 20:44 UTC (permalink / raw)
To: kernel-hardening, Jason A. Donenfeld
Cc: Jean-Philippe Aumasson, George Spelvin, Andi Kleen, David Miller,
David Laight, Eric Biggers, Hannes Frederic Sowa,
Linux Crypto Mailing List, LKML, Andy Lutomirski, Netdev,
Linus Torvalds, Theodore Ts'o, vegard.nossum,
Daniel J . Bernstein
[-- Attachment #1: Type: text/plain, Size: 465 bytes --]
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
usual construction for non-DoS mitigation, but why not try SipHash 1-3,
1-2, etc. for DoS mitigation?
Rust and Swift both went with SipHash 1-3 for hash tables.
[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 866 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2016-12-17 16:14 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-12-16 21:01 Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF Jason A. Donenfeld
2016-12-16 21:15 ` Hannes Frederic Sowa
-- strict thread matches above, loose matches on Subject: below --
2016-12-17 1:39 Jason A. Donenfeld
2016-12-17 2:15 ` George Spelvin
2016-12-17 15:41 ` Theodore Ts'o
2016-12-17 16:14 ` Jeffrey Walton
2016-12-15 23:00 Jean-Philippe Aumasson
2016-12-16 3:46 ` George Spelvin
2016-12-16 8:08 ` Jean-Philippe Aumasson
2016-12-16 12:39 ` Jason A. Donenfeld
2016-12-16 19:47 ` Tom Herbert
2016-12-16 20:44 ` Daniel Micay
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).