News for hackers. Stuff that matters.
Re:X86 is a high-level language by yxhuvud on Wednesday March 25, 2015 @01:40PM (#9264517)
I wonder if introducing a sleep that is longer than the computation could conceivably take would work to solve (or at least make it a lot harder to defeat) the actual problem. The failure case where the computation actually is slow enough to matter could be detected and thrown away.

This of course would require a fully async crypto lib..

Re:X86 is a high-level language by mikeash on Wednesday March 25, 2015 @01:51PM (#9264600)
The timing is a signal, and you're proposing to mask that signal by adding noise. This does work, but you can work around it by gathering more samples and averaging out the noise. You increase the work required from an attacker, but it's not insurmountable.
Re:X86 is a high-level language by semi-extrinsic on Wednesday March 25, 2015 @04:01PM (#9265519)
What if you use random noise from a Cauchy distribution? It (interestingly enough) has no mean, so the amount of time the attacker thinks she has to subtract from her average depends on the number of samples that she takes, and does not converge as she increases the number of samples.
Re:X86 is a high-level language by mikeash on Wednesday March 25, 2015 @09:55PM (#9267365)
I'm not particularly familiar with this so the odds of the following being correct are not terribly great....

As far as I can tell, the interesting properties of the Cauchy distribution come from the "fat tail," which means that large numbers are relatively more likely than if you used, for example, a gaussian distribution. This is going to cause problems when applying it to this case because you can't sleep arbitrarily long. There will have to be some sort of ceiling on it, and I think that will bring the behavior back into a realm where the attacker can make use of it.

As to your question in your other reply about how the attacker will know to use the median instead of the mean, is there any distribution where using the median wouldn't work? If not, the attacker could just use the median as a matter of course.

The idea posted here is interesting:

https://news.ycombinator.com/item?id=9264760

Basically, have the artificial delay be unpredictable to an attacker, but constant for any given input. You'd still have to watch out for inputs which are computationally equivalent but not bytewise equal, but perhaps that can be managed.

Re:X86 is a high-level language by dcauchy on Wednesday March 25, 2015 @04:53PM (#9265848)
Attacker uses the median
Re:X86 is a high-level language by semi-extrinsic on Wednesday March 25, 2015 @05:07PM (#9265920)
Hmm. How does she know to use the median? What if I alternate between a Cauchy distribution and a lognormal (having different mean and median)? (Very apropos nick, by the way)
Re:X86 is a high-level language by matthewmacleod on Wednesday March 25, 2015 @01:58PM (#9264682)
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.

Re:X86 is a high-level language by chaosphere2112 on Wednesday March 25, 2015 @02:05PM (#9264742)
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?
Re:X86 is a high-level language by matthewmacleod on Wednesday March 25, 2015 @02:24PM (#9264900)
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.

Re:X86 is a high-level language by mreiland on Wednesday March 25, 2015 @06:13PM (#9266357)
> 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?

Re:X86 is a high-level language by matthewmacleod on Wednesday March 25, 2015 @08:08PM (#9266936)
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.

Re:X86 is a high-level language by mreiland on Wednesday March 25, 2015 @11:07PM (#9267584)
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.

Re:X86 is a high-level language by matthewmacleod on Thursday March 26, 2015 @11:58AM (#9270555)
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.

Re:X86 is a high-level language by mreiland on Thursday March 26, 2015 @07:16PM (#9273801)
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).

Re:X86 is a high-level language by renfredxh on Thursday March 26, 2015 @12:59AM (#9267902)
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.
Re:X86 is a high-level language by mreiland on Thursday March 26, 2015 @01:19AM (#9267958)
I'm interested in reality, not an oversimplification for academic reasoning. I thought that was clear.
Re:X86 is a high-level language by zvrba on Thursday March 26, 2015 @04:19AM (#9268333)
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?

Re:X86 is a high-level language by JonnieCache on Wednesday March 25, 2015 @02:07PM (#9264760)
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.
Re:X86 is a high-level language by matthewmacleod on Wednesday March 25, 2015 @07:54PM (#9266882)
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!

Re:X86 is a high-level language by TheLoneWolfling on Thursday March 26, 2015 @12:08AM (#9267770)
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.

Re:X86 is a high-level language by nickodell on Wednesday March 25, 2015 @04:02PM (#9265533)
This seems like it's insecure if the attacker can predict request_content, too.
Re:X86 is a high-level language by TheLoneWolfling on Wednesday March 25, 2015 @04:14PM (#9265615)
That's secure as long as the hash is (securely) salted.
Re:X86 is a high-level language by saidajigumi on Wednesday March 25, 2015 @01:54PM (#9264633)
This is only if the channel is a purely-external measurement of the computation, e.g. total turnaround time time to a result. A sleep won't do anything to mask a side-channel which involves (sometimes obscure) access to the actual work being done by the processor.
Re:X86 is a high-level language by ewindisch on Wednesday March 25, 2015 @02:11PM (#9264804)
Up-voting the parent.

There are attacks such as FLUSH-RELOAD which are today difficult to avoid on modern hardware and allow this sort of introspection into the CPU instructions and their timings.

Of course, there are a whole range of active and valid side-channels that are readily exploitable today. These are no longer NOBUS vulnerabilities, but are increasingly within the range and scope of ordinary attackers.

Re:X86 is a high-level language by saidajigumi on Wednesday March 25, 2015 @04:14PM (#9265616)
And relevant to the post re: sleep, there are things like Cross-VM side channels[1], an important consideration given how much infrastructure runs in shared environments these days.

[1] PDF: https://www.cs.unc.edu/~reiter/papers/2012/CCS.pdf

Re:X86 is a high-level language by ewindisch on Wednesday March 25, 2015 @04:49PM (#9265832)
Interestingly, the authors of the CCS paper are Yinqian Zhang and Michael K. Reiter. More recently, they've been publishing papers which deepen our understanding of the FLUSH+RELOAD side-channel as I described in my post (F+R was originally discovered by Yuval Yarom).
Re:X86 is a high-level language by dragontamer on Wednesday March 25, 2015 @01:50PM (#9264596)
If the sleep were cryptographically random, I can imagine it working out actually. But I wouldn't approach the subject unless I were more confident in my knowledge of cryptography.
Re:X86 is a high-level language by fchollet on Wednesday March 25, 2015 @01:51PM (#9264605)
How about random sleeps distributed so that the mean sleep time is always the same for every computation? (and much longer than any likely computation).

timer.start();

computation();

time = timer.stop();

sleep(random_centered_on(mean-time));

Re:X86 is a high-level language by TheLoneWolfling on Wednesday March 25, 2015 @04:16PM (#9265627)
For one thing, that means that your performance is horrible.

And it doesn't prevent against indirect sidechannels. For instance, seeing how long other requests take.