CN118233115A - Improved comprehensive protection method based on threshold technology - Google Patents

Abstract

The present invention discloses an improved comprehensive protection method based on threshold technology, and the steps include: 1) to resist d-order side channel attack, construct a d-order threshold implementation scheme for the protected cryptographic algorithm, which is called the original threshold implementation; 2) construct a d-order threshold implementation that is completely the same as that in step 1) for the protected cryptographic algorithm, which is called the redundant threshold implementation; 3) using the same plaintext as encryption input, synchronously executing the original threshold implementation and the redundant threshold implementation; after each nonlinear operation, exchanging partial shares of the original threshold implementation and the redundant threshold implementation; 4) using a compensation function to exchange partial shares of the final output of the original threshold implementation and the final output result of the redundant threshold implementation, as the ciphertext output of the original threshold implementation and the ciphertext output result of the redundant threshold implementation; 5) after step 4) is completed, selecting the output ciphertext of the original threshold implementation or the redundant threshold implementation as the output ciphertext of the comprehensive protection.

Description

An improved comprehensive protection method based on threshold technology

Technical Field

The present invention relates to the field of block cipher algorithm protection, and in particular to a comprehensive protection method against side channel attacks and fault attacks based on threshold implementation technology.

Background technique

In the traditional black-box attack model, the attacker mainly analyzes the security of the cryptographic algorithm through the input and output information of the cryptographic algorithm. The security of the existing block cipher algorithm under the black-box model has been fully theoretically demonstrated. However, under the gray-box model, the security of the block cipher algorithm faces huge challenges. Under the gray-box model, the adversary's attack capability is enhanced. In addition to the input and output of the cryptographic algorithm, the adversary can also use the physical information leaked during the execution of the cryptographic algorithm or interfere with the execution of the cryptographic algorithm to attack. Among them, the attack using the physical information leaked during the execution of the cryptographic algorithm is called a side channel attack. According to the different physical information used, it can be divided into energy side channel attack, electromagnetic side channel attack, optical side channel attack and sound side channel attack. Side channel attacks pose a huge threat to the security of the implementation of cryptographic algorithms due to their simplicity of implementation and higher attack efficiency than black-box attacks. Attacks that interfere with the execution of cryptographic algorithms are called fault attacks. Fault attacks require more stringent attack conditions than side channel attacks, but the attack efficiency is relatively higher, which is also a huge threat to the security of cryptographic algorithms.

In response to the threat of side channel attacks, corresponding protection strategies have been proposed. The essence of side channel attacks is to use the correlation between side channel information and the intermediate values of cryptographic operations to attack, so the protection strategy achieves protection by destroying this correlation. According to different specific protection ideas, side channel protection can be divided into hiding technology and masking technology. Hiding technology mainly destroys the correlation between side channel information and intermediate states by changing the original distribution of side channel information. Specifically, it can be achieved by reducing the signal-to-noise ratio and balancing the side channel information of a single clock. Studies have shown that protection schemes designed based on hiding technology can increase the difficulty of attackers to a certain extent, but they can be broken by increasing the number of collected side channel curves, signal preprocessing, etc., so they cannot provide theoretically complete security. Masking technology is a side channel protection idea based on secret sharing. It destroys the correlation between intermediate values and side channel information by randomly splitting the original intermediate values. Since masking technology has a more complete theoretical support, it has received extensive research and attention since it was proposed. In early mask protection schemes, it was assumed that the operation was strictly performed in a predetermined order, ignoring the impact of burrs in CMOS circuits on the security of protection schemes. Subsequent studies have shown that protection schemes designed by ignoring the impact of burrs are mostly unsafe.

In order to deal with the impact of burr phenomenon on the security of mask protection, the threshold implementation protection idea is proposed. In order to deal with the threat of d-order side channel attack, it is necessary to implement d-order threshold implementation. A d-order threshold implementation includes two parts: input variable splitting and operation splitting. Taking y=f(x) as an example, in the input variable splitting stage, S _x -1 random numbers are used Split the input variable x into /> Satisfaction/> Where S _x is the number of shares of the input variable split, and the d-order threshold implementation needs to satisfy S _x ≥ d+1. In the operation splitting stage, the split input variable is brought into the original operation, and we can get/> Then split the above operation into output components/> Where _Sy represents the number of shares of the function decomposition. The above division needs to satisfy three major properties: (1) correctness, /> (2) Incompleteness: any combination of d output components is independent of at least one component of the input variable, ensuring d-order side channel security in a glitch environment; (3) Output uniformity: each possible output partition has an equal probability of appearing, meeting the security requirements of the next stage during the iterative operation of the cryptographic algorithm.

