Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[Jason A. Donenfeld]

On Thu, Jan 12, 2017 at 4:04 PM, Herbert Xu  wrote:
>> typedef struct {
>>u64 v[2];
>> } siphash_key_t;
>
> If it's just an 128-bit value then we have u128 in crypto/b128ops.h
> that could be generalised for this.

Nope, it's actually two 64-bit values. Yes, the user fills it in as
one blob to get_random_bytes, but it's used internally by the
algorithm as two distinct variables (which conveniently fit into
64-bit registers).

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[Jason A. Donenfeld]

On Thu, Jan 12, 2017 at 4:04 PM, Herbert Xu  wrote:
>> typedef struct {
>>u64 v[2];
>> } siphash_key_t;
>
> If it's just an 128-bit value then we have u128 in crypto/b128ops.h
> that could be generalised for this.

Nope, it's actually two 64-bit values. Yes, the user fills it in as
one blob to get_random_bytes, but it's used internally by the
algorithm as two distinct variables (which conveniently fit into
64-bit registers).

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[Herbert Xu]

Eric Biggers  wrote:
> Hi Jason, just a few comments:
> 
> On Fri, Jan 06, 2017 at 09:10:52PM +0100, Jason A. Donenfeld wrote:
>> +#define SIPHASH_ALIGNMENT __alignof__(u64)
>> +typedef u64 siphash_key_t[2];
> 
> I was confused by all the functions passing siphash_key_t "by value" until I 
> saw
> that it's actually typedefed to u64[2].  Have you considered making it a 
> struct
> instead, something like this?
> 
> typedef struct {
>u64 v[2];
> } siphash_key_t;

If it's just an 128-bit value then we have u128 in crypto/b128ops.h
that could be generalised for this.

Cheers,
-- 
Email: Herbert Xu 
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[Herbert Xu]

Eric Biggers  wrote:
> Hi Jason, just a few comments:
> 
> On Fri, Jan 06, 2017 at 09:10:52PM +0100, Jason A. Donenfeld wrote:
>> +#define SIPHASH_ALIGNMENT __alignof__(u64)
>> +typedef u64 siphash_key_t[2];
> 
> I was confused by all the functions passing siphash_key_t "by value" until I 
> saw
> that it's actually typedefed to u64[2].  Have you considered making it a 
> struct
> instead, something like this?
> 
> typedef struct {
>u64 v[2];
> } siphash_key_t;

If it's just an 128-bit value then we have u128 in crypto/b128ops.h
that could be generalised for this.

Cheers,
-- 
Email: Herbert Xu 
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[Jason A. Donenfeld]

Hi Eric,

Thanks for the review. I wish we had gotten to this much earlier
before the merge, when there were quite a few revisions and
refinements, but better late than never, and I'm quite pleased to have
your feedback for making this patchset perfect. Comments are inline
below.

On Sat, Jan 7, 2017 at 5:04 AM, Eric Biggers  wrote:
> I was confused by all the functions passing siphash_key_t "by value" until I 
> saw
> that it's actually typedefed to u64[2].  Have you considered making it a 
> struct
> instead, something like this?
>
> typedef struct {
> u64 v[2];
> } siphash_key_t;

That's a good idea. I'll make this change.

