TWI418197B - Encryption protection method - Google Patents

Description

Encryption protection method

The present invention relates to a protected cryptographic hardware engine that is protected from locked cryptanalysis attacks during operations, and is particularly useful in protecting encrypted algorithms by using masking methods (error or pseudo-operations) (S-box The input value of the operation (on the key side) so that it is not attacked by the side channel in any given round.

These problems are discussed in U.S. Patent Application Publication No. 2004/0139340 to Johnson et al., which incorporates the use of a pseudo-code to hide the real code, so that the encryption algorithm is safe and prevents, for example, statistics and data. The so-called "white box attack" of flow analysis. Johnson et al. provide an alternative solution that includes a wide distribution of information conversions, combinations, or losses, as well as generating more functions and transformations to change the processing activity visible to the attacker. These solutions are applied to the illustrated implementation for securing a smart card that uses the DES algorithm or its variations.

In US Patent Application Publication No. 2003/0044003 to Chari et al., a method and system for performing a look-up table against side channel attacks is disclosed. This system and method uses a table mask operation where the items in this mask table are completely independent of the items in the original table. This table mask operation is implemented by one or both of the following: (1) table decomposition operation for large tables or tables with large exponential sizes; or (2) table integration operations, integrating several tables into one table .

In US Patent Application Publication No. 2003/0093684 to Kaiserwerth et al., the potential weakness of encryption algorithms, particularly for power analysis attacks, is discussed. In its context, it suggests that the small key size (effectively 56 bits) of this single DES is no longer considered safe for preventing key exhaustive attacks, but needs to progress to, for example, three variants of DES (using at least two And preferably three independent keys are executed three times as: encryption-decryption-encryption. Furthermore, the S-box in this DES is potentially vulnerable to the analysis of the difference between the S-box input and output, so that 48 key bits can be obtained from 56 key bits. Kaiserwerth et al. disclose several measures to defeat this type of attack, including the use of mask operations and Hamming neutral bit strings.

In U.S. Patent No. 6,278,783 to Kocher et al., an improved DES implementation is disclosed in which the S-box table is blinded and randomly transformed on a regular basis, and both the key and the message block are obscured. The value of the transformable two parts associated with the original value is generated by a mutually exclusive or (XOR) operation by bit.

Typically, such side channel attacks involve externally monitoring the power consumption or electromagnetic emissions of the cryptographic hardware during execution of the target encryption algorithm, and attempting to correlate the time profile of the monitored feature with the target algorithm operator. Get information about the key that can be used. For example, one such attack can directly target the execution side of the S-box's input side algorithm, where the data and the secondary key are XORed in a given round. One way to protect this cryptographic algorithm to prevent side channel attacks is to use a random mask or masking method that performs various pseudo or sham operations together with the real operation. However, the problem with such a random masking method is that it does not control the entropy injected in the increased pseudo-operation execution, so that statistical techniques can still be used to expose the computation.

The present invention relates to a decisive masking method for an encryption algorithm that is easily targeted as a target attack, which is particularly applicable but not limited to such encryption algorithms, which use an alternative (S-box) operation or a data and round key. Logically combined, for example, the bit will be XORed on the input side of the encrypted S-box. The decisive masking method of the present invention controls the entropy injected when performing a set of pseudo or pseudo operations to achieve a much greater protection against real operations than purely random masking or masking techniques.

The method generally begins with the construction of a mask table in advance, which includes: corresponding to one of the real keys and a plurality of guard columns, which are established to mask at least some of the keys in the various combinations. When the columns from this table are logically combined with a given key, this method obtains a set of keys, of which only one is true and all others are false keys. (For example, in the case of a bitwise combination of XOR operations, this column corresponding to the real key is a mask that includes all 0 bits, and this guard column is at least a mask with some bits of 1.) This cryptographic algorithm is executed multiple times on the message block in random order using these real and false keys to produce the corresponding real and false round secondary keys. The result obtained by applying the real key to the encryption operation is stored in the memory, and the result obtained by the pseudo key is stored in the dummy memory location. After the encryption has been performed for each of these keys, the real result can be accessed by this memory.

Alternatively, in such encryption rounds, such columns of the mask table can be logically combined with the secondary keys to obtain a real secondary key for each of the rounds, and a set of false secondary keys. Then, according to this plus code round, these secondary keys are applied to process the message block, and only the real result is transmitted to the next round.

For such encryption algorithms that use S-box operations, these number of n bits will enter the input side of this S-box (which is typically executed as a lookup table). There are therefore 2 ⁿ possible input values for this S-box. In a specific example of the invention, a mask table comprising 2 ⁿ masks is constructed. One of these masks contains all 0s (corresponding to the real operation), and all other masks contain some bits of 1 (corresponding to false operations). These masks are XOR by bit, which is used to generate a set of keys (a real key and other false keys) with (a) a key to thereby generate a corresponding real and false secondary key; or (b) Each round of key produces a set of secondary keys for each of these rounds (again, one for the actual secondary key for this round, and the rest for the false secondary key for this round). In these encryption rounds, each of these secondary keys is then logically combined with the data in the n-bytes to enter the S-box. The pseudo-masks in this table can be specifically chosen such that the combined byte entered into the S-box will have all 2 ⁿ possible input values, thus completely removing the entropy seen by this attacker. Therefore, it cannot be determined externally: this is used in the real round key in this S-box operation.

This deterministic masking according to the invention can be applied as a "whole" masking method or an "internal" masking method. The basic idea is to apply the columns of this mask to the key or round key to get the real and false keys or secondary keys. In this overall masking method, masks of such columns with masked tables are applied to all encryption keys except the rounds performed by this encryption algorithm. This allows the execution of the existing hardware or software of this encryption algorithm itself without any internal corrections. This integral mask produces a real encryption key and a set of fake encryption keys. These encryption keys are then continuously applied in random order to the message blocks in the multiple loops of the encryption algorithm. Therefore, the implementation of this overall masking method can handle the loop of 64 operations of the encryption method. In this loop, the table can be randomly accessed to randomly retrieve the unused index i to obtain the mask "i" from the mask table. This produces a masked key in XOR operation by bit in the encryption key having the first order mask "i". This mask key can then be processed by the message block in this encryption algorithm, which can include the secondary key by which the mask key is generated by this mask. If the index i is IndexMaskZero, then the masked key is the real key, and the result of applying the encrypted algorithm loop to the message block is a real result, which is then stored in the memory. If this index i is different from IndexMaskZero, then the masked key is a fake key and this false result will be stored in the pseudo position in the memory. Once all loops have been executed, this real result can be accessed from this memory.

An alternative is the "internal" masking method. This technique modifies the interior of this encryption algorithm and applies the mask inside to these round secondary keys. In each of these encrypted rounds, all masks in this masked table are continuously applied to this round of secondary keys in a random order to obtain the rounds for this round to the real round and various false secondary keys. Use these masked secondary keys to handle multiple loops in one round of this encryption algorithm. In particular, the execution of this internal masking method can process the loop of 64 operations for each encryption round, with an exponent i randomly selected from the index values that have not been used in this round to obtain the mask from the mask table. Cover "i" and apply it to this round of secondary keys. After this loop is used to mask the loop, if the index is IndexMaskZero and corresponds to the real secondary key, the correct result of this round is stored in the memory. If this index is different from IndexMaskZero, it means that the loop of this round has been processed with this false key, and this incorrect result is stored in the pseudo position of this memory. This correct result will be used in the next round, and this false result will be overwritten.

The decision masking method of the present invention can be applied to various cryptographic algorithms executed in a hardware cryptographic engine susceptible to side channel attacks, and in particular any symmetry region using key scheduling with key mixing and S-box operations. Block encryption. For illustrative purposes, the following description will refer to the "Data Encryption Algorithm", which was originally published on January 15, 1977 by the Federal Information Processing Standards (FIPS) publication 46-3, by the US National Bureau of Standards. (now the National Institute of Standards and Technology) at the heart of the Data Encryption Standard (DES), which was redefined on October 25, 1999 (now withdrawn) and is widely used in several variants. . Most notably, one variant known as three DES (3DES) is also known as the Three Data Encryption Algorithm (TDEA), which involves applying this data encryption algorithm three times in succession with a separate key, as As described in NIST Special Publication 800-67 (May 2004). A more computationally replaceable variant is DES-X, which uses a technique known as key whitening, by XORing this extra 64-bit key material before and after the core DES round to add keys Effective size (ie, DES-X _{K , K 1 , K 2} (M) = DES _K (K1 ⊕ M) ⊕ K2). These and other DES variants are methods that reduce the weakness of DES for exhaustive key searches due to their small effective key size. There are other variants that modify the S-box table, key schedule, or other core functions to better resist linear cryptanalysis, or to resist other potential weaknesses that are not specifically designed for this DES. DES and its variants are commonly used as encryption engines in smart cards, which are particularly vulnerable to side channel attacks because of their ease of access. The decision masking method of the present invention substantially reduces this weakness in smart cards and other cryptographic hardware.

This DES operates on the 64-bit message block with 16 equal rounds between the first and last permutations of these blocks. Set these modes of operation to apply DES to messages that are longer than a single block. This DES uses a 64-bit key (KEY), of which 8 bits are dedicated to parity, so the effective key length is 56 bits. A key scheduling function KS uses this KEY to generate 16 secondary keys K1 to K16, and a secondary key is used for each round. These secondary keys are generated for decryption and are applied in reverse order. The complete definition of this key schedule KS involves: one of the PC-1 and PC-2 alternatives (typically implemented as a table), and one of the selected key bits of the two 28-bit blocks. Yuan rotation, as explained in FIPS Publication 46-3. However, the final effect of such operations is that each of the secondary keys K1 through K16 can be considered a separate function of KEY and represented as a list to set a particular permutation selection for the 48 bits obtained by the KEY. Each of these 56 KEY bits is used in a different one of about 14 of the 16 secondary keys. As an example, the secondary key K1 defined by the DES key scheduling function KS is:

These numbers represent the bits selected by the KEY and the secondary key, and are organized into 8 groups of 6 bits each.

The 16 DES rounds have a Feistel structure in which a 64-bit message block is divided into two ("left" and "right") half blocks, and is designed in a continuous round (for rounds i = 1 to 16). , L _i = R _{i - 1} and R _i = L _{i - 1} ⊕ f (R _{i - 1} , K _i )) are alternately processed. This decryption is designed to be similar. As can be seen in Figure 1, this cryptographic function f(R, K) for DES rounds involves the following combinations: (1) Extension function E, which uses a 32-bit half-block R _{i - 1} And generating a 48-bit output; (2) a key-mixing function, which is an XOR operation by bit, and this 48-bit extended output is used for the 48-bit secondary key K _i used for this round. (3) Non-linear alternative conversion, using this 48-bit key mixed output, split it into 8 6-bit pieces, and apply these pieces as input to individually address the 8 selection tables Or S-boxes S ₁ through S ₈ to obtain a set of 8 4-bit outputs; and (4) permutation function P to reconfigure the 32 output bits from the S-boxes.

Each DES S-box S ₁ through S ₈ is a function that associates a 6-bit input with a 4-bit output, as illustrated in FIPS Publication 46-3. These 6-bit groups enter each S-box and one of the 64 4-bit items is selected. The method of the present invention ensures that all 64 possibilities from each S-box are accessed. To achieve this, construct a mask table containing 64 masks. The masks in this table can be octet wide, with 48 bits used for mask operations, and the remaining 16 bits (eg, two bits from each tuple) can be: ( a) 8 parity bits (or other error checking bits), which can be calculated by applying the parity rule of the DES key, and (b) extra bits that can be randomly selected, or by using 48 The same mechanism is derived from the same location, but is used in addition to these S-boxes in one or more other rounds. This 48 bits used in the mask form a set of 8 6-bit values ranging from 0 to 63. In this group of each of these eight 6- bit value corresponds to one of eight different S- boxes S ₁ to S ₈ of. (Please note: in order to hide the identity of this real mask for false masks, and also to hide the false values used, these masking bits that form these 8 values do not need to be continuous or In the ascending order, for example, one of these key schedules can be used, for example for a round, to obtain this value from each mask. Thus, bits 10, 51, 34, 60, 49 can be used. , and 17, to obtain S ₁ corresponding to the case of such S- mask value.)

The following is the simplest mask table, and rows S1 through S8 show the decimal equivalents assigned to the 6-bit values for each mask S-box:

Therefore, the columns of this table here contain 8 equal values. However, if any of the possible values from 0 to 63 occur once and only once in any given row (corresponding to a particular S-box), then other mask tables can be constructed. The values in each row can be in a random order. Typically, one of these masks, for example, mask [0] contains all zero values and is designated as a "real" mask.

During the encryption operation using this overall masking method, all masks from the reconstructed mask table are applied to all encryption keys before starting this uncorrected encryption algorithm. As a whole of this encryption algorithm, different mask keys can be used for each loop of the entire encryption, so it can be looped multiple times. One of these mask keys is a real key that produces a real round key as part of this encryption algorithm, while all other mask keys are false keys that produce false secondary keys and obtain false results. Assigning these zero values to a single mask allows for real results when using a mask.

During the encryption operation using this internal mask method, all masks from the pre-constructed mask table are applied to all S-box inputs in each round. A display described embodiment, during this first round this encryption mask 64 represents one example the mask "15", applied to the first tank S- S ₁ in FIG. This illustrates the corrections made internally to this encryption algorithm when the internal mask is executed. This applies the mask to other S-boxes S ₂ to S ₈ as similarly as in other mask applications, and also in subsequent rounds. In each turn using the internal mask, this process loops 64 times to apply all masks, including real masks, to the secondary key and data. This mask can be applied in any order, such as a random order, which can be different for each round, assuming that each mask is only used once in any round, and that this real mask is known to the encryption engine. That is, random access to the mask table can be used. The identity of the real mask can be stored in the scratchpad and compared to an index as the process passes through the set of mask loops. The actual result output by the eight S-boxes is held in the scratchpad or memory until all 64 masks have been applied, and then the actual result is passed to the next step of the encryption algorithm. . This DES permutation function P can be implemented in conjunction with this storage of the actual results from the S-box output. If desired, the error results can also be left in the dummy memory location and can be replaced, but not transmitted to the next round of the encryption.

The inputs to the eight S-boxes include: (1) the extended data block DATA obtained by the DES extension function E; (2) the DES key for the specific round, here the secondary key K1; and (3) ) The specific mask that is used, here is the mask "15". Typically for DES, this bit from the expanded data block DATA is continuously allocated to 8 S-boxes, with bits 1-6 for S ₁ and bits 7-12 for S ₂ Wait. Such a secondary key K1 for the bit assigned to continuously equally S- box 8, and to the K1 bits 1-6 to S _1, K1 bits 7-12 for the S ₂ and the like. The difference is: remember that the key K1 itself, like these other secondary keys for the subsequent round, is selected and reconfigured by the bits from the master key KEY. These are from the specific bits of the mask "15" and are also selected and ordered as with other masks in this table to capture the values applied to each S-box, as already explained above. Therefore, for the first S-box S ₁ , the 10th, 51st, 34th, 60th, 49th, and 17th bits can be extracted from the mask "15" to obtain the value, and the mask "15" S _{1 is} used for S ₁ . This value is described here as 101010 (or decimal 42).

