* 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: [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 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: 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 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: 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 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: 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: 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: 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: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: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: 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: 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: 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: [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: Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
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
* Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: Jason A. Donenfeld @ 2016-12-16 21:09 UTC (permalink / raw)
To: Daniel Micay
Cc: kernel-hardening, 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: <1481921067.1054.6.camel@gmail.com>
Hi Daniel,
On Fri, Dec 16, 2016 at 9:44 PM, Daniel Micay <danielmicay@gmail.com> 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 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.
Maybe not a bad idea.
SipHash2-4 for MD5 replacement, as we've done so far. This is when we
actually want things to be secure (and fast).
And then HalfSipHash1-3 for certain jhash replacements. This is for
when we're talking only about DoS or sort of just joking about
security, and want things to be very competitive with jhash. (Of
course for 64-bit we'd use SipHash1-3 instead of HalfSipHash for the
speedup.)
I need to think on this a bit more, but preliminarily, I guess this
would be maybe okay...
George, JP - what do you think?
Jason
^ permalink raw reply
* Re: Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
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
In-Reply-To: <CAHmME9pz=syTiLXUsbXFyGdbGK6pxbnU+TVLDkbYiTa-9+sckQ@mail.gmail.com>
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
* Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: George Spelvin @ 2016-12-16 21:25 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: <CAHmME9q0LaxQ3uinzWyD1mDCpyeLw_2TEAN33T6dDrTKCuHs7g@mail.gmail.com>
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 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.
Oh, geez, I didn't realize you didn't understand this code.
Full details at
https://en.wikipedia.org/wiki/TCP_sequence_prediction_attack
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 boot time.
But then someone observed that I can start a connection to host X,
see the sequence number it gives back to me, and thereby learn the
seauence number it's using on its connections to host Y.
And I can use that to inject forged data into an X-to-Y connection,
without ever seeing a single byte of the traffic! (If I *can* observe
the traffic, of course, none of this makes the slightest difference.)
So the random base was made a keyed hash of the endpoint identifiers.
(Practically only the hosts matter, but generally the ports are thrown
in for good measure.) That way, the ISN that host X sends to me
tells me nothing about the ISN it's using to talk to host Y. Now the
only way to inject forged data into the X-to-Y connection is to
send 2^32 bytes, which is a little less practical.
^ permalink raw reply
* Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: Jason A. Donenfeld @ 2016-12-16 21:31 UTC (permalink / raw)
To: kernel-hardening
Cc: George Spelvin, 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,
Theodore Ts'o, Vegard Nossum
In-Reply-To: <20161216212528.26003.qmail@ns.sciencehorizons.net>
Hi George,
On Fri, Dec 16, 2016 at 10:25 PM, George Spelvin
<linux@sciencehorizons.net> 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 boot time.
>
> But then someone observed that I can start a connection to host X,
> see the sequence number it gives back to me, and thereby learn the
> seauence number it's using on its connections to host Y.
>
> And I can use that to inject forged data into an X-to-Y connection,
> without ever seeing a single byte of the traffic! (If I *can* observe
> the traffic, of course, none of this makes the slightest difference.)
>
> So the random base was made a keyed hash of the endpoint identifiers.
> (Practically only the hosts matter, but generally the ports are thrown
> in for good measure.) That way, the ISN that host X sends to me
> tells me nothing about the ISN it's using to talk to host Y. Now the
> only way to inject forged data into the X-to-Y connection is to
> send 2^32 bytes, which is a little less practical.
Oh, okay, that is exactly what I thought was going on. I just thought
you were implying that jiffies could be moved inside the hash, which
then confused my understanding of how things should be. In any case,
thanks for the explanation.
Jason
^ permalink raw reply
* Re: [PATCH v6 3/5] random: use SipHash in place of MD5
From: Andy Lutomirski @ 2016-12-16 21:31 UTC (permalink / raw)
To: Jason A. Donenfeld
Cc: Netdev, kernel-hardening@lists.openwall.com, LKML, linux-crypto,
David Laight, Ted Tso, Hannes Frederic Sowa, Linus Torvalds,
Eric Biggers, Tom Herbert, George Spelvin, Vegard Nossum,
Andi Kleen, David S. Miller, Jean-Philippe Aumasson
In-Reply-To: <20161216030328.11602-4-Jason@zx2c4.com>
On Thu, Dec 15, 2016 at 7:03 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> -static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash)
> - __aligned(sizeof(unsigned long));
> +static DEFINE_PER_CPU(u64, get_random_int_chaining);
>
[...]
> unsigned long get_random_long(void)
> {
> - __u32 *hash;
> unsigned long ret;
> + u64 *chaining;
>
> if (arch_get_random_long(&ret))
> return ret;
>
> - hash = get_cpu_var(get_random_int_hash);
> -
> - hash[0] += current->pid + jiffies + random_get_entropy();
> - md5_transform(hash, random_int_secret);
> - ret = *(unsigned long *)hash;
> - put_cpu_var(get_random_int_hash);
> -
> + chaining = &get_cpu_var(get_random_int_chaining);
> + ret = *chaining = siphash_3u64(*chaining, jiffies, random_get_entropy() +
> + current->pid, random_int_secret);
> + put_cpu_var(get_random_int_chaining);
> return ret;
> }
I think it would be nice to try to strenghen the PRNG construction.
FWIW, I'm not an expert in PRNGs, and there's fairly extensive
literature, but I can at least try. Here are some properties I'd
like:
1. A one-time leak of memory contents doesn't ruin security until
reboot. This is especially value across suspend and/or hibernation.
2. An attack with a low work factor (2^64?) shouldn't break the scheme
until reboot.
This is effectively doing:
output = H(prev_output, weak "entropy", per-boot secret);
One unfortunately downside is that, if used in a context where an
attacker can see a single output, the attacker learns the chaining
value. If the attacker can guess the entropy, then, with 2^64 work,
they learn the secret, and they can predict future outputs.
I would advocate adding two types of improvements. First, re-seed it
every now and then (every 128 calls?) by just replacing both the
chaining value and the percpu secret with fresh CSPRNG output.
Second, change the mode so that an attacker doesn't learn so much
internal state. For example:
output = H(old_chain, entropy, secret);
new_chain = old_chain + entropy + output;
This increases the effort needed to brute-force the internal state
from 2^64 to 2^128 (barring any weaknesses in the scheme).
Also, can we not call this get_random_int()? get_random_int() sounds
too much like get_random_bytes(), and the latter is intended to be a
real CSPRNG. Can we call it get_weak_random_int() or similar?
--Andy
^ permalink raw reply
* Re: [PATCH v6 3/5] random: use SipHash in place of MD5
From: Jason A. Donenfeld @ 2016-12-16 21:45 UTC (permalink / raw)
To: Andy Lutomirski
Cc: Netdev, kernel-hardening@lists.openwall.com, LKML,
Linux Crypto Mailing List, David Laight, Ted Tso,
Hannes Frederic Sowa, Linus Torvalds, Eric Biggers, Tom Herbert,
George Spelvin, Vegard Nossum, Andi Kleen, David S. Miller,
Jean-Philippe Aumasson
Hi Andy,
On Fri, Dec 16, 2016 at 10:31 PM, Andy Lutomirski <luto@amacapital.net> wrote:
> I think it would be nice to try to strenghen the PRNG construction.
> FWIW, I'm not an expert in PRNGs, and there's fairly extensive
> literature, but I can at least try.
In an effort to keep this patchset as initially as uncontroversial as
possible, I kept the same same construction as before and just swapped
out slow MD5 for fast Siphash. Additionally, the function
documentation says that it isn't cryptographically secure. But in the
end I certainly agree with you; we should most definitely improve
things, and seeing the eyeballs now on this series, I think we now
might have a mandate to do so.
> 1. A one-time leak of memory contents doesn't ruin security until
> reboot. This is especially value across suspend and/or hibernation.
Ted and I were discussing this in another thread, and it sounds like
he wants the same thing. I'll add re-generation of the secret every
once in a while. Perhaps time-based makes more sense than
counter-based for rekeying frequency?
> 2. An attack with a low work factor (2^64?) shouldn't break the scheme
> until reboot.
It won't. The key is 128-bits.
> This is effectively doing:
>
> output = H(prev_output, weak "entropy", per-boot secret);
>
> One unfortunately downside is that, if used in a context where an
> attacker can see a single output, the attacker learns the chaining
> value. If the attacker can guess the entropy, then, with 2^64 work,
> they learn the secret, and they can predict future outputs.
No, the secret is 128-bits, which isn't feasibly guessable. The secret
also isn't part of the hash, but rather is the generator of the hash
function. A keyed hash (a PRF) is a bit of a different construction
than just hashing a secret value into a hash function.
> Second, change the mode so that an attacker doesn't learn so much
> internal state. For example:
>
> output = H(old_chain, entropy, secret);
> new_chain = old_chain + entropy + output;
Happy to make this change, with making the chaining value additive
rather than a replacement.
However, I'm not sure adding entropy to the new_chain makes a
different. That entropy is basically just the cycle count plus the
jiffies count. If an attacker can already guess them, then adding them
again to the chaining value doesn't really add much.
Jason
^ permalink raw reply
* Re: [PATCH v6 3/5] random: use SipHash in place of MD5
From: Jason A. Donenfeld @ 2016-12-16 22:12 UTC (permalink / raw)
To: Andy Lutomirski, Ted Tso
Cc: Netdev, kernel-hardening@lists.openwall.com, LKML,
Linux Crypto Mailing List, David Laight, Hannes Frederic Sowa,
Linus Torvalds, Eric Biggers, Tom Herbert, George Spelvin,
Vegard Nossum, Andi Kleen, David S. Miller,
Jean-Philippe Aumasson
In-Reply-To: <CAHmME9rbKi3O1SS89LRMEUeMdKyrdutXAfjb9QmW3KNoCuE-wg@mail.gmail.com>
Hi Andy, Ted,
I've made the requested changes. Keys now rotate and are per-CPU
based. The chaining value is now additive instead of replacing.
DavidL suggested I lower the velocity of `git-send-email` triggers, so
if you'd like to take a look at this before I post v7, you can follow
along at my git tree here:
https://git.zx2c4.com/linux-dev/log/?h=siphash
Choose the commit entitled "random: use SipHash in place of MD5"
Thanks,
Jason
^ permalink raw reply
* Re: [PATCH v6 3/5] random: use SipHash in place of MD5
From: Andy Lutomirski @ 2016-12-16 22:13 UTC (permalink / raw)
To: Jason A. Donenfeld
Cc: Netdev, kernel-hardening@lists.openwall.com, LKML,
Linux Crypto Mailing List, David Laight, Ted Tso,
Hannes Frederic Sowa, Linus Torvalds, Eric Biggers, Tom Herbert,
George Spelvin, Vegard Nossum, Andi Kleen, David S. Miller,
Jean-Philippe Aumasson
In-Reply-To: <CAHmME9rbKi3O1SS89LRMEUeMdKyrdutXAfjb9QmW3KNoCuE-wg@mail.gmail.com>
On Fri, Dec 16, 2016 at 1:45 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> Hi Andy,
>
> On Fri, Dec 16, 2016 at 10:31 PM, Andy Lutomirski <luto@amacapital.net> wrote:
>> I think it would be nice to try to strenghen the PRNG construction.
>> FWIW, I'm not an expert in PRNGs, and there's fairly extensive
>> literature, but I can at least try.
>
> In an effort to keep this patchset as initially as uncontroversial as
> possible, I kept the same same construction as before and just swapped
> out slow MD5 for fast Siphash. Additionally, the function
> documentation says that it isn't cryptographically secure. But in the
> end I certainly agree with you; we should most definitely improve
> things, and seeing the eyeballs now on this series, I think we now
> might have a mandate to do so.
>
>> 1. A one-time leak of memory contents doesn't ruin security until
>> reboot. This is especially value across suspend and/or hibernation.
>
> Ted and I were discussing this in another thread, and it sounds like
> he wants the same thing. I'll add re-generation of the secret every
> once in a while. Perhaps time-based makes more sense than
> counter-based for rekeying frequency?
Counter may be faster -- you don't need to read a timer. Lots of CPUs
are surprisingly slow at timing. OTOH jiffies are fast.
>
>> 2. An attack with a low work factor (2^64?) shouldn't break the scheme
>> until reboot.
>
> It won't. The key is 128-bits.
Whoops, I thought the key was 64-bit...
>
>> This is effectively doing:
>>
>> output = H(prev_output, weak "entropy", per-boot secret);
>>
>> One unfortunately downside is that, if used in a context where an
>> attacker can see a single output, the attacker learns the chaining
>> value. If the attacker can guess the entropy, then, with 2^64 work,
>> they learn the secret, and they can predict future outputs.
>
> No, the secret is 128-bits, which isn't feasibly guessable. The secret
> also isn't part of the hash, but rather is the generator of the hash
> function. A keyed hash (a PRF) is a bit of a different construction
> than just hashing a secret value into a hash function.
I was thinking in the random oracle model, in which case the whole
function is just a PRF that takes a few input parameters, one of which
is a key.
>
>> Second, change the mode so that an attacker doesn't learn so much
>> internal state. For example:
>>
>> output = H(old_chain, entropy, secret);
>> new_chain = old_chain + entropy + output;
>
> Happy to make this change, with making the chaining value additive
> rather than a replacement.
>
> However, I'm not sure adding entropy to the new_chain makes a
> different. That entropy is basically just the cycle count plus the
> jiffies count. If an attacker can already guess them, then adding them
> again to the chaining value doesn't really add much.
Agreed. A simpler contruction would be:
chaining++;
output = H(chaining, secret);
And this looks a whole lot like Ted's ChaCha20 construction.
The benefit of my construction is that (in the random oracle model,
assuming my intuition is right), if an attacker misses ~128 samples
and entropy has at least one bit of independent min-entropy per
sample, then the attacker needs ~2^128 work to brute-force the
chaining value even fi the attacker knew both the original chaining
value and the secret.
--Andy
^ 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