Abstract:
A fault detection method for an encryption/decryption system based on a block cipher comprises the steps of subjecting a state array (CST) to multiple rounds, each round comprising a same series of sequential operations transforming the state array; storing the state of a reference operation (ShiftRows) of a current round as a checkpoint state (CHK); storing the state of the reference operation in the next round as an intermediate state; applying one round of reciprocal operations to the intermediate state, starting from the reciprocal of the reference operation (InvShiftRows); and comparing the result state of said one round of reciprocal operations with the checkpoint state.

Description:
FIELD 
       [0001]    The present invention relates to encryption standards, and more specifically to a fault detection method in a system implementing a block cipher such as defined by the AES standard (“Advanced Encryption Standard”). 
       BACKGROUND 
       [0002]      FIG. 1A  is a flowchart illustrating the operations involved in an encryption process or cipher according to the AES standard. The process takes a 128-bit word of “plaintext” PTXT and transforms it through sequential operations into a 128-bit word of “ciphertext” CTXT. The operations are performed on a two-dimensional array of bytes called the “state”. 
         [0003]    As depicted in  FIG. 1A , the operations may be grouped in an initial round, a series of N−1 rounds of the same four sequential operations, and a final round, where N depends on the cipher key size. The cipher key may have a size of 128, 192 or 256 bits, yielding respective values 10, 12 or 14 for N. 
         [0004]    Each round includes a sequential combination of the following four operations:
       AddRoundKey: a transformation in which a round key is added to the state using an exclusive-OR operation. A different round key is used in each round, taken from a key schedule derived from the cipher key.   SubBytes: a transformation that processes the state using a non-linear byte substitution table (S-box) that operates on each of the state bytes independently.   ShiftRows: a transformation that processes the state by cyclically shifting the last three rows of the state by different offsets.   MixColumns: a transformation that takes all of the columns of the state and mixes their data (independently of one another) to produce new columns.       
 
         [0009]    In  FIG. 1A , the initial round includes one operation AddRoundKey. Follow N−1 rounds of the sequence of operations SubBytes, ShiftRows, MixColumns and AddRoundKey. The final round differs from the previous rounds by the omission of the MixColumns operation, i.e. it includes the sequence of operations SubBytes, ShiftRows and AddRoundKey. 
         [0010]      FIG. 1B  is a flowchart illustrating the operations involved in a decryption process or inverse cipher according to the AES standard. The process takes a 128-bit word of ciphertext CTXT and transforms it through the reciprocal operations of the encryption process of  FIG. 1A  into a 128-bit word of plaintext PTXT. 
         [0011]    Each of the operations of  FIG. 1A  is replaced in  FIG. 1B  by its reciprocal operation in reverse order. The reciprocal operations have the same labels as in  FIG. 1A , prefixed by “Inv”. The AddRoundKey operation is its own reciprocal. 
         [0012]    Each of the processes of  FIGS. 1A and 1B  is usually called a cipher calculation, or simply a cipher. 
         [0013]    In some circumstances, there is a need to detect faults that may modify the result of the process. Such faults may be injected by an attacker in attempts to guess the cipher key, but can also happen due to a malfunction of the device, for example by single event upsets (SEU). 
         [0014]    Straightforward fault detection techniques may be based on applying a cipher twice and comparing the results of the two ciphers. It is unlikely that a fault will affect the two cipher calculations in the same way, whereby a difference in the results will imply a fault. The second cipher may be calculated by duplicate hardware, effectively doubling the circuit surface area of the function, or by using the same hardware twice, effectively doubling the cipher calculation times. 
       SUMMARY 
       [0015]    A general fault detection method is provided herein for an encryption/decryption system based on a block cipher, comprising the steps of subjecting a state array to multiple rounds, each round comprising a same series of sequential operations transforming the state array; storing the state of a reference operation of a current round as a checkpoint state; storing the state of the reference operation in the next round as an intermediate state; applying one round of reciprocal operations to the intermediate state, starting from the reciprocal of the reference operation; and comparing the result state of said one round of reciprocal operations with the checkpoint state. 
         [0016]    The method may comprise the steps of performing the rounds sequentially using a first hardware accelerator configured to carry out the operations of one round; and performing the round of reciprocal operations in parallel using a second hardware accelerator configured to carry out the reciprocal operations of one round. 
         [0017]    Each round may comprise sequentially substituting bytes from the content of the state array; shifting rows; mixing columns; adding a round key; and writing the add round key result in the state array. The mentioned reference operation may then be shifting rows. 
         [0018]    Each round may comprise sequentially inverse shifting rows from the content of the state array; inverse substituting bytes; adding a round key; inverse mixing columns; and writing the inverse mixing columns result in the state array. The mentioned reference operation may then be inverse substituting bytes. 
         [0019]    The method may comprise the additional steps of generating and storing a reverse key from a cipher key using key expansions; applying reciprocal key expansions to the reverse key and comparing the result to the cipher key; and in each round, expanding a new round key from the cipher key and comparing the last round key to the stored key. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0020]    Other advantages and features will become more clearly apparent from the following description of particular embodiments of the invention provided for exemplary purposes only and represented in the appended drawings, in which: 
           [0021]      FIGS. 1A and 1B , previously described, are respective flowcharts of an AES cipher and an AES inverse cipher; 
           [0022]      FIGS. 2A and 2B  are high-level block diagrams of respective hardware accelerators for carrying out the AES ciphers of  FIGS. 1A and 1B , including each an embodiment of fault detection hardware according to the invention; 
           [0023]      FIGS. 3A and 3B  are more detailed block diagrams of respective exemplary hardware accelerators for integrally carrying out the AES ciphers of  FIGS. 1A and 1B ; 
           [0024]      FIG. 4  is an unrolled flowchart illustrating a straightforward operation possibility of the accelerator with fault detection of  FIG. 2A ; 
           [0025]      FIGS. 5A and 5B  are unrolled flowcharts illustrating operation possibilities of the accelerators with fault detection of  FIGS. 2A and 2B , respectively, using the circuits of  FIGS. 3A and 3B ; 
           [0026]      FIG. 6  is a more detailed block diagram of an exemplary hardware accelerator including an embodiment of a fault detection circuit based on the accelerators of  FIGS. 3A and 3B ; and 
           [0027]      FIG. 7  is a block diagram of an embodiment of fault detection hardware for the AES key expansion process. 
       
    
    
     DESCRIPTION OF EMBODIMENTS 
       [0028]    A fault detection approach as disclosed herein, for a system implementing a block cipher, is based on the assumption that the system implements bidirectional encrypted communication and will therefore implement the cipher and its inverse using separate hardware accelerators. In such a case, both accelerators are generally not active simultaneously. The idle hardware accelerator may then be used for detecting faults in the active hardware accelerator, as disclosed hereunder. 
         [0029]      FIG. 2A  is a high-level block diagram of a hardware accelerator for carrying out the AES cipher of  FIG. 1A , including an embodiment of a fault detection circuit using the accelerator for the inverse cipher of  FIG. 1B . The accelerator may comprise four combinational logic circuit blocks  20  connected in cascade for carrying out in one clock cycle the four operations of the round loop of  FIG. 1A , i.e. SubBytes, ShiftRows, MixColumns, and AddRoundKey. The ShiftRows operation may be performed in hardware by a fixed wire-routing pattern between the output of circuit SubBytes and the input of circuit MixColumns. The intermediate state of each round produced by circuit AddRoundKey may be stored in a register CST (Ciphertext STate) at the rhythm of a round clock RCK. The content of register CST may be used as the input state of the accelerator for the next round determined by clock RCK. 
         [0030]    For detecting faults in the rounds implemented by the accelerator, the content of register CST may be fed in parallel to a series of combinational logic circuit blocks  22  configured for performing the reciprocal operations of the round within one clock cycle, i.e. AddRoundKey, InvMixColumns, InvShiftRows, and InvSubBytes. This reciprocal logic thus “undoes” the effect of the round by reproducing the input state of the round from the current output state of the round, provided both AddRoundKey operations use the same round key. 
         [0031]    The input state of the accelerator is stored at each round as a checkpoint in a register CHK and is compared at  24  to the output state of the reciprocal logic  22 . 
         [0032]    If the output state of the reciprocal logic  22  and the checkpoint state don&#39;t match, then a fault occurred in the round in the accelerator, the reciprocal logic, or both. Comparator  24  signals this fault, whereby appropriate measures can be taken by further hardware or software. 
         [0033]      FIG. 2B  is a high-level block diagram of a hardware accelerator for carrying out the AES inverse cipher of  FIG. 1B , including an embodiment of a fault detection circuit using the accelerator for the cipher of  FIG. 1A . The accelerator is in fact symmetrical to the accelerator of  FIG. 2A  in that the logic circuits  20  and  22  are exchanged. The logic circuit  22  is used for performing the rounds, whereas the logic circuit  20  is used for detecting faults in each round. 
         [0034]    The intermediate state of each round is stored in a register designated by PST (Plaintext STate) instead of CST and the checkpoint state comparator is designated by  26 . 
         [0035]    It is apparent from  FIGS. 2A and 2B  that the circuitry  20  for the encryption path may be reused for checking the circuitry  22  for the decryption path, and reciprocally. Therefore, in integrated circuits that implement bidirectional encrypted paths, fault detection in one path may be achieved by reusing idle hardware of the other path, i.e. at no extra hardware cost. The fault detection occurring in parallel with the rounds, there is no time cost either. 
         [0036]      FIG. 3A  is a more detailed block diagram of an exemplary accelerator circuit  20 ′ for integrally carrying out the AES encryption of  FIG. 1A  in N+1 cycles of clock RCK. Same labels designate same elements as in  FIG. 2A . One or two multiplexers may be inserted in the circuit loop to perform the final (i=N), or initial (i=0) and final (i=N) rounds without duplicating AES functions. A first multiplexer  30  is configured to open the circuit loop and feed an input plaintext word PTXT to circuit AddRoundKey in the initial round (i=0). The second multiplexer  32  is configured to bypass circuit MixColumns in the final round (i=N). The AddRoundKey circuit receives a new round key Ki in each round i. 
         [0037]    With this configuration, N+1 clock cycles after providing the input plaintext word PTXT, register CST contains the desired ciphertext word CTXT. 
         [0038]    In an alternative embodiment, requiring only N clock cycles, the multiplexer  30  may be placed at the output of circuit AddRoundKey. The plaintext word PTXT is then provided to the multiplexer  30  through an additional AddRoundKey circuit. 
         [0039]      FIG. 3B  is a more detailed block diagram of an exemplary accelerator circuit  22 ′ for integrally carrying out the AES decryption of  FIG. 1B  in N+1 cycles of clock RCK. Same labels designate same elements as in  FIG. 2B . In fact, the operations of logic circuit  22  are not performed in the same order as in  FIG. 2B —the operations are reordered circularly to perform a modified version of the flow-chart of  FIG. 1B , comprising N−1 rounds of a loop shown in dotted lines in  FIG. 1B , i.e. InvShiftRows, InvSubBytes, AddRoundKey, and InvMixColumns. 
         [0040]    One or two multiplexers may be inserted in the circuit loop to perform the final (i=N), or initial (i=0) and final (i=N) rounds without duplicating AES functions. A first multiplexer  34  is configured to open the circuit loop and feed an input ciphertext word CTXT to circuit AddRoundKey in the initial round (i=0). The second multiplexer  36  is configured to bypass circuit MixColumns in the initial and final rounds (i=0 and i=N). The AddRoundKey circuit receives a new round key Ki in each round i. 
         [0041]    With this configuration, N+1 clock cycles after providing the input ciphertext word CTXT, register PST contains the desired plaintext word PTXT. 
         [0042]    In an alternative embodiment, requiring only N clock cycles, the multiplexer  34  may be placed at the output of circuit AddRoundKey. The ciphertext word CTXT is then provided to the multiplexer  34  through an additional AddRoundKey circuit. 
         [0043]      FIG. 4  depicts the flowchart of  FIG. 1A  with its loop unrolled, together with the corresponding fault detection operations such as indicated in  FIG. 2A . Each of rounds RND 1 to RND N−1 may be performed by circuit  20  and ends with the operation AddRoundKey, the result of which is stored in register CST to be used as the input for the next round. The reciprocal operations that may be performed by circuit  22  start from the content of register CST and continue in parallel with the operations of the next round. 
         [0044]    All N+1 rounds depicted in  FIG. 4 , especially the initial round and the final round, may me performed integrally by the encryption accelerator  20 ′ of  FIG. 3A . However, the order of the operations of circuit  22  as shown in  FIG. 4  may differ from the order of the operations performed by the actual decryption accelerator, which is the case if the decryption accelerator  22 ′ of  FIG. 3B  were to be used. 
         [0045]      FIG. 5A  is an unrolled flowchart similar to that of  FIG. 4 , illustrating alternative fault detection operations that may be performed using the actual decryption accelerator  22 ′ of  FIG. 3B . Instead of taking its input from register CST, i.e. the output of the AddRoundKey operation, circuit  22 ′ takes its input from a selected reference operation that may be anywhere between the first and last operations of one round, for instance the ShiftRows operation. Thus, the fault detection rounds may not start in synchronization with the encryption rounds, which however does not affect the correct operation of the fault detection. 
         [0046]      FIG. 5B  is an unrolled flowchart reciprocal to that of  FIG. 5A , where the roles of the circuits  20 ′ and  22 ′ are exchanged to perform a decryption with fault checking. 
         [0047]      FIG. 6  is a more detailed block diagram of an exemplary hardware accelerator designed to implement the encryption operations of  FIG. 5A  using the accelerators of  FIGS. 3A and 3B . Moreover, this structure is configured to detect faults in all N+1 encryption rounds with minor hardware modifications to the circuits of  FIGS. 3A and 3B . 
         [0048]    The encryption accelerator  20 ′ is unchanged. The decryption accelerator  22 ′ may be adapted for the fault detection needs with a multiplexer. In addition, some logic and registers may be used to compare the result. This logic can be reused in the reverse direction. A first multiplexer, not shown, may be provided to connect the input of the circuit InvShiftRows to the output of circuit ShiftRows of accelerator  20 ′ through a register REG. The register REG is clocked by signal RCK to store the intermediate state produced by circuit ShiftRows in each round. A multiplexer  60  is configured to select the output of the AddRoundKey circuit in the first round (i=0) and the output of register PST in the other rounds. The multiplexer  60  produces the re-calculated initial state to compare at  62  to the checkpoint state. 
         [0049]    The checkpoint state is stored in two cascaded registers CHK clocked by signal RCK. An additional register CHK is provided in this configuration because the circuit  22 ′ operates one round behind circuit  20 ′. A multiplexer  64  is configured to select the input plaintext word PTXT as the checkpoint state in the initial round (i=0). In the other rounds, the multiplexer  64  selects the content of register REG as the checkpoint state. 
         [0050]    The multiplexers  34  and  36  present in circuit  22 ′ for the decryption rounds are set in a fixed state forcing the use of all four available operations, i.e. connecting circuit InvSubBytes to circuit AddRoundKey, and not bypassing circuit InvMixColumns. 
         [0051]    Since the circuit  22 ′ operates two rounds behind the circuit  20 ′, the AddRoundKey operation of circuit  22 ′ uses a key two rounds behind (Ki−2), while the AddRoundKey operation of circuit  20 ′ uses the current round key (Ki). For the same reasons, the multiplexer  60  is controlled with two rounds delay, as shown by two flip-flops FF at the control input of the multiplexer. 
         [0052]    The final round of  FIG. 5A  only includes the AddRoundKey operation. The structure as shown in  FIG. 6  does not detect faults in this last operation. If detecting faults is desired in this case, the content of register PST after the last loop iteration may be fed back into the circuit for the final round via the CTXT input of multiplexer  34 , while multiplexer  36  is controlled to bypass circuit InvMixColumns. 
         [0053]    The circuits of  FIGS. 3A and 3B  may be similarly adapted to perform the decryption operations of  FIG. 5B . 
         [0054]    The choice of the operation from which the reciprocal path starts in each round for the fault detection (ShiftRows in  FIG. 5A  or InvSubBytes in  FIG. 5B ) may affect the critical paths when adapting circuits  20 ′ and  22 ′. In some situations, the critical paths could be affected such that the circuitry does not provide results in time between two rounds. The exemplary choice of  FIGS. 5A and 5B  and the corresponding circuit adaptation of  FIG. 6  respect the critical paths. 
         [0055]    Other configurations are possible that respect the critical paths, bearing in mind that the operations ShiftRows and InvShiftRows introduce no latency (they are performed by fixed wire routing). 
         [0056]    The keys used by the AddRoundKey operations are changed using a cipher key expansion at each round of the cipher. The key expansion may also be subject to faults. 
         [0057]      FIG. 7  is a block diagram of an embodiment of fault detection hardware for the AES key expansion process. Conventionally a round key schedule is produced in N+1 expansion rounds of a cipher key CKEY. The keys in the schedule are then used sequentially in the N+1 rounds of the cipher. Each expansion round is recursive and may take place on the fly before the corresponding round of the cipher, or the key schedule may be produced integrally before the cipher rounds. Since the expansion rounds are recursive, a fault in one key produces faults in all the following keys, i.e. a fault in the last key may reflect a fault in the last key itself, or a fault in any of the other keys. 
         [0058]    In order to detect faults in the key generation process, in a preliminary phase, the cipher key CKEY is subjected to a series of recursive expansions  72  to produce a last key KN after N rounds, also called reverse key. This key includes the last round key. The reverse key KN is stored in a register  70  and is subjected to a series of recursive inverse expansions  74 . The inverse expansions normally produce the original key CKEY. This original key is compared at  76  to the key produced by the inverse expansions. If the keys don&#39;t match, the comparator  76  signals a fault. 
         [0059]    To detect eventual corruptions during actual cipher operations, the round keys Ki are expanded in  72 ′ on the fly, as they are needed in the cipher rounds. The key available after the last round, i.e. the reverse key is compared at  78  to the corresponding key KN stored in the register  70 . If the keys don&#39;t match, the comparator  78  signals a fault. 
         [0060]    In a decryption process, the operations may be similar. In  FIG. 7 , the expansions would be exchanged with the inverse expansions, and the cipher key CKEY would be exchanged with the reverse key KN.