The protection strategies against fault attacks can be roughly divided into two categories: "check-block" and fault randomization. In the "check-block" type of fault protection, the fault injection is first detected by means of time redundancy, space redundancy, etc. When the fault injection is detected, the output of the fault ciphertext will be blocked, thereby achieving protection against fault attacks that rely on the fault ciphertext. This type of protection strategy requires a judgment statement to determine whether the fault is injected or not. This judgment statement is often a vulnerable point for fault attacks. When the judgment statement is skipped by the fault attack, the protection strategy will fail. Different from the "check-block" type of fault protection, the fault randomization protection strategy allows the output of the ciphertext during fault injection without the need for a judgment statement, so it does not have the security defects of the "check-block" type of fault protection. Infection protection is a mainstream protection scheme in fault randomization. Joye et al. proposed an infection protection scheme based on the exchange mechanism in 2007. In this scheme, by exchanging some bytes of the intermediate state, the ciphertext finally output during fault injection cannot be used by the adversary. However, in this protection scheme, the swap operation is a deterministic step without any increase in randomness. When the implementation scheme is known, the adversary can implement the attack through logical deduction. This scheme only increases the difficulty of fault attacks to a certain extent and cannot achieve the theoretical fault attack security.

At present, the research on protection against side channel attacks and fault attacks is often carried out independently. The protection scheme for one type of attack is often unable to resist the other type of attack, and vice versa. The current comprehensive protection scheme is often a simple superposition of two protection strategies, which has brought a large increase in resource consumption. In response to this situation, Feng Jingyi et al. proposed a low-cost comprehensive protection method (patent number: ZL201911359164.2) by combining the threshold realization idea and the exchange mechanism. In this comprehensive scheme, first, in order to resist the d-order side channel attack, a d-order original threshold realization is implemented for the cryptographic algorithm to be protected; secondly, a completely identical redundant threshold realization is implemented for the cryptographic algorithm to be protected; thirdly, the propagation of faults is realized by exchanging some components of the intermediate operation of the original threshold realization and the redundant threshold realization, and the randomness of the components in the threshold realization scheme is used to achieve the uniform randomness of the final output ciphertext. However, in the above scheme, its exchange operation is a probabilistic event for the propagation of faults. For block cipher algorithms, their operations often include multiple rounds of iterative operations. When faults are injected in the first few rounds of cryptographic operations, the injected faults can be diffused to the two-way operations with a probability close to 1 after multiple rounds of exchanges, and the final output presents uniform randomness, thereby achieving protection against fault attacks. However, when faults are injected in the later rounds of the cryptographic algorithm, especially in the last round, the number of exchanges is small, and the injected faults may not be diffused to the two-way operations, so that one operation retains all the information of the injected fault, and finally causes the leakage of the faulty ciphertext.

Summary of the invention

In view of the above situation, the present invention considers adding a compensation function after the execution of the cryptographic algorithm and before the ciphertext output, thereby increasing the probability of fault diffusion by increasing the number of exchanges, thereby constructing a more secure comprehensive protection scheme.

The present invention is an improved comprehensive protection method based on threshold technology, which comprises the following steps:

1) To resist d-order side channel attacks, a d-order threshold implementation scheme is constructed for the protected cryptographic algorithm, which is called the original threshold implementation;

2) Treating the d-order threshold implementation whose protection cryptographic algorithm construction is exactly the same as that in step 1) as redundant threshold implementation;

3) Using the same plaintext as encryption input, synchronously execute the algorithm flow of step 1) and step 2), and exchange the partial shares of the original threshold realization and the redundant threshold realization after each nonlinear operation;

4) To increase the probability of fault diffusion, a compensation function is added to both the original threshold implementation and the redundant threshold implementation, and the same exchange operation as step 3) is performed during the execution of the compensation function;

5) After step 4) is completed, the output ciphertext of the original threshold implementation or the redundant threshold implementation is selected as the output ciphertext of the comprehensive protection.

Preferably, the d-order thresholds described in step 1) and step 2) divide the encrypted input, the encrypted intermediate value and the encrypted result into at least s shares, s≥d+1.

Preferably, the number of exchange shares described in step 3) is (0, d] ∪ (0, s-d], and the exchanged shares are in the same position in the original threshold implementation and the redundant threshold implementation. That is, 1 to d shares can be exchanged, or other shares after removing d shares can be exchanged.

Preferably, the compensation function described in step 4) includes two design methods: one based on an inversion structure and the other based on a Feistel structure.

In block cipher algorithms, a mainstream method for constructing S-boxes is to use inversion operations on finite fields. For example, the S-boxes of AES and SM4 algorithms can be regarded as constructed by inversion operations on finite fields. In the threshold implementation of such algorithms, it is necessary to convert the S-box into an inversion operation on a finite field and then construct a protection scheme. Therefore, the compensation function can be constructed by connecting an even number of inversion operations in series. Its basic unit structure is shown in Figure 1, where x ^-1 is the inversion operation after adding a threshold implementation in the S-box. After two inversion operations, the operation restores the original value, and the additional nonlinear operation increases the probability of fault diffusion to two-way operations. Moreover, since the inversion operation can reuse the inversion operation of the S-box, it does not increase the additional implementation cost. The compensation function can contain multiple basic unit structures. The increase in the number will increase the probability of fault diffusion and improve security, but it will also increase the calculation delay of the algorithm. It should be selected according to the actual situation.

