Secret key estimation methods and devices

Abstract

A secret key estimation device is provided for determining an estimate of at least one secret key used during a number of executions of a cryptographic function used by at least one cryptographic algorithm. The number of executions of the cryptographic function is at least equal to two. The secret key estimation device comprises an analysis unit for determining a plurality of sets of leakage traces from a side-channel information acquired during the number of executions of the cryptographic function. Each set of leakage traces corresponds to an execution of the cryptographic function and comprising at least one leakage trace. The secret key estimation device further comprises a processing unit configured to determine a statistical distribution of the acquired plurality of sets of leakage traces. The statistical distribution is dependent on a leakage function, the leakage function being represented in a basis of functions by a set of real values. The secret key estimation device is configured to determine the secret key from the statistical distribution of the plurality of sets of leakage traces using an estimation algorithm according to the maximization of a performance metric.

Claims

1. A device for determining an estimate of at least one secret key used during a number of executions of a cryptographic function used by at least one cryptographic algorithm, said number of executions of said cryptographic function being at least equal to two, wherein the device is configured to: determine a plurality of sets of leakage traces from a side-channel information acquired during said number of executions of said cryptographic function, the number of said sets of leakage traces being at least equal to two, each set of leakage traces corresponding to one execution of said cryptographic function and comprising at least one leakage trace, said plurality of sets of leakage traces being represented by a measurements matrix, said measurements matrix comprising column vectors, a column vector comprising leakage traces acquired during one execution of said cryptographic function; and determine a statistical distribution of said plurality of sets of leakage traces, said statistical distribution being dependent on a leakage function, said leakage function being represented by a set of unknown real values corresponding to its coordinates in a canonical basis of functions spanning a space vector, said leakage function being the same for all said sets of leakage traces, said device being further configured to determine said statistical distribution of said plurality of sets of leakage traces depending on a noise of a known covariance matrix, wherein the device is configured to determine said at least one secret key from said statistical distribution of said plurality of sets of leakage traces represented by said measurements matrix using an estimation algorithm according to a maximization of a performance metric, wherein said estimation algorithm is an iterative algorithm, said iterative algorithm being applied to jointly determine estimates of said unknown real values representing said leakage function and said at least one secret key.

2. The device of claim 1, wherein the number of said plurality of sets of leakage traces is determined from said number of executions of said cryptographic function.

3. The device of claim 1, wherein the number of leakage traces in each set of leakage traces is determined depending on a signal to noise ratio and/or on a target performance metric.

4. The device of claim 1, wherein said performance metric is chosen in a group consisting of a probability of success secret key calculation, a guessing entropy and a success rate of a given order.

5. The device of claim 1, wherein said iterative algorithm is an expectation maximization algorithm, said expectation maximization algorithm operating by iteratively alternating between an expectation step and a maximization step.

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

7. The device of claim 1, wherein said at least one cryptographic algorithm is a block cipher algorithm, and wherein said cryptographic function is a substitution box and said secret key is a symmetric key.

8. The device of claim 7, wherein said block cipher algorithm is an advanced encryption standard algorithm.

9. The device of claim 5, wherein the expectation step comprises evaluation of an expected value of a logarithmic likelihood function with respect to a conditional distribution of a mask applied to the secret key and the maximization step comprising finding parameters of a vector of unknown values that maximize the expected value of the logarithmic likelihood function evaluated in the expectation step.

10. A method of determining an estimate of at least one secret key used during a number of executions of a cryptographic function used by at least one cryptographic algorithm, said number of executions of said cryptographic function being at least equal to two, wherein said method comprises: determining a plurality of sets of leakage traces from a side-channel information acquired during said number of executions of said cryptographic function, each set of leakage traces comprising at least one leakage trace, said plurality of sets of leakage traces being represented by a measurements matrix, said measurements matrix comprising column vectors, a column vector comprising leakage traces acquired during an execution of said cryptographic function; and determining a statistical distribution of said plurality of sets of leakage traces, said statistical distribution being dependent on a leakage function, said leakage function being represented by a set of unknown real values corresponding to its coordinates in a canonical basis of functions spanning a space vector, said leakage function being the same for all said sets of leakage traces, the method further comprising determining said statistical distribution of said plurality of sets of leakage traces depending on a noise of a known covariance matrix; wherein said method further comprises determining said at least one secret key from said statistical distribution of said plurality of sets of leakage traces represented by said measurements matrix using an estimation algorithm according to a maximization of a performance metric, and wherein said estimation algorithm being an iterative algorithm, said iterative algorithm being applied to jointly determine estimates of said unknown real values representing said leakage function and said at least one secret key.

Description

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 key estimation device;

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

(4) FIG. 3 is a flowchart depicting a method of secret key estimation according to an exemplary embodiment of the present invention;

(5) FIGS. 4a-4d depict several diagrams illustrating the success rate obtained using the secret key estimation method according to certain embodiments;

(6) FIG. 5 is a diagram illustrating the success rate obtained using the secret key estimation method according to certain embodiments; and

