Skip to contentSkip to conversation

keys: fix keyring assoc-array out-of-bounds read and index inconsistency

PATCH In review Michael Bommarito 2 participants 6 messages Jul 19 – Jul 23

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

v3 cover keys: fix keyring assoc-array out-of-bounds read and index inconsistency

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.

v3 changes (patch 1 only; patches 2 and 3 are unchanged):
Per Jarkko's review, patch 1 no longer extends the existing keyring_get_key_chunk() declaration line; the new offset is declared on its own line as unsigned int. No functional change.

Patches 2 and 3 are unchanged from v2 and carry Jarkko's Reviewed-by.

v2: https://lore.kernel.org/keyrings/[email protected]/
v1: https://lore.kernel.org/keyrings/[email protected]/

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 | 14 ++++++++------
 2 files changed, 10 insertions(+), 7 deletions(-)

base-commit: 2c7c88a412aa6d09cd04b414211b4ef8553b5309

Signature · 1 line
2.53.0
#1 lore raw

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

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
---
 security/keys/keyring.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)
security/keys/keyring.c +5 -4
index 7a2ee0ded7c93..085f7a743354c 100644
@@ -271,6 +271,7 @@ static unsigned long keyring_get_key_chunk(const void *data, int level)
 	unsigned long chunk = 0;
 	const u8 *d;
 	int desc_len = index_key->desc_len, n = sizeof(chunk);
+	unsigned int offset;
 
 	level /= ASSOC_ARRAY_KEY_CHUNK_SIZE;
 	switch (level) {
@@ -284,12 +285,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 {
Signature · 1 line
2.53.0
#2 lore raw

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

In reply to 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
---
 security/keys/keyring.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
security/keys/keyring.c +3 -2
index 085f7a743354c..15bf4af8f2821 100644
@@ -293,9 +293,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;
 	}
@@ -376,7 +377,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;
Signature · 1 line
2.53.0
#3 lore raw

PATCH v3 3/3 assoc_array: trim the final shortcut word using the current chunk end

In reply to 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
---
 lib/assoc_array.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
lib/assoc_array.c +2 -1
index bcc6e0a013eb8..b6c9723e12ced 100644
@@ -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);
Signature · 1 line
2.53.0
maintainer
#4 lore raw
In reply to Michael Bommarito
Quoted 23 lines · 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.

v3 changes (patch 1 only; patches 2 and 3 are unchanged):
Per Jarkko's review, patch 1 no longer extends the existing keyring_get_key_chunk() declaration line; the new offset is declared on its own line as unsigned int. No functional change.

Patches 2 and 3 are unchanged from v2 and carry Jarkko's Reviewed-by.

v2: https://lore.kernel.org/keyrings/[email protected]/
v1: https://lore.kernel.org/keyrings/[email protected]/

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

Quoted 9 lines
 lib/assoc_array.c       |  3 ++-
 security/keys/keyring.c | 14 ++++++++------
 2 files changed, 10 insertions(+), 7 deletions(-)

base-commit: 2c7c88a412aa6d09cd04b414211b4ef8553b5309

Signature · 1 line
2.53.0

I'm setting up the testing environment now and hopefully have final feedback within let's say "hours" (i.e. I'll do the job, and it takes what it takes).

BR, Jarkko

maintainer Reviewed-by Tested-by
#5 lore raw
Quoted 29 lines · Jarkko Sakkinen
Quoted 28 lines · 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.

v3 changes (patch 1 only; patches 2 and 3 are unchanged):
Per Jarkko's review, patch 1 no longer extends the existing keyring_get_key_chunk() declaration line; the new offset is declared on its own line as unsigned int. No functional change.

Patches 2 and 3 are unchanged from v2 and carry Jarkko's Reviewed-by.

v2: https://lore.kernel.org/keyrings/[email protected]/
v1: https://lore.kernel.org/keyrings/[email protected]/

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 | 14 ++++++++------
 2 files changed, 10 insertions(+), 7 deletions(-)
Quoted 8 lines
Quoted 4 lines

base-commit: 2c7c88a412aa6d09cd04b414211b4ef8553b5309

Signature · 1 line
2.53.0

I'm setting up the testing environment now and hopefully have final feedback within let's say "hours" (i.e. I'll do the job, and it takes what it takes).

Good news. I got it tested. I'll push and mirror the patches to linux-next. Once they show up there, I'll send a PR to Linus.

                                               # reproducer.

Really good work IMHO and also great example of legit use of AI assisted patches in my books. Thank you.

BR, Jarkko