9 ms·

SipHash and HalfSipHash Added to Linux Kernel

76 points by zx2c4 10y ago

nerdponx 10y ago
I have never come anywhere near developing a kernel in my life. What's the purpose of including this in the kernel itself? Why couldn't developers just use some kind of "libsiphash" instead?
- kspaans 10y ago
  Generally speaking, the kernel community doesn't like to add external dependencies. And then including it in the kernel tree gives some advantages: architecture-specific speed hacks can be applied, kernel-specific utilities can be used in the implementation.
- foota 10y ago
  Maybe it's used in the kernel? Edit: although I think the developers could include it as a statically linked library at compile time even if it's used in the kernel?
  - deleted 10y ago
    [deleted]
- zx2c4 10y ago
  This implementation is optimized for kernel usage and follows kernel idioms. If you're curious, here's the source: Header: https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.git/tree/include/linux/siphash.h https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.... Source: https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.git/tree/lib/siphash.c https://git.kernel.org/cgit/linux/kernel/git/davem/net-next....
- jstimpfle 10y ago
  My guess (not a kernel developer): Technically I think it could be built as a dynamically loadable kernel module and shipped separately from the kernel image under /lib/modules. This does not make sense if the functionality is always needed, in which case it should be statically compiled in. In any case there is no benefit of developping separately considering that the module must call functionality from the kernel (at least for the entropy part) so the code is tightly bound to the kernel (and to specific versions of the kernel at that). The functionality could also live in userland, and the kernel could start a process, which links the libsiphash shared library. The process could then communicate with the kernel by other means, reducing dependencies. And of course that would be too slow.
- ajdlinux 10y ago
  I haven't been actively watching SipHash but I do subscribe to the linux-hardening list and have seen a little bit of the discussion - my understanding is there are a bunch of potential applications in the kernel in areas that already use other hash functions, such as TCP sequence numbers, which are security sensitive, where SipHash could be faster and/or more secure. Hash functions aren't included in the kernel for exposure to userspace, they're included for internal kernel use. edit: see e.g. this email from Linus: http://www.openwall.com/lists/kernel-hardening/2016/12/13/5 http://www.openwall.com/lists/kernel-hardening/2016/12/13/5
- mfukar 10y ago
  The primary users of siphash, as seen in lkml, are ipv[4|6] syncookies (/net/ipv4/syncookies.c), and TCP sequence numbers (/net/core/secure_seq.c).
  - zx2c4 10y ago
    Hopefully not "primary" for long. These are just the first uses I saw to immediately convert to siphash with the least amount of controversy to actually get siphash in the kernel. Now that these have landed, other developers can gradually start using it in more and more places. Who knows what the "primary" use will be after 4.11.
- alfalfasprout 10y ago
  When in the kernel you don't really have access to most of the standard library so there's no real guarantee that "libsiphash" wouldn't need symbols defined elsewhere. The kernel does allow for loadable modules but the point of some of these hashes is to replace calls to some md5 and sha equivalents inside the kernel itself. As a result, the symbols would need to be defined at compile time (so these functions need to be compiled in).
- geofft 10y ago
  This isn't intended for userspace developers to use - they should use a libsiphash. This is intended for use where the kernel needs cryptographically strong hash tables and such, which happens about as often in the kernel as in any userspace program of comparable complexity and functionality.
mrigor 10y ago
https://en.wikipedia.org/wiki/SipHash https://en.wikipedia.org/wiki/SipHash
- zer0t3ch 10y ago
  As someone who's not at all versed in cryptography, (yet) anyone want to put this in more laymen terms? Maybe compare it to an existing cryptographical-method I might understand or at least know of?
  - semi-extrinsic 10y ago
    ELI5 (distilled from wikipedia page linked by GP, forgive me any errors): Web servers use hash tables for storing per-request data. If an attacker knows the hash function (say, SHA1), they can create a few hundred requests that yield the same hash, giving hundreds of hash collisions and creating a Denial-of-Service attack with the same effect as millions of ordinary requests. It's a form of DoS amplification. A keyed hash function fixes this by keeping part of the hash algorithm (the key) secret. You can turn e.g. SHA1 into a keyed hash function by e.g. HMAC, but that's computationally expensive. SipHash, being a "natively keyed" hash function, is much faster.
    - daveguy 10y ago
      Except if the hash is SHA1 (or any other non-compromised cryptographic hash) they would have a very difficult time creating requests that yield the same hash, that aren't the same request, right?
      - semi-extrinsic 10y ago
        I'm not sure, but I think if you're just interested in creating N collisions, as opposed to finding something that collides with given plaintext X, that the birthday paradox gives you a huge performance increase and makes it feasible. Also, I think many still use MD5 in applications where SipHash is intended (at least the Linux kernel does).
  - 10y ago
