[PATCH v2 0/3] keys: fix keyring assoc-array out-of-bounds read and index inconsistency

[PATCH v2 0/3] keys: fix keyring assoc-array out-of-bounds read and index inconsistency

[Michael Bommarito]

An unprivileged keyring whose keys collide through the description-chunk
path can drive assoc_array node splitting into an out-of-bounds slot write.
Patch 1 stops the out-of-bounds read in keyring_get_key_chunk(); patch 2
makes the chunk byte order agree with keyring_diff_objects(); patch 3 fixes
the shortcut-walk trim so the walk cannot be steered down the wrong
descendant.

v2 changes (patch 3 only; patches 1 and 2 are unchanged):
As sashiko pointed out, the v1 patch-3 guard (sc_level + CHUNK >
skip_to_level) fixed the word-aligned leak but wrongly fired for an
unaligned first word whose skip_to_level sits on the next chunk
boundary: shift = skip_to_level & CHUNK_MASK is then 0 and the trim clears
the whole dissimilarity word, making a differing shortcut compare equal.  v2
keys the trim on the end of the chunk that contains sc_level,
round_down(sc_level, CHUNK) + CHUNK, which matches a brute-force oracle over
every sc_level/skip_to_level pair; the original round_up guard and the v1
guard each disagree with the oracle in one regime.

v1: https://lore.kernel.org/keyrings/20260712014500.480410-1-michael.bommarito@gmail.com/

Michael Bommarito (3):
  keys: fix out-of-bounds read in keyring_get_key_chunk()
  keys: make keyring key-chunk byte order agree with keyring_diff_objects()
  assoc_array: trim the final shortcut word using the current chunk end

 lib/assoc_array.c       |  3 ++-
 security/keys/keyring.c | 15 ++++++++-------
 2 files changed, 10 insertions(+), 8 deletions(-)

-- 
2.53.0

[PATCH v2 1/3] keys: fix out-of-bounds read in keyring_get_key_chunk()

[Michael Bommarito]

For description-level chunks keyring_get_key_chunk() advances the read
pointer by level * sizeof(long) past the inline prefix but only
bounds-checks the prefix, so a long enough key description is read past
its kmemdup(desc, desc_len + 1) allocation.  Compute the full byte
offset and bounds-check the description against it before reading.

The walk only reaches a description-level chunk when two keys collide
through the hash, x, type and domain_tag chunks, so this is reached from
an unprivileged add_key(2) with a crafted pair of same-type keys whose
index hashes collide; KASAN reports a slab-out-of-bounds read.

Fixes: f771fde82051 ("keys: Simplify key description management")
Assisted-by: Claude:claude-opus-4-8
Signed-off-by: Michael Bommarito <michael.bommarito@gmail.com>
---
 security/keys/keyring.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

KASAN, x86_64: add_key(2) of a crafted hash-colliding "user"-key pair
(~63-byte descriptions) reports

  BUG: KASAN: slab-out-of-bounds in keyring_get_key_chunk
  keyring_get_key_chunk <- assoc_array_insert <- __key_link_begin
    <- __do_sys_add_key

reading one byte past the description allocation; the same trigger is
KASAN-clean with this patch.  On a kernel built without init-on-alloc,
reading the colliding keyring back with KEYCTL_READ returns
uninitialized slab until patches 2 and 3 are applied too.  Trigger
available off-list.

diff --git a/security/keys/keyring.c b/security/keys/keyring.c
index 7a2ee0ded7c93..1739373172ad5 100644
--- a/security/keys/keyring.c
+++ b/security/keys/keyring.c
@@ -270,7 +270,7 @@ static unsigned long keyring_get_key_chunk(const void *data, int level)
 	const struct keyring_index_key *index_key = data;
 	unsigned long chunk = 0;
 	const u8 *d;
