Hacker News Reader

Comment by cperciva | Hacker News Reader

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.

View on HN

Ralf-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.

carry 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.

You'll be surprised by the background of many computer security people. It's a varied field consisting of people with all kinds of backgrounds.

My 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.

Anecdote: a computer security professor at my university has deep roots in biology. Everything he touches has traces of evolution and homeostasis.

>Ralf-Phillip Weinmann had a good Black Hat presentation about this bug class.

https://www.youtube.com/watch?v=PqW8-MUu09c

https://comsecuris.com/research/slides-bignum-bhus2015.pdf

Earlier 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.

I 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.

Off 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

Sure, 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.

The "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).

I think this is one of the things targeted by running through a check list (like flying). Could that approach help for code?

Can this bug cause invalid or easily breakable private keys?

Not 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.

I certainly wouldn't be surprised.

I would be. How un-surprised would you be? Enough to bet?

Not 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.

It at least sounds, theoretically, hard to execute?

I 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.

I thought Cryptography was interesting, but I didn't know it was that interesting...

Maybe. 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.

Reply on news.ycombinator.com