(7) FIG. 6 is an exemplary hardware architecture of the secret key estimation device according to certain embodiments of the invention.

DETAILED DESCRIPTION

(8) Embodiments of the invention provide methods and devices for side-channel analysis of cryptographic implementations against one or more side-channel attacks. In particular, embodiments of the invention provide methods and devices for determining at least one estimate of a secret cryptographic key used during a number of executions of a cryptographic function used by a cryptographic algorithm from side-channel leakage information. The leaked information from the analyzed cryptographic system is characterized by a statistical distribution of a plurality of sets of leakage traces. The statistical distribution depends on a leakage function. The leakage function is represented in a canonical basis of functions by a set of unknown values.

(9) Referring to FIG. 1, there is shown an exemplary implementation of a secret key estimation device 13, according to certain embodiments. The secret key estimation device 13 may be implemented to evaluate the security level and vulnerability of the cryptographic system 10 against one or more side-channel attacks during a number of executions of a cryptographic function implemented in a cryptographic algorithm 11 by exploring the acquired side-channel information 12 during a number of executions of the cryptographic function.

(10) Secret value estimation methods and devices according to the various embodiments of the invention may be deployed in the design, manufacturing or certification process to evaluate the security level of a manufactured cryptographic system 10. The cryptographic system 10 may be any information system or device implementing a cryptographic algorithm 11 for ensuring data protection and/or security. The cryptographic algorithm 11 may use a secret cryptographic key for hiding the content of data/information in the form of a “ciphertext”.

(11) The cryptographic system 10 may be used in various storage, information processing or communication systems. For example, in a storage system application of the invention, the cryptographic system 10 may represent any fixed or mobile storage device such as memory cards or hard discs with logon access monitored by cryptographic algorithms. In information processing applications of the invention, the cryptographic system 10 may be for example a computer system, a database, an online sale system or a financial system implementing a cryptographic algorithm 11 for securing data that are to be exchanged or stored in the system, such as personal financial or medical data. In an application of the invention to communication systems, the cryptographic system 10 may be for example a user terminal, a relay or a base station deployed in wireless communication networks, the cryptographic system 10 implementing the cryptographic algorithm 11 for ensuring data security during its transit over unsecure communication media.

(12) Each cryptographic algorithm 11 implemented in the cryptographic system 10 may be associated with an indicator of successful extraction of the secret cryptographic key and a degree of security of the system against side-channel attacks. Such parameters may depend on the leakage model characterization and/or on the calculation algorithms used to determine estimates of the used secret key(s), also referred to hereinafter as “distinguishers”.

(13) The various embodiments of the invention provide secret key estimation methods and devices that do not require any a priori knowledge on the leakage behavior of the cryptographic system. The determination of an estimate of the used cryptographic key may be optimally performed by exploiting the leakage information acquired during the different executions of the cryptographic function.

(14) The following description of certain embodiments will be made with reference to an application of the invention to a communication system, for illustration purposes only. However, the skilled person will readily understand that the various embodiments of the invention may be applied to other types of systems such as data processing or storage systems.

(15) Referring to FIG. 2, there is shown an exemplary implementation of methods and devices for estimating at least one secret key for use by a communication device 20 comprised in a communication system 200. The communication device 20 may be a fixed device, such as a computer operating in a wired communication system, or a mobile device, such as user terminals operational in wireless networks. The communication device 20 may comprise for example:

(16) A Message generator or a message receiver 201 respectively configured to generate output data or receive input data (for example in the form of a signal or a message);

(17) A cryptographic unit 202 implementing a cryptographic algorithm for performing one or more cryptographic operations.

(18) As used herein, a cryptographic operation designates a specific cryptographic processing or function configured to perform a specific task in a cryptographic implementation. Exemplary cryptographic operations comprise data encryption/decryption, message authentication, cryptographically secure pseudorandom number generation, digital signature and cryptographic hash functions calculation.

(19) In exemplary embodiments where the cryptographic unit 202 is configured to perform encryption/decryption, the cryptographic unit 202 may implement at least one cryptographic algorithm using at least one cryptographic secret key. An encryption process or function refers to an encoding of messages or information delivered by the message generator/receiver 201 into a text, referred to as “a ciphertext”. The ciphertext is encoded such that a receiver can only read it if it holds the cryptographic key used to generate the ciphertext. A decryption process or function designates the reverse operation which allows recovering the original text from an encrypted message.

(20) In one embodiment of the invention, the cryptographic algorithm used to encrypt/decrypt data may be a symmetric-key cryptographic algorithm which reuses a same instance of a cryptographic function several times. The repeated calls to the same cryptographic function using different input values or messages may be advantageously exploited for estimating some properties of the cryptographic implementation. Examples of such embodiment comprise block ciphers, like the AES algorithm, which reuse the same instance of a substitution box (noted “S-Box”) during a number of L executions, with L being at least equal to two. A substitution box is a basic component key-based cryptographic function which performs substitution.

