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

Groups > linux.kernel > #1543077 > unrolled thread

Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function

Back to article view | Back to linux.kernel

Contents

  Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-15 22:30 +0100
    Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-15 22:50 +0100
      Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-16 00:50 +0100
      Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function "Jason A. Donenfeld" <Jason@zx2c4.com> - 2016-12-16 01:00 +0100
        Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable  function Hannes Frederic Sowa <hannes@stressinduktion.org> - 2016-12-16 01:10 +0100

#1543077 — Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function

On Thu, Dec 15, 2016 at 10:17 PM, Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
> And I was exactly questioning this.
>
> static unsigned int inet6_hash_frag(__be32 id, const struct in6_addr *saddr,
>                                     const struct in6_addr *daddr)
> {
>         net_get_random_once(&ip6_frags.rnd, sizeof(ip6_frags.rnd));
>         return jhash_3words(ipv6_addr_hash(saddr), ipv6_addr_hash(daddr),
>                             (__force u32)id, ip6_frags.rnd);
> }

For this example, the replacement is the function entitled siphash_4u32:

 static unsigned int inet6_hash_frag(__be32 id, const struct in6_addr *saddr,
                                     const struct in6_addr *daddr)
 {
         net_get_random_once(&ip6_frags.rnd, sizeof(ip6_frags.rnd));
         return siphash_4u32(ipv6_addr_hash(saddr), ipv6_addr_hash(daddr),
                 (__force u32)id, 0, ip6_frags.rnd);
 }

And then you make ip6_frags.rnd be of type siphash_key_t. Then
everything is taken care of and works beautifully. Please see v5 of
this patchset.

> I would be interested if the compiler can actually constant-fold the
> address of the stack allocation with an simple if () or some
> __builtin_constant_p fiddeling, so we don't have this constant review
> overhead to which function we pass which data. This would also make
> this whole discussion moot.

I'll play with it to see if the compiler is capable of doing that.
Does anybody know off hand if it is or if there are other examples of
the compiler doing that?

In any case, for all current replacement of jhash_1word, jhash_2words,
jhash_3words, there's the siphash_2u32 or siphash_4u32 functions. This
covers the majority of cases.

For replacements of md5_transform, either the data is small and can
fit in siphash_Nu{32,64}, or it can be put into a struct explicitly
aligned on the stack.

For the remaining use of jhash_nwords, either siphash() can be used or
siphash_unaligned() can be used if the source is of unknown alignment.
Both functions have their alignment requirements (or lack thereof)
documented in a docbook comment.

I'll look into the constant folding to see if it actually works. If it
does, I'll use it. If not, I believe the current solution works.

How's that sound?

Jason

[toc] | [next] | [standalone]

#1543081 — Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function

On 15.12.2016 22:25, Jason A. Donenfeld wrote:
> On Thu, Dec 15, 2016 at 10:17 PM, Hannes Frederic Sowa
> <hannes@stressinduktion.org> wrote:
>> And I was exactly questioning this.
>>
>> static unsigned int inet6_hash_frag(__be32 id, const struct in6_addr *saddr,
>>                                     const struct in6_addr *daddr)
>> {
>>         net_get_random_once(&ip6_frags.rnd, sizeof(ip6_frags.rnd));
>>         return jhash_3words(ipv6_addr_hash(saddr), ipv6_addr_hash(daddr),
>>                             (__force u32)id, ip6_frags.rnd);
>> }
> 
> For this example, the replacement is the function entitled siphash_4u32:
> 
>  static unsigned int inet6_hash_frag(__be32 id, const struct in6_addr *saddr,
>                                      const struct in6_addr *daddr)
>  {
>          net_get_random_once(&ip6_frags.rnd, sizeof(ip6_frags.rnd));
>          return siphash_4u32(ipv6_addr_hash(saddr), ipv6_addr_hash(daddr),
>                  (__force u32)id, 0, ip6_frags.rnd);
>  }
> 
> And then you make ip6_frags.rnd be of type siphash_key_t. Then
> everything is taken care of and works beautifully. Please see v5 of
> this patchset.

Sorry to not be specific enough, the Hash-DoS is in ipv6_addr_hash.
Maybe it was a silly example to start with, sorry. But anyway, your
proposal wouldn't have prevented the hash DoS. I wanted to show how it
can be difficult to make sure that all pointers come from an appropriate
aligned memory region.

The idea would be to actually factor out the key in the data structure
and align it with __aligned(SIPHASH_ALIGNMENT), make sure the padding
bits are all equal zero to not cause any bugs and irregularities with
the corresponding equality function. This might need some serious review
when switching to siphash to actually make use of it and prevent
HashDoS. Or simply use the unaligned version always...

