Security Analysis Of Block Cipher

Although the two security principles, confusion and diffusion, that the design of modern block cipher based on were proposed by Shannon in 1949, the real start of the research into modern block cipher theory was actually marked by the publication of DES in the mid 1970’s. The emergence of differential cryptanalysis, linear cryptanalysis and many other cryptanal-ysis techniques as well as the rapid development of computing power in the 1990’s finally impelled the America and the Europe to launch the AES and the NESSIE projects, respective-ly. These projects greatly promoted the development of the design as well as cryptanalysis theory of modern block cipher. Inspired by differential and linear cryptanalysis, lots of new cryptanalysis models have been introduced to the field of block cipher cryptanalysis. Differ-ential cryptanalysis focuses on the propagation of difference with high probability within the cipher structure to mount key recovery attacks against target ciphers. As a variant of differ-ential cryptanalysis, the impossible differential cryptanalysis observes the cipher structure in another way:utilizing the impossible differential (differential with probability 0) to distin-guish the right key guess and wrong key guess. Due to the significant results achieved by impossible differential and the similarity between differential and linear cryptanalysis (both are based on the existence of high probability events residing in the cipher structure), the exis-tence of a similar technique in the domain of linear cryptanalysis (like impossible differential cryptanalysis to differential cryptanalysis) became an interesting topic.Fortunately, the proposition of zero-correlation (ZC) linear cryptanalysis by Bogdanov and Rijmen in 2012 led to a new line of research into this direction. Linear cryptanalysis takes advantage of the existence of linear approximation (linear hull) with high probability bias, whereas ZC linear cryptanalysis relies on linear approximations with correlation zero (bias being zero). Bogdanov and Rijmen demonstrated how to use such ZC linear approx-imations to mount key recovery attacks against target ciphers. Despite the novelty of this new technique at the publication time, its application is severely limited by the high data complexity requirement. Inspired by the multiple linear cryptanalysis, Bogdanov and Wang proposed to reduce the data complexity with multiple ZC linear approximations in the way of distinguishing statistical distributions, referred as multiple ZC linear cryptanalysis. By using l ZC linear approximations, this new model could reduce the data complexity to l(2n/(?)), where n is the block length in bits of the target cipher. Yet, the new cryptanalysis model is controversial due to a strong assumption that does not always hold in real ciphers, ZC linear cryptanalysis still needs further improvements. To remove the dependence on the strong as-sumption, Bogdanov et al. introduced a new cryptanalysis model, the multidimensional ZC linear cryptanalysis, at ASIACRYPT 2012. This new model shares basically the same data complexity with the multiple ZC linear cryptanalysis model and relies on no strong assump-tion. With multidimensional ZC linear cryptanalysis, ZC linear cryptanalysis finally matured.The Fast Fourier Transformation (FFT) technique was firstly introduced to the domain of block cipher cryptanalysis by Collard et al. at ICISC 2007, where they found that under cer-tain conditions the time complexity of linear cryptanalysis could be reduced by utilizing FFT technique. Due to the similarity between linear cryptanalysis and multiple ZC linear crypt-analysis, FFT can also be integrated into the attack procedure of multiple ZC linear crypt-analysis to improve the corresponding time complexity. The FFT technique has been utilized in linear cryptanalysis, multiple ZC linear cryptanalysis as well as integral attack. Despite the wide applications of FFT technique, to use FFT technique in the key recovery attack it is required that only XOR operation with subkeys or at most one modular addition with subkey are involved in the partial encryption/decryption phase. With this requirement, the FFT tech-nique normally cannot be utilized in the ARX block cipher context where it is common to have multiple modular addition operations with subkeys in the partial encryption/decryption phase.General FFT Scheme and Its Application to CAST-256 We investigate the circulant ma-trix theory behind the FFT technique and find that even in the context of ARX ciphers where multiple modular with subkeys are involved in the key recovery procedure the FFT technique can still be used to reduce the time complexity of certain key recovery attacks. Based on this observation, we reexamined the security of CAST-256 against the multiple ZC linear attack. By integrating the FFT technique into the key recovery procedure, we successfully mount key recovery attack against 29-round CAST-256. This is the best result against CAST-256 without weak key assumption at the time of publication.Multidimensional ZC Linear Attack on HIGHT HIGHT is a lightweight block cipher designed in Korea with the involvement of Korea Information Security Agency. It was pro-posed at CHES 2006 for usage in lightweight applications such as sensor networks and RFID tags. Later it was adopted as an ISO standard block cipher. HIGHT adopts the structure of 8-line Type-Ⅱ generalized Feistel network with a total of 32 rounds. Whitening keys are ap-plied before the first and after the last round. By tracing the propagation of linear mask inside the cipher structure, we successfully reveal ZC linear approximations over 16-round HIGH-T. With these linear approximations and combined with optimized key guessing procedure as well as the application of bitwise partial-sum technique, we are able to attack 26-round HIGHT (round 4 to round 29) with all whitening keys.This attack of ours is the first one against 26-round HIGHT with all whitening keys in the single-key setting. Besides, a key recovery attack against 27-round HIGHT (round 4 to round 30) with all whitening keys is also presented. Compared with the previous best attack against HIGHT (not considering Bi-clique attacks), the impossible differential attack on 27-round HIGHT provided by Chen et al. at AFRICACRYPT 2012, our attack against 27-round HIGHT has significant advantage in terms of memory complexity.Multidimensional ZC Linear Attack on E2 E2 is a block cipher designed by NTT, Japan and is one of the first-round AES candidates. E2’s design principles influenced several more recent block ciphers including Camellia, an ISO/IEC standard block cipher. The key size of E2 can be 128,192 or 256-bit, denoted as E2-128, E2-192 and E256 respectively. All three versions have a total of 12 rounds. We construct ZC linear approximations over 6-round E2. Key recovery attacks on 8-round E2-128 and 9-round E2-256 without considering IT and FT are mounted using multidimensional ZC linear cryptanalytic technique. Compared with the previous impossible differential attacks against E2, our attacks can work one more round. Compared with the previous truncated differential attacks, the time complexity of our attack against 8-round E2 is explicitly lower. Attacks against 6-round E2-128 and 7-round E2-256 with both IT and FT considered with the same cryptanalytic technique are also presented in this thesis. These are the first key recovery attacks against E2 considering both IT and FT.Due to the effectiveness of ZC linear cryptanalysis, the links between the ZC linear dis-tinguisher and other distinguishers become an interesting topic. Bogdanov et al. pointed out in that under certain conditions, the ZC linear distinguisher is equivalent to the integral dis-tinguisher. Like the FFT technique, those conditions cannot be met in ARX ciphers and thus security analysis of ARX ciphers cannot benefit from this observation. Integral ZC distin-guisher for ARX Ciphers with Application to SHACAL-2 We examine the common pattern of ZC linear approximation over ARX ciphers and its relation to the integral distinguisher and find that these ZC linear approximations can also be converted to an integral distinguisher. With this observation, the ZC linear approximations we constructed over 12-round SHACAL-2 are converted to an integral distinguisher. With this distinguisher, we present key recovery attacks against 30-round as well as 32-round SHACAL-2.Related-Key Impossible Differential Attack against 23-Round LBlock Besides al-1 those works related to ZC linear attack, we also look into the security of LBlock in the related-key setting, utilizing the classic related-key impossible differential cryptanalysis. L-Block is a lightweight block cipher designed by Wu and Zhang at ACNS 2011. It adopts 64-bit block size and 80-bit key size. Its structure is based on a modified 32-round Feistel structure. Normally, related-key impossible differential over more rounds leads to key recov-ery against more rounds of the target cipher. In order to find longer related-key impossible differential, we design an searching algorithm. By splitting the master key space into disjoin-t sets, we successfully construct related-key impossible differential over 16-round LBlock (only 15-round related-key impossible differential of LBlock was reported previously). By taking advantage of the 16-round related-key impossible differential, we can mount key re-covery attack against 23-round LBlock. This was the first attack against 23-round LBlock at the time of publication.