CN114095148B - A white-box password encryption method based on local differential privacy protection - Google Patents

Abstract

The invention discloses a white-box cipher encryption method based on local differential privacy protection, which includes using the personal private key allocated by the system to construct a block cipher. The constructed block cipher has a total of R rounds; for rounds 1 to R-1, random equations and The system of polynomial equations is disrupted; round R performs local differential privacy protection on the inversion result of the output of round R-1; the random equation is discarded, the system of polynomial equations is perturbed to become 0, and the output of round R is obtained; multiple instances are used, Conduct voting and filter the same parts of the final output results to obtain the ciphertext output. The invention can ensure the smooth progress of encryption and decryption algorithms in a white-box attack environment and provide the most perfect protection for confidential information.

Description

A white-box password encryption method based on local differential privacy protection

Technical field

The present invention relates to the field of information security, and in particular to a secure white-box cipher encryption method based on differential privacy protection in an insecure software running environment.

Background technique

With the rapid development of information technology, most software today is in an extremely insecure environment, that is, a white-box attack environment. The so-called white box attack means that the attacker enjoys sufficient privileges and can use advanced technology to locate the cryptographic algorithm and observe the terminal or server containing the cryptographic algorithm. The algorithm is visible and the dynamic execution of the algorithm and its internal state can be observed. , and can modify the intermediate value to obtain the secret key information.

Since the attacker has complete control over the terminal, traditional cryptographic algorithms are extremely vulnerable in this environment and their security is no longer applicable. Therefore, a new cryptographic technology, namely white-box cryptographic technology, emerged as the times require. It provides effective means for the security and confidentiality of cryptographic algorithms running on untrusted terminals. Because white-box cryptography is applied in an extremely exposed environment, its security can effectively resist black-box attacks and gray-box attacks (side-channel attacks) on traditional cryptographic analysis.

The design of white-box cryptographic algorithms generally applies knowledge such as diffusion, algebra, probability, confusion, software protection, information hiding, etc. It can protect the safe execution of cryptographic algorithms and related software in a white-box attack environment. Its application prospects are very broad. It can be applied to the secure distribution of digital content to provide security protection against theft or abuse of digital assets of content creators and providers. It can be applied to secure computing in wireless ad hoc networks, cloud computing, etc., to provide Untrustworthy terminals process confidential information to provide anti-observation, anti-tampering, anti-theft and other services; they can be applied to software protection, destroying the original structure of software design to prevent reverse engineering, etc.

At present, the design ideas of white-box cryptography are generally divided into two categories, namely designing white-box implementation of existing cryptographic algorithms and designing a new white-box cryptographic algorithm. Currently, the common white-box implementations of cryptographic algorithms include three methods: lookup table method, insertion of scrambling items, and multi-variable cipher method. In terms of current white box implementation solutions, the main ones are:

For white-box encryption using lookup tables, chow et al. proposed AES white-box encryption [1] and DES white-box encryption [2] as early as 2002. But both schemes can recover the encryption key within efficient time complexity. Subsequent scholars improved it [3] and studied white-box ciphers based on lookup tables for other block ciphers (such as SM4, SM2, etc.). But they were all broken down one by one.

Another method of designing a white box is the white box implementation based on adding perturbation terms proposed by Bringer et al. in 2006 [4], but it was broken by Mulder in 2010 [5].

In terms of new white-box cryptographic algorithm design, in 2014, Biryukov et al. proposed a white-box cryptographic algorithm based on ASASA structural design [6], which was broken in 2015. In the same year, a white-box cipher scheme called Space-hard cipher was also proposed, but its efficiency was not high.

To sum up, among several white-box cryptography schemes, there is no recognized secure and highly efficient white-box cryptography scheme so far. Therefore, it is necessary to design a safe and effective scheme that can resist white-box attacks. Cryptozoological algorithms are used in digital content distribution systems based on encrypted information broadcasting to improve the security of user private keys in a white-box environment, ensure safe distribution of digital content, and improve system security.

Contents of the invention

