Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1541797

RE: [PATCH 1/3] siphash: add cryptographically secure hashtable function

Show all headers | View raw

From: Jason A. Donenfeld
> Sent: 14 December 2016 00:17
> SipHash is a 64-bit keyed hash function that is actually a
> cryptographically secure PRF, like HMAC. Except SipHash is super fast,
> and is meant to be used as a hashtable keyed lookup function.
> 
> SipHash isn't just some new trendy hash function. It's been around for a
> while, and there really isn't anything that comes remotely close to
> being useful in the way SipHash is. With that said, why do we need this?
> 
> There are a variety of attacks known as "hashtable poisoning" in which an
> attacker forms some data such that the hash of that data will be the
> same, and then preceeds to fill up all entries of a hashbucket. This is
> a realistic and well-known denial-of-service vector.
> 
> Linux developers already seem to be aware that this is an issue, and
> various places that use hash tables in, say, a network context, use a
> non-cryptographically secure function (usually jhash) and then try to
> twiddle with the key on a time basis (or in many cases just do nothing
> and hope that nobody notices). While this is an admirable attempt at
> solving the problem, it doesn't actually fix it. SipHash fixes it.
> 
> (It fixes it in such a sound way that you could even build a stream
> cipher out of SipHash that would resist the modern cryptanalysis.)
> 
> There are a modicum of places in the kernel that are vulnerable to
> hashtable poisoning attacks, either via userspace vectors or network
> vectors, and there's not a reliable mechanism inside the kernel at the
> moment to fix it. The first step toward fixing these issues is actually
> getting a secure primitive into the kernel for developers to use. Then
> we can, bit by bit, port things over to it as deemed appropriate.
> 
> Dozens of languages are already using this internally for their hash
> tables. Some of the BSDs already use this in their kernels. SipHash is
> a widely known high-speed solution to a widely known problem, and it's
> time we catch-up.
...
> +u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN])
...
> +	u64 k0 = get_unaligned_le64(key);
> +	u64 k1 = get_unaligned_le64(key + sizeof(u64));
...
> +		m = get_unaligned_le64(data);

All these unaligned accesses are going to get expensive on architectures
like sparc64.

	David

Back to linux.kernel | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

[PATCH 1/3] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 01:30 +0100
  [PATCH 4/3] random: use siphash24 instead of md5 for get_random_int/long "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 04:20 +0100
    Re: [PATCH 4/3] random: use siphash24 instead of md5 for  get_random_int/long Theodore Ts'o <tytso@mit.edu> - 2016-12-14 17:40 +0100
      Re: [kernel-hardening] Re: [PATCH 4/3] random: use siphash24 instead  of md5 for get_random_int/long "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 19:00 +0100
      Re: [kernel-hardening] Re: [PATCH 4/3] random: use siphash24 instead  of md5 for get_random_int/long "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-14 20:20 +0100
        Re: [kernel-hardening] Re: [PATCH 4/3] random: use siphash24 instead  of md5 for get_random_int/long "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 02:30 +0100
  RE: [PATCH 1/3] siphash: add cryptographically secure hashtable  function David Laight <David.Laight@ACULAB.COM> - 2016-12-14 11:00 +0100

csiph-web