The Fuzzing Project

A bug in the NSS library can cause certain cryptographic calculations to produce wrong results. The bug is in the function mp_div(), this function gets used by the function mp_exptmod(), a combination of an exponentiation and a modulo operation. The mp_exptmod() function is used in several cryptographic algorithms, most notably it's the function to sign and encrypt with RSA and to calculate Diffie Hellman key exchanges. The NSS library is used for TLS connections in various Mozilla products.

This bug was found by comparing the results of NSS and OpenSSL bignum calculations and fuzzing the input with american fuzzy lop. A similar bug was also found and fixed in OpenSSL recently.

I first reported both issues separately, not knowing that they were caused by the same bug. In a first analysis both the Mozilla developers and I thought that the impact of the mp_div() bug would be minor, because it wasn't used in the cryptography code of NSS. But we overlooked that it was indirectly used through the mp_exptmod() function.

It is unclear what the exact impact and severity of this bug is. I am not aware of a practical way to exploit it, but as it affects important crypto code it might be possible to find exploitable scenarios.

I have published code examples with test inputs triggering the bug for both functions on Github. This bug is fixed in NSS 3.21 and in Firefox 44.

Mozilla Foundation Security Advisory 2016-07
Commit with the fix
Bug report for mp_div() (still private)
Bug report for mp_exptmod() (still private)
Example for mp_div()
Example for mp_exptmod()
CVE-2016-1938

The GNU Coreutils project has just released the new version 8.25 which fixes an out of bounds heap read bug in the shred tool that I reported. It is a nice example of the subtle bugs one can find by testing code with address sanitizer.

shred is a tool to overwrite files with random data before deleting them. It generates a random memory pattern and in this pattern generation there was a heap overread. Due to the random pattern generation this bug is not deterministic and one has to run shred with certain parameters (for example -n 20) multiple times to trigger it.

Upstream bug report
Git commit / fix
Coreutils 8.25 release notes

OpenVPN versions before 2.3.9 contain an out of bounds read error. The bug happens in the function resolve_remote() in the file socket.c.

I reported this bug to the OpenVPN security team on December 6th. I was informed that this was already reported to them previously and fixed in the repository. The new release 2.3.9 fixes this. The current git head code of OpenVPN has this code part completely reworked, it is thus not affected.

The reason for this bug is that for both IPv4 and IPv6 connections OpenVPN will read a struct sockaddr_in6, but in the IPv4 case the data structure is smaller than in the IPv6 case. The bug was found by trying to run OpenVPN with Address Sanitizer.

I don't know whether this is in any way exploitable, but as OpenVPN is a security sensitive software I found it worthy to make it public.

Today OpenSSL released a security advisory and updates for a carry propagation bug that I discovered in the BN_mod_exp() function. The bug is in the 1.0.2 branch of OpenSSL and is fixed in 1.0.2e. It only affects the x86_64 assembly optimizations. Other architectures and older versions are not affected.

The bug was introduced in commit this commit and fixed in this one. It got CVE-2015-0860 assigned. A simple proof of concept test can be found here.

Fuzzing Bignum libraries

This is not the first time a miscalculation bug was found in the bignum library of OpenSSL. In January OpenSSL already had to fix a bug in the squaring function BN_sqr(). Back then I already asked myself if it would be worthwhile to use fuzzing to find such bugs. The BN_sqr() bug was special that it only occurred on very rare occasions. Only one out of 2^128 inputs would produce a wrong result. That effectively means random testing will never find such a bug. However american fuzzy lop has shown to be surprisingly successful in finding hard to find bugs. In a talk given at the Black Hat conference Ralph-Philipp Weinmann showed that with a very simple test tool he was able to re-find the BN_sqr() bug in OpenSSL with american fuzzy lop.

Finding bugs we already know may give interesting insights, but what we really want to do is to find new bugs. I tried various strategies to fuzz bignum libraries. There are two basic options to do so:

1. Do a calculation with one bignum library and check it for consistencies. This depends on the calculation you do. An example would be a division function. If you divide a by b, store the result in r and the remainder in s then r*b+s must be a again. In case of the BN_sqr() bug a possibility is simply to compare the result of the squaring with a multiplication of a number by itself. They should produce the same result.
2. Do differential testing with two different implementations. You simply take two different bignum libraries, do the same operation and compare the results.

One small challenge is how you structure the input data. When you have a single input value it is easy: Just take the whole file and interpret it as a number. But for most functions you will have different input values. What I did was that I simply took the first two bytes and used them to decide how to split the rest of the file in pieces. To compare the results I used a simple assert call. In case an assert failure happens american fuzzy lop will detect that.