The purpose of the present invention is to improve Bringer's white-box implementation in view of the shortcomings of the above-mentioned existing technologies, make up for the shortcomings of this solution, and propose an encryption method for white-box passwords based on localized differential privacy protection, which is used in white-box Attack environments, such as digital content distribution systems based on encrypted information broadcast. Or other systems that require software containing encryption algorithms to resist white-box attacks in actual application environments to ensure the smooth progress of encryption and decryption algorithms and provide the most complete protection for confidential information.

In order to achieve the above objectives, the technical solution adopted by the present invention is: a white-box password encryption method based on local differential privacy protection, which includes the following steps:

Step 1: Use the personal private key assigned by the system to construct a block cipher. The constructed block cipher has R rounds in total;

Step 2: Use random equations and polynomial equations to disrupt rounds 1 to R-1 respectively;

Step 3: Round R performs local differential privacy protection on the inversion result of the output of round R-1;

Step 4: Discard the random equation, the polynomial equation system becomes 0, and obtain the output of the R-th round;

Step 5: Use multiple instances to vote and filter the same parts of the final output results to obtain the correct ciphertext output.

Constructing the block cipher described in step 1 includes; G represents the specific representation method of changing the private key to the public key in a certain round, s and t represent two linear mappings, E _θ represents the monomial function,/> Represents the identification function;

The entire encryption description for user j is:

Represents the implementation of the entire block cipher for user j, from round 1 to round R, /> represents the connection operation, and G _r,j represents the i-th round performed by user j using the personal private key assigned by the system.

Furthermore, the 1~R-1 rounds of disruption described in step 2 include:

Round 1:

Among them, S ₁ is the equation system of the first round of the original password, Represents the output variable of the first round,/> is a constant value system of polynomial equations,/> is the given polynomial, R ₁ (X) is the first round of t ₁ random polynomial equations, M ₁ is a linear bijection, represented by a square matrix of size n+s+t ₁ , /> Represents the system of polynomial equations after the first round of perturbation, /> represents a random equation, Z ₁ represents the output variable of round 1;

Round 2~R-1:

Among them, r=2,...R-1, S _r is the system of equations of the r-th round original password, Ran _r is the new system of polynomial equations of t _i equations, M _r is a linear bijection, with size Square matrix representation of n+s+t _i , Representing the system of equations of the original wheel,/> Represents a system of polynomial equations used for perturbation, /> Represents a new system of equations consisting of t _i random equations, Z _r represents the output of the r-th round, and S _r represents the system of equations of the r-th round of encryption.

Further, the R-th round disrupts

R _R is the system of equations corresponding to the last round of the original password; O _Φ is the system of n polynomial equations, RR is the local differential privacy preserving model, Represents the result of perturbation through the m-RR mechanism after the inversion of the output result of the R-1 round, and the perturbed result is considered as the input of the original system S _R of the R-th round,/> Indicates that the result of the disturbance is considered as a loss of the disturbed system,/> Indicates that the result after the disturbance is considered as the input of the R-th round random system random system R _R , /> Represents the output of the last round of S _R through the original system, /> Represents the output of the last round of O _Φ through the random system.

Specifically, the local differential privacy protection adopts the m-RR model. For N values, each value corresponds to a sensitive value, and there are m sensitive values in total. The model can be specifically described as: (1) Input m sensitive values , (2) Use the m-RR model for local differential privacy protection, (3) Output m perturbed values.

More specifically, the m-RR model is modeled as the transmission process of a multivariate discrete channel, and the input is The output is/> Local differential privacy protection is the conditional probability of mapping x _i to y _j ,

The model is specifically described as:

In the formula, λ represents the introduced parameter, ω _i represents the weight, i represents the sensitive value index value when input, and j represents the sensitive value index value after passing the RR mechanism.

The discrete channel of the m-RR model is symmetric, that is, when i=j, x _i =y _j .

Compared with the existing technology, the beneficial effect of the present invention is that the existing scheme of adding scrambling items to implement white-box ciphers can easily recover the key by the attack proposed by Mulder et al. This scheme makes up for the original scheme against Mulder attacks and other attacks. The vulnerability prevents the white-box attacker from conducting separate attacks on each round, but also ensures that in the last round, the decomposed key part, the scrambled part and the randomness will not be extracted by changing its input and observing changes in the final output result. part value. This encryption scheme will not allow the attacker to restore the entire encryption due to a white-box attack, ensuring the security of encryption algorithms running on untrusted terminals.

