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 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.
Something interesting to note is that at least in the Pentium 4, the number of cycles spent on integer division instructions varies depending on the values of the operands [1].
A colleague of mine mentioned how this has been the case for quite a bit longer than Haswell, see "Compiler mitigations for time attacks on modern x86 processors" (from 2012). Or Agner Fog's timings pages, where many DIV instructions list widely ranging latencies, with the comment "[l]ow values are for small results, high values for high results".
Thanks for the reference, that is much better than my vague recollections.
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.
> 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.
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.
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?
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.
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.
Why is it people can't ever respond to sanity, but instead assume idiocy?
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.
You haven't explained why it doesn't solve the problem. My experience has been if I can't understand it, it's because it's bullshit.
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.
> 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 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.
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?
> 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?
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:
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)
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.
> 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:
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.
For what it's worth, I mostly[1] agree with you. You should consider should writing this up more formally as a challenge. Figure out some some of money you can afford to lose, and award it as a cash prize to anyone who can disprove you.
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.
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.
"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:
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 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.
> 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.
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.
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.
> You won't find data-dependent branches or look-ups in straightforward implementations of Curve25519
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.
That's the whole point, though - the algorithm is very straightforward to implement without data-dependent look-ups. So while any of those could affect execution time, none should do so in a way that leaks data.
x86 encoding is not that compact, especially if you're using some of the odder addressing modes or instructions. (the packing functions, xmm operations, etc) It wastes a fair number of single byte encodings on infrequently used instructions, like BCD arithmetic. An instruction set designed for space efficiency could be smaller without foregoing too much rational and orthogonal opcode design.
It's definitely more compact than a simplistic orthogonal opcode design with a generous allocation of registers, for sure.
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.
As a side note, the Pentium II was largely just the PPro with the parallel developed Pentium MMX's MMX instruction set also integrated into the core ISA (as opposed to being a separate execution unit like on the Pentium MMX), with a better bus and a smaller fab size (theres other small issues, but you only need to know about those if you're into writing kernels or writing compilers).
It's actually pretty straight forward to implement branch free RSA or ECC. Don't use Mod operations, use Montgomery Reduction or ECC curve specific reductions which are branch free.
I wrote an article [1] about this back in 2010 when Apple got into the chipmaking business with their A4 - there was a lot of confusion on the internet about RISC vs CISC and not much clarity on how the playing field has changed since the early days.
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 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".)
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.
Every 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.
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.
Intel 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...
PCLMULQDQ 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.
Ah, interesting - so this applies in particular to elliptic curves over binary fields.
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.
As far as I know they didn't try to make a good implementation without CLMUL. However, the older endomorphism-free curve2251 implementation [2, 3] is eye-opening:
- 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.
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.
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.
This sort of attack would be easy to defeat, though. For example, one fix would be to precompute a few megs of randomness data from your hardware source, and only use it after a few minutes have passed since generation. If the malicious RNG can predict the contents of the rest of the pool after this time (without modifying them) then there are bigger problems with the randomness generation.
Yeah, I've always found it odd how proponents of various entropy combining methods think it's reasonable to be afraid of hardware smart enough to know when to sabotage the RNG, but think it's unrealistic to postulate that it would also know the right way to poison their entropy pool.
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 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...
And 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.
I 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..
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.
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.
Hmm. 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)
That's not an effective technique, unfortunately. You still end up leaking timing information.
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.
What if, instead of a random sleep, you have a defined period of time for a function to take– you take a clock reading at the start and end of your execution, and sleep the remainder of the execution time?
The problem there is that sleeping alters the performance characteristics of your system. 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.
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.
> 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.
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 quickly then sleep, versus when we complete an option slowly and sleep for less time.
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.
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.
It's not much of a stretch from the Lucky 13 attack (http://www.isg.rhul.ac.uk/tls/TLStiming.pdf) to something like I described – it might be worth having a look at that paper if you're interested in seeing how much information can be extracted from delicate timing changes!
I understand your scepticism, but there have been a fair few timing attacks showing the viability of this approach.
It isn't the idea of a timing attack I take issue with. I can understand how that could be possible.
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).
He/she said "ignoring loads of complexity". It was a gross oversimplification, but over thousands of trials it is possible to extract the information using a similar method.
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!
This is only if the channel is a purely-external measurement of the computation, e.g. total turnaround time time to a result. A sleep won't do anything to mask a side-channel which involves (sometimes obscure) access to the actual work being done by the processor.
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.
And relevant to the post re: sleep, there are things like Cross-VM side channels[1], an important consideration given how much infrastructure runs in shared environments these days.
Interestingly, the authors of the CCS paper are Yinqian Zhang and Michael K. Reiter. More recently, they've been publishing papers which deepen our understanding of the FLUSH+RELOAD side-channel as I described in my post (F+R was originally discovered by Yuval Yarom).
If 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.
How about random sleeps distributed so that the mean sleep time is always the same for every computation? (and much longer than any likely computation).
Anecdotally, 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 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.
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?
I 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).
Or 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
I 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.
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.
When 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.
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)
nah, 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. :)
One 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)
Forget 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?
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?
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" 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.
> 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.
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.
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.
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.
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.