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

Message-ID: <20250920075018.631959-1-zhanghongru@xiaomi.com>
Date: Sat, 20 Sep 2025 15:50:18 +0800
From: Hongru Zhang <zhanghongru06@...il.com>
To: stephen.smalley.work@...il.com
Cc: linux-kernel@...r.kernel.org,
	omosnace@...hat.com,
	paul@...l-moore.com,
	selinux@...r.kernel.org,
	zhanghongru06@...il.com,
	zhanghongru@...omi.com
Subject: Re: [PATCH] selinux: Make avc cache slot size configurable during boot

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