Masking and leakage-resilient primitives: One, the other(s) or both?

Securing cryptographic implementations against side-channel attacks is one of the most important challenges in modern cryptography. Many countermeasures have been introduced for this purpose, and analyzed in specialized security models. Formal solutions have also been proposed to extend the guarantees of provable security to physically observable devices. Masking and leakage-resilient cryptography are probably the most investigated and best understood representatives of these two approaches. Unfortunately, claims whether one, the other or their combination provides better security at lower cost remained vague so far. In this paper, we provide the first comprehensive treatment of this important problem. For this purpose, we analyze whether cryptographic implementations can be security-bounded, in the sense that the time complexity of the best side-channel attack is lower-bounded, independent of the number of measurements performed. Doing so, we first put forward a significant difference between stateful primitives such as leakage-resilient PRGs (that easily ensure bounded security), and stateless ones such as leakage-resilient PRFs (that hardly do). We then show that in practice, leakage-resilience alone provides the best security vs. performance tradeoff when bounded security is achievable, while masking alone is the solution of choice otherwise. That is, we highlight that one (x)or the other approach should be privileged, which contradicts the usual intuition that physical security is best obtained by combining countermeasures. Besides, our experimental results underline that despite defined in exactly the same way, the bounded leakage requirement in leakage-resilient PRGs and PRFs imply significantly different challenges for hardware designers. Namely, such a bounded leakage is much harder to guarantee for stateless primitives (like PRFs) than for statefull ones (like PRGs). As a result, constructions of leakage-resilient PRGs and PRFs proven under the same bounded leakage assumption, and instantiated with the same AES implementation, may lead to different practical security levels.