rurban 10y ago
Counter argument: http://perl11.org/blog/seed.html http://perl11.org/blog/seed.html Now even the kernel devs are drinking the coolaid, verbatim copying wrong claims from the SipHash authors.
- CJefferson 10y ago
  Saying you can read the hash seed from memory sounds like a "wrong side of the airtight hatchway" problem. If I can already read bytes from the running executable, I can just smash it to bits. If I can run processes on the machine at all, I don't need to slow it down with hash collisions, I can just fork bomb. Can you usefully attack without having that kind of access?
  - rurban 10y ago
    No. The problem is the commit message, not yet the implementation. What will follow is what followed at all the other cases: ruby, python, php, rust, ... They will replace SHA1 with siphash (already done in this branch), their open-addressing with chaining and primes with power of 2. So they will loose all the previous performance and security by the false security and performance claim of siphash. siphash essentially says: we are DoS secure and we are fast. Both is provable wrong.
    - zx2c4 10y ago
      Sorry but you still haven't substantiated your argument with any such "proof". It looks like you also made a "prediction" about what's going to be decided by people who certainly aren't you in the future. Got a cryptographically secure PRF that's faster than Siphash for small inputs and has undergone extensive cryptanalysis? If so, I'm all ears. If not, get lost, troll. There's a real use case for a secure PRF fast for small inputs. That's why this code has been added.
      - rurban 10y ago
        You are the troll when you dont see the obvious proofs. 1. DOS proof: a hash function can never lead to DoS proofness. Every hash function can be trivially brute forced to find enough collisions for such an attack. When you need to protect against such a worst case you don't make your hash function slower and get limited seed hiding, you rather check for such an attack and mitigate it directly, at the collision resolution. 2. Slowness: see my smhasher page. The slowest of all hash functions which is used in hash tables. I don't see a usecase for a slow PRF in net. All other PRF's are faster. I also don't see more security, only less. SHA1 replaced by SipHash surely makes it faster, but not safer.

76 points by zx2c4 10y ago

I have never come anywhere near developing a kernel in my life. What's the purpose of including this in the kernel itself? Why couldn't developers just use some kind of "libsiphash" instead?

kspaans 10y ago
Generally speaking, the kernel community doesn't like to add external dependencies. And then including it in the kernel tree gives some advantages: architecture-specific speed hacks can be applied, kernel-specific utilities can be used in the implementation.
foota 10y ago
Maybe it's used in the kernel? Edit: although I think the developers could include it as a statically linked library at compile time even if it's used in the kernel?
- deleted 10y ago
  [deleted]
zx2c4 10y ago
This implementation is optimized for kernel usage and follows kernel idioms. If you're curious, here's the source: Header: https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.git/tree/include/linux/siphash.h https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.... Source: https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.git/tree/lib/siphash.c https://git.kernel.org/cgit/linux/kernel/git/davem/net-next....
jstimpfle 10y ago
My guess (not a kernel developer): Technically I think it could be built as a dynamically loadable kernel module and shipped separately from the kernel image under /lib/modules. This does not make sense if the functionality is always needed, in which case it should be statically compiled in. In any case there is no benefit of developping separately considering that the module must call functionality from the kernel (at least for the entropy part) so the code is tightly bound to the kernel (and to specific versions of the kernel at that). The functionality could also live in userland, and the kernel could start a process, which links the libsiphash shared library. The process could then communicate with the kernel by other means, reducing dependencies. And of course that would be too slow.
ajdlinux 10y ago
I haven't been actively watching SipHash but I do subscribe to the linux-hardening list and have seen a little bit of the discussion - my understanding is there are a bunch of potential applications in the kernel in areas that already use other hash functions, such as TCP sequence numbers, which are security sensitive, where SipHash could be faster and/or more secure. Hash functions aren't included in the kernel for exposure to userspace, they're included for internal kernel use. edit: see e.g. this email from Linus: http://www.openwall.com/lists/kernel-hardening/2016/12/13/5 http://www.openwall.com/lists/kernel-hardening/2016/12/13/5
mfukar 10y ago
The primary users of siphash, as seen in lkml, are ipv[4|6] syncookies (/net/ipv4/syncookies.c), and TCP sequence numbers (/net/core/secure_seq.c).
- zx2c4 10y ago
  Hopefully not "primary" for long. These are just the first uses I saw to immediately convert to siphash with the least amount of controversy to actually get siphash in the kernel. Now that these have landed, other developers can gradually start using it in more and more places. Who knows what the "primary" use will be after 4.11.