When the S-box of the block cipher algorithm is not constructed by the inversion operation, the compensation function based on the inversion structure is no longer applicable. Considering the compensation function based on the Feistel structure, the S-box of the block cipher algorithm is used as the nonlinear component of the compensation function. Its basic unit structure is shown in Figure 2. Its inputs _L0 and _R0 are the data of the mask input bit width of two adjacent S-boxes for the cryptographic operation, specifically 2sL, where L represents the input bit width of the S-box, s represents the number of threshold realization shares, and the S-box multiplexing block cipher algorithm threshold realization protected S-box operation. The basic unit structure consists of the first exchange iterative operation, the second non-exchange iterative operation, the third exchange iterative operation and the fourth non-exchange iterative operation. After 4 rounds of iterative operations, the intermediate value of the left-path operation changes to _L1 = _R0 , After 4 iterations, the intermediate value of the right-hand operation changes to

R ₄ =R ₃ =R ₀ ,/> S stands for XOR. As described in the above formula, after four iterations, both the left and right paths are restored to their original values. The additional nonlinear operation increases the probability of fault diffusion to the two-way operation. The S-box of the basic unit construction multiplexing block cipher algorithm is a nonlinear component, so it does not increase the additional implementation cost. The compensation function can contain multiple basic unit constructions. The increase in the number will increase the probability of fault diffusion, but it will also increase the calculation delay of the algorithm. It should be selected according to the actual situation.

Compared with the prior art, the present invention has the following advantages:

1. The present invention effectively solves the problem of uneven diffusion of fault injection in the last round, and improves the fault protection security of the comprehensive protection scheme;

2. The compensation function of the present invention is constructed by reusing the original components in the cryptographic algorithm, so the added implementation cost can be ignored, maintaining the low-cost advantage of the comprehensive protection solution.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a schematic diagram of an inverse compensation function;

Fig. 2 is a schematic diagram of the Feistel structure compensation function;

Figure 3 is a schematic diagram of the AES algorithm comprehensive protection S-box;

FIG. 4 is a flow chart of the present invention.

Detailed ways

The specific implementation techniques of the present invention are described below by way of examples, but are not intended to limit the scope of the present invention in any way.

This example uses the AES algorithm as the block cipher algorithm to be protected, and designs a comprehensive protection scheme that can resist fault attacks and first-order side channel attacks.

The block length of the AES block cipher algorithm can support 128 bits, 192 bits and 256 bits. The present invention takes the 128-bit AES algorithm encryption operation as an example to illustrate. The AES round iteration operation consists of S-box, row shift, column confusion and key XOR operation. The S-box is the only nonlinear operation, and the exchange operation of the comprehensive protection scheme is only performed in the S-box part. The specific implementation of the AES comprehensive protection scheme includes the following steps:

1) To resist the first-order side channel attack, the original threshold implementation splits the plaintext input and the key input into three parts. The key to the threshold implementation of the AES algorithm lies in the nonlinear component, namely the S-box. To achieve the threshold implementation of the S-box, the S-box is first regarded as a combination of the inversion operation and the affine operation on the GF(2 ⁸ ) finite field, and then further performs composite field decomposition to transform the inversion operation on GF(2 ⁸ ) into operations on GF(2 ⁴ ) and GF(2 ² ). The specific structure of the S-box of the original threshold implementation part is shown in the upper half of Figure 3, which includes 6 stages. Stage 1 is the affine operation M ₁ ; Stage 2 includes multiplication operations on GF(2 ⁴ ) and linear operations L ₁ ; Stage 3 includes multiplication operations on GF(2 ² ) and linear operations L ₂ ; Stage 4 includes inversion operations L ₃ and multiplication operations on GF(2 ² ); Stage 5 includes 2 multiplication operations on GF(2 ⁴ ); Stage 6 is the affine operation M ₂ . Based on the above decomposition, three shares of threshold protection are performed on the operations of different stages of the S-box.

2) Implement a redundant threshold implementation for the AES algorithm that is exactly the same as the original threshold implementation.

3) The exchange operation occurs after the nonlinear operation, that is, the S-box part, as shown in Figure 3, where the multiplication operation is the only nonlinear operation. There are a total of 4 stages with multiplication operations, so 4 exchange operations are performed, and one of the 3 shares is exchanged during the exchange process.

