Hi all,

TL;DR userspace fuzzing may be very effective for finding bugs in
crypto code, but might require some kernel-side changes.

When the attached binary file,
crash-bbeda07d4ce60cf3b7fc20c3af92297e19f6dbae, is passed as payload
to add_key("asymmetric", "desc", payload, len), it triggers a
slab-out-of-bounds KASAN report (see below). This can be reproduced
with the attached program, add_key.c.

We found this bug by fuzzing asn1_ber_decoder() in the userspace using
libFuzzer (http://llvm.org/docs/LibFuzzer.html).
The trick is to compile and link together several translation units
that provide a transitive closure of asn1_ber_decoder() (some of the
kernel functions need to be re-implemented to run in the userspace).
I've attached the resulting fuzzer as well (asn1_fuzzer.tar.gz). It
can operate on its own, although better results are achieved when
using the fuzzing corpus from
https://github.com/google/boringssl/tree/master/fuzz and
https://github.com/openssl/openssl/tree/master/fuzz.

The question I'd like to raise is the testability of the crypto code
in the kernel.

Right now it's quite hard to extract the implementation of e.g.
message parsers to run them in the userspace, although there's nothing
kernel-specific in those algorithms. For example, I haven't managed to
quickly build a similar fuzzer for decoding PKCS7 messages, because of
too many extra dependencies.
I've started looking into linking libFuzzer into an UML build, but
that's also pretty invasive.

The main reason for testing this code in the userspace is speed.
Syzkaller fuzzing the add_key() syscall in the kernel can operate at
the speed of maybe 2000 executions per second (usually a lot less),
whereas a libFuzzer-based userspace fuzzer can run tens of thousands
tests per second. This will sure shed some light into the dark corners
and perhaps find more bugs. Once we are there, it should be easy to
leverage the power of https://github.com/google/oss-fuzz to automate
the fuzzing.

Could it be possible to decouple the parsing algorithms from the rest
of kernel-specific crypto code? Maybe someone has other ideas about
how this code can be ran in the userspace?

Alex.

KASAN report below:

==================================================================
BUG: KASAN: slab-out-of-bounds in x509_fabricate_name.constprop.1+0x19f/0x940
Read of size 128 at addr ffff8800334747af by task add_key/2599

CPU: 0 PID: 2599 Comm: add_key Not tainted 4.14.0+ #1289
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Bochs 01/01/2011
Call Trace:
 __dump_stack lib/dump_stack.c:17
 dump_stack+0x90/0x10e lib/dump_stack.c:53
 print_address_description+0x65/0x270 mm/kasan/report.c:252
 kasan_report_error mm/kasan/report.c:351
 kasan_report+0x251/0x340 mm/kasan/report.c:409
 memcpy+0x1f/0x50 mm/kasan/kasan.c:302
 x509_fabricate_name.constprop.1+0x19f/0x940
crypto/asymmetric_keys/x509_cert_parser.c:366
 asn1_ber_decoder+0x9cf/0x1dc0 lib/asn1_decoder.c:447
 x509_cert_parse+0x1c2/0x600 crypto/asymmetric_keys/x509_cert_parser.c:89
 x509_key_preparse+0x5c/0x850 crypto/asymmetric_keys/x509_public_key.c:174
 asymmetric_key_preparse+0x8e/0xe0 crypto/asymmetric_keys/asymmetric_type.c:388
 key_create_or_update+0x4d3/0x1080 security/keys/key.c:855
 SYSC_add_key security/keys/keyctl.c:122
 SyS_add_key+0x145/0x280 security/keys/keyctl.c:62
 entry_SYSCALL_64_fastpath+0x13/0x6c arch/x86/entry/entry_64.S:203
...
Allocated by task 2599:
 set_track mm/kasan/kasan.c:459
 kasan_kmalloc+0xa0/0xd0 mm/kasan/kasan.c:551
 __kmalloc_node+0x7d/0x240 mm/slub.c:3807
 kvmalloc ./include/linux/mm.h:540
 SYSC_add_key security/keys/keyctl.c:104
...
Freed by task 7:
 set_track mm/kasan/kasan.c:459
 kasan_slab_free+0x71/0xc0 mm/kasan/kasan.c:524
 slab_free_hook mm/slub.c:1391
 slab_free_freelist_hook mm/slub.c:1412
 slab_free mm/slub.c:2968
 kfree+0x88/0x190 mm/slub.c:3899
 __rcu_reclaim kernel/rcu/rcu.h:190
 rcu_do_batch kernel/rcu/tree.c:2758
 invoke_rcu_callbacks kernel/rcu/tree.c:3012
 __rcu_process_callbacks kernel/rcu/tree.c:2979
 rcu_process_callbacks+0x58e/0x1cb0 kernel/rcu/tree.c:2996
 __do_softirq+0x1e6/0x696 kernel/softirq.c:285

The buggy address belongs to the object at ffff880033474780
 which belongs to the cache kmalloc-96 of size 96
The buggy address is located 47 bytes inside of
 96-byte region [ffff880033474780, ffff8800334747e0)
The buggy address belongs to the page:
page:ffffea0000cd1d00 count:1 mapcount:0 mapping:          (null) index:0x0
flags: 0x100000000000100(slab)
raw: 0100000000000100 0000000000000000 0000000000000000 0000000180200020
raw: ffffea0000cd35c0 0000000800000008 ffff880035c01780 0000000000000000
page dumped because: kasan: bad access detected

Memory state around the buggy address:
 ffff880033474680: fb fb fb fb fb fb fb fb fb fb fb fb fc fc fc fc
 ffff880033474700: fb fb fb fb fb fb fb fb fb fb fb fb fc fc fc fc
>ffff880033474780: 00 00 00 00 00 00 00 00 06 fc fc fc fc fc fc fc
                                           ^
 ffff880033474800: 00 00 00 00 00 00 00 00 00 00 00 fc fc fc fc fc
 ffff880033474880: fb fb fb fb fb fb fb fb fb fb fb fb fc fc fc fc
==================================================================


-- 
Alexander Potapenko
Software Engineer

Google Germany GmbH
Erika-Mann-Straße, 33
80636 München

Geschäftsführer: Paul Manicle, Halimah DeLaine Prado
Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg