Live data from Hacker News

X86 is a high-level language

blog.erratasec.com

41–50 of 125 posts

Re: X86 is a high-level language

#41
post #28

The author's conclusion that side channel attacks are unpreventable because x86 instructions execute in a variable amount of time does not follow. Side channel attacks that rely on variable instruction timing rely on _content-dependent_ timing. For example, the time spent for a mov from a memory location does not depend on the contents of the memory, but it does depend on the address of that memory. If that address i…

> 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 the discussion of cmov.

Re: X86 is a high-level language

#42

If "constant time" programming isn't possible, could crypto code thwart side channel analysis by moving in the "other" direction - adding random amounts of spurious computation? If I can't hide the work my code is doing by making it take the same amount of time (and use the same amount of power) no matter what I'm doing, seems like I could obscure it by adding a random amount of work - so that even the same "real" cr…

> Although I guess that would only be a partial solution at best. If an attacker could monitor many runs of the same "real" workload, some simple statistical analysis would still tell you some things.

Yes, exactly. If you're doing a timing attack under non-ideal conditions, there are already plenty of sources of random delays -- e.g. network delays, delays introduced by the kernel scheduler, and so on. Adding additional random delay doesn't solve this fundamental problem.

Re: X86 is a high-level language

#43
post #20

Earlier quoted context omitted.

I think that's the author's point: x86 is now a significant abstraction from the actual details of execution.

But what x86 can express hasn't changed; just how it performs. An abstraction never includes the details of execution; abstraction is that separation itself! A piece of 80386 code running on an 80386 is no more or less abstract than the same piece of code on a Core i7. They agree in their external effects, like what inputs are loaded from memory, and what result is written. The fact that EAX is renamed to different i…

It used to be that the x86 instruction set was representative of the processor architecture that it programmed. That is no longer the case. Now, it is valid to view the x86 instruction set as an abstraction of the processor architecture. That is, you can mostly pretend that the processor you're programming for is accurately represented by the architecture implied by the x86 instruction set, but it is not. And when it comes to instruction timings, this abstraction leaks.

If the term "abstraction" bothers you, then ignore it. The point of the post is to give people perspective.

Re: X86 is a high-level language

#44
post #16
post #13

Earlier quoted context omitted.

Linking to an earlier post doesn't really do anything except fragment any conversation across two different posts. I'm sure the original poster won't take it personally that his post didn't make the front page and this one did.

This is his MO on this site. Yes, I too have noticed that things tend to get posted multiple times, or that the same fucking Jargon File entries get posted every time the previous one "expires". I just don't harp on it (much)

Please note that Colin is not trying to be pedantic. He's trying to link the discussions for now and the future. This is a Good Thing.

Re: X86 is a high-level language

#45

If "constant time" programming isn't possible, could crypto code thwart side channel analysis by moving in the "other" direction - adding random amounts of spurious computation? If I can't hide the work my code is doing by making it take the same amount of time (and use the same amount of power) no matter what I'm doing, seems like I could obscure it by adding a random amount of work - so that even the same "real" cr…

Depending on how much insight you could get into the system, you could probably find out when it is doing “random” work and when it does actual work, since they will most likely look different in terms of eg. heat output, power consumption and what not.

Re: X86 is a high-level language

#46
post #19

Earlier quoted context omitted.

Any idea why the manufacturers haven't shown more interest in helping out crypto implementers? Surely timing attacks are a pretty prominent problem in microprocessor design circles by now.

There's a lot of fear surrounding in-hardware crypto primitives. See for example: http://arstechnica.com/security/2013/12/we-cannot-trust-inte... I personally would be very leery of OpenSSL relying on RdRand or AES-NI.

I think that you have extrapolated the legitimate concern around hardware random number generators to AES-NI, where it is not a legitimate concern.

With random numbers, the point is that there's no good way to tell exactly how random something is, and it's quite easy to generate deterministic stuff that looks random.

Furthermore, by changing a couple of transistors, you can destroy the randomness of Intel's generator.

So, you can mix in Intel's random data as part of your entropy pool (because it can't hurt if done properly), but don't use it as a sole source.

The difference with AES-NI is that the spec it's supposed to implement is well known and deterministic. In particular, if it somehow encrypts something wrong, then anyone who tries to decrypt it without AES-NI wouldn't be able to do so.

