X86 is a high-level language
blog.erratasec.com
blog.erratasec.com
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.
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.
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.
Why wouldn't that approach work?
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.
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.
You measure page faults in terms of milliseconds, I was not suggesting you even out the cryptographic timings to the tune of milliseconds, especially when you consider most cryptographic functions are setup specifically to take longer than that.
There is a delta that you can come up with such that things like page faults fall within it and it would still have acceptable performance. All but the most pounded of servers would be able to fall within it with no problem whatsoever.
And most of the cryptographic functions we're talking about here are things for webservers, where low performance leaves you open to easy (D)DOSing.
So why not take another crack at explaining why that wouldn't solve the problem? And don't complain to me about DDOS, people specifically code cryptographic functions to take longer than they absolutely have to. If they're not worried about DDOS, neither are we for the purposes of this conversation.
[1] https://gmplib.org/~tege/x86-timing.pdf (pages 4 & 6)
What I remembered having seen advertised (presented as an improvement, of course) is new early-exit paths for the easier arguments to division. The marketing brochure emphasised the novelty, so I must have wrongly inferred that division took constant time before that.
Considering paragraph 2.2 in http://users.elis.ugent.be/~brdsutte/research/publications/2... , I may have been remembering a new division algorithm in Nehalem. I will cite that article from now on.
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.
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 faulty, I would be delighted to know which. The article does not even specifically answer the specific question of whether memory-dependence-speculative execution is always canceled when a write occurs that goes to the location that was read, or it is can sometimes not be canceled when the written value coincides with the previous value. It's either one or the other. This is one assumption that we could make, or not, (we'll try not to make it if it's faulty!). But no help there. The article doesn't say.
____________
Something I should clarify and that may be the cause of the misunderstanding (here, or in the article if the article really points out faulty assumptions—I'm not sure it does):
It is called “constant-time programming” by tradition, but it is really “secret-independent-time-programming”, which does not roll off the tongue in the same way. Certainly, the execution time of the crucial instructions that directly handle cryptographic secrets depends on the state in which the previous instructions have left the processor. This is no big deal, because we are not trying to prove that this execution time is constant! We are only trying to prove that it does not depend on the secrets.
And we do this by proving
* that each instruction's execution time does not depend on the secret (this is what ctgrind does, with a basic but adequate set of assumptions on what the execution time of an instruction depends on. The time taken by xor eax, eax does not depend on the previous value of eax, and it doesn't matter that it is different from the time taken by xor eax, ebx. The time taken by xor eax, ebx does not depend on the values of these registers either. And so on. The only arguable chink in the ctgrind armor is integer division, which I don't know whether Adam Langley remembered to count as having an execution time that possibly depends on the value of its arguments—as pointed out in another thread). This works super well for symmetric cryptography. Seriously, problem solved! Now we just need to replace AES with a cipher implemented according to the new rules (the rules predate AES and the reference AES implementation does not follow them. And it would apparently be very difficult to build an AES implementation that would be efficient and that would follow the rules).
* that we can subdivide the code into subgroups of instructions such that each subgroup's execution time does not depend on the secret. This is obviously going to be necessary for perfect “constant-time” asymmetric cryptography. Most subgroups are only one instruction (phew! for these the problem is no harder than above) but a few subgroups need to have more than one. The StackOverflow question is about one such subgroup. Another subgroup is going to be the instructions that access tables in a secret-dependent way. These two non-unitary subgroups of instructions are already written in a very careful way by crypto implementers, who have been aware of the issues for some time. I am only doing a second check, questioning assumptions, and perhaps building an automatic tool for checking that an implementation does not leak information through timing when executed on current, relatively well-understood micro-architectures (better than future micro-architectures that haven't been imagined yet anyway).
“BUT THE ARTICLE SAYS ‘EXECUTION TIME’ IS A ABSTRACTION”, I hear you scream.
Yes. Define “execution time(s)” of an instruction/a group of instructions as “any observable number of cycles in the interaction between the instruction(s) and any other instructions that could be placed around it. The goal is to make all execution times independent of all secrets. It is easy, because currently, apart from memory accesses, conditional jumps, and possibly division, all the execution times of an instruction are independent of the data it handles.
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?
One only needs to trust the timings of instructions that one actually needs to implement cryptography. I admit I had not even considered whether an interruption and a visit through the scheduler could take an amount of time that depended of secrets; on some architectures it is possible to write code on purpose to leak secrets through this channel (a flag indicates whether multimedia registers are used, and these register, which can represent large amounts of memory to read and write, are only saved if they are used). But this is something developers would have to go out of their way to use. The implementation of cryptographic primitives should not require the flags to depend on secrets, so we can simply forbid this from happening rather than having to consider the execution times of all comparatively exotic instructions that handle the flags.
> 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.
Is this not the same question as the one in the StackOverflow question at http://stackoverflow.com/questions/29149058/does-memory-depe... ? I don't know, but someone who knows more about current micro-architectures than me thinks that instructions writing to memory takes the same execution times (see definition above) whether the value written is the same as the old value or not.
> It seems to me that all values that affect registers could potentially turn into a memory access.
You need to keep track of what register values depend on secrets. This is what ctgrind does. ctgrind warns when a register that has been computed from a secret is used for branching or memory access:
https://www.imperialviolet.org/2010/04/01/ctgrind.html
I made an equivalent version for C source (if you can separately convince yourself that your C compiler translates the C to assembler naively. This is another interesting question, but sometimes C source is what you have, so C source is what you need to verify)
http://blog.frama-c.com/index.php?post/2011/12/31/Do-not-use...
I have written a ton of articles on “C source code might not be translated to assembly that does what you think” and I have the trademark on that phrase, so please do not change the discussion to that of the compilation of C, it is a separate problem.
Ctgrind and Frama-C already work fine for symmetric cryptography, where they can help you check that the execution time does not depend on secrets simply by never using a secret in a branch or in the computation of an address of a memory access.
- that leaves the question of whether the time taken by the memory access can depend on the value being read. This is the StackOverflow question. Don't ask me, kidnap the family dogs of executives at Intel, AMD and ARM and get them to describe the current behavior of modern processors. Get them to make a few crucial promises for future processors while you're at it.
- it is not reasonable to constrain asymmetric cryptography to be implemented without memory accesses to addresses depending on secrets. The argument is going to need to be more subtle, saying that all possible secrets lead to the same instruction time. I am not sure how ctgrind could be adapted for this new challenge, but the good news is that Frama-C is very good at handling lots of possible values for variables and at computing program properties that hold for all these values.
I don't see how keeping track of register values that depend on secrets helps. All registers that contain secrets can potentially be written to memory, and as such leak information. Due to context switching. So saying "don't use registers that contain secrets for memory accesses" doesn't help, because the only way to accomplish that is either to never have registers that contain secrets or guarantee that the kernel also does the same thing. And I don't see how the kernel can context-switch without doing so.
Here is a proposal: I have verified that when the Skein cryptographic hash function is computed on a buffer of length n, using the reference implementation, then out of the program inputs, the computation time only depends on:
- n, the length of the buffer
- one, a static const variable used to determine endianness
and NOT on the contents of the buffer.
Please take any widespread processor of your choice, any widespread OS of your choice, any reasonable C compiler (not a C compiler that transforms constant-time operations into non-constant-time, I can write one of these as well as you, this is not the goal of the exercise), the length n of your choice, two input buffer contents of length n of your choice, and show how measuring the execution time as often as you like lets you discern between one input buffer version and the other.
Do as much statistic analysis as you need. Launch Skein a billion times if you need to. Have a device on the USB port that causes interrupts if that helps. Disable all cores except one. Disable hyperthreading. Enable hyperthreading.
But only come back when you have concrete proof of your claim.
Deal?
NOTE: you may think it's too much work just to satisfy some dude on Hacker News, but I'm sure you can become quite famous if you know how to do this. You are not doing this to convince only me. The people behind Skein think that its execution time does not depend on secrets, the fools, and since I followed Adam Langley's methodology to verify that property, you'll be proving him wrong too.
I have neither the time nor the expertise to be able to do this myself.
You're not trying to defend against people with my level of expertise (or rather, lack thereof). You're trying to defend against people who are a whole lot smarter than me, and have a whole lot more time on their hands.
I was hoping you either had something showing it wasn't a problem, or a workaround. Instead you've basically gone "I don't think it's a problem" and dismissed it. Normally, that would be ok. But it's cryptography. That's not good enough.
The other way of putting it is that you are arguing about things that you may not fully understand, or perhaps you are not able to put your ideas into words that others can understand.
You are right, I have given up on understanding what you meant. I will look forward to the proof of concept.
show how measuring the execution time as often as you like lets you discern between one input buffer version and the other
I think you can simplify this even further: is there any set of two inputs that can be distinguished from each other by measurement of execution time? One does not even need to identify which input is which --- merely show that there is some measurable property that is different for hashing A vs hashing B.
[1] I think the weakness is the reference to a "reasonable C compiler". It seems likely to me that at least one of GCC/Clang/MSVC/ICC with some combination of legal flags will generate assembly that defeats the obvious intent of your algorithm. This would be a disappointing way to lose your bet.
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:
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".)
If the term "abstraction" bothers you, then ignore it. The point of the post is to give people perspective.
Those are equivalent terms to all but the most obstinate pedants.
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 instructions. As the fabs improved, the Pentium Pro technology moved to the mainstream. The Pentium II and III were Pentium Pro architecture.
This killed the basic advantage of RISC. The "all instructions the same length" concept really killed it - it meant 2x code bloat. That meant bigger caches or worse cache performance. It meant more RAM and more RAM bandwidth or worse memory performance. The x86 instruction set, for all its faults, is compact.
For the crypto problem, the trouble is that modern crypto algorithms are not branch free. DES was. Vernam was. Rotor machines were. RSA and elliptic curve stuff, no. This is independent of the CPU architecture.
Hmm, but wasn't the PowerPC 601 superscalar?
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.
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.
As it was pointed out already starting since Pentium 4, for example, the same assembly instruction "add dest, src" might take a different time depending on the value of dest and src.
Unless those modern elliptic curve compensate for specific models of CPUs they run on, their straight C and assembly code might behave as if it has data dependent branches.
I only saw evidence of data-dependent timing with respect to the div operation, but maybe I missed something.
Of course, I am not suggesting other operations are inherently immune to data-dependent timing leaks.
EDIT: I see there are also some notes on adc and sbb in some situations, i.e. chains of instructions that all light up the carry flag.
- Are in cache
- Were touched by a previous instruction (regardless of cache)
- Their cache line was touched by a previous instruction
- Will be read/write (immediately) after that instruction
- You're accessing data shared by multiple cores (lock prefix)
timing will vary
It's definitely more compact than a simplistic orthogonal opcode design with a generous allocation of registers, for sure.
1: https://neosmart.net/blog/2010/the-arm-the-ppc-the-x86-and-t...
I'm not really sure that is a big deal today, however. Maybe it was when caches were much smaller, but AArch64 went back from a variable width encoding scheme (Thumb) to uniform width instructions in 64-bit mode, without any problems that I'm aware of, and the performance is quite good. At the same time, the x86-64 ISA has gotten quite a bit less space-efficient: because of the extension to 16 registers, REX prefixes are everywhere and eat up lots of bytes of the instruction stream.
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...
Isn't this more typically used in GHASH implementations? Maybe it's applicable to both.
I may have missed this, but did they note how performance fared in the absence of hardware support?
Also, have binary curves (this or the NIST ones or any others) seen widespread deployment anywhere? I was under the impression that prime field curves were more widely used.
- the SSSE3 implementation is ~2.7 times slower than with CLMUL - the generic (using mpfq, which should actually be pretty good) implementation is 5-6 times slower than with CLMUL
Binary curves used to be a lot more popular than they are now, before we all had fat multipliers in CPUs. The patent situation is worse for binary fields too, I think. That said, I'm pretty sure there are deployments somewhere using them; Dan Boneh's TLS survey [1] shows an overwhelming 96% of TLS clients using NIST's P-256, but the second most popular curve is NIST's B-233, at 3.6%. I would guess that this is due to hardware accelerators.
[1] http://www.w2spconf.com/2014/papers/TLS.pdf
[2] http://bench.cr.yp.to/web-impl/amd64-titan0-crypto_dh.html
http://arstechnica.com/security/2013/12/we-cannot-trust-inte...
I personally would be very leery of OpenSSL relying on RdRand or AES-NI.
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.
I guess it would be difficult in practice to make a malicious hardware randomness source, but it's an interesting perspective; to have confidence in your algorithm you should carefully restrict where the randomness enters it.
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.
Again, the reason why people care (or rather, should care) about RNGs is because it's theoretically very easy to tamper with them and very hard to then detect such tampering unless you're actively looking for it: http://arstechnica.com/security/2013/09/researchers-can-slip...
A small one kilobyte of escrow is a lot more nefarious and harder to detect.
When Linus worked at Transmeta, doing a weird kind of processors and x86 was considered "a charming odity that works well".
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.
This of course would require a fully async crypto lib..
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.
timer.start();
computation();
time = timer.stop();
sleep(random_centered_on(mean-time));
And it doesn't prevent against indirect sidechannels. For instance, seeing how long other requests take.
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.
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.
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.
how?
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.
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.
I understand your scepticism, but there have been a fair few timing attacks showing the viability of this approach.
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).
By what means can he determine which percentage of T+t_noise was spent in actual work?
sleep(float(hash(request_content)) % n)
I'm not a cryptography guy though, so I could well be wrong!
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.
Don't implement crypto in software, only hardware? Does that cut out algorithm-writers who won't have FPGAs and fabrication available to them?...
The civilian world might need to catch up.
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).
#define BN_CONSTTIME_SWAP(ind) \
do { \
t = (a->d[ind] ^ b->d[ind]) & condition; \
a->d[ind] ^= t; \
b->d[ind] ^= t; \
} while (0)if (foo) BN_CONSTTIME_SWAP(0);
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.
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.
I think the words 'outside' and 'inside' have been swaped
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.
As a rule, hand-written x86 assembly will outperform C or C++, when both are very thoroughly optimised.