Abstract:
A method of improving the operation of a processor executing a cryptographic process, by automatically detecting faults during both encryption and decryption operations by the cryptographic process, comprises segmenting the data to be encrypted and encrypting the data segments using a complex non-linear algorithm that can lead to faults; computing an output parity bit from a selected step of the algorithm for a selected data segment, based on the input value of that segment; comparing the actual output parity bit of the selected segment with the computed output parity bit for that segment; and determining whether a fault exists, based on whether the actual output parity bit matches the computed output parity bit for the selected segment.

Description:
FIELD OF THE INVENTION 
       [0001]    The present disclosure relates to fault detection in encryption systems. 
       BRIEF SUMMARY 
       [0002]    In accordance with one embodiment, a method is provided for improving the operation of a processor executing a cryptographic process by automatically detecting faults during both encryption and decryption operations by the cryptographic process. The method comprises segmenting the data to be encrypted and encrypting the data segments using a complex non-linear algorithm that can lead to faults; computing an output parity bit from a selected step of the algorithm for a selected data segment, based on the input value of that segment; comparing the actual output parity bit of the selected segment with the computed output parity bit for that segment; and determining whether a fault exists, based on whether the actual output parity bit matches the computed output parity bit for the selected segment. The data segments may be encrypted and decrypted, and the computing, comparing and determining operations are executed during both encrypting and decrypting. The data is preferably encrypted and decrypted using the Advanced Encryption Standard specification. 
         [0003]    In one implementation, the method comprises computing an input parity bit for the selected data segment input to the selected step of the algorithm, based on the output value of that segment from the selected step of the algorithm; comparing the actual input parity bit of the selected segment input to the selected step of the algorithm, with the computed input parity bit for that data segment, and determining whether a fault exists, based on whether the actual input parity bit matches the computed input parity bit for the selected segment. 
         [0004]    In a preferred implementation, the method computes an output parity bit from multiple steps of the algorithm; compares the actual output parity bit of each of the multiple steps with the computed output parity bit for that step; and determines whether a fault exists, based on whether the actual output parity bit matches the computed output parity bit for each of the multiple steps. 
         [0005]    In another implementation, the method comprises segmenting the data to be encrypted and encrypting the data segments using a complex non-linear algorithm that can lead to faults; computing an output parity bit from a data segment processed by the algorithm, based on the input value of that segment before being processed by the algorithm; comparing the actual output parity bit of the data segment with the computed output parity bit for that segment, and determining whether a fault exists, based on whether the actual output parity bit matches the computed output parity bit for the selected segment. In one implementation, the data segments are encrypted and decrypted, and the computing, comparing and determining operations are executed for each data segment that is encrypted or decrypted. 
         [0006]    The foregoing and additional aspects and embodiments of the present disclosure will be apparent to those of ordinary skill in the art in view of the detailed description of various embodiments and/or aspects, which is made with reference to the drawings, a brief description of which is provided next. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0007]    The foregoing and other advantages of the disclosure will become apparent upon reading the following detailed description and upon reference to the drawings. 
           [0008]      FIG. 1  is a diagram of an embodiment of an encryption engine using two-way parity fault detection. 
           [0009]      FIG. 2  is a diagram of an embodiment of the key expansion engine using two-way parity fault detection. 
       
    
    
       [0010]    While the present disclosure is susceptible to various modifications and alternative forms, specific embodiments or implementations have been shown by way of example in the drawings and will be described in detail herein. It should be understood, however, that the disclosure is not intended to be limited to the particular forms disclosed. Rather, the disclosure is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of an invention as defined by the appended claims. 
       REFERENCES 
       [0011]    [1] Federal Information Processing Standards (FIPS).  Advanced Encryption Standard  ( AES ). Publication 197. November 2001. 
       DETAILED DESCRIPTION 
       [0012]    The Advanced Encryption Standard (AES) [1] executes a complex non-linear algorithm which can lead to faults. In order to detect faults, the whole AES engine can be duplicated and executed twice in parallel. Results from both are compared to detect faults. However, this approach leads to more than 100% overhead, which for high-throughput engines is a large price to pay. 
         [0013]    Using single parity to detect faults in AES engines can be considered as a solution to reduce the cost. In this case, the parity of the fault-free output is computed based on the input data and is compared with the parity generated from the output data. Only uneven bit errors can be detected. However, given the fact that errors in an AES engine spread quickly throughout the data and the control blocks, they are generally not detectable by single parity fault detection leading to unacceptable fault coverage. 
         [0014]    There is a need for a low cost fault detection method with reliable fault coverage. 
         [0015]    In this embodiment, checkpoints are incorporated throughout the data blocks to verify the parity and prevent the errors from spreading. 
         [0016]    A two-way parity fault detector is applied to the AES datapath (in both encryption and decryption paths), while the control logic (e.g., finite state machine, multiplexors and registers) are optionally covered via duplication. 
         [0017]    Referring to  FIG. 1 , the round cipher module is protected using several fault detection steps. The S-box and inv S-box process  101  and the MixColumns and Inv MixColumns process  122  are each covered by a two-way parity fault detection with 1 parity bit per 8 bits. The output parity bit (1 parity bit per 8-bits of data) is computed based on the input value and compared with the actual output parity bit. 
         [0018]    Data  100  of size 128-bits or 256-bits is segmented into 8-bit segments in step  102 . Prior to performing the S-box/inv S-box process  101 , a 1-bit parity of the fault-free output on w2 is computed based on the input w1 on the segments in step  106 . This computed parity is compared with the actual parity of the output of the S-box/inv S-box process  101 , and if the actual parity does not match the computed parity, a fault is detected at step  108 . At the same time, based on the segment output from the segment S-box/inv S-box process  101 , a 1-bit parity of the fault-free input packet is computed based on w2 at step  110  and compared with the input segment parity to detect a fault at step  112 . 
         [0019]    The ShiftRows/inv ShiftRows process  114  is performed if no faults are detected, then the key  116  is segmented  117  and combined to perform the encrypt/decrypt process  118 . 
         [0020]    Optionally, for higher fault coverage, parity for the encrypted/decrypted segments from the encrypt/decrypt process is computed at step  120  prior to input into the MixColumn/invMixColumn process  122 . Prior to performing the MixColumn/invMixColumn process  122 , a 1-bit parity of the fault-free output on w4 is computed based on the input w3 on the segments in step  120 . This computed parity is compared with the actual parity of the output of the MixColumn/invMixColumn process  122 , and if the actual parity does not match the computed parity, a fault is detected at step  124 . At the same time, based on the segment output from the MixColumn/invMixColumn process  122 , a 1-bit parity of the fault-free input packet is computed based on w4 at step  130  and compared with the input segment parity to detect a fault at step  132 . 
         [0021]    Furthermore, based on the encrypted/decrypted segments from the encrypt/decrypt process, parity on the expected input segment can be computed at step  126  and compared with the original input segment for fault detection at step  128 . 
         [0022]    Parity of the initial segment is compared with the output segments after the last round  134  for fault detection at step  136  prior to output of the data  150 . 
         [0023]    An example of a protected key expansion module is shown in  FIG. 2 . A 128-bit key is stored in registers  203 . The key is XORed at step  201 , and 4 segments of 32-bits  200   a  . . .  200   d  are re-circulated to the registers  203  for the next round. The round number  221  is input to the round constant process (RCON)  220 . Parity on the output of the RCON process based on the expected round number is compared to the parity of the RCON output for fault detection at step  224 . 
         [0024]    A control function  205  selects either the first 32-bit segment of the new round key or the previous round key depending upon whether it is performing decryption or encryption. The bits of the selected segment are shifted by 8 to the left. Prior to performing the S_box process  210 , a 1-bit parity of the fault-free output on w7 is computed based on the input w6 on the segments in step  208 . This computed parity is compared with the actual parity of the output of S_box process  210 , and if the actual parity does not match the computed parity, a fault is detected at step  216 . At the same time, based on the segment output from the S_box process  210 , a 1-bit parity of the fault-free input packet is computed based on w7 at step  212  and compared with the input segment parity to detect a fault at step  214 . 
         [0025]    A 1-bit parity check  222  can be optionally added to the RCON function  220  to detect faults in RCON block  224 . 
         [0026]    The control logic and multiplexors can be optionally protected using duplication. 
         [0027]    When a fault is detected  108 ,  112 ,  124 ,  128 ,  132 ,  136  the process can be halted and the most recent encryption/decryption round restarted from the beginning to avoid wasting further cycles on ciphering segments with errors. Statistics on the frequency of detected faults and the step involved in the fault can be optionally gathered and used to manage the processor. 
         [0028]    Conventional duplication method provides 100% fault coverage with greater than 100% area overhead. The two-way parity fault detection embodiment described provides for 99.9% fault detection coverage with 41% area overhead. 
         [0029]    Although the algorithms described above including those with reference to the foregoing flow charts have been described separately, it should be understood that any two or more of the algorithms disclosed herein can be combined in any combination. Any of the methods, algorithms, implementations, or procedures described herein can include machine-readable instructions for execution by: (a) a processor, (b) a controller, and/or (c) any other suitable processing device. Any algorithm, software, or method disclosed herein can be embodied in software stored on a non-transitory tangible medium such as, for example, a flash memory, a CD-ROM, a floppy disk, a hard drive, a digital versatile disk (DVD), or other memory devices, but persons of ordinary skill in the art will readily appreciate that the entire algorithm and/or parts thereof could alternatively be executed by a device other than a controller and/or embodied in firmware or dedicated hardware in a well known manner (e.g., it may be implemented by an application specific integrated circuit (ASIC), a programmable logic device (PLD), a field programmable logic device (FPLD), discrete logic, etc.). Also, some or all of the machine-readable instructions represented in any flowchart depicted herein can be implemented manually as opposed to automatically by a controller, processor, or similar computing device or machine. Further, although specific algorithms are described with reference to flowcharts depicted herein, persons of ordinary skill in the art will readily appreciate that many other methods of implementing the example machine readable instructions may alternatively be used. For example, the order of execution of the blocks may be changed, and/or some of the blocks described may be changed, eliminated, or combined. 
         [0030]    It should be noted that the algorithms illustrated and discussed herein as having various modules which perform particular functions and interact with one another. It should be understood that these modules are merely segregated based on their function for the sake of description and represent computer hardware and/or executable software code which is stored on a computer-readable medium for execution on appropriate computing hardware. The various functions of the different modules and units can be combined or segregated as hardware and/or software stored on a non-transitory computer-readable medium as above as modules in any manner, and can be used separately or in combination. 
         [0031]    While particular implementations and applications of the present disclosure have been illustrated and described, it is to be understood that the present disclosure is not limited to the precise construction and compositions disclosed herein and that various modifications, changes, and variations can be apparent from the foregoing descriptions without departing from the spirit and scope of an invention as defined in the appended claims.