The BN_mod_exp() bug was found by comparing libgcrypt with OpenSSL. Unfortunately I have been sloppy with archiving my code and I lost the exact code that I used to fuzz the bug. But I think I recreated an almost functionally equivalent example. (I should mention that libfuzzer might be the better tool for this job, but I still haven't gotten around trying it out.)

Fuzzing is usually associated with typical memory corruption bugs. What these examples show is that you can use fuzzing to target entirely different classes of bugs. Essentially fuzz testing can target any kind of bug class that depends on an input and that has a testable failure state. For mathematics the failure state is pretty obvious: If the result of a calculation is wrong then there is a bug.

Fuzzing versus branch-free code

After reporting the bug I was asked by the OpenSSL developers if I could do a similar test on their HMAC implementation. I did that and the result is interesting. At first I was confused: A while after the fuzzing started american fuzzy lop was only reporting two code paths. Usually it finds dozends of code paths within seconds.

This happens because cryptographic code is often implemented in a branch-free way. That means that there are no if-blocks that will execute different parts of the code depending on the input. The reason this is done is to protect against all sorts of sidechannel attacks. This conflicts with the way modern fuzzers like american fuzzy lop or libfuzzer work. They use the detection of new code paths as a way to be smart about their inputs.

I don't want to suggest here that branch-free code is bad. I think the advantages of branch-free code are undisputed, but it's interesting to see that it can make fuzz testing harder.

In case you wonder why american fuzzy lop still found two code paths: The reason is likely the input length. The HMAC code is branch-free for each block, but if the block number changes you will get a different code path.

What's the impact?

Finally you may ask what the impact of the BN_mod_exp() bug is. This is in part still unknown and I can only offer a preliminary analysis.

The BN_mod_exp() function is used to exponentiate a number in a modulus (a^b mod m) and is used in many algorithms. It is the core of both RSA and Diffie Hellman. In the case of RSA I think it's unlikely that there is a vulnerability. A potential attacker has basically no control over the input values. The base is either random (RSA exchange) or a hash (DHE/ECDHE exchange). The exponent and the modulus are part of the key. I haven't looked into DSA, because nobody uses it.

Diffie Hellman looks more interesting. I first thought it's not interesting, because usually in a Diffie Hellman key exchange the secret key is only used for one connection. Therefore the only thing an attacker could do is attacking a connection that he himself is part of. That is unlikely to give him anything interesting. But Juraj Somorovsky pointed out to me that OpenSSL caches and reuses the ephemeral key for several Diffie Hellman exchanges until the application restarts. So it might be possible to construct an oracle that will extract this cached ephemeral key. I leave it to people who know more about cryptography and x64 assembly to decide whether that is the case.

The conclusions of the OpenSSl team in the advisory are similar to mine.

OpenSSL has an option to disable this key caching. This can be done by passing the SSL_OP_SINGLE_DH_USE (for classic Diffie Hellman) and SSL_OP_SINGLE_ECDH_USE (for Elliptic Curve Diffie Hellman) values to SSL_CTX_set_options(). In my opinion this should be the default, reusing the ephemeral key seems quite dangerous. Many popular applications, including the Apache web server, already set this option.

I invite everyone to analyze this further and try to come up with a practical attack.

Thanks to Tom Ritter, Ralph-Philipp Weinmann and Juraj Somorovsky for valuable discussions on the topic.

Two stack overflows and one stack out of bounds access were fixed in dpkg, the package management tool from Debian.

A call to the function read_line didn't consider a trailing zero byte in the target buffer and thus could cause a one byte stack overflow with a zero byte. This issue was already fixed in the testing code when I reported it, but the fix wasn't backported to stable yet.
Git commit / fix
Minimal PoC file
The Debian developers consider this as non-exploitable, therefore no CVE got assigned.

A second almost identical stack overflow due to a call to the function read_line was in the same file.
Minimal PoC file
This issues got the id CVE-2015-0860.

A stack out of bounds read can happen in the function dpkg_ar_normalize_name. There is a read access to an array where the index can have the value -1. A check if the index is a positive value fixes this.
Minimal PoC file

All issues were found with the help of american fuzzy lop and address sanitizer.

Debian has published the advisory DSA 3407-1. Fixes packages for both stable (Jessie) and oldstable (Wheezy) have been published.

Ubuntu has published the advisory USN-2820-1. Fixed packages for Ubuntu 15.10, 15.04 and the LTS versions 14.04 and 12.04 have been published.

The updates fix all three issues. All users of Ubuntu, Debian and other dpkg/apt-based distributions should update.

Zstandard or short zstd is a new compression algorithm and tool developed by Yann Collet. Fuzzing zstd with american fuzzy lop and address sanitizer uncovered two out of bounds reads.

Heap out of bounds read in function ZSTD_copy8:
Input sample
Upstream bug report
Git commit / fix

Stack out of bounds read in function HUF_readStats:
Input sample
Upstream bug report
Git commit / fix

The new zstd version 0.2.1 fixes both issues.

exfat-utils is a collection of tools to work with the exFAT filesystem. Fuzzing the exfatfsck with american fuzzy lop led to the discovery of a write heap overflow and an endless loop.

Especially at risk are systems that are configured to run filesystem checks automatically on external devices like USB flash drives.

A malformed input can cause a write heap overflow in the function verify_vbr_checksum. It might be possible to use this for code execution.
Upstream bug report
Sample file triggering the bug
Git commit for fix
CVE-2015-8026

Another malformed input can cause an endless loop, leading to a possible denial of service.
Upstream bug report
Sample file triggering the bug
Git commit of fix

Both issues have been fixed in the latest release 1.2.1 of exfat-utils.

OpenSSH 6.9 has been released yesterday and fixes two out of bounds read issues I had reported.

The first one is not very interesting. A null byte in a configuration file can cause an off-by-one read access. As a config file is not attacker controlled this doesn't have any security impact.

The second issue is an out of bounds read access in the function match_pattern_list() through the ssh handshake. I found this while experimenting with a way to do network fuzzing with american fuzzy lop via preloading a library that will intercept networking functions. I hope to be able to release the tool I use for it at some point, right now it's not really in a usable state. (I later learned that there is a similar tool called Preeny.)

The match_pattern_list() function had two strings and the length of the second string as parameters. The length of the first string was determined by strlen(). A call in the file combat.c called that function with the length of the first string as the parameter, causing an out of bounds read.

This issue can be reproduced by:
a) Compiling openssh 6.8p1 with address sanitizer (./configure CFLAGS="-fsanitize=address" LDFLAGS="-fsanitize=address"; make)
b) Running this netcat-command:
echo "SSH-2.0-OpenSSH_6.5"|nc -l -p 22
c) Connecting to it: ./ssh 127.0.0.1

