releases/3.16.3/keys-fix-termination-condition-in-assoc-array-garbage-collection.patch

   1 From 95389b08d93d5c06ec63ab49bd732b0069b7c35e Mon Sep 17 00:00:00 2001
   2 From: David Howells <dhowells@redhat.com>
   3 Date: Wed, 10 Sep 2014 22:22:00 +0100
   4 Subject: KEYS: Fix termination condition in assoc array garbage collection
   5
   6 From: David Howells <dhowells@redhat.com>
   7
   8 commit 95389b08d93d5c06ec63ab49bd732b0069b7c35e upstream.
   9
  10 This fixes CVE-2014-3631.
  11
  12 It is possible for an associative array to end up with a shortcut node at the
  13 root of the tree if there are more than fan-out leaves in the tree, but they
  14 all crowd into the same slot in the lowest level (ie. they all have the same
  15 first nibble of their index keys).
  16
  17 When assoc_array_gc() returns back up the tree after scanning some leaves, it
  18 can fall off of the root and crash because it assumes that the back pointer
  19 from a shortcut (after label ascend_old_tree) must point to a normal node -
  20 which isn't true of a shortcut node at the root.
  21
  22 Should we find we're ascending rootwards over a shortcut, we should check to
  23 see if the backpointer is zero - and if it is, we have completed the scan.
  24
  25 This particular bug cannot occur if the root node is not a shortcut - ie. if
  26 you have fewer than 17 keys in a keyring or if you have at least two keys that
  27 sit into separate slots (eg. a keyring and a non keyring).
  28
  29 This can be reproduced by:
  30
  31         ring=`keyctl newring bar @s`
  32         for ((i=1; i<=18; i++)); do last_key=`keyctl newring foo$i $ring`; done
  33         keyctl timeout $last_key 2
  34
  35 Doing this:
  36
  37         echo 3 >/proc/sys/kernel/keys/gc_delay
  38
  39 first will speed things up.
  40
  41 If we do fall off of the top of the tree, we get the following oops:
  42
  43 BUG: unable to handle kernel NULL pointer dereference at 0000000000000018
  44 IP: [<ffffffff8136cea7>] assoc_array_gc+0x2f7/0x540
  45 PGD dae15067 PUD cfc24067 PMD 0
  46 Oops: 0000 [#1] SMP
  47 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
  48 CPU: 0 PID: 26011 Comm: kworker/0:1 Not tainted 3.14.9-200.fc20.x86_64 #1
  49 Hardware name: Bochs Bochs, BIOS Bochs 01/01/2011
  50 Workqueue: events key_garbage_collector
  51 task: ffff8800918bd580 ti: ffff8800aac14000 task.ti: ffff8800aac14000
  52 RIP: 0010:[<ffffffff8136cea7>] [<ffffffff8136cea7>] assoc_array_gc+0x2f7/0x540
  53 RSP: 0018:ffff8800aac15d40  EFLAGS: 00010206
  54 RAX: 0000000000000000 RBX: 0000000000000000 RCX: ffff8800aaecacc0
  55 RDX: ffff8800daecf440 RSI: 0000000000000001 RDI: ffff8800aadc2bc0
  56 RBP: ffff8800aac15da8 R08: 0000000000000001 R09: 0000000000000003
  57 R10: ffffffff8136ccc7 R11: 0000000000000000 R12: 0000000000000000
  58 R13: 0000000000000000 R14: 0000000000000070 R15: 0000000000000001
  59 FS:  0000000000000000(0000) GS:ffff88011fc00000(0000) knlGS:0000000000000000
  60 CS:  0010 DS: 0000 ES: 0000 CR0: 000000008005003b
  61 CR2: 0000000000000018 CR3: 00000000db10d000 CR4: 00000000000006f0
  62 Stack:
  63  ffff8800aac15d50 0000000000000011 ffff8800aac15db8 ffffffff812e2a70
  64  ffff880091a00600 0000000000000000 ffff8800aadc2bc3 00000000cd42c987
  65  ffff88003702df20 ffff88003702dfa0 0000000053b65c09 ffff8800aac15fd8
  66 Call Trace:
  67  [<ffffffff812e2a70>] ? keyring_detect_cycle_iterator+0x30/0x30
  68  [<ffffffff812e3e75>] keyring_gc+0x75/0x80
  69  [<ffffffff812e1424>] key_garbage_collector+0x154/0x3c0
  70  [<ffffffff810a67b6>] process_one_work+0x176/0x430
  71  [<ffffffff810a744b>] worker_thread+0x11b/0x3a0
  72  [<ffffffff810a7330>] ? rescuer_thread+0x3b0/0x3b0
  73  [<ffffffff810ae1a8>] kthread+0xd8/0xf0
  74  [<ffffffff810ae0d0>] ? insert_kthread_work+0x40/0x40
  75  [<ffffffff816ffb7c>] ret_from_fork+0x7c/0xb0
  76  [<ffffffff810ae0d0>] ? insert_kthread_work+0x40/0x40
  77 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
  78 RIP  [<ffffffff8136cea7>] assoc_array_gc+0x2f7/0x540
  79  RSP <ffff8800aac15d40>
  80 CR2: 0000000000000018
  81 ---[ end trace 1129028a088c0cbd ]---
  82
  83 Signed-off-by: David Howells <dhowells@redhat.com>
  84 Acked-by: Don Zickus <dzickus@redhat.com>
  85 Signed-off-by: James Morris <james.l.morris@oracle.com>
  86 Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
  87
  88 ---
  89  lib/assoc_array.c |    4 +++-
  90  1 file changed, 3 insertions(+), 1 deletion(-)
  91
  92 --- a/lib/assoc_array.c
  93 +++ b/lib/assoc_array.c
  94 @@ -1723,11 +1723,13 @@ ascend_old_tree:
  95                 shortcut = assoc_array_ptr_to_shortcut(ptr);
  96                 slot = shortcut->parent_slot;
  97                 cursor = shortcut->back_pointer;
  98 +               if (!cursor)
  99 +                       goto gc_complete;
 100         } else {
 101                 slot = node->parent_slot;
 102                 cursor = ptr;
 103         }
 104 -       BUG_ON(!ptr);
 105 +       BUG_ON(!cursor);
 106         node = assoc_array_ptr_to_node(cursor);
 107         slot++;
 108         goto continue_node;