Each of these bytes (mask, secondary key, data) is combined with the others by XOR operation using a bitwise element. This XOR operation is denoted by ⊕ in FIG. The mask shown here is first applied to the key, and then the resulting masked key is applied to this material. However, since this bitwise element can conform to the commutative and associative rules in XOR operations, it can be applied to these three groups (masks, secondary keys, and data) in virtually any order, and still The same S-box input can be obtained. Indeed, it is beneficial to change the order in which this applies to different S-boxes, masks, and rounds so that such operations are more ambiguous to any external observer.

As explained above, the masking process of the present invention can be applied to encryption other than DES and its variants. For example, Rijndael, which is adopted as the Advanced Encryption Standard (AES) and in the NIST FIPS Publication 197, uses an S-box with 8-bit input and output. A mask table with 256 (= 2 ⁸ ) different masks can be constructed and applied as part of the encrypted AddRoundKey() conversion. Many other encryption algorithms use S-boxes or similar surrogate tables and provide key mixing operations on the input side of such S-boxes. This decisive mask, as explained here for DES, can be applied to such encryption.

Referring to Figure 3, an exemplary hardware for performing the integral mask of the present invention can be seen therein. The memory 31 is a storage for reading/writing data, and the material includes a masked key. A random number generator 32 produces a random number used by other units, including a random index i for accessing the columns of the mask table. It can use any suitable generator known in the art. A mask table generating unit 33 generates an item of the mask table and writes it in the memory 31. This arithmetic sequencer 34 issues instructions to other units and orders their actions. During each loop of the DES algorithm, a key mask unit 36 reads the ("real") encryption key from the memory 31 to mask it from an item stored in the memory 31 mask table. And writing the masked key into the memory 31. The DES calculation unit 37 reads from the memory 31: the masked key and the input material (this general content or encrypted content message block), using the masked key to perform a DES encryption algorithm, which includes The key is masked to generate any secondary keys, and the result is written back to the memory 31 as output data. The location of the memory used to store this result will depend on whether the masked key is a real key or a fake key.

