Does a masked look-up table prevent cache timing attacks?

Question

When applying the boolean masking countermeasure to a cipher which uses an S-box $S$, a way to handle this nonlinear operation is to recompute a new S-box $S'$ such that $S'(x \oplus r_{in}) = S(x) \oplus r_{out}$ (see, e.g., this paper).

On the other hand, for processors using cache techniques, look-up tables have been proven vulnerable against timing attacks (see this paper). Therefore, it is recommended to use regular implementations (e.g., bitsliced implementations).

My first impression is that the masking technique described above also acts as a countermeasure against the timing attack introduced by Bernstein (as the look-up table accesses do no longer directly depend on the internal state, but also on a random mask $r_{in}$). However some works study bitsliced masked implementations to prevent timing and power side-channel attacks (see, e.g., this paper).

So my question is, does a masked look-up table as described above (assuming $r_{in}$ and $r_{out}$ are renewed at each execution) also prevent from cache timing attacks? Are there any published papers on the link between this countermeasure and timing side-channels?

Answer 1

After going through this, you can use bit slicing to mask power and timing of data. This is because it does not leak any information if you interrupt that calculation that is useful to reconstruct and identify the type of calculation. Having said that, it's very slow and you wouldn't want to do it. I'm going to just use my cache description from a previous side-channel attack question.

The general idea behind cache timing attacks is that you can create a memory collision in the tag table of the cache so that you can know which index is being reloaded. This attack works very well against a lookup table, which is how everyone would probably calculate this in software, which is a pre-calculated array.

Can you calculate this bit-wise in software to get around these attacks? Absolutely, but it will be very slow to execute. I did this type of implementation for the AES S-Box because I was trying to support simulation for my semiconductor implementation and I wrote it an BASH. It was terrible, but it gave me an easy way to extract strobes (For this same purpose, I have a complete AES implementation in BASH and it's not pleasant. It takes about 1 second to compute a single block with AES256).

There's a paper by Satoshi et al that I used for the mathematics, which gives $$\left(n_1x+n_0\right)^{-1}=n_1\left(n_1^2\lambda+ n_0\left(n_1+n_0\right)\right)^{-1}x +\left(n_0x+n_1\right)\left(n_1^2\lambda+n_0\left(n_1+n_0\right)\right)^{-1},$$ which becomes the following circuit:

You would have to make a bit-slice implementation for each of those blocks in the figure. And having done that, i'm going to guess that in a C implementation it's going to be 100x slower at a minimum than just using a lookup table, but I do not believe that you will leak any useful data because there's no way to identify from cache misses or power the values that you are calculating.

If you have a "masked" value, it must not be logically masked, but functionally masked. The means that branch-index returns must not be used for values, and everything must be explicitly calculated. Therefore a XOR mask alone is insufficient to hide the data.