OpenSSH fixed this by changing the function match_pattern_list() to accept only the two strings and checking both lengths with strlen().

Now there's a backstory to this. When I reported this to Damien Miller he considered it not security relevant and published the fix right away to the public git. It wasn't noticed by anyone until I briefly mentioned it in a post to the american fuzzy lop users mailing list. People started linking to this post on twitter so I thought I should explain it more detailed and wrote a message to oss-security. That only caused more (probably undeserved) attention, up to the point where some people would call it a high risk vulnerability.

Some people criticised me for calling this issue a heap overflow. This highlights a problem: The term buffer overflow and the related terms stack / heap overflow aren't defined in a strict way. Some consider only out of bounds writes an overflow (e. g. the CWE-120 definition), others also call out of bounds reads an overflow (e. g. Address Sanitizer). See also David Wheeler's discussion on Heartbleed. To avoid any confusion I decided for myself to use the term out of bounds read in the future for similar issues.

There are two takeaways for me from this story:
a) If you write about potential vulnerabilities in important security software it's hard to avoid that others will exaggerate the issue.
b) Vulnerability terminology can be ambiguous and is not always strictly defined.

Two memory access issues were found in the Courier mail server. These issues were discovered by compiling the software with Address Sanitizer (-fsanitize=address) and running the test suite.

In the file mailboxlist.c, part of the IMAP folder parser, there is a memcmp call checking whether the fist six bytes of a string match "SHARED". However the string can be less than six bytes, which will cause an out of bounds read access. This issue is unlikely to cause much trouble.

In the mailbot tool (mailbot.c) there is a memory allocation for a zero-terminated list of pointers. The allocation only reserves one byte for the zero termination, however it must be the size of the pointer (8 bytes on 64 bit systems). Therefore it causes a write heap overflow of seven zero bytes. The code parses command line data, therefore it is unlikely that any attacker controlled input is affected.

Both issues have been reported to Courier's developer Sam Varshavchik on 27th June 2015 and were fixed with the release of courier 0.75 on 29th June 2015.