(21) In another embodiment of the invention, the cryptographic algorithm may execute several instances of various cryptographic functions simultaneously. Hardware cryptographic implementations of block ciphers are exemplary applications of such embodiments.

(22) The communication device 20 may be configured to communicate secured 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.

(23) 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 during an encryption/decryption process, the processing time required to perform a given cryptographic operation, the electromagnetic emanations, sound or infrared radiations emitted by the communication device 20, etc. Such leaked information may be represented by a series of values (referred to as “side-channel traces”). Leaked information may statistically reveal certain characteristics related to the cryptographic algorithm running in the cryptographic unit 202.

(24) Side-channel leaked information 22 may be collected by a measurement unit 23 configured to gather a plurality of sets of trace measurements from the leaked information during the run time of the communication device 20. The measurement unit 23 may comprise:

(25) a selection unit 231 configured to determine the number Q of traces to be collected for each set of leakage traces;

(26) a data acquisition unit 232 configured to collect samples of traces from the leaked information from the communication device 20. The data acquisition unit 232 may be for example a 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) configured to detect physical properties of the communication device 20 from the leaked information 22 such as voltage, current, power, electromagnetic probes, or temperature or acoustic sensors, etc.

(27) In certain embodiments where the cryptographic unit 202 implements a block cipher which uses a same instance of a substitution box for a number of executions L≤2, the measurement unit 23 may be configured to collect a number of sets of leakage traces lower than or equal to L. For each execution of the substitution box (in general a cryptographic function), the measurement unit 23 may be configured to collect a set of Q traces. In such embodiments, successive calls to the substitution box may be separated by at least one clock period.

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

(29) In other embodiments, the selection unit 231 may be configured to determine the number Q of acquired leakage traces in each set of traces depending on a target performance metric.

(30) The collected traces may be then delivered to the secret key estimation device 24 for determining at least one estimation of a secret key from the sets of leakage traces.

(31) In one embodiment, the secret key estimation device 24 may comprise:

(32) an analysis unit 241 configured to process the acquired sets of leakage traces for removing alignment errors, highlighting signals and/or reducing the noise level;

(33) a processing unit 242 configured to determine a statistical distribution of the collected sets of leakage traces from the data processed by the analysis unit 241. The processing unit 242 may be further configured to generate estimate(s) of secret key(s) using an estimation algorithm and according to the maximization of a performance metric;

(34) a performance evaluation unit 243 configured to calculate a performance metric for measuring the efficiency of the estimation algorithm and the vulnerability of the communication device 20 against one or more side-channel attacks.

(35) In certain embodiments, the processing unit 242 may be configured to determine the statistical distribution of the collected sets of leakage traces depending on a leakage function.

(36) In some embodiments, the processing unit 242 may be configured to determine the statistical distribution of the collected sets of leakage traces depending on a noise of a known covariance matrix.

(37) In one embodiment, the leakage function may be represented in a canonical basis of functions by a set of real values of unknown values.

(38) In one embodiment, the processing unit 242 may be configured to generate estimate(s) of secret keys according to the maximization of the probability of success of key recovery. In such embodiments, the performance evaluation unit 243 may be configured to measure the security level of the communication device 20 by determining the success rate or the rate of successful recovery of the secret key(s) implemented by the cryptographic unit 202. Accordingly, in embodiments where the leakage function is represented in a canonical basis of functions by a set of unknown real values, the processing unit may be further configured to determine estimates of the unknown real values jointly with the estimation of the secret key(s). The processing unit 242 may use an iterative algorithm such as the EM algorithm to jointly determine these estimates.

(39) According to the various embodiments of the invention, there is provided methods and devices for an efficient side-channel analysis of a cryptographic implementation with particular algebraic properties. In particular, the analyzed cryptographic implementation may run various executions or iterative calls of a same cryptographic function, a number L≥2 of times. In contrast to collision attacks that consider only leakage traces corresponding to internal collisions, various embodiments of the invention provide effective and optimal side-channel analysis methods and devices by exploiting the leakage information corresponding to the total executions of the cryptographic function.

(40) FIG. 3 is a flowchart illustrating a secret key estimation method according to an exemplary embodiment of the invention for performing a side-channel analysis and security evaluation of a cryptographic implementation based on a cryptographic algorithm that reuses a same instance of a cryptographic function several times. The secret key estimation method is carried out based on a cryptographic operation previously loaded and run on the analyzed cryptographic device, for example a system analyzer or administrator.

(41) The following description will be made with reference to block ciphers cryptographic algorithms that reuse a same instance of a substitution box during a number of executions L that is at least equal to two for data encryption, for illustration purpose only. However, the skilled person will readily understand that certain embodiments described hereinafter may be also applied to any cryptographic operation using any cryptographic algorithm based on several calls of a given cryptographic function.

