Masking with randomized look up tables: Towards preventing side-channel attacks of all orders

We propose a new countermeasure to protect block ciphers implemented in leaking devices, at the intersection between One-Time Programs and Boolean masking schemes. First, we show that this countermeasure prevents side-channel attacks of all orders during the execution of a protected block cipher implementation, given that some secure precomputations can be performed. Second, we show that taking advantage of the linear diffusion layer in modern block ciphers allows deriving clear arguments for the security of their implementations, that can be easily interpreted by hardware designers. Masking with randomized look up tables allows fast execution times but its memory requirements are high and, depending on the block cipher to protect, can be prohibitive. We believe this proposal brings an interesting connection between former countermeasures against side-channel attacks and recent formal solutions to cope with physical leakage. It illustrates the security vs. performance tradeoff between these complementary approaches and, as a result, highlights simple design guidelines for leakage resilient ciphers.