Commit / Patch (bundles some unrelated changes, the relevant parts are in mailbot.c and mailboxlist.c)
Courier 0.75 release announcement

Lately I started an effort to systematically fuzz all possible file input vectors of OpenSSL. This led to the discovery of one potential security issue and two minor non-security fixes.

Malformed inputs can cause an out of bounds heap read access in the function X509_cmp_time. This issue was reported to the OpenSSL developers on 11th March. It was independently discovered three days earlier by Google developer Robert Swiecki.

During the fuzzing I also discovered several issues in the parser of ASN1 definition files. These can be used to create ASN1 data structures with OpenSSL. It is unlikely that there is any situation where ASN1 definitions are attacker controlled, therefore these are not considered security issues.

The latest security updates of OpenSSL (1.0.2b, 1.0.1n, 1.0.0s, 0.9.8zg) fix all three issues. These releases also fix a number of other security issues. Shortly after publishing these updates OpenSSL issued another update (1.0.2c, 1.0.1o), because the versions contained an ABI change which should not happen in minor releases.

I am aware that a couple of other people were also fuzzing OpenSSL lately. Noteworthy is one issue that was found by Joseph Birr-Pixton in the parser of elliptic curve parameters. It is an endless loop and can be used to hang processes with a high CPU load. Endless loop issues tend to get ignored because they are often false positives.

It is definitely getting harder finding any new issues through fuzzing in OpenSSL. This is good news.

Out of bounds read in X509_cmp_time
CVE-2015-1789
Git commit / fix
OpenSSL Security Advisory
Sample malformed cert (test with openssl verify [input])

Samples for issues in ASN1 definition parser (test with openssl asn1parse -genconf [input]):
Out of bounds read heap
Stack overflow through endless recursion
Uninitialized memory access

Update: Around one year after these bugs were reported it turned out that one of the issues is actually more severe than we thought.

uudecode is a tool to decode uuencoded data. It is shipped with the package sharutils.

An invalid input file can cause an out of bounds stack read access in the function expand_tilde(). This issue has been reported to the developers on 2015-03-04. It has been fixed in sharutils 4.15.2 (2015-05-30).

To see this bug one needs to use a tool like valgrind or address sanitizer that detects out of bounds memory reads. The bug was found with american fuzzy lop.

Sample file

Address sanitizer output:

==8209==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fff8a4a8690 at pc 0x40738d bp 0x7fff8a4a44a0 sp 0x7fff8a4a4490
READ of size 1 at 0x7fff8a4a8690 thread T0
#0 0x40738c in expand_tilde /mnt/ram/sharutils-4.14/src/uudecode.c:252
#1 0x40738c in decode /mnt/ram/sharutils-4.14/src/uudecode.c:437
#2 0x403660 in main /mnt/ram/sharutils-4.14/src/uudecode.c:530
#3 0x7f13d97fff9f in __libc_start_main (/lib64/libc.so.6+0x1ff9f)
#4 0x403c81 (/mnt/ram/sharutils-4.14/src/uudecode+0x403c81)

Address 0x7fff8a4a8690 is located in stack of thread T0 at offset 16800 in frame
#0 0x403da7 in decode /mnt/ram/sharutils-4.14/src/uudecode.c:362

This frame has 7 object(s):
[32, 36) 'mode'
[96, 104) 'outlen'
[160, 168) 'ctx'
[224, 368) 'attr'
[416, 16800) 'buf' <== Memory access at offset 16800 overflows this variable
[16832, 33216) 'buf_in'
[33248, 49632) 'buf'

While fuzzing SQLite I discovered two read heap overflow errors. One is in the database file parser, one in the sql command parser. Both issues are present in SQLite 3.8.9 and are fixed in SQLite 3.8.10.1. These bugs can be seen with either valgrind or address sanitizer.

Passing the command ".\" will cause a one byte heap overflow in the function resolve_backslashes().
Sample input file (test with sqlite3 < [inputfile])
Upstream commit / patch

Parsing a malformed database file will cause a heap overflow of several bytes in the function sqlite3VdbeExec(). This only matters if your attack scenario involves parsing untrusted database files.
Sample input file (test with sqlite3 [inputfile] .dump)
Upstream commit / patch

Please also note:
Finding bugs in SQLite, the easy way - Michal Zalewski fuzzed SQLite with a dictionary - most of these were already fixed in 3.8.9, the version I was testing.
SQL Fuzz Using The American Fuzzy Lop Fuzzer - SQLite developers themselve now use regular fuzz testing to find further bugs.
SQLite 3.8.10.1 release notes mention fixes for "many obscure problems discovered while SQL fuzzing", so there are likely more fixes than the two I mentioned above.