Referring to Figure 4, an exemplary hardware for performing the internal mask of the present invention can be seen therein. As with the implementation of the overall mask hardware, the internal mask execution also includes a memory 41, a random number generator 42, and a mask table generating unit 43, all of these basic functions and hardware in the overall mask. The corresponding units 31-33 are the same. The arithmetic sequencer 44 also issues instructions to other units and orders their actions, but this internal mask sequence is different from the overall mask sequence. The execution of the hardware further includes: a DES initial calculation unit 45; a round secondary key mask unit 46; a DES round calculation unit 47; and a DES final calculation unit 48. This DES initial calculation unit 45 performs a pre-DES round calculation. In particular, it reads the input data from memory 41 (to process general content or encrypted content message blocks), and performs the initial processing steps of DES (including key whitening or similar changes from DES-X) before the first round, And writing the result of this step back to the memory 41. In addition, the unit 45 reads the real encryption key from the memory 41, generates a set of round secondary keys according to the defined DES key generation routine, and stores the round secondary keys back into the memory 41. . Alternatively, the generation of such secondary keys may be performed by the DES round calculation unit 47 on a "one round - one round" basis. In either of the above two cases, the secondary key can be masked by the secondary secondary key mask unit 46, which reads the corresponding secondary key from the memory 41, and in each loop of the round, An item from the mask table of the memory 41 masks it and writes the masked secondary key into the memory 41. The DES round calculation unit 47 reads from the memory 41: the masked secondary key for the given loop of the DES round, and the input data for the round, performs the round calculation and writes the result back to the memory 41. This is used to store the memory location of the loop result for this round, depending on whether the masked secondary key is the real secondary key or false secondary key for the round. Each DES round circuit is repeated multiple times until all the masks of the secondary key have been used. This information comes from applying this real secondary key to the data entered by the memory 41 in the next round. The DES final calculation unit 48 reads the result of this last round from the memory 41, performs the DES round calculation, and writes the result (this fully processed message block) back to the memory 41.

