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.
X86 is a high-level language
21–30 of 125 posts
Re: X86 is a high-level language
#22I 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..
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…
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?
Re: X86 is a high-level language
#23I 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..
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…
The solution i've seen is:
sleep(float(hash(request_content)) % n)
Re: X86 is a high-level language
#24[deleted]
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.
Re: X86 is a high-level language
#25And 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.
Re: X86 is a high-level language
#26Every 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.
Their response has been to add new instructions and features to the chip. Like AES-NI in x86.
Re: X86 is a high-level language
#27I 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..
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.
Up-voting the parent.
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.
Re: X86 is a high-level language
#28The 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.
Re: X86 is a high-level language
#29Every 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...
Re: X86 is a high-level language
#30[deleted]
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.
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. :)