While fuzzing GnuTLS I discovered a malformed certificate input sample that would cause a heap overflow read of 99 bytes in the DER decoding functions of Libtasn1. The heap overflow happens in the function _asn1_extract_der_octet().

This issue was reported to the Libtasn1 developer on 16th April. A fix was committed on 20th April and is part of the Libtasn1 4.5 release. This issue was found with american fuzzy lop and address sanitizer.

Git commit / fix
Libtasn1 4.5 release notes
Sample malformed certificate exposing heap overflow (test with certtool -i --inder --infile=[sample] and address sanitizer or valgrind)
CVE-2015-3622

Today version 7.42.0 of curl was released. It fixes two vulnerabilities and one not security relevant bug that I found via fuzzing and reported.

When fuzzing an application the question is always which input vector you fuzz. The tool american fuzzy lop is purely file-based, therefore one needs some kind of file input to fuzz an application. Curl has a couple of potentially interesting file inputs.

One feature of curl is to save cookies to a file and later re-use that cookie file for followup connections. By fuzzing these inputs I found out that using a double-quote character (") as the path causes a memory access to a -1 index of an array. This could also be triggered by a malicious webpage.

The other input vector I fuzzed was the config file. Usually config files are not attacker-controlled, so one may question whether this makes sense at all. But here's what happened: The config file allows to pass an URL to curl and by that I found an out ouf bounds memory access in the URL parser. And an URL can be attacker controlled in many situations (for example through HTTP forwards). So the takeaway message here is that testing input vectors that are never attacker controlled (like config files) may still uncover potential security issues, because they might trigger code paths that matter in other situations.

All issues were reported to the curl security team on 16th April 2015 and are fixed in curl 7.42.0. Thanks to Daniel Stenberg of the curl team who quickly fixed all the issues I reported. Please also note that curl 7.42.0 fixes two other unrelated security issues.

cookie parser out of boundary memory access (cURL Security Advisory)
Patch
Git commit
CVE-2015-3145
Sample file (test with curl -b)

host name out of boundary memory access (cURL Security Advisory)
Patch
Git commit
CVE-2015-3144
Sample file (test with curl -K on the sample or just curl :0

Git commit for non-security config file parser issue
Sample file (test with curl -K)

GnuPG is a popular E-Mail encryption solution. GnuPG also ships a tool gpgsm that can be used to sign and encrypt mails according to the S/MIME standard. To parse S/MIME data structures the library libksba is used. GpgOL is a GnuPG-based plugin to use OpenPGP-encryption in Microsoft Outlook.

Fuzzing various input vectors of GnuPG led to the discovery of several potential security issues.

An integer overflow in the BER decoder of libksba can lead to an invalid write / heap overflow. This is fixed in libksba 1.3.3.

Git commit / fix
Sample file (test with gpgsm --verify)

An invalid UTF-8 encoding can cause an assert in libksba. This may be abused to crash / DoS an application. This is fixed in libksba 1.3.3.

Git commit / fix
Sample file (test with gpgsm --verify)

A stack overflow in an internal stack of the BER decoder of libksba can be abused to crash / DoS an application. This is fixed in libksba 1.3.3.

Git commit / fix
Sample file (test with gpgsm --verify)

An invalid mail header can cause an off by one read access / heap overflow in the tool gpgparsemail, which is part of GnuPG. The same code is present in GpgOL, a plugin to use OpenPGP encryption in Microsoft Outlook. The gpgparsemail issue is fixed in GnuPG 2.1.3. There is no new release of GpgOL yet.

(Due to an incomplete fix there are two commits each.)

Git commit 1 for gpgparsemail / GnuPG
Git commit 2 for gpgparsemail / GnuPG
Git commit 1 for GpgOL
Git commit 2 for GpgOL
Sample file for original issue
Sample file for incomplete fix

A malformed packet could cause GnuPG to detect a negative packet length. The size variable is unsigned, resulting in an malloc call to a very large value and a crash / DoS. This is fixed in GnuPG 2.1.3.

Git commit / fix
Sample file for malloc DoS (test with gpg --import or gpg --list-packets)

A malformed private key can cause a null pointer access when trying to import the key. This came too late for GnuPG 2.1.3 and is not yet fixed in a release.

Git commit / fix
Sample file (test with gpg --verify)