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.

Improve this question
$\endgroup$
4
  • 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, 2017 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, 2017 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, 2017 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, 2017 at 19:44

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • 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, 2017 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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