| 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
| ||
|
Message-ID: <20230724195813.11319-1-kuniyu@amazon.com>
Date: Mon, 24 Jul 2023 12:58:13 -0700
From: Kuniyuki Iwashima <kuniyu@...zon.com>
To: <trawets@...zon.com>
CC: <aksecurity@...il.com>, <benh@...zon.com>, <davem@...emloft.net>,
<dsahern@...nel.org>, <edumazet@...gle.com>, <kuba@...nel.org>,
<kuni1840@...il.com>, <kuniyu@...zon.co.jp>, <netdev@...r.kernel.org>,
<pabeni@...hat.com>, <samjonas@...zon.com>
Subject: Re: [PATCH v2 net] tcp: Reduce chance of collisions in inet6_hashfn().
From: "Smith, Stewart" <trawets@...zon.com>
Date: Sat, 22 Jul 2023 03:17:53 +0000
> On Jul 21, 2023, at 6:39 PM, Iwashima, Kuniyuki <kuniyu@...zon.co.jp> wrote:
> >
> > From: Amit Klein <aksecurity@...il.com>
> > Date: Sat, 22 Jul 2023 03:07:49 +0300
> >> Resending because some recipients require plaintext email. Sorry.
> >> Original message:
> >>
> >> This is certainly better than the original code.
> >
> > Thanks for reviewing!
> >
> >
> >>
> >> Two remarks:
> >>
> >> 1. In general, using SipHash is more secure, even if only for its
> >> longer key (128 bits, cf. jhash's 32 bits), which renders simple
> >> enumeration attacks infeasible. I understand that in a different
> >> context, switching from jhash to siphash incurred some overhead, but
> >> maybe here it won't.
> >
> > I see. Stewart tested hsiphash and observed more overhead as
> > noted in the changelog, but let me give another shot to SipHash
> > and HSiphash.
>
> When originally looking at what to do for the collisions, it did seem
> like siphash would be the better hash, but I did have some concern around
> what the real-world performance impact could be, and wanted to have
> something that would alleviate the issue at hand that nobody could even
> *possibly* remotely contemplate complaining was a problem to apply the
> patch to their systems because of “performance”.. which was why keeping
> jhash but with modifications was where we started.
>
> Two things about siphash/hsiphash that I had open questions about:
> - is the extra overhead of the hash calculation going to be noticeable at
> all in any regular workload
> - all the jhash stuff gets inlined nicely and the compiler does wonderful
> things, but it’s possible that siphash will end up always with a jump,
> which would add more to the extra overhead (and that llvm-mca doesn’t
> really model well, so it was harder to prove in sim). Again, not quite
> sure the real world impact to real world workloads.
Here is the llvm-mca result. Base commit is 1671bcfd76fd.
In Total Cycles, siphash is much slower than others.
On Skylake: jhash2: +10%, hsiphash +8%, siphash: +23%
On Nehalem: jahsh2: +5%, hsiphash +9%, siphash: +26%
Skylake base jhash2 hsiphash siphash
Iterations 1.00 1.00 (100.00) 1.00 (100.00) 1.00 (100.00)
Instructions 104.00 137.00 (131.73) 166.00 (159.62) 222.00 (213.46)
Total Cycles 155.00 171.00 (110.32) 168.00 (108.39) 191.00 (123.23)
Total uOps 132.00 166.00 (125.76) 192.00 (145.45) 248.00 (187.88)
Dispatch Width 6.00 6.00 (100.00) 6.00 (100.00) 6.00 (100.00)
uOps Per Cycle 0.85 0.97 (114.12) 1.14 (134.12) 1.30 (152.94)
IPC 0.67 0.80 (119.40) 0.99 (147.76) 1.16 (173.13)
Nehalem base jhash2 hsiphash siphash
Iterations 1.00 1.00 (100.00) 1.00 (100.00) 1.00 (100.00)
Instructions 104.00 137.00 (131.73) 166.00 (159.62) 222.00 (213.46)
Total Cycles 173.00 182.00 (105.20) 190.00 (109.83) 218.00 (126.01)
Total uOps 130.00 170.00 (130.77) 215.00 (165.38) 295.00 (226.92)
Dispatch Width 4.00 4.00 (100.00) 4.00 (100.00) 4.00 (100.00)
uOps Per Cycle 0.75 0.93 (124.00) 1.13 (150.67) 1.35 (180.00)
IPC 0.60 0.75 (125.00) 0.87 (145.00) 1.02 (170.00)
However, inet6_ehashfn() is not dominant in the fast path, and there
seems to be not so big impact during benchmarking with super_netperf.
for i in $(seq 1 5);
do
for i in 64 128 256 512 1024 2048 4096;
do
printf "%4d: " $i;
./super_netperf 32 -H ::1 -l 60 -- -m $i -M $i;
done
done
Average of 5 run:
$i 10^6 bps
size base jhash2 hsiphash siphash
64 20735.80 20419.96 (98.48) 20335.60 (98.07) 20404.08 (98.40)
128 40450.40 40167.66 (99.30) 39957.32 (98.78) 40222.06 (99.44)
256 73740.84 74219.26 (100.65) 73625.76 (99.84) 74081.52 (100.46)
512 142075.60 142461.80 (100.27) 141237.00 (99.41) 141789.60 (99.80)
1024 254391.00 253553.20 (99.67) 252751.00 (99.36) 253718.00 (99.74)
2048 421221.20 421175.60 (99.99) 420142.80 (99.74) 418189.20 (99.28)
4096 599158.20 597958.20 (99.80) 594472.20 (99.22) 598591.00 (99.91)
Also, in the kernel with hsiphash/siphash, there is call op as
hsiphash_4u32() and siphash_2u64() are exposed to modules, but
both functions did not have jumps.
hsiphash:
$ gdb -batch -ex 'file vmlinux' -ex 'disassemble inet6_ehashfn' | grep hsiphash
0xffffffff81de5bcc <+92>: call 0xffffffff81f637e0 <hsiphash_4u32>
$ gdb -batch -ex 'file vmlinux' -ex 'disassemble hsiphash_4u32' | grep j
0xffffffff81f63970 <+400>: jmp 0xffffffff81f85ec0 <__x86_return_thunk>
siphash:
$ gdb -batch -ex 'file vmlinux' -ex 'disassemble inet6_ehashfn' | grep siphash
0xffffffff81de5bc4 <+84>: call 0xffffffff81f625e0 <siphash_2u64>
$ gdb -batch -ex 'file vmlinux' -ex 'disassemble siphash_2u64' | grep j
0xffffffff81f62837 <+599>: jmp 0xffffffff81f85ec0 <__x86_return_thunk>
All of the data above are uploaded here.
https://github.com/q2ven/inet6_ehashfn
Thanks!
Powered by blists - more mailing lists