linux-toradex.git/security/keys/keyring.c, branch v3.14.4

KEYS: Make the keyring cycle detector ignore other keyrings of the same name

2014-03-10T01:57:18+00:00

This fixes CVE-2014-0102.

The following command sequence produces an oops:

	keyctl new_session
	i=`keyctl newring _ses @s`
	keyctl link @s $i

The problem is that search_nested_keyrings() sees two keyrings that have
matching type and description, so keyring_compare_object() returns true.
s_n_k() then passes the key to the iterator function -
keyring_detect_cycle_iterator() - which *should* check to see whether this is
the keyring of interest, not just one with the same name.

Because assoc_array_find() will return one and only one match, I assumed that
the iterator function would only see an exact match or never be called - but
the iterator isn't only called from assoc_array_find()...

The oops looks something like this:

	kernel BUG at /data/fs/linux-2.6-fscache/security/keys/keyring.c:1003!
	invalid opcode: 0000 [#1] SMP
	...
	RIP: keyring_detect_cycle_iterator+0xe/0x1f
	...
	Call Trace:
	  search_nested_keyrings+0x76/0x2aa
	  __key_link_check_live_key+0x50/0x5f
	  key_link+0x4e/0x85
	  keyctl_keyring_link+0x60/0x81
	  SyS_keyctl+0x65/0xe4
	  tracesys+0xdd/0xe2

The fix is to make keyring_detect_cycle_iterator() check that the key it
has is the key it was actually looking for rather than calling BUG_ON().

A testcase has been included in the keyutils testsuite for this:

	http://git.kernel.org/cgit/linux/kernel/git/dhowells/keyutils.git/commit/?id=891f3365d07f1996778ade0e3428f01878a1790b

Reported-by: Tommi Rantala 
Signed-off-by: David Howells 
Acked-by: James Morris 
Signed-off-by: Linus Torvalds

KEYS: Fix searching of nested keyrings

2013-12-02T11:24:19+00:00

If a keyring contains more than 16 keyrings (the capacity of a single node in
the associative array) then those keyrings are split over multiple nodes
arranged as a tree.

If search_nested_keyrings() is called to search the keyring then it will
attempt to manually walk over just the 0 branch of the associative array tree
where all the keyring links are stored.  This works provided the key is found
before the algorithm steps from one node containing keyrings to a child node
or if there are sufficiently few keyring links that the keyrings are all in
one node.

However, if the algorithm does need to step from a node to a child node, it
doesn't change the node pointer unless a shortcut also gets transited.  This
means that the algorithm will keep scanning the same node over and over again
without terminating and without returning.

To fix this, move the internal-pointer-to-node translation from inside the
shortcut transit handler so that it applies it to node arrival as well.

This can be tested by:

	r=`keyctl newring sandbox @s`
	for ((i=0; i<=16; i++)); do keyctl newring ring$i $r; done
	for ((i=0; i<=16; i++)); do keyctl add user a$i a %:ring$i; done
	for ((i=0; i<=16; i++)); do keyctl search $r user a$i; done
	for ((i=17; i<=20; i++)); do keyctl search $r user a$i; done

The searches should all complete successfully (or with an error for 17-20),
but instead one or more of them will hang.

Signed-off-by: David Howells 
Tested-by: Stephen Gallagher

KEYS: Fix multiple key add into associative array

2013-12-02T11:24:18+00:00

If sufficient keys (or keyrings) are added into a keyring such that a node in
the associative array's tree overflows (each node has a capacity N, currently
16) and such that all N+1 keys have the same index key segment for that level
of the tree (the level'th nibble of the index key), then assoc_array_insert()
calls ops->diff_objects() to indicate at which bit position the two index keys
vary.

However, __key_link_begin() passes a NULL object to assoc_array_insert() with
the intention of supplying the correct pointer later before we commit the
change.  This means that keyring_diff_objects() is given a NULL pointer as one
of its arguments which it does not expect.  This results in an oops like the
attached.

With the previous patch to fix the keyring hash function, this can be forced
much more easily by creating a keyring and only adding keyrings to it.  Add any
other sort of key and a different insertion path is taken - all 16+1 objects
must want to cluster in the same node slot.

This can be tested by:

	r=`keyctl newring sandbox @s`
	for ((i=0; i<=16; i++)); do keyctl newring ring$i $r; done

This should work fine, but oopses when the 17th keyring is added.

Since ops->diff_objects() is always called with the first pointer pointing to
the object to be inserted (ie. the NULL pointer), we can fix the problem by
changing the to-be-inserted object pointer to point to the index key passed
into assoc_array_insert() instead.

Whilst we're at it, we also switch the arguments so that they are the same as
for ->compare_object().

BUG: unable to handle kernel NULL pointer dereference at 0000000000000088
IP: [] hash_key_type_and_desc+0x18/0xb0
...
RIP: 0010:[] hash_key_type_and_desc+0x18/0xb0
...
Call Trace:
 [] keyring_diff_objects+0x21/0xd2
 [] assoc_array_insert+0x3b6/0x908
 [] __key_link_begin+0x78/0xe5
 [] key_create_or_update+0x17d/0x36a
 [] SyS_add_key+0x123/0x183
 [] tracesys+0xdd/0xe2

Signed-off-by: David Howells 
Tested-by: Stephen Gallagher

KEYS: Fix the keyring hash function

2013-12-02T11:24:18+00:00

The keyring hash function (used by the associative array) is supposed to clear
the bottommost nibble of the index key (where the hash value resides) for
keyrings and make sure it is non-zero for non-keyrings.  This is done to make
keyrings cluster together on one branch of the tree separately to other keys.

Unfortunately, the wrong mask is used, so only the bottom two bits are
examined and cleared and not the whole bottom nibble.  This means that keys
and keyrings can still be successfully searched for under most circumstances
as the hash is consistent in its miscalculation, but if a keyring's
associative array bottom node gets filled up then approx 75% of the keyrings
will not be put into the 0 branch.

The consequence of this is that a key in a keyring linked to by another
keyring, ie.

	keyring A -> keyring B -> key

may not be found if the search starts at keyring A and then descends into
keyring B because search_nested_keyrings() only searches up the 0 branch (as it
"knows" all keyrings must be there and not elsewhere in the tree).

The fix is to use the right mask.

This can be tested with:

	r=`keyctl newring sandbox @s`
	for ((i=0; i<=16; i++)); do keyctl newring ring$i $r; done
	for ((i=0; i<=16; i++)); do keyctl add user a$i a %:ring$i; done
	for ((i=0; i<=16; i++)); do keyctl search $r user a$i; done

This creates a sandbox keyring, then creates 17 keyrings therein (labelled
ring0..ring16).  This causes the root node of the sandbox's associative array
to overflow and for the tree to have extra nodes inserted.

Each keyring then is given a user key (labelled aN for ringN) for us to search
for.

We then search for the user keys we added, starting from the sandbox.  If
working correctly, it should return the same ordered list of key IDs as
for...keyctl add... did.  Without this patch, it reports ENOKEY "Required key
not available" for some of the keys.  Just which keys get this depends as the
kernel pointer to the key type forms part of the hash function.

Reported-by: Nalin Dahyabhai 
Signed-off-by: David Howells 
Tested-by: Stephen Gallagher

KEYS: Fix keyring content gc scanner

2013-11-14T14:09:53+00:00

Key pointers stored in the keyring are marked in bit 1 to indicate if they
point to a keyring.  We need to strip off this bit before using the pointer
when iterating over the keyring for the purpose of looking for links to garbage
collect.

This means that expirable keyrings aren't correctly expiring because the
checker is seeing their key pointer with 2 added to it.

Since the fix for this involves knowing about the internals of the keyring,
key_gc_keyring() is moved to keyring.c and merged into keyring_gc().

This can be tested by:

	echo 2 >/proc/sys/kernel/keys/gc_delay
	keyctl timeout `keyctl add keyring qwerty "" @s` 2
	cat /proc/keys
	sleep 5; cat /proc/keys

which should see a keyring called "qwerty" appear in the session keyring and
then disappear after it expires, and:

	echo 2 >/proc/sys/kernel/keys/gc_delay
	a=`keyctl get_persistent @s`
	b=`keyctl add keyring 0 "" $a`
	keyctl add user a a $b
	keyctl timeout $b 2
	cat /proc/keys
	sleep 5; cat /proc/keys

which should see a keyring called "0" with a key called "a" in it appear in the
user's persistent keyring (which will be attached to the session keyring) and
then both the "0" keyring and the "a" key should disappear when the "0" keyring
expires.

Signed-off-by: David Howells 
Acked-by: Simo Sorce

KEYS: Fix keyring quota misaccounting on key replacement and unlink

2013-10-30T11:15:24+00:00

If a key is displaced from a keyring by a matching one, then four more bytes
of quota are allocated to the keyring - despite the fact that the keyring does
not change in size.

Further, when a key is unlinked from a keyring, the four bytes of quota
allocated the link isn't recovered and returned to the user's pool.

The first can be tested by repeating:

	keyctl add big_key a fred @s
	cat /proc/key-users

(Don't put it in a shell loop otherwise the garbage collector won't have time
to clear the displaced keys, thus affecting the result).

This was causing the kerberos keyring to run out of room fairly quickly.

The second can be tested by:

	cat /proc/key-users
	a=`keyctl add user a a @s`
	cat /proc/key-users
	keyctl unlink $a
	sleep 1 # Give RCU a chance to delete the key
	cat /proc/key-users

assuming no system activity that otherwise adds/removes keys, the amount of
key data allocated should go up (say 40/20000 -> 47/20000) and then return to
the original value at the end.

Reported-by: Stephen Gallagher 
Signed-off-by: David Howells

KEYS: Fix a race between negating a key and reading the error set

2013-10-30T11:15:24+00:00

key_reject_and_link() marking a key as negative and setting the error with
which it was negated races with keyring searches and other things that read
that error.

The fix is to switch the order in which the assignments are done in
key_reject_and_link() and to use memory barriers.

Kudos to Dave Wysochanski  and Scott Mayhew
 for tracking this down.

This may be the cause of:

BUG: unable to handle kernel NULL pointer dereference at 0000000000000070
IP: [] wait_for_key_construction+0x31/0x80
PGD c6b2c3067 PUD c59879067 PMD 0
Oops: 0000 [#1] SMP
last sysfs file: /sys/devices/system/cpu/cpu3/cache/index2/shared_cpu_map
CPU 0
Modules linked in: ...

Pid: 13359, comm: amqzxma0 Not tainted 2.6.32-358.20.1.el6.x86_64 #1 IBM System x3650 M3 -[7945PSJ]-/00J6159
RIP: 0010:[] wait_for_key_construction+0x31/0x80
RSP: 0018:ffff880c6ab33758  EFLAGS: 00010246
RAX: ffffffff81219080 RBX: 0000000000000000 RCX: 0000000000000002
RDX: ffffffff81219060 RSI: 0000000000000000 RDI: 0000000000000000
RBP: ffff880c6ab33768 R08: 0000000000000000 R09: 0000000000000000
R10: 0000000000000001 R11: 0000000000000000 R12: ffff880adfcbce40
R13: ffffffffa03afb84 R14: ffff880adfcbce40 R15: ffff880adfcbce43
FS:  00007f29b8042700(0000) GS:ffff880028200000(0000) knlGS:0000000000000000
CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 0000000000000070 CR3: 0000000c613dc000 CR4: 00000000000007f0
DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
DR3: 0000000000000000 DR6: 00000000ffff0ff0 DR7: 0000000000000400
Process amqzxma0 (pid: 13359, threadinfo ffff880c6ab32000, task ffff880c610deae0)
Stack:
 ffff880adfcbce40 0000000000000000 ffff880c6ab337b8 ffffffff81219695
 0000000000000000 ffff880a000000d0 ffff880c6ab337a8 000000000000000f
 ffffffffa03afb93 000000000000000f ffff88186c7882c0 0000000000000014
Call Trace:
 [] request_key+0x65/0xa0
 [] nfs_idmap_request_key+0xc5/0x170 [nfs]
 [] nfs_idmap_lookup_id+0x34/0x80 [nfs]
 [] nfs_map_group_to_gid+0x75/0xa0 [nfs]
 [] decode_getfattr_attrs+0xbdd/0xfb0 [nfs]
 [] ? __dequeue_entity+0x30/0x50
 [] ? __switch_to+0x26e/0x320
 [] decode_getfattr+0x83/0xe0 [nfs]
 [] ? nfs4_xdr_dec_getattr+0x0/0xa0 [nfs]
 [] nfs4_xdr_dec_getattr+0x8f/0xa0 [nfs]
 [] rpcauth_unwrap_resp+0x84/0xb0 [sunrpc]
 [] ? nfs4_xdr_dec_getattr+0x0/0xa0 [nfs]
 [] call_decode+0x1b3/0x800 [sunrpc]
 [] ? wake_bit_function+0x0/0x50
 [] ? call_decode+0x0/0x800 [sunrpc]
 [] __rpc_execute+0x77/0x350 [sunrpc]
 [] ? bit_waitqueue+0x17/0xd0
 [] rpc_execute+0x61/0xa0 [sunrpc]
 [] rpc_run_task+0x75/0x90 [sunrpc]
 [] rpc_call_sync+0x42/0x70 [sunrpc]
 [] _nfs4_call_sync+0x30/0x40 [nfs]
 [] _nfs4_proc_getattr+0xac/0xc0 [nfs]
 [] ? futex_wait+0x227/0x380
 [] nfs4_proc_getattr+0x56/0x80 [nfs]
 [] __nfs_revalidate_inode+0xe3/0x220 [nfs]
 [] nfs_revalidate_mapping+0x4e/0x170 [nfs]
 [] nfs_file_read+0x77/0x130 [nfs]
 [] do_sync_read+0xfa/0x140
 [] ? autoremove_wake_function+0x0/0x40
 [] ? apic_timer_interrupt+0xe/0x20
 [] ? common_interrupt+0xe/0x13
 [] ? selinux_file_permission+0xfb/0x150
 [] ? security_file_permission+0x16/0x20
 [] vfs_read+0xb5/0x1a0
 [] sys_read+0x51/0x90
 [] ? __audit_syscall_exit+0x265/0x290
 [] system_call_fastpath+0x16/0x1b

Signed-off-by: David Howells 
cc: Dave Wysochanski 
cc: Scott Mayhew

KEYS: Add a 'trusted' flag and a 'trusted only' flag

2013-09-25T16:17:01+00:00

Add KEY_FLAG_TRUSTED to indicate that a key either comes from a trusted source
or had a cryptographic signature chain that led back to a trusted key the
kernel already possessed.

Add KEY_FLAGS_TRUSTED_ONLY to indicate that a keyring will only accept links to
keys marked with KEY_FLAGS_TRUSTED.

Signed-off-by: David Howells 
Reviewed-by: Kees Cook

KEYS: Expand the capacity of a keyring

2013-09-24T09:35:18+00:00

Expand the capacity of a keyring to be able to hold a lot more keys by using
the previously added associative array implementation.  Currently the maximum
capacity is:

	(PAGE_SIZE - sizeof(header)) / sizeof(struct key *)

which, on a 64-bit system, is a little more 500.  However, since this is being
used for the NFS uid mapper, we need more than that.  The new implementation
gives us effectively unlimited capacity.

With some alterations, the keyutils testsuite runs successfully to completion
after this patch is applied.  The alterations are because (a) keyrings that
are simply added to no longer appear ordered and (b) some of the errors have
changed a bit.

Signed-off-by: David Howells

KEYS: Drop the permissions argument from __keyring_search_one()

2013-09-24T09:35:17+00:00

Drop the permissions argument from __keyring_search_one() as the only caller
passes 0 here - which causes all checks to be skipped.

Signed-off-by: David Howells