Fun with Bignums: Crashing MatrixSSL and more
If you've been following my fuzzing work you will be aware that I've fuzzed various bignum libraries and found several bugs by comparing implementations against each other.
I recently had a look at the MatrixSSL's modular exponentiation function, for reasons I'll explain later. I wrote a wrapper, similar to previous experiments, comparing its result to OpenSSL.
I immediately noted that the pstm_exptmod() function of MatrixSSL has certain limitations that weren't documented. If one tries to calculate a modular exponentiation with the base equal to the modulus (a^b mod a, code) it would return an error. If one tries to calculate a modular exponentiation with the base zero (0^b mod a, code, CVE-2016-6885) it would crash with an invalid free operation, potentially leading to memory corruption.
In normal cryptographic operations these values should never appear. But these values are in many situations attacker controlled. One situation is during an RSA key exchange. What happens here is that a client encrypts a random secret with the server's key. However a malicious client could simply send a zero or the key's modulus here. I created a patch against openssl that allows to test this. Both values crash the MatrixSSL server. However the crash seems not to happen in pstm_exptmod(), it hits another bug earlier (CVE-2016-6886). In both cases the crash happens due to an invalid memory read in the function pstm_reverse(), which is not prepared for zero-sized inputs and will underflow the len variable.
The crashes have been fixed in 3.8.4, but the pstm_exptmod() function still doesn't accept these inputs. However it no longer crashes with a zero base. It may be possible that these issues can be triggered through other code paths. I haven't tested Diffie Hellman key exchanges, which also allows putting attacker-controlled values into a modular exponentiation.
This is an interesting class of bugs. Bignum functions often aren't designed to handle all inputs and only consider values that make sense in the context of the cryptographic operations. However if they are attacker-controlled this may lead to problems. I just discovered a somewhat similar issue in Nettle. They switched their RSA implementation from GMP's mpz_powm() function to mpz_powm_sec(), which is supposed to be sidechannel resistant. However mpz_powm_sec() is no drop-in replacement. Unlike mpz_pown() it doesn't accept even moduli and crashes with a floating point error. Therefore when trying to use a specifically crafted RSA key with an even modulus this will crash. Fortunately this was discovered before the change made it into a release.
But back to MatrixSSL: Independent of these corner case values that lead to failures I was able to identify an input value that caused a wrong calculation result (code,CVE-2016-6887.
There's a particularly severe risk with calculation errors in the modulo exponentiation when it comes to the RSA algorithm. A common way to speed up the calculation of RSA signatures is an algorithm based on the chinese remainder theorem (CRT) that splits it up into two smaller calculations. However if one of these calculations goes wrong an attacker can learn the private key. Last year Florian Weimer observed that various devices had this error and he could extract their keys. He recently mentioned on the oss-security mailing list that he also observed this in devices using MatrixSSL.
The way the MatrixSSL team "fixed" the miscalculation issue is not really satisfying: They now restrict the input to the pstm_exptmod() function to a set of bit sizes (512, 1024, 1536, 2048, 3072, 4096). My test input had a different bit size, therefore I cannot reproduce the miscalculation any more, but the underlying bug is most likely still there. I've tried to find inputs matching these restrictions and still causing wrong results, but without success yet. Independent of that the restriction means that connections to sites with unusual key sizes or Diffie Hellman moduli will no longer work. While they are not common, there is no rule that RSA keys or Diffie Hellman moduli need to have certain sizes.
Despite the fact that the bug may be still there the CRT attack will probably no longer work. A protection mechanism against that was implemented in version 3.8.3.
I got told by the MatrixSSL developers that their bignum code is based on libtommath. Therefore I also checked if the same bugs appeared there. That wasn't the case. The test input causing wrong results in MatrixSSL were correctly calculated by libtommath and it was also capable of correctly using a zero base or a base equal to the modulus.
I recently had a look at the MatrixSSL's modular exponentiation function, for reasons I'll explain later. I wrote a wrapper, similar to previous experiments, comparing its result to OpenSSL.
I immediately noted that the pstm_exptmod() function of MatrixSSL has certain limitations that weren't documented. If one tries to calculate a modular exponentiation with the base equal to the modulus (a^b mod a, code) it would return an error. If one tries to calculate a modular exponentiation with the base zero (0^b mod a, code, CVE-2016-6885) it would crash with an invalid free operation, potentially leading to memory corruption.
In normal cryptographic operations these values should never appear. But these values are in many situations attacker controlled. One situation is during an RSA key exchange. What happens here is that a client encrypts a random secret with the server's key. However a malicious client could simply send a zero or the key's modulus here. I created a patch against openssl that allows to test this. Both values crash the MatrixSSL server. However the crash seems not to happen in pstm_exptmod(), it hits another bug earlier (CVE-2016-6886). In both cases the crash happens due to an invalid memory read in the function pstm_reverse(), which is not prepared for zero-sized inputs and will underflow the len variable.
The crashes have been fixed in 3.8.4, but the pstm_exptmod() function still doesn't accept these inputs. However it no longer crashes with a zero base. It may be possible that these issues can be triggered through other code paths. I haven't tested Diffie Hellman key exchanges, which also allows putting attacker-controlled values into a modular exponentiation.
This is an interesting class of bugs. Bignum functions often aren't designed to handle all inputs and only consider values that make sense in the context of the cryptographic operations. However if they are attacker-controlled this may lead to problems. I just discovered a somewhat similar issue in Nettle. They switched their RSA implementation from GMP's mpz_powm() function to mpz_powm_sec(), which is supposed to be sidechannel resistant. However mpz_powm_sec() is no drop-in replacement. Unlike mpz_pown() it doesn't accept even moduli and crashes with a floating point error. Therefore when trying to use a specifically crafted RSA key with an even modulus this will crash. Fortunately this was discovered before the change made it into a release.
But back to MatrixSSL: Independent of these corner case values that lead to failures I was able to identify an input value that caused a wrong calculation result (code,CVE-2016-6887.
There's a particularly severe risk with calculation errors in the modulo exponentiation when it comes to the RSA algorithm. A common way to speed up the calculation of RSA signatures is an algorithm based on the chinese remainder theorem (CRT) that splits it up into two smaller calculations. However if one of these calculations goes wrong an attacker can learn the private key. Last year Florian Weimer observed that various devices had this error and he could extract their keys. He recently mentioned on the oss-security mailing list that he also observed this in devices using MatrixSSL.
The way the MatrixSSL team "fixed" the miscalculation issue is not really satisfying: They now restrict the input to the pstm_exptmod() function to a set of bit sizes (512, 1024, 1536, 2048, 3072, 4096). My test input had a different bit size, therefore I cannot reproduce the miscalculation any more, but the underlying bug is most likely still there. I've tried to find inputs matching these restrictions and still causing wrong results, but without success yet. Independent of that the restriction means that connections to sites with unusual key sizes or Diffie Hellman moduli will no longer work. While they are not common, there is no rule that RSA keys or Diffie Hellman moduli need to have certain sizes.
Despite the fact that the bug may be still there the CRT attack will probably no longer work. A protection mechanism against that was implemented in version 3.8.3.
I got told by the MatrixSSL developers that their bignum code is based on libtommath. Therefore I also checked if the same bugs appeared there. That wasn't the case. The test input causing wrong results in MatrixSSL were correctly calculated by libtommath and it was also capable of correctly using a zero base or a base equal to the modulus.