# Chosen Plaintext Combined Attack against SM4 Algorithm
## 3 Methodologies
### Differential Analysis  
Differential analysis of the above selected plaintext data includes three different plaintext inputs. It is known that the first round S-box input difference (the S-box input XOR value obtained from the XOR between the first plaintext input and the second plaintext input) \(\triangle A_{1}\) satisfies the following formula:  
\[\triangle\,A_{1}=M_{0}\oplus rk_{0}\oplus M_{0}^{\prime}\oplus rk_{0}=M_{0} \oplus M_{0}^{\prime} \tag{18}\]  
Similarly, the difference \(\triangle A_{1}^{\prime}\) of the first round S-box input obtained by XOR of the first plaintext input and the third plaintext input satisfies \(\triangle\,A_{1}^{\prime}=M_{0}\oplus M_{0}^{\prime\prime}\). Accordingly, Equation (17) shows that the differences \(\triangle\,C_{1}\) and \(\triangle\,C_{1}^{\prime}\) of the first round of \(L\) transformation meet the following formula respectively. \[\triangle\,C_{1}=T(A_{1})\oplus T(A_{1}^{\prime})=V_{1}\oplus V_{2} \tag{19}\]  
\[\triangle\,C_{1}^{\prime}=T(A_{1})\oplus T(A_{1}^{\prime\prime})=V_{1}\oplus V_ {3} \tag{20}\]  
The output difference \(\triangle\,B_{1}\) and \(\triangle\,B_{1}^{\prime}\) of S-box in the first round can be obtained by conducting \(L^{-1}\) inverse operation on \(\triangle\,C_{1}\) and \(\triangle\,C_{1}^{\prime}\), and the formula is as follows. \[\triangle\,B_{1}=\tau(A_{1})\oplus\tau(A_{1}\oplus\triangle A_{1})=L^{-1}(V_{1 }\oplus V_{2}) \tag{21}\]\[\bigtriangleup B_{1}^{\prime}=\tau(A_{1})\oplus\tau(A_{1}\oplus\bigtriangleup A_{1 }^{\prime})=L^{-1}(V_{1}\oplus V_{3}) \tag{22}\]  
According to the differential definition of S-boxes in Section 2.3, given the input and output differences \((\bigtriangleup A_{1},\bigtriangleup B_{1})\) and \(\bigtriangleup A_{1}^{\prime},\bigtriangleup B_{1}^{\prime})\) of the four S-boxes in the first round, for the input \((M_{0}\oplus rk_{0})\) and \((M_{0}^{\prime}\oplus rk_{0})\) of the four S-boxes, where \(M_{0}\) and \(M_{0}^{\prime}\) are known values, then the number of candidate values of every byte \(rk_{j,0}(j=0,1,2,3)\) could be two or four. The probability is 99.2% for two values and is 0.8% for four values. In the following analysis, suppose that the round key has two candidate values. In case there exist four candidate values (very low probability), the attack is seen to fail and is carried out with different inputs again. For the differential analysis results of the above two times, the correct key is the intersection of the two, that is, two sets of key candidate values (99.2% probability) are obtained by the two analyses, respectively, and there is a same value in the two sets, that is, the correct round key byte \(rk_{j,0}\). The next step is to analyze and recover the four bytes of \(rk_{0}\) in turn, and then recover \(rk_{1}\) from \(V_{1}\). Finally, the correctness of \(rk_{0}\) and \(rk_{1}\) can be further verified by substituting \(rk_{0}\) and \(rk_{1}\) into equations set (17). After \(rk_{0}\) and \(rk_{1}\) are recovered, the same method as above is adopted to select plaintext input so that the 12 bytes (3 words) after the third round of input are XOR fixed, that is, \(M=X_{3}\oplus X_{4}\oplus X_{5}\) is a fixed value, and the first 4 bytes \(X_{2}\) are random values, where \(X_{3}\) and \(X_{4}\) meet the following formulas. \[X_{4}=T(X_{1}\oplus X_{2}\oplus X_{3}\oplus rk_{0})\oplus X_{0} \tag{23}\]  
\[X_{5}=T(X_{2}\oplus X_{3}\oplus X_{4}\oplus rk_{1})\oplus X_{1} \tag{24}\]  
The chosen plaintext input can be determined through derivation. For example, if \(X_{2}\) is selected as random, \(X_{0}=X_{1}=X_{2}\), and \(X_{3}\) is a fixed value, then the round input of the third round can be ensured to meet the condition. Similarly, combining the above Sections 3.1 and 3.2 for power analysis and differential analysis based on chosen plaintext, respectively, can restore the values of \(rk_{2}\) and \(rk_{3}\) in turn.