AddressSanitizer finding in lookup3.c

[noloader]

Hi Everyone,

I'm building Unbound 1.9.1 from the tarball on Fedora 29, x86_64. It has a modern version of GCC with sanitizers. The build adds CFLAGS+=-fsanitize=address and CXXFLAGS+=-fsanitize=address (and LDFLAGS+=-fsanitize=address as needed). Then I run make check to see what happens.

make check
...
libtool: link: gcc -I. -I/var/sanitize/include -DNDEBUG -I/var/sanitize/include -I/var/sanitize/include -I/var/sanitize/include -DSRCDIR=. -g2 -O2 -fsanitize=address -march=native -fPIC -pthread -fsanitize=address -Wl,-R -Wl,/var/sanitize/lib64 -Wl,--enable-new-dtags -o testbound .libs/testbound.o .libs/replay.o .libs/fake_event.o .libs/testpkts.o .libs/worker.o .libs/acl_list.o .libs/daemon.o .libs/stats.o .libs/shm_main.o .libs/dns.o .libs/infra.o .libs/rrset.o .libs/dname.o .libs/msgencode.o .libs/as112.o .libs/msgparse.o .libs/msgreply.o .libs/packed_rrset.o .libs/iterator.o .libs/iter_delegpt.o .libs/iter_donotq.o .libs/iter_fwd.o .libs/iter_hints.o .libs/iter_priv.o .libs/iter_resptype.o .libs/iter_scrub.o .libs/iter_utils.o .libs/localzone.o .libs/mesh.o .libs/modstack.o .libs/view.o .libs/outbound_list.o .libs/alloc.o .libs/config_file.o .libs/configlexer.o .libs/configparser.o .libs/fptr_wlist.o .libs/edns.o .libs/locks.o .libs/log.o .libs/mini_event.o .libs/module.o .libs/net_help.o .libs/random.o .libs/rbtree.o .libs/regional.o .libs/rtt.o .libs/dnstree.o .libs/lookup3.o .libs/lruhash.o .libs/slabhash.o .libs/tcp_conn_limit.o .libs/timehist.o .libs/tube.o .libs/winsock_event.o .libs/autotrust.o .libs/val_anchor.o .libs/validator.o .libs/val_kcache.o .libs/val_kentry.o .libs/val_neg.o .libs/val_nsec3.o .libs/val_nsec.o .libs/val_secalgo.o .libs/val_sigcrypt.o .libs/val_utils.o .libs/dns64.o .libs/cachedb.o .libs/redis.o .libs/authzone.o .libs/respip.o .libs/ub_event.o .libs/keyraw.o .libs/sbuffer.o .libs/wire2str.o .libs/parse.o .libs/parseutil.o .libs/rrdef.o .libs/str2wire.o .libs/strlcat.o .libs/strlcpy.o .libs/arc4random.o .libs/arc4random_uniform.o .libs/arc4_lock.o  -L/var/sanitize/lib64 -L/var/sanitize/lib -lssl -ldl -lpthread -lcrypto -lhiredis -pthread  -Wl,-rpath -Wl,/var/sanitize/lib
./unittest
Start of unbound 1.9.1 unit test.
test authzone functions
=================================================================
==23867==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fff1d847e80 at pc 0x0000004e0f5f bp 0x7fff1d847e30 sp 0x7fff1d847e20
READ of size 4 at 0x7fff1d847e80 thread T0
    #0 0x4e0f5e in hashlittle util/storage/lookup3.c:378
    #1 0x45ccac in rrset_key_hash util/data/packed_rrset.c:170
    #2 0x543ca5 in auth_packed_rrset_copy_region services/authzone.c:179
    #3 0x545b7e in msg_add_rrset_an services/authzone.c:234
    #4 0x545b7e in msg_add_rrset_an services/authzone.c:219
    #5 0x547621 in az_generate_positive_answer services/authzone.c:2811
    #6 0x547621 in az_generate_answer_with_node services/authzone.c:3062
    #7 0x547621 in auth_zone_generate_answer services/authzone.c:3157
    #8 0x557363 in auth_zones_lookup services/authzone.c:3194
    #9 0x4382fc in q_ans_query testcode/unitauth.c:775
    #10 0x4382fc in check_az_q_ans testcode/unitauth.c:830
    #11 0x4382fc in check_queries testcode/unitauth.c:852
    #12 0x4382fc in authzone_query_test testcode/unitauth.c:888
    #13 0x4382fc in authzone_test testcode/unitauth.c:899
    #14 0x406e2c in main testcode/unitmain.c:888
    #15 0x7fa0a952a412 in __libc_start_main ../csu/libc-start.c:308
    #16 0x40a54d in _start (/home/jwalton/Build-Scripts/unbound-1.9.1/unittest+0x40a54d)