>
>> +static inline u64 ___siphash_aligned(const __le64 *data, size_t len, const 
>> siphash_key_t key)
>> +{
>> + if (__builtin_constant_p(len) && len == 4)
>> + return siphash_1u32(le32_to_cpu(data[0]), key);
>
> Small bug here: data[0] is not valid if len is 4.  This can be fixed by 
> casting
> to a le32 pointer:
>
> return siphash_1u32(le32_to_cpup((const __le32 *)data), key);

Since data[0] is then passed to a function that takes a u32, gcc
actually does the right thing here and doesn't generate an out of
bounds read. But of course this isn't good behavior to rely on. I'll
fix this up. Thanks for catching it.

>
>> +static int __init siphash_test_init(void)
>> +{
>> + u8 in[64] __aligned(SIPHASH_ALIGNMENT);
>> + u8 in_unaligned[65];
>
> It seems that in_unaligned+1 is meant to be misaligned, but that's not
> guaranteed because in_unaligned has no alignment restriction, so it could
> theoretically be misaligned in a way that makes in_unaligned+1 aligned.  So it
> should be 'in_unaligned[65] __aligned(SIPHASH_ALIGNMENT)'.

Thanks, will do.

>
> There are also a lot of checkpatch warnings produced by this patch.  It looks
> like many of them can be ignored, but there may be some that should be
> addressed.

Will have a look and address for v2.

Thanks again for your review!

Regards,
Jason

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[Jason A. Donenfeld]

Hi Eric,

Thanks for the review. I wish we had gotten to this much earlier
before the merge, when there were quite a few revisions and
refinements, but better late than never, and I'm quite pleased to have
your feedback for making this patchset perfect. Comments are inline
below.

On Sat, Jan 7, 2017 at 5:04 AM, Eric Biggers  wrote:
> I was confused by all the functions passing siphash_key_t "by value" until I 
> saw
> that it's actually typedefed to u64[2].  Have you considered making it a 
> struct
> instead, something like this?
>
> typedef struct {
> u64 v[2];
> } siphash_key_t;

That's a good idea. I'll make this change.

>
>> +static inline u64 ___siphash_aligned(const __le64 *data, size_t len, const 
>> siphash_key_t key)
>> +{
>> + if (__builtin_constant_p(len) && len == 4)
>> + return siphash_1u32(le32_to_cpu(data[0]), key);
>
> Small bug here: data[0] is not valid if len is 4.  This can be fixed by 
> casting
> to a le32 pointer:
>
> return siphash_1u32(le32_to_cpup((const __le32 *)data), key);

Since data[0] is then passed to a function that takes a u32, gcc
actually does the right thing here and doesn't generate an out of
bounds read. But of course this isn't good behavior to rely on. I'll
fix this up. Thanks for catching it.

>
>> +static int __init siphash_test_init(void)
>> +{
>> + u8 in[64] __aligned(SIPHASH_ALIGNMENT);
>> + u8 in_unaligned[65];
>
> It seems that in_unaligned+1 is meant to be misaligned, but that's not
> guaranteed because in_unaligned has no alignment restriction, so it could
> theoretically be misaligned in a way that makes in_unaligned+1 aligned.  So it
> should be 'in_unaligned[65] __aligned(SIPHASH_ALIGNMENT)'.

Thanks, will do.

>
> There are also a lot of checkpatch warnings produced by this patch.  It looks
> like many of them can be ignored, but there may be some that should be
> addressed.

Will have a look and address for v2.

Thanks again for your review!

Regards,
Jason

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[Eric Biggers]

Hi Jason, just a few comments:

On Fri, Jan 06, 2017 at 09:10:52PM +0100, Jason A. Donenfeld wrote:
> +#define SIPHASH_ALIGNMENT __alignof__(u64)
> +typedef u64 siphash_key_t[2];

I was confused by all the functions passing siphash_key_t "by value" until I saw
that it's actually typedefed to u64[2].  Have you considered making it a struct
instead, something like this?

typedef struct {
u64 v[2];
} siphash_key_t;

Then it would be strongly typed and thus harder to misuse, and all the functions
would take 'const siphash_key_t *' instead of 'const siphash_key_t' which would
make it clear that the key is passed by pointer not by value.

> +static inline u64 ___siphash_aligned(const __le64 *data, size_t len, const 
> siphash_key_t key)
> +{
> + if (__builtin_constant_p(len) && len == 4)
> + return siphash_1u32(le32_to_cpu(data[0]), key);

Small bug here: data[0] is not valid if len is 4.  This can be fixed by casting
to a le32 pointer:

return siphash_1u32(le32_to_cpup((const __le32 *)data), key);

> +static int __init siphash_test_init(void)
> +{
> + u8 in[64] __aligned(SIPHASH_ALIGNMENT);
> + u8 in_unaligned[65];

It seems that in_unaligned+1 is meant to be misaligned, but that's not
guaranteed because in_unaligned has no alignment restriction, so it could
theoretically be misaligned in a way that makes in_unaligned+1 aligned.  So it
should be 'in_unaligned[65] __aligned(SIPHASH_ALIGNMENT)'.

There are also a lot of checkpatch warnings produced by this patch.  It looks
like many of them can be ignored, but there may be some that should be
addressed.

- Eric

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[Eric Biggers]

Hi Jason, just a few comments:

On Fri, Jan 06, 2017 at 09:10:52PM +0100, Jason A. Donenfeld wrote:
> +#define SIPHASH_ALIGNMENT __alignof__(u64)
> +typedef u64 siphash_key_t[2];

I was confused by all the functions passing siphash_key_t "by value" until I saw
that it's actually typedefed to u64[2].  Have you considered making it a struct
instead, something like this?

typedef struct {
u64 v[2];
} siphash_key_t;

Then it would be strongly typed and thus harder to misuse, and all the functions
would take 'const siphash_key_t *' instead of 'const siphash_key_t' which would
make it clear that the key is passed by pointer not by value.

> +static inline u64 ___siphash_aligned(const __le64 *data, size_t len, const 
> siphash_key_t key)
> +{
> + if (__builtin_constant_p(len) && len == 4)
> + return siphash_1u32(le32_to_cpu(data[0]), key);

Small bug here: data[0] is not valid if len is 4.  This can be fixed by casting
to a le32 pointer:

return siphash_1u32(le32_to_cpup((const __le32 *)data), key);

> +static int __init siphash_test_init(void)
> +{
> + u8 in[64] __aligned(SIPHASH_ALIGNMENT);
> + u8 in_unaligned[65];

It seems that in_unaligned+1 is meant to be misaligned, but that's not
guaranteed because in_unaligned has no alignment restriction, so it could
theoretically be misaligned in a way that makes in_unaligned+1 aligned.  So it
should be 'in_unaligned[65] __aligned(SIPHASH_ALIGNMENT)'.

There are also a lot of checkpatch warnings produced by this patch.  It looks
like many of them can be ignored, but there may be some that should be
addressed.

- Eric

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[David Miller]

Please do not quote an entire large patch, just to make a small comment or
annotation.  This makes it so that every reader of your posting has to
scroll down a lot just to see a small amount of new content.

Simply edit down the quoted material to the actually required context, and
then add the content you wish.

I do realize that a lot of email clients make this difficult, but that is
no excuse for not maintaining this basic level of consideration for the
other people on this mailing list.

Thanks.

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[David Miller]

Please do not quote an entire large patch, just to make a small comment or
annotation.  This makes it so that every reader of your posting has to
scroll down a lot just to see a small amount of new content.

Simply edit down the quoted material to the actually required context, and
then add the content you wish.

I do realize that a lot of email clients make this difficult, but that is
no excuse for not maintaining this basic level of consideration for the
other people on this mailing list.

Thanks.

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[Jean-Philippe Aumasson]

>
>
> On Fri, Jan 6, 2017 at 9:11 PM Jason A. Donenfeld  wrote:
>
> 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, or as a
> general PRF for short input use cases, such as sequence numbers or RNG
> chaining.
>
> For the first usage:
>
> 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. Currently
> hashtables use jhash, which is fast but not secure, and some kind of
> rotating key scheme (or none at all, which isn't good). SipHash is meant
> as a replacement for jhash in these cases.
>
> 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.
>
> While SipHash is extremely fast for a cryptographically secure function,
> it is likely a bit slower than the insecure jhash, and so replacements
> will be evaluated on a case-by-case basis based on whether or not the
> difference in speed is negligible and whether or not the current jhash usage
> poses a real security risk.
>
> For the second usage:
>
> A few places in the kernel are using MD5 or SHA1 for creating secure
> sequence numbers, syn cookies, port numbers, or fast random numbers.
> SipHash is a faster and more fitting, and more secure replacement for MD5
> in those situations. Replacing MD5 and SHA1 with SipHash for these uses is
> obvious and straight-forward, and so is submitted along with this patch
> series. There shouldn't be much of a debate over its efficacy.
>
> Dozens of languages are already using this internally for their hash
> tables and PRFs. Some of the BSDs already use this in their kernels.
> SipHash is a widely known high-speed solution to a widely known set of
> problems, and it's time we catch-up.
>
> Signed-off-by: Jason A. Donenfeld 
> Cc: Jean-Philippe Aumasson 
> Cc: Linus Torvalds 
> Cc: Eric Biggers 
> Cc: David Laight 
> Cc: Eric Dumazet 
> ---
> Documentation/siphash.txt | 79 
> MAINTAINERS | 7 ++
> include/linux/siphash.h | 79 
> lib/Kconfig.debug | 6 +-
> lib/Makefile | 5 +-
> lib/siphash.c | 232 ++
> lib/test_siphash.c | 119 
> 7 files changed, 522 insertions(+), 5 deletions(-)
> create mode 100644 Documentation/siphash.txt
> create mode 100644 include/linux/siphash.h
> create mode 100644 lib/siphash.c
> create mode 100644 lib/test_siphash.c
>
> diff --git a/Documentation/siphash.txt b/Documentation/siphash.txt
> new file mode 100644
> index ..39ff7f0438e7
> --- /dev/null
> +++ b/Documentation/siphash.txt
> @@ -0,0 +1,79 @@
> + SipHash - a short input PRF
> +---
> +Written by Jason A. Donenfeld 
> +
> +SipHash is a cryptographically secure PRF -- a keyed hash function -- that
> +performs very well for short inputs, hence the name. It was designed by
> +cryptographers Daniel J. Bernstein and Jean-Philippe Aumasson. It is intended
> +as a replacement for some uses of: `jhash`, `md5_transform`, `sha_transform`,
> +and so forth.
> +
> +SipHash takes a secret key filled with randomly generated numbers and either
> +an input buffer or several input integers. It spits out an integer that is
> +indistinguishable from random. You may then use that integer as part of 
> secure
> +sequence numbers, secure cookies, or mask it off for use in a hash table.
> +
> +1. Generating a key
> +
> +Keys should always be generated from a cryptographically secure source of
> +random numbers, either using get_random_bytes or get_random_once:
> +
> +siphash_key_t key;
> +get_random_bytes(key, sizeof(key));
> +
> +If you're not deriving your key from here, you're doing it wrong.
> +
> +2. Using the functions
> +
> +There are two variants of the function, one that takes a list of integers, 
> and
> +one that takes a buffer:
> +
> +u64 siphash(const void *data, size_t len, siphash_key_t key);
> +
> +And:
> +
> +u64 siphash_1u64(u64, siphash_key_t key);
> +u64 siphash_2u64(u64, u64, siphash_key_t key);
> +u64 siphash_3u64(u64, u64, u64, siphash_key_t key);
> +u64 siphash_4u64(u64, u64, u64, u64, siphash_key_t key);
> +u64 siphash_1u32(u32, siphash_key_t key);
> +u64 siphash_2u32(u32, u32, 

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[Jean-Philippe Aumasson]

>
>
> On Fri, Jan 6, 2017 at 9:11 PM Jason A. Donenfeld  wrote:
>
> 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, or as a
> general PRF for short input use cases, such as sequence numbers or RNG
> chaining.
>
> For the first usage:
>
> 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. Currently
> hashtables use jhash, which is fast but not secure, and some kind of
> rotating key scheme (or none at all, which isn't good). SipHash is meant
> as a replacement for jhash in these cases.
>
> 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.
>
> While SipHash is extremely fast for a cryptographically secure function,
> it is likely a bit slower than the insecure jhash, and so replacements
> will be evaluated on a case-by-case basis based on whether or not the
> difference in speed is negligible and whether or not the current jhash usage
> poses a real security risk.
>
> For the second usage:
>
> A few places in the kernel are using MD5 or SHA1 for creating secure
> sequence numbers, syn cookies, port numbers, or fast random numbers.
> SipHash is a faster and more fitting, and more secure replacement for MD5
> in those situations. Replacing MD5 and SHA1 with SipHash for these uses is
> obvious and straight-forward, and so is submitted along with this patch
> series. There shouldn't be much of a debate over its efficacy.
>
> Dozens of languages are already using this internally for their hash
> tables and PRFs. Some of the BSDs already use this in their kernels.
> SipHash is a widely known high-speed solution to a widely known set of
> problems, and it's time we catch-up.
>
> Signed-off-by: Jason A. Donenfeld 
> Cc: Jean-Philippe Aumasson 
> Cc: Linus Torvalds 
> Cc: Eric Biggers 
> Cc: David Laight 
> Cc: Eric Dumazet 
> ---
> Documentation/siphash.txt | 79 
> MAINTAINERS | 7 ++
> include/linux/siphash.h | 79 
> lib/Kconfig.debug | 6 +-
> lib/Makefile | 5 +-
> lib/siphash.c | 232 ++
> lib/test_siphash.c | 119 
> 7 files changed, 522 insertions(+), 5 deletions(-)
> create mode 100644 Documentation/siphash.txt
> create mode 100644 include/linux/siphash.h
> create mode 100644 lib/siphash.c
> create mode 100644 lib/test_siphash.c
>
> diff --git a/Documentation/siphash.txt b/Documentation/siphash.txt
> new file mode 100644
> index ..39ff7f0438e7
> --- /dev/null
> +++ b/Documentation/siphash.txt
> @@ -0,0 +1,79 @@
> + SipHash - a short input PRF
> +---
> +Written by Jason A. Donenfeld 
> +
> +SipHash is a cryptographically secure PRF -- a keyed hash function -- that
> +performs very well for short inputs, hence the name. It was designed by
> +cryptographers Daniel J. Bernstein and Jean-Philippe Aumasson. It is intended
> +as a replacement for some uses of: `jhash`, `md5_transform`, `sha_transform`,
> +and so forth.
> +
> +SipHash takes a secret key filled with randomly generated numbers and either
> +an input buffer or several input integers. It spits out an integer that is
> +indistinguishable from random. You may then use that integer as part of 
> secure
> +sequence numbers, secure cookies, or mask it off for use in a hash table.
> +
> +1. Generating a key
> +
> +Keys should always be generated from a cryptographically secure source of
> +random numbers, either using get_random_bytes or get_random_once:
> +
> +siphash_key_t key;
> +get_random_bytes(key, sizeof(key));
> +
> +If you're not deriving your key from here, you're doing it wrong.
> +
> +2. Using the functions
> +
> +There are two variants of the function, one that takes a list of integers, 
> and
> +one that takes a buffer:
> +
> +u64 siphash(const void *data, size_t len, siphash_key_t key);
> +
> +And:
> +
> +u64 siphash_1u64(u64, siphash_key_t key);
> +u64 siphash_2u64(u64, u64, siphash_key_t key);
> +u64 siphash_3u64(u64, u64, u64, siphash_key_t key);
> +u64 siphash_4u64(u64, u64, u64, u64, siphash_key_t key);
> +u64 siphash_1u32(u32, siphash_key_t key);
> +u64 siphash_2u32(u32, u32, siphash_key_t key);
> +u64 siphash_3u32(u32, u32, u32, siphash_key_t key);
> +u64 siphash_4u32(u32, u32, u32, u32, siphash_key_t key);
> +
> +If you pass the generic siphash function 

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[Jason A. Donenfeld]

Will resubmit. Sorry. I had this in earlier series and dropped it in
this one. Apologies. Give me 30 minutes and you'll have a beautiful
and conformant patch series.

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[Jason A. Donenfeld]

Will resubmit. Sorry. I had this in earlier series and dropped it in
this one. Apologies. Give me 30 minutes and you'll have a beautiful
and conformant patch series.

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[David Miller]

Proper patch series submissions require a header "[PATCH 0/N] ..." posting
explaining at a high level, what the series is doing, how it is doing it,
and why it is doing it that way.

Re: [PATCH net-next 1/4] siphash: add cryptographically secure PRF

[David Miller]

Proper patch series submissions require a header "[PATCH 0/N] ..." posting
explaining at a high level, what the series is doing, how it is doing it,
and why it is doing it that way.