In the afternoon of the second day of EUROCRYPT 2016, Emmanuel Prouff gave a tutorial on how to securely implement cryptographic schemes on embedded devices. The main focus of the tutorial was on the security definitions of side-channel countermeasures, their construction and analyses.
A side-channel observation tends to leak information on the operation being performed at a given point in time and also on the data under manipulation. To secure an implementation against side-channel leakage, we need effective and efficient countermeasures that can be formally analysed in reasonably realistic models of leakage. The need for formal security analysis need not be emphasised given the fact that the side-channel analysis research community has witnessed several ad hoc analyses being invalidated. Practical security evaluation of countermeasures that come with sound theoretical analysis is also necessary for various reasons, the most important of which is to validate the practical relevance of the formal model of leakage adopted.
Side-channel observations are inherently noisy and the efficiency of a side-channel attack depends on the amount of noise in an observation. So a natural way to secure implementations against such attacks is to increase the noise in the observations. One method to achieve this is to secret share sensitive intermediate variables in such a way that probing a few intermediate values would not reveal any information about the secret parameters. For example, a secret key $x$ could be shared as $x = x_0 \oplus \ldots \oplus x_d$. This method belongs to a popular class of countermeasures known as masking, and these type of countermeasures are of algorithmic nature, which is in contrast to physical countermeasures such as hiding. One of the reasons for the popularity of the masking countermeasure is its amenability to a formal security analysis. Though the "crypto theory" community has shown considerable interest to provide effective defenses against side-channel attacks, for instance, the research on leakage-resilient cryptography [MR04,DP08], a practical solution currently seems to be out of reach due to its lack of efficiency. A possible reason for this is that the formal model of leakage often used is too strong compared to that observed in practice.
The first use of the idea of secret sharing as a side-channel countermeasure dates back to the works [GP99] and [CJRR99]. The practical effectiveness of the masking countermeasure can be deduced from a result in [CJRR99] that the number of side-channel traces necessary to distinguish the underlying unmasked bit increases exponentially w.r.t. to the number of shares of the corresponding bit. To formally analyse the security of masking schemes the most popular model of leakage used is the probing model of [ISW03]. In this model, an adversary is allowed to obtain leakage corresponding to a fixed number of wires of a boolean circuit. A more realistic leakage model, called as information bounded model, was proposed in [RP13]. These two models were unified in [DDF14].
A side-channel observation tends to leak information on the operation being performed at a given point in time and also on the data under manipulation. To secure an implementation against side-channel leakage, we need effective and efficient countermeasures that can be formally analysed in reasonably realistic models of leakage. The need for formal security analysis need not be emphasised given the fact that the side-channel analysis research community has witnessed several ad hoc analyses being invalidated. Practical security evaluation of countermeasures that come with sound theoretical analysis is also necessary for various reasons, the most important of which is to validate the practical relevance of the formal model of leakage adopted.
Side-channel observations are inherently noisy and the efficiency of a side-channel attack depends on the amount of noise in an observation. So a natural way to secure implementations against such attacks is to increase the noise in the observations. One method to achieve this is to secret share sensitive intermediate variables in such a way that probing a few intermediate values would not reveal any information about the secret parameters. For example, a secret key $x$ could be shared as $x = x_0 \oplus \ldots \oplus x_d$. This method belongs to a popular class of countermeasures known as masking, and these type of countermeasures are of algorithmic nature, which is in contrast to physical countermeasures such as hiding. One of the reasons for the popularity of the masking countermeasure is its amenability to a formal security analysis. Though the "crypto theory" community has shown considerable interest to provide effective defenses against side-channel attacks, for instance, the research on leakage-resilient cryptography [MR04,DP08], a practical solution currently seems to be out of reach due to its lack of efficiency. A possible reason for this is that the formal model of leakage often used is too strong compared to that observed in practice.
The first use of the idea of secret sharing as a side-channel countermeasure dates back to the works [GP99] and [CJRR99]. The practical effectiveness of the masking countermeasure can be deduced from a result in [CJRR99] that the number of side-channel traces necessary to distinguish the underlying unmasked bit increases exponentially w.r.t. to the number of shares of the corresponding bit. To formally analyse the security of masking schemes the most popular model of leakage used is the probing model of [ISW03]. In this model, an adversary is allowed to obtain leakage corresponding to a fixed number of wires of a boolean circuit. A more realistic leakage model, called as information bounded model, was proposed in [RP13]. These two models were unified in [DDF14].
Two main issues that need to be addressed while designing a masking scheme are: (1) how to share the sensitive data, and (2) how to securely process the shared data. For the former problem, most often one adopts a linear secret sharing scheme, in particular, the boolean masking. This method is closely related to the problem of constructing error correcting codes with large dual distance. Other alternatives to the linear secret sharing schemes are multiplicative masking, affine masking, modular additive masking, homographic masking, inner product masking, etc.
The latter problem of securely processing on shared data is closely related to the problem of secure multi-party computation. In the context of boolean masking, a well known method to compute in the presence of shares is from [ISW03]. Note that for circuits over the finite field of two elements $\mathbb{F}_2$ (i.e., boolean circuits), processing an $\mathbb{F}_2$-addtion gate (i.e., an xor gate) is straightforward as we just need to add up the corresponding shares of the input to produce the shares of the output of the addition gate. The main difficulty is to process an $\mathbb{F}_2$--multiplication gate (i.e., an and gate). The method proposed in [ISW03] to securely perform multiplication in the presence of shares requires quadratic amount (in the number of shares) of time and randomness, and hence is more expensive compared to performing an addition. The [ISW03] method was generalised to $\mathbb{F}_{2^n}$-arithmetic circuits in [CGPQR12] for improved efficiency in software implementations. In [CGPQR12], the function represented by a given (non-randomised) arithmetic circuit over $\mathbb{F}_{2^n}$ is represented by an univariate polynomial over $\mathbb{F}_{2^n}$, which is then evaluated by a sequence of the following operations: polynomial addition, scalar multiplication, polynomial squaring and multiplication of two distinct polynomials. While the first three are $\mathbb{F}_{2}$-linear operations, and hence relatively cheap to process, only the multiplication operation is non-linear and relatively more expensive. Currently, the heuristic method of [CRV14] is the most efficient polynomial evaluation method over binary finite fields that seeks to minimise the total count of non-linear multiplications. Recently, [CPRR15] proposed an algebraic decomposition method where the target function to be securely evaluated is represented as a composition of quadratic or higher algebraic-degree functions, which in turn are securely implemented more efficiently than by using previously known techniques.
While the probing model is effective against differential power analysis-like attacks, however, they are vulnerable to attacks that exploit the presence of glitches. The security requirements of glitch-resistant side-channel countermeasures are more demanding than that of masking schemes and, as a consequence, are less efficient in practice than masking schemes. Threshold implementations are a well-known class of glitch-resistant countermeasures.
The speaker concluded the tutorial by emphasising the need for algorithmic side-channel countermeasures enabled with formal security analysis, the need for formal models of leakage that suit the physical reality of devices and that enables relatively simple security proofs, and the need for efficient countermeasures.
References:
[CGPQR12] Claude Carlet, Louis Goubin, Emmanuel Prouff, Michaël Quisquater, Matthieu Rivain: Higher-Order Masking Schemes for S-Boxes. FSE 2012.
[CJRR99] Suresh Chari, Charanjit S. Jutla, Josyula R. Rao, Pankaj Rohatgi: Towards Sound Approaches to Counteract Power-Analysis Attacks. CRYPTO 1999.
[CPRR15] Claude Carlet, Emmanuel Prouff, Matthieu Rivain, Thomas Roche: Algebraic Decomposition for Probing Security. CRYPTO 2015.
[CRV14] Jean-Sébastien Coron, Arnab Roy, Srinivas Vivek: Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures. CHES 2014.
[DDF14] Alexandre Duc, Stefan Dziembowski, Sebastian Faust: Unifying Leakage Models: From Probing Attacks to Noisy Leakage. EUROCRYPT 2014.
[DP08] Stefan Dziembowski, Krzysztof Pietrzak: Leakage-Resilient Cryptography. FOCS 2008.
[GP99] Louis Goubin, Jacques Patarin: DES and Differential Power Analysis (The "Duplication" Method). CHES 1999.
[ISW03] Yuval Ishai, Amit Sahai, David Wagner: Private Circuits: Securing Hardware against Probing Attacks. CRYPTO 2003.
[MR04] Silvio Micali, Leonid Reyzin: Physically Observable Cryptography (Extended Abstract). TCC 2004.
[RP13] Emmanuel Prouff, Matthieu Rivain: Masking against Side-Channel Attacks: Masking against Side-Channel Attacks: A Formal Security Proof. EUROCRYPT 2013.
No comments:
Post a Comment