[PATCH] assoc_array: Preserve full words when splitting shortcuts

[PATCH] assoc_array: Preserve full words when splitting shortcuts

[Kyle Zeng]

assoc_array_insert_mid_shortcut() copies enough index-key words for the
new pre-shortcut, then masks off the unused bits in its last word.  If
diff is word-aligned, the shift is zero and the mask clears that entire
word, even though all of it belongs to the required prefix.  The new
shortcut no longer matches the objects behind it, so lookups can fail
for both the existing objects and the new one.

For example, inserting a user key with a different description length
into a keyring containing enough full-hash collisions can split a
shortcut at bit 64 and erase its hash word.  The resulting search
failure can also expose the pointer-dependent keyring hash as a KASLR
oracle.

Only trim the last word when diff ends inside it.  This mirrors
commit bb2ba2d75a2d ("assoc_array: Fix shortcut creation"), which fixed
the terminal-node case, and leaves non-word-aligned splits unchanged.

Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
Cc: stable@vger.kernel.org
Assisted-by: Codex:gpt-6-astra
Signed-off-by: Kyle Zeng <kylebot@openai.com>
---
 lib/assoc_array.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/lib/assoc_array.c b/lib/assoc_array.c
index b6c9723e12ce..20ef69e03780 100644
--- a/lib/assoc_array.c
+++ b/lib/assoc_array.c
@@ -865,9 +865,11 @@ static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
 		memcpy(new_s0->index_key, shortcut->index_key,
 		       flex_array_size(new_s0, index_key, keylen));
 
