Abstract:
An encryption method and apparatus for implementing an overlapping operation, a variable clock operation, and a combination of the two operations. In the encryption method based on an overlapping operation technique, first, first through N-th fault sources effect first through N-th rounds of a first hardware engine to output a first cipher text. Thereafter, the second through (N+1)th fault sources effect first through N-th rounds of a second hardware engine, respectively, to output a second cipher text. The first and second cipher texts are compared to each other, and if the first and second cipher texts are identical, the first or second cipher text is output. The first and second hardware engines operate according to a data encryption standard (DES) algorithm. As described above, if the first and second cipher texts are identical, the first or second cipher text is output. Thus, a highly stable encryption algorithm is provided.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     Embodiments of the present invention relate to an encryption method implemented by overlapping or using a variable clock. This application claims the priority of Korean Patent Application No. 2003-55031, filed on Aug. 8, 2003, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference.  
         [0003]     2. Description of the Related Art  
         [0004]     The Data Encryption Standard (DES) algorithm is used as an encryption method and is important in communication networking. For example, the DES algorithm is used in security Internet applications, remote access servers, cable modems, and satellite modems. The DES algorithm inputs a 64-bit block and outputs a 64-bit block. 56 bits among the 64 bits are used for encryption and decryption. The remaining 8 bits are used for parity checking. A DES system is an encryption apparatus which receives a 64-bit plain text block and a 56-bit key and outputs a 64-bit cipher text.  
         [0005]     Examples of techniques implementing the DES algorithm include permutation (e.g. P-Box), substitution (e.g. S-Box), and key scheduling for generating subkeys. During data encryption, 16 rounds of repetitive operations are performed. An input portion performs initial permutation (IP) and an output portion performs inverse IP.  
         [0006]      FIG. 1  is a block diagram of an encryption apparatus, which implements a DES algorithm. First, the initial permutation (IP) portion  110  permutates a 64-bit plain text block. Next, the transformation portion  120  divides the 64-bit plain text block into two 32-bit blocks. One of the 32-bit blocks is stored in the left variable (L 0 ) register, while the other 32-bit block is stored in the right variable (R 0 ) register. 16 rounds of a product transformation using a cipher functions (f) and  16  rounds of a block transformation are then performed. The block transformation is executed by crossing left and right variables L i  and R i  (where i is an integer ranging from 1 to 16) with each other. The inverse initial permutation (IP−1) portion  130  encrypts the result of the above transformations using inverse initial permutation and outputs the cipher text.  
         [0007]     Product transformations are achieved by the cipher function (f)  121  and the exclusive OR (XOR) portion  122 . The cipher function (f)  121  receives the 32-bit block data of the right variable R i  from an R i  register together with the subkey K i  and performs an encryption algorithm. The subkey K i  is produced by a key scheduler. The XOR portion  122  performs an XOR operation on the result of the cipher function (f)  121  and the output of an L i  register. The XOR outputs the result of the XOR operation to the right variable register, next to the R i  register. Specifically, the 32-bit block data obtained by the XOR portion  122  is transferred to and stored in a right variable (R i+1 ) register. The 32-bit data stored in the Ri register is transferred to and stored in a left variable (L 1+1 ) register. This algorithm corresponds to one round and 16 rounds are performed in the DES algorithm.  
         [0008]     When a 64-bit plain text block is processed by the IP portion  110 , it is divided into two blocks. These two blocks are stored in the L 0  and R 0  registers, each of the 16 rounds are expressed in Equations 1 and 2: 
 
 L=R   i−1 , i=1, 2, . . . , 16  (1) 
 
 R   i   =L   i−1   ⊕f ( R   i−1   ,Ki ), i=1, 2, . . . 16  (2) 
 
         [0009]      FIG. 2  illustrates a key scheduler that generates a subkey K i  (where i is an integer ranging from 1 to 16). The key scheduler includes the first permutation choice (PC) portion  200 , the basic operation portion  210 , and the second PC portions  220 . The first PC portion  200  receives and permutates a 56-bit key. The basic operation portion  210  divides a 56-bit key block, permutated by the first PC  200  into two 28-bit blocks. The basic operation portion store the first 28-bit block in a variable (C 0 ) register and stores the second 28-bit block in a variable (D 0 ) register. The basic operation portion  210  produces 48-bit subkeys that are required by a cipher function operation during the 16 rounds of the product transformation. To achieve this subkey production, left shifters  213  and  214  of the basic operation portion  210  left-shift a left variable (C i ) of a C i  register  211  and a right variable (D i ) of a D 1  register  212 , respectively, by one or two places. The left shifters  213  and  214  store the left-shifted left and right variables C i  and D i  in a left variable (C i +1) register and a right variable (D i +1) register, respectively. The second PC portions  220  receive 28-bit blocks of the left and right variables C i  and D i , left-shifted in each round. The second PC portions  220  outputs 48-bit subkeys K i . During 16 rounds, the left and right variables C i  and D i  are shifted by 28 places. Accordingly, the left variable C 16  is the same as the left variable C 0  and the right variable D 16  is the same as the right variable D 0 .  
         [0010]      FIG. 3  is a block diagram of a general DES core architecture. Referring to  FIG. 3 , the cipher function (f) includes the expansion permutation portion  300 , the XOR portion  310 , the S-Box permutation portion  320 , and the P-Box permutation portion  330 . The expansion permutation portion  300  copies some of the 32 bits of the right variable R i−1  received from an R i−1  register to permutate the 32-bit right variable R i−1  to provide a 48-bit right variable. The XOR portion  310  performs an XOR operation on the result of the permutation by the expansion permutation portion  300  and a 48-bit subkey produced during each round by a key scheduler. The S-Box permutation portion  320  substitutes a 32-bit block for a 48-bit block obtained by the XOR portion  310 . The P-Box permutation portion  330  permutates the 32-bit block obtained by the S-Box permutation portion  320  and provides a permutated 32-bit block. The 32-bit block output from the P-Box permutation portion  330  is XOR-operated with a 32-bit left variable L i−1 , stored in an L i−1  register. The result of the XOR operation is stored as a right variable R i  in an R i  register. A 32-bit right variable R i−1  stored in the R i−1  register is transferred to and stored in an L i  register.  
         [0011]     A differential cryptanalysis and a linear cryptanalysis are widely used as algorithms for attacking the DES encryption algorithm. Because these encryption attack algorithms are based on the vulnerableness of the DES algorithm, they are not suitable for actual attacks on encryption. Fault attacks have recently emerged as effective methods of attacking a public key encryption algorithm, such as, an RSA encryption algorithm. Eli Biham, who has devised the differential cryptanalysis, has proposed a differential fault attack (DFA) in which the fault attack is applied to a block encryption technique, such as the DES algorithm. The fault attack enables a key to be detected using several hundreds of pairs of a plain text, which is much less than that in related art attack methods. Hence, the fault attack is more powerful than other theoretical attack methods. Thus, an encryption apparatus and method resistible against the DFA is required.  
       SUMMARY OF THE INVENTION  
       [0012]     Aspects of embodiments of the present invention provide an encryption method for implementing an overlapping operation, in order to prevent a key value from leaking due to artificial and natural faults. Aspects of embodiments of the present invention provide an encryption method for implementing variable clock operation. Aspects of embodiments of the present invention provide an encryption method for implementing both an overlapping operation and/or a variable clock operation.  
         [0013]     According to embodiments of the present invention, an encryption method implementing an overlapping operation is utilized. This encryption method may includes the following. Sequentially providing first through N-th fault sources to first through N-th rounds of a first hardware engine, respectively, to output a first cipher text. Sequentially providing the second through (N+1)th fault sources to first through N-th rounds of a second hardware engine, respectively, to output a second cipher text. Comparing the first and second cipher texts and outputting the first (or second) cipher text if the first and second cipher texts are identical.  
         [0014]     In embodiments, each of the N rounds of each of the first and second hardware engines may include the following. Dividing a plain text block into two sub-blocks and storing one sub-block in a left register and the other in a right register. Executing an encryption operation by performing a cipher function with respect to data stored in the right register and a subkey. Performing an exclusive OR operation on the result of the cipher function and the output of the left register. Storing the result of the exclusive OR operation in a right register in the next round. Transferring data stored in the right register to a left register in the next round. This round repeats N times. Accordingly, each of the first and second hardware engines performs first through N-th rounds of an encryption operation.  
         [0015]     According to embodiments of the invention, the first and second hardware engines operate according to a block encryption algorithm that can distinguish rounds (e.g. a data encryption standard (DES) algorithm). The first through (N+1)th fault sources may be environmental changes (e.g. temperature shock, barometric shock, radio frequency (RF) energy, heavy ion bombardment, ultraviolet, and laser energy). Such environmental changes attack the first and second hardware engines so that different faults are generated in their corresponding operation rounds. Accordingly, the first and second hardware engines obtain different operation results to prevent the use of a faulty cipher text. According to embodiments of the invention, the encryption method for implementing an overlapping operation further include preventing output of cipher texts if the first and second cipher texts are different. The plain text is composed of 64 bits and the 64-bit plain text is divided into two 32-bit sub-blocks.  
         [0016]     According to embodiments of the invention, there is provided an encryption method for implementing a variable clock operation. The method may include the following. Sequentially providing first through N-th fault sources to first through N-th rounds of a first hardware engine, respectively, in response to a first clock signal to output a first cipher text. Sequentially providing the first through N-th fault sources to first through N-th rounds of a second hardware engine, respectively, in response to a second clock signal to output a second cipher text. Comparing the first and second cipher texts and outputting the first (or second) cipher text if the first and second cipher texts are identical.  
         [0017]     Each of the N rounds of each of the first and second hardware engines may include the following. Dividing a plain text block into two sub-blocks and storing one sub-block in a left register and the other in a right register. Executing an encryption operation by performing a cipher function with respect to data stored in the right register and a subkey. Performing an exclusive OR operation on the result of the cipher function and the output of the left register, storing the result of the exclusive OR operation in a right register in the next round, and transferring data stored in the right register to a left register in the next round. This round repeats N times. Accordingly, each of the first and second hardware engines performs first through N-th rounds of an encryption operation.  
         [0018]     According to embodiments of the invention, in an encryption method implementing a variable clock operation, the encryption operations of the first and second hardware engines may be set to start at different points of time, similar to the encryption method implementing overlapping operations. When implementing a variable clock operation, the operating clocks speeds of the first and second hardware engines are different. Accordingly, when an attacker applies a fault source to the first and second hardware engines, a corresponding fault is generated at different operation points of time of the first and second hardware engines, so that they obtain different operation results. Implementing a variable clock operation may include preventing output of cipher texts if the first and second cipher texts do not match. The plain text may be composed of 64 bits and the 64-bit plain text may be divided into two 32-bit sub-blocks.  
         [0019]     According to embodiments of the invention, an encryption method implements both an overlapping operation and a variable clock operation. This method may include the following. Sequentially providing first through N-th fault sources to first through N-th rounds of a first hardware engine, respectively, in response to a first clock signal to output a first cipher text. Sequentially providing the second through (N+1)th fault sources to first through N-th rounds of a second hardware engine, respectively, in response to a second clock signal to output a second cipher text. Comparing the first and second cipher texts and outputting the first (or second) cipher text if the first and second cipher texts are identical.  
         [0020]     Each of the N rounds of each of the first and second hardware engines may include the following. Dividing a plain text block into two sub-blocks and storing one sub-block in a left register and the other in a right register. Executing an encryption operation by performing a cipher function with respect to data stored in the right register and a subkey. Performing an exclusive OR operation on the result of the cipher function and the output of the left register. Storing the result of the exclusive OR operation in a right register in the next round. Transferring data stored in the right register to a left register in the next round. This round repeats N times and each of the first and second hardware engines may perform first through N-th rounds of encryption operations.  
         [0021]     In an encryption method according to embodiments of the present invention, different fault sources are provided to corresponding rounds of operations of first and second hardware engines and they operate with different clock frequency. Consequently, first and second cipher texts are likely to be different. In spite of this circumstance, if the first and second cipher texts are identical, the first or second cipher text is output, thus providing a highly stable encryption algorithm. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0022]      FIG. 1  is a block diagram of an encryption apparatus implementing a DES algorithm.  
         [0023]      FIG. 2  is a block diagram of a key scheduler that generates the subkey K i  of  FIG. 1 .  
         [0024]      FIG. 3  is a block diagram of DES core architecture.  
         [0025]      FIG. 4  illustrates an exemplary cryptographic engine implementing an overlapping operation.  
         [0026]      FIG. 5  illustrates an exemplary cryptographic engine implementing a variable clock operation. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0027]     The present invention is described with reference to the accompanying drawings, in which embodiments of the invention are illustrated. Embodiments of the present invention are provided in order to more completely explain the present invention to one skilled in the art.  
         [0028]      FIG. 4  is an exemplary illustration of a cryptographic engine implementing an overlapping operation, according to embodiments of the present invention. The cryptographic engine  400  may include the first hardware engine  430  and the second hardware engine  440 , which use N overlapping operation modes. In the first hardware engine  430 , fault sources F 1 , F 2 , F 3 , . . . , Fn−1, and Fn are provided to respective rounds. In the second hardware engine  440 , fault sources F 2 , F 3 , . . . , Fn, and Fn+1 are provided to respective rounds. The fault sources F 1 , F 2 , F 3 , . . . , Fn−1, Fn, and Fn+1 can be environmental changes (e.g. temperature shock, barometric shock, radio frequency (RF) energy, heavy ion bombardment, ultraviolet, laser energy) which individually attack the rounds to generate faults in the rounds.  
         [0029]     The 64-bit plain text block  410  is input to each of the first and second hardware engines  430  and  440 . Each of the first and second hardware engines  430  and  440  has a similar structure to the transformation portion  120  of  FIG. 1 . Each of the first and second hardware engines  430  and  440  divide the 64-bit plain text block  410  into two 32-bit sub-blocks. Each of the first and second hardware engines  430  and  440  transfer one sub-block to the L i  register of  FIG. 1  and the other to the R i  register of  FIG. 1 . Each of the first and second hardware engines  430  and  440  perform encryption on the data stored in the R i  register and a subkey K i  by using a cipher function (f). Each of the first and second hardware engines  430  and  440  perform an XOR operation on the result of the cipher function (f) and the output of the L register in an i-th round. Each of the first and second hardware engines  430  and  440  transfer the result of the XOR operation to an R i+1  register in an (i+1)th round and the data stored in the R i  register to an L i+1  register in the (i+1)th round. This operation of one round repeats n times.  
         [0030]     The first fault source F 1  is present during a first round of the first hardware engine  430 . The second through n-th fault sources F 2 , F 3 , . . . , Fn−1, and Fn are present during second through n-th rounds of the first hardware engine  430 , respectively. The second fault source F 2  received by the second round of the first hardware engine  430  is present during a first round of the second hardware engine  440 . The third fault source F 3  received by the third round of the first hardware engine  430  is present during a second round of the second hardware engine  440 . The n-th fault source Fn received by the n-th round of the first hardware engine  430  is present during a (n−1)th round of the second hardware engine  440 . The (n+1)th fault source is present during an n-th round of the second hardware engine  440 . The 64-bit plain text block  410  is encrypted by the first hardware engine  430  and output as a first cipher text. The 64-bit plain text block  410  is also encrypted by the second hardware engine  440  and output as a second cipher text.  
         [0031]     In the first round, the first hardware engine  430  receives the 64-bit plain text block  410  and outputs an operation effected by a first round fault generated due to the first fault source F 1 . In the second round, the first hardware engine  430  receives the operation result effected by the first round fault generated in the first round. The second round outputs an operation result based on the output of the first round and effected by a second round fault generated into the second fault source F 2 . Finally, in the n-th round, the first hardware engine  430  receives an operation result that is effected by an (n−1)th round fault generated in the (n−1)th round. In the n-th round, the first hardware engine  430  outputs the first cipher text effected by an n-th round fault generated due to the n-th fault source Fn, as shown in step  435 .  
         [0032]     In the first round, the second hardware engine  440  receives the 64-bit plain text block  410  and outputs an operation result effected by the second round fault generated due to the second fault source F 2 . In the second round, the second hardware engine  440  receives the operation result that is effected by the second round fault generated in the first round, and outputs an operation result that is effected by a third round fault generated due to the third fault source F 3 . In the (n−1)th round, the second hardware engine  440  receives an operation result that is effected by an (n−2)th round fault generated in the (n−2)th round, and outputs an operation result that is effected by the n-th round fault generated due to the n-th fault source Fn. In the n-th round, the second hardware engine  440  receives the operation result effected by the n-th round fault generated in the (n−1)th round, and outputs as the second cipher text an operation result effected by the (n+1)th round fault generated due to the (n+1)th fault source Fn+1, as shown in step  445 .  
         [0033]     In step  450 , the first and second cipher texts are compared with each other. If the first and second cipher texts are identical, the identical cipher text is output, in step  460 . If the first and second cipher texts are different, no cipher texts are output, in step  470 . In the cryptographic engine  400 , the first and second hardware engines  430  and  440  are expected to output first and second cipher texts that are identical, because the algorithms of first and second hardware engines  430  and  440  are the same. However, if corresponding rounds of the first and second hardware engines  430  and  440  are effected by different fault sources among F 1 , F 2 , . . . , F(n−1), Fn, and Fn+1, the output of first and second hardware engines  430  and  440  will be different. Accordingly, corresponding rounds of the first and second hardware engines  430  and  440  include different errors, thus increasing a probability that their operation results are different. Hence, if an encryption device is attacked by fault sources, the first and second cipher texts output by the first and second hardware engines  430  and  440 , respectively, should be different. Likewise, if the first and second cipher texts output by the first and second hardware engines  430  and  440  are identical, this means that the 64-bit plain text block  410  has been successfully encrypted without being effected by the fault sources F 1 , F 2 , . . . , F(n−1), Fn, and Fn+1. In embodiments, different fault sources among F 1 , F 2 , . . . , F(n−1), Fn, and Fn+1 are provided to corresponding rounds of the first and second hardware engines  430  and  440 . To achieve this, the first and second hardware engines  430  and  440  are offset in time by at least one round.  
         [0034]      FIG. 5  illustrates an exemplary cryptographic engine  500  according to embodiments of the present invention utilizing a variable clock operation. The cryptographic engine  500  is different from the cryptographic engine  400  of  FIG. 4  in that rounds of first and second hardware engines  530  and  540  are not offset in time. However, the frequency of a first clock signal CLK 1  for first hardware engine  530  is set differently from that of a second clock signal CLK 2  for second hardware engine  540 .  
         [0035]     As an example, a 64-bit plain text block  510  is input to each of the first and second hardware engines  530  and  540 . Each of the first and second hardware engines  530  and  540  divides the 64-bit plain text block  510  into two 32-bit sub-blocks. Each of the two 32-bit sub-blocks undergoes one round of the operation of  FIG. 3 . This round repeats n times. The first fault source F 1  is provided to a first round of the first hardware engine  530 . The second through n-th fault sources F 2 , F 3 , . . . , Fn−1, and Fn are provided to second through n-th rounds of the first hardware engine  530 , respectively. The first fault source F 1  provided to the first round of the first hardware engine  530  is also provided to a first round of the second hardware engine  540 . The second fault source F 2  provided to the second round of the first hardware engine  530  is also provided to a second round of the second hardware engine  540 . The n-th fault source Fn provided to the n-th round of the first hardware engine  530  is also provided to an n-th round of the second hardware engine  540 .  
         [0036]     In the first round, the first hardware engine  530  receives the 64-bit plain text block  510  in response to the first clock signal CLK 1  and outputs an operation result effected by a first round fault due to the first fault source F 1 . In the second round, the first hardware engine  530  receives the operation result effected by the first round fault in the first round and outputs an operation result effected by a second round fault due to the second fault source F 2 . In the n-th round, the first hardware engine  530  receives an operation result effected by an (n−1)th round fault generated in the (n−1)th round. The n-th round outputs first cipher text as an operation result effected by an n-th round fault generated due to the n-th fault source Fn, as shown in step  535 .  
         [0037]     In the first round, the second hardware engine  540  receives the 64-bit plain text block  510  in response to the second clock signal CLK 2  and outputs an operation result effected by the first round fault due to the first fault source F 1 . In the second round, the second hardware engine  540  receives the operation result effected by the first round fault in the first round and outputs an operation result effected by a second round fault due to the second fault source F 2 . In the n-th round, the second hardware engine  540  receives the operation result effected by the (n−1)th round fault generated in the (n−1)th round and outputs as a second cipher text that is an operation result effected by an n-th round fault due to the n-th fault source Fn, as shown in step  545 .  
         [0038]     In step  550 , the first and second cipher texts are compared with each other. If the first and second cipher texts are identical, the identical cipher text is output, in step  560 . If the first and second cipher texts are different, no cipher texts are output, in step  570 . In the cryptographic engine  500 , the first and second hardware engines  530  and  540  are expected to output first and second cipher texts that are identical, because the algorithms of first and second hardware engines  530  and  540  are the same. However, the first and second hardware engines  530  and  540  start their operations at different points in time, because the first and second clock signals CLK 1  and CLK 2  have different clock frequencies. Accordingly, the first and second hardware engines  530  and  540  execute different rounds in the same time zone, and although an identical fault is provided at the same time, it effects different operation stages of the first and second hardware engines  530  and  540 . Hence, the first and second hardware engines  530  and  540  output different operation results.  
         [0039]     Nevertheless, if the first and second cipher texts output by the first and second hardware engines  530  and  540  are identical, this indicates that the 64-bit plain text block  510  has been stably encrypted with immunity against the fault sources F 1 , F 2 , . . . , F(n−1), Fn, and Fn+1. Thus, if the first and second cipher texts are identical, the cryptographic engine  500  outputs the first (or second) cipher text and finishes encryption.  
         [0040]     While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present invention as defined by the following claims.