Are lookup tables safe when they fit in a cache line? 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.
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.