* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: Tom Herbert @ 2016-12-16 20:57 UTC (permalink / raw)
To: George Spelvin
Cc: Jason A. Donenfeld, Andi Kleen, David S. Miller, David Laight,
Daniel J . Bernstein, Eric Biggers, Hannes Frederic Sowa,
Jean-Philippe Aumasson, kernel-hardening,
Linux Crypto Mailing List, LKML, Andy Lutomirski,
Linux Kernel Network Developers, Linus Torvalds,
Theodore Ts'o, vegard.nossum
In-Reply-To: <20161216204128.25034.qmail@ns.sciencehorizons.net>
On Fri, Dec 16, 2016 at 12:41 PM, George Spelvin
<linux@sciencehorizons.net> 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 nsecs). So that might closer
>> to a more palatable replacement for jhash. Do we lose any security
>> advantages with halfsiphash?
>
> 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?
>
Sorry, that is over an IPv4 tuple. Intel(R) Xeon(R) CPU E5-2660 0 @
2.20GHz. Recoded the function I was using to look like more like 64
bit version and yes it is indeed slower.
> These are very odd results. On a 64-bit machine, SipHash should be the
> same speed per round, and faster because it hashes more data per round.
> (Unless you're hitting some unexpected cache/decode effect due to REX
> prefixes.)
>
> On a 32-bit machine (other than ARM, where your results might make sense,
> or maybe if you're hashing large amounts of data), the difference should
> be larger.
>
> And yes, there is a *significant* security loss. SipHash is 128 bits
> ("don't worry about it"). hsiphash is 64 bits, which is known breakable
> ("worry about it"), so we have to do a careful analysis of the cost of
> a successful attack.
>
> As mentioned in the e-mails that just flew by, hsiphash is intended
> *only* for 32-bit machines which bog down on full SipHash. On all 64-bit
> machines, it will be implemented as an alias for SipHash and the security
> concerns will Just Go Away.
>
> The place where hsiphash is expected to make a big difference is 32-bit
> x86. If you only see 33% difference with "gcc -m32", I'm going to be
> very confused.
^ permalink raw reply
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
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
* Re: Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
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
In-Reply-To: <CALx6S351VFRZmEQphRQy6YtmZYPnOtTN7=XiNrJmhWJGv4HUBg@mail.gmail.com>
[-- 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
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: Theodore Ts'o @ 2016-12-16 20:43 UTC (permalink / raw)
To: George Spelvin
Cc: Jason, ak, davem, David.Laight, djb, ebiggers3, hannes,
jeanphilippe.aumasson, kernel-hardening, linux-crypto,
linux-kernel, luto, netdev, tom, torvalds, vegard.nossum
In-Reply-To: <20161216201739.24567.qmail@ns.sciencehorizons.net>
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. The point
> is you only have to raise the cost to equal that of a packet flood.
> (Just like in electronic warfare, the best you can possibly do is force
> the enemy to use broadband jamming.)
>
> Hash collision attacks just aren't that powerful. The original PoC
> was against an application that implemented a hard limit on hash chain
> length as a DoS defense, which the attack then exploited to turn it into
> a hard DoS.
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?
- Ted
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.
^ permalink raw reply
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
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
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: George Spelvin @ 2016-12-16 20:41 UTC (permalink / raw)
To: Jason, tom
Cc: ak, davem, David.Laight, djb, ebiggers3, hannes,
jeanphilippe.aumasson, kernel-hardening, linux-crypto,
linux-kernel, linux, luto, netdev, torvalds, tytso, vegard.nossum
In-Reply-To: <CALx6S351VFRZmEQphRQy6YtmZYPnOtTN7=XiNrJmhWJGv4HUBg@mail.gmail.com>
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 security
> advantages with halfsiphash?
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?
These are very odd results. On a 64-bit machine, SipHash should be the
same speed per round, and faster because it hashes more data per round.
(Unless you're hitting some unexpected cache/decode effect due to REX
prefixes.)
On a 32-bit machine (other than ARM, where your results might make sense,
or maybe if you're hashing large amounts of data), the difference should
be larger.
And yes, there is a *significant* security loss. SipHash is 128 bits
("don't worry about it"). hsiphash is 64 bits, which is known breakable
("worry about it"), so we have to do a careful analysis of the cost of
a successful attack.
As mentioned in the e-mails that just flew by, hsiphash is intended
*only* for 32-bit machines which bog down on full SipHash. On all 64-bit
machines, it will be implemented as an alias for SipHash and the security
concerns will Just Go Away.
The place where hsiphash is expected to make a big difference is 32-bit
x86. If you only see 33% difference with "gcc -m32", I'm going to be
very confused.
^ permalink raw reply
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: Jason A. Donenfeld @ 2016-12-16 20: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
In-Reply-To: <CAGiyFddB_HT3H2yhYQ5rprYZ487rJ4iCaH9uPJQD57hiPbn9ng@mail.gmail.com>
Hi JP,
On Fri, Dec 16, 2016 at 2:22 PM, Jean-Philippe Aumasson
<jeanphilippe.aumasson@gmail.com> 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 construction (BLAKE, SipHash, NORX), I'm
> confident it will be safe as it is.
I've implemented it in my siphash kernel branch:
https://git.zx2c4.com/linux-dev/log/?h=siphash
It's the commit that has "HalfSipHash" in the log message. As the
structure is nearly identical to SipHash, there wasn't a lot to
change, and so the same implementation strategy exists for each.
When you've finished your security review and feel good about it, some
test vectors using the same formula (key={0x03020100, 07060504},
input={0x0, 0x1, 0x2, 0x3...}, output=test_vectors) would be nice for
verification.
Jason
^ permalink raw reply
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: George Spelvin @ 2016-12-16 20:17 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
In-Reply-To: <CAHmME9pe39s5FWxfKNiRKkHnEO-9v2yLcEQc8rnMC89P6roTmA@mail.gmail.com>
>> 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
> like this arrangement.
This is a basic assumption I make in the security analysis below:
on most machines, it's 128-bit-key SipHash everywhere and we can
consider security solved.
Our analysis *only* has to consider 32-bit machines. My big concern
is home routers, with IoT appliances coming second. The routers have
severe hardware cost constraints (so limited CPU power), but see a lot
of traffic and need to process (NAT) it.
> 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. The point
is you only have to raise the cost to equal that of a packet flood.
(Just like in electronic warfare, the best you can possibly do is force
the enemy to use broadband jamming.)
Hash collision attacks just aren't that powerful. The original PoC
was against an application that implemented a hard limit on hash chain
length as a DoS defense, which the attack then exploited to turn it into
a hard DoS.
>> Let me consider your second example above, "secure against local users".
>> I should dig through your patchset and find the details, but what exactly
>> are the consequences of such an attack? Hasn't a local user already
>> got much better ways to DoS the system?
> For example, an unpriv'd user putting lots of entries in one hash
> bucket for a shared resource that's used by root, like filesystems or
> other lookup tables. If he can cause root to use more of root's cpu
> schedule budget than otherwise in a directed way, then that's a bad
> DoS.
This issue was recently discussed when we redesigned the dcache hash.
Even a successful attack doesn't slow things down all *that* much.
Before you overkill every hash table in the kernel, think about whether
it's a bigger problem than the dcache. (Hint: it's probably not.)
There's no point armor-plating the side door when the front door was
just upgraded from screen to wood.
>> These days, 32-bit CPUs are for embedded applications: network appliances,
>> TVs, etc. That means basically single-user. Even phones are 64 bit.
>> Is this really a threat that needs to be defended against?
> I interpret this to indicate all the more reason to alias hsiphash to
> siphash on 64-bit, and then the problem space collapses in a clear
> way.
Yes, exactly.
> Right. Hence the need for always using full siphash and not hsiphash
> for sequence numbers, per my earlier email to David.
>
>> I wish we could get away with 64-bit security, but given that the
>> modern internet involves attacks from NSA/Spetssvyaz/3PLA, I agree
>> it's just not enough.
>
> I take this comment to be relavent for the sequence number case.
Yes.
> For hashtables and hashtable flooding, is it still your opinion that
> we will benefit from hsiphash? Or is this final conclusion a rejection
> of hsiphash for that too? We're talking about two different use cases,
> and your email kind of interleaved both into your analysis, so I'm not
> certain so to precisely what your conclusion is for each use case. Can
> you clear up the ambiguity?
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.
If 2x hsiphash is faster than siphash, we could use a double-hashing
system like syncookies. One 32-bit hash with a permanent key, summed
with a k-bit counter and a (32-k)-bit hash, where the key is rotated
(and the counter incremented) periodically.
The requirement is that the increment rate of the counter hash doesn't
shorten the sequence number wraparound too much. The old code used an
8-bit counter and 24-bit hash, with the counter bumped every 5 minutes.
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.)
^ permalink raw reply
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
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
In-Reply-To: <CAHmME9pjoAsoct1sVDpFFuqaqutv9X7DGJ5OBQXRAS57KFimUA@mail.gmail.com>
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
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: Jason A. Donenfeld @ 2016-12-16 18:00 UTC (permalink / raw)
To: George Spelvin
Cc: Jean-Philippe Aumasson, Andi Kleen, David Miller, David Laight,
Daniel J . Bernstein, Eric Biggers, Hannes Frederic Sowa,
kernel-hardening, Linux Crypto Mailing List, LKML,
Andy Lutomirski, Netdev, Tom Herbert, Linus Torvalds,
Theodore Ts'o, Vegard Nossum
In-Reply-To: <20161216173624.21544.qmail@ns.sciencehorizons.net>
Hi George,
On Fri, Dec 16, 2016 at 6:36 PM, George Spelvin
<linux@sciencehorizons.net> 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 that's not implemented" and punt until someone find a need.
That's a good way to think about it. Okay, I'll do precisely that.
> 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
like this arrangement.
> Fortunately, the cost of brute-forcing hash functions can be fairly
> exactly quantified, thanks to bitcoin miners. It currently takes 2^70
> hashes to create one bitcoin block, worth 25 bitcoins ($19,500). Thus,
> 2^63 hashes cost $152.
>
> Now, there are two factors that must be considered:
> - That's a very very "wholesale" rate. That's assuming you're doing
> large numbers of these and can put in the up-front effort designing
> silicon ASICs to do the attack.
> - That's for a more difficult hash (double sha-256) than SipHash.
> That's a constant fator, but a pretty significant one. If the wholesale
> assumption holds, that might bring the cost down another 6 or 7 bits,
> to $1-2 per break.
>
> If you're not the NSA and limited to general-purpose silicon, let's
> assume a state of the art GPU (Radeon HD 7970; AMD GPUs seem do to better
> than nVidia). The bitcoin mining rate for those is about 700M/second,
> 29.4 bits. So 63 bits is 152502 GPU-days, divided by some factor
> to account for SipHash's high speed compared to two rounds of SHA-2.
> Call it 1000 GPU-days.
>
> It's very doable, but also very non-trivial. The question is, wouldn't
> it be cheaper and easier just to do a brute-force flooding DDoS?
>
> (This is why I wish the key size could be tweaked up to 80 bits.
> That would take all these numbers out of the reasonable range.)
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?
> Let me consider your second example above, "secure against local users".
> I should dig through your patchset and find the details, but what exactly
> are the consequences of such an attack? Hasn't a local user already
> got much better ways to DoS the system?
For example, an unpriv'd user putting lots of entries in one hash
bucket for a shared resource that's used by root, like filesystems or
other lookup tables. If he can cause root to use more of root's cpu
schedule budget than otherwise in a directed way, then that's a bad
DoS.
> The thing to remember is that we're worried only about the combination
> of a *new* Linux kernel (new build or under active maintenance) and a
> 32-bit host. You'd be hard-pressed to find a *single* machine fitting
> that description which is hosting multiple users or VMs and is not 64-bit.
>
> These days, 32-bit CPUs are for embedded applications: network appliances,
> TVs, etc. That means basically single-user. Even phones are 64 bit.
> Is this really a threat that needs to be defended against?
I interpret this to indicate all the more reason to alias hsiphash to
siphash on 64-bit, and then the problem space collapses in a clear
way.
> For your first case, network applications, the additional security
> is definitely attractive. Syncookies are only a DoS, but sequence
> numbers are a real security issue; they can let you inject data into a
> TCP connection.
> With sequence numbers, large amounts (32 bits) the hash output is
> directly observable.
Right. Hence the need for always using full siphash and not hsiphash
for sequence numbers, per my earlier email to David.
>
> I wish we could get away with 64-bit security, but given that the
> modern internet involves attacks from NSA/Spetssvyaz/3PLA, I agree
> it's just not enough.
I take this comment to be relavent for the sequence number case.
For hashtables and hashtable flooding, is it still your opinion that
we will benefit from hsiphash? Or is this final conclusion a rejection
of hsiphash for that too? We're talking about two different use cases,
and your email kind of interleaved both into your analysis, so I'm not
certain so to precisely what your conclusion is for each use case. Can
you clear up the ambiguity?
Jason
^ permalink raw reply
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: George Spelvin @ 2016-12-16 17:36 UTC (permalink / raw)
To: Jason, jeanphilippe.aumasson
Cc: ak, davem, David.Laight, djb, ebiggers3, hannes, kernel-hardening,
linux-crypto, linux-kernel, linux, luto, netdev, tom, torvalds,
tytso, vegard.nossum
In-Reply-To: <CAHmME9rxCYfwyF6EADWqpAEt+yqCPgCLUVH0FPdAy7r-oPnrRg@mail.gmail.com>
> 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 128-bit output option was added to SipHash after the initial publication;
this is just the equivalent in 32-bit.
> - Is this a reasonable choice?
Yes.
> - Are there reasons why hsiphash with 64-bit output would be
> reasonable? Or will we be fine sticking with 32-bit output only?
Personally, I'd put in a comment saying that "there's a 64-bit output
variant that's not implemented" and punt until someone find a need.
> With both hsiphash and siphash, the division of usage will probably become:
> - Use 64-bit output 128-bit key siphash for keyed RNG-like things,
> such as syncookies and sequence numbers
> - Use 64-bit output 128-bit key siphash for hashtables that must
> absolutely be secure to an extremely high bandwidth attacker, such as
> userspace directly DoSing a kernel hashtable
> - Use 32-bit output 64-bit key hsiphash for quick hashtable functions
> that still must be secure but do not require as large of a security
> margin.
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.
On a 32-bit machine, it's a much trickier case. I'd be tempted to
use the 32-bit code always, but it needs examination.
Fortunately, the cost of brute-forcing hash functions can be fairly
exactly quantified, thanks to bitcoin miners. It currently takes 2^70
hashes to create one bitcoin block, worth 25 bitcoins ($19,500). Thus,
2^63 hashes cost $152.
Now, there are two factors that must be considered:
- That's a very very "wholesale" rate. That's assuming you're doing
large numbers of these and can put in the up-front effort designing
silicon ASICs to do the attack.
- That's for a more difficult hash (double sha-256) than SipHash.
That's a constant fator, but a pretty significant one. If the wholesale
assumption holds, that might bring the cost down another 6 or 7 bits,
to $1-2 per break.
If you're not the NSA and limited to general-purpose silicon, let's
assume a state of the art GPU (Radeon HD 7970; AMD GPUs seem do to better
than nVidia). The bitcoin mining rate for those is about 700M/second,
29.4 bits. So 63 bits is 152502 GPU-days, divided by some factor
to account for SipHash's high speed compared to two rounds of SHA-2.
Call it 1000 GPU-days.
It's very doable, but also very non-trivial. The question is, wouldn't
it be cheaper and easier just to do a brute-force flooding DDoS?
(This is why I wish the key size could be tweaked up to 80 bits.
That would take all these numbers out of the reasonable range.)
Let me consider your second example above, "secure against local users".
I should dig through your patchset and find the details, but what exactly
are the consequences of such an attack? Hasn't a local user already
got much better ways to DoS the system?
The thing to remember is that we're worried only about the combination
of a *new* Linux kernel (new build or under active maintenance) and a
32-bit host. You'd be hard-pressed to find a *single* machine fitting
that description which is hosting multiple users or VMs and is not 64-bit.
These days, 32-bit CPUs are for embedded applications: network appliances,
TVs, etc. That means basically single-user. Even phones are 64 bit.
Is this really a threat that needs to be defended against?
For your first case, network applications, the additional security
is definitely attractive. Syncookies are only a DoS, but sequence
numbers are a real security issue; they can let you inject data into a
TCP connection.
Hash tables are much harder to attack. The information you get back from
timing probes is statistical, and thus testing a key is more expensive.
With sequence numbers, large amounts (32 bits) the hash output is
directly observable.
I wish we could get away with 64-bit security, but given that the
modern internet involves attacks from NSA/Spetssvyaz/3PLA, I agree
it's just not enough.
^ permalink raw reply
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: Jason A. Donenfeld @ 2016-12-16 17:09 UTC (permalink / raw)
To: David Laight
Cc: George Spelvin, ak@linux.intel.com, davem@davemloft.net,
ebiggers3@gmail.com, hannes@stressinduktion.org,
jeanphilippe.aumasson@gmail.com,
kernel-hardening@lists.openwall.com, linux-crypto@vger.kernel.org,
linux-kernel@vger.kernel.org, luto@amacapital.net,
netdev@vger.kernel.org, tom@herbertland.com,
torvalds@linux-foundation.org, tytso@mit.edu,
vegard.nossum@gmail.com, djb@cr.yp.to
In-Reply-To: <063D6719AE5E284EB5DD2968C1650D6DB0241238@AcuExch.aculab.com>
Hi David,
On Fri, Dec 16, 2016 at 6:06 PM, David Laight <David.Laight@aculab.com> 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 use the original siphash, since the 128-bit
key is rather important for these kinds of secrets. Additionally,
64-bit siphash is already faster than the md5_transform that it
replaces. So the alignment concerns (now, non-issues; problems have
been solved, I believe) still remain.
Jason
^ permalink raw reply
* RE: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: David Laight @ 2016-12-16 17:06 UTC (permalink / raw)
To: 'George Spelvin', ak@linux.intel.com, davem@davemloft.net,
ebiggers3@gmail.com, hannes@stressinduktion.org, Jason@zx2c4.com,
jeanphilippe.aumasson@gmail.com,
kernel-hardening@lists.openwall.com, linux-crypto@vger.kernel.org,
linux-kernel@vger.kernel.org, luto@amacapital.net,
netdev@vger.kernel.org, tom@herbertland.com,
torvalds@linux-foundation.org, "tytso@mit.edu" <tytso
Cc: djb@cr.yp.to
In-Reply-To: <20161215232840.22459.qmail@ns.sciencehorizons.net>
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 pushed to 80 bits, that would be nice,
> but honestly 64 bits is fine. This is DoS protection, and while it's
> possible to brute-force a 64 bit secret, there are more effective (DDoS)
> attacks possible for the same cost.
A 32bit hash would also remove all the issues about the alignment
of IP addresses (etc) on 64bit systems.
> (I'd suggest a name of "HalfSipHash" to convey the reduced security
> effectively.)
>
> > Regarding output size, are 64 bits sufficient?
>
> As a replacement for jhash, 32 bits are sufficient. It's for
> indexing an in-memory hash table on a 32-bit machine.
It is also worth remembering that if the intent is to generate
a hash table index (not a unique fingerprint) you will always
get collisions on the final value.
Randomness could still give overlong hash chains - which might
still need rehashing with a different key.
David
^ permalink raw reply
* Re: [PATCH v5 3/4] secure_seq: use SipHash in place of MD5
From: Jason A. Donenfeld @ 2016-12-16 15:57 UTC (permalink / raw)
To: David Laight
Cc: Netdev, kernel-hardening@lists.openwall.com, LKML,
linux-crypto@vger.kernel.org, Ted Tso, Hannes Frederic Sowa,
Linus Torvalds, Eric Biggers, Tom Herbert, George Spelvin,
Vegard Nossum, ak@linux.intel.com, davem@davemloft.net,
luto@amacapital.net
In-Reply-To: <063D6719AE5E284EB5DD2968C1650D6DB0240E66@AcuExch.aculab.com>
Hi David,
On Fri, Dec 16, 2016 at 10:59 AM, David Laight <David.Laight@aculab.com> wrote:
> You are still putting over-aligned data on stack.
> You only need to align it to the alignment of u64 (not the size of u64).
> If an on-stack item has a stronger alignment requirement than the stack
> the gcc has to generate two stack frames for the function.
Yesterday, folks were saying that sometimes 32-bit platforms need
8-byte alignment for certain 64-bit operations, so I shouldn't fall
back to 4-byte alignment there. But actually, looking at this more
closely, I can just make SIPHASH_ALIGNMENT == __alignof__(u64), which
will take care of all possible concerns, since gcc knows best which
platforms need what alignment. Thanks for making this clear to me with
"the alignment of u64 (not the size of u64)".
> Oh - and wait a bit longer between revisions.
Okay. We can be turtles.
Jason
^ permalink raw reply
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: Jason A. Donenfeld @ 2016-12-16 15:51 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
In-Reply-To: <CAGiyFddB_HT3H2yhYQ5rprYZ487rJ4iCaH9uPJQD57hiPbn9ng@mail.gmail.com>
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 implement one output length size. Right now I'm leaning toward
32-bit. Questions:
- Is this a reasonable choice?
- When hsiphash is desired due to its faster speed, are there any
circumstances in which producing a 64-bit output would actually be
useful? Namely, are there any hashtables that could benefit from a
64-bit functions?
- Are there reasons why hsiphash with 64-bit output would be
reasonable? Or will we be fine sticking with 32-bit output only?
With both hsiphash and siphash, the division of usage will probably become:
- Use 64-bit output 128-bit key siphash for keyed RNG-like things,
such as syncookies and sequence numbers
- Use 64-bit output 128-bit key siphash for hashtables that must
absolutely be secure to an extremely high bandwidth attacker, such as
userspace directly DoSing a kernel hashtable
- Use 32-bit output 64-bit key hsiphash for quick hashtable functions
that still must be secure but do not require as large of a security
margin
Sound good?
Jason
^ permalink raw reply
* RE: [PATCH v5 2/4] siphash: add Nu{32,64} helpers
From: George Spelvin @ 2016-12-16 15:44 UTC (permalink / raw)
To: ak, davem, David.Laight, ebiggers3, hannes, Jason,
kernel-hardening, linux-crypto, linux-kernel, linux, luto, netdev,
tom, torvalds, tytso, vegard.nossum
In-Reply-To: <063D6719AE5E284EB5DD2968C1650D6DB0240EFA@AcuExch.aculab.com>
Jason A. Donenfeld wrote:
> Isn't that equivalent to:
> v0 = key[0];
> v1 = key[1];
> v2 = key[0] ^ (0x736f6d6570736575ULL ^ 0x646f72616e646f6dULL);
> v3 = key[1] ^ (0x646f72616e646f6dULL ^ 0x7465646279746573ULL);
(Pre-XORing key[] with the first two constants which, if the constants
are random in the first place, can be a no-op.) Other than the typo
in the v2 line, yes. If they key is non-public, then you can xor an
arbitrary constant in to both halves to slightly speed up the startup.
(Nits: There's a typo in the v2 line, you don't need to parenthesize
associative operators like xor, and the "ull" suffix is redundant here.)
> Those constants also look like ASCII strings.
They are. The ASCII is "somepseudorandomlygeneratedbytes".
> What cryptographic analysis has been done on the values?
They're "nothing up my sleeve numbers".
They're arbitrary numbers, and almost any other values would do exactly
as well. The main properties are:
1) They're different (particulatly v0 != v2 and v1 != v3), and
2) Neither they, nor their xor, is rotationally symmetric like 0x55555555.
(Because SipHash is mostly rotationally symmetric, broken only by the
interruption of the carry chain at the msbit, it helps slightly
to break this up at the beginning.)
Those exact values only matter for portability. If you don't need anyone
else to be able to compute matching outputs, then you could use any other
convenient constants (like the MD5 round constants).
^ permalink raw reply
* Re: algif for compression?
From: abed mohammad kamaluddin @ 2016-12-16 14:11 UTC (permalink / raw)
To: Herbert Xu; +Cc: linux-crypto
In-Reply-To: <20161210081014.GA32746@gondor.apana.org.au>
>
> The compression interface is currently in a state of flux. We
> should make it settle down first before exporting it to user-space.
>
> For a start it would be good to actually switch IPsec/IPcomp over
> to the new compression interface.
Thanks Herbert. Are there timelines or ongoing efforts for moving
IPcomp/Ipsec to use acomp? Or any proposals that have been or need to
be taken up in this regard.
Thanks,
Abed
^ permalink raw reply
* Re: [PATCH] crypto: AF_ALG - fix memory management of aio with multiple iocbs
From: Stephan Müller @ 2016-12-16 13:58 UTC (permalink / raw)
To: Herbert Xu; +Cc: linux-crypto
In-Reply-To: <20161216123127.GA20406@gondor.apana.org.au>
Am Freitag, 16. Dezember 2016, 20:31:27 CET schrieb Herbert Xu:
Hi Herbert,
> >
> > You are right, this will introduce a memleak. But with the immediate
> > freeing of sreq->tsg in the current code, the AIO interface cannot
> > support multiple IOCBs.
> >
> > Thus, the entire memory handling in the AIO case seems broken.
>
> Right, but can we please fix it properly? For example, you could
> save the original tsg in a new field and free that when you are
> done.
Absolutely, I concur. I will work on that.
Ciao
Stephan
^ permalink raw reply
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: Jean-Philippe Aumasson @ 2016-12-16 13:22 UTC (permalink / raw)
To: Jason A. Donenfeld
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
In-Reply-To: <CAHmME9pjoAsoct1sVDpFFuqaqutv9X7DGJ5OBQXRAS57KFimUA@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 827 bytes --]
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 construction (BLAKE, SipHash, NORX), I'm
confident it will be safe as it is.
On Fri, Dec 16, 2016 at 1:44 PM 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.
>
> 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
>
[-- Attachment #2: Type: text/html, Size: 1706 bytes --]
^ permalink raw reply
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
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
In-Reply-To: <CAGiyFdd6_LVzUUfFcaqMyub1c2WPvWUzAQDCH+Aza-_t6mvmXg@mail.gmail.com>
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
* Re: [PATCH] crypto: AF_ALG - fix memory management of aio with multiple iocbs
From: Herbert Xu @ 2016-12-16 12:31 UTC (permalink / raw)
To: Stephan Müller; +Cc: linux-crypto
In-Reply-To: <2916745.RxhEJByb92@tauon.atsec.com>
On Fri, Dec 16, 2016 at 01:27:50PM +0100, Stephan Müller wrote:
> Am Freitag, 16. Dezember 2016, 19:54:36 CET schrieb Herbert Xu:
>
> Hi Herbert,
>
> > On Tue, Dec 13, 2016 at 09:42:45PM +0100, Stephan Müller wrote:
> > > + /*
> > > + * The async operation may have processed only a subset of
> > > + * the data that was initially received from the caller.
> > > + * Thus, we only can release the data that a cipher operation
> > > + * processed.
> > > + */
> > > + if (len < sg->length) {
> > > + /* ensure that empty SGLs are not referenced any more */
> > > + sreq->tsg = sg;
> >
> > Hmm if you change sreq->tsg how is the original tsg ever going to
> > get freed?
>
> You are right, this will introduce a memleak. But with the immediate freeing
> of sreq->tsg in the current code, the AIO interface cannot support multiple
> IOCBs.
>
> Thus, the entire memory handling in the AIO case seems broken.
Right, but can we please fix it properly? For example, you could
save the original tsg in a new field and free that when you are
done.
Cheers,
--
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
^ permalink raw reply
* Re: [PATCH] crypto: AF_ALG - fix memory management of aio with multiple iocbs
From: Stephan Müller @ 2016-12-16 12:27 UTC (permalink / raw)
To: Herbert Xu; +Cc: linux-crypto
In-Reply-To: <20161216115436.GA19917@gondor.apana.org.au>
Am Freitag, 16. Dezember 2016, 19:54:36 CET schrieb Herbert Xu:
Hi Herbert,
> On Tue, Dec 13, 2016 at 09:42:45PM +0100, Stephan Müller wrote:
> > + /*
> > + * The async operation may have processed only a subset of
> > + * the data that was initially received from the caller.
> > + * Thus, we only can release the data that a cipher operation
> > + * processed.
> > + */
> > + if (len < sg->length) {
> > + /* ensure that empty SGLs are not referenced any more */
> > + sreq->tsg = sg;
>
> Hmm if you change sreq->tsg how is the original tsg ever going to
> get freed?
You are right, this will introduce a memleak. But with the immediate freeing
of sreq->tsg in the current code, the AIO interface cannot support multiple
IOCBs.
Thus, the entire memory handling in the AIO case seems broken.
>
> > +
> > + /* advance the buffers to the unprocessed data */
> > + sg->length -= len;
> > + sg->offset += len;
> > + return;
> > + }
> > +
> > + len -= sg->length;
> > + put_page(page);
> > + }
> >
> > kfree(sreq->tsg);
>
> Thanks,
Ciao
Stephan
^ permalink raw reply
* Re: [PATCH v2] crypto: marvell - Copy IVDIG before launching partial DMA ahash requests
From: Herbert Xu @ 2016-12-16 12:07 UTC (permalink / raw)
To: Romain Perier
Cc: boris.brezillon, arno, linux-crypto, jason, andrew,
sebastian.hesselbarth, gregory.clement, thomas.petazzoni, nadavh,
oferh, radioconfusion, romain.perier, stable
In-Reply-To: <20161214141507.19105-1-romain.perier@free-electrons.com>
Romain Perier <romain.perier@free-electrons.com> wrote:
> Currently, inner IV/DIGEST data are only copied once into the hash
> engines and not set explicitly before launching a request that is not a
> first frag. This is an issue especially when multiple ahash reqs are
> computed in parallel or chained with cipher request, as the state of the
> request being computed is not updated into the hash engine. It leads to
> non-deterministic corrupted digest results.
>
> Fixes: commit 2786cee8e50b ("crypto: marvell - Move SRAM I/O operations to step functions")
> Signed-off-by: Romain Perier <romain.perier@free-electrons.com>
> Acked-by: Boris Brezillon <boris.brezillon@free-electrons.com>
> Cc: <stable@vger.kernel.org>
Patch applied. Thanks.
--
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
^ permalink raw reply
* Re: [PATCH] crypto: AF_ALG - fix memory management of aio with multiple iocbs
From: Herbert Xu @ 2016-12-16 11:54 UTC (permalink / raw)
To: Stephan Müller; +Cc: linux-crypto
In-Reply-To: <4632372.rm33NXUfDp@positron.chronox.de>
On Tue, Dec 13, 2016 at 09:42:45PM +0100, Stephan Müller wrote:
>
> + /*
> + * The async operation may have processed only a subset of
> + * the data that was initially received from the caller.
> + * Thus, we only can release the data that a cipher operation
> + * processed.
> + */
> + if (len < sg->length) {
> + /* ensure that empty SGLs are not referenced any more */
> + sreq->tsg = sg;
Hmm if you change sreq->tsg how is the original tsg ever going to
get freed?
> +
> + /* advance the buffers to the unprocessed data */
> + sg->length -= len;
> + sg->offset += len;
> + return;
> + }
> +
> + len -= sg->length;
> + put_page(page);
> + }
>
> kfree(sreq->tsg);
Thanks,
--
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
^ permalink raw reply
* (unknown),
From: системы администратор @ 2016-12-16 10:46 UTC (permalink / raw)
внимания;
аши сообщения превысил лимит памяти, который составляет 5 Гб, определенных администратором, который в настоящее время работает на 10.9GB, Вы не сможете отправить или получить новую почту, пока вы повторно не проверить ваш почтовый ящик почты. Чтобы восстановить работоспособность Вашего почтового ящика, отправьте следующую информацию ниже:
имя:
Имя пользователя:
пароль:
Подтверждение пароля:
Адрес электронной почты:
телефон:
Если вы не в состоянии перепроверить сообщения, ваш почтовый ящик будет отключен!
Приносим извинения за неудобства.
Проверочный код: EN: Ru...776774990..2016
Почты технической поддержки ©2016
спасибо
системы администратор
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox