Heartbleed: I'm thinking BIGNUM

On Friday night, I started up my 'heartleech' program slurping down data from www.cloudflarechallenge.com at 30-mbps, then went to bed. The next day, I had over 100-gigabytes of data, but I couldn't find the private key. What was the bug in my code that prevented me from finding it? I spent two days trying to solve this problem, it was very frustrating.

The answer was "byte-order". I was looking for the prime factor in the same way that it'd appear in a DER0-encoded file, which is "big-endian". Instead, the way to look for the key is in little-endian format.

I've misread the OpenSSL code before, but my feeling is that this comes from the "BIGNUM" representation in OpenSSL. RSA key and it's constituent factors are all just integers that are thousands of bits long. Because they don't fit in normal 64-bit integers, they require a special library to manipulate them. The big-endian byte arrays are extracted from the private key file, then converted into the internal representation, at which point you can call functions to add, subtract, multiply, and so on.

The internal representation for OpenSSL is as a series of integers, with low-order integers first. Since the integers on Intel x86 are also little-endian, this means that the internal representation is just byte-swapped from the external form. This would not be the case on something like Solaris SPARC, which has big-endian integers. OpenSSL still stores the array of integers least-significant first, but each integer itself will be big-endian.

My guess is that the reason we can find the prime factors is that there is some BIGNUM memory sitting around that shouldn't be.

What's really annoying is that I started down this BIGNUM path, but then some other people won the www.cloudeflarechallenge.com using Python scripts. I therefore made the assumption that Python used an external big-endian form, so I chose that instead. I then tested my code and successfully found the prime factors when reading from DER encoded private key files. So I knew my code was correct. But then my code didn't find the prime factors in the data I dumped from CloudFlare. Moreover, I couldn't test their Python scripts, because the files I created from the dumps were 13-gigs in size. Their scripts would first read in the entire file before parsing it -- and would barf at 13-gigs. I have some small 400-meg files -- but none of them contain the key. Sigh.