This invention adds a perturbation system and a random system to the original system. The introduced perturbation system solves the polynomial isomorphism-based vulnerability of traceable block ciphers proposed by Faugère and Perret. At the same time, the introduced random system increases the complexity of algebraic analysis. This solution The introduced RR mechanism confuses the input of the R-th round, so the input is not changed, and the changes in the final output result are observed to extract the values of the decomposed key part, the scrambled part and the random part, thereby resisting the Mulder attack .

Description of the drawings

Figure 1 is a flow chart of the first round after perturbation of the white-box cipher encryption method based on local differential privacy protection of the present invention;

Figure 2 is a flow chart of the r-th round after perturbation of the white-box cipher encryption method based on local differential privacy protection of the present invention (2≤r≤R-1);

Figure 3 is a flow chart of the Rth round after scrambling the encryption method of the white-box cipher based on local differential privacy protection of the present invention;

Figure 4 is a schematic structural diagram of the m-RR model.

Detailed ways

The present invention will be further described in detail below in conjunction with the accompanying drawings and examples.

Each legitimate user of a digital content distribution system based on encrypted information broadcasting (such as encrypted pay TV, distribution of multimedia content on the Internet, etc.) has an equivalent key and can use this personal key to decrypt the content. In content distribution systems that broadcast encrypted information, each user is equipped with a "decryption box." It may be a smart card integrated with the decoding equipment in some existing pay-TV systems or a smart card integrated with software in a personal computer. Traceable cryptographic applications use assigned private secret equivalent keys and their corresponding function descriptions for encryption and decryption. This idea of equivalent key protection can be applied to different representations of private key passwords, that is, the key is hidden in a specific algorithm to ensure the security of the password and implement white-box implementation. R is the number of constructed groups, then the meta-key consists of two one-to-one mappings, t, and r (d-1) tuples Θ _i , such that for r=1,..,R is distinguishable. Then the function can be described as

s,t represents two slaves to/> Linear mapping of /> is a single function, r=1,...,R, θ is a (d-1) tuple, such that/> and q ⁿ -1 are relatively prime, Fκ refers to the implementation of the entire block cipher. /> The construction is to make this tuple relatively prime with q ⁿ -1.

according to

s,t represents two slaves to/> A linear mapping of E _θ represents a monomial function. If s, t are unknown, then G is considered to be one-way. Φ represents an identification function that converts a finite field/> Expansion of domain/> Elements in use/> n-tuple (a ₀ ,..., _an ) is expressed, where L is defined as: L=K(X)/P(X), P(X) is a polynomial of degree n, then the identification function It can be expressed as:/> G represents the specific representation method of changing the private key to the public key in a certain round.

Now given the user key κ _j , using R-1 linear mappings L _1,j ,...,L _R-1,j from K ⁿ to K ⁿ , the user obtains a series of functions G _1,j ,. ..,G _R,j . G _r,j represents the system of equations of user j’s rth round. That is, a certain user j uses the personal private key s, t, θ assigned by the system to perform the i-th round of representation, which is considered a public key.

Then the entire encryption of user j can actually be described as:

Represents the implementation of the entire block cipher for user j, from round 1 to round R, /> Represents the connection operation.

The idea is to use 0 polynomials to generate replacement polynomials for G _r,j to hide the algebraic structure. A new system is then used to replace the original system, and random equations are added to mask the information. Through this idea of hiding personal keys as concurrent polynomial systems, in a white-box environment, such as a specific content distribution system, it is assumed that the system is fully visible and executable to the attacker, that is, it has the same capabilities as the key owner , the user uses the assigned personal key implemented as a polynomial system G _r,j , and in each round there are multiple concurrent systems running simultaneously, and the correct result can only be obtained in the last round, thus hiding the key into the algorithm , then the attacker can execute the intermediate results of each round. Because of the hidden random equation and the concurrent polynomial system, the key is completely embedded in the algorithm. The attacker cannot obtain the key, nor can he obtain other information. Equivalent description, thereby achieving the security of user private keys in a white-box environment and ensuring the safe distribution of digital content.

