Research On Linear Cryptanalysis And Its Extensions

Block cipher is one of the most important components in cryptology, and it is always served as the core cryptological algorithm in the aspects such as data encryption, message authentication, key management, and so on. With the presentation of differential cryptanalysis and linear cryptanalysis, people can investigate the security of block cipher systematically. Since then, the research work based on differential cryptanalysis and linear cryptanalysis has become a hotspot in cryptology, many efforts have been made to generalize and extend these approaches in order to derive more effective crypanalytic methods such as truncated differential cryptanalysis, higher order differential cryptanalysis, impossible differential cryptanalysis, boomerang attack, rectangle attack, multiple linear cryptanalysis, non-linear cryptanalysis, multidimensional linear cryptanalysis, differential-linear cryptanalysis, and so on. Such work has dramatically pushed forward the analysis theory of block cipher, resulting in considerable improvement of the design theory of block cipher and finally facilitating the development of block cipher greatly.In this dissertation, we work on linear cryptanalysis and its extensions from two aspects. Firstly, we study the security of some well-known block ciphers by means of linear cryptanalysis and multiple linear cryptanalysis, which may be helpful in the security evaluation of these ciphers. Moreover, we propose some new effective cryptanalytic methods based on the approaches such as linear cryptanalysis, multiple linear cryptanalysis, multidimensional linear cryptanalysis, linear hull, and so on. As a matter of fact, our novel cryptanalytic tools can be used in the security analysis of various block ciphers. The highlights of this dissertation are listed as follows:(1) The block cipher ARIA was selected as a data encryption standard by the Korean Ministry of Commerce, Industry and Energy in 2004. In this dissertation, we present a kind of special linear characteristics for SPN block ciphers and then derive a series of 4-round linear characteristics of ARIA. Based on such 4-round linear characteristics, we propose attacks on 7-round, 9-round and 11-round ARIA respectively. The designers of ARIA expect that there isn't any effective attack on 8 or more rounds of ARIA by means of linear cryptanalysis. However, our work shows that such attacks do exist. Moreover, our cryptanalytic results are the best known cryptanalytic results of ARIA so far.(2) SMS4, the first commercial cryptological algorithm released by Chinese government in 2006, is an underlying block cipher used in WLAN Authentication and Privacy Infrastructure (WAPI), the Chinese national standard for WLAN. In this dissertation, we study the security of the block cipher SMS4 against multiple linear crytanalysis for the first time. By analyzing the properties of the structure and the round function of SMS4, we find a series of 5-round iterative linear characteristics of the cipher, from which a list of 18-round linear characteristics of the cipher can be constructed. With the help of such 18-round linear characteristics, we mount an effective key recovery attack on 22-round SMS4. Compared with the previously best cryptanalytic results on 22-round SMS4, our result has better data complexity as well as comparable time complexity and memory complexity.(3) In 1994, K. Nyberg proposed a cryptanalytic approach by using a set of linear characteristics with the same input mask and the same output mask which is denoted as linear hull. Following this idea, we introduce the concept of differential-linear hull and the cryptanalytic method by adopting differential-linear hull. In comparison with differential-linear crypatanlysis, our new method can exploit more statistical properties from a differential-linear hull, thus leading to a better data complexity. For the purpose of illustration, we mount an effective key recovery attack on reduced-round SERPENT by applying the new method.(4) Generally, modern block ciphers are devised to avoid good long truncated differential and linear characteristics in order to resist traditional attacks such as differential, truncated differential and linear cryptanalysis, but usually good short ones still exist. According to differential-linear cryptanalysis, an adversary can obtain long cryptanalytic distinguishers by concatenating good short truncated differential and linear characteristics, which leads to more powerful attacks on block ciphers. In this dissertation, we present several extensions to differential-linear cryptanalysis, called differential-multiple linear cryptanalysis and differential-multidimensional linear cryptanalysis, by combining differential and multiple linear cryptanalysis, differential and multidimensional linear cryptanalysis respectively. Compared with differential-linear cryptanalysis, our extensions improve the data complexity of cryptanalysis. As a demonstration, we use the new approaches to cryptanalyze reduced-round DES and SERPENT respectively, and the corresponding cryptanalytic results confirm the effectiveness of these approaches.(5) As one of the most important approaches in side channel attacks, differential fault analysis (DFA) has already been applied to attack many block ciphers by means of inducing some faults at the last few rounds of block ciphers. In this dissertation, we present a new fault attack on block ciphers called linear fault analysis (LFA), in which linear characteristics for some consecutive rounds of a block cipher will be utilized instead of exploiting differential distributions of S-Boxes within the block cipher in DFA. Basically, the new approach can handle the case that faults are induced several rounds earlier compared to DFA. For the sake of verification, we mount a key recovery attack on SERPENT by adopting LFA and achieve a good cryptanalytic result.