1 /* Basic authentication token and access key management
3 * Copyright (C) 2004-2007 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 * insert a key with a fixed serial number
144 static void __init
__key_insert_serial(struct key
*key
)
146 struct rb_node
*parent
, **p
;
150 p
= &key_serial_tree
.rb_node
;
154 xkey
= rb_entry(parent
, struct key
, serial_node
);
156 if (key
->serial
< xkey
->serial
)
158 else if (key
->serial
> xkey
->serial
)
164 /* we've found a suitable hole - arrange for this key to occupy it */
165 rb_link_node(&key
->serial_node
, parent
, p
);
166 rb_insert_color(&key
->serial_node
, &key_serial_tree
);
168 } /* end __key_insert_serial() */
170 /*****************************************************************************/
172 * assign a key the next unique serial number
173 * - these are assigned randomly to avoid security issues through covert
176 static inline void key_alloc_serial(struct key
*key
)
178 struct rb_node
*parent
, **p
;
181 /* propose a random serial number and look for a hole for it in the
182 * serial number tree */
184 get_random_bytes(&key
->serial
, sizeof(key
->serial
));
186 key
->serial
>>= 1; /* negative numbers are not permitted */
187 } while (key
->serial
< 3);
189 spin_lock(&key_serial_lock
);
193 p
= &key_serial_tree
.rb_node
;
197 xkey
= rb_entry(parent
, struct key
, serial_node
);
199 if (key
->serial
< xkey
->serial
)
201 else if (key
->serial
> xkey
->serial
)
207 /* we've found a suitable hole - arrange for this key to occupy it */
208 rb_link_node(&key
->serial_node
, parent
, p
);
209 rb_insert_color(&key
->serial_node
, &key_serial_tree
);
211 spin_unlock(&key_serial_lock
);
214 /* we found a key with the proposed serial number - walk the tree from
215 * that point looking for the next unused serial number */
219 if (key
->serial
< 3) {
221 goto attempt_insertion
;
224 parent
= rb_next(parent
);
226 goto attempt_insertion
;
228 xkey
= rb_entry(parent
, struct key
, serial_node
);
229 if (key
->serial
< xkey
->serial
)
230 goto attempt_insertion
;
233 } /* end key_alloc_serial() */
235 /*****************************************************************************/
237 * allocate a key of the specified type
238 * - update the user's quota to reflect the existence of the key
239 * - called from a key-type operation with key_types_sem read-locked by
240 * key_create_or_update()
241 * - this prevents unregistration of the key type
242 * - upon return the key is as yet uninstantiated; the caller needs to either
243 * instantiate the key or discard it before returning
245 struct key
*key_alloc(struct key_type
*type
, const char *desc
,
246 uid_t uid
, gid_t gid
, struct task_struct
*ctx
,
247 key_perm_t perm
, unsigned long flags
)
249 struct key_user
*user
= NULL
;
251 size_t desclen
, quotalen
;
254 key
= ERR_PTR(-EINVAL
);
258 desclen
= strlen(desc
) + 1;
259 quotalen
= desclen
+ type
->def_datalen
;
261 /* get hold of the key tracking for this user */
262 user
= key_user_lookup(uid
);
266 /* check that the user's quota permits allocation of another key and
268 if (!(flags
& KEY_ALLOC_NOT_IN_QUOTA
)) {
269 spin_lock(&user
->lock
);
270 if (!(flags
& KEY_ALLOC_QUOTA_OVERRUN
)) {
271 if (user
->qnkeys
+ 1 >= KEYQUOTA_MAX_KEYS
||
272 user
->qnbytes
+ quotalen
>= KEYQUOTA_MAX_BYTES
278 user
->qnbytes
+= quotalen
;
279 spin_unlock(&user
->lock
);
282 /* allocate and initialise the key and its description */
283 key
= kmem_cache_alloc(key_jar
, GFP_KERNEL
);
288 key
->description
= kmemdup(desc
, desclen
, GFP_KERNEL
);
289 if (!key
->description
)
293 atomic_set(&key
->usage
, 1);
294 init_rwsem(&key
->sem
);
297 key
->quotalen
= quotalen
;
298 key
->datalen
= type
->def_datalen
;
304 key
->payload
.data
= NULL
;
305 key
->security
= NULL
;
307 if (!(flags
& KEY_ALLOC_NOT_IN_QUOTA
))
308 key
->flags
|= 1 << KEY_FLAG_IN_QUOTA
;
310 memset(&key
->type_data
, 0, sizeof(key
->type_data
));
313 key
->magic
= KEY_DEBUG_MAGIC
;
316 /* let the security module know about the key */
317 ret
= security_key_alloc(key
, ctx
, flags
);
321 /* publish the key by giving it a serial number */
322 atomic_inc(&user
->nkeys
);
323 key_alloc_serial(key
);
329 kfree(key
->description
);
330 kmem_cache_free(key_jar
, key
);
331 if (!(flags
& KEY_ALLOC_NOT_IN_QUOTA
)) {
332 spin_lock(&user
->lock
);
334 user
->qnbytes
-= quotalen
;
335 spin_unlock(&user
->lock
);
342 kmem_cache_free(key_jar
, key
);
344 if (!(flags
& KEY_ALLOC_NOT_IN_QUOTA
)) {
345 spin_lock(&user
->lock
);
347 user
->qnbytes
-= quotalen
;
348 spin_unlock(&user
->lock
);
352 key
= ERR_PTR(-ENOMEM
);
356 spin_unlock(&user
->lock
);
358 key
= ERR_PTR(-EDQUOT
);
361 } /* end key_alloc() */
363 EXPORT_SYMBOL(key_alloc
);
365 /*****************************************************************************/
367 * reserve an amount of quota for the key's payload
369 int key_payload_reserve(struct key
*key
, size_t datalen
)
371 int delta
= (int) datalen
- key
->datalen
;
376 /* contemplate the quota adjustment */
377 if (delta
!= 0 && test_bit(KEY_FLAG_IN_QUOTA
, &key
->flags
)) {
378 spin_lock(&key
->user
->lock
);
381 key
->user
->qnbytes
+ delta
> KEYQUOTA_MAX_BYTES
386 key
->user
->qnbytes
+= delta
;
387 key
->quotalen
+= delta
;
389 spin_unlock(&key
->user
->lock
);
392 /* change the recorded data length if that didn't generate an error */
394 key
->datalen
= datalen
;
398 } /* end key_payload_reserve() */
400 EXPORT_SYMBOL(key_payload_reserve
);
402 /*****************************************************************************/
404 * instantiate a key and link it into the target keyring atomically
405 * - called with the target keyring's semaphore writelocked
407 static int __key_instantiate_and_link(struct key
*key
,
421 mutex_lock(&key_construction_mutex
);
423 /* can't instantiate twice */
424 if (!test_bit(KEY_FLAG_INSTANTIATED
, &key
->flags
)) {
425 /* instantiate the key */
426 ret
= key
->type
->instantiate(key
, data
, datalen
);
429 /* mark the key as being instantiated */
430 atomic_inc(&key
->user
->nikeys
);
431 set_bit(KEY_FLAG_INSTANTIATED
, &key
->flags
);
433 if (test_and_clear_bit(KEY_FLAG_USER_CONSTRUCT
, &key
->flags
))
436 /* and link it into the destination keyring */
438 ret
= __key_link(keyring
, key
);
440 /* disable the authorisation key */
446 mutex_unlock(&key_construction_mutex
);
448 /* wake up anyone waiting for a key to be constructed */
450 wake_up_bit(&key
->flags
, KEY_FLAG_USER_CONSTRUCT
);
454 } /* end __key_instantiate_and_link() */
456 /*****************************************************************************/
458 * instantiate a key and link it into the target keyring atomically
460 int key_instantiate_and_link(struct key
*key
,
469 down_write(&keyring
->sem
);
471 ret
= __key_instantiate_and_link(key
, data
, datalen
, keyring
, instkey
);
474 up_write(&keyring
->sem
);
478 } /* end key_instantiate_and_link() */
480 EXPORT_SYMBOL(key_instantiate_and_link
);
482 /*****************************************************************************/
484 * negatively instantiate a key and link it into the target keyring atomically
486 int key_negate_and_link(struct key
*key
,
501 down_write(&keyring
->sem
);
503 mutex_lock(&key_construction_mutex
);
505 /* can't instantiate twice */
506 if (!test_bit(KEY_FLAG_INSTANTIATED
, &key
->flags
)) {
507 /* mark the key as being negatively instantiated */
508 atomic_inc(&key
->user
->nikeys
);
509 set_bit(KEY_FLAG_NEGATIVE
, &key
->flags
);
510 set_bit(KEY_FLAG_INSTANTIATED
, &key
->flags
);
511 now
= current_kernel_time();
512 key
->expiry
= now
.tv_sec
+ timeout
;
514 if (test_and_clear_bit(KEY_FLAG_USER_CONSTRUCT
, &key
->flags
))
519 /* and link it into the destination keyring */
521 ret
= __key_link(keyring
, key
);
523 /* disable the authorisation key */
528 mutex_unlock(&key_construction_mutex
);
531 up_write(&keyring
->sem
);
533 /* wake up anyone waiting for a key to be constructed */
535 wake_up_bit(&key
->flags
, KEY_FLAG_USER_CONSTRUCT
);
539 } /* end key_negate_and_link() */
541 EXPORT_SYMBOL(key_negate_and_link
);
543 /*****************************************************************************/
545 * do cleaning up in process context so that we don't have to disable
546 * interrupts all over the place
548 static void key_cleanup(struct work_struct
*work
)
554 /* look for a dead key in the tree */
555 spin_lock(&key_serial_lock
);
557 for (_n
= rb_first(&key_serial_tree
); _n
; _n
= rb_next(_n
)) {
558 key
= rb_entry(_n
, struct key
, serial_node
);
560 if (atomic_read(&key
->usage
) == 0)
564 spin_unlock(&key_serial_lock
);
568 /* we found a dead key - once we've removed it from the tree, we can
570 rb_erase(&key
->serial_node
, &key_serial_tree
);
571 spin_unlock(&key_serial_lock
);
575 security_key_free(key
);
577 /* deal with the user's key tracking and quota */
578 if (test_bit(KEY_FLAG_IN_QUOTA
, &key
->flags
)) {
579 spin_lock(&key
->user
->lock
);
581 key
->user
->qnbytes
-= key
->quotalen
;
582 spin_unlock(&key
->user
->lock
);
585 atomic_dec(&key
->user
->nkeys
);
586 if (test_bit(KEY_FLAG_INSTANTIATED
, &key
->flags
))
587 atomic_dec(&key
->user
->nikeys
);
589 key_user_put(key
->user
);
591 /* now throw away the key memory */
592 if (key
->type
->destroy
)
593 key
->type
->destroy(key
);
595 kfree(key
->description
);
598 key
->magic
= KEY_DEBUG_MAGIC_X
;
600 kmem_cache_free(key_jar
, key
);
602 /* there may, of course, be more than one key to destroy */
605 } /* end key_cleanup() */
607 /*****************************************************************************/
609 * dispose of a reference to a key
610 * - when all the references are gone, we schedule the cleanup task to come and
611 * pull it out of the tree in definite process context
613 void key_put(struct key
*key
)
618 if (atomic_dec_and_test(&key
->usage
))
619 schedule_work(&key_cleanup_task
);
622 } /* end key_put() */
624 EXPORT_SYMBOL(key_put
);
626 /*****************************************************************************/
628 * find a key by its serial number
630 struct key
*key_lookup(key_serial_t id
)
635 spin_lock(&key_serial_lock
);
637 /* search the tree for the specified key */
638 n
= key_serial_tree
.rb_node
;
640 key
= rb_entry(n
, struct key
, serial_node
);
642 if (id
< key
->serial
)
644 else if (id
> key
->serial
)
651 key
= ERR_PTR(-ENOKEY
);
655 /* pretend it doesn't exist if it's dead */
656 if (atomic_read(&key
->usage
) == 0 ||
657 test_bit(KEY_FLAG_DEAD
, &key
->flags
) ||
658 key
->type
== &key_type_dead
)
661 /* this races with key_put(), but that doesn't matter since key_put()
662 * doesn't actually change the key
664 atomic_inc(&key
->usage
);
667 spin_unlock(&key_serial_lock
);
670 } /* end key_lookup() */
672 /*****************************************************************************/
674 * find and lock the specified key type against removal
675 * - we return with the sem readlocked
677 struct key_type
*key_type_lookup(const char *type
)
679 struct key_type
*ktype
;
681 down_read(&key_types_sem
);
683 /* look up the key type to see if it's one of the registered kernel
685 list_for_each_entry(ktype
, &key_types_list
, link
) {
686 if (strcmp(ktype
->name
, type
) == 0)
687 goto found_kernel_type
;
690 up_read(&key_types_sem
);
691 ktype
= ERR_PTR(-ENOKEY
);
696 } /* end key_type_lookup() */
698 /*****************************************************************************/
702 void key_type_put(struct key_type
*ktype
)
704 up_read(&key_types_sem
);
706 } /* end key_type_put() */
708 /*****************************************************************************/
710 * attempt to update an existing key
711 * - the key has an incremented refcount
712 * - we need to put the key if we get an error
714 static inline key_ref_t
__key_update(key_ref_t key_ref
,
715 const void *payload
, size_t plen
)
717 struct key
*key
= key_ref_to_ptr(key_ref
);
720 /* need write permission on the key to update it */
721 ret
= key_permission(key_ref
, KEY_WRITE
);
726 if (!key
->type
->update
)
729 down_write(&key
->sem
);
731 ret
= key
->type
->update(key
, payload
, plen
);
733 /* updating a negative key instantiates it */
734 clear_bit(KEY_FLAG_NEGATIVE
, &key
->flags
);
745 key_ref
= ERR_PTR(ret
);
748 } /* end __key_update() */
750 /*****************************************************************************/
752 * search the specified keyring for a key of the same description; if one is
753 * found, update it, otherwise add a new one
755 key_ref_t
key_create_or_update(key_ref_t keyring_ref
,
757 const char *description
,
762 struct key_type
*ktype
;
763 struct key
*keyring
, *key
= NULL
;
768 /* look up the key type to see if it's one of the registered kernel
770 ktype
= key_type_lookup(type
);
772 key_ref
= ERR_PTR(-ENODEV
);
776 key_ref
= ERR_PTR(-EINVAL
);
777 if (!ktype
->match
|| !ktype
->instantiate
)
780 keyring
= key_ref_to_ptr(keyring_ref
);
784 key_ref
= ERR_PTR(-ENOTDIR
);
785 if (keyring
->type
!= &key_type_keyring
)
788 down_write(&keyring
->sem
);
790 /* if we're going to allocate a new key, we're going to have
791 * to modify the keyring */
792 ret
= key_permission(keyring_ref
, KEY_WRITE
);
794 key_ref
= ERR_PTR(ret
);
798 /* if it's possible to update this type of key, search for an existing
799 * key of the same type and description in the destination keyring and
800 * update that instead if possible
803 key_ref
= __keyring_search_one(keyring_ref
, ktype
, description
,
805 if (!IS_ERR(key_ref
))
806 goto found_matching_key
;
809 /* decide on the permissions we want */
810 perm
= KEY_POS_VIEW
| KEY_POS_SEARCH
| KEY_POS_LINK
| KEY_POS_SETATTR
;
811 perm
|= KEY_USR_VIEW
| KEY_USR_SEARCH
| KEY_USR_LINK
| KEY_USR_SETATTR
;
814 perm
|= KEY_POS_READ
| KEY_USR_READ
;
816 if (ktype
== &key_type_keyring
|| ktype
->update
)
817 perm
|= KEY_USR_WRITE
;
819 /* allocate a new key */
820 key
= key_alloc(ktype
, description
, current
->fsuid
, current
->fsgid
,
821 current
, perm
, flags
);
823 key_ref
= ERR_PTR(PTR_ERR(key
));
827 /* instantiate it and link it into the target keyring */
828 ret
= __key_instantiate_and_link(key
, payload
, plen
, keyring
, NULL
);
831 key_ref
= ERR_PTR(ret
);
835 key_ref
= make_key_ref(key
, is_key_possessed(keyring_ref
));
838 up_write(&keyring
->sem
);
845 /* we found a matching key, so we're going to try to update it
846 * - we can drop the locks first as we have the key pinned
848 up_write(&keyring
->sem
);
851 key_ref
= __key_update(key_ref
, payload
, plen
);
854 } /* end key_create_or_update() */
856 EXPORT_SYMBOL(key_create_or_update
);
858 /*****************************************************************************/
862 int key_update(key_ref_t key_ref
, const void *payload
, size_t plen
)
864 struct key
*key
= key_ref_to_ptr(key_ref
);
869 /* the key must be writable */
870 ret
= key_permission(key_ref
, KEY_WRITE
);
874 /* attempt to update it if supported */
876 if (key
->type
->update
) {
877 down_write(&key
->sem
);
879 ret
= key
->type
->update(key
, payload
, plen
);
881 /* updating a negative key instantiates it */
882 clear_bit(KEY_FLAG_NEGATIVE
, &key
->flags
);
890 } /* end key_update() */
892 EXPORT_SYMBOL(key_update
);
894 /*****************************************************************************/
898 void key_revoke(struct key
*key
)
902 /* make sure no one's trying to change or use the key when we mark it
903 * - we tell lockdep that we might nest because we might be revoking an
904 * authorisation key whilst holding the sem on a key we've just
907 down_write_nested(&key
->sem
, 1);
908 if (!test_and_set_bit(KEY_FLAG_REVOKED
, &key
->flags
) &&
910 key
->type
->revoke(key
);
914 } /* end key_revoke() */
916 EXPORT_SYMBOL(key_revoke
);
918 /*****************************************************************************/
920 * register a type of key
922 int register_key_type(struct key_type
*ktype
)
928 down_write(&key_types_sem
);
930 /* disallow key types with the same name */
931 list_for_each_entry(p
, &key_types_list
, link
) {
932 if (strcmp(p
->name
, ktype
->name
) == 0)
937 list_add(&ktype
->link
, &key_types_list
);
941 up_write(&key_types_sem
);
944 } /* end register_key_type() */
946 EXPORT_SYMBOL(register_key_type
);
948 /*****************************************************************************/
950 * unregister a type of key
952 void unregister_key_type(struct key_type
*ktype
)
957 down_write(&key_types_sem
);
959 /* withdraw the key type */
960 list_del_init(&ktype
->link
);
962 /* mark all the keys of this type dead */
963 spin_lock(&key_serial_lock
);
965 for (_n
= rb_first(&key_serial_tree
); _n
; _n
= rb_next(_n
)) {
966 key
= rb_entry(_n
, struct key
, serial_node
);
968 if (key
->type
== ktype
)
969 key
->type
= &key_type_dead
;
972 spin_unlock(&key_serial_lock
);
974 /* make sure everyone revalidates their keys */
977 /* we should now be able to destroy the payloads of all the keys of
978 * this type with impunity */
979 spin_lock(&key_serial_lock
);
981 for (_n
= rb_first(&key_serial_tree
); _n
; _n
= rb_next(_n
)) {
982 key
= rb_entry(_n
, struct key
, serial_node
);
984 if (key
->type
== ktype
) {
987 memset(&key
->payload
, KEY_DESTROY
, sizeof(key
->payload
));
991 spin_unlock(&key_serial_lock
);
992 up_write(&key_types_sem
);
994 } /* end unregister_key_type() */
996 EXPORT_SYMBOL(unregister_key_type
);
998 /*****************************************************************************/
1000 * initialise the key management stuff
1002 void __init
key_init(void)
1004 /* allocate a slab in which we can store keys */
1005 key_jar
= kmem_cache_create("key_jar", sizeof(struct key
),
1006 0, SLAB_HWCACHE_ALIGN
|SLAB_PANIC
, NULL
);
1008 /* add the special key types */
1009 list_add_tail(&key_type_keyring
.link
, &key_types_list
);
1010 list_add_tail(&key_type_dead
.link
, &key_types_list
);
1011 list_add_tail(&key_type_user
.link
, &key_types_list
);
1013 /* record the root user tracking */
1014 rb_link_node(&root_key_user
.node
,
1016 &key_user_tree
.rb_node
);
1018 rb_insert_color(&root_key_user
.node
,
1021 /* record root's user standard keyrings */
1022 key_check(&root_user_keyring
);
1023 key_check(&root_session_keyring
);
1025 __key_insert_serial(&root_user_keyring
);
1026 __key_insert_serial(&root_session_keyring
);
1028 keyring_publish_name(&root_user_keyring
);
1029 keyring_publish_name(&root_session_keyring
);
1031 /* link the two root keyrings together */
1032 key_link(&root_session_keyring
, &root_user_keyring
);
1034 } /* end key_init() */