Hacking a Virtual Power Plant

Trying Out the API

When I went to generate an API token, I was pleasantly surprised to find options for expiration time and fine-grained control over permissions. I clicked “generate”, and got:

From the eyJ prefix, I recognized a base64 encoded JSON object. Upon closer inspection, it turned out to be two JSON objects and some binary data, separated by periods:

More precisely, a JSON Web Token (JWT) signed with an RSA+SHA-256.

In the past, some JWT implementations allowed verification to be bypassed by changing the algorithm to “none”, so I tried that. It didn’t work, which was a relief. That signature though... 64 bytes? At eight bits per byte that’s 512 bits. But that would mean an easily crackable 512 bit RSA key. I hoped this wasn’t as bad as it seemed. Perhaps each account had a different key?

Signing Like It’s 1999

The first publicly known factorization of a 512 bit RSA modulus was completed in August of 1999.

[W]e estimate that within three years the algorithmic and computer technology which we used to factor RSA–155 will be widespread […]. This makes these keys useless for authentication or for the protection of data required to be secure for a period longer than a few days.

—Cavallar et al.

In 2009, several 512 bit RSA signing keys for Texas Instruments graphing calculators were cracked by hobbyists. The point was further driven home in 2015 by the factoring as a service paper:

In this paper, we present an improved implementation which is able to factor a 512-bit RSA key on Amazon EC2 in as little as four hours for $75.

—Valenta et al.

Despite this, many modern cryptography libraries still support using and even creating the these keys almost a decade later.

Recovering the Modulus

With the factors of the JWT private signing key, I could reconstruct the rest of the parameters and produce modified API tokens that should be accepted as valid. I’d factored eBay’s 512 bit DKIM key in April of 2012, so I had a pretty good idea of what to do. The problem was, I had nothing to factor. Just some signed data. Maybe I could use that to get what I needed?

Skip the rest of this section if you’re not interested in the math.

RSA needs three values to work, the modulus n, the private exponent d, and the public exponent e. An RSA signature is computed as s = m^d mod n — message m is raised to the power of d modulo n. It’s validated by checking that s^e mod n ≡ m. With the prime factors of n, it’s trivial to calculate d, and for a 512 bit key finding the prime factors is doable, but I didn’t have n or e. By convention, e is nearly always 65537, but I had no idea what n was. I do, however, know algebra.

Subtracting m from both sides of the signature verification equation gives s^e mod n − m ≡ 0. Since modular subtraction is associative, that also means that s^e − m mod n ≡ 0. The modulo operation finds the remainder, so s^e − m is an integer multiple of n. This is not useful on its own, but it means that with another message and signature, I’d have two different integer multiples of n. Running those through a GCD algorithm would give me n × x where x is a small integer, easily factored out by trial division.

This Isn’t Textbook RSA

The math above only covers “Textbook RSA” operating on raw numbers, which has a number of problems in practice. It can only operate on numbers smaller than the key’s modulus. The numbers also can’t be too small, otherwise various attacks are possible. To address this, the message is hashed and padded using PKCS #1 v1.5 encoding before being signed. Not wanting to deal with the encoding, I went looking for a pre-existing tool. After a few false starts, I found JWT-Key-Recovery, which quickly provided the modulus.

Cracking the Key

The modulus is generated by picking large prime numbers, usually denoted p and q, and multiplying them together. If you want more detail, please see my previous post, Artisnal RSA. The most efficient known algorithm for factoring the modulus back into primes is called general number field sieve (GNFS). This wasn’t my first time cracking an RSA key, but it’d been a while, so I found some instructions. I started cado-nfs on my workstation and let it run overnight. By the time I got done with work the next day, I was feeling impatient and rented a few hundred CPU cores to make it go faster. A few hours and a $70 compute bill later, I had the two prime numbers I needed.

Exploiting the Vulnerability

I used my own tool to generate the private key, made a trivial change to my API token, signed it, and made a request. It worked. I still wasn’t sure whether the key was specific to my account, so I needed another to try.

The easy way would have been to just try a random account id, but that would expose that customer’s personal information, which would be a bit rude to say the least. Poking around a bit, I noticed “View Demo Dashboard” on the login page. That’d do. A few minutes of fiddling with developer tools and I had the account id.

Changing the API token, I requested “my” account details:

The account ids seemed to be sequential, so I could just change that and access any of them. I had another look at the API documentation and saw there were some methods limited to “engineer+”. Plus? I tried setting the account id to “1”, figuring it’d probably be an admin account. Indeed it was, and seemingly subject to no permissions checks, as I could access data for my own system from it.

All your battery are belong to us.

The Vendor Response

Just before bed on July 8^th I sent off an email to their head of security[1] politely explaining what I’d done and why it was a problem. I included the following as proof:

A response was waiting for me in the morning, thanking me and making it clear that they were taking it seriously and a fix was their top priority.

I followed up thanking them for the update, and offering to confirm their fix for them when it was ready.

Their CTO followed up late that evening, thanking me again and asking if he could take me up on my offer to test their fix. Which was already deployed.

They did what now? I read the email again. Twice. I did some testing. They’d switch to a 4096 bit RSA key, but not only was I no longer able to mint my own API tokens, the legitimate ones I’d initially generated still worked. Was I dreaming?

My confirmation led with:

Wow, this is by far the best vendor response I’ve ever seen.

Seriously. A+++++ would tell them I pwned their stuff again.

They’ve posted their take on the issue.

The Bigger Picture

Expecting developers to know that 512 bit RSA is insecure clearly doesn’t work. They’re not cryptographers. This is not their job. The failure wasn’t that someone used 512 bit RSA. It was that a library they were relying on let them.

I’m in favor of task-oriented cryptography libraries which provide tools to solve problems without forcing non-experts to make security decisions.

Python’s cryptography library has been working to provide this, as well as the low level stuff for when it’s needed - they call it “hazmat”. It comes with a warning:

This is a “Hazardous Materials” module. You should ONLY use it if you’re 100% absolutely sure that you know what you’re doing because this module is full of land mines, dragons, and dinosaurs with laser guns.

Support for 512 bit RSA is a land mine, but it’s one that can be defused.

I’m now working to get major cryptography libraries to drop support for it.

Python’s cryptography library did so coincidentally in a release a few weeks ago (the commit was in January).

I’ve submitted a pull request to OpenSSL.

Similar changes for Go’s crypto library are now under discussion.

These changes will take some time to become widely distributed, but eventually people will no longer make this mistake.

This blog post was covered in Ars Technica.