The processing units shown in these examples, with the exception of mask units 36 and 46, are conventional elements known for performing DES or other encryption algorithms. The memories 31 and 41 have locations that can be assigned items for storing the mask table; store the real and false keys and secondary keys; and store real and false data processing results. These masking units 36 and 46 use this masking table item to perform a bitwise XOR, or other logical combination, or arithmetic operation on the key or round secondary key to produce a real and false key or secondary key.

Variations to the above illustrative examples can be readily constructed and are suitable for use with different cryptographic applications. For example, with a suitable fast processor and careful designation of such real and false addresses for the rounded data results, then the overall and internal masking methods according to the present invention can be derived from the overall technology. Used in combination with a false key, these keys are used as encryption keys, and internal masks are applied to the corresponding round key set.

31. . . Memory

32. . . Random generator

33. . . Mask table generation unit

34. . . Operational sequencer

36. . . Key mask unit

37. . . DES calculation unit

41. . . Memory

42. . . Random generator

43. . . Mask table generation unit

44. . . Operational sequencer

45. . . DES initial calculation unit

46. . . Round secondary key mask unit

47. . . DES round calculation unit

48. . . DES final calculation unit

1 is a schematic block diagram illustrating a DES encryption function according to a conventional DES standard; FIG. 2 is a schematic block diagram illustrating a DES encryption function modified according to a specific example of the present invention; and FIGS. 3 and 4 are exemplified A hardware schematic block diagram of an encryption engine for implementing the various integral and internal masks of the method in accordance with the present invention.

