Methods and devices for estimating secret values

Abstract

A secret value estimation device is provided for determining an estimate of at least one secret value used by at least one cryptographic mechanism implemented in a cryptographic system from a statistical distribution of a set of multivariate leakage traces determined by a leakage traces statistical distribution unit. Each leakage trace being a vector comprises a plurality of random values, the number of said random values being an integer number superior or equal to 1, the statistical distribution being a function of parametric linear combinations of a set of leakage model basis vectors representing a multivariate leakage model, the number of basis vectors being an integer number superior or equal to 1, and the linear combinations being defined by a matrix of real values.

Claims

1. A device for determining an estimate of at least one secret value used by at least one cryptographic mechanism, from a statistical distribution of a set of multivariate leakage traces, each leakage trace being a vector comprising a plurality of random values, the number of said random values being an integer number greater than or equal to 1, said statistical distribution being a function of parametric linear combinations of a set of leakage model basis vectors representing a multivariate leakage model, the number of said basis vectors being an integer number greater than or equal to 1, said parametric linear combinations being defined by a matrix of real values comprising at least one unknown value, wherein said device is configured to simultaneously determine (i) said estimate of at least one secret value and (ii) an estimate of said at least one unknown value of said matrix of real values defining said parametric linear combinations, using a multivariate estimation algorithm that maximizes a probability of successful secret values recovery and that is an expectation maximization algorithm.

2. The device of claim 1, wherein it comprises an analysis unit configured to determine said set of multivariate leakage traces from at least a leakage dimensionality and a set of acquired side-channel leakage information, wherein said number of said random values comprised in a vector of each leakage trace is equal to said leakage dimensionality.

3. The device of claim 1, wherein it comprises a processing unit configured to determine said statistical distribution of a set of multivariate leakage traces from at least a leakage dimensionality, a leakage model dimensionality, and a leakage model.

4. The device of claim 3, wherein said processing unit is further configured to determine said statistical distribution of a set of multivariate leakage traces depending on a noise of a known covariance matrix.

5. The device of claim 4, wherein said leakage dimensionality of said multivariate leakage traces depends on the noise probability distribution within each leakage trace, and the known covariance matrix is the covariance matrix of said noise distribution.

6. The device of claim 1, wherein said expectation maximization algorithm iteratively alternates between an expectation step and a maximization step, until a convergence of estimated parameters to local maxima.

7. The device of claim 1, wherein said device is further configured to deliver a security performance metric from said estimate of at least one secret value.

8. The device of claim 1, wherein said device is configured to determine the number of said set of multivariate leakage traces depending on the signal to noise ratio (SNR) or/and on a target security performance metric.

9. The device of claim 1, wherein said secret value is a cryptographic secret key used in said at least one cryptographic mechanism to encrypt and/or decrypt data and wherein said cryptographic secret key comprises a set of bits, each bit having a leakage property.

10. The device of claim 9, wherein the leakage properties of the bits are similar.

11. A method of estimating at least one secret value used by at least one cryptographic mechanism from a statistical distribution of a set of multivariate leakage traces, each leakage trace being a vector comprising a plurality of random values, the number of said random values being an integer number greater than or equal to 1, said statistical distribution being a function of parametric linear combinations of a set of leakage model basis vectors representing a multivariate leakage model, the number of said basis vectors being an integer number greater than or equal to 1, said parametric linear combinations being defined by a matrix of real values comprising at least one unknown value, wherein the method comprises simultaneously determining (i) said estimate of at least one secret value and (ii) an estimate of said at least one unknown value of said matrix of real values defining said parametric linear combinations, using a multivariate estimation algorithm that maximizes a probability of successful secret values recovery and that is an expectation maximization algorithm.

12. The method of claim 11, wherein said expectation maximization algorithm iteratively alternates between an expectation step and a maximization step, until a convergence of estimated parameters to local maxima.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate various embodiments of the invention and, together with the general description of the invention given above, and the detailed description of the embodiments given below, serve to explain the embodiments of the invention.

(2) FIG. 1 is a schematic diagram of an implementation of a secret value estimation device;

(3) FIG. 2 is a block diagram illustrating a detailed structure of a secret value estimation device according to an exemplary embodiment of the present invention;

(4) FIG. 3 is a flowchart depicting a method of secret value estimation given multivariate leakage and model according to an exemplary embodiment of the present invention;

(5) FIG. 4 is exemplary hardware architecture of the secret value estimation device according to certain embodiments of the invention.

DETAILED DESCRIPTION

(6) Embodiments of the invention provide methods and devices for estimating at least one secret value used in a cryptographic mechanism implemented in a cryptographic system from leakage information or side-channel information. The cryptosystem is associated with statistical distribution of multivariate leakage traces being function of noisy parametric linear combinations of a set of multivariate leakage model basis vectors, said linear combinations being represented by a matrix of real values, said real values being wholly known or comprising at least one unknown value.

