Cryptanalysis Of Block Cipher Clefia And Macs Based On Four Rounds AES

Block ciphers belong to symmetric ciphers, which use the same key for both encryption and decryption. A block cipher is an efficient, keyed permutation that transforms a fixed-length block of plaintext into a block of ciphertext of the same length. Block ciphers can be used in many cryptographic primitives, such as encryption and message authentication code (MAC). A MAC function takes as input a secret key and a message of arbitrary length, and produces as output a short tag. MAC is used to ensure integrity and authenticity of messages. The security evaluation of block ciphers and MAC functions has been hot topics of cryptographic research during the past decade.There are two main approaches to construct block ciphers, one is Feistel Network, and another is Substitution-Permutation Network (SPN). An early and highly influential block cipher, the Data Encryption Standard (DES), is based on the Feistel Network, which has a block size of 64-bit and key size of 56-bit. As the rapid development of computer technology, the inadequacy in the key length became apparent. In September 1997, National Institute of Standards and Technology (NIST) announced request for candidate algorithms for the Advanced Encryption Standard (AES),a successor to DES. In October 2000, Rijndael, which is designed by Daemen and Rijnmen, was selected as the proposed AES, and was approved as FIPS PUB 197 in November 2001. AES is a SPN, with a block size of 128-bit and key size of 128/192/256-bit, which has been one of the most popular block ciphers.Many other block ciphers are influenced by the design rationale of the above two, such as CLEFIA, which was proposed by Shirai et al. at FSE 2007. CLEFIA is a 4-branch generalized Feistel Network, and supports 128-bit input and 128/192/256-bit key for 18/22/26-round, respectively. Each round contains two SP-type F-functions, composed of AddRoundKey, SubByte and MixColumn operations. Sony claimed that CLEFIA will be used across various applications and products.The development of block ciphers influences the design of MAC algorithms. Beside the CBC-MAC, which is a well-known mode for block ciphers to provide MACs, several new MAC constructions have been proposed. They take a block cipher and a reduced version of the block cipher as main components, in order to gain higher performance. The AES and reduced AES are taken as representative. Daemen and Ri-jmen, the designer of AES, proposed the A_LRED construction at FSE'05, and presented an instance based on AES and 1-round AES, which is named A_LPHA-MAC. Later, they published an optimized version of A_LPHA-MAC, the P_ELICAN algorithm, which is composed of AES and 4-round AES. Minematsu and Tsunoom introduced the MT-MAC construction and PC-MAC construction at FSE'06, including two examples MT-MAC-AES and PC-MAC-AES, which are also based on AES and 4-round AES. Since they take reduced AES, all of them are efficient than CBC-MAC instantiated with AES.New design techniques improve the performance of algorithms, while their impact on the security needs further investigation. Under the instructions of my supervisor, Xiaoyun Wang, we present cryptanalysis of block cipher CLEFIA and MAC functions P_ELICAN, MT-MAC-AES and PC-MAC-AES as follows.(1) Saturation cryptanalysis of reduced CLEFIASony Corporation published the security and performance evaluations of CLEFIA, which claimed that CLEFIA achieves sufficient immunity against known cryptanalytic attacks. For saturation cryptanalysis, they presented two 8-round saturation characteristics, and applied them to attack the CLEFIA reduced to 10-round without key whitenings.We point out that the 8-round distinguishes proposed by the designers are wrong, and present a right one. We observe that the whitening key can be combined with the round subkey, and the equation with 32-bit variable can be subdivided into 4 byte-wise equations, thus the number of guessed subkeys can be reduced by a divide-and-conquer strategy. Moreover, the partial sum technique is adopted to reduce the time complexity. As a result, the 10-round saturation cryptanalysis is extended to 11-round CLEFIA-128/192/256,12-round CLEFIA-192/256 and 13-round CLEFIA-256, taking the whitening keys into consideration. Till now, it's the best result in the saturation cryptanalysis of CLEFIA.The new 8-round saturation distinguisher we identify is:where A₀₍₉₆₎,A₁₍₉₆₎ and A₂₍₉₆₎ are 32-bit words, and A₀₍₉₆₎|A₁₍₉₆₎|A₂₍₉₆₎ stands for all states of 96-bit values. The distinguisher means that for 2⁹⁶ different inputs where the third 32-bit word is a constant, the XOR value of the 2⁹⁶ 8-round outputs is zero at the first word.According to the 8-round distinguisher, the correct subkey candidates are suggested by the equation (?)C₃^8,i=0, where i=0,…,2⁹⁶. Choose other sets of plaintexts enough, and get such an equation respectively, only the right subkey value satisfies all equations.Combining with the structure of CLEFIA, we find that a divide-and-conquer strat-egy can be used to guess solutions for the equation (?)C₃^8,i=0, which is equivalent to four byte-wise equations. Moreover, we observe that the XOR of 128-bit whitening key and 128-bit subkey can be considered as a 128-bit equivalent subkey. Therefore, the number of related subkeys which are needed to do a partial decryption is reduced greatly. Taking the attack on 10-round version for example, the first byte-wise equation can be written aswhere Y₀ can be derived from the ciphertexts directly. To do a partial decryption, only 40-bit subkey (RK'_17,0,RK₁₈) is needed to guess instead of 64-bit subkey (RK₁₇,RK₁₈) claimed in. The partial sum technique is adopted to reduce the time complexity of our attack.The time complexity of the guessing step is about 2^46.2 encryptions, while the previous result is about 2¹²⁴ encryptions. Thus we can directly extend the 10-round attack to 11-round by guessing the 64-bit subkeys involved in the 11-th round. The complexity is 2^111.4 encryptions and 2^99.8 chosen plaintexts. The attacks on 12-round CLEFIA-192/256 and 13-round CLEFIA-256 can be proceeded in a similar way.(2) Impossible differential cryptanalysis of reduced CLEFIAFor impossible differential cryptanalysis, Sony corporation proposed two 9-round impossible differentials, and analyzed 10-round CLEFIA-128/192/256, 11-round CLEFIA-192/256 and 12-round CLEFIA-256, where they did not consider key whitenings in 12-round attack.We utilize the same impossible differentials, but adopt different extension way. Exploring more technique details, the wrong subkeys can be filtered out more efficiently. Based on the specific difference of plaintexts pairs, we propose the birthday sieve method to reduce the time complexity of precomputation greatly. For CLEFIA-128/192/256, we extend the attack from 10-round to 12-round. For 13-round CLEFIA-192/256 and 14-round CLEFIA-256, our attack still works. We correct the error in the complexity evaluation of 12-round attack in. Meanwhile, it is clear that the whitening keys have no influence on the resistance against impossible differential cryptanalysis.To perform the impossible differential cryptanalysis, we prepend and append more rounds on the top and end of the impossible differential first, and obtain the wanted input/output difference. Construct plaintexts structures where each two plaintexts satisfy the input difference, and sieve the plaintexts pairs with the required output differences by precomputation. Since there are 2^2n-1 plaintexts pairs from 2ⁿ plaintexts, we need to explore a more efficient algorithm to sieve required pairs. We observe the relation between the difference of input and output, and propose a birthday sieve method based on the birthday attack, which reduces the time complexity of sieving pairs to 2ⁿ XOR operations. Suppose the input differenceΔP=(0,0,α,*) and the wanted output dif-ferenceΔC=(*,*,0,α), whereαis a fixed 32-bit value, and * denotes arbitrary 32-bit nonzero value. Since the second and third bytes ofΔP equal to the third and fourth bytes ofΔC respectively,ΔC=(*,*,0,α) is equivalent toΔ(?)=(*,*,0,0), where (?)=(P>>>32)(?)C. And the pairs satisfyingΔ(?)=(*,*,0,0) can be obtained by birthday attack.Then, for each sieved pair, discard the wrong subkeys which cause the partial encryption and decryption to match the impossible differential. Only the correct subkey is left in the subkey space after enough pairs are analyzed. In the sieve process, the following property can be used to deduce one 32-bit subkey in one F-computation by time-memory tradeoff.·For the F-function F (F₀orF₁), let (In,In') be two 32-bit inputs, andΔOut be the difference of the corresponding outputs, the 32-bit round subkey RK involved in F can be deduced with about one F-computation.Moreover, from the specific structure of CLEFIA, we deduce a linear relation between the whitening key and round subkey, and take the two subkeys as one, which reduce the number of related subkeys.·For r-round CLEFIA, let (RK_2r-3,RK_2r-4) be the subkey in the (r-1)-th round, (RK_2r-1,RK_2r-2) be the subkey in the r-th round, (WK₂, WK₃) be the whiten-ing key in the final round, and C^r=(C₀^r,C₁^r,C₂^r,C₃^r) be the ciphertext, we have the following two equations which reveal the correlations among subkeys WK₂, WK₃,RK_2r-3, and RK_2r-4:Here InS_F0^r-1 and InS_F1^r-1 are the inputs to the four S-boxes of F₀^r-1 and F₁^r-1 inthe (r-1)-th round, respectively.By these observations, our attack on 11-round CLEFIA only takes 2^103.1 encryp-tions and 2^103.1 chosen plaintexts, instead of the original 2¹⁸⁸ encryptions and 2^103.5 chosen plaintexts. Moreover, combining with a special way to choose plaintexts pairs, our attack can be applied to 12-round CLEFIA-128/192/256 with 2^119.1 time complexity and 2^119.1 data complexity.Independently, similar observations are presented by Tsunoo et al. They presented some new 9-round impossible differentials, which were applied to attack 12-round CLEFIA-128/192/256, 13-round CLEFIA-192/256 and 14-round CLEFIA-256. However, in the attack on 12-round CLEFIA, they neglected the time complexity of the precomputation. Thus the time complexity is 2^125.8 encryptions actually, which is higher than the claimed 2^118.9. Using the birthday sieve method described in this dissertation, we correct this mistake and keep the previous complexity. At present, these results had been improved by Tsujihara et al.(3) Impossible differential cryptanalysis of MACs based on 4-round AESP_ELICAN, MT-MAC-AES and PC-MAC-AES belong to iterative MAC algorithms. Based on birthday attack, Preneel et al. presented a general forgery attack on all iterative MACs with (?) messages and (?) queries, where n is the length of MAC value. Furthermore, for P_ELICAN, suppose a key or an internal state is known, the second preim-age can be found. In addition, a side-channel collision attack can recover its internal state, which mounts a selective forgery attack.Recently, Wang et al. explored new ideas based on the birthday attack to detect the inner near-collision with specific difference rather than collision, from which more information can be derived. According to birthday paradox, the existence of the inner near-collision with specific difference can be guaranteed by collection of 2^n/2 (message, MAC) pairs. Then such a collision is detected with probability close to 1 by appending message pairs with specific form. The series works extended these ideas to the second preimage attack on CBC-like MACs and an equivalent subkey recovery attack on A_lpha-MAC, respectively.Enlightened by the above techniques, Xiaoyun Wang suggests us to adopt the impossible differential cryptanalysis on MACs, which brings new idea to the cryptanalysis of MACs. Impossible differential cryptanalysis is a powerful attack on AES, which can be applied to 7-round AES-128 (10 rounds in total) . However, little has been done for impossible differential cryptanalysis on MACs, due to the fact that the internal state values as well as their difference, are concealed by the final encryption or complex keyed iterations. We identify the difference of the internal states by birthday attack. Since the main components of P_ELICAN, MT-MAC-AES and PC-MAC-AES are AES and 4-round AES, we can recover the internal state of P_ELICAN with 2^85.5 chosen messages and 2^85.5 queries with a new 3-round impossible differential of AES. Then the selective forgery attack can be processed. This internal state recovery attack directly turns to be a subkey recovery attack on MT-MAC-AES with the same complexities. For PC-MAC-AES, we are able to recover its two 128-bit secret keys separately, once the internal state is identified with 2^85.5 chosen messages and 2¹²⁸ queries.The main idea is as follows: First, construct two structures to produce messagepairs with specific difference. Each structure has 2^n/2 messages. Second, utilize thebirthday attack to search collisions between the two structures. Since the compressionfunction is a permutation, output collision means inner collision. And the inner valueis the XOR of message word and internal state. Thus, the difference of the internalstates can be detected from the difference of message words. Third, once the differenceof the internal states is verified, we can recover the internal state XORed with themessage using a 3-round impossible differential property since 4-round AES is takenas a building block. The 3-round impossible differential characteristic is as follows:·For 3-round AES, given an input pair (z₂^I,z₂^I') whose components equal in allexcept six bytes indexed by (0,1,5,8,12,13) (or (0,1,4,5,9,12), or (0,4,5,8,9,13), or (1,4,8,9,12,13)), the difference of the output pair (z₄^O,z₄^O') can not haveexactly one nonzero byte.