From: David Miller <davem@davemloft.net> Date: 2011-07-08 17:11:01
Using Jenkins is over the top.
If the premise is that the hash_rnd is a random unpredictable key,
then:
key ^ dev->ifindex ^ hash_rnd
results in an unpredictable hash result, even if an attacker
controls 'key' and 'dev->ifindex' completely.
Therefore, if this hash result is unpredictable, then the
final fold phase of:
(val >> 8) ^ (val >> 16) ^ (val >> 24)
is unpredictable as well.
Signed-off-by: David S. Miller <davem@davemloft.net>
---
Someone please check my logic :-) This sames ~100 cycles during a
neigh_lookup() on my Niagara2 box.
From: Martin Mares <mj@ucw.cz> Date: 2011-07-08 17:46:02
Hello!
Using Jenkins is over the top.
If the premise is that the hash_rnd is a random unpredictable key,
then:
key ^ dev->ifindex ^ hash_rnd
results in an unpredictable hash result, even if an attacker
controls 'key' and 'dev->ifindex' completely.
Therefore, if this hash result is unpredictable, then the
final fold phase of:
(val >> 8) ^ (val >> 16) ^ (val >> 24)
is unpredictable as well.
If I understand the new hash function correctly, it should be very easy
for an outside attacker to force arbitrary collisions.
The hash function is linear, so it can be reduced to:
a = key ^ dev->ifindex
return (a >> 8) ^ (a >> 16) ^ (a >> 24) // (1)
^ (hash_rnd >> 8) ^ (hash_rnd >> 16) ^ (hash_rnd >> 24) // (2)
Where (1) is under control of the attacker and while (2) is not, the
only effect of (2) is a random permutation on the hash buckets.
I.e., the attacker can generate arbitrarily long collision chains,
although he cannot pick the bucket where the collisions happen :)
Am I right?
Have a nice fortnight
--
Martin `MJ' Mares [off-list ref] http://mj.ucw.cz/
Faculty of Math and Physics, Charles University, Prague, Czech Rep., Earth
If going to a church makes you a Christian, does going to a garage make you a car?
The hash function is linear, so it can be reduced to:
a = key ^ dev->ifindex
return (a >> 8) ^ (a >> 16) ^ (a >> 24) // (1)
^ (hash_rnd >> 8) ^ (hash_rnd >> 16) ^ (hash_rnd >> 24) // (2)
Is this really the same? The inclusion of a full 32-bit xor
with hash_rnd before folding was intentional, so that the
final folding occurs on a completely "random" value.
Where (1) is under control of the attacker and while (2) is not, the
only effect of (2) is a random permutation on the hash buckets.
I.e., the attacker can generate arbitrarily long collision chains,
although he cannot pick the bucket where the collisions happen :)
Am I right?
The hash function is linear, so it can be reduced to:
a = key ^ dev->ifindex
return (a >> 8) ^ (a >> 16) ^ (a >> 24) // (1)
^ (hash_rnd >> 8) ^ (hash_rnd >> 16) ^ (hash_rnd >> 24) // (2)
Is this really the same? The inclusion of a full 32-bit xor
with hash_rnd before folding was intentional, so that the
final folding occurs on a completely "random" value.
For example, try out this test program. Run as "./x ${RANDOM_VALUE}",
it shows that the attacker cannot simply just iterate by the number of
hash table slots to create collisions, assuming a hash table size of
256 slots:
--------------------
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char **argp)
{
int i, rnd;
rnd = atoi(argp[1]);
for (i = 1; i < (64 * 1024); i += 256) {
int x = (i ^ rnd);
x ^= (x >> 8) ^ (x << 16) ^ (x >> 24);
x &= 0xff;
printf("%d\n", x);
}
return 0;
}
The hash function is linear, so it can be reduced to:
a = key ^ dev->ifindex
return (a >> 8) ^ (a >> 16) ^ (a >> 24) // (1)
^ (hash_rnd >> 8) ^ (hash_rnd >> 16) ^ (hash_rnd >> 24) // (2)
Is this really the same? The inclusion of a full 32-bit xor
with hash_rnd before folding was intentional, so that the
final folding occurs on a completely "random" value.
Martin's reduction looks exactly correct to me.
-John
The hash function is linear, so it can be reduced to:
a = key ^ dev->ifindex
return (a >> 8) ^ (a >> 16) ^ (a >> 24) // (1)
^ (hash_rnd >> 8) ^ (hash_rnd >> 16) ^ (hash_rnd >> 24) // (2)
Is this really the same? The inclusion of a full 32-bit xor
with hash_rnd before folding was intentional, so that the
final folding occurs on a completely "random" value.
Martin's reduction looks exactly correct to me.
Ok, there was also an unintended bug in my original patch,
I lost the bottom 8 bits in the fold, the hash function
should instead be:
+static inline u32 arp_hashfn(u32 key, const struct net_device *dev, u32 hash_rnd)
+{
+ u32 val = key ^ dev->ifindex ^ hash_rnd;
+
+ return val ^ (val >> 8) ^ (val >> 16) ^ (val >> 24);
+}
From: Roland Dreier <hidden> Date: 2011-07-08 19:26:38
On Fri, Jul 8, 2011 at 11:06 AM, David Miller [off-list ref] wrote:
Ok, there was also an unintended bug in my original patch,
I lost the bottom 8 bits in the fold, the hash function
should instead be:
+static inline u32 arp_hashfn(u32 key, const struct net_device *dev, u32 hash_rnd)
+{
+ u32 val = key ^ dev->ifindex ^ hash_rnd;
+
+ return val ^ (val >> 8) ^ (val >> 16) ^ (val >> 24);
+}
Doesn't seem to matter much -- this is now equivalent to
a = key ^ dev->ifindex
return (a ^ (a >> 8) ^ (a >> 16) ^ (a >> 24)) // (1)
^ (rnd ^ (rnd >> 8) ^ (rnd >> 16) ^ (rnd >> 24)) // (2)
where again the attacker controls (1), and (2) is a constant.
On Fri, Jul 8, 2011 at 11:06 AM, David Miller [off-list ref] wrote:
quoted
Ok, there was also an unintended bug in my original patch,
I lost the bottom 8 bits in the fold, the hash function
should instead be:
+static inline u32 arp_hashfn(u32 key, const struct net_device *dev, u32 hash_rnd)
+{
+ u32 val = key ^ dev->ifindex ^ hash_rnd;
+
+ return val ^ (val >> 8) ^ (val >> 16) ^ (val >> 24);
+}
Doesn't seem to matter much -- this is now equivalent to
a = key ^ dev->ifindex
return (a ^ (a >> 8) ^ (a >> 16) ^ (a >> 24)) // (1)
^ (rnd ^ (rnd >> 8) ^ (rnd >> 16) ^ (rnd >> 24)) // (2)
where again the attacker controls (1), and (2) is a constant.
Right, but how can you attack it? Show me how you can grow
a hash chain of arbitrary length by modulating the key in
a deterministic way.
Nobody has done this yet.
On Fri, Jul 8, 2011 at 11:06 AM, David Miller [off-list ref] wrote:
quoted
Ok, there was also an unintended bug in my original patch,
I lost the bottom 8 bits in the fold, the hash function
should instead be:
+static inline u32 arp_hashfn(u32 key, const struct net_device *dev, u32 hash_rnd)
+{
+ u32 val = key ^ dev->ifindex ^ hash_rnd;
+
+ return val ^ (val >> 8) ^ (val >> 16) ^ (val >> 24);
+}
Doesn't seem to matter much -- this is now equivalent to
a = key ^ dev->ifindex
return (a ^ (a >> 8) ^ (a >> 16) ^ (a >> 24)) // (1)
^ (rnd ^ (rnd >> 8) ^ (rnd >> 16) ^ (rnd >> 24)) // (2)
where again the attacker controls (1), and (2) is a constant.
Right, but how can you attack it? Show me how you can grow
a hash chain of arbitrary length by modulating the key in
a deterministic way.
For 256 buckets its easy:
hash_index = b[0] ^ b[1] ^ b[2] ^ b[3];
(b[i] are bytes of the key)
With b[3] = b[0] ^ b[1] ^ b[2] you get 2^24 keys that hash to the same bucket.
Best Regards,
Michał Mirosław
With b[3] = b[0] ^ b[1] ^ b[2] you get 2^24 keys that hash to the same bucket.
Ok, I'm convinced, thanks :-)
Although, actually it's not this simple. The attack doesn't work.
As they "attack" us, the ARP hash table grows and thus the hash mask
changes to match. Then his old collisions won't collide any more.
We could even adjust the fold shifts as the table grows to make this
effect even more pronounced.
With b[3] = b[0] ^ b[1] ^ b[2] you get 2^24 keys that hash to the same bucket.
Ok, I'm convinced, thanks :-)
Although, actually it's not this simple. The attack doesn't work.
As they "attack" us, the ARP hash table grows and thus the hash mask
changes to match. Then his old collisions won't collide any more.
We could even adjust the fold shifts as the table grows to make this
effect even more pronounced.
There will still be 2^32/n_buckets known values that hash to the same
bucket for every n_buckets. So if the attacker knows when and how the
hash size changes, he can adapt accordingly. It should be easier to
see when you get rid of the XOR [random, but] constant part.
Best Regards,
Michał Mirosław
With b[3] = b[0] ^ b[1] ^ b[2] you get 2^24 keys that hash to the same bucket.
Ok, I'm convinced, thanks :-)
Although, actually it's not this simple. The attack doesn't work.
As they "attack" us, the ARP hash table grows and thus the hash mask
changes to match. Then his old collisions won't collide any more.
We could even adjust the fold shifts as the table grows to make this
effect even more pronounced.
There will still be 2^32/n_buckets known values that hash to the same
bucket for every n_buckets. So if the attacker knows when and how the
hash size changes, he can adapt accordingly. It should be easier to
see when you get rid of the XOR [random, but] constant part.
BTW, am I correct, that neighbour hash tables never shrink? Looking at
net/core/neighbour.c it seems that after the table reaches gc_thresh3
capacity, it is never reallocated again.
Best Regards,
Michał Mirosław
BTW, am I correct, that neighbour hash tables never shrink? Looking at
net/core/neighbour.c it seems that after the table reaches gc_thresh3
capacity, it is never reallocated again.
From: Roland Dreier <hidden> Date: 2011-07-08 20:45:05
quoted
Doesn't seem to matter much -- this is now equivalent to
a = key ^ dev->ifindex
return (a ^ (a >> 8) ^ (a >> 16) ^ (a >> 24)) // (1)
^ (rnd ^ (rnd >> 8) ^ (rnd >> 16) ^ (rnd >> 24)) // (2)
where again the attacker controls (1), and (2) is a constant.
Right, but how can you attack it? Show me how you can grow
a hash chain of arbitrary length by modulating the key in
a deterministic way.
Well, if two things hash to different buckets with the full hash
function, then they already hashed to different buckets without
the extra randomness. So why bother with hash_rnd?
The answer is that you have to mix hash_rnd into the hash
in a nonlinear way, so that an attacker can't know if two values
end up in the same bucket or not.
With your hash function, the attacker can just compute the
hash (without hash_rnd) for all the values of key ^ ifindex
and then use all the values that end up in the same bucket.
- R.
The answer is that you have to mix hash_rnd into the hash
in a nonlinear way, so that an attacker can't know if two values
end up in the same bucket or not.
With your hash function, the attacker can just compute the
hash (without hash_rnd) for all the values of key ^ ifindex
and then use all the values that end up in the same bucket.
Ok, thanks everyone for explaining things.
So what is the cheapest non-linear function we could use?
From: Roland Dreier <hidden> Date: 2011-07-08 23:11:21
On Fri, Jul 8, 2011 at 3:32 PM, David Miller [off-list ref] wrote:
So what is the cheapest non-linear function we could use?
I'm not comfortable giving cryptographic advice, but even + (addition
with carry) is nonlinear when combined with ^. However that seems
like the low-order bits might be too predictable.
Maybe * of hash key with a random odd value is good enough?
- R.
From: Stephen Hemminger <hidden> Date: 2011-07-08 23:41:31
What about using murmur hash which has a four byte pass as well.
https://sites.google.com/site/murmurhash/
---
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#define u32 uint32_t
/* Do a one pass murmurhash2 */
static u32 arp_hashfn(u32 key, int ifindex, u32 hash_rnd)
{
/* murmurhash mixiing constants */
const unsigned int m = 0x5bd1e995;
const int r = 24;
/* Initialize the hash to a 'random' value */
unsigned int h = ifindex ^ hash_rnd;
unsigned int k = key;
k *= m;
k ^= k >> r;
k *= m;
h *= m;
h ^= k;
/* Do a few final mixes of the hash to ensure the last few
* bytes are well-incorporated.
*/
h ^= h >> 13;
h *= m;
h ^= h >> 15;
return h;
}
int main(int argc, char **argv)
{
u32 rnd, key, hash;
int ifindex;
key = atoi(argv[1]);
ifindex = atoi(argv[2]);
rnd = atoi(argv[3]);
hash = arp_hashfn(key, ifindex, rnd);
printf("%u, %d, %u => %u\n", key, ifindex, rnd, hash);
return 0;
}
I'm trying to avoid multiplies that are not done in hardware on some
cpus.
Right now I'm looking at one of Thomas Wang's hashes, referenced on
Bob Jenkin's hash analysis page:
u32 hashint(u32 a)
{
a += ~(a<<15);
a ^= (a>>10);
a += (a<<3);
a ^= (a>>6);
a += ~(a<<11);
a ^= (a>>16);
return a;
}
It's 15 instructions, and produces better entropy in the low bits of
the result than the high bits, which is fine for how we'll use this
thing.
I'm trying to avoid multiplies that are not done in hardware on some
cpus.
Right now I'm looking at one of Thomas Wang's hashes, referenced on
Bob Jenkin's hash analysis page:
u32 hashint(u32 a)
{
a += ~(a<<15);
a ^= (a>>10);
a += (a<<3);
a ^= (a>>6);
a += ~(a<<11);
a ^= (a>>16);
return a;
}
It's 15 instructions, and produces better entropy in the low bits of
the result than the high bits, which is fine for how we'll use this
thing.
Ok. but you really have sell those Sparc's while they are still
worth something on Ebay :-)
Maybe * of hash key with a random odd value is good enough?
Yes, from what I've read over the past few days it should
be. More precisely:
(key * hash_rnd) >> (32 - hash_table_size_log2)
where "hash_rnd" is odd.
The reason we want the top bits is because multiplies intrinsically
work such that bits in the inputs can only effect the same or higher
bits in the result.