If you’ve been tracking the ebb and flow of news related to the Heartbleed vulnerability, you may remember how what at first seemed like good news about the limited potential for a worst-case scenario attack quickly turned south when a challenge held by Web security company CloudFlare proved the flaw could indeed be exploited.
Today the person who won the CloudFlare challenge, Rubin Xu, a security researcher and PhD candidate at Cambridge University in the UK, revealed how he did it. (The post was republished on Ars Technica, which is where I first read it.)
Xu’s post gets into a lot of technical detail but what it comes down to is this: Knowing the right kind of number to look for out of data pilfered from a server compromised by the Heartbleed bug.
It’s helpful here to remember what the Heartbleed bug allows, and why it’s so nasty: An attacker can use it to gain access to data that is stored in main memory on a server, essentially grabbing random scoops of data that might contain pretty much anything stored there in the normal course of the server’s operation.
RSA keys are used to generate server certificates, which are sort of like a Web server’s driver’s license, and used to authenticate a server’s identity. If private server keys can be stolen, fake certificates can be generated, and servers can be impersonated. The result: The next time you sign on to your bank’s website, you might actually be signing on to a fake server set up to look just like it, and then give up your account information to whoever set it up. That’s Heartbleed’s worst-case scenario and the reason why companies rushed to address it, generating new server keys and certificates in recent weeks.
So back to Xu’s explanation for how he stole the keys in the CloudFlare test, thus confirming that Heartbleed was indeed the big deal that everyone said it was. The way RSA keys work — and I’m likely going to strain the details in the interest of simplicity here — is that a big number (N) is created by multiplying two randomly generated prime numbers (p and q). There’s more on the math of RSA keys in this Wikipedia article.
The result of that multiplication is a numerical public key that can be shared with other users. The two prime numbers used to generate it are kept secret. Theoretically you can break the key by figuring out what those secret numbers are.
Where Heartbleed comes in, Xu explains, is that a server stores those secret numbers in memory in order to use the key. Once a Heartbleed attack has taken place it’s simply a matter of scanning the resulting data for the right kinds of numbers (prime numbers that are 1,024 bits long) and dividing them into the number used for the public key using trial and error. Several people who defeated the CloudFlare challenge did it this way.
Xu’s research found a better and faster way to figure out what one of those secret numbers was by determining that one of them was leaking out of a vulnerable server’s memory (more on that here). Suffice to say, it was a pretty impressive feat of mathematical and computational reasoning that led him to that realization. CloudFlare CEO Matthew Prince called Xu’s “the most sophisticated we saw,” of those who attempted to defeat the challenge.
— Matthew Prince (@eastdakota) April 27, 2014