lkml.org 
[lkml]   [2007]   [Feb]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
Subject[PATCH] security/keys: correct handling of key->serial collisions
Date
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 <matt@favoritemo.com>
---
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 majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2007-02-09 17:33    [W:0.027 / U:1.480 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site