Protection against passive sniffing

Abstract

The invention relates in particular to a method for securing the execution of a cryptographic algorithm (ALG) against passive sniffing, the method implementing masking (MSK) of data processed by the cryptographic algorithm. The masking (MSK) of said data includes a linear encoding step such as x′=x.Math.L+c, in which x is the data to be masked, x′ is the corresponding masked data, c is a code word included in a linear code C, and L is a matrix made up of linearly independent vectors not included in the linear code C. The invention also relates to a device (SC) implementing such a method.

Claims

1. A method for securing an electronic device executing a cryptographic algorithm against passive sniffing via a side channel based on analyzing a measurable physical parameter of the electronic device during operation, the method comprising: masking data processed by the cryptographic algorithm, including applying a transformation step x′=x.Math.L+c, where x is data to be masked, x′ is the corresponding masked data, c is a codeword included in a linear code C, and L is a matrix consisting of linearly independent vectors not included in the linear code C; and generating the measurable physical parameter of the electronic device by applying the cryptographic algorithm, wherein the measurable physical parameter is communicated via the side channel of the electronic device, and a third-party attacker is unable to correlate the measurable physical parameter with the data processed by the cryptographic algorithm.

2. The method according to claim 1, wherein the codeword c is chosen randomly during each execution of the cryptographic algorithm.

3. The method according to claim 1, wherein the matrix L is randomly chosen one time only for all executions of the cryptographic algorithm (ALG).

4. The method according to claim 1, comprising carrying out an unmasking operation after executing the cryptographic algorithm.

5. The method according to claim 1, wherein the cryptographic algorithm is an algorithm executing a nonlinear operation S, said nonlinear operation S being replaced with a nonlinear operation S′ such that S′(x.Math.L+c)=S(x).Math.L+c′, where c′ is a codeword of the linear code C.

6. The method according to claim 5, wherein the cryptographic algorithm comprises several rounds, each round comprising the same nonlinear operation S, and the nonlinear operation S is replaced with the same nonlinear operation S′ during each round.

7. The method according to claim 5, wherein c′=c.

8. The method of claim 1, comprising transmitting the data processed by the cryptographic algorithm via a communication channel.

9. The method of claim 1, wherein the measurable physical parameter is one of emitted vibration, electromagnetic radiation, or temperature.

10. An electronic device comprising: a processing unit; and a memory storing instructions for securing execution of a cryptographic algorithm against passive sniffing via a side channel based on analyzing a measurable physical parameter of the electronic device during operation, wherein the instructions, when executed on the processing unit, cause the electronic device to: mask data processed by the cryptographic algorithm, including apply a transformation x′=x.Math.L+c, where x is data to be masked, x′ is the corresponding masked data, c is a codeword included in a linear code C, and L is a matrix consisting of linearly independent vectors not included in the linear code C; and generate the measurable physical parameter of the electronic device by applying the cryptographic algorithm, wherein the measurable physical parameter is communicated via the side channel of the electronic device, and a third-party attacker is unable to correlate the measurable physical parameter with the data processed by the cryptographic algorithm.

11. The electronic device according to claim 10, the instructions further causing the electronic device to choose the codeword c randomly during each execution of the cryptographic algorithm.

12. The electronic device according to claim 10, the instructions further causing the electronic device to choose the matrix L randomly one time only for all executions of the cryptographic algorithm.

13. The electronic device according to claim 10, the instructions further causing the electronic device to perform the masking before executing the cryptographic algorithm, to execute the cryptographic algorithm, and to perform an unmasking operation after executing the cryptographic algorithm.

14. The electronic device according to claim 10, wherein the cryptographic algorithm is an algorithm including a nonlinear operation S, the instructions further causing the electronic device to replace the nonlinear operation S with a nonlinear operation S′ such that S′(x.Math.L+c)=S(x).Math.L+c′, where c′ is a codeword of the linear code C.

15. The electronic device according to claim 14, wherein the cryptographic algorithm comprises several rounds, each round comprising the same nonlinear operation S, the instructions further causing the electronic device to replace the nonlinear operation S with the same nonlinear operation S′ during each round.

16. The electronic device according to claim 14, wherein c′=c.

17. The electronic device of claim 10, wherein the electronic device includes a smart card.

