Differential-Algebraic Cryptanalysis On Block Cipher Serpent-256

Modern cryptographic theory and cryptographic technology are important basis of information security. The encryption scheme in modern cryptography includes symmetric encryption and asymmetric encryption and the former is further classified as block cipher, stream cipher and hash function. Block cipher has become an important encryption scheme for attractive features such as high rate, easy for standardization and efficient implementation of software and hardware.In order to obtain an excellent encryption algorithm, cryptographers make use of all kinds of mathematic technique to design secure and efficient ciphers, then cryptanalyze their weakness and improve it, finally the excellent algorithm will be found. At present, differential cryptanalysis, linear cryptanalysis, square attack and algebraic cryptanalysis have been the main cryptanalysis technologies.Approved in 1977, the Data Encryption Standard (DES) was an early standard for block cipher, which has been widely used in the world. The block size and the key length are respectively 64 bits and 56 bits, which became the main security disadvantages. So DES has been unsecured and need to be replaced. To this end the National Institute of Standards and Technology (NIST) has been holding a competition to develop the Advanced Encryption Standard (AES) as a replacement for DES. Triple DES has been regarded as a temporary standard to be used until the AES is finished sometime in 2001.In 1997, NIST announced the initiation of the AES development effort and called for new algorithm. The call required the AES, as a block cipher, the block size should be 128 bits and the key size should be 128, 192 and 256 bits.In 1998, NIST announced fifteen AES candidate algorithms at the First AES Candidate Conference. The Second AES Candidate Conference was held in 1999 to discuss the results of the analysis by the global cryptanalyzers on the candidate algorithms. At last, NIST selected five algorithms from the original fifteen submissions. The AES finalist candidate algorithms were MARS, RC6, Rijndael, Serpent, and Twofish. In the third AES Candidate Conference, Rijndael[1] as the winner, got 87 votes, Serpent got 59 votes, Twofish 31 votes, RC6 23 votes and MARS 13 votes. In the end, NIST selected Rijndael as AES. Because Rijndael is faster than Serpent, so Rijndael became the winner.Serpent was designed by Ross Anderson, Eli Biham and Lars Knudsen and is faster than DES and more secure than Triple DES. It provides users with a very high level of assurance that no shortcut attack has been found. The designers for this cipher provide some cryptanalysis for the block cipher and prove that Serpent can resist many known attacks. The key strategy for Serpent uses 32 rounds which is twice as 16 rounds for most ciphers. Though some unknown attacks may break 16-round Serpent as other block ciphers, but breaking 32 rounds Serpent is very difficult. So Serpent is regarded as a strong algorithm. However, the increase for the number of round must reduce the encryption rate, so Serpent is slower than Rijndael. The designers regard that Serpent has lifespan of at least a century. So the cryptanalysis on Serpent is very significant. Many cryptanalysis attempts for Serpent have been done[2, 3, 4, 5].In 2002, Courtois and Pieprzyk used algebraic attack, which is a cryptanalysis technology of stream cipher, to cryptanalyze block cipher[6]. They attacked Rijndael and Serpent. Algebraic attack on block cipher exploits algebraic properties of S-boxes and represents a block cipher as boolean equations. In the equations, the input and output of S-box in each round are unknown variables, and extend the boolean equations to the whole cipher, so the number of unknown variables and the number of equations are very great. The basic method of solving system of quadratic equations is linearization, in which each quadratic expression is substituted with a new term, and the solving problem becomes a solution problem to find the solution for a linear system equations. In addition, the number of equations is less than the number of unknown variables, so the system equations is over-defined system. For the over-defined system, an extended linearization technique is proposed in [34], in which some variable is multiplied by equations to produce new equation. But this method can't guarantee the new produced equations are independent. Another linearization method is put forward in [6], the method uses the sparse structure of equations related to a block cipher and produces more equations without introducing new terms. However, the exact time complexity for this method is difficult to be compute, so the efficiency for this method is still unknown.Differential cryptanalysis[7,8] is a general cryptanalytic tool invented in 1990 by Eli Biham and Adi Shamir. The attacker observes the difference between the two ciphertexts is related with the difference between the corresponding plaintexts. In the differential cryptanalysis, the attacker finds the high probability differential characteristic as a distinguisher, and combines with some key bit guesses of one or two rounds to retrieve the key.In this dissertation we will present a new shortcut attack, differential-algebraic cryptanalysis, and utilize the new cryptanalysis technology to attack Serpent.Concentrating on security analysis, there are two principal achievements in this dissertation:1.Put forward New Cryptanalysis Strategy, Differential-algebraic Cryptanalysis.The efficiency of differential cryptanalysis lies in how to distinguish the differential characteristic of a block cipher. For the algebraic attack, as the round number increases, the number of equations will rise, thus the equations are difficult to be solved. How to extend to more rounds for algebraic attack? Many researchers try to find the efficient technique to solve these equations, such as XL algorithm. In the differential cryptanalysis, if the best differential characteristic of a block cipher has been found, the current differential cryptanalytic result for a block cipher is difficult to be improved by the differential cryptanalysis method. For algebraic attack, if the efficient algorithm can't be developed, the current cryptanalytic result from algebraic attack can't be improved. Can we utilize the algebraic properties for block cipher to extend the differential cryptanalysis to more rounds?Based on the above, Prof.Xiaoyun Wang proposed the idea of differential-algebraic cryptanalysis for this dissertation, which combines the differential cryptanalysis with the algebraic cryptanalysis. Based on the idea, we construct the mathematic model for differential-algebraic cryptanalysis under the guidance by my supervisor.If a r-round differential characteristic with high probability has been found in differential cryptanalysis, in general the attack on r+1 or r+2 rounds can be performed by differential cryptanalysis method. However we would like to extend the attack to more rounds by the proposed differential-algebraic cryptanalysis. So the first step is to build the algebraic multivariable system equations for the last s rounds from round r + 1 to round r + s, in which the unknown variables are subkey bits and the coefficients are related to the cipher and output difference of the differential characteristic. If a given plaintext-ciphertext pair satisfies the differential characteristic, substitute the ciphertext pairs into the system of equations, so the solutions for the system of equations must include the right subkey value for the last s rounds. If we can find the solution, the attack on r + s rounds is successful.For constructing the system of equations, the algorithm to present the Boolean function for S-box is given in the dissertation. Given the truth table for S-box (m input bits and n output bits), we developed a software to automatically build the Boolean function for S-box with the algorithm.However, because the system equations of the last several rounds are nonlinear, solving the equations is difficult too. But the verification for the system of equations is very easy to be realized.In order to reduce the complexity of the cryptanalysis, the verification process includes the following key techniques,1)If the avalanche effect for a block cipher is not ideal, only part of round subkey bits appear in each equation, which is helpful to our attack. The verification for the equation can be finished one by one. Based on the random distribution principle, in each verification, half of all possible solutions satisfy the verified equation, half of them do not.2)Select the optimized verification order of equations.The equation involving fewer subkey variables should be verified in ad- vance. As deciding the next verified equation among the remained equations, choose the equation which have the largest number of subkey variables which have been verified in advance.3)Divide the subkey space involved in each equation. All possible subkey values need to be verified. If the number of subkey bit involved in each equation is large, the advantage for the differential-algebraic cryptanalysis is not obvious compared with the differential cryptanalysis. In order to enhance the advantage, two methods are used: one is to extend the output difference information of the differential characteristic to more rounds for reducing the number of variable and term; the other is to introduce some special transformation for subkey variable for reducing the number of variable.Because our cryptanalysis makes use of the distribution rules of subkey bits in the equations, the number of verified subkey values in differential-algebraic attack is less than the number of guessed subkey value in differential cryptanalysis. So all the subkey space is divided more thoroughly than in differential cryptanalysis. In order to compare with differential cryptanalysis, we introduce two important evaluating parameters. One is the signal-to-noise proposed by Eli Biham and Adi Shamir; the other is the successful rate P_S which satisfies standard normal school. P_S is related with the number of chosen plaintext, S/N and etc. Based on the relationship, we obtain the following conclusion: the time complexity and the data complexity in differential-algebraic cryptanalysis are less than that in differential cryptanalysis. For a block cipher, if the subkey distribution for the last several rounds is not ideal, i.e. the ciphertext bit is only related with part subkeys for the last several rounds, the differential-algebraic cryptanalysis on this cipher will be efficient than differential cryptanalysis on it.2.Differential-Algebraic Cryptanalysis on 8-round Serpent-256Until now, the best differential cryptanalysis result is finished by Biham et.al, they found the 6-round differential characteristics with 2^-93 probability, then 7-round and 8-round differential cryptanalysis was given respectively based on this differential characteristic. The time complexity is 2^206.7 times eight-round Serpent encryptions, the data complexity is 2⁸⁴ and the memory requirements are about 2⁸⁹ bytes[9].In this dissertation, we give the differential-algebraic attack on 8-round Serpent with 256 bits key based on 6-round differential characteristic. We construct the system equations for the last two rounds, where the unknown variables are subkey bits of 7-8 rounds and the coefficients are related to the ciphertexts and the output difference of the 6-round differential characteristic. By making use of the characteristic for non-active S-box, the input difference of 5 bits for round 8, the output difference of 52 bits for round 7 and the input difference of 76 bits for round 7 are deduced. So our constructed system equations includes 128 equations, among which 76 equations with the degree 9 have about 5000 terms, 47 equations with the degree 3 have about 250 terms, and 5 equations with the degree 3 have no more than 10 terms.We find a best order to verify the system equations which is useful to reduce the time complexity of the cryptanalysis. Our attack can recover the 256-bit key by about 2⁸³ chosen plaintexts, 2^180.4 8-round Serpent encryptions and 2^176.7 bytes memory. Compared with differential cyrptanalysis, the time complexity in our attack is reduced significantly and the data complexity in our attack is reduced slightly. In addition, from our attack, the conclusion can be deduced: the linear transformation in Serpent is not ideal for less subkey bits are involved in each linear transformation function.