netdev - tc: u32: Wrong sample hash calculation

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-next>] [day] [month] [year] [list]

Message-ID: <20210118112919.GC3158@orbyte.nwl.cc>
Date:   Mon, 18 Jan 2021 12:29:19 +0100
From:   Phil Sutter <phil@....cc>
To:     Jamal Hadi Salim <jhs@...atatu.com>,
        Stephen Hemminger <stephen@...workplumber.org>
Cc:     netdev@...r.kernel.org, Cong Wang <xiyou.wangcong@...il.com>,
        Jiri Pirko <jiri@...nulli.us>,
        Russell Stuart <russell-lartc@...art.id.au>
Subject: tc: u32: Wrong sample hash calculation

Hi!

Playing with u32 filter's hash table I noticed it is not possible to use
'sample' option with keys larger than 8bits to calculate the hash
bucket. Turns out key hashing in kernel and iproute2 differ:

* net/sched/cls_u32.c (kernel) basically does:

hash = ntohl(key & mask);
hash >>= ffs(ntohl(mask)) - 1;
hash &= 0xff;
hash %= divisor;

* while tc/f_u32.c (iproute2) does:

hash = key & mask;
hash ^= hash >> 16;
hash ^= hash >> 8;
hash %= divisor;

In iproute2, the code changed in 2006 with commit 267480f55383c
("Backout the 2.4 utsname hash patch."), here's the relevant diff:

  hash = sel2.sel.keys[0].val&sel2.sel.keys[0].mask;
- uname(&utsname);
- if (strncmp(utsname.release, "2.4.", 4) == 0) {
-         hash ^= hash>>16;
-         hash ^= hash>>8;
- }
- else {
-         __u32 mask = sel2.sel.keys[0].mask;
-         while (mask && !(mask & 1)) {
-                 mask >>= 1;
-                 hash >>= 1;
-         }
-         hash &= 0xFF;
- }
+ hash ^= hash>>16;
+ hash ^= hash>>8;
  htid = ((hash%divisor)<<12)|(htid&0xFFF00000);

The old code would work if key and mask weren't in network byteorder. I
guess that also changed since then.

I would simply send a patch to fix iproute2, but I don't like the
kernel's hash "folding" as it ignores any bits beyond the first eight.
So I would prefer to "fix" the kernel instead but would like to hear
your opinions as that change has a much larger scope than just
iproute2's 'sample' option.

Thanks, Phil