9
$\begingroup$

The typical cache line size of modern x86 machines is 64 bytes. Is it safe to use lookup tables with secret data if the table does not exceed the cache line size, and is aligned accordingly?

I was thinking about how to make a constant-time GHASH (GCM) implementation. I want to have a table of 128x4 128-bit entries. Each two bits of the block being multiplied would determine which of four entries is XORed into the result. Repeat 64 times, and you've multiplied the block by $H$.

As far as I can tell, this should be immune to timing attacks, because at no time does secret data determine which cache line is read.

$\endgroup$
  • 1
    $\begingroup$ Even the position in a cache line can affect performance. I remenber a discussion of this approach in the context of GCM where it was determined to not be safe. $\endgroup$ – CodesInChaos Jan 24 '17 at 7:50
  • $\begingroup$ i can guarantee this in every processor but the x86. i can cache lock most of them. now that intel purchased altera, you could just grump this on the fpga fabric $\endgroup$ – b degnan Jan 24 '17 at 11:34
  • $\begingroup$ @CodesInChaos can you link anything that mentions that? I'd imagine what you are saying might be true if CPU believes data is on cache-line boundary. But I've never heard of performance reduction based on position in cache-line (if anything, we move away from it, movaps vs movups is now same speed). $\endgroup$ – axapaxa Jan 24 '17 at 18:42
  • 1
    $\begingroup$ @axapaxa From my design, all data accesses will be aligned. In my code, systems with SSE2 but not pclmulqdq will use movdqa or directly pxor from memory, both of which require alignment anyway. $\endgroup$ – Myria Jan 24 '17 at 19:44
9
$\begingroup$

The typical cache line size of modern x86 machines is 64 bytes.

This might not be true for all processors. You should retrieve that from system if you want to know that. Ideally you should split data further, in your example you can split it to a bit every 16 bytes, so you will support every machine with cache line size of 16 or bigger (and 16bytes is size of SSE register so most machines that come with SSE should have that cache size - so most CPUs in this millennium).

As far as I can tell, this should be immune to timing attacks, because at no time does secret data determine which cache line is read.

We can only hope.

x86 and x64 processors aren't security devices. They don't come with any guarantees of data access time or any constant time guarantees. In fact, they are known to do anything they can to avoid being constant time, they want to do it faster if possible.

But hopes are (for example OpenSSL RSA relies on that) that this is indeed constant time. There aren't any guarantees from Intel nor AMD. But as far as we understand processors they produced - this is indeed true as of now.

However you should be careful. It isn't hard to introduce timing-attacks into your code - it's very easy to even introduce branch depending on secret if you are using anything but assembly. Best thing you can do is testing if something is indeed constant time on your machine. This doesn't mean it will always take same amount of time. Instead, different secrets shouldn't take different amount of time in long run.

$\endgroup$
4
$\begingroup$

Apparently aligned memory access within a cache line in is not constant time. In particular accessing the first word (64-bits in the sample program) of a cache line seems to be slower.

$\endgroup$
  • 1
    $\begingroup$ Sadly sources you mentioned aren't very clear in what problem is. I've written simple program to try to determine if random access to cache-lines have this problem. I've only observed performance decrease with reads with 61-63 offsets, which would be cache-line boundary. Tested on i5-3230M. $\endgroup$ – axapaxa Jan 26 '17 at 23:23

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.