-		blank = ULONG_MAX << (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
-		pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, diff, blank);
-		new_s0->index_key[keylen - 1] &= ~blank;
+		if (diff & ASSOC_ARRAY_KEY_CHUNK_MASK) {
+			blank = ULONG_MAX << (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
+			pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, diff, blank);
+			new_s0->index_key[keylen - 1] &= ~blank;
+		}
 	} else {
 		pr_devel("no pre-shortcut\n");
 		edit->set[0].to = assoc_array_node_to_ptr(new_n0);
-- 
2.53.0

Re: [PATCH] assoc_array: Preserve full words when splitting shortcuts

[Andrew Morton]

On Tue,  6 Oct 2026 15:06:38 -0700 Kyle Zeng <kylebot@openai.com> wrote:

> assoc_array_insert_mid_shortcut() copies enough index-key words for the
> new pre-shortcut, then masks off the unused bits in its last word.  If
> diff is word-aligned, the shift is zero and the mask clears that entire
> word, even though all of it belongs to the required prefix.  The new
> shortcut no longer matches the objects behind it, so lookups can fail
> for both the existing objects and the new one.
> 
> For example, inserting a user key with a different description length
> into a keyring containing enough full-hash collisions can split a
> shortcut at bit 64 and erase its hash word.  The resulting search
> failure can also expose the pointer-dependent keyring hash as a KASLR
> oracle.
> 
> Only trim the last word when diff ends inside it.  This mirrors
> commit bb2ba2d75a2d ("assoc_array: Fix shortcut creation"), which fixed
> the terminal-node case, and leaves non-word-aligned splits unchanged.

Thanks.

When fixing a bug please clearly describe the userspace-visible runtime
effects of that bug.  Including how-to-hit-it, reproducer, user reports, etc.

> Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
> Cc: stable@vger.kernel.org

Especially when proposing a backport. 
Documentation/process/stable-kernel-rules.rst provides guidelines.

> Assisted-by: Codex:gpt-6-astra
> Signed-off-by: Kyle Zeng <kylebot@openai.com>
> ---
>  lib/assoc_array.c | 8 +++++---

get_maintainer coverage is poor.  Please use git-show also:
hp2:/usr/src/mm> git show -s --format="%an <%ae> - %s" 3cb989501c26
David Howells <dhowells@redhat.com> - Add a generic associative array implementation.

Also, as this affects keyrings, grep -i keyrings MAINTAINERS shows the
mailing list.

Re: [PATCH] assoc_array: Preserve full words when splitting shortcuts

[Kyle Zeng]

On Tue, Oct 06, 2026 at 03:25:08PM -0700, Andrew Morton wrote:
> On Tue,  6 Oct 2026 15:06:38 -0700 Kyle Zeng <kylebot@openai.com> wrote:
> 
> > assoc_array_insert_mid_shortcut() copies enough index-key words for the
> > new pre-shortcut, then masks off the unused bits in its last word.  If
> > diff is word-aligned, the shift is zero and the mask clears that entire
> > word, even though all of it belongs to the required prefix.  The new
> > shortcut no longer matches the objects behind it, so lookups can fail
> > for both the existing objects and the new one.
> > 
> > For example, inserting a user key with a different description length
> > into a keyring containing enough full-hash collisions can split a
> > shortcut at bit 64 and erase its hash word.  The resulting search
> > failure can also expose the pointer-dependent keyring hash as a KASLR
> > oracle.
> > 
> > Only trim the last word when diff ends inside it.  This mirrors
> > commit bb2ba2d75a2d ("assoc_array: Fix shortcut creation"), which fixed
> > the terminal-node case, and leaves non-word-aligned splits unchanged.
> 
> Thanks.
> 
> When fixing a bug please clearly describe the userspace-visible runtime
> effects of that bug.  Including how-to-hit-it, reproducer, user reports, etc.

Hi Andrew,

Thanks for the response.
As mentioned in the commit message, a search failure can expose the
pointer-dependent keyring hash as a KASLR oracle. As a result, a local
unprivileged user can use this to leak kernel pointer and bypass KASLR.

The reproducer is not attached intentionally but can be shared through
DM.

Best,
Kyle

> 
> > Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
> > Cc: stable@vger.kernel.org
> 
> Especially when proposing a backport. 
> Documentation/process/stable-kernel-rules.rst provides guidelines.
> 
> > Assisted-by: Codex:gpt-6-astra
> > Signed-off-by: Kyle Zeng <kylebot@openai.com>
> > ---
> >  lib/assoc_array.c | 8 +++++---
> 
> get_maintainer coverage is poor.  Please use git-show also:
> hp2:/usr/src/mm> git show -s --format="%an <%ae> - %s" 3cb989501c26
> David Howells <dhowells@redhat.com> - Add a generic associative array implementation.
> 
> Also, as this affects keyrings, grep -i keyrings MAINTAINERS shows the
> mailing list.

Re: [PATCH] assoc_array: Preserve full words when splitting shortcuts

[Andrew Morton]

On Tue, 6 Oct 2026 15:33:53 -0700 Kyle Zeng <kylebot@openai.com> wrote:

> On Tue, Oct 06, 2026 at 03:25:08PM -0700, Andrew Morton wrote:
> > On Tue,  6 Oct 2026 15:06:38 -0700 Kyle Zeng <kylebot@openai.com> wrote:
> > 
> > > assoc_array_insert_mid_shortcut() copies enough index-key words for the
> > > new pre-shortcut, then masks off the unused bits in its last word.  If
> > > diff is word-aligned, the shift is zero and the mask clears that entire
> > > word, even though all of it belongs to the required prefix.  The new
> > > shortcut no longer matches the objects behind it, so lookups can fail
> > > for both the existing objects and the new one.
> > > 
> > > For example, inserting a user key with a different description length
> > > into a keyring containing enough full-hash collisions can split a
> > > shortcut at bit 64 and erase its hash word.  The resulting search
> > > failure can also expose the pointer-dependent keyring hash as a KASLR
> > > oracle.
> > > 
> > > Only trim the last word when diff ends inside it.  This mirrors
> > > commit bb2ba2d75a2d ("assoc_array: Fix shortcut creation"), which fixed
> > > the terminal-node case, and leaves non-word-aligned splits unchanged.
> > 
> > Thanks.
> > 
> > When fixing a bug please clearly describe the userspace-visible runtime
> > effects of that bug.  Including how-to-hit-it, reproducer, user reports, etc.
> 
> Hi Andrew,
> 
> Thanks for the response.
> As mentioned in the commit message, a search failure can expose the
> pointer-dependent keyring hash as a KASLR oracle. As a result, a local
> unprivileged user can use this to leak kernel pointer and bypass KASLR.

I googled it.

: In computer security and exploit development, a KASLR oracle is any
: mechanism or vulnerability that allows an attacker to reliably
: determine whether a specific virtual memory address contains valid
: kernel code or data.  
: 
: The term "oracle" comes from cryptography and computer science, meaning
: a black box that answers a specific question in this case, "Is there
: kernel memory loaded at this guessed address?" By querying this oracle
: repeatedly for different memory ranges, an attacker can pinpoint the
: exact base address of the kernel, completely neutralizing Kernel
: Address Space Layout Randomization (KASLR)

oh.  Hadn't heard that one before.

Anyway, please add those cc's and resend, thanks.