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

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

[Hem Parekh]

From: fs-audit <a@b.c>

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().

Signed-off-by: fs-audit <a@b.c>
---
 fs/befs/btree.c | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

diff --git a/fs/befs/btree.c b/fs/befs/btree.c
index aa24f1d..33a13da 100644
--- a/fs/befs/btree.c
+++ b/fs/befs/btree.c
@@ -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

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

[Hem Parekh]

From: fs-audit <a@b.c>

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().

Signed-off-by: fs-audit <a@b.c>
---
 fs/befs/btree.c | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

diff --git a/fs/befs/btree.c b/fs/befs/btree.c
index aa24f1d..33a13da 100644
--- a/fs/befs/btree.c
+++ b/fs/befs/btree.c
@@ -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