|Publication number||US7471791 B1|
|Application number||US 09/913,884|
|Publication date||Dec 30, 2008|
|Filing date||Jan 20, 2000|
|Priority date||Feb 17, 1999|
|Also published as||CN1630999A, CN100393029C, DE60027163D1, DE60027163T2, EP1198921A2, EP1198921B1, WO2000049765A2, WO2000049765A3|
|Publication number||09913884, 913884, PCT/2000/130, PCT/FR/0/000130, PCT/FR/0/00130, PCT/FR/2000/000130, PCT/FR/2000/00130, PCT/FR0/000130, PCT/FR0/00130, PCT/FR0000130, PCT/FR000130, PCT/FR2000/000130, PCT/FR2000/00130, PCT/FR2000000130, PCT/FR200000130, US 7471791 B1, US 7471791B1, US-B1-7471791, US7471791 B1, US7471791B1|
|Inventors||Jean-Sebastien Coron, Nathalie Feyt, Olivier Benoit|
|Export Citation||BiBTeX, EndNote, RefMan|
|Patent Citations (13), Non-Patent Citations (7), Referenced by (7), Classifications (17), Legal Events (3)|
|External Links: USPTO, USPTO Assignment, Espacenet|
This disclosure is based upon, and claims priority from French Application No. 99/01937, filed on Feb. 17, 1999 and International Application No. PCT/FR00/00130, filed Jan. 20, 2000, which was published on Aug. 24, 2000 in a language other than English, the contents of which are incorporated herein by reference.
The present invention concerns a countermeasure method in an electronic component using a secret key cryptography algorithm. They are used in applications where access to services or to data is strictly controlled. Such components have an architecture formed around a microprocessor and memories, including a program memory which contains the secret key.
These components are notably used in smart cards, for certain applications thereof. These are for example applications involving access to certain databanks, banking applications, remote payment applications, for example for television, petrol dispensing or passing through motorway tolls.
These components or cards therefore use a secret key cryptography algorithm, the best known of which is the DES algorithm (standing for Data Encryption Standard in British and American literature). Other secret key algorithms exist, such as the RC5 algorithm or the COMP128 algorithm. This list is of course not exhaustive.
In general terms and briefly, the function of these algorithms is to calculate an enciphered message from a message applied at the input (to the card) by a host system (a server, banking dispenser etc) and the secret key contained in the card, and supplying this enciphered message in return to the host system, which for example enables the host system to authenticate the component or the card, to exchange data etc.
The characteristics of the secret key cryptography algorithms are known: calculations made, parameters used. The only unknown is the secret key contained in program memory. All the security of these cryptography algorithms relates to this secret key contained in the card and unknown to the world outside this card. This secret key cannot be deduced solely from knowledge of the message applied as an input and the enciphered message supplied in return.
However, it has become apparent that external attacks, based on current consumptions or a differential current consumption analysis when the microprocessor of a card is running the cryptography algorithm in order to calculate an enciphered message, enable ill-intentioned third parties to find the secret key contained in this card. These attacks are referred to as DPA attacks, the English acronym for Differential Power Analysis.
The principle of these DPA attacks is based on the fact that the current consumption of the microprocessor executing the instructions varies according to the data being manipulated.
Notably, when an instruction executed by the microprocessor requires manipulation of data bit by bit, there are two different current profiles depending on whether this bit is “1” or “0”. Typically, if the microprocessor manipulates a “0”, there is at this time of execution a first consumed current amplitude, and if the microprocessor manipulates a “1” there is a second consumed current amplitude, different from the first.
Thus the DPA attack exploits the difference in current consumption profile in the card during the execution of an instruction according to the value of the bit manipulated. In simplified terms, conducting a DPA attack consists of identifying one or more particular periods during which the algorithm is run comprising the execution of at least one instruction manipulating data bit by bit; reading a very large number N of current consumption curves during this period or periods, one curve per different message to which the algorithm is applied; predicting, for each curve, the value taken by a bit of the data for an assumption on a subkey, that is to say on at least part of the secret key, which makes it possible to make the prediction; and making a sort of the curves according to the corresponding Boolean selection function: a first packet of curves is obtained for which the prediction is “1” and a second packet of curves for which the prediction is “0”. By making a differential analysis of the mean current consumption between the two packets of curves obtained, an information signal DPA(t) is obtained. If the subkey assumption is not correct, each packet in reality comprises as many curves corresponding to the manipulation of a “1” as there are curves manipulating a “0”. The two packets are therefore equivalent in terms of current consumption and the information signal is substantially zero. If the subkey assumption is correct, one packet actually comprises the curves corresponding to the manipulation of a “0” and the other packet actually comprises the curves corresponding to the manipulation of a “0”: the information signal DPA(t) is not zero: it comprises consumption peaks corresponding to the manipulation by the microprocessor of the bit on which the sorting is based. These peaks have an amplitude corresponding to the difference in consumption by the microprocessor depending on whether it is manipulating a “1” or a “0”. Thus, step by step, it is possible to discover all or part of the secret key contained in an electronic component.
There are many secret key algorithms for the execution of which the microprocessor must at certain times manipulate data bit by bit.
Notably, the algorithms generally comprise permutations which require such manipulations by the microprocessor. By analysing the current consumption during the execution of these manipulations bit by bit, it is possible to find the value of some bits at least of the data item manipulated. Knowledge of this data item can supply information on intermediate results obtained during the execution of the enciphering algorithm, which in their turn can make it possible to find at least some of the bits of the secret key used.
Three documents resembling the invention whilst being distinguished from it are cited below.
The first document “NTT Review, Vol. 6, No 4, of 1 Jul. 1997, pages 85-90, Miyaguchi S: “Secret key ciphers that change the encipherment algorithm under the control of the key”, XP000460342”, denoted D1, concerns a resolution of a mathematical problem which avoids the known enciphered attacks with a message. The method described modifies the “key schedule”, translated by “subpart of the key in the algorithm”, of any secret key algorithm. However, this method no longer applies to the standard DES algorithm, a well-known secret key algorithm. The technology described in this document consists of effecting data rotations and also data substitution.
The second document “Institute of Electrical and Electronics Engineers, IEEE Global Telecommunications Conference, Phoenix, Ariz., Nov. 3-8, 1997, vol. 2, 3 Nov. 1997, pages 689-693, Yi X et al: “A method for obtaining cryptographically strong 8×8 S-boxes”, XP000737626”, denoted D2, concerns a proposal to improve the S-boxes in the standard DES algorithm intended to improve security on a cryptanalysis level, that is to say in mathematics, but not in physical cryptography.
The third document “FR-A-2 672 402”, denoted D3, concerns a method and device using the standard DES algorithm for constructing a random number generator. The DES algorithm is a secret key algorithm with data such as for example a counter intended to generate as an output a result which can be assimilated to a random number, a result situated outside the DES.
The object of the present invention is to protect the data on which manipulations are made bit by bit, by applying a countermeasure to them, that is to say a scrambling, so that the analysis of the current consumption during the manipulation of this data reveals no information on this data: the information signal DPA(t) will always be zero whatever the subkey or key assumptions made in the DPA attacks.
As claimed, the invention concerns a countermeasure method in an electronic component using a cryptographic algorithm with a secret key K.
According to the invention, the countermeasure method consists, for an operation or a series of operations applied to an input data item and comprising at least one manipulation bit by bit, of first drawing a first random data item of the same size as the first data item, calculating a second random data item by effecting an exclusive OR between the first random data item and the input data item, and successively applying the operation or series of operations to the first random data item and to the second random data item.
In this way, the operation or series of operations manipulates only random data items so that it is no longer possible to implement a DPA attack.
In order to find the output data item corresponding to the application of the series of steps to the input data item, it suffices to calculate the exclusive OR between the first and second random results.
In a first method of applying this countermeasure method, the operation or series of operations relate to a data item calculated from the message to be enciphered.
In a second method of applying the countermeasure method according to the invention, this method is applied to operations relating directly to the secret key and supplying, for each round of the algorithm, the subkey to be used.
In this method of applying the countermeasure method according to the invention, provision is made for effecting a first series of steps according to the method indicated above so that a first random subkey and a second random subkey are obtained.
In this variant, instead of calculating the true subkey for the round in question, these random subkeys are used, so that the true subkey of each round no longer appears in clear: only random subkeys are manipulated.
Thus the present invention is distinguished first of all from document D1 in that it concerns solely the DES without modifying its structure, nor its inputs, nor its data outputs. The XOR operation used described below makes it possible to mask the data with a random parameter.
It is also distinguished from document D2 in that it deals with the problems of physical cryptographies, that is to say it sets out to resolve problems of implementation through the appearance of secondary effects; in addition does not concern the S-boxes but deals with the problems of security during compressions, permutations and expansions of data (cf
Finally, it is distinguished from document D3 in that it uses a random number within the DES algorithm for protecting the execution of the DES against all types of attack.
Other characteristics and advantages of the invention are detailed in the following description given for indication and in no way limitatively, and with reference to the accompanying drawings, in which:
The DES secret key cryptographic algorithm (hereinafter reference will be made more simply to the DES or to the DES algorithm) includes 16 calculation rounds, denoted T1 to T16, as depicted in
The DES begins with an initial permutation IP on the input message M (
The secret key K, which is a word q of 64 bits, itself undergoes a permutation and a compression in order to supply a word r of 56 bits.
The first round comprises an operation EXP PERM on the parameter R0, consisting of an expansion and a permutation, in order to supply as an output a word 1 of 48 bits.
This word 1 is combined with a parameter K1, in an operation of the exclusive OR type denoted XOR, in order to supply a word b of 48 bits. The parameter K1, which is a word m of 48 bits, is obtained from the word r by a shift by one position (the operation denoted SHIFT in
The word b is applied to an operation denoted SBOX, at the output of which a word a of 32 bits is obtained. This particular operation consists of supplying an output data a taken from a table of constants TC0 according to an input data item b.
The word a undergoes a permutation P PERM, giving as an output the word c of 32 bits.
This word c is combined with the input parameter L0 of the first round T1, in a logic operation of the exclusive OR type, denoted XOR, which supplies as an output the word g of 32 bits.
The word h (=R0) of the first round supplies the input parameter L1 of the following round (T2) and the word g of the first round supplies the input parameter R1 of the following round. The word p of the first round supplies the input r of the following round.
The other rounds T2 to T16 occur in a similar fashion, except with regard to the shift operation SHIFT, which is effected on one or two positions according to the rounds in question.
Each round Ti thus receives as an input the parameters Li−1, Ri−1 and r and supplies as an output the parameters Li and Ri and r for the following round Ti+1.
At the end of the DES algorithm (
This calculation of the enciphered message C comprises in practice the following operations:
It can be seen that this algorithm comprises many operations manipulating the data bit by bit, like the permutation operation.
According to the countermeasure method according to the invention, a software countermeasure is applied when the microprocessor which calculates the enciphered message effects a manipulation bit by bit. In this way, the statistical processing and the Boolean selection function of the DPA attack applied to the current consumption curves no longer supplies any information: the signal DPA(t) remains zero whatever the subkey assumptions made.
The software countermeasure according to the invention then consists of making each of the bits manipulated by the microprocessor unpredictable.
The principle of this countermeasure is depicted in
Let an input data item be D.
Let there be an operation OPN to be calculated on this input data item D, the result of which is denoted OPN(D). This operation OPN requires a bit by bit manipulation of the input data item D by the microprocessor; it is a case for example of a permutation.
According to the invention, instead of applying the operation OPN to the input data item D in order to calculate the result OPN(D) of the operation, the following different steps are performed:
This method can equally well be applied to a single operation or to a series of operations.
A first method of applying the countermeasure method according to the invention concerns operations on data calculated from the message (M) to which the algorithm is applied. The input data item D is in this case a data item calculated from the message M.
In a practical example of this first method of application of the algorithm DES depicted in
In the figure the application of this countermeasure to these operations is denoted CM(EXP PERM) and CM(P PERM).
The software countermeasure according to the invention then consists of performing, in place of each operation P PERM and EXP PERM, the operations CM(EXP PERM) and CM(P PERM) according to the calculation sequence described in
Experience shows that it is the first three rounds and the last three rounds which allow DPA attacks. Afterwards, it becomes very difficult or even impossible to predict the bits.
Thus an implementation of a countermeasure method according to the invention which is less expensive in calculation time consists of applying only these first three and last three rounds of the DES.
Different variant applications of the countermeasure method according to the invention concern the drawing of a random value for the first random data item U. Depending on whether or not a great deal of calculation time is available, it is possible to draw a new random value each time, for each of the operations or series of operations for which the countermeasure method according to the invention is implemented.
Or else it is possible to draw a new random value for each round of the algorithm, or a single random value at the start of the algorithm.
The implementation of the countermeasure method according to the invention depends principally on the applications concerned, depending on whether or not it is possible to devote a great deal of additional time to the countermeasure.
A second mode of applying the countermeasure method according to the invention is depicted in
The countermeasure method according to the invention is then applied by protecting the data item, the secret key in this case, before performing these operations, so that it is no longer possible to obtain information by DPA attack.
Thus, and as schematically shown in
In the example, the sequence of operations comprises the following operations KEY PERM, SHIFT, COMP PERM. Then this sequence of operations is applied to each of the two random data items Y and Z, successively. Thus, from these two data items Y and Z applied successively as an input, the data items Y′, PiY′, KiY′, or respectively Z′, PiZ′, KiZ′ are obtained, at the output of the operations KEY PERM, SHIFT, COMP PERM.
A practical example of an application to the DES is shown in
In the DES, the operation KEY PERM is executed only once, at the start, whilst the sequence of operations SHIFT and COMP PERM is executed in each round.
In addition, the output of the operation SHIFT of a round Ti is applied as an input of the operation SHIFT of the following round Ti+1 (see
In order to apply the countermeasure method according to the second mode of application to this DES algorithm, the first operation KEY PERM is then applied to the random data Y and Z, which gives two intermediate random data, denoted Y′ and Z′. These two intermediate random data are successively applied to the operations SHIFT of the first round T1, supplying two intermediate random data denoted P1Y′ and P1Z′. These two random data are on the one hand stored in working memory for the operation SHIFT of the following round (the second round), and on the other hand applied successively to the operation EXP PERM of the first round, in order to supply a first intermediate result K1Y′ and K1Z′.
This procedure is followed in each round. Thus, at each round Ti, a first random result is obtained: KiY′=EXP PERM (SHIFT (Y′)) and a second random result: KiZ′=EXP PERM (SHIFT (Z′));
and the intermediate random data SHIFT (Y′)=PiY′ and SHIFT (Z′)=PiZ′ are stored in working memory for the following round Ti+1.
For each round Ti, it would then be possible to recalculate the corresponding subkey Ki corresponding to the sequence of operations KEY PERM, SHIFT and COMP PERM of this round applied to the secret key K, making an exclusive OR between the two random results KiY′ and KiZ′: Ki=KiY′ XOR KiZ′.
However, preferably and as depicted in
By then effecting an exclusive OR XOR of this intermediate result b′ with the second random result KiZ′, the output data item b=XOR (1, Ki) is found. The following operations are then performed in each round Ti, in order to calculate the parameter b from 1:
b′=1 XOR KiY′ and
b=b′ XOR KiZ′, as shown for the first and second rounds in
In this way, the secret subkey itself is no longer used in calculating the enciphered message, but “random subkeys”: the key is then protected before and during the execution of the cryptographic algorithm, since KiY′ and KiZ′ being random and not known to the external world of the component (or of the card), they are liable to change at each new execution of the cryptography algorithm. It should be noted that, in the application of the countermeasure method according to the invention to the calculation and use of the subkeys, a random value is drawn only once, at the start of execution of the algorithm, before the operations on the secret key.
This second mode of applying the countermeasure method according to the invention to the secret key can advantageously be combined with the first mode of applying the countermeasure method to the calculation of the enciphered message proper, this combination making the countermeasure particularly effective.
The present invention applies to the DES secret key cryptography algorithm, for which examples of implementation have been described. It applies more generally to any secret key cryptography algorithm where the execution by the microprocessor of certain operations requires a bit by bit manipulation of data.
An electronic component 1 using a countermeasure method according to the invention in a DES secret key cryptography algorithm comprises typically, as shown in
|Cited Patent||Filing date||Publication date||Applicant||Title|
|US5168521 *||Jul 24, 1990||Dec 1, 1992||U.S. Philips Corp.||Method of executing an irregular permutation of data protected by encryption|
|US5214701 *||Jul 24, 1990||May 25, 1993||U.S. Philips Corporation||Method of processing data by compression and permutation for microcircuit cards|
|US5550809 *||Aug 16, 1994||Aug 27, 1996||Ericsson Ge Mobile Communications, Inc.||Multiple access coding using bent sequences for mobile radio communications|
|US5625690 *||Nov 15, 1993||Apr 29, 1997||Lucent Technologies Inc.||Software pay per use system|
|US5870470 *||Feb 20, 1996||Feb 9, 1999||International Business Machines Corporation||Method and apparatus for encrypting long blocks using a short-block encryption procedure|
|US5987124 *||Apr 28, 1997||Nov 16, 1999||International Business Machines Corporation||Method and apparatus for encrypting long blocks using a short-block encryption procedure|
|US6278783 *||Jun 3, 1999||Aug 21, 2001||Cryptography Research, Inc.||Des and other cryptographic, processes with leak minimization for smartcards and other cryptosystems|
|US6327661 *||Jun 3, 1999||Dec 4, 2001||Cryptography Research, Inc.||Using unpredictable information to minimize leakage from smartcards and other cryptosystems|
|US6615354 *||Mar 20, 2000||Sep 2, 2003||Hitachi, Ltd.||Information processing equipment|
|US6631471 *||Dec 10, 1999||Oct 7, 2003||Hitachi, Ltd.||Information processing equipment|
|US6940975 *||Aug 19, 1999||Sep 6, 2005||Kabushiki Kaisha Toshiba||Encryption/decryption apparatus, encryption/decryption method, and program storage medium therefor|
|US7073072 *||Mar 17, 1999||Jul 4, 2006||Axalto Sa||Method to prevent power dissipation attacks on a cryptographic algorithm by implementing a random transformation step|
|FR2672402A1||Title not available|
|1||*||Chari et al. "Towards Sound Approaches to Counteract Power-Analysis Attacks", 1999 Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, Springer-Verlag, pp. 398-412.|
|2||*||Kocher et al. "Differential Power Analysis", 1999 Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, Springer-Verlag, pp. 388-397.|
|3||*||Messerges et al. "Investigations of Power Analysis Attacks on Smartcards", 1999, Usenix, pp. 1-12.|
|4||Miyaguchi, S., "Secret Key Ciphers That Change the Encipherment Algorithm Under the Control of the Key", NTT Review, vol. 6, No. 4, Jul. 1, 1994, pp. 85-90.|
|5||*||Schneier et al. "Twofish: A 128-Bit Block Cipher" 1998, Counterpane Systems pp. 1-68.|
|6||Y, X. et al, "A Method for Obtaining Cryptographically Strong 8x8 S-Boxes", IEEE Global Telecommunications Conference, Phoenix, Arizona, Nov. 3-8, 1997, vol. 2, Nov. 3, 1997, pp. 689-693, Institute of Electrical and Electronics Engineers.|
|7||*||Zhu et al. "The Analysis of a New Class of Unbalanced Cast Ciphers", 1997, IEEE pp. 1-4.|
|Citing Patent||Filing date||Publication date||Applicant||Title|
|US8577942||Jul 7, 2004||Nov 5, 2013||Mitsubishi Electric Corporation||Electronic device and data processing device for implementing cryptographic algorithms|
|US8681972 *||May 9, 2008||Mar 25, 2014||Morpho||Method of executing a cryptographic calculation|
|US9141793 *||Dec 26, 2008||Sep 22, 2015||Ingenico Group||Method for securing a microprocessor, corresponding computer program and device|
|US9208333||Mar 30, 2011||Dec 8, 2015||British Telecommunications Public Limited Company||Secure data recorder|
|US20080021940 *||Jul 7, 2004||Jan 24, 2008||Daisuke Suzuki||Electronic Device And Data Processing Method|
|US20090172268 *||Dec 26, 2008||Jul 2, 2009||Compagnie Industrielle Et Financiere D'ingenierie "Ingenico"||Method for securing a microprocessor, corresponding computer program and device|
|US20110213972 *||May 9, 2008||Sep 1, 2011||Sagem Securite||Method of executing a cryptographic calculation|
|U.S. Classification||380/29, 713/193, 380/259|
|International Classification||G06F21/55, H04L9/06, H04L9/10, H04K1/02, G09C1/00, G06K19/07, H04L9/28|
|Cooperative Classification||H04L9/003, H04L2209/08, H04L9/0625, G06F21/558, G06F2207/7219|
|European Classification||G06F21/55C2, H04L9/06C|
|Jan 16, 2002||AS||Assignment|
Owner name: GEMPLUS, FRANCE
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:CORON, JEAN-SEBASTIEN;FEYT, NATHALIE;BENOIT, OLIVIER;REEL/FRAME:012476/0725;SIGNING DATES FROM 20011212 TO 20020107
|Feb 12, 2009||AS||Assignment|
Owner name: GEMALTO SA, FRANCE
Free format text: MERGER;ASSIGNOR:GEMPLUS;REEL/FRAME:022248/0188
Effective date: 20081001
|May 25, 2012||FPAY||Fee payment|
Year of fee payment: 4