[PATCH] security/keys: correct handling of key->serial collisions

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



The randomized key->serial choice algorithm introduced in 2.6.18 exposed some bugs in the handling of collisions in the rbtree of allocated key->serials. Collisions then resulted in eventual kernel oopses (due to rbtree corruption) once cleanup was attempted. This patch corrects the collision handling to behave correctly. Additionally, the (admittedly unlikely) scenario in which there are no more key->serials available results in a return of -ENOMEM rather than an oops.

Signed-off-by: Matt Mitchell <[email protected]>
---
The collision resolution procedure works like the old one was intended to -- if you get a collision on your random serial selection, try the next serial (wrapping at 2^31) until you either (a) find a hole or (b) wrap completely around the keyspace. Since the keyspace is 2^31, collisions are fairly rare -- however, with certain workloads, they happen with some frequency. Samba in particular is a common culprit among those of us that ran across this bug due to its need to masquerade as many users (and therefore create lots of session keyrings and the like).

This patch could/should be applied to 2.6.18 and 2.6.19 as well.

diff --git a/security/keys/key.c b/security/keys/key.c
index 700400d..bdc7837 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -178,17 +178,21 @@ static inline void key_alloc_serial(struct key *key)
	struct rb_node *parent, **p;
	struct key *xkey;
+	key_serial_t orig;
+	int keyspace_loop;
+
	/* propose a random serial number and look for a hole for it in the
	 * serial number tree */
	do {
		get_random_bytes(&key->serial, sizeof(key->serial));
		key->serial >>= 1; /* negative numbers are not permitted */
+		orig = key->serial;
+		keyspace_loop = 0;
	} while (key->serial < 3);
	spin_lock(&key_serial_lock);
-attempt_insertion:
	parent = NULL;
	p = &key_serial_tree.rb_node;
@@ -200,8 +204,26 @@ attempt_insertion:
			p = &(*p)->rb_left;
		else if (key->serial > xkey->serial)
			p = &(*p)->rb_right;
-		else
-			goto serial_exists;
+		else {	
+			/* if we have already looped, check for exhausted
+			 * keyspace */
+			if ((keyspace_loop == 1) && (key->serial >= orig)) {
+				/* this is just a dummy */
+				key->serial = -1;
+				spin_unlock(&key_serial_lock);
+				printk(KERN_WARNING "key_alloc_serial: "
+						"keyspace exhausted\n");
+				return;
+			}
+
+			key->serial++;
+			if (key->serial < 2) {
+				keyspace_loop = 1;
+				key->serial = 2;
+			}
+			parent = NULL;
+			p = &key_serial_tree.rb_node;
+		}
	}
	/* we've found a suitable hole - arrange for this key to occupy it */
@@ -209,26 +231,6 @@ attempt_insertion:
	rb_insert_color(&key->serial_node, &key_serial_tree);
	spin_unlock(&key_serial_lock);
-	return;
-
-	/* we found a key with the proposed serial number - walk the tree from
-	 * that point looking for the next unused serial number */
-serial_exists:
-	for (;;) {
-		key->serial++;
-		if (key->serial < 3) {
-			key->serial = 3;
-			goto attempt_insertion;
-		}
-
-		parent = rb_next(parent);
-		if (!parent)
-			goto attempt_insertion;
-
-		xkey = rb_entry(parent, struct key, serial_node);
-		if (key->serial < xkey->serial)
-			goto attempt_insertion;
-	}
} /* end key_alloc_serial() */
@@ -319,9 +321,14 @@ struct key *key_alloc(struct key_type *type, const char *desc,
		goto security_error;
	/* publish the key by giving it a serial number */
-	atomic_inc(&user->nkeys);
	key_alloc_serial(key);
+	/* check for success */
+	if (key->serial == -1)
+		goto no_memory_3;
+	else
+		atomic_inc(&user->nkeys);
+
error:
	return key;


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[Index of Archives]     [Kernel Newbies]     [Netfilter]     [Bugtraq]     [Photo]     [Stuff]     [Gimp]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Video 4 Linux]     [Linux for the blind]     [Linux Resources]
  Powered by Linux