Abstract:
A method of detecting a fault attack including generating a first signature of a first group of data values by performing a single commutative non-Boolean arithmetic operation between all the data values of the first group; generating a second set of data values by performing a permutation of the first set of data values; generating a second signature of the second group of data values by performing said single commutative non-Boolean arithmetic operation between all the data values of the second group; and comparing the first and second signatures to detect a fault attack.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the priority benefit of French patent application Ser. No. 09/58140, filed on Nov. 18, 2009, entitled “Method of Detecting a Fault Attack,” which is hereby incorporated by reference to the maximum extent allowable by law. 
       BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to a method and circuitry for detecting fault attacks, and in particular to method and circuitry providing detection based on signatures. 
         [0004]    2. Discussion of the Related Art 
         [0005]    Integrated circuits may comprise circuitry that is considered sensitive in view of the security of the data it manipulates, such as authentication keys, signatures, etc., or in view of the algorithms it uses, such as encryption or decryption algorithms. Such information is desired to be kept secret, meaning that it should not be communicated to or otherwise be detectable by third parties or unauthorized circuits. 
         [0006]    A common process for pirating information manipulated by an integrated circuit consists in detecting the zones of the circuit that are used during the processing of that information. For this, the circuit is activated or placed in a functional environment and data packets to be encoded are introduced at an input. While the data is being processed, the surface of the integrated circuit is swept by a laser to inject faults in the functioning of the circuit. By analysing in parallel the outputs of the circuit, this enables the zones of the circuit that process the data to be determined. Having localized these zones, the pirate can concentrate attacks on these zones in order to determine the secret data being processed. 
         [0007]    Signatures provide a way of protecting a circuit against fault attacks. A signature is generated based on one or more data values that will be used by an algorithm. A signature is then generated on the same data values after they have been used by the algorithm. A difference in the two signatures will indicate the occurrence of an attack. Once the detection circuit has detected such an attack, it can trigger a counter measure, such as resetting the circuit, and/or incrementing a counter, which renders the integrated circuit permanently inactive once a certain number of faults have been detected. 
         [0008]    Side channel attacks are a different type of attack involving, for example, measuring the power consumption of a circuit. Blinding provides a way of protecting a circuit against side channel attacks. Blinding involves altering the inputs of an algorithm using a random variable in a non-destructive fashion. 
         [0009]    It would be desirable to provide circuits in which the same group of data values can be used to generate signatures to detect fault attacks and be blinded to make side channel attacks harder. However, there are difficulties in implementing effective circuits that combine these functions. 
       SUMMARY OF THE INVENTION 
       [0010]    It is an aim of embodiments of the present invention to at least partially address one or more problems in the prior art. 
         [0011]    According to one embodiment of the present invention, there is provided a method of detecting a fault attack comprising: generating a first signature of a first group of data values by performing a single commutative non-Boolean arithmetic operation between all the data values of the first group; generating a second group of data values by performing a permutation of the first group of data values; generating a second signature of the second group of data values by performing said single commutative non-Boolean arithmetic operation between all the data values of the second group; and comparing the first and second signatures to detect a fault attack. 
         [0012]    According to one embodiment, the first signature and second signature are generated based on the following calculation: S 1 =D 1 +D 2 + . . . +D N , S 2 =D 1 ′+D 2 ′+ . . . +D N ′, wherein D 1  to D N  are the data values of the first group and D 1 ′ to D N ′ are the data values of the second group. 
         [0013]    According to another embodiment, the first signature S 1  and second signature S 2  are generated based on the following calculation: S 1 =D 1 ×D 2 × . . . ×D N , S 2 =D 1 ′×D 2 ′× . . . ×D N ′, wherein D 1  to D N  are the data values of the first group and D 1 ′ to D N ′ are the data values of the second group. 
         [0014]    According to another embodiment, said permutation the first group of data values is performed by applying the exclusive OR between each data value of the first group and a blinding value. 
         [0015]    According to another embodiment, said permutation of the first group of data values is performed by shifting the address of each data value by a blinding value. 
         [0016]    According to another embodiment of the present invention, there is provided a circuit for detecting a fault attack comprising: a blinding block arranged to generate a second group of data values by performing a permutation of a first group of data values; a signature unit arranged to generate a first signature of the first group of data values by performing a single commutative non-Boolean arithmetic operation between all the data values of the first group and a second signature of the second group of data values by performing said single commutative non-Boolean arithmetic operation between all the data values of the second group; and a comparator arranged to compare the first and second signatures to detect a fault attack. 
         [0017]    According to another embodiment of the present invention, there is provided an integrated circuit comprising: a cryptographic block arranged to perform a cryptographic operation on the blinded first group of data values; and the above circuitry. 
         [0018]    According to an embodiment, the first group of data values is an SBOX used during a DES or AES cryptographic operation. 
         [0019]    According to another embodiment of the present invention, there is provided an IC card comprising the above integrated circuit. 
         [0020]    According to another embodiment aspect of the present invention, there is provided an IC card reader comprising the above integrated circuit. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0021]    The foregoing and other purposes, features, aspects and advantages of the invention will become apparent from the following detailed description of embodiments, given by way of illustration and not limitation with reference to the accompanying drawings, in which: 
           [0022]      FIG. 1  illustrates a circuit for detecting fault attacks according to an embodiment of the present invention; 
           [0023]      FIGS. 2 and 3  illustrate the circuit of  FIG. 1  in more detail according to alternative embodiments; 
           [0024]      FIG. 4  illustrates an example of an application of the circuit of  FIG. 1 ; and 
           [0025]      FIG. 5  illustrates an electronic device comprising circuitry for detecting fault attacks according to an embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0026]    For clarity, only those steps and elements useful in an understanding of the invention have been represented in the figures and will be described in detail. In particular, the circuitry for resetting an integrated circuit or rendering it inactive upon detection of one or more fault injections has not been detailed, the invention being applicable to any such circuits. Furthermore, the primary functions of the integrated circuit being protected have not been described in detail, the invention being compatible with integrated circuits implementing any sensitive functions, such as encryption or decryption, or other functions involving sensitive data. 
         [0027]      FIG. 1  illustrates a circuit  100  comprising a function unit  102 , which, for example, implements an algorithm involving sensitive data, such as an encryption key or the like. In the present example, unit  102  receives a key K on an input line  104 . 
         [0028]    A group of data values D 1  to D N  are provided on a line  106  to a blinding block  108 , which applies a blinding algorithm on these data values based on a blinding value R provided on an input line  110  to the blinding block  108 . The blinding value R is for example a pseudo-random value. The blinded data values D 1 ′ to D N ′ are then provided on a line  112  to the function unit  102 . Function unit  102  implements an algorithm that uses the blinded data values D 1 ′ to D N ′, and outputs a result C, which could be an encrypted or decrypted data block, or other value. 
         [0029]    While being used by function unit  102 , the blinded data values D 1 ′ to D N ′ are for example stored in a register. At various stages during execution of the algorithm by the function block  102 , and/or at the end of this execution, the blinded values D 1 ′ to D N ′ are output on a line  114  to a signature block  116 . The original data values D 1  to D N  are also provided to the signature block  116  on a line  118 . 
         [0030]    Signature block  116  generates a signature S 1  based on the original data values D 1  to D N , and a signature S 2  based on the blinded data values D 1 ′ to D N ′. The signatures S 1  and S 2  are then compared by a comparator  120 , which provides an output on an output line  122  indicating whether or not the signatures match. 
         [0031]    The blinding scheme implemented by block  108  and the signature algorithm used by block  116  to generate each of the signatures are chosen such that in the absence of a fault attack, the signatures match. Thus any fault attack aimed at the functional unit  102  is likely to alter one of the blinded data values D 1 ′ to D N ′. 
         [0032]    The blinding scheme implemented by blinding block  108  is chosen to implement a permutation of the data values D 1  to D N . In other words, all the values present in the blinded data value group D 1 ′ to D N ′ are also present in the original data group D 1  to D N . An example of such a blinding scheme is the XOR function, for a blinding value of the same length as the data values D 1  to D N  and applied bit by bit between each of the data values and the blinding value R, assuming for example that each possible value is represented. More generally, blinding with the XOR function causes a permutation when the values represented in the blinded data values D 1 ′ to D N ′ are present an equal number of times in the corresponding blinded data value D 1 ′ to D N ′. In other words, calling the data values D 1  to D N  the set A, and assuming a blinding value R, the following condition should hold: 
         [0033]    for i=1 to N, V=D i  and V=D i  XOR R, V should be present in A the same number of times as V is present in A. 
         [0034]    For example, the data values of the group D 1  to D N  could comprise a complete set of all the possible values for a given bit length. In other words, assuming each data value D 1  to D N  is n bits long, each of the values 0 to 2 (n-1)  occurs once in the data values D 1  to D N . In this case, it follows that all of these values will also be present once in the blinded group D 1 ′ to D N ′, and thus the blinding operation results in a permutation of the data values, without adding or removing new values. 
         [0035]    Alternatively, in the case that the data values D 1  to D N  do not meet condition 1 above, the blinding function  108  could, for example, alter the order of the data values, based on the blinding value R. For example, the blinding value R, which is the same for all of the data values D 1  to D N , could be used to shift the position of the respective data values by R places. 
         [0036]    The signature algorithm applied by signature block  116  is chosen to be a single commutative non-Boolean arithmetic operation applied, for signature S 1 , between all the data values of the group D 1  to D N , and for signature S 2 , between all the data values of the group D 1 ′ to D N ′. In particular, while it would be possible to use a commutative Boolean function, such as XOR function calculated as follows for signature S 1 : 
         [0000]      S 1 =D 1 XOR D 1 XOR D 2 XOR . . . XOR D N , 
         [0037]    such a scheme lacks effectiveness against certain attacks. In particular, a simple Boolean function, such as the XOR function, applied between two n-bit values will not register a difference where the k th  bit of each value is flipped. For example, the XOR of two values computes the Hamming distance between them, and thus if they change by the same amount, the Hamming distance remains the same. 
         [0038]    The present inventors have found that an arithmetic non-Boolean function has much greater effectiveness for detecting such faults. 
         [0039]      FIGS. 2 and 3  illustrate examples of the circuit  100  in which the blinding block  108  performs a permutation on the data values D 1  to D N , for example by applying an XOR function, using the blinding value R. 
         [0040]    Furthermore, as shown in  FIG. 2 , the blinded data values D 1 ′ to D N ′ at the output of the permutation block  108  are provided to the signature block  116 , which in this example performs an addition of each of the data values D 1 ′ to D N ′. Furthermore, before or after generation of signature S 2 , the signature block  116  generates the signature S 1 , by adding together each of the original data values D 1  to D N . Thus S 1  and S 2  are calculated as follows: 
         [0000]        S   1   =D   1   +D   2   + . . . +D   N ; and 
         [0000]        S   2   =D   1   ′+D   2   + . . . +D   N ′
 
         [0041]    This addition is a commutative operation meaning that the order that the addition is performed will not affect the result. The result of this addition will, for example, be a value represented in a greater number of bits that each of the data values D 1  to D N . Assuming each of the data values D 1  to D N  has a bit length equal to n, the signatures S 1  and S 2  are, for example, represented by P bits, where: 
         [0000]        P=n  log 2 ( N )+1 
         [0042]    where N is the total number of data values D 1  to D N , and For example, assuming 16 data values each having 4 bits, the signatures S 1  and S 2  are each for example represented in 17 bits. 
         [0043]    As shown in  FIG. 3 , the blinded data values D 1 ′ to D N ′ at the output of the permutation block  108  are provided to the signature block  116 , which in this example performs a multiplication of each of the data values D 1 ′ to D N ′. Furthermore, before or after generation of signature S 2 , the signature block  116  generates the signature S 1 , by multiplying together each of the original data values D 1  to D N . Thus S 1  and S 2  are calculated as follows: 
         [0000]        S   1   =D   1   ×D   2   × . . . ×D   N ; and 
         [0000]        S   2   =D   1   ′×D   2   ′× . . . ×D   N ′.
 
         [0044]    This multiplication is a commutative operation meaning that the order that the multiplication is performed will not affect the result. The signatures resulting from this multiplication will, for example, be values each represented in a greater number of bits than the number of bits of the data values D 1  to D N . Assuming each of the data values D 1  to D N  has a bit length equal to n, the signatures S 1  and S 2  are, for example, presented by P bits, where: 
         [0000]        P=n   N +1 
         [0045]    where N is the total number of data values D 1  to D N . For example, assuming 16 data values each having 4 bits, the signatures S 1  and S 2  will each be represented in 64 bits. 
         [0046]    In practise, a length m is for example defined as the bit length of the result of the addition of  FIG. 2  or the multiplication of  FIG. 3 , m being greater that n, but less than P, giving a good compromise for providing a uniform distribution of outputs. 
         [0047]    Alternative non-Boolean commutative arithmetic operations could be used to determine the signatures. For example, a combination of an addition and multiplication could be used, such as the product of all the data values added to or multiplied by the sum of all the data values. Additionally or alternatively, to reduce the overall length of the product, only a certain number of bits, such as the 16 least significant bits of the sum and/or product are stored as the signature. 
         [0048]    As a further example, an alternative non-Boolean commutative arithmetic operation would be as follows: 
         [0000]        S   1   =D   1   k   ×D   2   k   × . . . ×D   N   k ; and 
         [0000]        S   2   =D   1 ′ k   ×D   2 ′ k   × . . . ×D   N ′ k  
 
         [0049]    where k is a constant value. 
         [0050]      FIG. 4  illustrates circuitry  400  showing a particular application of the circuitry  100  of  FIG. 1 , in which the function block is a cryptographic block  402  implementing a cryptographic algorithm, such as an encryption or decryption operation. For example, block  402  performs a DES or AES algorithm, based on input data packets P arriving on an input line  404 , a secret key K received on an input line  406 , and an SBOX table received on an input line  408 . The cryptographic block  402  for example generates an output data packet C, provided on an output line  410 . 
         [0051]    In this embodiment, the SBOX comprises the data values D 1  to D N . The SBOX used in such algorithms is in the form of a table used for performing a translation on input data. The SBOX can be public, and for example comprises 256 bytes of data, each of 8 bits. The values in the SBOX comprise a complete set of values for the given number of bits, in other words, assuming each data value is 8 bits, comprising all the value from “00000000” to “11111111”. 
         [0052]    In this embodiment, the cryptographic block  402  performs the blinding is operation on the SBOX on line  408 , by performing the XOR between each value of the SBOX and a blinding value R received on an input line  411 . Then, at a particular stage during processing of the cryptographic algorithm, for example at the same time as or before the packet C is outputted, the blinded SBOX is provided on an output line  412  to the signature block  416 . The signature block  416  generates the signature S 2  using each value of the blinded SBOX. In parallel or beforehand, the signature block  416  generates a signature of the original SBOX received on line  408 . The signatures S 1  and S 2  are compared by the comparator  418 , which provides an output on line  420  indicating whether a mismatch between the signatures has been detected, indicating a fault in the original SBOX or the blinded SBOX. 
         [0053]      FIG. 5  illustrates an electronic device  500  comprising a microprocessor  502 , a memory block  504 , and an input line  506 , which provides input values to the microprocessor  502 . The microprocessor  502  provides output values on an output line  508 . Furthermore, protection circuitry  510  comprises the signature block, comparator and/or blinding block described herein. This circuitry  510  provides an alert signal on an output line  512  provided back to the microprocessor  502 , which for example triggers a reset of the microprocessor  502  and/or increments a counter, which will permanently deactivate the microprocessor once a certain count value has been reached. 
         [0054]    The electronic device  500  is, for example, an IC card, such as a smart card, an IC card reader, such as a credit card payment terminal, or a set-top box, a hard disk for a PC or laptop computer, a PC or laptop computer, a vending machine or other device handling sensitive information. 
         [0055]    An advantage of embodiments described herein is that, by generating signatures by performing a commutative non-Boolean numerical arithmetic operation between all the data values of a permutated group and a non-permutated group, fault detection that is effective and relatively easily implemented is achieved. In particular, the signature scheme is particularly effective at detecting errors which, in other types of signature schemes, would not be detected. 
         [0056]    A particular advantage of generating the signatures based on an addition is that it is easy to implement, and it is more effective than signatures using Boolean operators. In particular, the same fault injected into the same bit position of two of the data values will be detectable. For example, if two data values equal 5 and 6, and a fault is injected into each so that the values become 1 and 2, the XOR before and after the fault injection will still result in “0011”, whereas the addition of these values will change from 11 to 3, thereby indicating a fault. 
         [0057]    An advantage of generating the signatures based on a multiplication of all the data values is that even opposite faults injected into the same bit position of different values can be detected. For example, if two data values equal 5 and 6, and each has a fault injected into its least significant bit, the values will become 4 and 7 respectively. The addition of these values will still equal 11, but the multiplication of these values will have gone from being equal to 30 to 28, thereby indicating a fault. 
         [0058]    While a number of particular embodiments of the present invention have been described, it will be apparent to those skilled in the art that numerous variations and alterations may be applied. 
         [0059]    For example, it will be apparent to those skilled in the art that the embodiments described herein could be applied to a broad range of circuits in which signature verification is used to detect faults. 
         [0060]    Furthermore, it will be apparent to those skilled in the art the embodiments described herein could be implemented in software, hardware or a combination thereof. Additionally, the features described in relation to the various embodiments could be combined in any combination in alternative embodiments. 
         [0061]    Such alterations, modifications, and improvements are intended to be part of this disclosure, and are intended to be within the spirit and the scope of the present invention. Accordingly, the foregoing description is by way of example only and is not intended to be limiting. The present invention is limited only as defined in the following claims and the equivalents thereto.