alfalfasprout 10y ago
When in the kernel you don't really have access to most of the standard library so there's no real guarantee that "libsiphash" wouldn't need symbols defined elsewhere. The kernel does allow for loadable modules but the point of some of these hashes is to replace calls to some md5 and sha equivalents inside the kernel itself. As a result, the symbols would need to be defined at compile time (so these functions need to be compiled in).
geofft 10y ago
This isn't intended for userspace developers to use - they should use a libsiphash. This is intended for use where the kernel needs cryptographically strong hash tables and such, which happens about as often in the kernel as in any userspace program of comparable complexity and functionality.

mrigor 10y ago

https://en.wikipedia.org/wiki/SipHash https://en.wikipedia.org/wiki/SipHash

zer0t3ch 10y ago
As someone who's not at all versed in cryptography, (yet) anyone want to put this in more laymen terms? Maybe compare it to an existing cryptographical-method I might understand or at least know of?
- semi-extrinsic 10y ago
  ELI5 (distilled from wikipedia page linked by GP, forgive me any errors): Web servers use hash tables for storing per-request data. If an attacker knows the hash function (say, SHA1), they can create a few hundred requests that yield the same hash, giving hundreds of hash collisions and creating a Denial-of-Service attack with the same effect as millions of ordinary requests. It's a form of DoS amplification. A keyed hash function fixes this by keeping part of the hash algorithm (the key) secret. You can turn e.g. SHA1 into a keyed hash function by e.g. HMAC, but that's computationally expensive. SipHash, being a "natively keyed" hash function, is much faster.
  - daveguy 10y ago
    Except if the hash is SHA1 (or any other non-compromised cryptographic hash) they would have a very difficult time creating requests that yield the same hash, that aren't the same request, right?
    - semi-extrinsic 10y ago
      I'm not sure, but I think if you're just interested in creating N collisions, as opposed to finding something that collides with given plaintext X, that the birthday paradox gives you a huge performance increase and makes it feasible. Also, I think many still use MD5 in applications where SipHash is intended (at least the Linux kernel does).
- 10y ago

rurban 10y ago

Counter argument: http://perl11.org/blog/seed.html http://perl11.org/blog/seed.html Now even the kernel devs are drinking the coolaid, verbatim copying wrong claims from the SipHash authors.

CJefferson 10y ago
Saying you can read the hash seed from memory sounds like a "wrong side of the airtight hatchway" problem. If I can already read bytes from the running executable, I can just smash it to bits. If I can run processes on the machine at all, I don't need to slow it down with hash collisions, I can just fork bomb. Can you usefully attack without having that kind of access?
- rurban 10y ago
  No. The problem is the commit message, not yet the implementation. What will follow is what followed at all the other cases: ruby, python, php, rust, ... They will replace SHA1 with siphash (already done in this branch), their open-addressing with chaining and primes with power of 2. So they will loose all the previous performance and security by the false security and performance claim of siphash. siphash essentially says: we are DoS secure and we are fast. Both is provable wrong.
  - zx2c4 10y ago
    Sorry but you still haven't substantiated your argument with any such "proof". It looks like you also made a "prediction" about what's going to be decided by people who certainly aren't you in the future. Got a cryptographically secure PRF that's faster than Siphash for small inputs and has undergone extensive cryptanalysis? If so, I'm all ears. If not, get lost, troll. There's a real use case for a secure PRF fast for small inputs. That's why this code has been added.
    - rurban 10y ago
      You are the troll when you dont see the obvious proofs. 1. DOS proof: a hash function can never lead to DoS proofness. Every hash function can be trivially brute forced to find enough collisions for such an attack. When you need to protect against such a worst case you don't make your hash function slower and get limited seed hiding, you rather check for such an attack and mitigate it directly, at the collision resolution. 2. Slowness: see my smhasher page. The slowest of all hash functions which is used in hash tables. I don't see a usecase for a slow PRF in net. All other PRF's are faster. I also don't see more security, only less. SHA1 replaced by SipHash surely makes it faster, but not safer.