Patent Publication Number: US-2004047468-A1

Title: Method and system for the encryption of data

Description:
BACKGROUND  
       [0001] The invention relates to a method for the encryption of a datastream, comprising the steps:  
       [0002] the datastream is logically combined with a secret key or data derived therefrom;  
       [0003] the resulting datastream is processed in an S-box in which the offered datastream is converted in a manner that cannot be predicted outside the system.  
       [0004] The invention also relates to a system for the encryption of the datastream, comprising a combination device in which the datastream is logically combined with a secret key or data derived therefrom and an S-box in which the datastream processed by the combination device is converted in an unpredictable manner.  
       [0005] An S-Box (in full: substitution box) can comprise a table in which, starting from the input values, output values are looked up and outputted with the aid of indexes. S-Boxes create an unpredictable relationship between the input and output of an encryption module.  
       [0006] The drawback of the known method and the known system is that the secret key can be discovered with the aid of an attack that is known as “Differential Power Analysis”, see e.g. reference  1 : “DES and differential power analysis; the Duplication method”. Naturally, the cryptographic key must remain secret, since its possession could enable, for example if the encryption process was performed in a GSM chipcard, telephone calls to be made via the GSM network at another person&#39;s expense.  
       [0007] An earlier patent application, WO200060807 (reference  2 ), discloses a method and means to make attacks far more difficult by keeping the operative part of the S-Box secret from potential attackers. A variant of the attack is however still possible and will be further described under “Implementation”.  
       THE INVENTION  
       [0008] The invention proposes an improved method for the encryption of a datastream wherein the steps in which the datastream is combined with a secret key and the resulting datastream is converted unpredictably in an S-box are preceded by a step in which the datastream is first converted in an extra, “initial S-box” in a manner that is unpredictable for an attacker and only thereafter combined with the secret key.  
       [0009] The encryption system—comprising a combination device in which the datastream is combined with the key, and an S-box in which the datastream is subsequently converted unpredictably—comprises according to the invention an initial S-box in which the datastream fed to the system is converted in an unpredictable manner and subsequently offered to the combination device.  
       [0010] The invention will now be explained with reference to an embodiment, preceded by a more detailed explanation of the attack against which the method and the system according to the invention offer a solution. 
     
    
    
     IMPLEMENTATION  
     [0011] The attack  
     [0012]FIG. 1 shows a “state-or-the-art” system for the encryption of the datastream I, comprising a combination device  1  in which the datastream is combined logically with a secret key K (i.e. modulo  2  addition, represented in the rest of the text by “I+|MOD  2 | K”; represented in the figures by ⊕) and an S-box  2  in which the datastream processed by the combination device  1  is, converted in an unpredictable manner to an output datastream O. The figure shows the (known) system twice. In the first case, the combination device  1  adds a data element I 1  modulo  2  to a key element K 1  and the S-box  2  subsequently converts the result to an output datastream O 1 . (All elements of the datastream are, for example, 1 byte large.) In the second case, the combination device  1  adds a data element I 2  modulo  2  to a key element K 2  and the S-box  2  subsequently converts the result to an output datastream O 2 . 
    
    
     [0013] In the event of an attack, which a system as illustrated in FIG. 1 cannot resist, the attacker keeps manipulating the first datastream input I 1  and the second datastream input I 2  until the first input I 1  combined—in the combination device  1  with the first part of the secret key material K 1  is equal to the second input I 2  combined with the second part of the key material K 2 . From the current consumption of the system during the look-up in the table of the S-box  2 , the attacker can deduce whether he managed to make I 1 +|MOD  2 | K 1  identical to I 2 +|MOD  2 | K 2 , since in this case the same value would be looked up twice in the S-Box; O 1  is equal to O 2 . The same current consumption would then be shown twice. If the method was unsuccessful, the current consumption would show random values. The attacker still does not know the absolute values of K 1  and K 2 , but only their difference, since: I 1 +|MOD  2 | K 1 =I 2 +|MOD  2 | K 2 , so K 1 +|MOD  2 | K 2 =I 1 +|MOD  2 | I 2 . But if the attacker is able, after a number of these attacks, to determine the difference between all n succeeding key bytes K 1  and K 2 , K 2  and K 3 , _ K n−1  and K n , all he needs to do is to “guess” the first byte and the rest follows automatically. This reduces the amount of work dramatically from an average of 2 8+n−1  to an average of 2 7 +(n−1)*2 7  possibilities. So if n is for example equal to 16 (which is a customary value), the attacker only needs to try out 2048 possibilities instead of 1.7*10 38  in order to discover the key.  
     [0014] The Security  
     [0015] The invention solves this security problem by not combining the input I directly with the key material K, but by using the input first as index for an initial S-Box  3 . This eliminates the influence that the attacker can exercise on the input for the EXOR operation in the combination device  1  with the key material K and thus on the input for the S-Box  2 . FIG. 2 shows this schematically. The datastream I is, before being offered to the combination device  1 , first fed to the initial S-box  3 . The output of this S-Box  3  is represented by S 3 [I]. After the EXOR operation (modulo- 2  addition) of S 3 [I] and K, the result is S 3 [I]+|MOD  2 | K. Unpredictable processing in S-box  2  results in an output datastream O=S 2 [S 3 [I]+|MOD  2 | K]. By adding the initial S-box  3  in front of the combination device  1 , the input of the S-Box  2  is screened from attackers and can therefore no longer be manipulated, which prevents attackers from discovering the secret key by varying the input data and simultaneously analysing the current consumption. It is important to keep the contents of S-Box  3  secret from the attacker, otherwise he could still manipulate I such that the above described attack would still be possible. With a secret S-Box, which can be achieved with the aid of the invention described in [2], the values of S[I] are unknown to the attacker, even if the values of I are known.  
     [0016] Another embodiment is shown in FIG. 3. In this figure, O (the output of the second S-Box  2 ) is again the input for a feedback shift register  4 . It is customary to initially load the secret key in this shift register. A is the final result of the encryption system and is, for example, a value by which a party can authenticate itself by means of a “challenge &amp; response” method. I is in this case a data series that is sent by the verifying party as “challenge” to a user who has to authenticate himself. The verifying party subsequently compares the “response” A of the encryption system of the user with the “response” (A′) generated by an identical encryption system at the verifying party. If A and A′ are identical, the user is authenticated.  
     REFERENCES  
     [0017] [1] Goubin L; Patarin J, DES and differential power analysis; the “Duplication” method Cryptographic Hardware and Embedded Systems. First International Workshop, CHES&#39;99. Proceedings (Lecture Notes in Computer Science Volume 1717), pp. 158-172, Published: Berlin, Germany, 1999, 352 pp.  
     [0018] [2] WO-A1-200060807, applicant Koninklijke KPN n.v.