4) After the encryption operation is completed and before the ciphertext is output, a compensation function is added to increase the number of exchange operations in the last round of fault injection and increase the probability of fault diffusion. For the AES algorithm, its S-box is constructed by inversion operation, so it can be constructed based on the inversion compensation function, with the second cascade of inversion operation on GF(2 ⁸ ) as the compensation function. When the S-box is not constructed by inversion operation, the compensation function based on Feistel structure can be considered.

5) After step 4), without loss of generality, the encryption result achieved by the original threshold is used as the ciphertext output of the comprehensive protection scheme.

In terms of side channel protection security. In the structure of comprehensive protection, both the original encryption and redundant encryption are designed for side channel protection using the threshold protection principle. According to the side channel security properties of the threshold implementation technology, the two circuits protected by the first-order threshold implementation can resist the first-order side channel attack. In addition, the exchange function is performed on the basis of the threshold implementation, and it is a linear operation that does not involve interactive operations between different shares, so it does not destroy the incompleteness of the threshold implementation. One intermediate mask component always maintains an independent relationship with the original intermediate value, which can resist the first-order side channel attack, so it can meet the side channel security. In summary, the comprehensive protection scheme can resist the first-order side channel attack as a whole.

In terms of fault protection security. The injected fault will undergo an exchange operation after nonlinear operation. If the fault injection component is diffused to the original threshold implementation and the redundant threshold implementation respectively, the final output ciphertext will be random due to the randomness of the threshold implementation share, thereby making the fault attack that relies on the faulty ciphertext invalid. When the fault is injected into the last round of the AES algorithm, after only one round of nonlinear operation, the exchange operation may not be able to diffuse the fault to the two-way operation; the addition of the compensation function further increases the number of exchange operations, increasing the protection capability against fault attacks; and because the compensation function is constructed by reusing the inverse operation of the S-box, it will not increase the additional implementation cost too much.

Although the specific embodiments of the present invention are disclosed for the purpose of illustration, the purpose is to help understand the content of the present invention and implement it accordingly, those skilled in the art will understand that various substitutions, changes and modifications are possible without departing from the spirit and scope of the present invention and the appended claims. Therefore, the present invention should not be limited to the content disclosed in the best embodiment, and the scope of the present invention is subject to the scope defined in the claims.

Claims (7)

1. An improved comprehensive protection method based on a threshold technology comprises the following steps:

1) Constructing a d-order threshold implementation scheme, called original threshold implementation, for the cryptographic algorithm to be protected in order to resist d-order side channel attack;

2) Constructing the d-order threshold implementation which is completely the same as that in the step 1) to the password algorithm to be protected, and calling the d-order threshold implementation as a redundant threshold implementation;

3) Taking the same plaintext as encryption input, and synchronously executing the original threshold implementation and the redundant threshold implementation; after the nonlinear operation of the same stage of the original threshold implementation and the redundant threshold implementation, exchanging part of shares of the original threshold implementation and the redundant threshold implementation;

4) The final output realized by the original threshold and the final output result realized by the redundancy threshold are subjected to partial share exchange by using a compensation function, and are used as ciphertext output realized by the original threshold and ciphertext output result realized by the redundancy threshold;

5) After the step 4) is completed, selecting the output ciphertext realized by the original threshold or the redundant threshold as the output ciphertext of the comprehensive protection.

2. The method of claim 1, wherein the original threshold implementation and the redundant threshold implementation divide each of the encrypted input, the encrypted intermediate value, and the encrypted result into at least s shares, s being greater than or equal to d+1.

3. The method of claim 2, wherein the partial share of the exchange of step 3) is (0, d ]. U.s-d ], and the shares being exchanged are in the same position in the original threshold implementation and the redundant threshold implementation.

4. A method according to claim 1 or 2 or 3, characterized in that the compensation function is an inverse structure based compensation function or a Feistel structure based compensation function.

5. The method according to claim 4, wherein the compensation function is based on an inversion structure, i.e. the compensation function is constructed by series connection of even-number inversion operations.

6. The method according to claim 4, wherein the compensation function is a Feistel structure-based compensation function comprising at least one base unit; the left input of the basic unit is recorded as L ₀, the right input is recorded as R ₀,L₀、R₀, two adjacent S box mask input bit-width data are subjected to password operation, the data size of L ₀ and R ₀ is 2sL, L represents the input bit-width of the S box, and S represents the threshold realization share; the basic unit is composed of iteration operation of the 1 st exchange, iteration operation of the 2 nd non-exchange, iteration operation of the 3 rd exchange and iteration operation of the 4 th non-exchange; after 4 iterative operations, the intermediate value of left-way operation is changed to L ₁＝R₀, Through 4 iterative operations, the intermediate value change of the right-way operation is/> R ₄＝R₃＝R₀, wherein/>S is an exclusive OR operation.

7. The method of claim 6, wherein the compensation function is a series arrangement of a plurality of the base units.