High-Order Conversion from Boolean to Arithmetic Masking
Masking with random values is an effective countermeasure against side-channel attacks. For cryptographic algorithms combining arithmetic and Boolean masking, it is necessary to switch from arithmetic to Boolean masking and vice versa. Following a recent
- PDF / 391,136 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 0 Downloads / 201 Views
Abstract. Masking with random values is an effective countermeasure against side-channel attacks. For cryptographic algorithms combining arithmetic and Boolean masking, it is necessary to switch from arithmetic to Boolean masking and vice versa. Following a recent approach by Hutter and Tunstall, we describe a high-order Boolean to arithmetic conversion algorithm whose complexity is independent of the register size k. Our new algorithm is proven secure in the Ishai, Sahai and Wagner (ISW) framework for private circuits. In practice, for small orders, our new countermeasure is one order of magnitude faster than previous work. We also describe a 3rd-order attack against the 3rd-order HutterTunstall algorithm, and a constant, 4th-order attack against the t-th order Hutter-Tunstall algorithms, for any t ≥ 4.
1
Introduction
The Masking Countermeasure. Masking is a very common countermeasure against side channel attacks, first suggested in [CJRR99,GP99]. It consists in masking every variable x into x = x ⊕ r, where r is a randomly generated value. The two shares x and r are then manipulated separately, so that a firstorder attack that processes intermediate variables separately cannot succeed. However first-order masking is vulnerable to a second-order attack combining information on the two shares x and r; see [OMHT06] for a practical attack. Boolean masking can naturally be extended to n shares, with x = x1 ⊕ · · · ⊕ xn ; in that case an implementation should be resistant against t-th order attacks, in which the adversary combines leakage information from at most t < n variables. It was shown in [CJRR99,PR13,DDF14] that under a reasonable noisy model, the number of noisy samples required to recover a secret x from its shares xi grows exponentially with the number of shares. Security Model. The theoretical study of securing circuits against side-channel attacks was initiated by Ishai, Sahai and Wagner (ISW) [ISW03]. In this model, the adversary can probe at most t wires in the circuit, but he should not learn anything about the secret key. The authors show that any circuit C can be transformed into a new circuit C of size O(t2 · |C|) that is resistant against such c International Association for Cryptologic Research 2017 W. Fischer and N. Homma (Eds.): CHES 2017, LNCS 10529, pp. 93–114, 2017. DOI: 10.1007/978-3-319-66787-4 5
94
J.-S. Coron
an adversary. The construction is based on secret-sharing every variable x into n shares with x = x1 ⊕ · · · ⊕ xn , and processing the shares in a way that prevents a t-limited adversary from leaning any information about the initial variable x, for n ≥ 2t + 1. The approach for proving security is based on simulation: instead of considering all possible t-uples of probes, which would be unfeasible since this grows exponentially with t, the authors show how to simulate any set of t wires probed by the adversary, from a proper subset of the input shares of the transformed circuit C . Since any proper subset of the input shares can be simulated without knowledge of the input v
Data Loading...
