Fuzzing Math - miscalculations in OpenSSL's BN_mod_exp (CVE-2015-3193)
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.
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.
Trackbacks
The Fuzzing Project on : nss: Wrong calculation results in mp_div() and mp_exptmod()
Show preview
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_ex
Comments
Display comments as Linear | Threaded
Pascal Cuoq on :
http://pastebin.com/rdLyQRVU
I think that the code is clearer once the patch is applied (the title of the blog post that goes with the patch is “When in doubt, express intent, and leave the rest to the compiler”), and it remains in my queue of patches to discuss when all null pointer dereferences from failed malloc() calls in OpenSSL are fixed.
Richard Könning on :