18. The electronic device of claim 10, wherein the electronic device includes a personal computer.

19. The electronic device of claim 10, wherein the electronic device includes one of an electronic driver's license, an electronic passport, a secure Universal Serial Bus (USB) key, a secure multimedia (MMC) card, or a secure token.

20. The electronic device of claim 10, wherein the measurable physical parameter is one of emitted vibration, electromagnetic radiation, or temperature.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The invention will be also better understood with reference to the drawings, which show the following:

(2) FIG. 1 illustrates a method according to the invention,

(3) FIG. 2 illustrates a device according to the invention, as well as equipment used in attack attempts on this device.

DETAILED DESCRIPTION

(4) FIG. 1 shows a highly schematic outline of a method according to the invention. In this method, the process starts by masking the data CL_TXT (for “clear text”), for example a data item to be encrypted, during a step MSK, and the cryptographic algorithm ALG to be protected is then executed (for example an encryption algorithm such as AES), then the result is unmasked at the end (in step U_MSK, for “unmask”) in order to restore the value CR_TXT (from “cipher text”, or encrypted text) which would normally have been produced by the algorithm ALG without masking. In other words, if the two steps of masking MSK with a linear code and of unmasking U_MSK (by corresponding decoding) are eliminated so that only the cryptographic algorithm ALG is retained, the same output CR_TXT is obtained from the input CL_TXT, which means that the algorithm has been made more secure by masking it without affecting its interoperability. The masking operations MSK can be integrated with the unmasking operations U_MSK within the cryptographic algorithm, thus obtaining a particular implementation of the cryptographic algorithm ALG which is functionally the same as those of the prior art but which is much more secure against passive sniffing attacks, in particular against the most elaborate attacks such as HODPA attacks. The representation shown in FIG. 1 is simplified to the extent that in the most frequent cases, it is not exactly the known cryptographic algorithm ALG which is executed in step ALG, but a modified version of this algorithm, to enable masking/unmasking in the presence of nonlinear operations.

(5) FIG. 2 shows a smart card SC according to the invention. A smart card is a possible example of a device for which the invention is particularly advantageous, considering its many applications in the field of cryptography (SIM cards authenticating a mobile phone user to an operator, bank cards authenticating the card holder during a financial transaction, health insurance cards, etc.). However, the invention is applicable to any portable device, such as an electronic passport, an e-visa, an electronic driver's license, a secure USB key, a secure MMC card, a secure token, etc. The invention may be also applied in a personal computer, a server, an SSL accelerator, etc. Most personal computers are not secure, unlike a protected device such as a smart card. This makes computers vulnerable to attacks that are much easier to implement than the attacks the invention protects against, such as attacks that are strictly software-based. These software attacks (by a virus, a Trojan horse, etc.) can often be carried out remotely without requiring physical access. It might seem absurd to try to protect against complex and restrictive attacks such as passive sniffing attacks when an attacker located on another continent could take control of the computer remotely and retrieve critical information in a manner that is much easier and less dangerous for him (there is no intrusion, the device is not stolen, etc.). However, some personal computers (for example computers used in military environments) are highly protected against purely software-based attacks, and in this context it is advantageous to protect them against passive sniffing attacks as well.

(6) FIG. 2 also shows a fake smart card FSC, which is merely a connector in the shape of a smart card and having electrical contacts at the standard positions so that these contacts are connected to the corresponding contacts of a real smart card SC via HODPA equipment, enabling an HODPA type of attack. The HODPA equipment is thus serially connected between the real smart card SC being targeted by an attacker, and a fake smart card FSC establishing the physical interface between the terminal that is supposed to accept the real smart card SC, and this real smart card SC. The purpose of the fake smart card FSC in this example is to spy on the current consumption of the smart card SC without having to modify the terminal using the card (and in particular the smart card reader). In the invention, the smart card SC is more resistant to attacks of this type and it is very difficult for HODPA equipment to extract the targeted information from the smart card SC.