The white-box cipher encryption method based on local differential privacy protection treats each round of the block cipher as a polynomial in a finite field, and can modify it to achieve a white-box cipher composed of a polynomial. In the process, additional items need to be embedded to clutter the original system. And a local differential privacy protection method is used to disrupt the final round of input. The method includes the following steps:

Step 1: Rounds 1 to R-1 use random equations and polynomial equations for disruption.

Use X=(x ₀ ,...,x ₁₅ ) to represent the input variables. represents the system of equations of the original wheel, represents a system of polynomial equations,/> represents a random equation. Represents the output variable of round i. Let S _i represent the system of equations of the i-th round of encryption. So,

Round 1 is represented as follows:

first round:

Among them, S ₁ is the equation system of the first round of the original password, Represents the output variable of the first round,/> is a constant value system of polynomial equations,/> is the given polynomial, R ₁ (X) is the first round of t ₁ random polynomial equations, M ₁ is a linear bijection represented by a square matrix of size n+s+t ₁ , n is the original The number of equations of the block cipher; s is the number of equations of the scrambled polynomial system of equations, and _t1 is the number of equations of the random polynomial system of equations. /> Represents the system of polynomial equations after the first round of perturbation, /> represents a random equation, and Z ₁ represents the output variable of round 1.

Rounds 2 to R-1 are expressed as follows:

Among them, r=2,...R-1, S _r is the system of equations of the r-th round original password, Ran _r is the new system of polynomial equations of t _i equations, M _r is a linear bijection, with size Square matrix representation of n+s+t _i , Representing the system of equations of the original wheel,/> Represents a system of polynomial equations used for perturbation, /> Represents a new system of equations consisting of t _i random equations, Z _r represents the output of the r-th round, and S _r represents the system of equations of the r-th round of encryption.

Step 2: Round R performs local differential privacy protection on the inversion result of the output of round R-1. The random equation is discarded, the polynomial becomes 0, and the output of round R is obtained.

R _R is the system of equations corresponding to the last round of the original cipher; O _Φ is the system of n polynomial equations, in The value is 0. The last round is Z _R = _RR ′(Z _R-1 ). RR is a local differential privacy protection model.

Step 3: Use multiple instances to vote and filter the same parts of the final output results to obtain the correct ciphertext output.

In the last round, differential privacy protection was performed on the input, and the scrambled data was obtained as a replacement for the original input, and the corresponding results were also changed. Disturbing polynomial Take the pre-given value/> And on the finite field GF(2), it can always be expressed by binary equations, the system /> will take two different values,/> and/> O _Φ is right Take 0, that is/> Eventually the effect of the perturbation polynomial on the original equation will disappear. Then the perturbation polynomial takes the predetermined value/> Voting is required from multiple instances, ultimately selecting four relevant polynomials/> So that for any input, two of them are 0, and the other two take different values, and the result after the disturbance disappears is obtained. So for the disruptive impact of differential privacy, we need to determine the relevant parameter values, and ultimately ensure the privacy and availability of data. Finally, in order to obtain the final result, it is necessary to extract the parts with the same results of the four instances to obtain the correct output of the final ciphertext.

The local differential privacy protection described in step 2 is a privacy protection scheme for multiple sensitive values, that is, the m-RR model. For N values, each value corresponds to a sensitive value. Assume that there are m sensitive values in total. The model can be specifically described as: (1) Input m sensitive values (2) Use the m-RR model for local differential privacy protection mechanism (3) Output m perturbed values.

Referring to Figure 4, m-RR model, the RR process can be modeled as the transmission process of a multivariate discrete channel, that is, an extended m-ary RR model to perform localized privacy protection of data. Enter as The output is/> This privacy protection mechanism can be described as the conditional probability of mapping _xi to y _j .

The model can be specifically described as:

In the formula, λ is a parameter introduced, and the corresponding degree of privacy protection can be achieved by adjusting the size of λ. ω _i refers to the sensitive value weight set for each sensitive value based on actual privacy requirements. i represents the sensitive value index value during input, and j represents the sensitive value index value after passing the RR mechanism. Different index values correspond to different types of sensitive values. The discrete symmetric channel of this model is symmetric, when i=j, x _i =y _j . At this time, is the probability of correct mapping.