(7) With reference to FIG. 1, an example of the implementation of a secret value estimation device 13 is illustrated. The secret value estimation device 13 is implemented to evaluate the vulnerability of a cryptographic system 10 implementing one or more cryptographic mechanisms 11 against one or more side-channel attacks by determining estimation of secret value(s) used in cryptographic mechanism(s) 11 given the side-channel information or leakage information 12 and a statistical distribution of a set of multivariate leakage traces determined by a leakage traces statistical distribution determination unit 14.

(8) Secret value estimation methods and devices according to certain embodiments of the invention may be implemented in the phase of designing or developing a cryptographic system 10 or estimating the security of manufactured embedded systems in a certification process. The cryptographic system 10 may be any type of system or device using a cryptographic mechanism 11 or algorithm to protect data, whatever the application, such as communication and data processing applications. For example, the cryptographic system 10 may be user equipment (e.g. smartphone), a relay station or a base station implemented in a wireless network (such as a cellular or adhoc networks), the cryptographic system 10 using cryptographic mechanism(s) 11 in order to secure the data (e.g. signals) transmitted over an unsecure communication channel. In another example, the cryptographic system 10 may be part of an information processing system (such as a computer system, a database, an online sale system or a financial systems) implementing a cryptographic mechanism 11 for securing data exchanged or stored in the system (for example personal data such as financial account numbers and social security numbers).

(9) Each cryptographic mechanism implemented in the cryptosystem is associated with an indicator of successful recovery of secret values and a degree of security of the secret value against side-channel attacks. Such parameters depend on the leakage model corresponding to a theoretical model used to characterize the leakage traces, as well as on the calculation algorithms used to calculate the secret values, also referred to as distinguishers. According to the various embodiments of the invention, the determination of secret value(s) is optimally performed by jointly calculating estimates of the unknown parameters of linear combinations of basis vectors of a multivariate leakage model and determining an estimate of the cryptographic secret value(s). The parameters of the linear combinations of the basis vectors of the leakage model correspond to the coefficients of the matrix a determining the link between the leakage traces and the theoretical leakage model.

(10) Referring to FIG. 2, there is shown an exemplary implementation of the secret value estimation methods and devices for a communication device 20 (representing the cryptosystem) implementing a hardware cryptographic mechanism and used in a communication system.

(11) The following description will be made with reference to a cryptographic mechanism implementing a cryptographic secret key for encryption/decryption for illustration purpose only. However, the skilled person will readily understand that other cryptographic mechanisms may be used according to which the secret value is different from the private cryptographic key.

(12) The communication device 20 may be a fixed device, such as a laptop computer operating in a wired communication system, or a mobile device, such as mobile phones operational in wireless environments. The communication device 20 may comprise for example: A Message generator/receiver unit 201 configured to generate or receive an input data (for example a signal or a message); A Cryptographic mechanism unit 202 configured to encrypt or decrypt a generated or received data.

(13) The communication device 20 may be configured to communicate encrypted data with at least another communication device 20 through a communication interface 21. The communication interface 21 may be for example a wired link, a wireless propagation medium or an optical connection.

(14) The side-channel 22 schematically represents the information leaked from the communication device 20. Leaked information may be for example the power consumption of the communication device 20 while running the cryptographic mechanism 202, the processing time required to perform a given cryptographic operations, the electromagnetic emanations, sound or infrared radiations emitted by the communication device 20. This leaked information takes, in general, the form of a series of values (side-channel traces). It may statistically reveal certain characteristics related to the cryptographic mechanisms 202 running on the communication device 20.

(15) The side-channel leaked information 22 may be intercepted by a measurement unit 23 configured to collect a set of trace measurements with respect to one or many side-channels leaked from the communication device 20. The measurement unit 23 may comprise: A number of measurements selection unit 231 configured to determine the number Q of measurements to be collected; A data acquisition unit 232 configured to collect samples of traces from leaked information from the communication device 20. The data acquisition unit 232 may be for example high speed equipment such as a modern digital oscilloscope with high speed analog-to-digital captures or any instrument equipped with a set of sensors (passive or active) such as voltage, current, power, electromagnetic probes, or temperature or acoustic sensors configured to detect physical properties of the communication device 20 from the leaked information 22.

(16) In certain embodiments, the number of measurements selection unit 231 may be configured to determine the number of the acquired leakage traces depending on the signal-to-noise ratio to take into account the level of the noise.

(17) In other embodiments, the number of measurements selection unit 231 may be configured to determine the number of the acquired leakage traces depending on a target performance metric according to a performance criterion.

(18) The collected traces may be then fed into a secret value estimation device 24 comprising an analysis unit 25 and a processing unit 26. The analysis unit 25 may be configured to analyze the acquired set of data and deliver a measurements series matrix X. The analysis unit 25 may comprise: A signal processing unit 251 configured to remove alignment errors, highlight signals and/or reduce the noise level. A leakage dimensionality determination unit 252 configured to determine a value of the dimensionality D of the multivariate leakage and generate a measurements series matrix X of dimension D×Q.

