Paper 2013/292

A Leakage Resilient MAC

Dan Martin and Elisabeth Oswald and Martijn Stam

Abstract

We put forward a message authentication code (MAC) for which we claim a high degree of resilience against a key-recovering attacker expoiting practical side channels. We achieve this by blending the lessons learned from many years of engineering with the scientific approach provided by leakage resilience. This highlights how the two often disparate fields can benefit from each other. Our MAC is relatively simple and intuitive: we essentially base our construction on bilinear groups and secret share out our key. The shares are then refreshed before each time they are used and the algebraic properties of the bilinear pairing are used to compute the tag without the need to reconstruct the key. This approach allows us to prove (in the random oracle model) existential unforgability of the MAC under chosen message attacks in the presence of (continuous) leakage, based on two novel assumptions: a bilinear Diffie--Hellman variant and an assumption related to how leaky performing a group operation is. In practice we envision our scheme would be implemented using pairings on some pairing friendly elliptic curve, where the leakiness of the group operation can be experimentally estimated. This allows us to argue about practical implementation aspects and security considerations of our scheme. We compare our scheme against other leakage resilient MACs (or related schemes) that have appeared in the literature and conclude ours is both the most efficient and by far the most practical.