Bug 523054 – kernel: incorrect termination condition in assoc array garbage collection (CVE-2014-3631)

• Product: Gentoo Security
• Status: RESOLVED OBSOLETE

[Description Tomáš Mózes 2014-09-17 18:02:05 UTC]

commit 1143261f66aec99fdfbc98903b55d51bb55572a1
Author: David Howells <[e-mail]>
Date:   Wed Sep 10 22:22:00 2014 +0100

    KEYS: Fix termination condition in assoc array garbage collection
    
    commit 95389b08d93d5c06ec63ab49bd732b0069b7c35e upstream.
    
    This fixes CVE-2014-3631.
    
    It is possible for an associative array to end up with a shortcut node at the
    root of the tree if there are more than fan-out leaves in the tree, but they
    all crowd into the same slot in the lowest level (ie. they all have the same
    first nibble of their index keys).
    
    When assoc_array_gc() returns back up the tree after scanning some leaves, it
    can fall off of the root and crash because it assumes that the back pointer
    from a shortcut (after label ascend_old_tree) must point to a normal node -
    which isn't true of a shortcut node at the root.
    
    Should we find we're ascending rootwards over a shortcut, we should check to
    see if the backpointer is zero - and if it is, we have completed the scan.
    
    This particular bug cannot occur if the root node is not a shortcut - ie. if
    you have fewer than 17 keys in a keyring or if you have at least two keys that
    sit into separate slots (eg. a keyring and a non keyring).
    
    This can be reproduced by:
    
    	ring=`keyctl newring bar @s`
    	for ((i=1; i<=18; i++)); do last_key=`keyctl newring foo$i $ring`; done
    	keyctl timeout $last_key 2
    
    Doing this:
    
    	echo 3 >/proc/sys/kernel/keys/gc_delay
    
    first will speed things up.
    
    If we do fall off of the top of the tree, we get the following oops:
    
    BUG: unable to handle kernel NULL pointer dereference at 0000000000000018
    IP: [<ffffffff8136cea7>] assoc_array_gc+0x2f7/0x540
    PGD dae15067 PUD cfc24067 PMD 0
    Oops: 0000 [#1] SMP
    Modules linked in: xt_nat xt_mark nf_conntrack_netbios_ns nf_conntrack_broadcast ip6t_rpfilter ip6t_REJECT xt_conntrack ebtable_nat ebtable_broute bridge stp llc ebtable_filter ebtables ip6table_ni
    CPU: 0 PID: 26011 Comm: kworker/0:1 Not tainted 3.14.9-200.fc20.x86_64 #1
    Hardware name: Bochs Bochs, BIOS Bochs 01/01/2011
    Workqueue: events key_garbage_collector
    task: ffff8800918bd580 ti: ffff8800aac14000 task.ti: ffff8800aac14000
    RIP: 0010:[<ffffffff8136cea7>] [<ffffffff8136cea7>] assoc_array_gc+0x2f7/0x540
    RSP: 0018:ffff8800aac15d40  EFLAGS: 00010206
    RAX: 0000000000000000 RBX: 0000000000000000 RCX: ffff8800aaecacc0
    RDX: ffff8800daecf440 RSI: 0000000000000001 RDI: ffff8800aadc2bc0
    RBP: ffff8800aac15da8 R08: 0000000000000001 R09: 0000000000000003
    R10: ffffffff8136ccc7 R11: 0000000000000000 R12: 0000000000000000
    R13: 0000000000000000 R14: 0000000000000070 R15: 0000000000000001
    FS:  0000000000000000(0000) GS:ffff88011fc00000(0000) knlGS:0000000000000000
    CS:  0010 DS: 0000 ES: 0000 CR0: 000000008005003b
    CR2: 0000000000000018 CR3: 00000000db10d000 CR4: 00000000000006f0
    Stack:
     ffff8800aac15d50 0000000000000011 ffff8800aac15db8 ffffffff812e2a70
     ffff880091a00600 0000000000000000 ffff8800aadc2bc3 00000000cd42c987
     ffff88003702df20 ffff88003702dfa0 0000000053b65c09 ffff8800aac15fd8
    Call Trace:
     [<ffffffff812e2a70>] ? keyring_detect_cycle_iterator+0x30/0x30
     [<ffffffff812e3e75>] keyring_gc+0x75/0x80
     [<ffffffff812e1424>] key_garbage_collector+0x154/0x3c0
     [<ffffffff810a67b6>] process_one_work+0x176/0x430
     [<ffffffff810a744b>] worker_thread+0x11b/0x3a0
     [<ffffffff810a7330>] ? rescuer_thread+0x3b0/0x3b0
     [<ffffffff810ae1a8>] kthread+0xd8/0xf0
     [<ffffffff810ae0d0>] ? insert_kthread_work+0x40/0x40
     [<ffffffff816ffb7c>] ret_from_fork+0x7c/0xb0
     [<ffffffff810ae0d0>] ? insert_kthread_work+0x40/0x40
    Code: 08 4c 8b 22 0f 84 bf 00 00 00 41 83 c7 01 49 83 e4 fc 41 83 ff 0f 4c 89 65 c0 0f 8f 5a fe ff ff 48 8b 45 c0 4d 63 cf 49 83 c1 02 <4e> 8b 34 c8 4d 85 f6 0f 84 be 00 00 00 41 f6 c6 01 0f 84 92
    RIP  [<ffffffff8136cea7>] assoc_array_gc+0x2f7/0x540
     RSP <ffff8800aac15d40>
    CR2: 0000000000000018
    ---[ end trace 1129028a088c0cbd ]---

[Comment 1 GLSAMaker/CVETool Bot 2014-10-05 21:17:15 UTC]

CVE-2014-3631 (http://nvd.nist.gov/nvd.cfm?cvename=CVE-2014-3631):
  The assoc_array_gc function in the associative-array implementation in
  lib/assoc_array.c in the Linux kernel before 3.16.3 does not properly
  implement garbage collection, which allows local users to cause a denial of
  service (NULL pointer dereference and system crash) or possibly have
  unspecified other impact via multiple "keyctl newring" operations followed
  by a "keyctl timeout" operation.

[Comment 2 Tomáš Mózes 2015-04-19 09:54:04 UTC]

Vulnerable versions not in tree.