(19) The measurements series matrix delivered by the analysis unit 25 is then fed into a processing unit 26. The processing unit 26 is configured to evaluate the vulnerability of the communication device 20 by determining estimate(s) of at least one secret value used in the cryptographic mechanism 202 from the leaked information via the side-channel 22. The processing unit 26 may comprise: A dimensionality of leakage model determination unit 261 configured to deliver a value S of the dimensionality of a leakage model; A secret value calculation unit 262 configured to generate estimate(s) of desired secret value(s). A performance evaluation unit 263 configured to calculate a security performance metric PM to measure the effectiveness of the secret value estimation unit 262 given its output. A performance metric output unit 264 configured to output the estimated secret value and/or the security performance metric or any metric indicative of the security level of the analyzed communication device 20.

(20) In certain embodiments, the analysis unit 25 may be configured to determine the dimensionality of the leakage traces depending on the noise correlation within each leakage trace.

(21) In certain embodiments, the processing unit 26 may be configured to determine an estimate of a cryptographic secret key implemented in the cryptographic mechanisms 202 to encrypt/decrypt data according to the maximization of the probability of success key recovery criterion. The cryptographic secret key may be composed of several bits with similar or different leakage properties. In such embodiments, the processing unit 26 may be configured to quantify the security level of the cryptosystem 20 by determining the success rate or the rate of successful recovery of the secret key used in the cryptographic mechanisms 202 implemented by the communication device 20. Accordingly, in embodiments where the leakage model is parametric, i.e. the coefficients of the linear combinations of the basis vectors of the leakage model are at least partially unknown; the secret value calculation unit 262 may be configured to jointly determine estimates of the unknown coefficients of the parametric leakage model and an estimate of the cryptographic secret key. In contrast to separate estimation of the unknown coefficients of the leakage coefficients of the leakage model in a model profiling step prior to extraction of the secret value, considered for example in template and stochastic side-channel attacks, joint estimation refers here to simultaneously determine estimates of the missing leakage model coefficients and an estimate of the secret key. The secret value calculation unit 262 may implement an expectation maximization algorithm to jointly calculate these estimates.

(22) When applied to evaluate the success recovery of a cryptographic secret key used in the communication device 20 to encrypt or/and decrypt data, the methods and devices according to the embodiments of the invention may provide an evaluation of the vulnerability of the used encryption/decryption secret key with respect to one or more side-channel attacks.

(23) FIG. 3 is a flowchart depicting a secret value estimation method according to an exemplary applied to controlling the security of a cryptographic device using a masked cryptographic secret key to encrypt input data against an implemented side-channel attack. The secret value estimation method is carried out based on a cryptographic primitive previously loaded and run on the analyzed communication device 20, for example by a cryptosystem analyzer. A cryptographic primitive designates a specific cryptographic function or algorithm designed to perform a specific task in the cryptographic system such as authentication, keyed one-way hash function, public or private key cryptography or digital signature.

(24) In step 300, a cryptographic primitive is triggered enabling to run one or more cryptographic mechanism on the cryptosystem under side-channel analysis. A secret key k∈{0,1}n may be used to encrypt original data, such as a message or text, referred to commonly hereinafter as ‘plaintext’ and noted t. The secret key and the original data may be represented by bit vectors composed of n bits. The secret key may be a deterministic variable whereas the original data may be random. Knowledge of the original data t by the cryptosystem analyzer, without any a-priori knowledge on the secret key, is assumed. The secret key may be masked using an unpredictable random mask m∈{0,1}n which may be a bit vector comprising n bits. The mask may be internally generated by the communication device 20.

(25) In step 301, the number Q of trace measurements to be collected from the leaked information is determined. The number Q may depend on the signal-to-noise ratio denoted by SNR. In certain embodiments, Q may further be determined according to a target performance measure or metric. For example, in a context of cryptographic secret key recovery, a target performance metric may be a target success rate SR∈0,1 indicating the probability of successful key extraction with respect to one or more side-channel attacks. In one embodiment, the number of trace measurements may be linked to the signal-to-noise ratio SNR and to a target success rate SR by the relation:

(26) $\begin{array}{cc}Q\cong .Math.\frac{2\ln \left(1-\mathrm{SR}\right)}{SNR\underset{k\ne k^{*}}{\min }\kappa \left(k,k^{*}\right)}.Math.& \left(1\right)\end{array}$

