4 ms·

That bignum one is weird. The patch suggests the character of it: something in the carry logic between 32-bit words, replicated for each assembly architecture a

by tlb 12y ago

That bignum one is weird. The patch suggests the character of it: something in the carry logic between 32-bit words, replicated for each assembly architecture as well as C. Here's the C version: #define mul_add_c2(a,b,c0,c1,c2) { \ BN_ULONG ta=(a),tb=(b),t0; \ BN_UMULT_LOHI(t0,t1,ta,tb); \ - t2 = t1+t1; c2 += (t2<t1)?1:0; \ - t1 = t0+t0; t2 += (t1<t0)?1:0; \ - c0 += t1; t2 += (c0<t1)?1:0; \ + c0 += t0; t2 = t1+((c0<t0)?1:0);\ c1 += t2; c2 += (c1<t2)?1:0; \ + c0 += t0; t1 += (c0<t0)?1:0; \ + c1 += t1; c2 += (c1<t1)?1:0; \ } The test case adds this number: 0x80000000000000008000000000000001FFFFFFFFFFFFFFFE0000000000000000 If you were wondering whether OpenSSL code has really gotten too complicated, wonder no more. Full patch: https://github.com/openssl/openssl/commit/e078642ddea29bbb6ba29788a6a513796387fbbb#diff-6dd63052b7680975a9eeb33dca68da52L478 https://github.com/openssl/openssl/commit/e078642ddea29bbb6b...

