Higher Order Masking of Look-Up Tables
We describe a new algorithm for masking look-up tables of block-ciphers at any order, as a countermeasure against side-channel attacks. Our technique is a generalization of the classical randomized table countermeasure against first-order attacks. We prov
- PDF / 330,068 Bytes
- 18 Pages / 439.363 x 666.131 pts Page_size
- 48 Downloads / 166 Views
Abstract. We describe a new algorithm for masking look-up tables of block-ciphers at any order, as a countermeasure against side-channel attacks. Our technique is a generalization of the classical randomized table countermeasure against first-order attacks. We prove the security of our new algorithm against t-th order attacks in the usual Ishai-Sahai-Wagner model from Crypto 2003; we also improve the bound on the number of shares from n ≥ 4t + 1 to n ≥ 2t + 1 for an adversary who can adaptively move its probes between successive executions. Our algorithm has the same time complexity O(n2 ) as the Rivain-Prouff algorithm for AES, and its extension by Carlet et al. to any look-up table. In practice for AES our algorithm is less efficient than Rivain-Prouff, which can take advantage of the special algebraic structure of the AES Sbox; however for DES our algorithm performs slightly better.
1
Introduction
Side-Channel Attacks. An implementation of a cryptographic algorithm on some concrete device, such as a PC or a smart-card, can leak additional information to an attacker through the device power consumption or electro-magnetic emanations, enabling efficient key-recovery attacks. One of the most powerful attack is the Differential Power Analysis (DPA) [KJJ99]; it consists in recovering the secret-key by performing a statistical analysis of the power consumption of the electronic device, for several executions of a cryptographic algorithm. Another powerful class of attack are template attacks [CRR02]; a template is a precise model for the noise and expected signal for all possible values of part of the key; the attack is then carried out iteratively to recover successive parts of the key. Random Masking. A well-known countermeasure against side-channel attacks consists in masking all internal variables with a random r, as first suggested in [CJRR99]. Any internal variable x is first masked by computing x = x ⊕ r, and the masked variable x and the mask r are then processed separately. An attacker trying to analyze the power consumption at a single point will obtain only random values; therefore, the implementation will be secure against first-order DPA. However, a first-order masking can be broken in practice by a second-order side channel attack, in which the attacker combines information from two leakage points [Mes00]; however such attack usually requires a larger P.Q. Nguyen and E. Oswald (Eds.): EUROCRYPT 2014, LNCS 8441, pp. 441–458, 2014. c International Association for Cryptologic Research 2014
442
J.-S. Coron
number of power consumption curves, which can be unfeasible in practice if the number of executions is limited (for example, by using a counter). For AES many countermeasures based on random masking have been described, see for example [HOM06]. More generally, one can split any variable x into n boolean shares by letting x = x1 ⊕ · · · ⊕ xn as in a secret-sharing scheme [Sha79]. The shares xi must then be processed separately without leaking information about the original variable x. Most block-ciphers (such
Data Loading...