(27) In equation (1), k* denotes the value of the correct key and κ designates a function that may depend on the original text t, the key and a theoretical leakage model Y(t, k). The relationship given in equation (1) may be used for example to set up the number of measurements in the case of symmetric key cryptography using 8-bits secret keys (n=8, a substitution box or S-box to implement algebraic treatment of data ciphering, and a leakage model using a Hamming weight function according to:
Y(t,k)=w.sub.H(f(t⊕k))  (2)

(28) In equation (2), f: F.sub.2.sub.n.fwdarw.F.sub.2.sub.n designates a bijective function such that f: x.fwdarw.x, x.sup.101, x.sup.254 respectively for the case of absence of Sbox, the case of an Sbox with average quality and an AES Sbox (without the affine transformation, which does not affect the confusion coefficient K). In this example, the minimum of the function K corresponding to the three previous cases is given by:

(29) $\underset{k\ne k^{*}}{\min }\kappa \left(k,k^{*}\right)=0.125,0.375,0.406250.$

(30) Given the determined number of measurements, Q pairs of traces (x, t) may be acquired in step 303 during the run time of the cryptographic primitive. Data acquisition may be performed through a temporal series of a set of discrete samples, typically within one clock period. For most cryptographic devices, the leakage signal may be represented as a continuous curve. It may be further required, in certain embodiments, that the measurement conditions remain strictly the same, and that the bandwidth of the acquisition tools be large enough such that any two successive acquired traces remain independent and such that the noise altering the measurement environment has the same probability distribution for all measured data.

(31) The signals corresponding to the collected traces are then processed in step 305 to improve the data outcome, highlight signals and/or reduce the noise level.

(32) In step 307, the leakage dimensionality D (D being an integer value and D≥1) is determined. The dimensionality D represents the number of time samples per measurement trace. A measurement series matrix X may be further constructed based on the traces obtained in step 305 and the leakage dimensionality. The value of D may depend on the noise correlation within each trace. The measurements series matrix X may be a D×Q matrix of real entries corresponding to the measurements samples 1≤q≤Q. The q.sup.th trace denoted by X.sub.q corresponds to the q.sup.th column vector of the measurements series matrix X composed of D random values.

(33) In step 309, an integer value S≥1 of the dimensionality of a theoretical leakage model Y is determined. The dimensionality of the leakage model represents the number of leakage model basis vectors that are used to model the set of measured leakage traces. In the context of cryptographic applications, the model Y(t, k) may depend on the cryptographic key k and the known text t. This dependency may be expressed using a function φ such that φ: F.sub.2.sub.n×F.sub.2.sub.n.fwdarw.R and Y=φ(t, k). For example, the Hamming weight function of the XOR operation of the text and the cryptographic key may be used to build the model (t, k)=φ(t, k) w.sub.H(t⊕k).

(34) The dimensionality S may depend on the knowledge of the leakage model and on the communication device 20. Linear and affine leakage models refer to leakage models for which the dimensionality S is equal to 1 or 2 (S=1 and S=2).

(35) In embodiments where the communication device 20 is a hardware circuit, the leakage model may be an affine model involving two basis vectors corresponding respectively to a constant and a Hamming distance between the internal variables of the circuit.

(36) In embodiments where the communication device 20 is a processor, the leakage model may be of dimensionality 1+w, where w is the bitwidth of registers (8, 16, 32, 64).

(37) In another embodiment where the hardware cryptographic device is fabricated in an advanced CMOS process, the leakage model may be of dimension 1+w+w(w+1)/2, taking into account the possible influence of the neighboring bits on each other.

(38) Given the determined leakage model dimensionality, the measurement series matrix X can be written as function of a theoretical model matrix Y∈R.sup.S×Q according to:
X=αY+N  (3)

(39) In equation (3), N∈RD×Q denotes a noise signal modeling the environment in which the communication device 20 is housed and the matrix α∈RD×S characterizes the link between the leakage traces and the theoretical model Y. The realizations of the random variables X, Y and N are respectively denoted by x, y and n (not to be confused by the number of bits on the key which is estimated).

(40) The noise distribution is assumed to be known from the cryptosystem analyzer and assumed multivariate independent and identically distributed zero-mean Gaussian of known covariance matrix Σ∈R.sup.D×D and probability density function p.sub.N(n) given by:

(41) $\begin{array}{cc}{p}_N\left(n\right)=\frac{1}{\sqrt{{\left(2\pi \right)}^D.Math.\Sigma .Math.}}\exp \left(\frac{-1}{2}{n}^t\stackrel{-1}{.Math.}n\right)& \left(4\right)\end{array}$

(42) In equation (4), n is a vector of D real numbers, the superscript (.).sup.t denotes the transpose operation and |Σ| and Σ.sup.−1 denote respectively the determinant and the inverse of the matrix Σ. The covariance matrix Σ is symmetric positive definite admitting decomposition in the form Σ=Σ.sup.1/2Σ.sup.1/2 where the matrix Σ.sup.1/2 is referred to as the standard deviation noise matrix.

(43) In other embodiments of the invention, the noise may be uniformly distributed or modeled by a Laplacian distribution.

(44) According to equation (3), multivariate leakage traces may be seen as linear combinations of basis vectors of multivariate leakage models. Each trace for 1≤q≤Q can be written in the form:
X.sub.q=αY.sub.q+N.sub.q  (5)

(45) In equation (5), X.sub.q ∈R.sup.D×1, Y.sub.q∈R.sup.S×1 and N.sub.q∈R.sup.D×1 denote respectively the trace of index q and its corresponding leakage model and noise vectors assumed to be identical for all the traces. Realizations of the random variables X.sub.q, Y.sub.q and N.sub.q are respectively denoted by x.sub.q, y.sub.q and n.sub.q.

(46) Accordingly, for each pair (t, k), in presence of Gaussian noise, the multivariate leakage traces X.sub.q, q=1, . . . , Q given y.sub.q are normally distributed according to the distribution N(αy.sub.q,Σ) of probability density function given by:

(47) $\begin{array}{cc}{p}_{X_q}\left(x_q.Math.y_q\right)=p_N\left(x_q-\alpha y_q\right)=\frac{1}{\sqrt{{\left(2\pi \right)}^D.Math.\Sigma .Math.}}\exp \left(\frac{-1}{2}{\left(x_q-\alpha y_q\right)}^t\stackrel{-1}{.Math.}\left(x_q-\alpha y_q\right)\right)& \left(6\right)\end{array}$

(48) The coefficients of the matrix a may be at least partially unknown by the cryptosystem analyzer. The number of the columns of the matrix a may depend on the complexity of the model.

(49) In an example of a weighted sum of bits leakage model, the model of each trace can be written as:
Y.sub.q=Σ.sub.i=b.sup.nα.sub.iY.sub.i+β  (7)

(50) In equation (7), Y.sub.i denotes the bit of index 1≤i≤n in the n-bit sensitive variable Y. Using this model, the dimensionality of the leakage model is equal to S=n+1 and the leakage traces can be modeled in the form of equation (3) where α=(α.sub.1, α.sub.2, . . . , α.sub.n, β) and

(51) $Y=\left(\begin{array}{c}{Y}_1\\ :\\ Y_n\\ 1\end{array}\right).$

(52) When the leakage model dimensionality is determined to be equal to 1, the model may be a modulation. General modulation models are leakage functions called “pseudo-Boolean” which are functions from n-bits to real numbers. These functions admit a unique decomposition as a Numerical Normal Form that can be represented as Y=Σ.sub.u∈F.sub.2.sub.nα.sub.uδ.sub.u (y), where δ.sub.u is a function which maps a vector of n-bits y to 1 if y=u or to 0 otherwise. Using such leakage models, the dimensionality of the leakage model is equal to S=2.sup.n and the leakage traces can be modeled in the form of equation (3) with:

(53) $\alpha =\left(a_{{\left(0\mathrm{.Math.00}\right)}_n,}{a}_{{\left(0\mathrm{.Math.01}\right)}_n},\mathrm{.Math.},a_{{\left(1\mathrm{.Math.11}\right)}_n}\right)\mathrm{and}Y=\left(\begin{array}{c}{\delta }_{{\left(0\mathrm{.Math.00}\right)}_n}\left(Y\right)\\ {\delta }_{{\left(0\mathrm{.Math.01}\right)}_n}\left(Y\right)\\ :\\ {\delta }_{{\left(1\mathrm{.Math.11}\right)}_n}\left(Y\right)\end{array}\right),$

(54) For all u∈F.sub.2.sup.n, δ.sub.u(Y) denotes the row vector (δ.sub.u(Y.sub.1), . . . , δ.sub.u(Y.sub.Q)) composed of Q components.

(55) When the leakage model dimensionality is determined to be equal to 2, the model may be an affine function according to which equation (3) may be expressed as follows:
X=αY+β1+N  (8)

(56) In equation (8), X∈R.sup.D×Q, N∈R.sup.D×Q, α∈R.sup.D and β∈R.sup.D represent column vectors, Y and 1=(1, . . . , 1) represent row vectors composed of Q entries. Equation (8) is a particular case of equation (3) for affine leakage models with S=2 where α represents the envelope of the signal and β represents the waveform in absence of signals. In this case, the model Y may be assumed centered with zero mean E(Y)=0=(0, . . . , 0) and of unit variance such that Var(Y.sub.q)=E(Y.sub.q.sup.2)=1 for every q=1, . . . , Q.

(57) In step 311, an estimation k of the secret key may be determined. Given the probability density function of the multivariate leakage traces, an estimation algorithm called “distinguisher” may be implemented in step 311 to calculate estimate(s) of the desired secret value(s) according to the optimization of a performance criterion. In the context of secret key estimation, optimal distinguishers are based on the maximization of the probability of successful key recovery criterion which consists in Maximum A Posteriori optimization. When the different key values are uniformly distributed over F.sub.2.sup.n, this criterion reduces to a Maximum Likelihood optimization problem according to which the optimal key estimate {circumflex over (k)} is the solution of the optimization problem given by:

(58) $\begin{array}{cc}\hat{k}=\underset{k\in F_2^n}{\mathrm{argmax}}\left(\underset{\alpha \in R^{D\times S}}{\max }\left(L_k\right)\right)& \left(9\right)\end{array}$

(59) In equation (9), the function L.sub.k represents a “logarithmic likelihood function”.

(60) In embodiments where the secret key is masked using a random mask m∈F.sub.2.sup.n and in presence of multivariate leakage traces and parametric multivariate leakage models of at least partially unknown coefficients, the likelihood function may be expressed as:
L.sub.k=Σ.sub.q=1.sup.Q log(Σ.sub.m=0.sup.2.sup.n.sup.−1P(M=m)p.sub.N(x.sub.q−αy.sub.q))  (10)

(61) In equation (10), P(M=m) denotes the probability of observing the mask m. In general, the distribution of the mask is uniform (such implementations are said to be perfectly masked); however, for efficiency reasons, it is possible to encounter non-uniform mask distributions, such as for instance in the low-entropy masking schemes. In particular, the presented likelihood function also apply in the case where masking is deactivated or not implemented, in which case P(M=m) is equal to zero for all values of m but one value. Combining equations (9) and (10), optimal estimation of the secret key under ML criterion may be obtained by solving the optimization problem given by:

(62) $\begin{array}{cc}\hat{k}=\underset{k\in F_2^n}{\mathrm{argmax}}\left(\underset{\alpha \in R^{D\times S}}{\max }\underset{q=1}{\overset{Q}{.Math.}}\log \left(\underset{m=0}{\overset{2^n-1}{.Math.}}P\left(M=m\right)p_N\left(x_q-\alpha y_q\right)\right)\right)& \left(11\right)\end{array}$

(63) In embodiments where the leakage model is parametric, the logarithmic likelihood function may be composed of statistical models of unknown parameters which are the coefficients of the matrix a. In such embodiments, the optimization problem in equation (11) may be a two-fold optimization problem allowing calculating estimates of the unknown parameters of the leakage model as well as calculating an estimate of the cryptographic secret key.

(64) According to certain embodiments of the invention where the leakage model is parametric, expectation-maximization (EM) techniques may be implemented in step 311 to solve the optimization problem in equation (11). An EM algorithm is an iterative algorithm used in statistics for parameters estimation in statistical models when the random variables involved in the models comprise wholly or partially unknown parameters. Accordingly, given the set of observed values X.sub.q realizations of the random traces X.sub.q, q=1, . . . , Q, the set of mask values m=0, . . . , 2.sup.n−1 and the matrix of unknown coefficients α, EM algorithms operate by iteratively alternating between an expectation step and a maximization step until a convergence of the estimated parameters to local maxima. During the expectation step, the EM algorithm evaluates the expected value of the logarithmic likelihood function with respect to the conditional distribution of m given x.sub.q−αy.sub.q under the current estimates of the missing parameters in the matrix a. During the maximization step, the algorithm finds the parameters of the matrix a that maximize the expected logarithmic likelihood function evaluated in the expectation step.

(65) In certain embodiments where the noise is Gaussian and the cryptographic key is not masked, it was shown that the optimal ML distinguisher in equation (9) is equivalent to solving:

(66) $\begin{array}{cc}\hat{k}=\underset{k\in F_2^n}{\mathrm{argmin}}\underset{\alpha \in R^{D\times S}}{\min }\left(\mathrm{tr}\left({\left(x-\alpha y\right)}^t\stackrel{-1}{.Math.}\left(x-\alpha y\right)\right)\right)& \left(12\right)\end{array}$

(67) In equation (12), tr(M) denotes the trace of the square matrix M computed by summing its diagonal terms.

(68) In such embodiments, the parameters of the leakage model composing the matrix a are treated as part of the values to be estimated with the secret key.

(69) The optimization problem of equation (12) may be solved by calculating estimates of the coefficients of the matrix α according to the inner minimization problem of equation (12), and determining an estimate of the value of the secret key by solving the outer maximization problem. According to this two-steps problem solving, the optimal value of a solution of the inner minimization problem of equation (12) may be given by:
α.sub.opt=(xy.sup.t)(yy.sup.t).sup.−1  (13)

(70) Accordingly, the corresponding expression of the ML distinguisher in equation (12) may be written as:

(71) 0$\begin{array}{cc}\hat{k}=\underset{k\in F_2^n}{\mathrm{argmax}}\mathrm{tr}\left({y^t\left({\mathrm{yy}}^t\right)}^{-1}{\mathrm{yx}}^t\stackrel{-1}{.Math.}x\right)& \left(14\right)\end{array}$

(72) In a particular embodiment where the noise is Gaussian, the leakage model is affine parametric with S=2 and the leakage traces are multivariate with D≥1, the optimal distinguisher of equation (14) may be expressed by:

(73) $\begin{array}{cc}\hat{k}=\underset{k\in F_2^n}{\arg \max }\mathrm{tr}\left(\stackrel{-1}{.Math.}\frac{C\hat{o}v\left(x,y\right)C\hat{o}{y\left(x,y\right)}^t}{V\hat{a}r\left(y\right)}\right)=\underset{k\in F_2^n}{\arg \max }\frac{1}{V\hat{a}r\left(y\right)}\underset{d=1}{\overset{D}{.Math.}}{\left(C\hat{o}v\left(x^{\prime },y\right)\right)}^2& \left(15\right)\end{array}$

(74) Where

(75) $C\hat{o}v\left(x,y\right)=\frac{1}{Q}{\mathrm{xy}}^t-\left(\frac{1}{Q}\underset{q=1}{\overset{Q}{.Math.}}{x}_q\right)\left(\frac{1}{Q}\underset{q=1}{\overset{Q}{.Math.}}{y}_q\right)$
and x′=Σ.sup.−1/2x results from the processing of the data measurement matrix using the standard deviation noise matrix.

(76) More particularly, if the noise is white, for which the matrix Σ is diagonal written in the form Σ=diag(σ.sub.1.sup.2, σ.sub.2.sup.2, . . . , σ.sub.D.sup.2), equation (15) is equivalent to:

(77) $\begin{array}{cc}\hat{k}=\underset{k\in F_2^n}{\arg \max }\underset{d=1}{\overset{D}{.Math.}}\frac{{\left(C\hat{o}v\left(x_d,y\right)\right)}^2}{{\sigma }_d^{2}V\hat{a}r\left(y\right)}& \left(16\right)\end{array}$

(78) In another embodiment where the leakage traces are monovariate with D=1 and the leakage model is an affine parametric model, the optimal ML distinguisher of equation (12) may be simplified as follows:

(79) $\begin{array}{cc}\hat{k}={\underset{k\in F_2^n}{\mathrm{argmax}}\left(\frac{C\hat{o}v\left(x,y\right)}{\sqrt{V\hat{a}r\left(x\right)V\hat{a}r\left(y\right)}}\right)}^2& \left(17\right)\end{array}$

(80) In other embodiments where the leakage model is known by the cryptosystem analyzer, the coefficients of the matrix α∈R.sup.D×S are perfectly known. The ML optimal distinguisher in the context of non-masked secret key in presence of multivariate leakage model and traces may amount to solving:

(81) $\begin{array}{cc}\hat{k}=\underset{k\in F_2^n}{\mathrm{argmax}}\mathrm{tr}\left({\left(x-\alpha y\right)}^t\stackrel{-1}{.Math.}\left(x-\alpha y\right)\right)& \left(18\right)\end{array}$

(82) In addition, in the case of affine leakage models, equation (18) can be written as:

(83) $\begin{array}{cc}\hat{k}=\underset{k\in F_2^n}{\mathrm{argmax}}||\tilde{x}-y{||}_2^2& \left(19\right)\end{array}$

(84) In equation (19), ∥v∥ denotes the Euclidean norm of the vector v and {tilde over (x)} is the vector of Q traces reduced to one single dimension using the linear projection according to:

(85) $\begin{array}{cc}\tilde{x}=\frac{{\alpha }^t\stackrel{-1}{.Math.}}{{\alpha }^t\stackrel{-1}{.Math.}\alpha }\left(x-\mathrm{\beta 1}\right)& \left(20\right)\end{array}$

(86) One advantage of such embodiment is that the linear projection step integrated in the ML distinguisher optimizes the signal-to-noise ratio which is greater than any SNR value obtained from monovariate leakage traces considering a same number of leakage traces and a same leakage model.

(87) In response to the estimation of the secret key in step 311, a performance metric PM may be calculated in step 313. In certain embodiments, a security metric such as the success rate evaluating the rate of successful recovery of the secret value(s) may be used. The rate of successful recovery of secret cryptographic keys is associated with a probability of error representing the probability that the estimated secret key is different from the correct key k* according to:
Pe=Pr({circumflex over (k)}≠k*)  (21)

(88) In step 315, the estimated secret value and the performance metric PM are output.

(89) In certain advantageous embodiments, a batch processing may be considered for determining the secret value(s) estimate(s). Accordingly, in step 303, the side-channel traces are collected by batches of B traces, with 1≤B≤Q. When B=Q, the secret value estimation is performed by processing the totality of the collected leakage traces at the same time. When B=1, an estimate of the secret value is determined on a trace-by-trace basis using Q batches, each batch comprising a single trace. Batch processing using B batches of traces with 1<B<Q may interestingly apply for example when batch processing using individual traces requires an intensive computation of success rate graphs, when the transfer of collected traces from the data acquisition unit 232 to the analysis unit 25 is slow, or when a real-time monitoring of the current calculated secret value(s) is required before the processing of all the leakage traces. In such embodiments, batch processing allows advantageously for faster computations and enables parallelization of the secret value(s) estimation steps. For example, the computational complexity required to process success rate graphs may be alleviated using batch processing to determine alternatively success rate graphs for each batch of traces. The transfer of collected traces from the data acquisition unit to the analysis unit may also be accelerated through batch processing by enabling the transfer of groups of traces rather than transferring each trace separately.

(90) In embodiments using batch processing, the logarithmic likelihood function L.sub.k defined in equation (10) involving the summation of the terms log(Σ.sub.m=0.sup.2.sup.n.sup.−1P(M=m)p.sub.N(x.sub.q−αy.sub.q)) over all the traces for q=1, . . . , Q may be computed by summing the partial terms calculated by batch of traces instead of individual traces. Accordingly, the expression of the optimal ML distinguisher in equation (14) rewrites as:

(91) $\begin{array}{cc}\begin{array}{c}\hat{k}=\underset{k\in F_2^n}{\mathrm{argmax}}\mathrm{tr}\left({\mathrm{Var}\left(y\right)}^{-1}{\mathrm{Cov}\left(x,y\right)}^t\stackrel{-1}{.Math.}\mathrm{Cov}\left(x,y\right)\right)\\ =\underset{k\in F_2^n}{\mathrm{argmax}}\mathrm{tr}\left({y^t\left({\mathrm{yy}}^t\right)}^{-1}{\mathrm{yx}}^t\stackrel{-1}{.Math.}x\right)==\underset{k\in F_2^n}{\mathrm{argmax}}\mathrm{tr}\left({\left({\mathrm{yy}}^t\right)}^{-1}{\left({\mathrm{xy}}^t\right)}^t\stackrel{-1}{.Math.}{\mathrm{xy}}^t\right)\end{array}& \left(22\right)\end{array}$

(92) In equation (22), yy.sup.t (respectively xy.sup.t) may be computed in batch as Var(y) (respectively Cov(x, y)) with

(93) $\mathrm{Var}\left(y\right)=\underset{q=1}{\overset{Q/B}{.Math.}}{y}_{q,B}{y}_{q,B}^t,\mathrm{Cov}\left(x,y\right)=\underset{q=1}{\overset{Q/B}{.Math.}}{x}_{q,B}{y}_{q,B}^t.x_{q,B}$
denotes a D×B matrix whose column vectors represent the leakage traces of index q′ for q′=(q−1)B+1, . . . , qB and y.sub.q,B denotes a S×B matrix of column vectors representing the leakage model corresponding to the leakage traces comprised in the matrix X.sub.q,B.

(94) The secret value estimation methods and devices described herein may be implemented by various means. For example, these techniques may be implemented in hardware, software, or a combination thereof. For a hardware implementation, the processing elements of the estimation device can be implemented for example according to a hardware-only configuration (for example, in one or more FPGA, ASIC or VLSI integrated circuits with the corresponding memory) or according to a configuration using both VLSI and DSP.

(95) FIG. 4 illustrates exemplary hardware architecture of a secret value estimation device 24 according to certain embodiments of the invention. As depicted, the secret value estimation device 24 may comprise computing, storage and communication devices possibly interacting with one another through a data and address link 49 and including: Input peripherals 41 for receiving for example input data from the measurement unit 23 or communicating with the cryptosystem analyzer to control the execution of the various instructions according to the various embodiments of the invention; Processing peripherals 43 comprising one or more microprocessors (CPU) such as an FPGA or an ASIC configured for example to execute the corresponding instructions to run the methods and algorithms according to the various embodiments of the invention; Storage peripherals 45 possibly comprising a random access memory (RAM) or a read-only memory to store for example the measurement series matrix, noise parameters or parameters of the leakage model. Output peripherals 47 comprising communication means such as displays enabling for example man-to-machine interaction between the cryptosystem analyzer and the secret value estimation device 24 for example in the form of a graphical user interface.

(96) While certain embodiments of the invention have been described in relation to the determination of a secret cryptographic key used for encryption/decryption of data, it should be noted that the invention it not limited to such application. For example, the invention also applies to a communication device 20 using cryptographic keys in data signature for ensuring the authenticity of a digital document or message used for example in files and software distributions or financial transactions, or in message authentication codes.

(97) Further, the invention is not limited to estimate secret values implemented in communication devices used in communication systems. For example, the invention may also apply to cryptographic systems used for example in data processing systems such as smart cards, multimedia players and recorders or mobile storage devices like memory cards and hard discs, with logon access monitored by cryptographic mechanisms. The secret value estimation methods and devices according to various embodiments of the invention more generally apply to a wide range of communication and data processing applications such as in the car industry to ensure anti-theft protection, in service provider systems to secure access cards, in RFID tags and electronic keys, in mobile phone devices to authenticate the control and access to batteries and accessories, in manufacturing of embedded devices and equipments to provide a protection of hardware and software algorithms against cloning and reverse engineering, in banking industry to secure banking accounts and financial transactions, etc.

(98) Further, the various embodiments of the invention are applicable to estimate secret cryptographic values used in any cryptographic mechanisms implemented in hardware devices such as electronic circuits, any software cryptographic algorithms operating on computer systems or any hybrid systems deploying both hardware and software cryptographic components. Furthermore, the methods described herein can be implemented by computer program instructions supplied to the processor of any type of computer to produce a machine with a processor that executes the instructions to implement the functions/acts specified herein. These computer program instructions may also be stored in a computer-readable medium that can direct a computer to function in a particular manner. To that end, the computer program instructions may be loaded onto a computer to cause the performance of a series of operational steps and thereby produce a computer implemented process such that the executed instructions provide processes for implementing the functions specified herein.