An interesting, seemingly minor, flaw
Of the talks that I attended at Blackhat this year, the most interesting was about how mangling a carry bit in a P- 256 calculation enabled compromise of a private key. This is a big deal.
Elliptic curve cryptography
Modern encryption often uses Elliptic-curve cryptography. It is used in setting up secure communication channels between two computers, say your laptop and a web server. It is also used in “signing”, a way to be sure that a key piece of information has not been tampered with. One example of this is to verify that a web site is who it claims it is. There are several other uses described in Wikipedia.
For two parties to agree on the validity of keys that they are exchanging, some rather involved arithmetic with numbers that are 256 bits long, Since most hardware does at most 64-bit arithmetic, the program must use multi-precision arithmetic to do the calculations.
Thus, the program must mimic what you would do when you are adding or multiplying multi-digit numbers. If two digits added result in a number greater than 10, you need to carry the one to the next leftmost column. In the case of the cryptography, you need to account for two 64-bit numbers added together have a carry. With 64-bit numbers added together, the program needs to explicitly handle that case.
First Noted
One common validation step is done for web certificates. These are issued by a Certificate Authority, and are used by the browser in deciding whether to warn you about the web being trusted, or showing you the nice green lock symbol next to the web site address.
In April 2017, Cloudflare, an internet service provider, received an unexpected error in validating a known-good certificate. The validation was done using the Go language library. They filed an issue against crypto/elliptic. The error was in not properly handling the carry bit in multi-precision arithmetic.
Quick reaction
The Go team and Cloudflare fixed the problem in the arithmetic used to calculate the P-256 point for the latest release, but debated about fixing previous versions.
In commenting on the bug, several industry veterans (for example Adam Langley, who wrote the original code, but not the vulnerable part) expressed doubt about fixing older versions, saying that it was not evident that this could lead to damage other than the occasional failure. But Adam did state that “It would be a cool paper”. Further, he said “Thus this should be treated as something to fix, but not something on fire, based on what we currently know.” Let’s see how that worked out.
Challenge accepted
While not intended as a challenge by the commenters, after the bug was fixed, a two researcher, Filippo Valsorda and Sean Devlin, took it up.
Filippo the result of the work at the session titled Squeezing a Key through a Carry Bit. Filippo walked through the history of the bug, how it was repaired, then proceeded to illustrate how to use this flaw to extract the private key. Kangaroos played in important part in the description.
In the presentation, they demonstrated the method to use a simple server that accepts JWT tokens to exfiltrate the key a few bits at a time, leading to complete knowledge of the private key.
This is far from “not exploitable”, and it seems more like Game Over. Or “something on fire”.
Filppo’s next job was going to work for Google. They put him in charge of the crypto part of the Go language. I asked him if it was punishment for finding the bug, to which he laughed.
Enormous CPU cost?
The cost using cloud spot instances to compute this? What is your guess?
It was on the order of $65.
Lessons from this exercise
First, there is now a tighter recommendation against using assembler, which is what was used to speed up the key multiplication step in the library.
Second, and I think more importantly, the lesson is of the importance of Application Security–the skill in taking small flaws and describing how they can lead to serious compromise of systems. Several very smart folks didn’t think this was exploitable, but it in fact turned out to be “on fire”.
Sometimes significant discoveries are heralded by “That’s funny” as opposed to “Eureka!”. If you are building software and exposing it to the internet, you need a skill on your staff that can look for, find, and help fix these seemingly small flaws that can have out-sized impacts.
DO try this at home
If you would like to play along, you can head over to cryptopals to tune up your knowledge of how crypto can be broken, and when you have done those, go do the challenge that is now available for review.
Thanks
Thanks to Sean and Filppo and Ruth for reading early drafts of this article.