Skip to contentSkip to conversation

befs: validate b+tree node geometry to prevent out-of-bounds reads

PATCH New Hem Parekh 1 participant 2 messages Jun 6

Subsystems (2)
lore
Share & tools
lore

Hem Parekh

author
#0 lore raw

PATCH 1/1 befs: validate b+tree node geometry to prevent out-of-bounds reads

From: fs-audit <[email protected]>

A befs b+tree node is parsed inside a single block-sized buffer_head returned by befs_read_datastream() (block_size is one of 1024/2048/4096/ 8192 and is capped at PAGE_SIZE). befs_bt_read_node() copies the on-disk all_key_count and all_key_length fields (each an unsigned 16-bit value, 0..65535) out of the node header but never bounds-checks them against the size of that buffer, and the b+tree node_size is likewise never compared to block_size.

befs_bt_keylen_index(), befs_bt_valarray() and befs_bt_get_key() then derive the keylen-index and value-array pointers directly from those untrusted counts:

    off = ALIGN(sizeof(befs_btree_nodehead) + all_key_length, 8);
    keylen_index = od_node + off;            /* may exceed the block   */
    valarray     = keylen_index + all_key_count * sizeof(fs16);

With all_key_length close to block_size, or all_key_count large, these pointers land past the end of the node buffer. Indexing them in befs_bt_get_key() (keylen_index[index - 1], keylen_index[index]) and the value reads in befs_btree_read()/befs_find_key() are then out-of-bounds reads of page-cache memory. The path is reachable from an unprivileged readdir()/lookup() on a mounted, crafted befs image.

befs_bt_get_key() additionally accepts index == all_key_count (index > all_key_count), reading one element past the keylen array even for an otherwise valid node; tighten the bound to >=.

Reject any node whose keylen-index + value arrays would extend past the block that backs it, once, in befs_bt_read_node().

---
 fs/befs/btree.c | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)
fs/befs/btree.c +16 -1
index aa24f1d..33a13da 100644
@@ -219,6 +219,21 @@ befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,
 	node->head.all_key_length =
 	    fs16_to_cpu(sb, node->od_node->all_key_length);
 
+	/*
+	 * od_node points into a single block_size buffer_head.  Reject
+	 * nodes whose (untrusted) key counts/lengths would push the
+	 * keylen-index or value arrays past the end of that block, which
+	 * would otherwise cause out-of-bounds reads in befs_bt_get_key()
+	 * and befs_bt_valarray().
+	 */
+	if (ALIGN(sizeof(befs_btree_nodehead) + node->head.all_key_length, 8) +
+	    (size_t)node->head.all_key_count * (sizeof(fs16) + sizeof(fs64)) >
+	    BEFS_SB(sb)->block_size) {
+		befs_error(sb, "corrupt b+tree node: keys (%u/%u) exceed block size",
+			   node->head.all_key_count, node->head.all_key_length);
+		return BEFS_ERR;
+	}
+
 	befs_debug(sb, "<--- %s", __func__);
 	return BEFS_OK;
 }
@@ -678,7 +693,7 @@ befs_bt_get_key(struct super_block *sb, struct befs_btree_node *node,
 	char *keystart;
 	fs16 *keylen_index;
 
-	if (index < 0 || index > node->head.all_key_count) {
+	if (index < 0 || index >= node->head.all_key_count) {
 		*keylen = 0;
 		return NULL;
 	}

--
2.34.1

author
#1 lore raw

PATCH 1/1 befs: validate b+tree node geometry to prevent out-of-bounds reads

From: fs-audit <[email protected]>

A befs b+tree node is parsed inside a single block-sized buffer_head returned by befs_read_datastream() (block_size is one of 1024/2048/4096/ 8192 and is capped at PAGE_SIZE). befs_bt_read_node() copies the on-disk all_key_count and all_key_length fields (each an unsigned 16-bit value, 0..65535) out of the node header but never bounds-checks them against the size of that buffer, and the b+tree node_size is likewise never compared to block_size.

befs_bt_keylen_index(), befs_bt_valarray() and befs_bt_get_key() then derive the keylen-index and value-array pointers directly from those untrusted counts:

    off = ALIGN(sizeof(befs_btree_nodehead) + all_key_length, 8);
    keylen_index = od_node + off;            /* may exceed the block   */
    valarray     = keylen_index + all_key_count * sizeof(fs16);

With all_key_length close to block_size, or all_key_count large, these pointers land past the end of the node buffer. Indexing them in befs_bt_get_key() (keylen_index[index - 1], keylen_index[index]) and the value reads in befs_btree_read()/befs_find_key() are then out-of-bounds reads of page-cache memory. The path is reachable from an unprivileged readdir()/lookup() on a mounted, crafted befs image.

befs_bt_get_key() additionally accepts index == all_key_count (index > all_key_count), reading one element past the keylen array even for an otherwise valid node; tighten the bound to >=.

Reject any node whose keylen-index + value arrays would extend past the block that backs it, once, in befs_bt_read_node().

---
 fs/befs/btree.c | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)
fs/befs/btree.c +16 -1
index aa24f1d..33a13da 100644
@@ -219,6 +219,21 @@ befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,
 	node->head.all_key_length =
 	    fs16_to_cpu(sb, node->od_node->all_key_length);
 
+	/*
+	 * od_node points into a single block_size buffer_head.  Reject
+	 * nodes whose (untrusted) key counts/lengths would push the
+	 * keylen-index or value arrays past the end of that block, which
+	 * would otherwise cause out-of-bounds reads in befs_bt_get_key()
+	 * and befs_bt_valarray().
+	 */
+	if (ALIGN(sizeof(befs_btree_nodehead) + node->head.all_key_length, 8) +
+	    (size_t)node->head.all_key_count * (sizeof(fs16) + sizeof(fs64)) >
+	    BEFS_SB(sb)->block_size) {
+		befs_error(sb, "corrupt b+tree node: keys (%u/%u) exceed block size",
+			   node->head.all_key_count, node->head.all_key_length);
+		return BEFS_ERR;
+	}
+
 	befs_debug(sb, "<--- %s", __func__);
 	return BEFS_OK;
 }
@@ -678,7 +693,7 @@ befs_bt_get_key(struct super_block *sb, struct befs_btree_node *node,
 	char *keystart;
 	fs16 *keylen_index;
 
-	if (index < 0 || index > node->head.all_key_count) {
+	if (index < 0 || index >= node->head.all_key_count) {
 		*keylen = 0;
 		return NULL;
 	}

--
2.34.1