From: "George Spelvin" <linux@sciencehorizons.net> To: Jason@zx2c4.com, jeanphilippe.aumasson@gmail.com Cc: ak@linux.intel.com, davem@davemloft.net, David.Laight@aculab.com, djb@cr.yp.to, ebiggers3@gmail.com, hannes@stressinduktion.org, kernel-hardening@lists.openwall.com, linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org, linux@sciencehorizons.net, luto@amacapital.net, netdev@vger.kernel.org, tom@herbertland.com, torvalds@linux-foundation.org, tytso@mit.edu, vegard.nossum@gmail.com Subject: Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF Date: 16 Dec 2016 12:36:24 -0500 [thread overview] Message-ID: <20161216173624.21544.qmail@ns.sciencehorizons.net> (raw) 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.
WARNING: multiple messages have this Message-ID (diff)
From: "George Spelvin" <linux@sciencehorizons.net> To: Jason@zx2c4.com, jeanphilippe.aumasson@gmail.com Cc: ak@linux.intel.com, davem@davemloft.net, David.Laight@aculab.com, djb@cr.yp.to, ebiggers3@gmail.com, hannes@stressinduktion.org, kernel-hardening@lists.openwall.com, linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org, linux@sciencehorizons.net, luto@amacapital.net, netdev@vger.kernel.org, tom@herbertland.com, torvalds@linux-foundation.org, tytso@mit.edu, vegard.nossum@gmail.com Subject: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF Date: 16 Dec 2016 12:36:24 -0500 [thread overview] Message-ID: <20161216173624.21544.qmail@ns.sciencehorizons.net> (raw) 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.
next prev parent reply other threads:[~2016-12-16 17:36 UTC|newest] Thread overview: 182+ messages / expand[flat|nested] mbox.gz Atom feed top 2016-12-15 20:29 [PATCH v5 0/4] The SipHash Patchset Jason A. Donenfeld 2016-12-15 20:29 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-15 20:30 ` [PATCH v5 1/4] siphash: add cryptographically secure PRF Jason A. Donenfeld 2016-12-15 20:30 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-15 22:42 ` George Spelvin 2016-12-15 22:42 ` [kernel-hardening] " George Spelvin 2016-12-15 23:00 ` Jean-Philippe Aumasson 2016-12-15 23:00 ` [kernel-hardening] " Jean-Philippe Aumasson 2016-12-15 23:28 ` George Spelvin 2016-12-15 23:28 ` [kernel-hardening] " George Spelvin 2016-12-16 17:06 ` David Laight 2016-12-16 17:06 ` [kernel-hardening] " David Laight 2016-12-16 17:06 ` David Laight 2016-12-16 17:09 ` Jason A. Donenfeld 2016-12-16 17:09 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 17:09 ` Jason A. Donenfeld 2016-12-16 3:46 ` George Spelvin 2016-12-16 3:46 ` [kernel-hardening] " George Spelvin 2016-12-16 8:08 ` Jean-Philippe Aumasson 2016-12-16 8:08 ` [kernel-hardening] " Jean-Philippe Aumasson 2016-12-16 12:39 ` Jason A. Donenfeld 2016-12-16 12:39 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 13:22 ` Jean-Philippe Aumasson 2016-12-16 13:22 ` [kernel-hardening] " Jean-Philippe Aumasson 2016-12-16 15:51 ` Jason A. Donenfeld 2016-12-16 15:51 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 17:36 ` George Spelvin [this message] 2016-12-16 17:36 ` George Spelvin 2016-12-16 18:00 ` Jason A. Donenfeld 2016-12-16 18:00 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 20:17 ` George Spelvin 2016-12-16 20:17 ` [kernel-hardening] " George Spelvin 2016-12-16 20:43 ` Theodore Ts'o 2016-12-16 20:43 ` [kernel-hardening] " Theodore Ts'o 2016-12-16 22:13 ` George Spelvin 2016-12-16 22:13 ` [kernel-hardening] " George Spelvin 2016-12-16 22:15 ` Andy Lutomirski 2016-12-16 22:15 ` [kernel-hardening] " Andy Lutomirski 2016-12-16 22:15 ` Andy Lutomirski 2016-12-16 22:18 ` Jason A. Donenfeld 2016-12-16 22:18 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 23:44 ` George Spelvin 2016-12-16 23:44 ` [kernel-hardening] " George Spelvin 2016-12-17 1:39 ` Jason A. Donenfeld 2016-12-17 1:39 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-17 2:15 ` George Spelvin 2016-12-17 2:15 ` [kernel-hardening] " George Spelvin 2016-12-17 15:41 ` Theodore Ts'o 2016-12-17 15:41 ` [kernel-hardening] " Theodore Ts'o 2016-12-17 16:14 ` Jeffrey Walton 2016-12-17 16:14 ` [kernel-hardening] " Jeffrey Walton 2016-12-19 17:21 ` Jason A. Donenfeld 2016-12-17 12:42 ` George Spelvin 2016-12-17 12:42 ` [kernel-hardening] " George Spelvin 2016-12-16 20:39 ` Jason A. Donenfeld 2016-12-16 20:39 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 19:47 ` Tom Herbert 2016-12-16 19:47 ` [kernel-hardening] " Tom Herbert 2016-12-16 20:41 ` George Spelvin 2016-12-16 20:41 ` [kernel-hardening] " George Spelvin 2016-12-16 20:57 ` Tom Herbert 2016-12-16 20:57 ` [kernel-hardening] " Tom Herbert 2016-12-16 20:44 ` Daniel Micay 2016-12-16 20:44 ` [kernel-hardening] " Daniel Micay 2016-12-16 21:09 ` Jason A. Donenfeld 2016-12-17 15:21 ` George Spelvin 2016-12-17 15:21 ` [kernel-hardening] " George Spelvin 2016-12-19 14:14 ` David Laight 2016-12-19 14:14 ` [kernel-hardening] " David Laight 2016-12-19 14:14 ` David Laight 2016-12-19 18:10 ` George Spelvin 2016-12-19 18:10 ` [kernel-hardening] " George Spelvin 2016-12-19 20:18 ` Jean-Philippe Aumasson 2016-12-19 20:18 ` [kernel-hardening] " Jean-Philippe Aumasson 2016-12-16 2:14 ` kbuild test robot 2016-12-16 2:14 ` [kernel-hardening] " kbuild test robot 2016-12-17 14:55 ` Jeffrey Walton 2016-12-17 14:55 ` [kernel-hardening] " Jeffrey Walton 2016-12-19 17:08 ` Jason A. Donenfeld 2016-12-19 17:08 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-19 17:19 ` Jean-Philippe Aumasson 2016-12-19 17:19 ` [kernel-hardening] " Jean-Philippe Aumasson 2016-12-15 20:30 ` [PATCH v5 2/4] siphash: add Nu{32,64} helpers Jason A. Donenfeld 2016-12-15 20:30 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 10:39 ` David Laight 2016-12-16 10:39 ` [kernel-hardening] " David Laight 2016-12-16 10:39 ` David Laight 2016-12-16 15:44 ` George Spelvin 2016-12-16 15:44 ` [kernel-hardening] " George Spelvin 2016-12-15 20:30 ` [PATCH v5 3/4] secure_seq: use SipHash in place of MD5 Jason A. Donenfeld 2016-12-15 20:30 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 9:59 ` David Laight 2016-12-16 9:59 ` [kernel-hardening] " David Laight 2016-12-16 9:59 ` David Laight 2016-12-16 15:57 ` Jason A. Donenfeld 2016-12-16 15:57 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 15:57 ` Jason A. Donenfeld 2016-12-15 20:30 ` [PATCH v5 4/4] random: " Jason A. Donenfeld 2016-12-15 20:30 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 3:03 ` [PATCH v6 0/5] The SipHash Patchset Jason A. Donenfeld 2016-12-16 3:03 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 3:03 ` [PATCH v6 1/5] siphash: add cryptographically secure PRF Jason A. Donenfeld 2016-12-16 3:03 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 3:03 ` [PATCH v6 2/5] secure_seq: use SipHash in place of MD5 Jason A. Donenfeld 2016-12-16 3:03 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 3:03 ` [PATCH v6 3/5] random: " Jason A. Donenfeld 2016-12-16 3:03 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 21:31 ` Andy Lutomirski 2016-12-16 21:31 ` [kernel-hardening] " Andy Lutomirski 2016-12-16 21:31 ` Andy Lutomirski 2016-12-16 3:03 ` [PATCH v6 4/5] md5: remove from lib and only live in crypto Jason A. Donenfeld 2016-12-16 3:03 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-16 3:03 ` [PATCH v6 5/5] syncookies: use SipHash in place of SHA1 Jason A. Donenfeld 2016-12-16 3:03 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-21 23:02 ` [PATCH v7 0/6] The SipHash Patchset Jason A. Donenfeld 2016-12-21 23:02 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-21 23:02 ` [PATCH v7 1/6] siphash: add cryptographically secure PRF Jason A. Donenfeld 2016-12-21 23:02 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-22 1:40 ` Stephen Hemminger 2016-12-22 1:40 ` [kernel-hardening] " Stephen Hemminger 2016-12-21 23:02 ` [PATCH v7 2/6] secure_seq: use SipHash in place of MD5 Jason A. Donenfeld 2016-12-21 23:02 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-21 23:02 ` [PATCH v7 3/6] random: " Jason A. Donenfeld 2016-12-21 23:02 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-21 23:13 ` Jason A. Donenfeld 2016-12-21 23:13 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-21 23:42 ` Andy Lutomirski 2016-12-21 23:42 ` [kernel-hardening] " Andy Lutomirski 2016-12-21 23:42 ` Andy Lutomirski 2016-12-22 2:07 ` Hannes Frederic Sowa 2016-12-22 2:07 ` [kernel-hardening] " Hannes Frederic Sowa 2016-12-22 2:07 ` Hannes Frederic Sowa 2016-12-22 2:09 ` Andy Lutomirski 2016-12-22 2:09 ` [kernel-hardening] " Andy Lutomirski 2016-12-22 2:09 ` Andy Lutomirski 2016-12-22 2:49 ` Jason A. Donenfeld 2016-12-22 2:49 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-22 2:49 ` Jason A. Donenfeld 2016-12-22 3:12 ` Jason A. Donenfeld 2016-12-22 3:12 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-22 3:12 ` Jason A. Donenfeld 2016-12-22 5:41 ` Theodore Ts'o 2016-12-22 5:41 ` [kernel-hardening] " Theodore Ts'o 2016-12-22 6:03 ` Jason A. Donenfeld 2016-12-22 15:58 ` Theodore Ts'o 2016-12-22 15:58 ` [kernel-hardening] " Theodore Ts'o 2016-12-22 16:16 ` Jason A. Donenfeld 2016-12-22 16:16 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-22 16:30 ` Theodore Ts'o 2016-12-22 16:36 ` Jason A. Donenfeld 2016-12-22 12:47 ` Hannes Frederic Sowa 2016-12-22 12:47 ` [kernel-hardening] " Hannes Frederic Sowa 2016-12-22 13:10 ` Jason A. Donenfeld 2016-12-22 15:05 ` Hannes Frederic Sowa 2016-12-22 15:12 ` Jason A. Donenfeld 2016-12-22 15:29 ` Jason A. Donenfeld 2016-12-22 15:33 ` Hannes Frederic Sowa 2016-12-22 15:33 ` [kernel-hardening] " Hannes Frederic Sowa 2016-12-22 15:41 ` Jason A. Donenfeld 2016-12-22 15:51 ` Hannes Frederic Sowa 2016-12-22 15:51 ` [kernel-hardening] " Hannes Frederic Sowa 2016-12-22 15:53 ` Jason A. Donenfeld 2016-12-22 15:54 ` Theodore Ts'o 2016-12-22 15:54 ` [kernel-hardening] " Theodore Ts'o 2016-12-22 18:08 ` Hannes Frederic Sowa 2016-12-22 18:13 ` Jason A. Donenfeld 2016-12-22 18:13 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-22 19:50 ` Theodore Ts'o 2016-12-22 2:31 ` Jason A. Donenfeld 2016-12-22 2:31 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-22 2:31 ` Jason A. Donenfeld 2016-12-21 23:02 ` [PATCH v7 4/6] md5: remove from lib and only live in crypto Jason A. Donenfeld 2016-12-21 23:02 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-21 23:02 ` [PATCH v7 5/6] syncookies: use SipHash in place of SHA1 Jason A. Donenfeld 2016-12-21 23:02 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-21 23:02 ` [PATCH v7 6/6] siphash: implement HalfSipHash1-3 for hash tables Jason A. Donenfeld 2016-12-21 23:02 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-22 0:46 ` Andi Kleen 2016-12-22 0:46 ` [kernel-hardening] " Andi Kleen 2016-12-16 20:43 [PATCH v5 1/4] siphash: add cryptographically secure PRF Jason A. Donenfeld 2016-12-16 20:49 Jason A. Donenfeld 2016-12-16 21:25 ` George Spelvin
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20161216173624.21544.qmail@ns.sciencehorizons.net \ --to=linux@sciencehorizons.net \ --cc=David.Laight@aculab.com \ --cc=Jason@zx2c4.com \ --cc=ak@linux.intel.com \ --cc=davem@davemloft.net \ --cc=djb@cr.yp.to \ --cc=ebiggers3@gmail.com \ --cc=hannes@stressinduktion.org \ --cc=jeanphilippe.aumasson@gmail.com \ --cc=kernel-hardening@lists.openwall.com \ --cc=linux-crypto@vger.kernel.org \ --cc=linux-kernel@vger.kernel.org \ --cc=luto@amacapital.net \ --cc=netdev@vger.kernel.org \ --cc=tom@herbertland.com \ --cc=torvalds@linux-foundation.org \ --cc=tytso@mit.edu \ --cc=vegard.nossum@gmail.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.