Claims (9)

An encryption protection method includes: constructing a mask table having a plurality of masks, including a real mask and a plurality of false masks, which can be effectively applied to any secondary keys of any round Masking at least some of the bits of the secondary key; applying all masks of the mask to one key and one data block during each round of encryption as part of a key mixing operation for the round In order to mask the key mixing operation, when the real mask is applied to the secondary key and the data block, the same result as applying the secondary key to the data block in the key mixing operation can be obtained, and when When all of the plurality of masks are applied in the key mixing operation, each possible combination of the S-box input values for the encryption can be obtained; applying the masked key mixing result to an input of the substitution table Or the encrypted S-box; and the result of using the real mask of this application, continue the next step of this encryption until all rounds are completed. The encryption protection method of claim 1, wherein the mask, the secondary key, and the data block are divided into a plurality of n-bit blocks in any encryption round, and each is assigned to a specific one. S-box input, the mask table contains 2 ⁿ masks, and each of these 2 ⁿ possible n-bit values occurs once and only once in the respective allocation blocks for the masks . The encryption protection method of claim 2, wherein the n-bit value assigned to the specific S-box input is determined by the predetermined selection and order of the pixels of the mask. Given a mask capture. The encryption protection method of claim 2, wherein the separately allocated mask block, secondary key, and data block form an S-box input in any encryption round, and the encrypted S-box The table is different. The encryption protection method of claim 1, wherein the mask table is applied to the secondary key and the data block as part of the key mixing operation, which involves an XOR operation by bit, The real mask includes a set of zero values. The encryption protection method of claim 1, wherein each mask in the mask table is accessed and applied once and only once in a random order in the key mixing operation, the real mask system. This encryption can be recognized. The cryptographic protection method of claim 1, wherein the encryption is a DES variant using a core algorithm as described in the DES standard already specified. The cryptographic protection method of claim 1, wherein each of the dummy masks has a set of identical non-zero values that are different from values in all other masks. The cryptographic protection method of claim 1, wherein each of the pseudo masks has a different non-zero value in the group.