arp_hash

arp_hash

[Herbert Xu]

Hi Dave:

While googling I found the 2011 discussion on changing the arp_hash
function.  I must say that I'm not really impressed by the new
function that replaced jhash :)

	u32 key = *(const u32 *)pkey;
	u32 val = key ^ hash32_ptr(dev);

	return val * hash_rnd[0];

Here pkey is the IP address (controllable by the attacker).  It
gets xored with the device pointer hash, which on x86-64 looks
like (0xffffffff ^ ptr) where ptr is a 32-bit value.  As ptr
must be aligned to at least 8 bytes (I think 16 is probably required
but I haven't checked), that means the bottom three bits of ptr
are 000 and hence the bottom three bits of hash32_ptr(dev) are
always 111.

So the attacker just has to use only addresses with the bottom
3 bits set to 111 and voila, the bottom three bits of val are
always 000.  So you've just cut down your search space by a factor
of 8.  If my assumption above of the 16-byte alignment is correct
then you can cut it down by a factor of 16.

If the attacker can somehow get the pointer value of the device
then all is lost since they could set any number of the low bits
of val to zero.

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

Re: arp_hash

[Eric Dumazet]

On Sun, 2015-03-22 at 22:42 +1100, Herbert Xu wrote:
> Hi Dave:
> 
> While googling I found the 2011 discussion on changing the arp_hash
> function.  I must say that I'm not really impressed by the new
> function that replaced jhash :)
> 
> 	u32 key = *(const u32 *)pkey;
> 	u32 val = key ^ hash32_ptr(dev);
> 
> 	return val * hash_rnd[0];
> 
> Here pkey is the IP address (controllable by the attacker).  It
> gets xored with the device pointer hash, which on x86-64 looks
> like (0xffffffff ^ ptr) where ptr is a 32-bit value.  As ptr
> must be aligned to at least 8 bytes (I think 16 is probably required
> but I haven't checked), that means the bottom three bits of ptr
> are 000 and hence the bottom three bits of hash32_ptr(dev) are
> always 111.
> 
> So the attacker just has to use only addresses with the bottom
> 3 bits set to 111 and voila, the bottom three bits of val are
> always 000.  So you've just cut down your search space by a factor
> of 8.  If my assumption above of the 16-byte alignment is correct
> then you can cut it down by a factor of 16.
> 
> If the attacker can somehow get the pointer value of the device
> then all is lost since they could set any number of the low bits
> of val to zero.

On x86_64, hash32_ptr(ptr) is not (0xffffffff ^ ptr) please look again.

Anyway, trying to avoid ARP 'attacks' is a lost battle.

Adding jhash() or whatever crypto will not fundamentally avoid the issue
there. 

Re: arp_hash

[David Miller]

From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Sun, 22 Mar 2015 05:56:21 -0700

> Anyway, trying to avoid ARP 'attacks' is a lost battle.
> 
> Adding jhash() or whatever crypto will not fundamentally avoid the
> issue there.

+1

Re: arp_hash

[Herbert Xu]

On Sun, Mar 22, 2015 at 05:56:21AM -0700, Eric Dumazet wrote:
>
> On x86_64, hash32_ptr(ptr) is not (0xffffffff ^ ptr) please look again.

OK it's not 0xffffffff but it's just as easy to figure out, you
can just cat /proc/net/unix.  On my machine everything starts at
0xffff880X and you can be pretty sure that if device was allocated
at boot then it's 0xffff8800.

And in my git tree it says:

static inline u32 hash32_ptr(const void *ptr)
{
	unsigned long val = (unsigned long)ptr;

#if BITS_PER_LONG == 64
	val ^= (val >> 32);
#endif
	return (u32)val;
}

What am I missing?

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

Re: arp_hash

[Herbert Xu]

On Sun, Mar 22, 2015 at 05:56:21AM -0700, Eric Dumazet wrote:
> On Sun, 2015-03-22 at 22:42 +1100, Herbert Xu wrote:
> > 
> > While googling I found the 2011 discussion on changing the arp_hash
> > function.  I must say that I'm not really impressed by the new
> > function that replaced jhash :)
> > 
> > 	u32 key = *(const u32 *)pkey;
> > 	u32 val = key ^ hash32_ptr(dev);
> > 
> > 	return val * hash_rnd[0];

