4 ms·
BN_mod_exp may produce incorrect results on x86_64 (CVE-2015-3193) This one is absolutely terrifying. There are common ways that TLS stacks break: Generally s
by cperciva 11y ago
BN_mod_exp may produce incorrect results on x86_64 (CVE-2015-3193)
This one is absolutely terrifying. There are common ways that TLS stacks break: Generally speaking, bugs in parsing certificates, bugs in the protocol handling, and side channel attacks on the cryptography. These are risks which we aim to work around -- just like infections are a known complication of surgery, and antibiotic prophylaxis is recommended in some cases.
A bug which results in multiplication producing the wrong answers is in a completely different category. This is a "never event", akin to a surgical scalpel being left inside a patient after surgery or the wrong leg being amputated.
- danielhlockard 11y agoIt at least sounds, theoretically, hard to execute?
- jerf 11y agoI believe cperciva's more trying to convey deep existential angst moreso than immediate threat. His post is shot in black and white, as he is smoking while sitting in an cafe on an otherwise abandoned European street, when the desultory wind blows in a creased newspaper with the headline "MODULAR MATH FOUND NOT TO WORK", and he turns to look at the camera with a slowly developing look of pure horror that the camera person spends a full 5 minutes in exploring every last nuance of. Just over two minutes in, a violinist wearing a tutu wanders in, plays some 12-tone music, delivers a poorly subtitled rumination on the ultimate futility of life and its connection to prime number elliptic curves, and then leaves, for no apparent reason. It's moving stuff, for certain audiences.
- badloginagain 11y agoI thought Cryptography was interesting, but I didn't know it was that interesting...
- cperciva 11y agoMaybe. The problem with getting such fundamental things wrong is that it's almost impossible to figure out every possible way to exploit it. I haven't looked at the code in question, but I'd be willing to bet that the NSA has figured out a way to exploit the broken multiplication which is completely unlike what the OpenSSL authors were considering.
- peterwwillis 11y agoOff topic, but tools left inside patients is common enough to be in the "risks we try to avoid" category. https://en.wikipedia.org/wiki/Retained_surgical_instruments https://en.wikipedia.org/wiki/Retained_surgical_instruments
- cperciva 11y agoSure, and "multiplication produces incorrect results" can be avoided by careful code review. It's still a "never event", and in a completely different category from postoperative infections.
- sneak 11y agoThe "goto fail;" was the one that really terrified me, as it is something that can be caught by straightforward (even black-box) testing (which was not being done for some reason by the largest corporation in the world).
- snthd 11y agoI think this is one of the things targeted by running through a check list (like flying). Could that approach help for code?
- 0x0 11y agoCan this bug cause invalid or easily breakable private keys?
- cperciva 11y agoI certainly wouldn't be surprised.
- tptacek 11y agoI would be. How un-surprised would you be? Enough to bet?
- cperciva 11y agoNot without looking at the code first. But the first thing which comes to mind is accidentally generating RSA primes which aren't prime because the broken multiplication makes a SPSP test accidentally pass. Granted, finding a concrete example would probably be very difficult, considering that replacing modexp by rand() is only going to pass N as a suspected prime with probability 1/N; but the question was can it, not will anyone ever find an example.
- ecesena 11y agoNot private key in public-key schemes (RSA, DH), because these are generally random integer and BN_mod_exp is not used in private key generation -- but it's used in public key generation so the result could be an invalid key pair. In addition, I think it could produce a wrong symmetric key, as a result of a bad computation e.g. in the Diffie-Hellman protocol. So you could have insecure symmetric (e.g., AES) keys.
- tptacek 11y agoRalf-Phillip Weinmann had a good Black Hat presentation about this bug class. It might not be online yet. He's part of one of a couple of efforts to come up with fuzzing and validation tools to find things like carry propagation bugs in bignum libraries. The good news about this particular bug is that carry propagation bugs are well-studied (they seem to be the textbook case of a bignum math bug), and if OpenSSL says they've scoped down the places this bug impacts, they're probably right. I don't know if it mitigates your existential dread, but carry propagation bugs in multiplication routines are not in fact all that rare.
- deleted 11y ago[deleted]
- cperciva 11y agocarry propagation bugs are well-studied True. But they tend to be well-studied by computer security people, not by mathematicians; and most computer security people won't have the necessary number theory / group theory background. This is precisely the class of bugs for which proper assessment requires mathematicians who study computer security... aka. NSA employees.
- Ar-Curunir 11y agoYou'll be surprised by the background of many computer security people. It's a varied field consisting of people with all kinds of backgrounds.
- jagger27 11y agoAnecdote: a computer security professor at my university has deep roots in biology. Everything he touches has traces of evolution and homeostasis.
- cperciva 11y agoMy background is mathematics too. But I'm not a mathematician, and I wouldn't trust myself to know enough mathematics to figure out how something like this could be exploited.
- hannob 11y agoEarlier this year a very similar bug was already found in OpenSSL (in BN_sqr). So it's already a "twice in a year just in OpenSSL" event.
- Quiark 11y agoI have only basic knowledge of this but it feels like it should be possible to mathematically prove the correctness of bignum implementation, even if it's in C, no? And it would be very valuable work too.