linux-kernel - Re: [PATCH] selinux: Make avc cache slot size configurable during boot

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: <CAEjxPJ41d8WcEh8QYp9E63+tCO2ukE5UWvCJ-hoXgN_Sx=P_-Q@mail.gmail.com>
Date: Mon, 22 Sep 2025 08:29:30 -0400
From: Stephen Smalley <stephen.smalley.work@...il.com>
To: Hongru Zhang <zhanghongru06@...il.com>
Cc: linux-kernel@...r.kernel.org, omosnace@...hat.com, paul@...l-moore.com, 
	selinux@...r.kernel.org, zhanghongru@...omi.com
Subject: Re: [PATCH] selinux: Make avc cache slot size configurable during boot

On Sat, Sep 20, 2025 at 3:50 AM Hongru Zhang <zhanghongru06@...il.com> wrote:
>
> > > Implementation of Muladd:
> > > static inline u32 avc_hash(u32 ssid, u32 tsid, u16 tclass)
> > > {
> > >         return (ssid * 0x9E3779B9 + tsid * 0x85EBCA77 + tclass * 0xC2B2AE35) & (avc_cache_slots - 1);
> > > }
> >
> > Can you cite the source of this hash function? Is it public domain or
> > otherwise GPLv2-compatible?
>
> Based on my input, the AI proposed this algorithm and provided an explanation
> for why it fits. The AI also stated that using these constants does not cause
> GPLv2 license compatibility issues. If needed, I'll check with the company's
> legal department.
>
> Hash constant explaination:
> * 0x9E3779B9 (2654435769)
>         * Origin: Golden ratio phi = (square(5) - 1) / 2 ~= 0.6180339887...
>         * Calculation: 2^32 * phi ~= 2654435769 = 0x9E3779B9
>         * Properties:
>                 * This is the classic constant for Knuth's multiplicative hashing
>                 * Excellent bit diffusion characteristics
>                 * Coprime with powers of 2, ensuring uniform distribution
> * 0x85EBCA77 (2246822519)
>         * Origin: Popular quality constant used in modern hash algorithms like MurmurHash
>         * Properties:
>                 * Contains good alternating patterns of 1s and 0s in binary representation
>                 * Shows excellent difference from other constants in bitwise perspective
>                 * Tested and verified for superior avalanche effect
> * 0xC2B2AE35 (3266489917)
>         * Origin: Also from modern hash algorithms (e.g., MurmurHash3)
>         * Properties:
>                 * Large prime-like properties
>                 * Complex distribution of 1s in binary representation
>                 * Complementary to the first two constants
>
> Advantages of this design:
> * Minimized collisions: Different inputs won't produce similar contributions
> * Bit diffusion: Each constant effectively scrambles input bits
> * Mathematical guarantee: These constants are theoretically analyzed and empirically validated
> * Complementarity: Three constants complement each other at the binary level

Given that the constants are from well known, public sources (which
you should document in the patch description and possibly as comments
in the code) and the combining function is trivial, I assume this is
fine to use, but at the end of the day, it is Paul's call. I would
recommend #define's for each constant with its source noted as a
comment.