Address 0x7fff1d847e80 is located in stack of thread T0 at offset 32 in frame
    #0 0x45cbcf in rrset_key_hash util/data/packed_rrset.c:163

  This frame has 1 object(s):
    [32, 34) 't' <== Memory access at offset 32 partially overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow util/storage/lookup3.c:378 in hashlittle
Shadow bytes around the buggy address:
  0x100063b00f80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100063b00f90: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100063b00fa0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100063b00fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100063b00fc0: 00 00 00 00 00 00 00 00 00 00 00 00 f1 f1 f1 f1
=>0x100063b00fd0:[02]f2 f2 f2 f3 f3 f3 f3 00 00 00 00 00 00 00 00
  0x100063b00fe0: 00 00 f1 f1 f1 f1 00 00 00 00 00 00 00 00 00 00
  0x100063b00ff0: 00 00 00 00 00 00 00 f2 f2 f2 f3 f3 f3 f3 00 00
  0x100063b01000: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100063b01010: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100063b01020: 00 00 00 00 f1 f1 f1 f1 04 f2 f2 f2 f2 f2 f2 f2
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==23867==ABORTING
gmake: *** [Makefile:311: test] Error 1
Failed to test Unbound
Failed to build Unbound

[noloader]

Oh my, you can't do this... That's a party foul!

First, reading beyond the array is undefined behavior in C. The code is illegal. Second, if that read crosses a page boundary and the subsequent page is not readable or not allocated, then the application will crash. Third, programs and libraries that depend upon Unbound will fail their testing due to Unbound.

The final reason to refrain is some folks will perform security testing and evaluation (ST&E). We will perform the acceptance testing, and grind on the code looking for weak spots with tools like Valgrind and Sanitizers. These kinds of findings waste your time and our time. And I am guessing the "savings" is 0.5 or 0.3 nano-seconds on a modern processor, which likely can't even be measured.

The "read off the existing page" got riskier since Stack Clash remediation are in place. Guard pages are no longer readable in some instances.

Stepping back a bit to 10,000 feet and looking at the high level engineering... You might consider using Aumasson and Bernstein's SipHash. It is a fast short-input PRF, it has proven security properties, and it has existing implementations in a number of libraries. There is no need to roll your own scheme or carry around the extra code.

---

    /*----------------------------- handle the last (probably partial) block */
    /*
     * "k[2]<<8" actually reads beyond the end of the string, but
     * then shifts out the part it's not allowed to read.  Because the
     * string is aligned, the illegal read is in the same word as the
     * rest of the string.  Every machine with memory protection I've seen
     * does it on word boundaries, so is OK with this.  But VALGRIND will
     * still catch it and complain.  The masking trick does make the hash
     * noticeably faster for short strings (like English words).
     */
#ifndef VALGRIND

    switch(length)
    {
    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
    case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
    case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
    case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
    case 8 : b+=k[1]; a+=k[0]; break;
    case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
    case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
    case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
    case 4 : a+=k[0]; break;
    case 3 : a+=k[0]&0xffffff00; break;
    case 2 : a+=k[0]&0xffff0000; break;
    case 1 : a+=k[0]&0xff000000; break;
    case 0 : return c;              /* zero length strings require no mixing */
    }

#else  /* make valgrind happy */

    k8 = (const uint8_t *)k;
    switch(length)                   /* all the case statements fall through */
    {
    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
    case 11: c+=((uint32_t)k8[10])<<8;  /* fall through */
    case 10: c+=((uint32_t)k8[9])<<16;  /* fall through */
    case 9 : c+=((uint32_t)k8[8])<<24;  /* fall through */
    case 8 : b+=k[1]; a+=k[0]; break;
    case 7 : b+=((uint32_t)k8[6])<<8;   /* fall through */
    case 6 : b+=((uint32_t)k8[5])<<16;  /* fall through */
    case 5 : b+=((uint32_t)k8[4])<<24;  /* fall through */
    case 4 : a+=k[0]; break;
    case 3 : a+=((uint32_t)k8[2])<<8;   /* fall through */
    case 2 : a+=((uint32_t)k8[1])<<16;  /* fall through */
    case 1 : a+=((uint32_t)k8[0])<<24; break;
    case 0 : return c;
    }

#endif /* !VALGRIND */

[wcawijngaards]

Hi noloader,
Yes, indeed, that hash function has some troublesome optimisations.
The page argument is not valid. The page boundaries are also on word boundaries, so that is not going to crash. Otherwise that would already crash.
But your other arguments are very real, and I agree that fixing this is good for security.
Thanks for the finding, I have closed it by making it respect the array boundaries.