CryptoDB

Matthieu Rivain

Publications

Year
Venue
Title
2019
TCHES
White-box cryptography is the last security barrier for a cryptographic software implementation deployed in an untrusted environment. The principle of internal encodings is a commonly used white-box technique to protect block cipher implementations. It consists in representing an implementation as a network of look-up tables which are then encoded using randomly generated bijections (the internal encodings). When this approach is implemented based on nibble (i.e. 4-bit wide) encodings, the protected implementation has been shown to be vulnerable to differential computation analysis (DCA). The latter is essentially an adaptation of differential power analysis techniques to computation traces consisting of runtime information, e.g., memory accesses, of the target software. In order to thwart DCA, it has then been suggested to use wider encodings, and in particular byte encodings, at least to protect the outer rounds of the block cipher which are the prime targets of DCA.In this work, we provide an in-depth analysis of when and why DCA works. We pinpoint the properties of the target variables and the encodings that make the attack (in)feasible. In particular, we show that DCA can break encodings wider than 4-bit, such as byte encodings. Additionally, we propose new DCA-like attacks inspired from side-channel analysis techniques. Specifically, we describe a collision attack particularly effective against the internal encoding countermeasure. We also investigate mutual information analysis (MIA) which naturally applies in this context. Compared to the original DCA, these attacks are also passive and they require very limited knowledge of the attacked implementation, but they achieve significant improvements in terms of trace complexity. All the analyses of our work are experimentally backed up with various attack simulation results. We also verified the practicability of our analyses and attack techniques against a publicly available white-box AES implementation protected with byte encodings –which DCA has failed to break before– and against a “masked” white-box AES implementation –which intends to resist DCA.
2018
TCHES
2018
ASIACRYPT
Masking is a common countermeasure to secure implementations against side-channel attacks. In 2003, Ishai, Sahai, and Wagner introduced a formal security model, named $t$-probing model, which is now widely used to theoretically reason on the security of masked implementations. While many works have provided security proofs for small masked components, called gadgets, within this model, no formal method allowed to securely compose gadgets with a tight number of shares (namely, $t+1$) until recently. In 2016, Barthe et al. filled this gap with maskComp, a tool checking the security of masking schemes composed of several gadgets. This tool can achieve provable security with tight number of shares by inserting mask-refreshing gadgets at carefully selected locations. However the method is not tight in the sense that there exists some compositions of gadgets for which it cannot exhibit a flaw nor prove the security. As a result, it is overconservative and might insert more refresh gadgets than actually needed to ensure $t$-probing security. In this paper, we exhibit the first tool, referred to as tightPROVE, able to clearly state whether a shared circuit composed of standard gadgets (addition, multiplication, and refresh) is $t$-probing secure or not. Given such a composition, our tool either produces a probing-security proof (valid at any order) or exhibits a security flaw that directly implies a probing attack at a given order. Compared to maskComp, tightPROVE can drastically reduce the number of required refresh gadgets to get a probing security proof, and thus the randomness requirement for some secure shared circuits. We apply our method to a recent AES implementation secured with higher-order masking in bitslice and we show that we can save all the refresh gadgets involved in the s-box layer, which results in an significant performance gain.
2018
ASIACRYPT
Since their introduction in the late 90’s, side-channel attacks have been considered as a major threat against cryptographic implementations. This threat has raised the need for formal leakage models in which the security of implementations can be proved. At Eurocrypt 2013, Prouff and Rivain introduced the noisy leakage model which has been argued to soundly capture the physical reality of power and electromagnetic leakages. In their work, they also provide the first formal security proof for a masking scheme in the noisy leakage model. However their work has two important limitations: (i) the security proof relies on the existence of a leak-free component, (ii) the tolerated amount of information in the leakage (aka leakage rate) is of O(1 / n) where n is the security parameter (i.e. the number of shares in the underlying masking scheme). The first limitation was nicely tackled by Duc, Dziembowski and Faust one year later (Eurocrypt 2014). Their main contribution was to show a security reduction from the noisy leakage model to the conceptually simpler random-probing model. They were then able to prove the security of the well-known Ishai-Sahai-Wagner scheme (Crypto 2003) in the noisy leakage model. The second limitation was addressed in a paper by Andrychowicz, Dziembowski and Faust (Eurocrypt 2016) which makes use of a construction due to Ajtai (STOC 2011) to achieve security in the strong adaptive probing model with a leakage rate of $O(1/\log n)$. The authors argue that their result can be translated into the noisy leakage model with a leakage rate of O(1) by using secret sharing based on algebraic geometric codes. In terms of complexity, the protected program scales from |P| arithmetic instructions to $\tilde{O}(|P| \, n^2)$. According to the authors, this $\tilde{O}(n^2)$ blow-up could be reduced to $\tilde{O}(n)$ using packed secret sharing but no details are provided. Moreover, such an improvement would only be possible for a program of width at least linear in n. The issue of designing an explicit scheme achieving $\tilde{O}(n)$ complexity blow-up for any arithmetic program is hence left open.In this paper, we tackle the above issue: we show how to securely compute in the presence of noisy leakage with a leakage rate $\tilde{O}(1)$ and complexity blow-up $\tilde{O}(n)$. Namely, we introduce a transform that turns any program P composed of arithmetic instructions on some filed $\mathbb {F}$ into a (functionally equivalent) program $\varPi$ composed of $|\varPi | = O(|P| n \log n)$ arithmetic instructions which can tolerate some (quasi-constant) amount of noisy leakage on its internal variables (while revealing negligible information). We use a polynomial encoding allowing quasilinear multiplication based on the fast Number Theoretic Transform (NTT). We first show that our scheme is secure in the random-probing model with leakage rate $O(1/\log n)$. Using the reduction by Duc et al. this result can be translated in the noisy leakage model with a $O(1/|\mathbb {F}|^2 \log n)$ leakage rate. However, a straight application of this reduction is not satisfactory since our construction requires $|\mathbb {F}| = O(n)$. In order to bypass this issue (which is shared with the construction of Andrychowicz et al.), we provide a generic security reduction from the noisy leakage model at the logical-instruction level to the random-probing model at the arithmetic level. This reduction allows us to prove the security of our construction in the noisy leakage model with leakage rate $\tilde{O}(1)$.
2017
EUROCRYPT
2017
CHES
Masking is a widespread countermeasure to protect implementations of block-ciphers against side-channel attacks. Several masking schemes have been proposed in the literature that rely on the efficient decomposition of the underlying s-box(es). We propose a generalized decomposition method for s-boxes that encompasses several previously proposed methods while providing new trade-offs. It allows to evaluate $n\lambda$ -bit to $m\lambda$ -bit s-boxes for any integers $n,m,\lambda \ge 1$ by seeing it a sequence of mn-variate polynomials over $\mathbb {F}_{2^{\lambda }}$ and by trying to minimize the number of multiplications over $\mathbb {F}_{2^{\lambda }}$ .
2016
CHES
2015
EPRINT
2015
CRYPTO
2014
CHES
2013
ASIACRYPT
2013
EUROCRYPT
2013
FSE
2012
FSE
2011
JOFC
2010
EPRINT
Implementations of cryptographic algorithms are vulnerable to Side Channel Analysis (SCA). To counteract it, masking schemes are usually involved which randomize key-dependent data by the addition of one or several random value(s) (the masks). When $d$th-order masking is involved (i.e. when $d$ masks are used per key-dependent variable), the complexity of performing an SCA grows exponentially with the order $d$. The design of generic $d$th-order masking schemes taking the order $d$ as security parameter is therefore of great interest for the physical security of cryptographic implementations. This paper presents the first generic $d$th-order masking scheme for AES with a provable security and a reasonable software implementation overhead. Our scheme is based on the hardware-oriented masking scheme published by Ishai et al. at Crypto 2003. Compared to this scheme, our solution can be efficiently implemented in software on any general-purpose processor. This result is of importance considering the lack of solution for $d\geq 3$.
2010
CHES
2009
EPRINT
Since their publication in 1996, Fault Attacks have been widely studied from both theoretical and practical points of view and most of cryptographic systems have been shown vulnerable to this kind of attacks. Until recently, most of the theoretical fault attacks and countermeasures used a fault model which assumes that the attacker is able to disturb the execution of a cryptographic algorithm only once. However, this approach seems too restrictive since the publication in 2007 of the successful experiment of an attack based on the injection of two faults, namely a second-order fault attack. Amongst the few papers dealing with second-order fault analysis, three countermeasures were published at WISTP'07 and FDTC'07 to protect the RSA cryptosystem using the CRT mode. In this paper, we analyse the security of these countermeasures with respect to the second-order fault model considered by their authors. We show that these countermeasures are not intrinsically resistant and we propose a new method allowing us to implement a CRT-RSA that resists to this kind of second-order fault attack.
2009
CHES
2009
CHES
2008
FSE
2008
EPRINT
In the recent years, side channel analysis has received a lot of attention, and attack techniques have been improved. Side channel analysis of second order is now successful in breaking implementations of block ciphers supposed to be effectively protected. This progress shows not only the practicability of second order attacks, but also the need for provably secure countermeasures. Surprisingly, while many studies have been dedicated to the attacks, only a few papers have been published about the dedicated countermeasures. In fact, only the method proposed by Schramm and Paar at CT-RSA 2006 enables to thwart second order side channel analysis. In this paper, we introduce two new methods which constitute a worthwhile alternative to Schramm and Paar's proposition. We prove their security in a strong security model and we exhibit a way to signifficantly improve their efficiency by using the particularities of the targeted architectures. Finally, we argue that the introduced methods allow to efficiently protect a wide variety of block ciphers, including AES.
2008
CHES
2007
CHES

TCC 2019
CHES 2019
CHES 2018
CHES 2018
Asiacrypt 2017
CHES 2017
CHES 2016
Eurocrypt 2016
CHES 2014
CHES 2013
CHES 2012