(42) In step 300, a cryptographic operation is triggered in the analyzed cryptographic implementation which can run one or more block cipher cryptographic algorithm. A block cipher cryptographic algorithm may execute a same substitution box L times with L≥2. At each execution of the substitution box, a set of messages or text data, referred to commonly hereinafter as ‘plaintext’, may be generated. A cryptographic key may be used at each execution of the substitution box to encrypt the plaintexts into ciphertexts. The secret keys used during the number of the executions of the substitution box and the original data may be represented by bit vectors, each vector comprising n bits. Each secret key may be a deterministic variable while the original data may be random. The cryptographic key used at the l.sup.th execution of the substitution box is denoted as k.sup.(1) ∈{0,1}.sup.n. The knowledge of the plaintexts by the system administrator, without any a priori knowledge on the secret keys, is assumed.

(43) In addition, the secret keys may be masked using a set of unpredictable random masks. A random mask may be represented by a bit vector comprising n bits. The mask may be internally generated by the block cipher. The mask used at the l.sup.th execution of the substitution box is denoted as m.sup.(l) ∈{0,1}.sup.n. A same or different mask may be used for the various executions of the substitution box.

(44) In step 301, the number of sets of leakage traces to be collected may be determined.

(45) In certain embodiments, the number of sets of leakage traces may be determined from the number of executions of the substitution box. In particular, the number of sets of leakage traces may be advantageously equal to the number L of the executions of the substitution box.

(46) The following description will be made with reference to exemplary embodiments where the number of sets of leakage traces to be collected is equal to the number of executions of the substitution box for illustration purpose only.

(47) In step 303, the number Q of the trace measurements to be collected from the leaked information at each execution of the substitution box may be determined. The number Q may be greater or equal to one (1). The number Q may depend on the signal-to-noise ratio denoted by SNR. In certain embodiments, the number Q of the trace measurements may further be determined according to a target performance measure or metric.

(48) Given the determined number of measurements for each execution of the substitution box, L sets of leakage traces comprising each Q traces may be acquired in step 305 during the L executions of the substitution box. Accordingly, the total number of leakage traces to be collected and analyzed while executing L times the same instance of the substitution box is equal to the product of Q by L (Q×L). Data acquisition may be performed through a temporal series of a set of discrete samples. For most cryptographic devices, the leakage signal may be represented as a continuous curve. In certain embodiments, it may be further needed 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.

(49) Accordingly, for the l.sup.th execution, a set of Q plaintexts is generated and processed using the secret cryptographic key k.sup.(l). The plaintext corresponding to the q.sup.th query of the l.sup.th execution is denoted as t.sub.q.sup.(l) for q=1, . . . , Q and l=1, . . . , L. The generated messages L×Q are assumed known by the system analyzer or administrator. The sets of L keys k.sup.(1), . . . , k.sup.(L) are estimated from the acquired total number of L×Q leakage traces.

(50) The signals corresponding to the collected L×Q traces may be then processed in step 307 to improve the data outcome, highlight signals and/or reduce the noise level. The processed leakage traces may be represented by the real value measurements matrix x.sup.(.)∈ R.sup.Q×L.

(51) The measurements matrix may be written in the form x.sup.(.)=(|x.sup.(1)| . . . |x.sup.(l)| . . . x.sup.(L)) where a column vector x.sup.(l)=(x.sub.1.sup.(l), . . . , x.sub.Q.sup.(l)).sup.t ∈ R.sup.Q of index l comprises the Q traces acquired during the l.sup.th execution of the substitution box. Similarly, k.sup.(.)=(k.sup.(1) . . . k.sup.(l) . . . k.sup.(L)) denotes the set of the secret keys processed during the different executions of the substitution box. Alternatively, the measurements matrix may be written in the form x.sup.(.)=(x.sub.1.sup.(.), . . . , x.sub.q.sup.(.), . . . , x.sub.Q.sup.(.)).sup.t where a row vector x.sub.q.sup.(.)=(x.sub.q.sup.(1), . . . , x.sub.q.sup.(L))∈ R.sup.L of index q comprises the L traces of index q corresponding to the total number L of the executions of the substitution box. According to the two notations, the leakage trace corresponding to the q.sup.th query of the l.sup.th execution of the substitution box is denoted as x.sub.q.sup.(l) and may be expressed as:
x.sub.q.sup.(l)=φ(t.sub.q.sup.(l)⊕k.sup.(l))+n.sub.q.sup.(l),l=1, . . . ,L,q=1, . . . Q

(52) In equation (1), φ designates a deterministic leakage function unknown by the system analyzer and assumed to be identical for all executions of the substitution box. t.sub.q.sup.(l) and n.sub.q.sup.(l) designate respectively the generated plaintext and a noise modeling the environment in which is carried out the side-channel analysis and corresponding to the q.sup.th query of the l.sup.th execution of the substitution box.

(53) The leakage function φ: {0,1}.sup.n.fwdarw.R is a pseudo-Boolean function that can be seen as a 2.sup.n-dimensional vector φ(.)∈ R.sup.2.sup.n where R.sup.2.sup.n designates the finite-dimensional Euclidean space equipped with the canonical scalar product. > such that for two vectors φ.sub.1 and φ.sub.2 their scalar product is given by φ.sub.1, φ.sub.2>Σ.sub.zφ.sub.1(z)φ.sub.2(z).

