8 ms·
Some small suggestions for the Intel instruction set
- akuma73 13y agoAt what point does it make sense to have a separate crypto-core / offload-engine? You could provide all of the isolation and funky instructions that you want without affecting the general purpose CPU. It may also be more efficient as it is a special purpose processor.
- SoftwareMaven 13y agoThose certainly exist and are used frequently in systems that require very high performance encryption, but what DJB is trying to do is ubiquitize encryption capability. A massive first step was taken when AES instructions were added to Intel CPUs, but more could be done. The advantage of having it be ubiquitous in the CPU is overall cost is reduced and the ability to utilize encryption in more and more places is increased since users aren't stuck waiting.
- oofabz 13y agoCrypto coprocessors have been available for many years. I have one of these in my ancient router: http://soekris.com/products/vpn14x1.html http://soekris.com/products/vpn14x1.html I doubt they will ever become ubiquitous. For most people CPU crypto will always be good enough and saving a few dollars is more important. Otherwise you would already own one.
- throwaway_yy2Di 13y agoI imagine this would only be more expensive in die area and cost, because you'd duplicate existing circuits. For example, one of djb's suggestions is to reuse the existing floating-point unit for crypto: to make small changes, exposing the functionality of the internal, 53-bit integer multiplier that's a component of the 64-bit floating point multiplier. There's already eight of these in each core (with AVX, since 2011), costing a formidable number of transistors. Creating a new crypto unit, either in the CPU or a coprocessor, would duplicate much of them. As djb emphasizes in the article, if it's too expensive it might not make sense for Intel to implement it.
- jph 13y ago> At what point does it make sense to have a separate crypto-core / offload-engine? When you're building servers that need to specialize in encryption. The separate chips are often called "cryptoprocessors". https://en.wikipedia.org/wiki/Secure_cryptoprocessor https://en.wikipedia.org/wiki/Secure_cryptoprocessor An example of commercialized cryptoprocessors: http://www.tiempo-ic.com/products/ip-cores/cryptoprocessors.html http://www.tiempo-ic.com/products/ip-cores/cryptoprocessors.... What DJB is asking (IMHO) is for improvements to general-purpose processors, for example the processor you already have in your laptop.
- pygy_ 13y agoEarlier on his blog: How to design an elliptic-curve signature system — There are many choices of elliptic-curve signature systems. The standard choice, ECDSA, is reasonable if you don't care about simplicity, speed, and security. He goes on to demonstrate his point in minute details.
- X-Istence 13y agoIt does not surprise me, considering he also co-authored http://safecurves.cr.yp.to http://safecurves.cr.yp.to with Tanja Lange.
- nanofortnight 13y agoIsn't it well known that Schnorr signatures are provably secure (under a random oracle model) while ECDSA isn't?
- jph 13y agoDJB is spot-on for the pipeline documentation. This can help many apps and workflows, ranging from the one he describes ( tiny tightly optimized cryptography code) all the way up to the entire JDK, JavaScript V8, Erlang, Beam and similar large VMs.
- dragontamer 13y agoExcept modern architectures don't have "pipelines"... at least not like ARM's pipelines are done. Modern Architectures have decoders to translate the assembly into micro-ops which are then stored into a cache (beyond the L1 cache) and then computed. Heck, the entire concept of Intel's "Hyperthreading" kills any pipeline determinism you would hope to achieve. Consider your typical ARM read-modify stall: add r1, r2 / add r1, r3. A stall needs to be inserted into the pipeline because r1's value will change. In contrast, the typical Out-of-Order (OoO) x86 computer (Steamroller, Ivy Bridge, and Bay Trail) will attempt to look at future instructions to execute during the pipeline stall. In the case of Hyperthreaded CPUs (Intel i7, i3, older Atoms), Intel will grab instructions from _another thread_ to execute while the stall is undergoing. And worse yet, as Intel and AMD upgrade their systems, sometimes there are massive architectural differences which cause regressions in some code. The infamous AMD Bulldozer (2011 chip) regressed in FPU and Vectorized code for instance, while AMD tried to up the core count and improve integer performance. If you really want to step into this arena, just use Agner Fog's optimization manual. http://www.agner.org/optimize/instruction_tables.pdf http://www.agner.org/optimize/instruction_tables.pdf But... it isn't as simple as ARM because x86 CPUs are far more complicated. Out-of-order processors just kill any determinism you have.... let alone hyperthreading or the other tricks these bigger CPUs do.
- lgg 13y agoOut of order processors do not "kill" determinism. If you can guarantee your initial state is the same you will get the same result in the same number of cycles repeatably. The fact that time it takes is non-obvious does not make it non-deterministic. Now hyperthreading does introduce real non-determinism from the standpoint of a single threaded calculation because it doesn't control the other thread using processor resources, but hyper threading introduces that sort of non-determinism even on in order processors.
- f0xf1re 13y agoFeedly on ios displays the linked page in black-on-almost-black for some reason.
- pascal_cuoq 13y ago> What's crazy about this is that we're limited to multiplying integers > of about 25 bits [...] > Why? Because the multiplier insists on rounding > its low output bits rather than giving them back to the programmer. > Why? Because the multiplier is buried inside the floating-point unit. The reference to the 25-bit success makes it seem like the author is thinking of bits 53-105 of the 106-bit result of multiplying two 53-bit inputs. The multiplier is not going to “give them back” to the programmer because it never computed them in the first place. Floating-point 53x53->53 multiplication is implemented with a couple of guard bits, the last of which is “sticky”. The multiplier the author is asking for is not “buried”, it does not exist in the processor. I am not sure why integer multiplication is not preferred. It goes up to 64x64->128, if the author wants all the bits of the product. > A 53-bit multiplier producing a full 106-bit product won't be much larger than a 53-bit multiplier producing a correctly rounded 53-bit floating-point result. Yes, it will. It will have to be 106-bit wide instead of 56-bit wide.
- nkurz 13y agoI am not sure why integer multiplication is not preferred. It goes up to 64x64->128, if the author wants all the bits of the product. I'm a little confused by this also, but given the level of detail in the linked paper (http://eprint.iacr.org/2014/134.pdf http://eprint.iacr.org/2014/134.pdf) it's definitely not just an oversight. The issue may be that he's aiming for fastest possible performance on Sandy Bridge (AVX), and 256-bit integer vector multiplication wasn't added until Haswell (AVX2). And even then, 64-bit integer elements can only be done one at a time. But since he's suggesting instruction set changes, he's clearly not thinking only of backwards compatibility.
- stromgo 13y agoHow do you correctly round, say, 6172293634027511 * 7059478094414279 / 2^53 = 4837593847918366.50000000000000011102 without essentially computing the full 106-bit product?
- dragontamer 13y agoIEEE Floating point rounds numbers in binary, not in decimal. So it is trivial by simply having a 54-bit register to hold the 53-bit mantissa. So the answer to your question is... Floating Point numbers "don't round correctly". They're actually quite complicated, and require careful study.
- userbinator 13y agoThe worst case is that today you promise secrecy for, e.g., the MUL inputs, and then realize in several years that you really want to make a faster variable-time multiplier; the commitment would then force you to add a new MULABORT instruction rather than violating the secrecy of the MUL instruction. Of course, if you don't make any commitments, then programmers have no choice but to rely on observations of CPU behavior; many of those programmers will assume constant-time MUL, and if you switch to variable-time MUL then you will be breaking cryptographic security. I disagree with this and think he has it backwards; the majority of applications will benefit from early-out multiplication, and it's only crypto that wants constant-time. Also, MUL has never been constant-time on x86, ever since the 8086. My suggestion would be to add a control register bit that puts the CPU into a mode where the guarantees needed for crypto are true. All that software would need to do is set the bit before performing sensitive operations, and clear it afterwards.
- haldean 13y agoI believe that's his point; I read that section not as "please make these instructions constant-time" and more as "please document whether these instructions are constant-time, so that we can rely on them being constant-time". If an instruction is constant time but then a new chipset comes out with early-exit semantics for multiplication, everything previously compiled for that architecture is suddenly vulnerable to timing attacks when it wasn't previously. He's just looking for a commitment for the leak and timing semantics of various instructions, even if the commitment is "you cannot rely upon this being constant-time".