Why Constant-Time Crypto?

Making the overall computation take a fixed amount of time does not plug indirect leaks. In particular, if the computation makes memory accesses at addresses that depend on secret values, then this will populate the memory caches for these addresses, and evict from the caches whatever data was using the same slots. The attacker may work out, after the computation, which previous data elements were evicted from cache, thereby leaking secret information. Crucially, the cryptographic computation itself took a fixed amount of time, but leakage occurs nonetheless.

This kind of leak still counts as a "timing attack" because the test for cache eviction is based on the time it takes to next access the relevant element (and this occurs _after_ the cryptographic computation, from other code). Notably, this can still be done remotely, possibly from a large distance, thanks to the efficiency of modern networking (this is what makes timing attacks special among side-channel leaks: power analysis, electro-magnetic emissions, sound... require the attacker to be in the physical vicinity of the target system, while timing attacks may be performed from hundreds of miles away). Demonstrations have been made with network access (over ethernet or optic fibre), and, in another kind of setup, when the attacker can run his own code on the same hardware, even with logical isolation (another process, or even in another VM that happens to run on some other cores of the same machine).

Thus, "true" constant-time code will make no memory access at an address that depends on secret data (but the data contents, of course, may be secret). Similarly, it won't make conditional jumps that depend on secret data (because of the cache accesses for loading the code, and also because of the jump prediction cache, both having been successfully exploited in lab demonstrations).

I had another idea for making constant time programs. The idea is that you create a virtual machine without loops or branch instructions, in which each instruction is tested so that the amount of time it takes is independent of the instruction's input or output. You then compile your C code to this instruction set, and execute it on the VM. A program running on this VM, no matter how it's produced, will execute for the same amount of time.

Why not do this for crypto?

Because as explained in the article, elementary things like memory access a[i] are not constant time with respect to i?

Because an arbitrary C program will have non-constant branches (so may become exponentially long in your proposed instruction set) and loops (not representable at all in your proposed instruction set)?

If what you are saying is that a language could hypothetically statically verify that the execution of a function was constant time with respect to certain inputs, that sounds like it would work and that the only obstacle is engineering effort. But compiling to such a language doesn't sound very practical to me.

I think someone wrote an applicative functor instance in haskell that would accomplish something like this. I forget if it was constant space or time or what (I can't find the link unfortunately).

All I remember at the time was thinking I had no idea why anyone would want this. But then someone (on either hn or proggit) mentioned that there were crypto reasons why it would be useful.

So I suspect that compiling isn't too bad ... however, programming with it probably is annoying.

EDIT: Actually, it looks like it was top comment in this thread: https://news.ycombinator.com/item?id=7557089

Kind of a neat idea at any rate.

I'd do it the other way round. A VM is a bit of a pain and you can't target a constant-time-only VM with a regular C compiler. Instead I'd produce a restricted C compiler that only accepted constant time programs, and mapped directly to a limited set of machine instructions. Regardless of what you do, you'd have to produce a whilelist of constant-time machine instructions, so you might as well emit them directly rather than relying on a general purpose optimising compiler to do the right thing.

You can then emit an object file containing the functions you're interested in and link it to the rest of your non-constant-time program.