1 /* Basic authentication token and access key management
3 * Copyright (C) 2004-2008 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version
9 * 2 of the License, or (at your option) any later version.
12 #include <linux/module.h>
13 #include <linux/init.h>
14 #include <linux/poison.h>
15 #include <linux/sched.h>
16 #include <linux/slab.h>
17 #include <linux/security.h>
18 #include <linux/workqueue.h>
19 #include <linux/random.h>
20 #include <linux/err.h>
23 static struct kmem_cache *key_jar;
24 struct rb_root key_serial_tree; /* tree of keys indexed by serial */
25 DEFINE_SPINLOCK(key_serial_lock);
27 struct rb_root key_user_tree; /* tree of quota records indexed by UID */
28 DEFINE_SPINLOCK(key_user_lock);
30 static LIST_HEAD(key_types_list);
31 static DECLARE_RWSEM(key_types_sem);
33 static void key_cleanup(struct work_struct *work);
34 static DECLARE_WORK(key_cleanup_task, key_cleanup);
36 /* we serialise key instantiation and link */
37 DEFINE_MUTEX(key_construction_mutex);
39 /* any key who's type gets unegistered will be re-typed to this */
40 static struct key_type key_type_dead = {
45 void __key_check(const struct key *key)
47 printk("__key_check: key %p {%08x} should be {%08x}\n",
48 key, key->magic, KEY_DEBUG_MAGIC);
53 /*****************************************************************************/
55 * get the key quota record for a user, allocating a new record if one doesn't
58 struct key_user *key_user_lookup(uid_t uid)
60 struct key_user *candidate = NULL, *user;
61 struct rb_node *parent = NULL;
65 p = &key_user_tree.rb_node;
66 spin_lock(&key_user_lock);
68 /* search the tree for a user record with a matching UID */
71 user = rb_entry(parent, struct key_user, node);
75 else if (uid > user->uid)
81 /* if we get here, we failed to find a match in the tree */
83 /* allocate a candidate user record if we don't already have
85 spin_unlock(&key_user_lock);
88 candidate = kmalloc(sizeof(struct key_user), GFP_KERNEL);
89 if (unlikely(!candidate))
92 /* the allocation may have scheduled, so we need to repeat the
93 * search lest someone else added the record whilst we were
98 /* if we get here, then the user record still hadn't appeared on the
99 * second pass - so we use the candidate record */
100 atomic_set(&candidate->usage, 1);
101 atomic_set(&candidate->nkeys, 0);
102 atomic_set(&candidate->nikeys, 0);
103 candidate->uid = uid;
104 candidate->qnkeys = 0;
105 candidate->qnbytes = 0;
106 spin_lock_init(&candidate->lock);
107 mutex_init(&candidate->cons_lock);
109 rb_link_node(&candidate->node, parent, p);
110 rb_insert_color(&candidate->node, &key_user_tree);
111 spin_unlock(&key_user_lock);
115 /* okay - we found a user record for this UID */
117 atomic_inc(&user->usage);
118 spin_unlock(&key_user_lock);
123 } /* end key_user_lookup() */
125 /*****************************************************************************/
127 * dispose of a user structure
129 void key_user_put(struct key_user *user)
131 if (atomic_dec_and_lock(&user->usage, &key_user_lock)) {
132 rb_erase(&user->node, &key_user_tree);
133 spin_unlock(&key_user_lock);
138 } /* end key_user_put() */
140 /*****************************************************************************/
142 * assign a key the next unique serial number
143 * - these are assigned randomly to avoid security issues through covert
146 static inline void key_alloc_serial(struct key *key)
148 struct rb_node *parent, **p;
151 /* propose a random serial number and look for a hole for it in the
152 * serial number tree */
154 get_random_bytes(&key->serial, sizeof(key->serial));
156 key->serial >>= 1; /* negative numbers are not permitted */
157 } while (key->serial < 3);
159 spin_lock(&key_serial_lock);
163 p = &key_serial_tree.rb_node;
167 xkey = rb_entry(parent, struct key, serial_node);
169 if (key->serial < xkey->serial)
171 else if (key->serial > xkey->serial)
177 /* we've found a suitable hole - arrange for this key to occupy it */
178 rb_link_node(&key->serial_node, parent, p);
179 rb_insert_color(&key->serial_node, &key_serial_tree);
181 spin_unlock(&key_serial_lock);
184 /* we found a key with the proposed serial number - walk the tree from
185 * that point looking for the next unused serial number */
189 if (key->serial < 3) {
191 goto attempt_insertion;
194 parent = rb_next(parent);
196 goto attempt_insertion;
198 xkey = rb_entry(parent, struct key, serial_node);
199 if (key->serial < xkey->serial)
200 goto attempt_insertion;
203 } /* end key_alloc_serial() */
205 /*****************************************************************************/
207 * allocate a key of the specified type
208 * - update the user's quota to reflect the existence of the key
209 * - called from a key-type operation with key_types_sem read-locked by
210 * key_create_or_update()
211 * - this prevents unregistration of the key type
212 * - upon return the key is as yet uninstantiated; the caller needs to either
213 * instantiate the key or discard it before returning
215 struct key *key_alloc(struct key_type *type, const char *desc,
216 uid_t uid, gid_t gid, struct task_struct *ctx,
217 key_perm_t perm, unsigned long flags)
219 struct key_user *user = NULL;
221 size_t desclen, quotalen;
224 key = ERR_PTR(-EINVAL);
228 desclen = strlen(desc) + 1;
229 quotalen = desclen + type->def_datalen;
231 /* get hold of the key tracking for this user */
232 user = key_user_lookup(uid);
236 /* check that the user's quota permits allocation of another key and
238 if (!(flags & KEY_ALLOC_NOT_IN_QUOTA)) {
239 spin_lock(&user->lock);
240 if (!(flags & KEY_ALLOC_QUOTA_OVERRUN)) {
241 if (user->qnkeys + 1 >= KEYQUOTA_MAX_KEYS ||
242 user->qnbytes + quotalen >= KEYQUOTA_MAX_BYTES
248 user->qnbytes += quotalen;
249 spin_unlock(&user->lock);
252 /* allocate and initialise the key and its description */
253 key = kmem_cache_alloc(key_jar, GFP_KERNEL);
258 key->description = kmemdup(desc, desclen, GFP_KERNEL);
259 if (!key->description)
263 atomic_set(&key->usage, 1);
264 init_rwsem(&key->sem);
267 key->quotalen = quotalen;
268 key->datalen = type->def_datalen;
274 key->payload.data = NULL;
275 key->security = NULL;
277 if (!(flags & KEY_ALLOC_NOT_IN_QUOTA))
278 key->flags |= 1 << KEY_FLAG_IN_QUOTA;
280 memset(&key->type_data, 0, sizeof(key->type_data));
283 key->magic = KEY_DEBUG_MAGIC;
286 /* let the security module know about the key */
287 ret = security_key_alloc(key, ctx, flags);
291 /* publish the key by giving it a serial number */
292 atomic_inc(&user->nkeys);
293 key_alloc_serial(key);
299 kfree(key->description);
300 kmem_cache_free(key_jar, key);
301 if (!(flags & KEY_ALLOC_NOT_IN_QUOTA)) {
302 spin_lock(&user->lock);
304 user->qnbytes -= quotalen;
305 spin_unlock(&user->lock);
312 kmem_cache_free(key_jar, key);
314 if (!(flags & KEY_ALLOC_NOT_IN_QUOTA)) {
315 spin_lock(&user->lock);
317 user->qnbytes -= quotalen;
318 spin_unlock(&user->lock);
322 key = ERR_PTR(-ENOMEM);
326 spin_unlock(&user->lock);
328 key = ERR_PTR(-EDQUOT);
331 } /* end key_alloc() */
333 EXPORT_SYMBOL(key_alloc);
335 /*****************************************************************************/
337 * reserve an amount of quota for the key's payload
339 int key_payload_reserve(struct key *key, size_t datalen)
341 int delta = (int) datalen - key->datalen;
346 /* contemplate the quota adjustment */
347 if (delta != 0 && test_bit(KEY_FLAG_IN_QUOTA, &key->flags)) {
348 spin_lock(&key->user->lock);
351 key->user->qnbytes + delta > KEYQUOTA_MAX_BYTES
356 key->user->qnbytes += delta;
357 key->quotalen += delta;
359 spin_unlock(&key->user->lock);
362 /* change the recorded data length if that didn't generate an error */
364 key->datalen = datalen;
368 } /* end key_payload_reserve() */
370 EXPORT_SYMBOL(key_payload_reserve);
372 /*****************************************************************************/
374 * instantiate a key and link it into the target keyring atomically
375 * - called with the target keyring's semaphore writelocked
377 static int __key_instantiate_and_link(struct key *key,
391 mutex_lock(&key_construction_mutex);
393 /* can't instantiate twice */
394 if (!test_bit(KEY_FLAG_INSTANTIATED, &key->flags)) {
395 /* instantiate the key */
396 ret = key->type->instantiate(key, data, datalen);
399 /* mark the key as being instantiated */
400 atomic_inc(&key->user->nikeys);
401 set_bit(KEY_FLAG_INSTANTIATED, &key->flags);
403 if (test_and_clear_bit(KEY_FLAG_USER_CONSTRUCT, &key->flags))
406 /* and link it into the destination keyring */
408 ret = __key_link(keyring, key);
410 /* disable the authorisation key */
416 mutex_unlock(&key_construction_mutex);
418 /* wake up anyone waiting for a key to be constructed */
420 wake_up_bit(&key->flags, KEY_FLAG_USER_CONSTRUCT);
424 } /* end __key_instantiate_and_link() */
426 /*****************************************************************************/
428 * instantiate a key and link it into the target keyring atomically
430 int key_instantiate_and_link(struct key *key,
439 down_write(&keyring->sem);
441 ret = __key_instantiate_and_link(key, data, datalen, keyring, instkey);
444 up_write(&keyring->sem);
448 } /* end key_instantiate_and_link() */
450 EXPORT_SYMBOL(key_instantiate_and_link);
452 /*****************************************************************************/
454 * negatively instantiate a key and link it into the target keyring atomically
456 int key_negate_and_link(struct key *key,
471 down_write(&keyring->sem);
473 mutex_lock(&key_construction_mutex);
475 /* can't instantiate twice */
476 if (!test_bit(KEY_FLAG_INSTANTIATED, &key->flags)) {
477 /* mark the key as being negatively instantiated */
478 atomic_inc(&key->user->nikeys);
479 set_bit(KEY_FLAG_NEGATIVE, &key->flags);
480 set_bit(KEY_FLAG_INSTANTIATED, &key->flags);
481 now = current_kernel_time();
482 key->expiry = now.tv_sec + timeout;
484 if (test_and_clear_bit(KEY_FLAG_USER_CONSTRUCT, &key->flags))
489 /* and link it into the destination keyring */
491 ret = __key_link(keyring, key);
493 /* disable the authorisation key */
498 mutex_unlock(&key_construction_mutex);
501 up_write(&keyring->sem);
503 /* wake up anyone waiting for a key to be constructed */
505 wake_up_bit(&key->flags, KEY_FLAG_USER_CONSTRUCT);
509 } /* end key_negate_and_link() */
511 EXPORT_SYMBOL(key_negate_and_link);
513 /*****************************************************************************/
515 * do cleaning up in process context so that we don't have to disable
516 * interrupts all over the place
518 static void key_cleanup(struct work_struct *work)
524 /* look for a dead key in the tree */
525 spin_lock(&key_serial_lock);
527 for (_n = rb_first(&key_serial_tree); _n; _n = rb_next(_n)) {
528 key = rb_entry(_n, struct key, serial_node);
530 if (atomic_read(&key->usage) == 0)
534 spin_unlock(&key_serial_lock);
538 /* we found a dead key - once we've removed it from the tree, we can
540 rb_erase(&key->serial_node, &key_serial_tree);
541 spin_unlock(&key_serial_lock);
545 security_key_free(key);
547 /* deal with the user's key tracking and quota */
548 if (test_bit(KEY_FLAG_IN_QUOTA, &key->flags)) {
549 spin_lock(&key->user->lock);
551 key->user->qnbytes -= key->quotalen;
552 spin_unlock(&key->user->lock);
555 atomic_dec(&key->user->nkeys);
556 if (test_bit(KEY_FLAG_INSTANTIATED, &key->flags))
557 atomic_dec(&key->user->nikeys);
559 key_user_put(key->user);
561 /* now throw away the key memory */
562 if (key->type->destroy)
563 key->type->destroy(key);
565 kfree(key->description);
568 key->magic = KEY_DEBUG_MAGIC_X;
570 kmem_cache_free(key_jar, key);
572 /* there may, of course, be more than one key to destroy */
575 } /* end key_cleanup() */
577 /*****************************************************************************/
579 * dispose of a reference to a key
580 * - when all the references are gone, we schedule the cleanup task to come and
581 * pull it out of the tree in definite process context
583 void key_put(struct key *key)
588 if (atomic_dec_and_test(&key->usage))
589 schedule_work(&key_cleanup_task);
592 } /* end key_put() */
594 EXPORT_SYMBOL(key_put);
596 /*****************************************************************************/
598 * find a key by its serial number
600 struct key *key_lookup(key_serial_t id)
605 spin_lock(&key_serial_lock);
607 /* search the tree for the specified key */
608 n = key_serial_tree.rb_node;
610 key = rb_entry(n, struct key, serial_node);
612 if (id < key->serial)
614 else if (id > key->serial)
621 key = ERR_PTR(-ENOKEY);
625 /* pretend it doesn't exist if it's dead */
626 if (atomic_read(&key->usage) == 0 ||
627 test_bit(KEY_FLAG_DEAD, &key->flags) ||
628 key->type == &key_type_dead)
631 /* this races with key_put(), but that doesn't matter since key_put()
632 * doesn't actually change the key
634 atomic_inc(&key->usage);
637 spin_unlock(&key_serial_lock);
640 } /* end key_lookup() */
642 /*****************************************************************************/
644 * find and lock the specified key type against removal
645 * - we return with the sem readlocked
647 struct key_type *key_type_lookup(const char *type)
649 struct key_type *ktype;
651 down_read(&key_types_sem);
653 /* look up the key type to see if it's one of the registered kernel
655 list_for_each_entry(ktype, &key_types_list, link) {
656 if (strcmp(ktype->name, type) == 0)
657 goto found_kernel_type;
660 up_read(&key_types_sem);
661 ktype = ERR_PTR(-ENOKEY);
666 } /* end key_type_lookup() */
668 /*****************************************************************************/
672 void key_type_put(struct key_type *ktype)
674 up_read(&key_types_sem);
676 } /* end key_type_put() */
678 /*****************************************************************************/
680 * attempt to update an existing key
681 * - the key has an incremented refcount
682 * - we need to put the key if we get an error
684 static inline key_ref_t __key_update(key_ref_t key_ref,
685 const void *payload, size_t plen)
687 struct key *key = key_ref_to_ptr(key_ref);
690 /* need write permission on the key to update it */
691 ret = key_permission(key_ref, KEY_WRITE);
696 if (!key->type->update)
699 down_write(&key->sem);
701 ret = key->type->update(key, payload, plen);
703 /* updating a negative key instantiates it */
704 clear_bit(KEY_FLAG_NEGATIVE, &key->flags);
715 key_ref = ERR_PTR(ret);
718 } /* end __key_update() */
720 /*****************************************************************************/
722 * search the specified keyring for a key of the same description; if one is
723 * found, update it, otherwise add a new one
725 key_ref_t key_create_or_update(key_ref_t keyring_ref,
727 const char *description,
733 struct key_type *ktype;
734 struct key *keyring, *key = NULL;
738 /* look up the key type to see if it's one of the registered kernel
740 ktype = key_type_lookup(type);
742 key_ref = ERR_PTR(-ENODEV);
746 key_ref = ERR_PTR(-EINVAL);
747 if (!ktype->match || !ktype->instantiate)
750 keyring = key_ref_to_ptr(keyring_ref);
754 key_ref = ERR_PTR(-ENOTDIR);
755 if (keyring->type != &key_type_keyring)
758 down_write(&keyring->sem);
760 /* if we're going to allocate a new key, we're going to have
761 * to modify the keyring */
762 ret = key_permission(keyring_ref, KEY_WRITE);
764 key_ref = ERR_PTR(ret);
768 /* if it's possible to update this type of key, search for an existing
769 * key of the same type and description in the destination keyring and
770 * update that instead if possible
773 key_ref = __keyring_search_one(keyring_ref, ktype, description,
775 if (!IS_ERR(key_ref))
776 goto found_matching_key;
779 /* if the client doesn't provide, decide on the permissions we want */
780 if (perm == KEY_PERM_UNDEF) {
781 perm = KEY_POS_VIEW | KEY_POS_SEARCH | KEY_POS_LINK | KEY_POS_SETATTR;
782 perm |= KEY_USR_VIEW | KEY_USR_SEARCH | KEY_USR_LINK | KEY_USR_SETATTR;
785 perm |= KEY_POS_READ | KEY_USR_READ;
787 if (ktype == &key_type_keyring || ktype->update)
788 perm |= KEY_USR_WRITE;
791 /* allocate a new key */
792 key = key_alloc(ktype, description, current->fsuid, current->fsgid,
793 current, perm, flags);
795 key_ref = ERR_CAST(key);
799 /* instantiate it and link it into the target keyring */
800 ret = __key_instantiate_and_link(key, payload, plen, keyring, NULL);
803 key_ref = ERR_PTR(ret);
807 key_ref = make_key_ref(key, is_key_possessed(keyring_ref));
810 up_write(&keyring->sem);
817 /* we found a matching key, so we're going to try to update it
818 * - we can drop the locks first as we have the key pinned
820 up_write(&keyring->sem);
823 key_ref = __key_update(key_ref, payload, plen);
826 } /* end key_create_or_update() */
828 EXPORT_SYMBOL(key_create_or_update);
830 /*****************************************************************************/
834 int key_update(key_ref_t key_ref, const void *payload, size_t plen)
836 struct key *key = key_ref_to_ptr(key_ref);
841 /* the key must be writable */
842 ret = key_permission(key_ref, KEY_WRITE);
846 /* attempt to update it if supported */
848 if (key->type->update) {
849 down_write(&key->sem);
851 ret = key->type->update(key, payload, plen);
853 /* updating a negative key instantiates it */
854 clear_bit(KEY_FLAG_NEGATIVE, &key->flags);
862 } /* end key_update() */
864 EXPORT_SYMBOL(key_update);
866 /*****************************************************************************/
870 void key_revoke(struct key *key)
874 /* make sure no one's trying to change or use the key when we mark it
875 * - we tell lockdep that we might nest because we might be revoking an
876 * authorisation key whilst holding the sem on a key we've just
879 down_write_nested(&key->sem, 1);
880 if (!test_and_set_bit(KEY_FLAG_REVOKED, &key->flags) &&
882 key->type->revoke(key);
886 } /* end key_revoke() */
888 EXPORT_SYMBOL(key_revoke);
890 /*****************************************************************************/
892 * register a type of key
894 int register_key_type(struct key_type *ktype)
900 down_write(&key_types_sem);
902 /* disallow key types with the same name */
903 list_for_each_entry(p, &key_types_list, link) {
904 if (strcmp(p->name, ktype->name) == 0)
909 list_add(&ktype->link, &key_types_list);
913 up_write(&key_types_sem);
916 } /* end register_key_type() */
918 EXPORT_SYMBOL(register_key_type);
920 /*****************************************************************************/
922 * unregister a type of key
924 void unregister_key_type(struct key_type *ktype)
929 down_write(&key_types_sem);
931 /* withdraw the key type */
932 list_del_init(&ktype->link);
934 /* mark all the keys of this type dead */
935 spin_lock(&key_serial_lock);
937 for (_n = rb_first(&key_serial_tree); _n; _n = rb_next(_n)) {
938 key = rb_entry(_n, struct key, serial_node);
940 if (key->type == ktype)
941 key->type = &key_type_dead;
944 spin_unlock(&key_serial_lock);
946 /* make sure everyone revalidates their keys */
949 /* we should now be able to destroy the payloads of all the keys of
950 * this type with impunity */
951 spin_lock(&key_serial_lock);
953 for (_n = rb_first(&key_serial_tree); _n; _n = rb_next(_n)) {
954 key = rb_entry(_n, struct key, serial_node);
956 if (key->type == ktype) {
959 memset(&key->payload, KEY_DESTROY, sizeof(key->payload));
963 spin_unlock(&key_serial_lock);
964 up_write(&key_types_sem);
966 } /* end unregister_key_type() */
968 EXPORT_SYMBOL(unregister_key_type);
970 /*****************************************************************************/
972 * initialise the key management stuff
974 void __init key_init(void)
976 /* allocate a slab in which we can store keys */
977 key_jar = kmem_cache_create("key_jar", sizeof(struct key),
978 0, SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);
980 /* add the special key types */
981 list_add_tail(&key_type_keyring.link, &key_types_list);
982 list_add_tail(&key_type_dead.link, &key_types_list);
983 list_add_tail(&key_type_user.link, &key_types_list);
985 /* record the root user tracking */
986 rb_link_node(&root_key_user.node,
988 &key_user_tree.rb_node);
990 rb_insert_color(&root_key_user.node,
993 } /* end key_init() */