12 ms·
X86 is a high-level language
- deleted 12y ago[deleted]
- dyladan 12y agoLinking 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.
- signa11 12y agonah, it absolutely doesn't matter at all. i am just interested in seeing a healthy discussion on the topic, and get a few more insights from the very talented folks that lurk here. :)
- jff 12y agoThis 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)
- scott_s 12y agoPlease 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.
- ColinWright 12y agoWhen I originally posted that there was discussion in neither place. Now that this is where discussion has happened I'll delete the cross-reference, since, as you say, it serves no value, and possibly has negative value. Usually I'm linking to an existing discussion, but in this case I was just pointing to an earlier submission in case that's where it started.
- tptacek 12y agoEvery major server ISA is, in this sense, "high level": the ISA is documented, but the microarchitecture isn't, and there are timing-relevant details known only to the manufacturers. Aciicmez famously demonstrated this with a timing attack on the branch prediction cache.
- schoen 12y agoAny 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.
- lallysingh 12y agoTheir response has been to add new instructions and features to the chip. Like AES-NI in x86.
- brohee 12y agoIntel added AES, SHA-1 and SHA-256 instruction. They also added the PCLMULQDQ instruction to efficiently implement ECC. Via Padlock also have AES and SHA, and instructions for Montgomery multiplication (RSA speedup). Plenty of ARM SoC vendors offer crypto cores. So the toolbox to implement e.g. TLS securely is pretty much there. What isn't here is a way to implement new crypto primitives that would be timing attack and power analysis attack proof. But short of shipping a FPGA, I don't see how they could do it...
- sdevlin 12y ago> They also added the PCLMULQDQ instruction to efficiently implement ECC. Isn't this more typically used in GHASH implementations? Maybe it's applicable to both.
- pbsd 12y agoPCLMULQDQ is a godsend to both (GCM and binary elliptic curves), since both rely heavily on multiplication performance over F_{2^n}. The current fastest elliptic curve implementations are over binary fields using this instruction: http://eprint.iacr.org/2013/131 http://eprint.iacr.org/2013/131.
- mackwic 12y agoI think it's time to dig this: http://yarchive.net/comp/linux/x86.html http://yarchive.net/comp/linux/x86.html When Linus worked at Transmeta, doing a weird kind of processors and x86 was considered "a charming odity that works well".
- scott_karana 12y agoI'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?...
- saidajigumi 12y agoOr perhaps that we need a ISA extension that provides primitives for security-sensitive code. The instructions may be superficially similar to ones we have now, but the guarantees are around properties that enable developers to reason about the security aspects of that code. /quite possibly wishful
- superuser2 12y agoAnecdotally, this is the U.S. government's infosec philosophy. Software crypto is looked down on as a toy. "Real" security applications use hardware crypto (smart cards, HSMs, other ASIC-based crypto). The civilian world might need to catch up.
- dyladan 12y agoThe takeaway is that it is extremely difficult to implement constant time calculations. It might be extended to mean that in order to have constant time crypto, you need to have a set of instructions specifically designed to be constant and predictable time.
- sliverstorm 12y agoYou 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?
- scott_karana 12y agoTrue! My takeaway was needlessly bleak. Thanks :)
- CHY872 12y agoI don't think it would - what you implement might have more side channel attacks in, but if it's more of a PoC it shouldn't matter. On the other hand, even if it did, FPGAs are quite cheap ($100-ish for a suitable one) and if you're a serious cryptographer you're almost certainly going to be based at a university or an agency of some kind which will be able to afford one (or have a whole bunch lying around).
- yxhuvud 12y agoI 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..
- dragontamer 12y agoIf 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.
- mikeash 12y agoThe 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.
- semi-extrinsic 12y agoWhat 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.
- dcauchy 12y agoAttacker uses the median
- semi-extrinsic 12y agoHmm. 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)
- kazinator 12y ago"high level" doesn't refer to how it is implemented. Even a RISC instruction set can be implemented by, say, either some very slick silicon gates, or by an emulator written in Javascript. The existence of the Javascript emulator doesn't make the RISC instruction a high level language, on the grounds that an instruction like "ADD R1, R2, R3" triggers a complicated traversal within the Javascript code. The "level" of a language should refer to the "abstraction level". Years ago, I came to favor the definition of "abstraction level" given in the glossary of the Tunes project: http://tunes.org/wiki/abstraction_20level.html http://tunes.org/wiki/abstraction_20level.html
- na85 12y agoI think that's the author's point: x86 is now a significant abstraction from the actual details of execution.
- kazinator 12y agoBut 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 internal registers or whatever isn't really "high level": not "high level" in any way that helps the programmer express something. It just changes the performance. It's not high level the way that, say, "reduce + list" is higher level relative to "for (total = 0; i = 0; i < list.length(); i++) {total += list[i];}" (Exceptions are situations where programs do certain things; e.g. self-modifying code needs to tackle instruction caches on one implementation, but not another. That's where the abstraction "leaks".)
- scott_s 12y agoIt 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.
- mjhoy 12y agoI had this very same thought today, reading Inside the Machine by Jon Stokes. Recommended. Amazing how abstract the programmer model can be from the real hardware.
- ChuckMcM 12y agoAnd this is perhaps a response to the 'heat leaks' story [1] about how tracking processor temperature over time you can get information out, or perhaps guess at what the processor is doing. (aka a 'side channel'). The basic observation is that in addition to the fact that CISC instructions do more than just one thing (they are essentially subroutine calls into microcode at one level of abstraction) out of order execution has added even more variability to when they are executing. Making a goal of "constant time" programming (popular in crypto code and video timing loops) very difficult to achieve as the time may vary based on the data in play, instruction ordering, etc. We're a long way from the time when you could right the number of cycles something would take on the right hand column of your assembly. [1] https://news.ycombinator.com/item?id=9250611 https://news.ycombinator.com/item?id=9250611
- jstarks 12y agoThe 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 is a function of the key or plain text, then the mov will leak sensitive timing information. If not, then the mov will not. None of the author's various examples have anything to do with side channel attacks. The fact that xor eax,eax is just a register operation doesn't mean it can leak sensitive information.
- deleted 12y ago[deleted]
- jlebar 12y ago> 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.
- barrkel 12y agoThe 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.
- JohnBooty 12y agoIf "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" crypto workload would use varying amounts of power on subsequent runs. 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.
- jlebar 12y ago> 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.
- justsid 12y agoDepending 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.
- malka 12y ago"Inside the CPU, the results always appear as if the processor executed everything in-order, but outside the CPU, things happen in strange order." I think the words 'outside' and 'inside' have been swaped
- TheLoneWolfling 12y agoNope. Look at load/store ordering, for instance. To your thread (i.e. inside the CPU you're running on), things look normal. But outside your CPU, the order may be different than expected.
- soup10 12y agoYet 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.
- Qwertious 12y agoOn 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.
- DrJokepu 12y agoForget the controversial opinion and drama, let's talk about something technical, how does the mov eax, ebx thing work? He said it will update eax to point to the same underlying register ebx points to. But then what happens when something like mov ebx, 9000h is executed? How does the CPU know that this will only apply to ebx, not eax?
- stephencanon 12y agoThe subsequent mov ebx, 9000h will cause ebx to "point to" a new underlying register, leaving the one that corresponds to eax intact.
- rdc12 12y agoOne of the links on the post, links to a stack overflow question, that has this code. What is the purpose of the do-while loop with the condition 0, how is that different to not having the loop at all? #define BN_CONSTTIME_SWAP(ind) \ do { \ t = (a->d[ind] ^ b->d[ind]) & condition; \ a->d[ind] ^= t; \ b->d[ind] ^= t; \ } while (0)
- stephencanon 12y agoIt's a common C macro idiom, that makes a multi-statment macro behave like a single statement. See http://stackoverflow.com/questions/154136/do-while-and-if-else-statements-in-c-c-macros http://stackoverflow.com/questions/154136/do-while-and-if-el...
- bmm6o 12y agodo with a while (0) executes the body one time. This trick is used to package several statements into one, so it can be used in places like: if (foo) BN_CONSTTIME_SWAP(0);