8
$\begingroup$

http://cr.yp.to/antiforgery/cachetiming-20050414.pdf states the following:

So what went wrong? Answer: NIST failed to recognize that table lookups do not take constant time. “Table lookup: not vulnerable to timing attacks,” NIST stated in [19, Section 3.6.2]. NIST’s statement was, and is, incorrect.

Sections 10 - 15 (inclusive) of that paper propose that changes be made to how things are placed in the L1/L2 caches of the CPU to remedy the issue. However, you're only ever really going to be able to control what's in the L1/L2 cache with assembly.

So how secure can non-assembly code truly ever be against timing attacks?

In the case of AES the afore mentioned paper says that you can get closer to constant time by doing away with the s-box lookups but even then it seems that there could still be issues with what's in the L1/L2 cache. If not with the s-boxes then with the plaintext and ciphertext themselves or the various components of the key schedule.

$\endgroup$
  • 1
    $\begingroup$ You can't really control what's in the L1/L2 cache with assembly; that also depends on interrupts the CPU takes, and what the other cores are doing (neither of which are under the user's control). If you controlled the operating system as well, you would have hope; however I believe that's focusing in on the wrong question; the answer to timing attacks isn't having precisely consistent timing, but have any variation in the timing uncorrelated to any secret we have. $\endgroup$ – poncho Aug 2 '15 at 11:41
5
$\begingroup$

So how secure can non-assembly code truly ever be against timing attacks?

First of all, let me state that this is a tricky subject.

The simplest method is of course to do away with the lookup tables or and other components that are vulnerable to timing attacks. So when a cipher designed, it should require a minimum of vulnerable components. And during execution a minimum of vulnerable constructs should be used to be absolutely secure. For instance AES can be implemented in various ways - some are more secure than others when it comes to side channel attacks. This is all stated by DJB in the paper as well.

It is extremely hard for a native library to control cache timings too. Generally libraries are generally not constructed for a specific CPU. It may be almost impossible to control and measure how the cache handling is performed - or even how much cache is present. So in that sense machine code is (almost) as vulnerable as non-native code.

One way to conquer such complexity is to have a CPU instruction, co-routine or co-processor perform AES. Such an instruction can be designed from the ground up to be invulnerable to timing attacks. If designed well it is completely independent from cache and memory and thus from side channel attacks that rely on them.

The fact that non-native code cannot directly control the instructions and memory addresses doesn't mean it cannot control it at all. Often you can still analyze what happens at a lower level. For instance, an array in Java is not stored in reverse. You know from the specifications that it will be a single, sequential block of data somewhere in memory.


If you are stuck with things like tables then you have various options. You can for instance make sure that an attacker simply does not have enough access to perform an attack. It may be hard for an attacker to put a table on two different pages in memory, for instance.

It may also be hard for an attacker to gain enough timing information. Almost any timing information may be extracted using statistics. But just like brute forcing, it may be that the amount of data required is too high for a practical attack.

Unfortunately this page is not large enough to discuss all measures that can be taken against side channel analysis, and then validate if they are secure for machine code and high level languages. Yes, there are constructs that are valid for both (RSA blinding is probably the most well known one). Is RSA blinding enough to show that code is secure against timing attacks? Probably not.


Note that pretty often the answer to the question is: we haven't tested the code against side channel attacks and hope our algorithms and protocols are secure enough.

One way to battle this in an organization is to buy a HSM (or TLS offloader or other secure system) which should be secure against side channel attacks, basically side stepping the issue completely. These things can be very expensive, but if you require the highest protection against side channel analysis you may have a lot to lose as well.

$\endgroup$
  • 1
    $\begingroup$ Note that I've handled a very expensive piece of equipment that was directly vulnerable to padding oracle attacks. Just buying expensive hardware in itself isn't the solution either :) $\endgroup$ – Maarten Bodewes Aug 2 '15 at 10:42
  • 4
    $\begingroup$ Fun fact: Even RSA blinding isn't always secure. $\endgroup$ – SEJPM Aug 2 '15 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.