(7) As the invention is based on the use of a linear code, it is worthwhile to recall that linear code is a particular type of code for correcting errors. A linear code C is a vector subspace of an n-dimensional vector space F.sub.q.sup.n, where F.sub.q is the finite field with q elements. This can be field F2 (q=2), in which case the linear code is a binary code. Let us call n−k the dimension of the vector subspace corresponding to the linear code C. The linear code C is defined by a generator matrix G. The element c (and more generally any element of the code C) can be broken down into the linear combination form c=m.sub.1v.sub.1+m.sub.2v.sub.2+ . . . +m.sub.n-kv.sub.n-k of a vector basis (v.sub.1, v.sub.2, . . . , v.sub.n-k), or c=mG, where m=(m.sub.1, m.sub.2, . . . m.sub.n-k), G being the generator matrix (of size (n−k)*n). A parity check matrix is also defined of size n*k, such that for every element c of the linear code C, c.Math.H=0, and reciprocally if c.Math.H=0 then c is an element of the linear code C.

(8) In general, m represents a message encoded by the linear code C. However, in the context of the invention, the codeword c does not need to represent a particular message. It can therefore be selected at random, in a manner similar to what is done in the coding employed for a wiretap channel. With a wiretap channel, the goal is to transmit a message from a sender to a receiver in the possible presence of a spy capable of intercepting the communications. It is assumed that the transmission channel is not perfect. The channel coding is arranged so that the message cannot be decoded by the attacker with the bit error rate in the intercepted message, while the message received by the receiver can be decoded with the bit error rate at the receiver.

(9) According to one embodiment of the invention, data protected by the linear code are only used internally within the cryptographic algorithm. This means that there is no concept of a legitimate sender or a legitimate receiver of the data protected by wiretap channel coding, nor a concept of error rate. The linear code is used within the calculations of a cryptographic algorithm, which generally does not need to communicate with other entities during the execution of the actual algorithm. When the device is a multitasking device, this does not rule out the device communicating with the outside while it is executing the cryptographic algorithm. This also does not rule out the device implementing a secure protocol (such as a key exchange protocol, for example Diffie-Hellman, or a protocol based on symmetric cryptography), in which successive cryptographic operations are performed by two parties which progressively exchange the results of the secure protocol in order to obtain for example a common key at the end of the secure protocol. In this context, the invention can be used to protect each cryptographic operation performed under the protocol. A cryptographic algorithm may sometimes erroneously be referred to as a secure protocol such as the one described above. However, in the sense of this invention, this is not a cryptographic algorithm but a protocol which makes use of a succession of cryptographic algorithms. In a modified cryptographic algorithm there will generally be no voluntary transmission of data protected by channel coding through any communication channel. In principle, this means that there is no data loss, unless for example a fault-based attack is present (such as a DFA attack), or if a cryptographic algorithm is executed on a defective electronic device. With the exception of these particular situations, the channel can be considered a perfect virtual channel (because there is no actual transmission of masked data). However, there is a transmission channel for an attacker attempting a passive sniffing attack, which is the side channel used (for example electromagnetic transmissions or power consumption, spied on with an HODPA attack). This channel is not perfect, and it can generally even be considered to be relatively noisy and disrupted by the many countermeasures which are typically present in electronic devices.

(10) According to one embodiment, in order to manipulate sensitive data x having k bits within a cryptographic algorithm while tolerating a leakage of at the most mu bits, one proceeds as follows: a linear code C is established having a generator matrix G of size (n−k)*n, and a parity check matrix H of size n*k such that all of its sub-matrices which have the size (n−mu)*k (namely sub-matrices having (n−mu) rows and k columns) will have the rank k, L.sub.1, L.sub.2, . . . L.sub.k linearly independent k vectors are established which have n bits and which are not included in the linear code C, c=mG is chosen, a codeword which is randomly selected, the sensitive data x, represented in the form of a vector (x.sub.1, x.sub.2, . . . x.sub.k), is then encoded as x′=x.Math.L+c, with x.Math.L=x.sub.1.Math.L.sub.1+ . . . +x.sub.k.Math.L.sub.k. In the case of a linear code C which is a binary code (field F2), the “+” operation can typically be an exclusive OR operation.

(11) This embodiment is advantageous because it can tolerate a number of bits of leakage of up to mu=n−k for arbitrarily large n.

