13 Aug 2009
Timing attacks are pretty horrible from the perspective of someone trying to write a secure cryptosystem. They work against a programmer’s best instincts—don’t do extra work—to give an attacker with access to a Statistics 101 textbook a good solid grip on your application’s guts.
In short, a timing attack uses statistical analysis of how long it takes your application to do something in order to learn something about the data it’s operating on. For HMACs, this means using the amount of time your application takes to compare a given value with a calculated value to learn information about the calculated value.
Take the recent Keyczar vulnerability that Nate Lawson found. He was able to take the fact that Keyczar used a simple break-on-inequality algorithm to compare a candidate HMAC digest with the calculated digest.
This is the offending code in Python:
and in Java:
A value which shares no bytes in common with the secret digest will return immediately; a value which shares the first 15 bytes will return 15 compares later. That’s a difference of perhaps microseconds, but given enough attempts—which is usually easy to arrange in web applications (how many of you throttle requests with bad session cookies?)—the random noise becomes a very predictable, normally distributed skew, leaving only the signal.
Oh, but it is.
I can choose what message I want to be authenticated—let’s say a session cookie with a specific user ID—and then calculate 256 possible values:
0000000000000000000000000000000000000000 0100000000000000000000000000000000000000 0200000000000000000000000000000000000000 ... snip 250 ... FD00000000000000000000000000000000000000 FE00000000000000000000000000000000000000 FF00000000000000000000000000000000000000
I go through each of these values until I find one—
A100000000000000000000000000000000000000—that takes a fraction of a
millisecond longer than the others. I now know that the first byte of what the
HMAC for that message should be is
A1. Repeat the process for the remaining
19 bytes, and all of a sudden I’m logged in as you.
Right about now, most people are thinking about the improbability of measuring the difference between two array comparisons in a web application, given all the routers, parsers, servers, proxies, etc. in the way.
According to Crosby et al.’s Opportunities And Limits Of Remote Timing Attacks: > We have shown that, even though the Internet induces significant timing > jitter, we can reliably distinguish remote timing differences as low as 20µs. > A LAN environment has lower timing jitter, allowing us to reliably distinguish > remote timing differences as small as 100ns (possibly even smaller). These > precise timing differences can be distinguished with only hundreds or possibly > thousands of measurements.
So. Almost microsecond resolution with hundreds to thousands of measurements. Who wants to bet that network jitter compensation models get worse instead of better?
A worst-case scenario for guessing an HMAC would require
\(20 \times 256 \times
n\) measurements, where
\(n\) is the number of measurements required to pin
down a single byte. So—around 5,000,000 requests. You could do that in less than
a week at a barely-perceptible 10 req/s.
It’s an attack which takes some planning and analysis, but it’s viable.
Instead of using a variable-time algorithm for comparing secrets, you should be using constant-time algorithms. Lawson recommends something like the following in Python:
In Java, that would look like this:
Oh, if only.
Check out what’s inside of
java.security.MessageDigest as recently as Java 6.0
Yep. Byte-by-byte comparison; returns on first inequality. Just what we don’t need.
I’ll be blunt here: any Java application which compares client-provided data
to a secret value using
MessageDigest.isEqual is vulnerable to timing
attacks. This includes HMACs, decryption results, etc.
I reported this to Sun on July 22nd, 2009. It’s Bug # 6863503, which isn’t publicly viewable due to the security concerns. Besides the automated email with the ticket number, I haven’t heard anything from Sun since then. In my bug report, I was explicit about my intent to follow through according to the RFPolicy, which says
D. If the MAINTAINER goes beyond 5 working days without any communication to the ORIGINATOR, the ORIGINATOR may choose to disclose the ISSUE. The MAINTAINER is responsible for providing regular status updates (regarding the resolution of the ISSUE) at least once every 5 working days.
So here I am, fully disclosing a rather large cryptographic vulnerability in one of the largest programming platforms there is. I can’t tell if that’s terrible or awesome.
Replace your usage of
MessageDigest.isEqual with a constant-time algorithm,
like the one above.
Every time you compare two values, ask yourself: what could someone do if they knew either of these values? If the answer is at all meaningful, use a constant-time algorithm to compare them.
This would be substantially less of an issue if more cryptographic libraries had better encapsulation. An HMAC is not just a series of characters or bytes—why treat it as such? Why have such a crucial piece of cryptography squirt out its state for others to man-handle?
As sophacles on Hacker News pointed out, I had overly refactored the suggested constant-time algorithms and introduced a more subtle timing attack vulnerability via the return statement’s boolean expression short-circuit. The algorithm has been updated to fix this.
The timing attack vulnerability in
MessageDigest was fixed in
Java SE 6 Update 17.