Classifications

• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
  • H04L9/06—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
  • H04L9/0618—Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation
  • H04L9/0625—Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
  • H04L9/002—Countermeasures against attacks on cryptographic mechanisms
  • H04L9/004—Countermeasures against attacks on cryptographic mechanisms for fault attacks
• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06F—ELECTRIC DIGITAL DATA PROCESSING
  • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
  • G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
  • G06F2207/7219—Countermeasures against side channel or fault attacks

Definitions

• the present invention relates to the protection of a secret key or data (generally a binary word) used in an authentication or identification process of an electronic device (for example, an integrated circuit of a smart card or a electronic card containing one or more integrated circuits) or the like, against hacking attempts.
• the invention relates more particularly to the detection of an attempt to hack the secret data, this detection making it possible to block the component or the process using this secret data, or even to simulate random behavior.
• the invention applies to attacks by statistical analysis of faults (Differential Faults Analysis, DFA) of a digital processing circuit exploiting private or secret data.
• DFA Different Faults Analysis
• the present invention applies more particularly to the protection of a secret key or datum used in a cryptography or encryption algorithm of an input datum by executing a predetermined number of successive iterations of the same function.
• a secret key or datum used in a cryptography or encryption algorithm of an input datum by executing a predetermined number of successive iterations of the same function.
• it is a DES (DATA ENCRYPTION STANDARD) type algorithm described, for example in the book “Handbook of applied cryptography” by Alfred J.
• FIG. 1 illustrates, very diagrammatically in the form of blocks, a conventional example of the DES process.
• a function block 1, F
• a function block 1, F
• the result of the function is then stored again in register 2 but by reversing the respective positions of the right and left parts of the words.
• the number of iterations is variable.
• the algorithm is executed taking into account respectively right (R) and left (L) parts of a word stored in a register 2.
• the result of the function is then stored again in register 2 but by reversing the respective positions of the right and left parts of the words.
• the number of iterations is variable.
• the algorithm is executed taking into account respectively right (R) and left (L) parts of a word stored in a register 2.
• the result of the function is then stored again in register 2 but by reversing the respective positions of the right and left parts of the words.
• the number of iterations is variable.
• the algorithm is executed taking into account respectively right (R) and left (L) parts
• the invention applies to any encryption algorithm by iterations.
• the functions implemented during each iteration are often simple functions (addition (s), multiplication (s), modular reduction (s), permutation (s), substitution (s), etc.) and the encryption efficiency comes from the repetition of these functions on the output data of the previous iteration.
• An attack by statistical analysis of faults generally consists of intervening on the last iteration of an algorithm (for example, DES).
• an algorithm for example, DES
• the encryption operation of the last iteration is carried out, a first time without fault and a second time having caused a fault either in at least one input bit, or in the program clock, or in any development.
• XOR logical addition
• L 16 F ( R 15 ' ⁇ l ⁇ ) ® L 15' or F represents the applied encryption function, where R represents the right part of the result register (R ⁇ 5 representing its content after the 15th iteration), where L represents the left part of the result register (Li5 representing its content after the 15th iteration), and where K represents the subkey implemented for the corresponding iteration (here, the 16th).
• R represents the right part of the result register (R ⁇ 5 representing its content after the 15th iteration)
• L represents the left part of the result register (Li5 representing its content after the 15th iteration)
• K represents the subkey implemented for the corresponding iteration (here, the 16th).
• L 16 ⁇ L 16 f F (R 15 f , K 16 ) ⁇ F (R 15 f , K 16 ), in which only the secret datum K ⁇ g is unknown.
• a first method constituting a countermeasure against DFA attacks is to duplicate the calculations. By carrying out each iterative calculation twice, we consider that we are able to detect if a fault has been introduced during one of the calculations. We then consider that there is little risk that the same fault will occur twice at the same time in the calculation. A disadvantage of this countermeasure method is that it is necessary to duplicate the DES algorithm twice.
• Another drawback is that it is necessary to store the final and intermediate data in registers in order to be able to compare the results of the two calculations to detect a possible attack.
• Another disadvantage is that it is in fact still possible that the same error is reproduced by the hacker with a non-zero probability.
• DPA statistical Power Analysis
• the invention aims to propose a new method for protecting secret data against attacks by statistical analysis of errors.
• the invention aims more particularly to propose a protection method which does not require doubling the iterative algorithm which it is desired to protect.
• the invention also aims to propose a particularly reliable method which in particular makes it possible to avoid the risk of seeing two consecutive errors appear.
• the invention further aims to propose a protection method which is not very demanding, whether in place on the integrated circuit or in computation time with respect to the encryption algorithm proper.
• the invention provides a method for securing a secret quantity, contained in an electronic device, and used at least in part in an encryption algorithm of at least one part of an input data item executing a predetermined number of successive iterations of the same function and producing at least part of an output data item, comprising the following steps: memorizing, after a first number of iterations, a intermediate outcome; applying, to the output data, a function opposite to that of the encryption during a number of iterations corresponding to the difference between the total number of iterations and the first number; compare the intermediate result to the result of the iterations of the inverse function; and to validate the encryption only if said two results are compatible.
• the comparison is carried out after application of a combination function and / or of an expansion function and / or of an arithmetic function, with intermediate results.
• the comparison of the intermediate and inverse function results takes into account only a part of the data.
• the time interval between obtaining the result of the encryption algorithm and the implementation of the iterations of the inverse function is made random.
• the security method is applied to the detection of a hacking attempt by statistical analysis of errors.
• the number of iterations before storing the intermediate result is a function of the probability of discovering the secret quantity according to the iteration to which an error is introduced.
• the security method is implemented by hardware means.
• the security method is implemented by software means.
• the intermediate result is only stored for the time necessary for its comparison with the result from iterations of the inverse function.
• the invention also provides a circuit for encrypting an input datum by means of at least one secret datum.
• FIG. 1 described previously represents, very schematically, an iteration of a conventional DES method of the type to which the present invention applies;
• FIG. 2 illustrates, in the form of block diagrams, an embodiment of the protection method of the invention in hardware form.
• the function proper implemented by the encryption algorithm which one wishes to protect has not been detailed and is arbitrary.
• a characteristic of the present invention is to store, during the execution of the encryption method, an intermediate calculation result corresponding to the result of the algorithm after a predetermined number of iterations.
• Another characteristic of the invention is, at the end of the algorithm, to apply to a number of iterations as a function of the number of iterations of the intermediate result, an inverse function from the final result.
• the memorization of the intermediate result makes it possible to compare this result with that obtained during the application of the iterations of the inverse function. If these results are identical, it can be considered that the circuit has not been the subject of a hacking attempt or that the error caused cannot be exploited by the hacker.
• FIG. 2 illustrates, in the form of a block diagram, an encryption cell 10 of an integrated circuit according to the present invention.
• the example of FIG. 2 relates to the implementation of a DES type encryption method as described above. Note however that the invention applies more generally to any encryption algorithm executing a predetermined number of successive iterations of the same function.
• a message M to be encrypted is, conventionally, introduced into an input / output register 11 (I / O REG) by a bus 12 communicating with the other conventional circuits of the integrated circuit (not shown).
• the register 11 is intended to contain, at the end of encryption, the encrypted message C.
• the number of bits in M and C messages depends on the application. For example, in a DES type process, the M and C messages are generally on sixty-four bits. These sixty-four bits of the message M are sent as input to the encryption cell
• the encryption algorithm may be exclusively implemented in software.
• a validation bit (block 21, FLAG) which will be described below, we start by executing a predetermined number X of iterations of the algorithm (blocks 13, X DES Rd).
• the function implemented at each iteration can correspond to any function of a conventional encryption algorithm. For example, this is the function F of a DES type algorithm as illustrated in FIG. 1.
• the result of the X iterations corresponds to the intermediate result of the invention, stored in a dedicated register (block 14, INT REG).
• Storage in the intermediate register is preferably temporary, that is to say that this register will be erased once the comparison has been made with the result from the application of ⁇ The inverse function as will be seen later.
• the encryption algorithm is ended by executing the remaining NX iterations (block 15, NX DES Rd), where N represents the total number of iterations of the encryption algorithm (16 for a DES algorithm).
• N represents the total number of iterations of the encryption algorithm (16 for a DES algorithm).
• the sixty-four bits resulting from the application of the algorithm are, conventionally, supplied to the input / output register 11 and correspond to the message C.
• NX iterations of the inverse function of the encryption algorithm (block 16, NX INV (DES)) are applied to this message so as to find the intermediate value stored in the register 14.
• the result of the NX reverse iterations is stored in a second temporary register (block 17, TEP REG).
• the comparison is only carried out on part of the messages contained in the registers 14 and 17.
• DES we preferentially compare the right or left part of the messages. Indeed, due to the successive inversions of the right and left parts at each iteration of the encryption algorithm, such a comparison is sufficient.
• the outputs of registers 14 and 17 on sixty-four bits pass through selection gates 19 and 20 respectively so as to supply only thirty-two bits to comparator 18.
• gates 19 and 20 perform any function, provided that 'it is "free collision", that is to say that a modification of an input bit is enough to modify the output.
• the encryption cell provides a validation bit (block 21, FLAG) which, by default, is in a state indicative of an error (a hacking attempt). It is only if the comparator 18 gives a result corresponding to an identity between the intermediate and inverse function results (or compatibility between these results if they pass through a function) that the validation bit 21 switches to the other state. Results are compatible if, applied to the same function (combination, parity bit calculations, CRC, hash function, etc.), they provide equal results.
• the state of the validation bit is used, for example, to authorize the supply of the message contained in the register 11 on the input / output bus 12. Any other use of the validation bit could be envisaged. For example, it can be used to inhibit other functions of the integrated circuit as long as an authentication is not considered to be valid. Or, we can provide, in the event of detected hacking, a random result which will have the effect of distorting the statistical analysis of errors.
• An advantage of the present invention is that it makes pirating by statistical analysis of errors more difficult by making it more difficult to reproduce the same error to be taken into account by the encryption algorithm.
• unlike conventional solutions consisting of carrying out encryption twice for which a possible pirate is liable to cause the same error twice at the same time in the course of the encryption algorithm such reproduction is made almost impossible by the fact that verification is performed on an inverse function. Consequently, by causing an error whether in the first X iterations or in the NX remaining iterations of the function, the same error reproduced at the start of the inverse function will not lead to the same results. This result leads to the fact that the method of the invention is robust, even for errors presented at randomly chosen iterations.
• the execution of the NX iterations of the inverse function of the encryption algorithm is delayed with a random delay in obtaining the result stored in the input / output register. This makes the reproducibility of a fault even less likely at the same stage of the encryption algorithm.
• the choice of the number X of iterations determining the intermediate result stored depends on the application and the encryption algorithm used. In the example of a DES type algorithm of sixteen iterations, we preferentially choose to store an intermediate result after eight iterations. This choice is linked to the fact that, statistically, the encryption key cannot be obtained by analyzing the results of the first eight iterations. Indeed, if an error is introduced during the first eight iterations, the analysis of the result of the encrypted message will not allow the encryption key to be obtained in economically viable time (generally estimated at a few months of data collection tainted with errors and automatic computer calculations). Consequently, the pirate reading of the intermediate register does not weaken the system.
• the comparison will preferably be carried out on all of the bits of the message so as not to miss the detection of an error if it occurred on a non-compared bit.
• the inversion of parts of the messages at each iteration as is the case for the DES algorithm, one can be satisfied with only comparing a part of the messages. Indeed, the probability of not detecting an attack by the introduction of an error is then negligible and a considerable time is saved on the comparison operation.
• the present invention is susceptible of various variants and modifications which will appear to those skilled in the art.
• the encryption algorithm is implemented in hardware, the read / write times in the registers can be used to perform certain calculations in parallel, in particular certain iterations of the inverse function of the encryption algorithm.
• the practical realization of the invention and its adaptation to a conventional encryption algorithm by successive iterations is within the reach of those skilled in the art from the functional indications given above, whether for software implementation. or material.
• the function F and the inversions of FIG. 1 correspond, in this example, to one of the N iterations.
• the invention applies whether the secret data is used in whole or in part in each iteration.
• the method of the invention is compatible with the conventional methods constituting countermeasures to attacks by statistical analysis of consumption.

Landscapes

• Engineering & Computer Science (AREA)
• Computer Security & Cryptography (AREA)
• Computer Networks & Wireless Communication (AREA)
• Signal Processing (AREA)
• Storage Device Security (AREA)

Applications Claiming Priority (3)

Publications (1)

Family

ID=8866949

Family Applications (1)

Country Status (5)

Families Citing this family (30)

Family Cites Families (6)

• 2001
  • 2001-09-04 FR FR0111430A patent/FR2829331B1/fr not_active Expired - Fee Related
• 2002
  • 2002-09-04 JP JP2003527939A patent/JP2005503069A/ja active Pending
  • 2002-09-04 EP EP02785487A patent/EP1423937A2/de not_active Withdrawn
  • 2002-09-04 US US10/488,630 patent/US20050021990A1/en not_active Abandoned
  • 2002-09-04 WO PCT/FR2002/003007 patent/WO2003024017A2/fr not_active Ceased

Non-Patent Citations (1)

Also Published As

Similar Documents

Legal Events