Figure 1 is a flow chart of the present invention after the first round of perturbation of the AEo/wS instance. For an input of 16 bytes, after the first round of R ₁ iteration of the original system, we obtain Then add the disruptor system/> Get/> and a random equation system Ran ₁ , which perturbs the original equation system and the perturbed system respectively. Finally/> and/> As input, the output Z ₁ of the first round is obtained through M linear mapping and random permutation.

In the same way, as shown in Figure 2 for the flow chart after the rth round (2≤r≤R-1) of the AEo/wS instance, the input of the next round requires the M matrix of the output of the previous round. Inversely we get and Z _r-1 are then used as the inputs of the original system R _r , the disturbed system I and the random system Ran _r respectively. Finally/> and/> As input, the output Z _r of the rth round is obtained through M linear mapping and random permutation.

In the last round, as shown in Figure 3 for the flow chart after the Rth round of perturbation of the AEo/wS instance, similarly, the input of the next round needs to be obtained by inverting the M matrix of the output of the previous round. and Z _R-1 , and then pass all the input values obtained through the m-RR local scoring privacy protection model as shown in Figure 4. Each input value will get a disturbed value, and then the corresponding system value will be As the original system R _r , the input to the perturbed system. At this point the stochastic equation has been discarded. At the same time, the system is disturbed by O _Φ such that/> That is, to eliminate the disturbing influence, and finally/> As input, the output of the last round Z _R is obtained by addition.

Here we take R=10, set the number of participating samples to 43, and set the sample value set That is, m=3, each Y represents a sensitive value, and the sample comes from the distribution PX=[16/43, 4/43, 23/43]. The m-RR mechanism is applicable to any discrete finite sensitive value of m≥2 elements. Personalized privacy protection based on RR). The sensitivity value ω _i and parameter λ can be set by yourself. In practice, the size of parameter λ can be adjusted to achieve the corresponding degree of privacy protection. However, certain availability and privacy of data need to be guaranteed. Specific measurement indicators can be referred to as follows:

estimation error

use To evaluate the privacy distribution estimation problem of the RR model, which is called the estimation error, then

Among them, the same privacy protection operation is performed on each sensitive value, and Pi _,1 =P _i,2 =...=P _i,m =P is set. _{The prior} probability _P The smaller it is, the smaller the estimation error is, which means the higher the accuracy of the privacy distribution.

The degree of privacy protection for a certain sensitive value

The _{objective privacy leakage} degree of a certain _{sensitive value} The ratio of experimental probabilities:

in,

It is the inversion operation of d _H (k _j ,i). P _ci reflects the average probability that the original sensitivity value is _xi and that _xi can be correctly guessed under the CMAP criterion.

Combining the above two indicators, after setting the sensitivity value appropriately, the effect of data privacy and availability can be achieved by adjusting the parameter λ.

After performing differential privacy protection, you will get scrambled data. This data has a high probability of being original data, but some cryptographic data may be randomly divided into other sensitive values, thereby entering a random system or a perturbation system. Therefore, in the end To get the correct result, you need to extract the same part of the data from the output results of the 10th round of all instances to get the correct result. The voting mechanism is also used here.

For this scheme, although the efficiency is based on the original scheme and increases the time consumption of an m-RR model algorithm, in terms of security, since the last round of input values are disturbed, it is modified, and the observation of the The output results in 10 rounds cannot be reversely speculated to divide the original system, perturbation system and random system, so it can resist Mulder attack very well. At the same time, it also meets the security of Bringer's original system. Due to the introduction of the perturbation system and the random system, it can also well resist algebraic attacks, interpolation attacks and coron attacks on AES (the example of this solution uses AEw/oS) .

references

[1]Chow, S., Eisen, P., Johnson, H. and Van Orschot, P.C. (2003) White-boxcryptography and an AES implementation. Selected Areas in Cryptography. 2595250-270.

[2] Chow, S., Eisen, P., Johnson, H. and van Oorschot, P.C. (2002) A white-boxDES implementation for DRM applications. Digital Rights Management. 2696 1-15.

[3]Y.Xiao and