Then there'd be a public outcry and Intel would have to recall millions and millions of processors (see Pentium floating point bug) with massive cost to them.

So, the only way it could be bad would be if the instructions could somehow leak data to other contexts or devices. This is possible, but is probably not how you'd perform such an attack, and if Intel did that knowingly, you've probably got bigger problems.

tl;dr - It's hard to trust random data and very easy to break Intel's hardware random number generator (couple of transistors), so don't give it importance above current methods because you have no way to verify that it's working as advertised. Not being able to trust AES-NI on the other hand would cost Intel billions and billions and billions. Furthermore, AES-NI is in principle more secure than a software implementation; not vulnerable to cache timing attacks, software bugs etc.

Re: X86 is a high-level language

#47

I'm not sure what the takeaway from this is. Don't implement crypto in software, only hardware? Does that cut out algorithm-writers who won't have FPGAs and fabrication available to them?...

You don't have to have FPGA or ASIC capabilities to develop a great new algorithm, do you? Do your research, prove it in software, get it into a product later... right?

True! My takeaway was needlessly bleak. Thanks :)

Re: X86 is a high-level language

#48
post #41
post #28

The author's conclusion that side channel attacks are unpreventable because x86 instructions execute in a variable amount of time does not follow. Side channel attacks that rely on variable instruction timing rely on _content-dependent_ timing. For example, the time spent for a mov from a memory location does not depend on the contents of the memory, but it does depend on the address of that memory. If that address i…

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

The point of the grandparent's post is that timing information is only leaked if the CPU's timing is data dependent. It's not enough to show that different instructions take unpredictable amounts of time. If the sequence of CPU instructions that get executed are the same for varying data, then the unpredictability of the individual instructions doesn't create a timing attack.

xor eax,eax scans, to an x86 assembly programmer, as "eax := 0". It's idiomatic for clearing a register. There ought not be any expectation from an assembly programmer that such a frequent operation would take the same amount of time as xor eax,ebx (in particular, xor eax,eax doesn't depend on the value of eax, so it doesn't need to stall waiting for its value to be calculated). But if xor eax,eax took a different amount of time depending on whether eax was equal to 42 or not, that would be a different matter.

Re: X86 is a high-level language

#49
post #36
post #20

Earlier quoted context omitted.

I think that's the author's point: x86 is now a significant abstraction from the actual details of execution.

That's true of all superscalar machines. That's what killed RISC. The original idea of RISC was one instruction per clock and a very simple CPU control section. Early MIPS CPUs realized that. Then superscalar came to microprocessors with the Pentium Pro. It took 3000 engineers at Intel to design that CPU, but it did much better than one instruction per clock while still handling all the weird cases in x86 instruction…

RSA is not "modern".

Modern elliptic curves are chosen with side channels in mind. You won't find data-dependent branches or look-ups in straightforward implementations of Curve25519 scalar multiplication, for example.

Re: X86 is a high-level language

#50
post #40
post #36

Earlier quoted context omitted.

That's true of all superscalar machines. That's what killed RISC. The original idea of RISC was one instruction per clock and a very simple CPU control section. Early MIPS CPUs realized that. Then superscalar came to microprocessors with the Pentium Pro. It took 3000 engineers at Intel to design that CPU, but it did much better than one instruction per clock while still handling all the weird cases in x86 instruction…

> Then superscalar came to microprocessors with the Pentium Pro. Hmm, but wasn't the PowerPC 601 superscalar?

The 601 was comparable to the multiple-issue scoreboard architectures used in 1960s supercomputers, such as the CDC 6600, the IBM 7030, and the UNIVAC LARC. The 601 (I think) was a scoreboard machine, not a rename and retire machine.

A scoreboard machine blocks when two instructions use the same register. A rename and retire machine (most modern out-of-order execution CPUs) can map the same program-visible register to multiple machine registers and parallelize even when there's a register reuse, as long as there isn't real data dependency. The "retirement unit" at the end of the pipeline sorts out conflicts.

Scoreboard machines need lots of program-visible registers, and compilers which avoid reusing them when there are registers free. How much of that needs to be done varies with the CPU implementation, which is why compilers for MIPS machines had flags to optimize compilation for each MIPS implementation. This was a huge pain for software distribution. One problem with having lots of registers visible to the program is that context switches require saving all of them to RAM, which is a drag on CPU dispatching.

Post reply on HN