(54) The noise distribution is assumed to be known from the system analyzer and assumed independent and identically distributed zero-mean Gaussian of known covariance. Accordingly, the noise vector n.sub.q.sup.(.)=(n.sub.q.sup.(1), . . . , n.sub.q.sup.(L)) associated to the traces vector x.sub.q.sup.(.) is statistically distributed according to the probability density function p.sub.N.sub.q.sub.(.)(n.sub.q.sup.(.)) given by:

(55) $\begin{array}{cc}{p}_{N_q^{(.Math.)}}\left(n_q^{(.Math.)}\right)=\frac{1}{\sqrt{{\left(2\pi \right)}^L.Math..Math..Math.}}\exp \left(\frac{-1}{2}{n}_q^{{(.Math.)}^t}\stackrel{-1}{.Math.}{n}_q^{(.Math.)}\right)& \left(2\right)\end{array}$

(56) In equation (2), Σ ∈ R.sup.L×L designates the known covariance matrix, the superscript (.).sup.t denotes the transpose operation and |Σ| and Σ.sup.−1 denote respectively the determinant and the inverse of the matrix Σ.

(57) Accordingly, in the presence of Gaussian noise, each leakage trace x.sub.q.sup.(l), q=1, . . . , Q; l=1, . . . , L given the deterministic leakage function cp is normally distributed. The trace vector x.sub.q.sup.(.) is distributed according to the Gaussian distribution N(φ(t.sub.q.sup.(.) ⊕ k.sup.(.)), Σ) of probability density function given by:
p.sub.X.sub.q.sub.(.)(x.sub.q.sup.(.)vφ,t.sub.q.sup.(.),k.sup.(.))=p.sub.N.sub.q.sub.(.)(x.sub.q.sup.(.)−φ(t.sub.q.sup.(.)⊕k.sup.(.)))  (3)

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

(59) In certain embodiments implementing masked cryptographic functions, and in particular when a same mask is used for all the executions of the substitution box m.sup.(1)=m, l=1, . . . , L, the leakage trace in equation (1) may be written as:
x.sub.q.sup.(l)=φ(S(t.sub.q.sup.(l)⊕k.sup.(l))⊕m)+n.sub.q.sup.(l),l=1, . . . ,L,q=1, . . . Q  (4)

(60) In equation (4), S designates the substitution box and m ∈{0,1}.sup.n stands for the mask. The trace vector x.sub.q.sup.(.) in such embodiments is distributed according to the Gaussian distribution N(φ(S(t.sub.q.sup.(.) ⊕ k.sup.(.)) ⊕ m), Σ) of probability density function given by:
p.sub.x.sub.q.sub.(.)(x.sub.q.sup.(.)vφ,t.sub.q.sup.(.),k.sup.(.))=Σ.sub.m=0.sup.2.sup.n.sup.−1P(M=m)p.sub.x.sub.q.sub.(.)(x.sub.q.sup.(.)vφ,t.sub.q.sup.(.),k.sup.(.),m)Σ.sub.m=0.sup.2.sup.n.sup.−1P(M=m)p.sub.N.sub.q.sub.(.)(x.sub.q.sup.(.)−φ(S(t.sub.q.sup.(.)⊕k.sup.(.))⊕m))  (5)

(61) In equation (5), 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 the sake of efficiency, it is possible to encounter non-uniform mask distributions, such as for instance in the low-entropy masking schemes.

(62) Given the statistical distribution of the totality of the acquired leakage traces during the total number of executions of the substitution box, an estimation of at least one secret cryptographic key may be determined in step 309. An estimation algorithm (also called “distinguisher”) may be implemented in step 309 to determine the estimate(s) of the secret keys according to the optimization of a performance metric. A distinguisher D(t.sup.(.), x.sup.(.)) is a function which returns key(s) estimation(s) given the set of known texts t.sup.(.) and the measured leakages x.sup.(.). It may be considered as a map from ({0,1}.sup.n).sup.Q×LR.sup.Q×L to ({0,1}.sup.n).sup.L.

(63) In certain embodiments, Maximum Likelihood distinguishers may be implemented in step 309. The ML distinguisher denoted as D.sub.opt enables, when the different key values are uniformly distributed over {0,1}.sup.n, for the maximization of the probability of success recovery of the secret key(s).

(64) The ML distinguishers may be generally expressed by:

(65) $\begin{array}{cc}{D}_{\mathrm{opt}}\left(t^{(.Math.)},x^{(.Math.)}\right)=\underset{k^{(.Math.)}\in {\left({\left\{0,1\right\}}^n\right)}^L}{\mathrm{argmax}}\left(\underset{\phi :{\left\{0,1\right\}}^n.fwdarw.R}{\max }\left(L\left(k^{(.Math.)},\phi \right)\right)\right)& \left(6\right)\end{array}$