In fact this function is worse than I thought.  Because the IP
address is stored in big-endian, the low bits correspond to the
first octet.  So in any network smaller than a /8 everything
hashes the same value.

Try running the following program with say 4096.

If this really didn't matter why don't you guys just use a linked
list? Surely that is going to be faster than doing a multiply :)

#include <stdio.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>

typedef unsigned char u8;
typedef unsigned int u32;

static inline u32 hash32_ptr(const void *ptr)
{
        unsigned long val = (unsigned long)ptr;

        val ^= (val >> 32);
        return (u32)val;
}

static inline u32 arp_hashfn(const void *pkey, const void *dev, u32 hash_rnd)
{
        u32 key = *(const u32 *)pkey;
        u32 val = key ^ hash32_ptr(dev);

        return val * hash_rnd;
}

int main(int argc, char **argv)
{
        int i;
        union {
                void *s;
                void *t;
                u32 l;
                in_addr_t a;
        } k = { .s = 0 };
        int total;

        total = atoi(argv[1]);

        k.a = inet_addr("10.0.0.0");

        for (i = 0; i < total; i++) {
                k.l = htonl(ntohl(k.l) + 1);
                printf("%s 0x%x\n", inet_ntoa(k.a), arp_hashfn(&k, (void *)0xffff88043d760000, 12345) & (total - 1));
        }

        return 0;
}

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

Re: arp_hash

[Herbert Xu]

On Mon, Mar 23, 2015 at 08:56:12AM +1100, Herbert Xu wrote:
> On Sun, Mar 22, 2015 at 05:56:21AM -0700, Eric Dumazet wrote:
> > On Sun, 2015-03-22 at 22:42 +1100, Herbert Xu wrote:
> > > 
> > > While googling I found the 2011 discussion on changing the arp_hash
> > > function.  I must say that I'm not really impressed by the new
> > > function that replaced jhash :)
> > > 
> > > 	u32 key = *(const u32 *)pkey;
> > > 	u32 val = key ^ hash32_ptr(dev);
> > > 
> > > 	return val * hash_rnd[0];
> 
> In fact this function is worse than I thought.  Because the IP

OK I'm wrong because net/core/neighbour.c uses only the high-order
bits of the hash.

Sorry for the noise.
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: arp_hash

[Herbert Xu]

On Mon, Mar 23, 2015 at 09:51:04AM +1100, Herbert Xu wrote:
> 
> OK I'm wrong because net/core/neighbour.c uses only the high-order
> bits of the hash.

Unfortunately even the high-order bits are too predictable:

10.0.0.128	0xbd78b1f2
10.0.0.64	0xfd78b1f2
10.0.0.192	0x7d78b1f2
10.0.0.32	0x9d78b1f2
...
10.0.0.63	0xd078b1f2
10.0.0.191	0x5078b1f2
10.0.0.127	0x9078b1f2
10.0.0.255	0x1078b1f2
10.0.1.0	0x60bdb1f2

As you can see there is a bit-to-bit correspondence.

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

Re: arp_hash

[Herbert Xu]

On Mon, Mar 23, 2015 at 10:22:42AM +1100, Herbert Xu wrote:
> On Mon, Mar 23, 2015 at 09:51:04AM +1100, Herbert Xu wrote:
> > 
> > OK I'm wrong because net/core/neighbour.c uses only the high-order
> > bits of the hash.
> 
> Unfortunately even the high-order bits are too predictable:
> 
> 10.0.0.128	0xbd78b1f2
> 10.0.0.64	0xfd78b1f2
> 10.0.0.192	0x7d78b1f2
> 10.0.0.32	0x9d78b1f2
> ...
> 10.0.0.63	0xd078b1f2
> 10.0.0.191	0x5078b1f2
> 10.0.0.127	0x9078b1f2
> 10.0.0.255	0x1078b1f2

I should've put this here

10.0.128.0	0x9af8b1f2

> 10.0.1.0	0x60bdb1f2
> 
> As you can see there is a bit-to-bit correspondence.

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

Re: arp_hash

[Herbert Xu]

