Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

X86 is a high-level language

blog.erratasec.com

Post reply on HN
Print view View original

91–100 of 125 posts

Re: X86 is a high-level language

#91

Post by jstarks »

mreiland wrote: post #75
jlebar wrote: post #41

Earlier quoted context omitted.

> The fact that xor eax,eax is just a register operation doesn't mean it can leak sensitive information. AIUI tfa's point is that you can't assume that xor eax,eax and xor eax,ebx take the same amount of time, because "x86 is a high level language". Similarly for his other examples. This, he claims, makes it difficult to write code that resists timing attacks, if you ever want to have a branch that does nothing. Thus…

Can someone explain to me why you wouldn't just count clock ticks at a higher level than the CPU? If the operation finishes early just... wait. I understand resolution and yes you'll probably only be w/i a delta of some sort, but isn't that the point? Why wouldn't that approach work?

Even if you could figure out the worst-case timings and how to simulate them in all cases, the performance would be unacceptable. The usual operations that are data-dependent in crypto algorithms are mov with a data-dependent address, and conditional jump with a data-dependent condition. To slow these down, you'd have to simulate the absolute worst case, which means no caches of any kind, which means possibly thousands or even millions of cycles (to simulate a page fault from disk) for every operation of unknown duration. Crypto would become infeasible.

There are much better ways to achieve this, by always computing both sides of a (logical) branch or using computation instead of branching or table lookups. You likely have to write this in assembly to be sure that the compiler doesn't "optimize" any of your tricks back into branches. Some of this is hard in older crypto algorithms (AES was designed to use table lookups in software), but newer crypto algorithms are much more amenable to safe implementation.

Re: X86 is a high-level language

#92

Post by mikeash »

semi-extrinsic wrote: post #54
mikeash wrote: post #10

Earlier quoted context omitted.

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.

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.

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

#93

Post by nightcracker »

CHY872 wrote: post #86
nightcracker wrote: post #81

Earlier quoted context omitted.

I disagree. The risk is not that the hardware encryption module like AES-NI encrypts _wrong_, at all. The risk is that it's possible to escrow the last N used AES-NI keys within the chip, and extract them using custom non-public microcode or physical access.

That's fanciful. If your hardware is vulnerable to such an extent, you might as well keel over and give up on any security. For example, such hardware could reasonably be expected to occasionally scan main memory for crypto keys in the first place, or perhaps install an SSH server and a root user, or... Again, the reason why people care (or rather, should care) about RNGs is because it's theoretically very easy to ta…

No, scanning main memory is very obvious and easy to detect.

A small one kilobyte of escrow is a lot more nefarious and harder to detect.

Re: X86 is a high-level language

#94

Post by Qwertious »

soup10 wrote: post #39

Yet another reason high-performance code will continue to be written in c/c++. Every abstraction layer from actual machine architecture severely convolutes the optimization process.

On x86 machines (which includes any standard desktop/laptop PC) C/C++ is compiled into x86 before it can be executed. Writing in C or C++ is actually more abstracted than x86.

As a rule, hand-written x86 assembly will outperform C or C++, when both are very thoroughly optimised.

Re: X86 is a high-level language

#95

Post by mreiland »

matthewmacleod wrote: post #84
mreiland wrote: post #77

Earlier quoted context omitted.

> 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 quick…

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

#96

Post by mreiland »

jstarks wrote: post #91
mreiland wrote: post #75

Earlier quoted context omitted.

Can someone explain to me why you wouldn't just count clock ticks at a higher level than the CPU? If the operation finishes early just... wait. I understand resolution and yes you'll probably only be w/i a delta of some sort, but isn't that the point? Why wouldn't that approach work?

Even if you could figure out the worst-case timings and how to simulate them in all cases, the performance would be unacceptable. The usual operations that are data-dependent in crypto algorithms are mov with a data-dependent address, and conditional jump with a data-dependent condition. To slow these down, you'd have to simulate the absolute worst case, which means no caches of any kind, which means possibly thousan…