(66) In equation (6), the function L(k.sup.(.), φ) designates a “logarithmic likelihood function”.

(67) The logarithmic likelihood function may be expressed as function of the statistical distribution of the acquired leakage traces according to:
L(k.sup.(.),φ)=log(p.sub.X.sub.(.)(x.sup.(.)vφ,t.sup.(.),k.sup.(.)))=log(Π.sub.q=1.sup.Qp.sub.x.sub.q.sub.(.)(x.sub.q.sup.(.)vφ,t.sub.q.sup.(.),k.sup.(.)))Σ.sub.q=1.sup.Q log(p.sub.x.sub.q.sub.(.)(x.sub.q.sup.(.)vφ,t.sub.q.sup.(.),k.sup.(.)))

(68) In embodiments where the secret keys are masked using a same mask, the likelihood function in equation (7) may be further expressed as:
L(k.sup.(.),φ)=Σ.sub.q=1.sup.Q log(Σ.sub.m=0.sup.2.sup.n.sup.−1P(M=m)p.sub.N.sub.q.sub.(.)(x.sub.q.sup.(.)−φ(S(t.sub.q.sup.(.)⊕k.sup.(.))⊕m)))  (8)

(69) In the presence of masked implementations using equiprobable mask values (i.e. (M=m)=½.sup.n) and Gaussian noise, combining equations (2), (5) and (8), the likelihood function may be expressed as:
L(k.sup.(.),φ)=Σ.sub.q=1.sup.Q log(Σ.sub.m=0.sup.2.sup.n.sup.−1 exp(−½(x.sub.q.sup.(.)−φ(S(t.sub.q.sup.(.)⊕k.sup.(.))⊕m)).sup.tΣ.sup.−1(x.sub.q.sup.(.)−φ(S(t.sub.q.sup.(.)⊕k.sup.(.))⊕m))))  (9)

(70) In particular embodiments, the noise may be isotropic, for which the covariance matrix may be written in the form Σ=σ.sup.2I.sub.L where I.sub.L is the identity matrix of dimensions L×L. In such embodiments, the likelihood function in equation (9) may be simplified to:

(71) $\begin{array}{cc}L\left(k^{(.Math.)},\phi \right)=\underset{q=1}{\overset{Q}{.Math.}}\log \left(\underset{m=0}{\overset{2^n-1}{.Math.}}\exp \left(\frac{-1}{2{\sigma }^2}{.Math.x_q^{(.Math.)}-\phi \left(S\left(t_q^{(.Math.)}\oplus k^{(.Math.)}\right)\oplus m\right).Math.}^2\right)\right)& \left(10\right)\end{array}$

(72) Now, using the expression of the individual leakage traces, the likelihood function in equation (10) may be written as:

(73) $\begin{array}{cc}L\left(k^{(.Math.)},\phi \right)=\underset{q=1}{\overset{Q}{.Math.}}\log \left(\underset{m=0}{\overset{2^n-1}{.Math.}}\exp \left(\frac{-1}{2{\sigma }^2}\underset{l=1}{\overset{L}{.Math.}}{\left(x_q^{\left(l\right)}-\phi \left(S\left(t_q^{\left(l\right)}\oplus k^{\left(l\right)}\right)\oplus m\right)\right)}^2\right)\right)& \left(11\right)\end{array}$

(74) The ML distinguisher accordingly, in the case of masked implementations in the presence of Gaussian isotropic noise may be written as:

(75) $\begin{array}{cc}{D}_{\mathrm{opt}}\left(t^{(.Math.)},x^{\left(.Math.\right)}\right)=\underset{k^{(.Math.)}\in {\left({\left\{0,1\right\}}^n\right)}^L}{\mathrm{argmax}}\underset{\phi :{\left\{0,1\right\}}^n.fwdarw.R}{\max }\underset{q=1}{\overset{Q}{.Math.}}\log \left(\underset{m=0}{\overset{2^n-1}{.Math.}}\exp \left(\frac{-1}{2{\sigma }^2}\underset{l=1}{\overset{L}{.Math.}}{\left(x_q^{\left(l\right)}-\phi \left(S\left(t_q^{\left(l\right)}\oplus k^{\left(l\right)}\right)\oplus m\right)\right)}^2\right)\right)& \left(12\right)\end{array}$

(76) The optimization problem solved by the optimal ML distinguisher in equation (12) involves a double maximization with respect to the leakage function φ and the secret keys k.sup.(l), l=1, . . . , L. Solving this double optimization problem may be performed simultaneously on the pair (k.sup.(.), φ). Alternatively, the resolution of equation (12) may be performed by seeking first the optimal leakage function solution of the inner maximization problem followed by finding the optimal keys forming the solution of the outer optimization problem in the form of a set of keys k.sup.(.).

(77) The ML distinguisher in equation (12) also applies in situations where masking is desactivated or not implemented. The corresponding expression of the ML distinguisher may be in this case simplified and given by:

