Cryptanalysis Of Several Block Ciphers

As the foundation stone of information security, cryptology plays a vital role in modern world. Together with the stream ciphers, the block ciphers belong to the symmetric-key ciphers that use the same key to encrypt and decrypt. Normally, the block ciphers are iterated structures, which could be well implemented and fast in both software and hardware. Owing to the wide use of the block ciphers, it is important to analyze the security of them. Cryptanalysis can not only discover the weakness of the existing block ciphers, but also guide the design of new block ciphers.The competition of AES by NIST, the process of NESSIE and CRYPTREC promote the design and analysis of block ciphers. The lightweight block ciphers, which are suitable for low resource devices, become more and more important with the de-velopment of the devices like RFID tags, sensor nodes, etc.This thesis focuses on the cryptanalysis of the ISO standard block cipher Camel-lia, as well as the lightweight block ciphers TEA, XTEA and HIGHT.Block cipher Camellia is proposed by NTT and Mitsubishi in2000. Its block size is128bits and it supports128-,192-and256-bit key sizes with18,24and24rounds respectively. Camellia was selected as an e-government recommended cipher by CRYPTREC and recommended in NESSIE block cipher portfolio. Then it was selected as an international standard by ISO/IEC18033-3.TEA, XTEA and HIGHT are lightweight block ciphers suitable for low resource devices. TEA was proposed by Needham and Wheeler in1994; it is a simple design that is easy to understand and implement. Then the same authors proposed an en-hanced version of TEA-XTEA. Both TEA and XTEA are implemented in the Linux kernel; they use modular addition (modulo232), shift (left and right) and XOR in their round functions. HIGHT, designed by Hong et al., was standardized by the Telecom-munications Technology Association (TTA) of Korea. Recently, it was adopted as an International Standard by ISO/IEC18033-3. It is an8-branch generalized Feistel structure with initial and final whitening layers; its round function uses addition mod-ulo28, rotation and XOR.The methodology used in this thesis are impossible differential cryptanalysis and meet-in-the-middle attack; the results are as follows:·Impossible Differential Cryptanalysis of Camellia1. Impossible Differential Attacks on Camellia-192and Camellia-256with FL/FL-1layersThe structure of Camellia is Feistel structure with FL/FL-1layers inserted every6rounds. The FL and FL-1functions are keyed linear functions which are designed to provide non-regularity across rounds. Due to this reason, a number of impos-sible differential attacks on Camellia focus on the simple versions which exclude the FL/FL-1layers and whitening keys.This thesis proposes the first impossible differentials that include the FL/FL-1functions. The number of rounds of these impossible differentials is6, the FL/FL-1layers are between the third and the fourth round. The reason leads to the impossible differential is there are some constraints before/after the FL/FL-1functions, which result in contradictions that some solutions of the equations must be zero, while the values are actually not zero. For example, by the constraints, we have:b2⊕b3⊕b4⊕b5⊕b6=b2⊕b3⊕b5⊕b6which means b4=0, but actually b4≠0, this is a contradiction.Furthermore, we present some properties of3-round Camellia. These properties benefit the use of early abort techniques, which results in lower time complexities. We also use some techniques to deal with the whitening keys. As a result, we propose impossible differential attacks on10-round Camellia-192and11-round (rounds1-11) Camellia-256with complexities2175.3and2218.5respectively. Then by carefully using the subkey relations and one of the8-round impossible differentials without FL/FL-1 layers proposed by Wu et al, we also present an impossible differential attack on15-round Camellia-256without FL/FL-1layers and whitening keys. A pre-computed table is set up to reduce the time complexity.These results were the best when published, in terms of the number of rounds and time complexity. Especially, the attacks on Camellia-192/-256with FL/FL-1layers attracted the attention of the cryptanalytic community, and led to more results.2. Automatically Searching the Impossible Differentials of CamelliaThere are some other impossible differentials proposed after our6-round impos-sible differentials. E.g., the7-round impossible differentials in, where the FL/FL-1layers are between the1st (6th)-round and the2nd (7th)-round, and the im-possible differentials with conditions in.The FL/FL-1layers in these impossible differentials varies from one and anoth-er, hence we would like to design an algorithm to search the impossible differentials of Camellia. The starting point of our algorithm is the Matrix Method. Similar to the Matrix Method, we adopt the Miss-in-the-Middle methodology to search the impossi-ble differentials. The representation of the differences in our algorithm is similar to that of the Matrix Method, but simpler. The conditions that lead to the contradictions in-cludes all types of impossible differentials of Camellia. In addition, we give a method to deal with the rotation in the FL/FL-1functions. Due to the rotation in the func-tions, some impossible differentials hold with conditions (like the7-round impossible differential in), our algorithm also gives the conditions, if there are any.With the algorithm, we obtain not only the impossible differentials that are already known, but also some new impossible differentials; these impossible differentials might lead to better attacks.·Meet-in-the-Middle Attack on Reduced-Round Camellia-256Besides the impossible differential attacks mentioned above, there are some other impossible differential attacks on Camellia (with FL/FL-1), as well as attacks with other methods. We know that for an impossible differential attack, the at-tacker has to find the pairs that meet the impossible differential under the wrong keys. Consequently, he has to choose a plenty of data if he wants to use an impossible d- ifferential that is long enough. The data complexities of the impossible differential attacks on Camellia are very high; the attacks in and have lower data com-plexities than those of the impossible differential attacks, which are294and256chosen plaintexts, respectively.This thesis presents a meet-in-the-middle (MITM) attack on Camellia-256with a data complexity of219. As the attacks in, our main idea inherits that of. In our MITM distinguisher, we express one bit of a function of Em(x) by some8-bit parameters and1-bit parameters. For the byte-oriented ciphers, the expressions of one bit and one byte usually need the same number of parameters; however, the scenario for Camellia is different due to the keyed linear functions FL and FL-1. Our distinguisher could be seen as an improvement of the6-round higher-order MITM distinguisher (with the FL layer between the4th and5th rounds) of Camellia-256in. We get rid of the integral property and built a standard MITM distinguisher with the FL layer between round5and round6by one-bit expression to reduce as many parameters as possible.Note that for Camellia, FL/FL-1layers insert every6rounds. In order to keep the structure of Camellia, we add1round to the top and4rounds to the bottom of the7-round distinguisher and mount an attack on12-round Camellia-256with only219chosen plaintexts. The attack also takes the whitening keys into account. The time complexity of our attack is2231.2.In terms of the data complexity, our attack is the lowest for Camellia-256. The time complexity is also the best, when one looks at the attacks that begin from the (6n+1)-th (n=0,1,2,3) round of Camellia-256.·Impossible Differential Cryptanalysis of Lightweight Block Ciphers TEA, X-TEA and HIGHTIn the single-key setting, Moon et al. gave impossible differential attacks on11-round TEA and14-round XTEA based on10-round and12-round impossible dif-ferentials, respectively. This thesis presents a novel method to derive impossible dif-ferentials for TEA and XTEA. Due to the one-directional diffusion property of TEA and XTEA, one can determine a one-bit difference after a chosen difference propagates several steps forward/backward, which might lead to a one-bit contradiction in cer-tain rounds if we choose two differences and make them propagate towards each other. Based on this technique, we identify13-round and14-round impossible differentials for TEA and XTEA respectively. These impossible differentials are significantly better than the10-round impossible differential of TEA and12-round impossible differential of XTEA in, and result in improved impossible differential attacks on17-round TEA and23-round XTEA. Our attack on17-round TEA needs257chosen plaintexts and2106.6encryptions. If we use262.3chosen plaintexts, we can attack23-round XTEA with2114.9encryptions; if we increase the data complexity to263, the complexity of the attack will become2106memory accesses and2105.6encryptions. We also present an impossible differential attack on HIGHT reduced to26rounds that improves the result of.In terms of the number of rounds and time complexity, these attacks are the best impossible differential attacks on the three ciphers.