fulafel 12y ago
Relevant snippet from advisory: "Bignum squaring (BN_sqr) may produce incorrect results on some platforms, including x86_64. This bug occurs at random with a very low probability, and is not known to be exploitable in any way, though its exact impact is difficult to determine. The following has been determined: - The probability of BN_sqr producing an incorrect result at random is very low: 1/2^64 on the single affected 32-bit platform (MIPS) and 1/2^128 on affected 64-bit platforms. - On most platforms, RSA follows a different code path and RSA operations are not affected at all. For the remaining platforms (e.g. OpenSSL built without assembly support), pre-existing countermeasures thwart bug attacks [1]. - Static ECDH is theoretically affected: it is possible to construct elliptic curve points that would falsely appear to be on the given curve. However, there is no known computationally feasible way to construct such points with low order, and so the security of static ECDH private keys is believed to be unaffected. - Other routines known to be theoretically affected are modular exponentiation, primality testing, DSA, RSA blinding, JPAKE and SRP. No exploits are known and straightforward bug attacks fail - either the attacker cannot control when the bug triggers, or no private key material is involved. [...] This issue was reported to OpenSSL on 2nd November 2014 by Pieter Wuille (Blockstream) who also suggested an initial fix. Further analysis was conducted by the OpenSSL development team and Adam Langley of Google. The final fix was developed by Andy Polyakov of the OpenSSL core team. "
- nullc 12y ago
  The issue was that one of the carry propagation conditions was missed. The bug was discovered as part of the development of libsecp256k1, a high performance (and hopefully high quality: correct, complete, side-channel resistant) implementation of the cryptographic operators used by Bitcoin, developed primarily by Bitcoin Core developer Pieter Wuille along with a number of other people. Part of our testing involves an automatic test harness that verifies agreement of our code with other implementations with random test data, including OpenSSL; though to reduce the chance of an uncontrolled disclosure we backed out some of the low level testing after discovering this bug. This randomized testing revealed the flaw in OpenSSL. I suppose it's also a nice example of statistical reasoning (p=2^-128 that a uniform input triggers the misbehaviour) doesn't itself express risk, since while we've put enormous amounts of CPU cycles into tests we've certainly not done 2^128 work. In this case the reason our testing revealed the issue was because we used non-uniform numbers specifically constructed with low transition probability to better trigger improbable branches like carry bugs (https://github.com/bitcoin/secp256k1/blob/master/src/testrand_impl.h#L45 https://github.com/bitcoin/secp256k1/blob/master/src/testran...). I used the same technique in the development of the Opus audio codec to good effect. (Whitebox fuzzing tools like Klee or AFL, or branch coverage analysis, while good tools, seem to not be as effective for errors where the code completely omits a condition rather than having a wrong condition which was not exercised by tests.) In libsecp256k1 the field operations (nearest parallel, we don't use generic bignums) are augmented with proofs of correctness (e.g. https://github.com/bitcoin/secp256k1/blob/master/src/field_10x26_impl.h#L810 https://github.com/bitcoin/secp256k1/blob/master/src/field_1... ) though only a small part of our provable correctness can be machine checked currently. Of course, correctness proofs are only one part of our strategy. Fortunately, because of the much smaller scope of libsecp256k1 we likely have an easier time hitting a higher level of assurance than OpenSSL does. We were initially unsure how serious the bug was and came up with several sophisticated attacks that were fortunately prevented by OpenSSL not using its optimized squaring operation in all the places it could have used it. Perhaps most interesting is that one of the reference implementations of curve25519 had almost exactly the same bug as OpenSSL: https://gist.github.com/CodesInChaos/8374632 https://gist.github.com/CodesInChaos/8374632 but it seems to have gone largely without notice.
pbsd 12y ago
It's not really fair to indict this bug on OpenSSL's complexity. Over the last couple of years, both NaCl [1] and TweetNaCl [2] had carry propagation bugs not unlike the above. I'm surprised this kind of bug is not found more often. [1] http://tweetnacl.cr.yp.to/tweetnacl-20140917.pdf http://tweetnacl.cr.yp.to/tweetnacl-20140917.pdf [2] http://blog.skylable.com/2014/05/tweetnacl-carrybit-bug/ http://blog.skylable.com/2014/05/tweetnacl-carrybit-bug/
- nullc 12y ago
  I'm only not surprised because of the very poor state of software assurance in the industry as a whole. Indeed, the issue is not OpenSSL specific, similar bugs have been made elsewhere (and I assume also carried forward in "more audited" OpenSSL forks). But thats the only reason I'm not surprised. Cryptographic code is safety/security critical and as an implementer (In my experience) the potential for this kind of error is very clear. This class of mistake can be found with a strong testing and verification strategy: it can be found with correctly targeted randomized tests (as was the case for this CVE), it can be found via manual review, or it can be found via formal methods. Widely deployed, high value cryptographic code should be using all these techniques and producing publicly visible evidence of their use. Of course, serious software issues aren't just cryptographic ones. Systems programming, as an industry needs to up its game. (And the common tropes of higher level languages to save everything is countered by examples like this: Software safety and correctness is more than memory safety. Higher level tools can be useful, but if they get in the way of really rigorous reasoning about the software they may be counter-productive.)
rab_oof 12y ago
It's clear LibreSSL is only a half measure. TLS is far too complicated with design-by-committee, special vendor extension sauce nonsense. Heck, the FIPS code was rushed and basically done at the behest of US/Canadian govts. OpenSSL should consider burning their deadwood and stop adding features until it gets its house in order. There's no telling how large of an attack surface remains at the protocol level, in the codebase and with CAs being compelled to issue rogue certs for MITMs. Moreover: Can TLS features be narrowed to focus on popular and high-value use-cases instead of SCTP, UDP, oh look a bird feature? It's fine for hacking on, but not production code. (If "TLS" is evolutionarily to "Perl," who's working on a "Python"?) BTW: What ever happened to the cert WoT overlay 'moxie0 was working on?
- nanolith 12y ago
  It is true that TLS is part of the problem. But, it is also a widely deployed standard that cannot be changed overnight. That's why LibreSSL is necessary. We need to build simpler protocols that make better use of cryptographic primitives, but first, we have to push back the tide. Eventually, TLS will be superseded by a better standard. But, this is something that even if started today with the most aggressive schedule would take 5 to 10 years to go industry-wide.
- tptacek 12y ago
  It was scaled back to TACK, a TLS extension that decentralizes certificate authority, which competed with HPKP, a similar but less ambitious standard; HPKP seems to have won. It's not optimal but it's progress.
rab_oof 12y ago
I'm working on a research language with an extra set "explicit math operators" which expose carry in, carry out, etc. explicitly, and doesn't do type promotions and signals errors on under/ overflow. "+!" If you want C-like behavior. It'll be imperative with full dependent types as well. Also interesting: cryptol, Irdis, coq, but the work is on making generic systems programming clear as possible in a static, imperative language without a titanic runtime or crawling along with superfluous assertions.
- nullc 12y ago
  Carry bugs in limbed bignum code don't usually result in integer overflow (though integer overflow does usually mean the code is busted for sure). Part of the reason for this is that it's common to use 'overcomplete' representations where the limbs are smaller than the underlying type so that multiple operations can be performed before propagating the carries all at once. This class of error is very much behind all the noise making I did at the Rust development team about treating integer overflow as a first class cause of software disaster as much as they have memory safety. Fortunately, they seem to be moving off the everything-wraps and wrapping-is-always-fine position.