>> I would be interested if the compiler can actually constant-fold the
>> address of the stack allocation with an simple if () or some
>> __builtin_constant_p fiddeling, so we don't have this constant review
>> overhead to which function we pass which data. This would also make
>> this whole discussion moot.
> 
> I'll play with it to see if the compiler is capable of doing that.
> Does anybody know off hand if it is or if there are other examples of
> the compiler doing that?

Not of the top of my head, but it should be easy to test.

> In any case, for all current replacement of jhash_1word, jhash_2words,
> jhash_3words, there's the siphash_2u32 or siphash_4u32 functions. This
> covers the majority of cases.

Agreed and this is also totally fine by me.

> For replacements of md5_transform, either the data is small and can
> fit in siphash_Nu{32,64}, or it can be put into a struct explicitly
> aligned on the stack.

> For the remaining use of jhash_nwords, either siphash() can be used or
> siphash_unaligned() can be used if the source is of unknown alignment.
> Both functions have their alignment requirements (or lack thereof)
> documented in a docbook comment.

I think the warning needs to be bigger, seriously. Most of the people
develop on 64 bit arch, where it will just work during testing and break
later on 32 bit. ;)

> I'll look into the constant folding to see if it actually works. If it
> does, I'll use it. If not, I believe the current solution works.
> 
> How's that sound?

I am still very much concerned about the API.

By the way, if you target net-next, it is currently closed. So no need
to hurry.

Bye,
Hannes

[toc] | [prev] | [next] | [standalone]

#1543134

On Thu, Dec 15, 2016 at 10:45 PM, Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
> By the way, if you target net-next, it is currently closed. So no need
> to hurry.

Honestly I have no idea what I'm targeting. The hash function touches
lib/. The secure_seq stuff touches net/. The rng stuff touches
random.c. Shall this be for net-next? For lib-next (doesn't exist)?
For tytso-next? Since a lot of feedback has come from netdev people, I
suspect net-next is the correct answer. In that case, I'll ask Ted for
his sign-off to touch random.c, and then we'll get this queued up in
net-next. Please correct me if this doesn't actually resemble how
things work around here...

Jason

[toc] | [prev] | [next] | [standalone]

#1543137

Hi Hannes,

Good news.

On Thu, Dec 15, 2016 at 10:45 PM, Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
>> How's that sound?
>
> I am still very much concerned about the API.

Thanks for pushing me and putting up with my daftness... the constant
folding works absolutely perfectly. I've run several tests. When gcc
knows that a struct is aligned (say, via __aligned(8)), then it erases
the branch and makes a direct jump to the aligned code. When it's
uncertain, it evaluates at runtime. So, now there is a single
siphash() function that chooses the best one automatically. Behind the
scene there's siphash_aligned and siphash_unaligned, but nobody needs
to call these directly. (Should I rename these to have a double
underscore prefix?) On platforms that have
CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS, of course all of this
disappears and everything goes directly to the aligned version.

So, I think this assuages your concerns entirely. A single API entry
point that does the right thing.

Whew! Good thinking, and thanks again for the suggestion.

Jason

[toc] | [prev] | [next] | [standalone]

#1543141 — Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function

On 16.12.2016 00:43, Jason A. Donenfeld wrote:
> Hi Hannes,
> 
> Good news.
> 
> On Thu, Dec 15, 2016 at 10:45 PM, Hannes Frederic Sowa
> <hannes@stressinduktion.org> wrote:
>>> How's that sound?
>>
>> I am still very much concerned about the API.
> 
> Thanks for pushing me and putting up with my daftness... the constant
> folding works absolutely perfectly. I've run several tests. When gcc
> knows that a struct is aligned (say, via __aligned(8)), then it erases
> the branch and makes a direct jump to the aligned code. When it's
> uncertain, it evaluates at runtime. So, now there is a single
> siphash() function that chooses the best one automatically. Behind the
> scene there's siphash_aligned and siphash_unaligned, but nobody needs
> to call these directly. (Should I rename these to have a double
> underscore prefix?) On platforms that have
> CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS, of course all of this
> disappears and everything goes directly to the aligned version.
> 
> So, I think this assuages your concerns entirely. A single API entry
> point that does the right thing.
> 
> Whew! Good thinking, and thanks again for the suggestion.

Awesome, thanks for trying this out. This basically resolves my concern
API-wise so far.

Hannes out. ;)

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web