you misunderstand me. Where the pause happens doesn't really matter, it doesn't have to be the cryptographic function.

This honestly strikes me as mental masturbation, the sort of thing that can't be worked around in theory, but the chances of an attack being able to glean something useful from it is astronomically small.

And I get what you're about to tell me, "I'm a terrible human being who shouldn't ever think about security".

But nothing anyone has stated so far in this thread has made any sense to me. One guy started talking about ping returning faster if your machine is sleeping instead of calculating. That literally gets swallowed up in network latency, router congestion, cache misses due to load balancing, a few extra legitimate requests, and so forth. I just don't see it in practice.

Re: X86 is a high-level language

#97

Post by caf »

DrJokepu wrote: post #88
stephencanon wrote: post #74

Earlier quoted context omitted.

The subsequent mov ebx, 9000h will cause ebx to "point to" a new underlying register, leaving the one that corresponds to eax intact.

So every time a new value is loaded into one of the "high level" registers, it's actually loaded into a new underlying register? So the underlying registers are basically immutable?

Yes, it's a allocation technique called "single static assignment".

Re: X86 is a high-level language

#98

Post by TheLoneWolfling »

mreiland wrote: post #75
jlebar wrote: post #41

Earlier quoted context omitted.

> The fact that xor eax,eax is just a register operation doesn't mean it can leak sensitive information. AIUI tfa's point is that you can't assume that xor eax,eax and xor eax,ebx take the same amount of time, because "x86 is a high level language". Similarly for his other examples. This, he claims, makes it difficult to write code that resists timing attacks, if you ever want to have a branch that does nothing. Thus…

Can someone explain to me why you wouldn't just count clock ticks at a higher level than the CPU? If the operation finishes early just... wait. I understand resolution and yes you'll probably only be w/i a delta of some sort, but isn't that the point? Why wouldn't that approach work?

Your operating system hits memory pressure and pages your RAM page to disk. Some time later it restores it. Hey, look, you've suddenly had an arbitrarily long delay. So you can't always finish early.

Also, even assuming you can always finish early, that plan won't prevent, for example, measuring the delay of other responses. (As your process sleeping will have an impact on how fast other responses are sent. Due to cache pressure, in particular. But also due to CPU throttling, scheduling, etc, etc.

Re: X86 is a high-level language

#99

Post by TheLoneWolfling »

pascal_cuoq wrote: post #60
bo1024 wrote: post #57

Earlier quoted context omitted.

> The author's conclusion that side channel attacks are unpreventable The author never said anything about "unpreventable". > None of the author's various examples have anything to do with side channel attacks. I think the author was trying to point more directly toward the stackoverflow post that was linked, using the examples to point out that it was based on some faulty assumptions.

I wrote the StackOverflow post, and I don't see anything in the article that points faulty assumptions. Don't get me wrong, I am glad that someone wrote that article. I was going to write a similar one myself within a few days with all the details I didn't need to expand on in the StackOverflow question because anyone who could answer didn't need them. If you see any specific assumption that the article points out as…

Have you checked to make sure that, for example, the kernel entry flag save / restore (i.e. PUSHFQ/POPFQ, etc.) doesn't take data-dependent time?

Also, what about context switches in general? Stack memory can be zeroed to start. If you're writing zeros to the stack on a context switch I could see that being a different amount of time taken than if it's not zero. Due to the CPU not having to publish the memory write.

This would be the case with any predictable value in the cache, not just zeros.

It seems to me that all values that affect registers could potentially turn into a memory access. Due to context switching. Or am I missing something here?

Re: X86 is a high-level language

#100

Post by TheLoneWolfling »

matthewmacleod wrote: post #83
JonnieCache wrote: post #23

Earlier quoted context omitted.

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.

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.

Post reply on HN