scottpiper 12y ago
KryptosLogic has a good write-up on this showing how it can be detected with Z3: http://kryptoslogic.blogspot.com/2015/01/openssls-squaring-bug-and-opportunistic.html http://kryptoslogic.blogspot.com/2015/01/openssls-squaring-b...

by tlb 12y ago

fulafel 12y ago

Relevant snippet from advisory: "Bignum squaring (BN_sqr) may produce incorrect results on some platforms, including x86_64. This bug occurs at random with a very low probability, and is not known to be exploitable in any way, though its exact impact is difficult to determine. The following has been determined: - The probability of BN_sqr producing an incorrect result at random is very low: 1/2^64 on the single affected 32-bit platform (MIPS) and 1/2^128 on affected 64-bit platforms. - On most platforms, RSA follows a different code path and RSA operations are not affected at all. For the remaining platforms (e.g. OpenSSL built without assembly support), pre-existing countermeasures thwart bug attacks [1]. - Static ECDH is theoretically affected: it is possible to construct elliptic curve points that would falsely appear to be on the given curve. However, there is no known computationally feasible way to construct such points with low order, and so the security of static ECDH private keys is believed to be unaffected. - Other routines known to be theoretically affected are modular exponentiation, primality testing, DSA, RSA blinding, JPAKE and SRP. No exploits are known and straightforward bug attacks fail - either the attacker cannot control when the bug triggers, or no private key material is involved. [...] This issue was reported to OpenSSL on 2nd November 2014 by Pieter Wuille (Blockstream) who also suggested an initial fix. Further analysis was conducted by the OpenSSL development team and Adam Langley of Google. The final fix was developed by Andy Polyakov of the OpenSSL core team. "