-	int desc_len = index_key->desc_len, n = sizeof(chunk);
+	int desc_len = index_key->desc_len, n = sizeof(chunk), offset;
 
 	level /= ASSOC_ARRAY_KEY_CHUNK_SIZE;
 	switch (level) {
@@ -284,12 +284,12 @@ static unsigned long keyring_get_key_chunk(const void *data, int level)
 		return (unsigned long)index_key->domain_tag;
 	default:
 		level -= 4;
-		if (desc_len <= sizeof(index_key->desc))
+		offset = sizeof(index_key->desc) + level * sizeof(long);
+		if (desc_len <= offset)
 			return 0;
 
-		d = index_key->description + sizeof(index_key->desc);
-		d += level * sizeof(long);
-		desc_len -= sizeof(index_key->desc);
+		d = index_key->description + offset;
+		desc_len -= offset;
 		if (desc_len > n)
 			desc_len = n;
 		do {
-- 
2.53.0

[PATCH v2 2/3] keys: make keyring key-chunk byte order agree with keyring_diff_objects()

[Michael Bommarito]

keyring_get_key_chunk() loads description bytes into the index chunk low
address first, while keyring_diff_objects() numbers the first differing
bit from the low end and folds the absolute byte index into the level
without removing the inline-prefix offset the level already carries.
The two disagree on byte order and bit position, so the array can be
told two keys first differ at a bit that does not differ in the chunk
the walker uses, letting crafted descriptions collide into one node.

Load the chunk in the order keyring_diff_objects() assumes and drop the
inline-prefix length when folding the byte index into the level.  This
only changes the in-memory ordering used to place keys within a keyring;
add, search and read of non-colliding keys are unaffected.

Fixes: f771fde82051 ("keys: Simplify key description management")
Assisted-by: Claude:claude-opus-4-8
Signed-off-by: Michael Bommarito <michael.bommarito@gmail.com>
---
 security/keys/keyring.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/security/keys/keyring.c b/security/keys/keyring.c
index 1739373172ad5..e7066893e6ffc 100644
--- a/security/keys/keyring.c
+++ b/security/keys/keyring.c
@@ -292,9 +292,10 @@ static unsigned long keyring_get_key_chunk(const void *data, int level)
 		desc_len -= offset;
 		if (desc_len > n)
 			desc_len = n;
+		d += desc_len;
 		do {
 			chunk <<= 8;
-			chunk |= *d++;
+			chunk |= *--d;
 		} while (--desc_len > 0);
 		return chunk;
 	}
@@ -375,7 +376,7 @@ static int keyring_diff_objects(const void *object, const void *data)
 	return -1;
 
 differ_plus_i:
-	level += i;
+	level += i - (int)sizeof(a->desc);
 differ:
 	i = level * 8 + __ffs(seg_a ^ seg_b);
 	return i;
-- 
2.53.0

[PATCH v2 3/3] assoc_array: trim the final shortcut word using the current chunk end

[Michael Bommarito]

assoc_array_walk() masks off the bits past shortcut->skip_to_level in the
word that contains skip_to_level, gated on
round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > skip_to_level.

That guard is wrong in two opposite ways:

 - When sc_level is word-aligned (every word after the first) round_up()
   is a no-op, so the guard is sc_level > skip_to_level and never fires for
   the word that holds skip_to_level.  A shortcut that spans more than one
   word and ends in the middle of its last word leaves that word untrimmed,
   and its stale high bits leak into the dissimilarity word and can steer
   the walk down the wrong descendant.

 - When sc_level is unaligned (the first word) and skip_to_level sits on
   the next chunk boundary, sc_level + CHUNK would exceed skip_to_level and
   fire the trim with shift = skip_to_level & CHUNK_MASK == 0, which clears
   the whole dissimilarity word and makes a differing shortcut compare
   equal.

Use the end of the chunk that contains sc_level instead:

	skip_to_level < round_down(sc_level, CHUNK) + CHUNK

For an aligned sc_level whose word holds skip_to_level this now fires (the
first bug); for an unaligned sc_level with skip_to_level on the following
boundary it does not, so shift is never 0 when the branch runs and the trim
never clears the whole word.

Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
Assisted-by: Claude:claude-opus-4-8
Signed-off-by: Michael Bommarito <michael.bommarito@gmail.com>
---
 lib/assoc_array.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/assoc_array.c b/lib/assoc_array.c
index bcc6e0a013eb8..b6c9723e12ced 100644
--- a/lib/assoc_array.c
+++ b/lib/assoc_array.c
@@ -255,7 +255,8 @@ assoc_array_walk(const struct assoc_array *array,
 		sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT];
 		dissimilarity = segments ^ sc_segments;
 
-		if (round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > shortcut->skip_to_level) {
+		if (shortcut->skip_to_level < round_down(sc_level,
+				ASSOC_ARRAY_KEY_CHUNK_SIZE) + ASSOC_ARRAY_KEY_CHUNK_SIZE) {
 			/* Trim segments that are beyond the shortcut */
 			int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK;
 			dissimilarity &= ~(ULONG_MAX << shift);
-- 
2.53.0

Re: [PATCH v2 1/3] keys: fix out-of-bounds read in keyring_get_key_chunk()

[Jarkko Sakkinen]

On Tue, Jul 14, 2026 at 07:54:49AM -0400, Michael Bommarito wrote:
> For description-level chunks keyring_get_key_chunk() advances the read
> pointer by level * sizeof(long) past the inline prefix but only
> bounds-checks the prefix, so a long enough key description is read past
> its kmemdup(desc, desc_len + 1) allocation.  Compute the full byte
> offset and bounds-check the description against it before reading.
> 
> The walk only reaches a description-level chunk when two keys collide
> through the hash, x, type and domain_tag chunks, so this is reached from
> an unprivileged add_key(2) with a crafted pair of same-type keys whose
> index hashes collide; KASAN reports a slab-out-of-bounds read.
> 
> Fixes: f771fde82051 ("keys: Simplify key description management")
> Assisted-by: Claude:claude-opus-4-8
> Signed-off-by: Michael Bommarito <michael.bommarito@gmail.com>
> ---
>  security/keys/keyring.c | 10 +++++-----
>  1 file changed, 5 insertions(+), 5 deletions(-)
> 
> KASAN, x86_64: add_key(2) of a crafted hash-colliding "user"-key pair
> (~63-byte descriptions) reports
> 
>   BUG: KASAN: slab-out-of-bounds in keyring_get_key_chunk
>   keyring_get_key_chunk <- assoc_array_insert <- __key_link_begin
>     <- __do_sys_add_key
> 
> reading one byte past the description allocation; the same trigger is
> KASAN-clean with this patch.  On a kernel built without init-on-alloc,
> reading the colliding keyring back with KEYCTL_READ returns
> uninitialized slab until patches 2 and 3 are applied too.  Trigger
> available off-list.
> 
> diff --git a/security/keys/keyring.c b/security/keys/keyring.c
> index 7a2ee0ded7c93..1739373172ad5 100644
> --- a/security/keys/keyring.c
> +++ b/security/keys/keyring.c
> @@ -270,7 +270,7 @@ static unsigned long keyring_get_key_chunk(const void *data, int level)
>  	const struct keyring_index_key *index_key = data;
>  	unsigned long chunk = 0;
>  	const u8 *d;
> -	int desc_len = index_key->desc_len, n = sizeof(chunk);
> +	int desc_len = index_key->desc_len, n = sizeof(chunk), offset;
>  
>  	level /= ASSOC_ARRAY_KEY_CHUNK_SIZE;
>  	switch (level) {
> @@ -284,12 +284,12 @@ static unsigned long keyring_get_key_chunk(const void *data, int level)
>  		return (unsigned long)index_key->domain_tag;
>  	default:
>  		level -= 4;
> -		if (desc_len <= sizeof(index_key->desc))
> +		offset = sizeof(index_key->desc) + level * sizeof(long);
> +		if (desc_len <= offset)
>  			return 0;
>  
> -		d = index_key->description + sizeof(index_key->desc);
> -		d += level * sizeof(long);
> -		desc_len -= sizeof(index_key->desc);
> +		d = index_key->description + offset;
> +		desc_len -= offset;
>  		if (desc_len > n)
>  			desc_len = n;
>  		do {
> -- 
> 2.53.0
> 

Same feedback as before.

BR, Jarkko

Re: [PATCH v2 2/3] keys: make keyring key-chunk byte order agree with keyring_diff_objects()

[Jarkko Sakkinen]

On Tue, Jul 14, 2026 at 07:54:50AM -0400, Michael Bommarito wrote:
> keyring_get_key_chunk() loads description bytes into the index chunk low
> address first, while keyring_diff_objects() numbers the first differing
> bit from the low end and folds the absolute byte index into the level
> without removing the inline-prefix offset the level already carries.
> The two disagree on byte order and bit position, so the array can be
> told two keys first differ at a bit that does not differ in the chunk
> the walker uses, letting crafted descriptions collide into one node.
> 
> Load the chunk in the order keyring_diff_objects() assumes and drop the
> inline-prefix length when folding the byte index into the level.  This
> only changes the in-memory ordering used to place keys within a keyring;
> add, search and read of non-colliding keys are unaffected.
> 
> Fixes: f771fde82051 ("keys: Simplify key description management")
> Assisted-by: Claude:claude-opus-4-8
> Signed-off-by: Michael Bommarito <michael.bommarito@gmail.com>
> ---
>  security/keys/keyring.c | 5 +++--
>  1 file changed, 3 insertions(+), 2 deletions(-)
> 
> diff --git a/security/keys/keyring.c b/security/keys/keyring.c
> index 1739373172ad5..e7066893e6ffc 100644
> --- a/security/keys/keyring.c
> +++ b/security/keys/keyring.c
> @@ -292,9 +292,10 @@ static unsigned long keyring_get_key_chunk(const void *data, int level)
>  		desc_len -= offset;
>  		if (desc_len > n)
>  			desc_len = n;
> +		d += desc_len;
>  		do {
>  			chunk <<= 8;
> -			chunk |= *d++;
> +			chunk |= *--d;
>  		} while (--desc_len > 0);
>  		return chunk;
>  	}
> @@ -375,7 +376,7 @@ static int keyring_diff_objects(const void *object, const void *data)
>  	return -1;
>  
>  differ_plus_i:
> -	level += i;
> +	level += i - (int)sizeof(a->desc);
>  differ:
>  	i = level * 8 + __ffs(seg_a ^ seg_b);
>  	return i;
> -- 
> 2.53.0
> 


Reviewed-by: Jarkko Sakkinen <jarkko@kernel.org>

BR, Jarkko

Re: [PATCH v2 3/3] assoc_array: trim the final shortcut word using the current chunk end

[Jarkko Sakkinen]

On Tue, Jul 14, 2026 at 07:54:51AM -0400, Michael Bommarito wrote:
> assoc_array_walk() masks off the bits past shortcut->skip_to_level in the
> word that contains skip_to_level, gated on
> round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > skip_to_level.
> 
> That guard is wrong in two opposite ways:
> 
>  - When sc_level is word-aligned (every word after the first) round_up()
>    is a no-op, so the guard is sc_level > skip_to_level and never fires for
>    the word that holds skip_to_level.  A shortcut that spans more than one
>    word and ends in the middle of its last word leaves that word untrimmed,
>    and its stale high bits leak into the dissimilarity word and can steer
>    the walk down the wrong descendant.
> 
>  - When sc_level is unaligned (the first word) and skip_to_level sits on
>    the next chunk boundary, sc_level + CHUNK would exceed skip_to_level and
>    fire the trim with shift = skip_to_level & CHUNK_MASK == 0, which clears
>    the whole dissimilarity word and makes a differing shortcut compare
>    equal.
> 
> Use the end of the chunk that contains sc_level instead:
> 
> 	skip_to_level < round_down(sc_level, CHUNK) + CHUNK
> 
> For an aligned sc_level whose word holds skip_to_level this now fires (the
> first bug); for an unaligned sc_level with skip_to_level on the following
> boundary it does not, so shift is never 0 when the branch runs and the trim
> never clears the whole word.
> 
> Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
> Assisted-by: Claude:claude-opus-4-8
> Signed-off-by: Michael Bommarito <michael.bommarito@gmail.com>
> ---
>  lib/assoc_array.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/assoc_array.c b/lib/assoc_array.c
> index bcc6e0a013eb8..b6c9723e12ced 100644
> --- a/lib/assoc_array.c
> +++ b/lib/assoc_array.c
> @@ -255,7 +255,8 @@ assoc_array_walk(const struct assoc_array *array,
>  		sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT];
>  		dissimilarity = segments ^ sc_segments;
>  
> -		if (round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > shortcut->skip_to_level) {
> +		if (shortcut->skip_to_level < round_down(sc_level,
> +				ASSOC_ARRAY_KEY_CHUNK_SIZE) + ASSOC_ARRAY_KEY_CHUNK_SIZE) {
>  			/* Trim segments that are beyond the shortcut */
>  			int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK;
>  			dissimilarity &= ~(ULONG_MAX << shift);
> -- 
> 2.53.0
> 

Reviewed-by: Jarkko Sakkinen <jarkko@kernel.org>

BR, Jarkko

Re: [PATCH v2 3/3] assoc_array: trim the final shortcut word using the current chunk end

[Jarkko Sakkinen]

On Sat, Jul 18, 2026 at 09:38:01PM +0300, Jarkko Sakkinen wrote:
> On Tue, Jul 14, 2026 at 07:54:51AM -0400, Michael Bommarito wrote:
> > assoc_array_walk() masks off the bits past shortcut->skip_to_level in the
> > word that contains skip_to_level, gated on
> > round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > skip_to_level.
> > 
> > That guard is wrong in two opposite ways:
> > 
> >  - When sc_level is word-aligned (every word after the first) round_up()
> >    is a no-op, so the guard is sc_level > skip_to_level and never fires for
> >    the word that holds skip_to_level.  A shortcut that spans more than one
> >    word and ends in the middle of its last word leaves that word untrimmed,
> >    and its stale high bits leak into the dissimilarity word and can steer
> >    the walk down the wrong descendant.
> > 
> >  - When sc_level is unaligned (the first word) and skip_to_level sits on
> >    the next chunk boundary, sc_level + CHUNK would exceed skip_to_level and
> >    fire the trim with shift = skip_to_level & CHUNK_MASK == 0, which clears
> >    the whole dissimilarity word and makes a differing shortcut compare
> >    equal.
> > 
> > Use the end of the chunk that contains sc_level instead:
> > 
> > 	skip_to_level < round_down(sc_level, CHUNK) + CHUNK
> > 
> > For an aligned sc_level whose word holds skip_to_level this now fires (the
> > first bug); for an unaligned sc_level with skip_to_level on the following
> > boundary it does not, so shift is never 0 when the branch runs and the trim
> > never clears the whole word.
> > 
> > Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
> > Assisted-by: Claude:claude-opus-4-8
> > Signed-off-by: Michael Bommarito <michael.bommarito@gmail.com>
> > ---
> >  lib/assoc_array.c | 3 ++-
> >  1 file changed, 2 insertions(+), 1 deletion(-)
> > 
> > diff --git a/lib/assoc_array.c b/lib/assoc_array.c
> > index bcc6e0a013eb8..b6c9723e12ced 100644
> > --- a/lib/assoc_array.c
> > +++ b/lib/assoc_array.c
> > @@ -255,7 +255,8 @@ assoc_array_walk(const struct assoc_array *array,
> >  		sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT];
> >  		dissimilarity = segments ^ sc_segments;
> >  
> > -		if (round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > shortcut->skip_to_level) {
> > +		if (shortcut->skip_to_level < round_down(sc_level,
> > +				ASSOC_ARRAY_KEY_CHUNK_SIZE) + ASSOC_ARRAY_KEY_CHUNK_SIZE) {
> >  			/* Trim segments that are beyond the shortcut */
> >  			int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK;
> >  			dissimilarity &= ~(ULONG_MAX << shift);
> > -- 
> > 2.53.0
> > 
> 
> Reviewed-by: Jarkko Sakkinen <jarkko@kernel.org>
> 
> BR, Jarkko

Were you able to reproduce this with basic command-line tools? The
patches are verifiable by reading the code but asking this just in
case if you had a snippet at hand (not interested on complex
reproducers).

BR, Jarkko

Re: [PATCH v2 3/3] assoc_array: trim the final shortcut word using the current chunk end

[Michael Bommarito]

On Sat, Jul 18, 2026 at 2:46 PM Jarkko Sakkinen <jarkko@kernel.org> wrote:
> Were you able to reproduce this with basic command-line tools? The
> patches are verifiable by reading the code but asking this just in
> case if you had a snippet at hand (not interested on complex
> reproducers).

No, it's a little tricky to hit, definitely not just a few keyctl
commands.  I can send offlist if you'd like but it requires at least
~50 or so lines of C/python

PS - I'll send v3 with the nit fixed and carry your tags today/tomorrow

Thanks,
Mike

Re: [PATCH v2 3/3] assoc_array: trim the final shortcut word using the current chunk end

[Jarkko Sakkinen]

On Sat, Jul 18, 2026 at 04:35:17PM -0400, Michael Bommarito wrote:
> On Sat, Jul 18, 2026 at 2:46 PM Jarkko Sakkinen <jarkko@kernel.org> wrote:
> > Were you able to reproduce this with basic command-line tools? The
> > patches are verifiable by reading the code but asking this just in
> > case if you had a snippet at hand (not interested on complex
> > reproducers).
> 
> No, it's a little tricky to hit, definitely not just a few keyctl
> commands.  I can send offlist if you'd like but it requires at least
> ~50 or so lines of C/python

Hey, please do, I'm happy to at least try to test this.

> 
> PS - I'll send v3 with the nit fixed and carry your tags today/tomorrow
> 
> Thanks,
> Mike

BR, Jarkko