Side-Channel Indistinguishability

Kindly presented by Prof. Jean-Luc Danger. HASP 2013 was collocated with ISCA 2013. See also http://dblp.uni-trier.de/rec/bibtex/conf/isca/CarletG13International audienceWe introduce a masking strategy for hardware that prevents any side-channel attacker from recovering uniquely the secret key of a cryptographic device. In this masking scheme, termed homomorphic, the sensitive data is exclusive-ored with a random value that belongs to a given set. We show that if this masking set is concealed, then no information about the cryptographic key leaks. If the masking set is public (or disclosed), then any (high-order) attack reveals a group of equiprobable keys. Those results are applied to the case of the AES, where sensitive variables are bytes. To any mask corresponds a masked substitution box. We prove that there exists a homomorphic masking with $16$ masks (hence a number of substitution boxes equal to that of the same algorithm without masking) that resists mono-variate first-, second-, and third-order side-channel attacks. Furthermore, even if the masking set is public, each byte of the correct key is found only ex aequo with $15$ incorrect ones, making the side-channel analysis insufficient alone -- the remaining key space shall be explored by other means (typically exhaustive search). Thus, our homomorphic masking strategy allows both to increase the number of side-channel measurements and to demand for a final non negligible brute-forcing (of complexity $16^{N_B}=2^{64}$ for AES, that has $N_B=16$ substitution boxes). The hardware implementation of the Rotating Substitution boxes Masking (RSM) is a practical instantiation of our homomorphic masking countermeasure