(12) The sensitive data x can be, for example, clear text CL_TXT which is to be encrypted using the cryptographic algorithm ALG to be protected. However, it can also be other information, for example a cryptographic key manipulated during the algorithm ALG, or a subkey such as a round key. It can be also encrypted data which is to be decrypted with the cryptographic algorithm ALG (for example an AES algorithm), data (clear or encrypted) which is to be signed, or signed data for which the signature is to be verified, etc.

(13) Given a generator matrix G for the linear code C, the random selection of a codeword from the linear code C can simply consist of randomly selecting a vector m in the vector space F.sub.q.sup.n-k, then calculating c=mG. This can be done each time the cryptographic algorithm is used.

(14) In order to determine the k linearly independent vectors L.sub.1, L.sub.2, . . . L.sub.k not included in the linear code C and which constitute the matrix L, a first vector L.sub.test can be randomly selected and then one can verify whether this vector is in the code by applying the parity check matrix H (or in other words by calculating L.sub.testH). If the result is zero, then the vector L.sub.test is in the linear code C and the operation is repeated with a new random vector. Otherwise, L.sub.1=L.sub.test is defined and the generation of vector L.sub.test is repeated until a new vector is found which is not in the linear code C, then an algorithm can be executed such as a Gaussian elimination algorithm in order to determine whether the vectors generated up until this point (here L.sub.1 and the last L.sub.test) are linearly dependent. If they are, the last generated vector L.sub.test is abandoned and a new one is randomly selected (until a vector L.sub.test is found which is not in the linear code C). If not, L.sub.2=L.sub.test is defined and a new vector L.sub.test is randomly selected until it is not in the linear code, then a Gaussian elimination is calculated based on all the vectors generated up until this point (L.sub.1 and L.sub.2, which by design are known not to be linearly dependent, plus the last L.sub.test), and so on until there are k independent vectors. These k linearly independent vectors L.sub.1, L.sub.2, . . . L.sub.k can be chosen once and for all for each target device. For example, for a smart card, the vectors could be calculated (separately) for each smart card during the card personalization step of said smart card. They can be also regenerated from time to time, as was explained above.

(15) The invention is particularly advantageous in the context of symmetric encryption/decryption algorithms such as the AES algorithm.

(16) The main steps of a conventional AES algorithm (which is very well known from the prior art) are:

(17) 1. AddRK(K0)=AddRoundKey(K0)

(18) 2. for i from 1 to 9:

(19) (a) S=SubBytes;

(20) (b) SR=ShiftRows;

(21) (c) MC=MixColumns;

(22) (d) AddRK(Ki).

(23) 3. S;

(24) 4. SR;

(25) 5. AddRK(K10)

(26) Thus after having executed, in a preliminary step not shown here, a key expansion operation in which the round keys K0 . . . K10 are derived from a given encryption key, we see the AddRoundKey operation which consists of combining each byte of the state with a round key (by means of an exclusive OR). After that, there is a succession of nine rounds, each round including the SubBytes operation (which is a nonlinear operation in which each byte is replaced with another byte using a substitution table), the ShiftRows operation, which implements a transposition during which each row of the state matrix is cyclically shifted, the MixColumn operation (which combines the four bytes of a column in each column of the state matrix), and finally the AddRoundKey operation already described above. At end of nine rounds, the AES algorithm again executes the SubBytes operation, which is followed by the ShiftRows operation, and then by the AddRoundKey operation.

(27) According to one embodiment, the AES algorithm is protected from end to end in the following manner.

(28) First, a preconfiguration is performed. Unlike the conventional additive masking of the prior art, the operations will be performed using intermediate variables in a different dimension than the one used for the intermediate variables of the conventional AES algorithm. This preconfiguration may be performed one time only (meaning only one time regardless of the number of times the AES algorithm will subsequently be used). The preconfiguration consists for example of generating new operations AddRK′, SR′, and MC′, such that:

(29) AddRK′(K)=AddRK(K).Math.L

(30) SR′(x.Math.L)=SR(x).Math.L

(31) MC′(x.Math.L)=MC(x).Math.L

(32) These calculations are easy to perform (and thus not very costly in terms of performance) because these are linear operations. This preconfiguration step can be performed for example in the factory, during the step of photomasking an electronic component that will implement this embodiment, the modified operations AddRK′, SR′ and MC′ being for example stored in the ROM as part of a smart card operating system. It is also possible to run the AddRK′, SR′ and MC′ operations electronically (for example as hardwired logic), which generally has the advantage of faster execution than when using software executed by a processor.