On Mon, Mar 23, 2015 at 10:35:12AM +1100, Herbert Xu wrote:
> On Mon, Mar 23, 2015 at 10:22:42AM +1100, Herbert Xu wrote:
>
> > Unfortunately even the high-order bits are too predictable:
> > 
> > 10.0.0.128	0xbd78b1f2
> > 10.0.0.64	0xfd78b1f2
> > 10.0.0.192	0x7d78b1f2
> > 10.0.0.32	0x9d78b1f2
> > ...
> > 10.0.0.63	0xd078b1f2
> > 10.0.0.191	0x5078b1f2
> > 10.0.0.127	0x9078b1f2
> > 10.0.0.255	0x1078b1f2
> 
> I should've put this here
> 
> 10.0.128.0	0x9af8b1f2

OK I don't have a good way of exploiting this, so maybe this
isn't a problem after all.

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

Re: arp_hash

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Mon, 23 Mar 2015 08:56:12 +1100

> On Sun, Mar 22, 2015 at 05:56:21AM -0700, Eric Dumazet wrote:
>> On Sun, 2015-03-22 at 22:42 +1100, Herbert Xu wrote:
>> > 
>> > While googling I found the 2011 discussion on changing the arp_hash
>> > function.  I must say that I'm not really impressed by the new
>> > function that replaced jhash :)
>> > 
>> > 	u32 key = *(const u32 *)pkey;
>> > 	u32 val = key ^ hash32_ptr(dev);
>> > 
>> > 	return val * hash_rnd[0];
> 
> In fact this function is worse than I thought.  Because the IP
> address is stored in big-endian, the low bits correspond to the
> first octet.  So in any network smaller than a /8 everything
> hashes the same value.

I won't argue that there might be some bugs here, and there is some
lost entropy, and that we should fix them.

But I do not agree with the idea that it is in any way possible to
stop someone with root access on the physical network from crudding up
our ARP hash tables.

Re: arp_hash

[Herbert Xu]

On Sun, Mar 22, 2015 at 06:58:50PM -0400, David Miller wrote:
>
> But I do not agree with the idea that it is in any way possible to
> stop someone with root access on the physical network from crudding up
> our ARP hash tables.

But you don't need root access to exploit the neighbour hash
table.  You just need a sufficiently large (e.g., /16) route
to a network and anybody on the system can then generate traffic
to it.

Granted these days hardly anybody on IPv4 would have such a route
but if you do then the hash table makes you exposed.

And for IPv6 everybody is potentially exposed.

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

Re: arp_hash

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Mon, 23 Mar 2015 10:08:48 +1100

> On Sun, Mar 22, 2015 at 06:58:50PM -0400, David Miller wrote:
>>
>> But I do not agree with the idea that it is in any way possible to
>> stop someone with root access on the physical network from crudding up
>> our ARP hash tables.
> 
> But you don't need root access to exploit the neighbour hash
> table.  You just need a sufficiently large (e.g., /16) route
> to a network and anybody on the system can then generate traffic
> to it.
> 
> Granted these days hardly anybody on IPv4 would have such a route
> but if you do then the hash table makes you exposed.
> 
> And for IPv6 everybody is potentially exposed.

BTW I asked for feedback when I posted the patches which created this
situation, and the multiply with the random input was believed to have
sufficient entropy and not create a situation any worse,
asymptotically, than what we had beforehand.

Perhaps the ipv6 case can be improved, by using a u32 random input
for each u32 of the address being hashed.

Re: arp_hash

[Herbert Xu]

On Sun, Mar 22, 2015 at 07:50:03PM -0400, David Miller wrote:
>
> BTW I asked for feedback when I posted the patches which created this
> situation, and the multiply with the random input was believed to have
> sufficient entropy and not create a situation any worse,
> asymptotically, than what we had beforehand.

I know.  I just didn't know at the time or I would have objected :)

> Perhaps the ipv6 case can be improved, by using a u32 random input
> for each u32 of the address being hashed.

See my follow-up email.  The multiplication is useless against
an adversary, even if you multiply it against a secret odd value
because there is a bit-to-bit correspondence between the key and
the final hash value.

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

Re: arp_hash

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Sun, 22 Mar 2015 22:42:04 +1100

> If the attacker can somehow get the pointer value of the device
> then all is lost since they could set any number of the low bits
> of val to zero.

