linux-kernel - RE: [PATCH 11/14] llvm: kCFI pointer stuff

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: <PH7PR11MB75722452CAEDFFE4C80FC05CBB542@PH7PR11MB7572.namprd11.prod.outlook.com>
Date: Wed, 30 Oct 2024 20:07:59 +0000
From: "Constable, Scott D" <scott.d.constable@...el.com>
To: Peter Zijlstra <peterz@...radead.org>, "x86@...nel.org" <x86@...nel.org>
CC: "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>, "Milburn,
 Alyssa" <alyssa.milburn@...el.com>, "joao@...rdrivepizza.com"
	<joao@...rdrivepizza.com>, "andrew.cooper3@...rix.com"
	<andrew.cooper3@...rix.com>, "jpoimboe@...nel.org" <jpoimboe@...nel.org>,
	"jose.marchesi@...cle.com" <jose.marchesi@...cle.com>, "hjl.tools@...il.com"
	<hjl.tools@...il.com>, "ndesaulniers@...gle.com" <ndesaulniers@...gle.com>,
	"samitolvanen@...gle.com" <samitolvanen@...gle.com>, "nathan@...nel.org"
	<nathan@...nel.org>, "ojeda@...nel.org" <ojeda@...nel.org>, "kees@...nel.org"
	<kees@...nel.org>, "alexei.starovoitov@...il.com"
	<alexei.starovoitov@...il.com>
Subject: RE: [PATCH 11/14] llvm: kCFI pointer stuff

> > Quick hack to extend the Clang-kCFI function meta-data (u32 hash) with a u8 bitmask of pointer arguments. This should really be under a new compiler flag, dependent on both x86_64 and kCFI.
> > 
> > Per the comment, the bitmask represents the register based arguments as the first 6 bits and bit 6 is used to cover all stack based arguments. The high bit is used for invalid values.
> > 
> > The purpose is to put a store dependency on the set registers, thereby blocking speculation paths that would otherwise expoit their value.
> 
> Given the ongoing discussion on [PATCH 13/14] where there is a growing consensus that all arguments (not just pointers) should be poisoned after a misprediction, a different encoding scheme would be needed. I believe there are 8 possibilities, which correspond to the function's arity:
> 
> 0: Function takes 0 args
> 1: Function takes 1 arg
> 2: Function takes 2 args
> 3: Function takes 3 args
> 4: Function takes 4 args
> 5: Function takes 5 args
> 6: Function takes 6 args
> 7: Function takes >6 args
>
> These possibilities can be encoded with 3 bits. I suspect that it might actually be beneficial to steal 3 bits from the u32 kCFI hash (either by using a smaller 29-bit hash or by truncating the 32-bit hash down to 29 bits). This scheme would arguably strengthen both kCFI and FineIBT by partitioning CFI edges such that a j-arity function cannot call a k-arity function unless j=k (or unless j>6 and k>6); the current 32-bit kCFI hash does not prevent, for example, a 2-arity fptr from calling a 3-arity target if the kCFI hashes collide. The disadvantage of the 29-bit hash is that it would increase the probability of collisions within each arity, but on the other hand the total number of functions of each given arity is much smaller than the total number of functions of all arities.

I have done some additional analysis on my Noble kernel, which suggests that the proposed 29-bit hash with 3-bit arity will only be more secure than the existing 32-bit hash. Consider: My kernel has 141,617 total indirect call targets, with 10,903 unique function types. With a 32-bit kCFI hash, the expected number of collisions is 2^-32 * (10903 C 2) = 0.01383765. Then I scanned the kernel to identify the number of unique function types for each arity, and computed the corresponding expected number of collisions within each arity, and assuming a 29-bit hash:

# Args	total targets	unique types	Expected collisions
0	12682	32	0.00000092
1	42981	2492	0.00578125
2	37657	3775	0.01326841
3	29436	2547	0.00603931
4	12343	1169	0.00127162
5	4137	519	0.00025038
6	1700	221	0.00004528
more	681	148	0.00002026

(Sorry if the formatting became weird after copying from Excel)

Hence, even the arity (2) with the largest number of unique function types (3775) has a lower expected value for 29-bit collisions (0.01326841) than the expected value for 32-bit collisions (0.01383765).

Regards,

Scott Constable