[4]Bringer J, Chabanne H, Dottax E. White Box Cryptography: Another Attempt [J]. IACR Cryptol. ePrint Arch., 2006, 2006 (2006): 468.

[5] De Mulder Y, Wyseur B, Preneel B. Cryptanalysis of a perturbated white-box AES implementation [C]//International Conference on Cryptology in India. Springer, Berlin, Heidelberg, 2010: 292-310.

[6] Biryukov A, Bouillaguet C, Khovratovich D. Cryptographic schemes based on the ASASA structure: Black-box, white-box, and public-key[C]//International conference on the theory and application of cryptology and information security. Springer, Berlin, Heidelberg, 2014: 63-84.

Bogdanov A, Isobe T. White-box cryptography revisited: Space-hardciphers[C]//Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. 2015:1058-1069.

Claims (3)

1. A white-box password encryption method based on local differential privacy protection, which is characterized by including the following steps: Step 1: Use the personal private key assigned by the system to construct a block cipher. The constructed block cipher has a total of R rounds, including; G represents the specific representation method of changing the private key to the public key in a certain round, s and t represent two linear mappings, E _θ represents the monomial function,/> Represents the identification function; The entire encryption description for user j is: Represents the implementation of the entire block cipher for user j, from round 1 to round R, /> Represents the connection operation, G _r,j represents the public key representation of user j using the personal private key assigned by the system for the i-th round; Step 2: Use random equations and polynomial equations to disrupt rounds 1 to R-1 respectively, including: Round 1: Among them, S ₁ is the equation system of the first round of the original password, Represents the output variable of the first round,/> is a constant value system of polynomial equations,/> is the given polynomial, R ₁ (X) is the first round of t ₁ random polynomial equations, M ₁ is a linear bijection, represented by a square matrix of size n+s+t ₁ , /> Represents the system of polynomial equations after the first round of perturbation, /> represents a random equation, Z ₁ represents the output variable of round 1; Round 2~R-1: Among them, r=2,..., R-1, S _r is the system of equations of the r-th round original password, Ran _r is the new system of polynomial equations of t _r equations, M _r is a linear bijection, with size is the square matrix representation of n+s+t _r , Representing the system of equations of the original wheel,/> Represents a system of polynomial equations used for perturbation, /> Represents a new system of equations composed of t _r random equations, Z _r represents the output of the r-th round, and S _r represents the system of equations of the r-th round of encryption; Step 3: In round R, local differential privacy protection is performed on the inversion result of the output of round R-1, the random equation is discarded, and the system of perturbed polynomial equations becomes 0 to obtain the output of round R; R _R is the system of equations corresponding to the last round of the original cipher; O _Φ is the system of n polynomial equations, in The value is 0, that is/> RR is a local differential privacy protection model,/> Represents the result of perturbation through the m-RR mechanism after the inversion of the output result of the R-1 round, and the perturbed result is considered as the input of the original system S _R of the R-th round,/> Indicates that the result after the disturbance is considered as the input of the R-th round of disturbance system, /> Indicates that the result after the disturbance is considered as the input of the R-th round random system random system Ran _R , /> represents the output of the last round of S _R through the original system, Represents the output of the last round of O _Φ through the random system; The local differential privacy protection adopts the m-RR model. For N values, each value corresponds to a sensitive value, and there are m sensitive values in total. The model can be specifically described as: (1) Input m sensitive values, (2 ) Use the m-RR model for local differential privacy protection, (3) output m perturbed values; The m-RR model is modeled as the transmission process of multivariate discrete channels, and the input is The output is Local differential privacy protection is the conditional probability of mapping x _i to y _j , The model is specifically described as: In the formula, λ represents the introduced parameter, ω _i represents the weight, i represents the sensitive value index value at input, and j represents the sensitive value index value output after passing through the RR mechanism; Step 4: Use multiple instances to vote and filter the same parts of the final output results to obtain the correct ciphertext output. 2. A white-box cryptographic encryption method based on local differential privacy protection according to claim 1, characterized in that: the discrete channel of the m-RR model is symmetrical, that is, when i=j, x _i = y _j . 3. A white-box cryptographic encryption method based on local differential privacy protection according to claim 1 or 2, characterized in that the system is a digital content distribution system based on encrypted information broadcast.