netdev - Re: [PATCH RFC] ipv6: use stronger hash for reassembly queue hash table

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 for Android: free password hash cracker in your pocket

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

Message-ID: <20130308130433.GB28531@order.stressinduktion.org>
Date:	Fri, 8 Mar 2013 14:04:33 +0100
From:	Hannes Frederic Sowa <hannes@...essinduktion.org>
To:	netdev@...r.kernel.org, eric.dumazet@...il.com,
	yoshfuji@...ux-ipv6.org
Subject: Re: [PATCH RFC] ipv6: use stronger hash for reassembly queue hash table

On Fri, Mar 08, 2013 at 06:57:18AM +0100, Hannes Frederic Sowa wrote:
> On Thu, Mar 07, 2013 at 10:42:11PM +0100, Hannes Frederic Sowa wrote:
> > ipv6_addr_hash can yield the exact same hash value for countless ip
> > addresses from one /64 subnet. Let's make it a bit harder to create a
> > long list of reassembly queues in the hash table by using a stronger hash.
> > 
> > I spotted this just by looking at the source and did not verify if it
> > is really the case, so this patch has RFC status. But the jhash change
> > should not really hurt anyway. This patch is only compile tested.
> 
> Hmpf, I haven't seen Eric's change(279e9f2: ipv6: optimize
> inet6_hash_frag()) and tried to compare a v3.8 against a net-next
> kernel. At a first sight, it seems in some kind of denial of service
> scenario the relative amount of time spend in inet_frag_find increased,
> but I will do more comparable benchmarks later today (could be also
> because of other changes). I just wanted to let you know that I will do
> more research on this one and that you shouldn't apply this patch for now.
> 
> I also noticed that this function is also used by netfilter in the
> forwarding path. Perhaps a jenkins hash on the destination address would
> be better, too. Perhaps a netfilter specific hash function could also
> be used.

Getting benchmarks on my box is actually pretty hairy without burning
it down. :)

Generating a flow of fragmented packets with frag_id set to zero and ipv6
addresses which generate the same ipv6_addr_hash I gathered this from a debug
printk in inet6_hash_frag (current version from net-next):

[   25.992202] FRAG6: hash -635286572
[   25.992218] FRAG6: hash -635286572
[   25.992237] FRAG6: hash -635286572
[   25.992253] FRAG6: hash -635286572
[   25.992273] FRAG6: hash -635286572
[   25.992289] FRAG6: hash -635286572
[   25.992309] FRAG6: hash -635286572
[   25.992327] FRAG6: hash -635286572
[   25.992347] FRAG6: hash -635286572
[   25.992363] FRAG6: hash -635286572
[   25.992382] FRAG6: hash -635286572
[   25.992398] FRAG6: hash -635286572

With the patches reverted:

[   39.770790] FRAG6: hash 1323153854
[   39.773691] FRAG6: hash 1323153854
[   39.776413] FRAG6: hash 977187067
[   39.778782] FRAG6: hash 977187067
[   39.781298] FRAG6: hash -1226453562
[   39.784043] FRAG6: hash -1226453562
[   39.786443] FRAG6: hash -923346920
[   39.789431] FRAG6: hash -923346920
[   39.792205] FRAG6: hash 282862966
[   39.794918] FRAG6: hash 282862966
[   39.797749] FRAG6: hash -1059175404
[   39.800054] FRAG6: hash -1059175404
[   39.802904] FRAG6: hash -1085381868

It is pretty simple to generate a source of different addresses that yield to
the same hash value.

So I am in favour to revert the optimization changes in 279e9f2. It seems that
even ipv6_addr_jhash is not strong enough when used in the forwarding path for
reassembly, because of the xor of the most significant 32 bits of the address.

Quick test program is here: https://gist.github.com/hannes/5116331

Ok if I send a patch later to revert this change? What do you think about
increasing the size of the fragmentation queue hash table INETFRAGS_HASHSZ,
too?

Thanks,

  Hannes

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