nullc 12y ago
The issue was that one of the carry propagation conditions was missed. The bug was discovered as part of the development of libsecp256k1, a high performance (and hopefully high quality: correct, complete, side-channel resistant) implementation of the cryptographic operators used by Bitcoin, developed primarily by Bitcoin Core developer Pieter Wuille along with a number of other people. Part of our testing involves an automatic test harness that verifies agreement of our code with other implementations with random test data, including OpenSSL; though to reduce the chance of an uncontrolled disclosure we backed out some of the low level testing after discovering this bug. This randomized testing revealed the flaw in OpenSSL. I suppose it's also a nice example of statistical reasoning (p=2^-128 that a uniform input triggers the misbehaviour) doesn't itself express risk, since while we've put enormous amounts of CPU cycles into tests we've certainly not done 2^128 work. In this case the reason our testing revealed the issue was because we used non-uniform numbers specifically constructed with low transition probability to better trigger improbable branches like carry bugs (https://github.com/bitcoin/secp256k1/blob/master/src/testrand_impl.h#L45 https://github.com/bitcoin/secp256k1/blob/master/src/testran...). I used the same technique in the development of the Opus audio codec to good effect. (Whitebox fuzzing tools like Klee or AFL, or branch coverage analysis, while good tools, seem to not be as effective for errors where the code completely omits a condition rather than having a wrong condition which was not exercised by tests.) In libsecp256k1 the field operations (nearest parallel, we don't use generic bignums) are augmented with proofs of correctness (e.g. https://github.com/bitcoin/secp256k1/blob/master/src/field_10x26_impl.h#L810 https://github.com/bitcoin/secp256k1/blob/master/src/field_1... ) though only a small part of our provable correctness can be machine checked currently. Of course, correctness proofs are only one part of our strategy. Fortunately, because of the much smaller scope of libsecp256k1 we likely have an easier time hitting a higher level of assurance than OpenSSL does. We were initially unsure how serious the bug was and came up with several sophisticated attacks that were fortunately prevented by OpenSSL not using its optimized squaring operation in all the places it could have used it. Perhaps most interesting is that one of the reference implementations of curve25519 had almost exactly the same bug as OpenSSL: https://gist.github.com/CodesInChaos/8374632 https://gist.github.com/CodesInChaos/8374632 but it seems to have gone largely without notice.

pbsd 12y ago

It's not really fair to indict this bug on OpenSSL's complexity. Over the last couple of years, both NaCl [1] and TweetNaCl [2] had carry propagation bugs not unlike the above. I'm surprised this kind of bug is not found more often. [1] http://tweetnacl.cr.yp.to/tweetnacl-20140917.pdf http://tweetnacl.cr.yp.to/tweetnacl-20140917.pdf [2] http://blog.skylable.com/2014/05/tweetnacl-carrybit-bug/ http://blog.skylable.com/2014/05/tweetnacl-carrybit-bug/

nullc 12y ago
I'm only not surprised because of the very poor state of software assurance in the industry as a whole. Indeed, the issue is not OpenSSL specific, similar bugs have been made elsewhere (and I assume also carried forward in "more audited" OpenSSL forks). But thats the only reason I'm not surprised. Cryptographic code is safety/security critical and as an implementer (In my experience) the potential for this kind of error is very clear. This class of mistake can be found with a strong testing and verification strategy: it can be found with correctly targeted randomized tests (as was the case for this CVE), it can be found via manual review, or it can be found via formal methods. Widely deployed, high value cryptographic code should be using all these techniques and producing publicly visible evidence of their use. Of course, serious software issues aren't just cryptographic ones. Systems programming, as an industry needs to up its game. (And the common tropes of higher level languages to save everything is countered by examples like this: Software safety and correctness is more than memory safety. Higher level tools can be useful, but if they get in the way of really rigorous reasoning about the software they may be counter-productive.)

rab_oof 12y ago

It's clear LibreSSL is only a half measure. TLS is far too complicated with design-by-committee, special vendor extension sauce nonsense. Heck, the FIPS code was rushed and basically done at the behest of US/Canadian govts. OpenSSL should consider burning their deadwood and stop adding features until it gets its house in order. There's no telling how large of an attack surface remains at the protocol level, in the codebase and with CAs being compelled to issue rogue certs for MITMs. Moreover: Can TLS features be narrowed to focus on popular and high-value use-cases instead of SCTP, UDP, oh look a bird feature? It's fine for hacking on, but not production code. (If "TLS" is evolutionarily to "Perl," who's working on a "Python"?) BTW: What ever happened to the cert WoT overlay 'moxie0 was working on?

nanolith 12y ago
It is true that TLS is part of the problem. But, it is also a widely deployed standard that cannot be changed overnight. That's why LibreSSL is necessary. We need to build simpler protocols that make better use of cryptographic primitives, but first, we have to push back the tide. Eventually, TLS will be superseded by a better standard. But, this is something that even if started today with the most aggressive schedule would take 5 to 10 years to go industry-wide.
tptacek 12y ago
It was scaled back to TACK, a TLS extension that decentralizes certificate authority, which competed with HPKP, a similar but less ambitious standard; HPKP seems to have won. It's not optimal but it's progress.

rab_oof 12y ago

I'm working on a research language with an extra set "explicit math operators" which expose carry in, carry out, etc. explicitly, and doesn't do type promotions and signals errors on under/ overflow. "+!" If you want C-like behavior. It'll be imperative with full dependent types as well. Also interesting: cryptol, Irdis, coq, but the work is on making generic systems programming clear as possible in a static, imperative language without a titanic runtime or crawling along with superfluous assertions.

nullc 12y ago
Carry bugs in limbed bignum code don't usually result in integer overflow (though integer overflow does usually mean the code is busted for sure). Part of the reason for this is that it's common to use 'overcomplete' representations where the limbs are smaller than the underlying type so that multiple operations can be performed before propagating the carries all at once. This class of error is very much behind all the noise making I did at the Rust development team about treating integer overflow as a first class cause of software disaster as much as they have memory safety. Fortunately, they seem to be moving off the everything-wraps and wrapping-is-always-fine position.

scottpiper 12y ago

KryptosLogic has a good write-up on this showing how it can be detected with Z3: http://kryptoslogic.blogspot.com/2015/01/openssls-squaring-bug-and-opportunistic.html http://kryptoslogic.blogspot.com/2015/01/openssls-squaring-b...