Havege does arithmetic on signed int

[gilles-peskine-arm]

Description

• Type: Bug
• Priority: Major

Runtime failure with Asan

1. Check out https://github.com/ARMmbed/mbedtls at f790a6c or https://github.com/ARMmbed/mbedtls/tree/mbedtls-2.16 at 20d707d or https://github.com/ARMmbed/mbed-crypto at 521dbc6.
2. Set the following configuration:
   scripts/config.pl full; scripts/config.pl unset MBEDTLS_MEMORY_BACKTRACE
   or
   scripts/config.pl full; scripts/config.pl unset MBEDTLS_MEMORY_BACKTRACE; scripts/config.pl unset MBEDTLS_MEMORY_BUFFER_ALLOC_C; scripts/config.pl unset MBEDTLS_MEMORY_DEBUG
3. Build with clang and ASan (I used clang 3.8.0 Ubuntu 16.04). I've reproduced it with both in-tree and out-of-tree builds, both with Asan and AsanDbg.

   mkdir build-asan
   cd build-asan
   CC=clang cmake -D CMAKE_BUILD_TYPE:String=AsanDbg .
   make -j3
   cd tests
   ./test_suite_entropy
   

4. Expected: the tests pass. Actual: ASan runtime errors like the following (the exact values change at every run):

   /tmp/mbedtls$ ./test_suite_entropy
   Create NV seed_file ............................................... PASS
   Entropy write/update seed file .................................... /tmp/mbedtls/library/havege.c:179:9: runtime error: left shift of 1813511924 by 23 places cannot be represented in type 'int'
   SUMMARY: AddressSanitizer: undefined-behavior /tmp/mbedtls/library/havege.c:179:9 in 
   /tmp/mbedtls$ ./test_suite_entropy
   Create NV seed_file ............................................... PASS
   Entropy write/update seed file .................................... /tmp/mbedtls/library/havege.c:179:9: runtime error: left shift of negative value -1080004887
   SUMMARY: AddressSanitizer: undefined-behavior /tmp/mbedtls/library/havege.c:179:9 in 
   

Note that I'm getting Asan complaints only with Clang, not with GCC. We run this test (in the configuration full minus MBEDTLS_MEMORY_BACKTRACE) on CI, but only with GCC, not with Clang, which is why we didn't notice sooner. I'm still surprised we never noticed in developer builds, though. I often test with clang+asan! So there may still be some extra condition needed to reproduce the complaints.

Analysis of havege.c

havege.c does indeed perform bit shifts on int that may cause an overflow. A shift that overflows a signed integer has undefined behavior in C. Asan's complaints are legitimate.

[gilles-peskine-arm]

Regardless of this potential bug in havege.c, I would recommend keeping MBEDTLS_HAVEGE_C disabled in most if not all environments. (It is disabled by default.) HAVEGE as a library is not very useful. But that doesn't excuse the undefined behavior, nor the strange way semi-reproducibility of ASan's warnings.