Hacker News Reader

Comment by richm44 | Hacker News Reader

I'm saying they're unfixable because there's no way to tell the JIT to create constant-time code. Certainly Christopher Meyer has said that he's reported some that remain private since they've not been fixed.

Heartbleed was certainly easier to exploit, than a timing attack - no disagreement there. But the Java SSL stack is pretty flakey and largely seems to be unused. It has lots of interoperability problems with other implementations and generally seems immature. It's not something I'd trust in production myself.

View on HN

Right - it is looking more and more like truly constant time code can only be obtained by using hand written assembly or hardware. In that eventuality, I guess the core crypto code in the JVM will have to be changed to use hand written assembly as well, however, SSL is huge and most of it doesn't need to be constant time (certificate parsing, managing network buffers, message parsing etc). That is often where the bugs creep in.

Going with JSSE does have the downside that it's less widely used. Browser makers don't patch it with the latest gizmos like they do with OpenSSL. However, it's at least got a full time development team (unlike OpenSSL until very recently), and ultimately if there are odd conformance bugs lurking the only way they'll be shaken out is by people using it for real. Passing the Qualys test is a good start, but for now my little website is ideal because it is unlikely to ever be popular enough to have serious scaling issues and I can tolerate some incompatibility with odd clients.

"Right - it is looking more and more like truly constant time code can only be obtained by using hand written assembly or hardware. In that eventuality, I guess the core crypto code in the JVM will have to be changed to use hand written assembly as well, however, SSL is huge and most of it doesn't need to be constant time (certificate parsing, managing network buffers, message parsing etc). That is often where the bugs creep in."

I completely agree with you there. X.509 is a nightmare and it's not an area where constant time matters at all. Being resistant to buffer overruns and general logic errors is much more important there.

X.509 is a nightmare because it is complex, and the political infrastructure is vulnerable.

There is no reason ciphers like djb's that use data-independent code paths couldn't be integrated into X.509 if the will was there. Totally separate issues.

> can only be obtained by using hand written assembly or hardware

Even that is harder than it looks.

For example, a common way of doing a constant time string compare is:

    $result |= (ord($safe[$i % $safeLen]) ^ ord($user[$i]));

i.e. get the character to compare mod the length, so you wrap around if the length of the two strings is not the same.

Unfortunately the mod operator does not take a constant time on a CPU! If the result is evenly divisible it's faster.

So even in assembly you might not be able to protect from a timing attack. Even if you check your current CPU a new one might be different.

(In this case a better way to do the compare is if the strings are not the same length, compare the attackers string against itself, and then return false.)

(In this case a better way to do the compare is if the strings are not the same length, compare the attackers string against itself, and then return false.)

Is there a reason for using the attacker's string rather than the valid string? Edit: it doesn't seem to me that using the valid string would leak its length unless the attacker knew quite a lot about the target machine.

How long it takes to do the comparison reveals the length of the string being checked, so you have to check the string which the attacker knows the length of already.

> Edit: it doesn't seem to me that using the valid string would leak its length unless the attacker knew quite a lot about the target machine.

It sounds like you are skeptical that timing attacks can be practically exploited. This is a reasonable skepticism that most people go through on initially learning about them. Unfortunately, there are in fact working exploits for this sort of thing.

No, I definitely realize the seriousness of timing attacks. I'm just curious about this particular implementation detail. I would have guessed that using the attacker's length would reveal more about the system than using a fixed length (unless the length of the valid string changed frequently). I'd like to understand why that isn't the case.

Ah, I see, you're assuming the "valid" string is fixed-width across all requests. I guess in that specific case you might be right. But it's easy for that not to be the case: e.g. if there are several different resources an attacker can request that have different-length strings. For example, an attacker might scan for users with short (=bad) passwords by comparing the time it takes to complete an authentication check against various users. So the safe thing to go is to go with the attacker's string.

What is an actual attack scenario where leaking string length mattered?

If you know the length of a user's password, it narrows the search space considerably.

1. Please don't store raw passwords and compare them with strcmp().

2. Less than you'd think. e.g., the total count of all 1 and 2 and 3 digit numbers is only 11% of the count of 4 digit numbers. (And that stat gets worse with just lower case letters.) Searching all shorter passwords ends up being an insignificant amount of time compared to searching all correctly sized passwords.

I agree. Perhaps there's a more practical example?

Question: if you know the attacker doesn't have local access, is it sufficient to simply introduce random response delays to mitigate JVM-JIT level timing differences? Even if you only delayed responses by a few hundred micros on average (with randomness), I imagine all but the smallest amount of fast-path/slow-path entropy would be lost in the noise.

It requires the attacker to acquire more data - perhaps so much data that the attack is not feasible - but it doesn't rule out a timing attack.

It's pretty easy to filter out the randomness using statistics.

As I understand it, the correct thing to do is to derive a sleep time from hashing the request content, along with some secret. This makes the delay "random" from the attackers point of view, but still deterministic and therefore impossible to filter out.

Note: I am not a security person, just an interested bystander. Take this half-remembered advice with a pinch of salt.

That won't work if there's an irrelevant parameter in the request that can be varied. Say spaces ignored somewhere or additional parameters ignored, for instance.

For this case, could one just introduce another mod operation which produces result + 1? In this case:

    ($i + 1) % $safeLen

Even so, I guess the only way to eliminate timing attacks would be to write a set of primitive operations (XOR, AND, OR, ORD,...) which are constant-time (on the supported hardware platform) and only use those wherever the private information is handled. Is this possible to do? Are there any attempts at this?

> I'm saying they're unfixable because there's no way to tell the JIT to create constant-time code.

