Hacker News Reader

Comment by matthewmacleod | Hacker News Reader

That's not an effective technique, unfortunately. You still end up leaking timing information.

Lets say you add a small, random sleep after each operation – this still leaks information, as the delay can be averaged out over multiple runs. A fixed sleep after each operation is no use either, for obvious reasons.

One approach I've seen is to break time into discrete quanta – for example, you could guarantee that every operation will take an integer number of seconds to complete (i.e. an operation takes exactly 1 second, or exactly 2 seconds, or… scaled as required). There are still statistical techniques to extract timing information regardless, however!

The takeaway is the cryptography is really, really hard; system integrity is even harder.

View on HN

What if, instead of a random sleep, you have a defined period of time for a function to take– you take a clock reading at the start and end of your execution, and sleep the remainder of the execution time?

The problem there is that sleeping alters the performance characteristics of your system. If an attacker submits multiple requests simultaneously, it would be possible for them to determine if you were actually working, or just sleeping - and you're back to leaking.

Sure, every confounding factor makes it more difficult to extract information. But there are many effective techniques for doing so, and we keep getting better at using them.

> If an attacker submits multiple requests simultaneously, it would be possible for them to determine if you were actually working, or just sleeping - and you're back to leaking.

how?

The basic cause of a timing attack is that if cryptographic operations can take different amounts of time depending on the content, then we can potentially be leaking information to an attacker. If we try to solve this by padding our work using sleep() or similar, we might reveal less information directly – but the performance characteristics of our machine will still be different when we complete and operation quickly then sleep, versus when we complete an option slowly and sleep for less time.

Here's a not-at-all real-world example – say an attacker causes a cryptographic operation to happen, while at the same time monitoring the time taken to respond to a ping request. Ignoring loads of complexity, we might find that a machine takes slightly longer to respond to a ping when it is performing an operation (i.e. the CPU is busy) than when it is sleeping. If that's the case, we're suddenly leaking timing information again.

I don't see it. I get what you're saying, but how does latency not swallow that difference? Or load balancing, or routing through the internal network behind the router.

It's really hard for me to buy that an attacker can determine the execution characteristics of your crypographic functions via ping over the internet.

He/she said "ignoring loads of complexity". It was a gross oversimplification, but over thousands of trials it is possible to extract the information using a similar method.

I'm interested in reality, not an oversimplification for academic reasoning. I thought that was clear.

It's not much of a stretch from the Lucky 13 attack (http://www.isg.rhul.ac.uk/tls/TLStiming.pdf) to something like I described – it might be worth having a look at that paper if you're interested in seeing how much information can be extracted from delicate timing changes!

I understand your scepticism, but there have been a fair few timing attacks showing the viability of this approach.

It isn't the idea of a timing attack I take issue with. I can understand how that could be possible.

I don't understand why purposefully having everything related to cryptography taking a predetermined time doesn't solve it. That's where my skepticism occurs.

I've had people mention OS page faults, ping requests, and DDOS concerns and I don't buy any of it. if the timing is really so tight that a page fault can throw you off, there's no way an outside attacker could possibly glean anything useful from the timing. The timings by definition have to be varying more than that.

I don't buy the DDOS because cryptographic functions are designed to be slow, we're not trying to make them slower, we're trying to make them even between requests. Choose a reasonable delta and anything that blows that delta starts over with another delta instead of just returning.

I don't understand why that wouldn't solve the problem reasonably. At this point I feel like it's an academic exercise rather than a practical one.

I'll openly admit a lot of these points become moot if the attacker has access to the machine itself where something like latency cannot dwarf the timings of the functions themselves (when they're specifically made to wait for a delta).

A remote attacker is only able to measure total predetermined latency T = t_work + t_sleep. (Actually, he will measure T + t_noise [network, etc.]).

By what means can he determine which percentage of T+t_noise was spent in actual work?

The solution i've seen is:

    sleep(float(hash(request_content)) % n)

this assumes that the attacker cannot control any non-relevant part of request_content.

This seems like it's insecure if the attacker can predict request_content, too.

That's secure as long as the hash is (securely) salted.

As far as I can tell, that would not be secure – wouldn't it end up being essentially cryptographically secure random timing noise? We already know that random jitter doesn't work, because it can be averaged out given enough samples.

I'm not a cryptography guy though, so I could well be wrong!

It cannot be averaged out, as there is no way to take multiple samples.

Look at it: for any specific input it always sleeps for a deterministic amount of time. Unlike random timing noise, which can be averaged away.

You take averages and all you know is the value of (actual time + some unknown value) very precisely. That doesn't help you.

(He is, however, missing that it should also have a random salt, generated once and stored.)

Of course, this is still breakable most of the time.

Reply on news.ycombinator.com