(78) $\begin{array}{cc}{D}_{\mathrm{opt}}\left(t^{(.Math.)},x^{(.Math.)}\right)=\underset{k^{(.Math.)}\in {\left({\left\{0,1\right\}}^n\right)}^L}{\mathrm{argmin}}\underset{\phi :{\left\{0,1\right\}}^n.fwdarw.R}{\min }\underset{q=1}{\overset{Q}{.Math.}}\underset{l=1}{\overset{L}{.Math.}}{\left(x_q^{\left(l\right)}-\phi \left(t_q^{\left(l\right)}\oplus k^{\left(l\right)}\right)\right)}^2& \left(13\right)\end{array}$

(79) Both optimization problems in equations (12) and (13) involve an optimization over all leakage functions φ: {0,1}.sup.n.fwdarw.R. According to some embodiments of the invention where the leakage function is assumed unknown by the system analyzer, the resolution of these optimization problems may be performed by representing the unknown leakage function φ in the canonical basis of functions. In such embodiments, the leakage function space may be represented using the canonical basis (which is orthonormal) denoted as (δ.sub.u).sub.u∈{0,1}.sub.n such that:

(80) $\begin{array}{cc}{\delta }_u\left(z\right)=\{\begin{array}{c}1\mathrm{ifz}=u\\ 0\mathrm{otherwise}\end{array}& \left(14\right)\end{array}$

(81) Accordingly, the leakage function cp can be decomposed in the canonical basis in the form φ(z)=Σ.sub.u∈[0,1].sub.n φ(u)δ.sub.u(z).

(82) Based on this decomposition, the expression of the ML distinguisher in equation (12) in embodiments using masked cryptographic keys and in the presence of isotropic Gaussian noise may be expressed as:

(83) $\begin{array}{cc}{D}_{\mathrm{opt}}\left(t^{(.Math.)},x^{(.Math.)}\right)=\underset{k^{(.Math.)}\in {\left({\left\{0,1\right\}}^n\right)}^L}{\mathrm{argmax}}\underset{a\in R^{2^n}}{\max }\underset{q=1}{\overset{Q}{.Math.}}\log \left(\underset{m=0}{\overset{2^n-1}{.Math.}}\exp \left(\frac{-1}{2{\sigma }^2}\underset{l=1}{\overset{L}{.Math.}}{\left(x_q^{\left(l\right)}-a_{S\left(t_q^{\left(l\right)}\oplus k^{\left(l\right)}\right)\oplus m}\right)}^2\right)\right)& \left(15\right)\end{array}$

(84) In equation (15), the variable a ∈ R.sup.2.sup.n in the inner optimization problem is associated with the decomposition of the leakage function in the canonical basis of functions such that a=(φ(u)).sub.u∈{0,1}.sub.n.

(85) Similarly, in embodiments where no masking is applied, the optimal ML distinguisher in equation (13) may be expressed as:

(86) $\begin{array}{cc}{D}_{\mathrm{opt}}\left(t^{(.Math.)},x^{(.Math.)}\right)=\underset{k^{(.Math.)}\in {\left({\left\{0,1\right\}}^n\right)}^L}{\mathrm{argmin}}\underset{a\in R^{2^n}}{\min }\underset{q=1}{\overset{Q}{.Math.}}\underset{l=1}{\overset{L}{.Math.}}{\left(x_q^{\left(l\right)}-\underset{u\in {\left\{0,1\right\}}^n}{.Math.}{a}_u{\delta }_u\left(t_q^{\left(l\right)}\oplus k^{\left(l\right)}\right)\right)}^2& \left(16\right)\end{array}$

(87) Using the optimization problems of equations (15) and (16), solving for the optimal leakage function φ is equivalently performed by solving for the optimal components of the vector a ∈ R.sup.2.sup.n.

(88) According to certain embodiments, iterative algorithms may be implemented to solve the optimization problems in equations (15) and (16) enabling for jointly determining estimates of the unknown parameters of the leakage function as well as estimates of the secret cryptographic key(s). Exemplary iterative algorithms comprise expectation maximization (EM) algorithms. 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. For example in the case of masked implementations, given the set of acquired leakage traces x.sub.q.sup.l during the L executions of the substitution box, the set of mask values m=0, . . . , 2.sup.n−1 and the unknown coefficients defining the vector a ∈ R.sup.2.sup.n, 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.sup.(l)−a.sub.s(t.sub.q.sub.(l).sub.⊕k.sub.(l).sub.)⊕m parameters in the vector a. During the maximization step, the algorithm finds the parameters of the vector a that maximize the expected logarithmic likelihood function evaluated in the expectation step.

(89) In response to the estimation of the secret key(s) in step 309, a performance metric PM may be calculated in step 311. In certain embodiments, a security metric such as the success rate evaluating the rate of successful recovery of the secret key(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 keys {circumflex over (k)}.sup.(1), . . . , {circumflex over (k)}.sup.(L) are different from the correct keys {acute over (k)}.sup.(1), . . . , {acute over (k)}.sup.(L) according to:
Pe=Pr(l=1, . . . ,L{circumflex over (k)}.sup.(l)≠{circumflex over (k)}.sup.(1))  (17)

(90) In step 313, the estimated secret keys and the performance metric PM may be output.

(91) FIGS. 4a-4d depict simulation results evaluating the performance of the proposed ML distinguisher (referred to in the legend as ‘Proposed method’) in terms of success rate according to certain embodiments of the invention for a side-channel analysis of a cryptographic implementation based on the PRESENT block cipher algorithm which uses a 4-bits substitution box S (n=4. Simulations are performed under the assumption of a leakage model given by the composition of the Hamming weight leakage model and the substitution box such that the leakage function is given by: φ=W.sub.H∘S. The noise is assumed centered and of variance σ2.

(92) The success rate performance is evaluated for different noise variance values: σ=0 in sub-figures (a), σ=1 in sub-figures (b), σ=2 in sub-figures (c) and σ=3 in sub-figures (d). In addition, the success rate is evaluated considering different number of traces and is compared to the success rate performance of template attacks (referred to in the legend as ‘Optimal’), classical collision attacks (referred to in the legend as ‘Collision’) and correlated enhanced attacks (referred to in the legend as ‘Corr.-enhanced Coll.’). Template attacks are performed on one substitution box and require the knowledge of the leakage model.

(93) The numerical results depicted in FIGS. 4a-4d show the outperformance of the ML distinguisher according to certain embodiments of the invention over the correlation-enhanced collision attacks for low noise and small number of leakage traces. In addition, the success rate performances achieved by the proposed ML distinguisher approach the performances provided by Template attacks, while not requiring any a priori knowledge on the leakage behavior.

(94) Further, a side-channel analysis under the same hypotheses considered for the simulations illustrated in FIGS. 4a-4d are performed on real traces collected from a masked implementation of the AES cipher algorithm with a perfect knowledge of the masks values related to each leakage trace. FIG. 5 illustrates the success rate performance which is obtained for a noise variance σ=1. The results depicted in FIG. 5 relate to an evaluation of the performance in the AES case. Such result match the results obtained with the PRESENT algorithm. The ML distinguisher according to certain embodiments thus provides higher success rate than conventional collision and correlation-enhanced collision techniques.

(95) It should be noted that the examples of FIGS. 4a-4d and 5 are simplified examples for illustrating the success rate which can be obtained with the present invention and are not intended to limit the scope of the invention.

(96) While certain embodiments of the invention have been described in application to the analysis of the side-channel leakage information associated to leaked information from a cryptographic device implementing a same cryptographic function during several times, it should be noted that the invention is not limited to such application. For example, the invention also applies to the side-channel analysis of cryptographic implementations using various cryptographic functions in parallel, at the same time. This is the case for example of hardware implementations of block ciphers where various substitution boxes may be instantiated in parallel. In such embodiments, the measurement unit 23 may be configured to aggregate information leaked from the communication device 20 simultaneously. In such embodiments and where no masking is applied, the acquired leakage may be represented as a single trace expressed as:
x=Σ.sub.l=1.sup.Lφ(t.sup.(l)⊕k.sup.(l))+n  (18)

(97) Accordingly, the optimal distinguisher in equation (13) may be expressed in hardware embodiments as:

(98) 0$\begin{array}{cc}{D}_{\mathrm{opt}}\left(t^{(.Math.)},x\right)=\underset{k^{(.Math.)}\in {\left({\left\{0,1\right\}}^n\right)}^L}{\mathrm{argmin}}\underset{\phi :{\left\{0,1\right\}}^n.fwdarw.R}{\min }{\left(x_q-\underset{l=1}{\overset{L}{.Math.}}\phi \left(t_q^{\left(l\right)}\oplus k^{\left(l\right)}\right)\right)}^2& \left(19\right)\end{array}$

(99) Equations (18) and (19) correspond to block ciphers with no masking schemes. However, the skilled person will readily understand that similar results can be derived in embodiments where the block ciphers implement masks.

(100) Further, 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.

(101) FIG. 6 illustrates exemplary hardware architecture of a secret key estimation device 24 according to certain embodiments of the invention. As depicted, the secret key estimation device 24 may comprise computing, storage and communication devices possibly interacting with one another through a data and address link 69 and including: Input peripherals 61 for receiving for example input data from the measurement unit 23 or communicating with the system analyzer to control the execution of the various instructions according to the various embodiments of the invention; Processing peripherals 63 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 65 possibly comprising a random access memory (RAM) or a read-only memory to store for example the trace measurements or noise parameters. Output peripherals 67 comprising communication means such as displays enabling for example man-to-machine interaction between the system analyzer and the secret key estimation device 24 for example in the form of a graphical user interface.

(102) 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 cryptographic unit 202 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.

(103) Further, the invention is not limited to estimate secret keys 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 key 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.

(104) Further, the various embodiments of the invention are applicable to estimate secret cryptographic values used in any cryptographic implementation 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.