netdev - Re: [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch

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-gAq=knRnf73qrOKuWy=WVaHvq2Vzb8RC39p81WBXZ8Q@mail.gmail.com>
Date:	Mon, 2 Mar 2015 07:31:45 -0800
From:	Tom Herbert <therbert@...gle.com>
To:	Eric Dumazet <eric.dumazet@...il.com>
Cc:	David Miller <davem@...emloft.net>,
	Linux Netdev List <netdev@...r.kernel.org>,
	Florian Westphal <fw@...len.de>
Subject: Re: [PATCH net-next 6/6] sched: Eliminate use of flow_keys in sch_sfq

On Sun, Mar 1, 2015 at 4:58 PM, Eric Dumazet <eric.dumazet@...il.com> wrote:
> On Sun, 2015-03-01 at 14:09 -0800, Tom Herbert wrote:
>> Call qdisc_skb_get_hash instead of doing skb_flow_dissect and then
>> jhash by hand.
>
> This defeats one of the perturbation goal :
>
> If two flows hashes into same hash, then skb_get_hash_perturb(skb,
> q->perturbation) will also give same hash forever and map to same hash
> bucket.
>
As I already mentioned, the probability of skb_get_hash returning the
same value for two flows is 1/2^32. I suspect it's greater probability
to get a hash collision between two IPv6 flows with subtlety different
addresses or simply match 4-tuples in different address spaces (like
VLAN or with VNID). If hash collision is really a problem, we can
periodically rekey skb->hash (either SW or HW) or maybe move to 64 bit
hashes somehow. Anyway, we potentially have the same problem in RSS
and other uses of the hash, if hashes collide then two flows share the
same bucket forever unless there is an action to break that.

> Ideally, we could add a 'u32 perturbation' salt to
> __skb_get_hash()/__flow_hash_from_keys()/__flow_hash_3words instead of
> using a net_get_random_once(&hashrnd, sizeof(hashrnd));
>
> but I guess all these functions are becoming very fat.
>
Same thing as rekeying.

>
>
--
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