This "attacker" with access to your physcial network?

I'm all for shifting the device pointer down a few bits to get more
entropy, but I don't completely agree with the rest of your
objections.

This hash function has to be as fast as possible, even jhash{,2} is
too expensive.

Re: arp_hash

[Herbert Xu]

On Sun, Mar 22, 2015 at 12:54:58PM -0400, David Miller wrote:
> From: Herbert Xu <herbert@gondor.apana.org.au>
> Date: Sun, 22 Mar 2015 22:42:04 +1100
> 
> > If the attacker can somehow get the pointer value of the device
> > then all is lost since they could set any number of the low bits
> > of val to zero.
> 
> This "attacker" with access to your physcial network?

It could be a malicious local user, or it could be any host
if you are a router.
 
> I'm all for shifting the device pointer down a few bits to get more
> entropy, but I don't completely agree with the rest of your
> objections.

Granted for IPv4 you're not going to be in big trouble unless
you have a very large network (e.g. /16) configured.  But with
IPv6 this could seriously hose your box.

> This hash function has to be as fast as possible, even jhash{,2} is
> too expensive.

So what scales we are talking about, twice, three times? Have you
considered more modern hashes such as SipHash or SpookyHash
(successor to jhash/lookup3 and supposedly faster)?

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

Re: arp_hash

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Mon, 23 Mar 2015 08:34:08 +1100

> So what scales we are talking about, twice, three times? Have you
> considered more modern hashes such as SipHash or SpookyHash
> (successor to jhash/lookup3 and supposedly faster)?

I want it to be one cycle or two.

Every single transmitted packet hits this hash demux.

Re: arp_hash

[Herbert Xu]

On Sun, Mar 22, 2015 at 06:57:14PM -0400, David Miller wrote:
> From: Herbert Xu <herbert@gondor.apana.org.au>
> Date: Mon, 23 Mar 2015 08:34:08 +1100
> 
> > So what scales we are talking about, twice, three times? Have you
> > considered more modern hashes such as SipHash or SpookyHash
> > (successor to jhash/lookup3 and supposedly faster)?
> 
> I want it to be one cycle or two.
> 
> Every single transmitted packet hits this hash demux.

For hosts can we cache this? For routers I guess this is just
the mummified remains of the route cache :)

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

Re: arp_hash

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Mon, 23 Mar 2015 10:42:18 +1100

> On Sun, Mar 22, 2015 at 06:57:14PM -0400, David Miller wrote:
>> From: Herbert Xu <herbert@gondor.apana.org.au>
>> Date: Mon, 23 Mar 2015 08:34:08 +1100
>> 
>> > So what scales we are talking about, twice, three times? Have you
>> > considered more modern hashes such as SipHash or SpookyHash
>> > (successor to jhash/lookup3 and supposedly faster)?
>> 
>> I want it to be one cycle or two.
>> 
>> Every single transmitted packet hits this hash demux.
> 
> For hosts can we cache this? For routers I guess this is just
> the mummified remains of the route cache :)

We want no reference counting of the neighbour entries, that's one of
the main points of all this.

That way packets getting stuck do not run into the classic
dreaded "Neighbour table overflow", remember that?

THAT is what is attackable when people have /8 subnets and
someone just spam pings every host on that subnet.

That is a more serious exposure than this hashing issue.

At least with ref-less use, as we have now, we could trim hash chains
that get too large with almost no barriers whatsoever because nearly
every neigh entry has no external references outside of these demux
sequences.

Re: arp_hash

[Herbert Xu]

On Sun, Mar 22, 2015 at 07:53:15PM -0400, David Miller wrote:
>
> We want no reference counting of the neighbour entries, that's one of
> the main points of all this.
> 
> That way packets getting stuck do not run into the classic
> dreaded "Neighbour table overflow", remember that?

Right.

> THAT is what is attackable when people have /8 subnets and
> someone just spam pings every host on that subnet.
> 
> That is a more serious exposure than this hashing issue.
> 
> At least with ref-less use, as we have now, we could trim hash chains
> that get too large with almost no barriers whatsoever because nearly
> every neigh entry has no external references outside of these demux
> sequences.

Yes if we trim the buckets to keep the chain length under a limit
it should be good enough I think.

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