(33) Next, a preliminary step is executed for each change of mask (this can be done for example each time the AES algorithm is used, or less frequently, in particular if a sufficiently large n parameter is chosen). The preliminary step can consist for example of randomly selecting two codewords c and c′ and generating S′ such that S′(x.Math.L+c)=S(x).Math.c′ for all x (here the same S′ is used for each round of the algorithm for reasons related to performance, although a different S′ could very well be used for each round, which would provide a slight general increase in security).

(34) Finally, a step is executed in which the data x is encrypted using the AES algorithm modified according to the invention, as follows:

(35) 0. calculate x.Math.L+c from x

(36) 1. AddRK′(K0)

(37) 2. for i from 1 to 9:

(38) (a) S′;

(39) (b) SR′;

(40) (c) MC′;

(41) (d) AddRK′(Ki)

(42) (e) x=x+c+MC′(SR′(c′))

(43) 3. S′;

(44) 4. SR′;

(45) 5. AddRK′(K10).

(46) 6. Apply the parity check matrix H to obtain the final result.

(47) In this manner, masking is performed in step 0 using a linear code. In step 2(e), the masking is corrected to take into account the fact that the nonlinear operation uses a constant c′ which is different from the one (constant c) used during the initial masking in step 9. In step 6, a projection of the resulting data is made using the parity check matrix. This eliminates all components which are in the linear code, and the data is thus recovered which would have been produced with the AES algorithm without the masking. In step 6, after the application of the parity check matrix H, it is then possible to perform the inversion of the resulting matrix (x.Math.L).Math.H.

(48) It is also possible to add a mask (another codeword) to the operations using the key (in particular the AddRK′ operation), which further reinforces the masking by making it more difficult to attack. In this case, the step of encrypting the data x with the modified AES algorithm of the invention can then be performed as follows:

(49) 0. calculate x.Math.L+c.sub.1 from x, where c.sub.1 is a random codeword

(50) 1. AddRK′(K0)+c.sub.2, with c.sub.1+c.sub.2=c

(51) 2. for i from 1 to 9:

(52) (a) S′;

(53) (b) SR′;

(54) (c) MC′;

(55) (d) AddRK′(Ki)+c.sub.2

(56) (e) x=x+c.sub.1+MC′(SR′(c′))

(57) 3. S′;

(58) 4. SR′;

(59) 5. AddRK′(K10)+c.sub.3, with random c.sub.3.

(60) 6. Apply the parity check matrix H to obtain the final result.

(61) The code can be chosen so as to minimize operation (e).

(62) In some configurations, instead of performing step (e): x=x+c+MC′(SR′(c′)), it is possible to apply in step (e) a function D(x, c) which takes x and the codeword c as input but not the word c′. This can be achieved for example by using a parity check matrix which is associated with the code including all MC′(SR′(cc)), where cc covers all words of the initial code. The advantage of this embodiment is that it eliminates the need to preserve the c′ value.

(63) A simple example implementation (in particular where SR′ and MC′ are deduced directly from SR and MC) corresponds to the case where x.Math.L has the value [x, 0 . . . 0] (x followed by n−k zeroes).

(64) Of course, the present invention is not limited to the example embodiment described above; it applies to other variants.

(65) Therefore, although a method for securing a step of AES encryption was described above, it is also possible to secure an AES decryption step in the same manner. Moreover, although the described embodiment relates to the AES algorithm, the invention applies to all types of cryptographic algorithms, and in particular to the DES algorithm (and its 3DES variant) and to the RC4 algorithm, but also to asymmetric algorithms or to hash functions (such as SHA-1, MD5, SHA-256, or RIPEMD-160) in which it may be desirable to protect certain linear functions.

(66) Furthermore, the method according to the invention does not exclude the use of other methods. For example, it is possible to combine the method according to the invention with other countermeasures such as the additive masking of the prior art. Such manipulated data can be classified, for example, by level of sensitivity, with the less sensitive data protected by a simple additive mask, the more sensitive data protected by masking according to the invention, and the most sensitive data protected with dual data masking (both the conventional additive masking and the masking according to the invention). All combinations are conceivable.