Your fallacy is that there are several JVMs to choose from, each with its own set of JIT and AOT compilers.

Don't judge Java by OpenJDK, it is only the reference implementation.

> I'm saying they're unfixable because there's no way to tell the JIT to create constant-time code.

What does that even mean? If you write your fail and success states to follow the same exact code paths (i.e. no branches, breaks, returns, or similar for failed) then you've created a "constant time" function.

The inputted parameters are dynamic so the JIT-compiler cannot optimise code away, and even if it could it would do so equally for both the failed or success states.

> Certainly Christopher Meyer has said that he's reported some that remain private since they've not been fixed.

I tried Googling that but nothing. Can you link whatever it is you're talking about?

Certainly. I was referring to this blog post, http://armoredbarista.blogspot.co.uk/2014/04/easter-hack-eve... however rereading it I see he was saying it was the ones in the hardware accelerators that haven't yet been fixed.

Sorry, I realised I'd failed to address your other point:

"What does that even mean? If you write your fail and success states to follow the same exact code paths (i.e. no branches, breaks, returns, or similar for failed) then you've created a "constant time" function."

Well, if you've got a JIT that is analysing which code actually executes, and no control over the optimisations then how do you achieve this? If the hotpath is normally the success condition for example then the JIT will optimise that more. The rare and more dangerous condition will be optimised less. If this happens of course will depend on the engine, but you can't control that without working at a much lower level than managed code offers.

> Well, if you've got a JIT that is analysing which code actually executes, and no control over the optimisations then how do you achieve this?

The same is true with native code optimising.

> If the hotpath is normally the success condition for example then the JIT will optimise that more.

The paths should be identical for both failure and success states. That's fundamentally how you "fix" timing attacks.

> If this happens of course will depend on the engine, but you can't control that without working at a much lower level than managed code offers.

You write code that has no hot paths regardless of if correct/wrong. That's how timing attacks are mitigated in all languages.

> The same is true with native code optimising.

This is rubbish. If I use custom assembler then that's what gets run. Even if I use C code then I know what the result will be since I can actually check.

> The paths should be identical for both failure and success states. That's fundamentally how you "fix" timing attacks.

That's certainly the ideal. But it's impossible - one result will succeed the other won't. The aim is to make sure both take the same time which is an achievable goal, however to do this you need to know what will execute. You might have that guarantee in practice on a particular JVM for example, but the whole point of using something like a JIT is that it will be smart about optimising stuff based on what actually happens. That's normally great, but this is a situation where all that needed is predictability not performance.

> This is rubbish. If I use custom assembler then that's what gets run. Even if I use C code then I know what the result will be since I can actually check.

It is "rubbish?" Nobody does that. Most crypto libraries are written in C or C++.

You can pre-JIT (AOT) managed code and check there too.

> That's certainly the ideal. But it's impossible - one result will succeed the other won't.

It is absolutely possible with high coding standards. Keep in mind you only have to write "correct" code in sections which have access to things like crypto keys (or things that are derived from similar), since that's what at risk with timing attacks.

> You might have that guarantee in practice on a particular JVM for example, but the whole point of using something like a JIT is that it will be smart about optimising stuff based on what actually happens.

If the code paths are identical (failure and success) what is it optimising out exactly?

> It is "rubbish?" Nobody does that. Most crypto libraries are written in C or C++. > You can pre-JIT (AOT) managed code and check there too.

Take a look. You'll see that for example openssl uses perl to generate assembly, and nettle also uses native code. This is needed if you want to use things like the AES instructions on modern CPUs.

If the code paths are identical (failure and success) what is it optimising out exactly?

JITs can create separate versions of a function for different inputs. A good JIT can turn one general case function into multiple optimized special cases using techniques that include eliminating pseudoconstants (variables that always have the same or a small number of values) and skipping computation of never-referenced results. Even normal compilers can do a lot of that.

I think a succinct way to put it is: on-the-fly "profile-guided optimization". A good JITter will do this automatically (as you said).

He's talking about a couple of recent very clever timing attacks on JSSE. However they are not comparable to Heartbleed or this SChannel overflow in severity at all:

(1) They require you to have a pre-recorded SSL session you're trying to crack. Random script kiddies won't find it useful.

(2) They require sending a lot of traffic to the server to try and break that single recording (you can get caught quite easily!)

(3) They don't reveal the private key, only per connection premaster secrets (if I understood correctly).

Basically, the first attack was possible because JSSE returned "internal server error" when faced with a particular kind of malformed packet instead of "bad padding" - this binary yes/no thing was enough to allow the attacker to divine some internal state and with enough queries retrieve the PMS. The second was a similar trick but instead of observing a different error code, it exploited the fact that internally the code was throwing an exception and this made a difference of some microseconds in the response. Over a LAN, with enough queries, that was enough to eventually reveal the PMS. However when running over a much noisier environment like the internet, number of queries required goes up quite a bit. I believe, they did not test that.

As I said before, they were both fixed, and I think Rich now agrees with me that they were fixed. There may be others that would require compiler support or hand coding of assembly to fix. Certainly there's nothing in the design of Java or the JVM that makes that impossible however. Stuff handling key material is only a small part of the overall SSL picture.

Yeah, like I said in my other comment, I'd misread which issues have been fixed. I still stand by point that for constant time you need to be close to the metal but I think we're in agreement there anyway.

I think using native code for the low-level implementation of the ciphers, padding etc. would be a good move from a security point of view and is the only way to get constant time implementation. As you say, there's nothing that prevents that in the design of Java.

Reply on news.ycombinator.com