netdev - Re: [PATCH net-next 0/6] net: Call skb_get

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CA+mtBx-2pjHmi4B0bo+oCQfMGWn7k26qvYUvNNwSLTZaK8YTwg@mail.gmail.com>
Date:	Thu, 5 Mar 2015 09:19:01 -0800
From:	Tom Herbert <therbert@...gle.com>
To:	David Laight <David.Laight@...lab.com>
Cc:	"davem@...emloft.net" <davem@...emloft.net>,
	"netdev@...r.kernel.org" <netdev@...r.kernel.org>,
	"eric.dumazet@...il.com" <eric.dumazet@...il.com>,
	"fw@...len.de" <fw@...len.de>
Subject: Re: [PATCH net-next 0/6] net: Call skb_get_hash in qdiscs

On Thu, Mar 5, 2015 at 3:13 AM, David Laight <David.Laight@...lab.com> wrote:
> From: Tom Herbert
> ...
>> - The probability that two different flows randomly match to the same
>>   hash from skb_get_hash is 1/2^32. If such a collision were to happen,
>>   then the flows potentially also map to the same qdisc queue in
>>   perpetuity despite perturbation being performed. Given the very low
>>   probability of this occurring, this may in practice only be an
>>   academic issue. If it is a real concern, rekeying of the underlying
>>   mechanisms of skb->hash could be done.
> ...
>
> The probability of a collision is much higher than that.
> With 10000 flows it is (if my 'ballpark maths' is right) nearer 1/100.
>

Probably a little closer to 1/50. But this is the best case scenario
that assumes a completely random input. In reality the input could be
heavily biased substantially increasing collisions. Consider if
we're in the forwarding path for two NVEs tunneling using VXLAN.
Encapsulated flows will differ in flow_keys only in source port with
14 bits of entropy. Now with 100 flows collision probability is 1/25,
at at 1000 flows you're pretty much guaranteed collisions. In such a
scenario, any amount of perturbation, re-keying of hashes, even
switching to more fancy hash algorithms doesn't help-- the root
problem is that the input domain does not contain sufficient entropy.

This is not just a performance issue, this is an obvious security
issue. It's fairly easy to DOS 5-tuples at will by spoofing packets
with different 5-tuples. This is absolutely trivial with IPv6. Given
we want to DOS a TCP connection with four tuple <S,D,s,d> and source
address is of form w::x:y, we can just change to the source address to
be w::x^J:y:^J and copy rest of the four-tuple. For any J this creates
same src value in flow_keys as w::x:y, hence always the same hash.
There are similar ways to spoof 4-tuple with IPv4 tunnels like the
VXLAN case above.

So if we want to fix this, we need to address the limited information
used in flow_keys. 1) flow_keys needs more information such as full
IPv6 address, VLAN, GRE keyid, and flow label. 2) We need a hash
function that can take more bits of flow_kesy as input to avoid the
aliasing problems like we see with the IPv6 case. This is where I am
going with these patches.

Tom
>         David
>
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html