Impossible Differential Cryptanalysis And Meet-in-the-Middle Attack On ARIA

The 21 st century is an era filled with information. People all over the world swim in the ocean constituted by information everyday. Lots of them manage information via network, such as, sending and receiving emails, transacting online, and so on. In-formation has become a significant resource during the development of human society. It has also turned into a massive dynamic and core of the world's evolution. The se-curity of information during the online transfer and interchange becomes more and more important. Information security is now directly relevant to the national security, electronic commerce, the protection of citizens'privacy, and so on. The importance of information security drives the research of cryptology. As a science of guaranteeing the security of data and information, the research of cryptology now becomes worldwide topic.Cryptosystem mainly contains two parts, i.e., public key crpytosystem, and sym-metric cryptosystem. Symmetric cryptography consists of block cipher, stream cipher, and message authentication code (MAC). Symmetric encryption algorithm has many attractive features, such as, high performance and small amount of memories for both software and hardware implementation.Block cipher is an efficient keyed permutation which transforms a fixed-length block of plaintext into a ciphertext block with same length. The keys of block cipher for encryption and decryption are either the same or both can be derived from a same key easily. Block cipher has extensive usage in many fields, such as computer com-munication and the security of information systems. The security evaluation of block cipher has become a hot topic of cryptographic research now a days. Therefore, the core of this thesis is the cryptanalysis of block cipher.We can design block cipher mainly using two constructions. One is Feistel Net-work. In this structure, only half of a block enters the F function every time. So it only possesses a small amount of hardware resource, which is a great feature when the capacity of computation is limited. DES (the Data Encryption Standard)[50], which was early standardized for worldwide block cipher encryption algorithm in 1977, is a typical block cipher based on Feistel Network. DES was highly influential and had been widely used in the world before 2000. Its block size is 64-bit and the key length is 56-bit. The other structure is Substitution-Permutation Network (SPN). The current block cipher standard-AES (the Advanced Encryption Standard)[15], is a typical block cipher which has SPN structure. AES has 128-bit block size, and 128/192/256-bit key length.The design of many other block ciphers is influenced by the rationale of DES and AES, such as the Korean block cipher standard-ARIA[40,52,53], which has extremely similar structure of AES. ARIA was proposed by a group of South Korean researchers in 2003[52], and was updated to version 1.0 in 2004[53]. ARIA is a general-purpose involution SPN block cipher algorithm, and its branch number is 8. ARIA has 128-bit block size with 128/192/256-bit key, and in the original version the corresponding round numbers are 10/12/14 respectively[52], while in the latest version, ARIA v1.O[53], the round numbers are altered to 12/14/16 respectively. ARIA consists of three parts: round key addition, substitution layer and diffusion layer.In 2003, ARIA version 0.8[52]was first announced at an Korean annual conference on security. It had 128-bit block size, and 10/12/14 rounds for key sizes of 128/192/256, and only two kinds of S-boxes were used. Later ARIA was updated to version 0.9[40], and used four different S-boxes in its substitution layer, while had no change about the round number. In the current one, ARIA version 1.0, the number of rounds was increased to 12/14/16, and also made some suitable modification of the key expan-sion. In 2004, this version was announced and published on its official website at http://www.nsri.re.kr/ARIA/. Later in December, ARIA was established as a Korean Standard block cipher algorithm (KS X 1213) by Korean Agency for Technology and Standards (KATS).As the structure similarity of ARIA and AES, lots of the technologies of cryptanal-ysis that work on AES can also affect ARIA. Vice-versa, cryptanalysis which attacks ARIA may also be used to break down AES. Therefore, the security analysis of ARIA becomes highly significant.The designers, Daesung Kwon et al., gave the initial cryptanalysis of ARIA[40]. It contained differential and linear cryptanalysis, truncated differential cryptanalysis, impossible differential cryptanalysis, square attack, higher order differential cryptanal-ysis, interpolation attack, and so on. Later in 2004, Alex Biryukov et al. performed a security evaluation of ARIA in which they focused on dedicated linear cryptanalysis and truncated differential cryptanalysis, and found attacks on ARIA up to 7 rounds. Af-ter that, an impossible differential analysis of 6-round ARIA was proposed by Wenling Wuetal. in 2007[61].In 2008, Shenhua Li improved Wu's impossible differential attack[44]. In 2009, Yanjun Li proposed integral attacks on ARIA[45]. And Xuehai Tang et al. discoved some meet-in-the-middle attacks on ARIA up to 8 rounds in 2010[60].In this thesis, we provide some cryptanalysis on ARIA version 1.0, such as impos-sible differential cryptanalysis, meet-in-the-middle attack, etc. The results are listed as follows.(1) Impossible differential cryptanalysis of ARIA reduced to 7 roundsWenling Wu et al. first found the 4-round impossible differentials, which the designers didn't expect, and first proposed an 6-round impossible differential cryptanalysis of ARIA. The 4-round impossible differential used in their crypt-analysis can be expressed below: (c,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)(?)(0,j,0,0,0,0,0,0,j,j,j,0,0,0,j,0), where c and j are some nonzero values. In 2008, Shenhua Li found a new impossible differential property which can be used for attacking 6-round ARIA more effectively. When attack 6-round ARIA using the above property,10 bytes of round keys need to be guessed in-stead of 12 bytes in the previous one, because 1 byte from round 1 and 1 byte from round 7 are no longer needed. Therefore, the time complexity is reduced by 216 times.The 4-round impossible differential property in Li's attack can be described as (0,c1,0,0,0,0,0,0,0,0,0,0,c12,0,0,0)(?)(0,0,0,j,0,0,0,0,0,0,0,j,j,j,0,0), where c1,c12 and j are some nonzero values.Li's attack needs 2120 chosen plaintexts and 296 encryptions.Based on all the above results, we do some research on the impossible dif-ferential property of ARIA. We notice that it's nearly impossible to reduce the byte number of guessed key. So we have to dig in from a different direction. We discover an important property of diffusion layer (DL), and combined with our new corresponding 4-round impossible differential property, we propose our 7-round ARIA-256 impossible differential attack.Important Property of DL.Since the DL transformation is linear, and DL=DL-1,we find out that there are 4 equations about the bytes of state before DL. And using these 4 equations, we are able to filter useless plaintext pairs in advance and reduced the time complexity massively.The 4 equations are:Letting the bytes of state?X1(SL) satisfy 4 equations, we can filter the plaintext pairs by probability 2-48. We also construct a 4-round impossible differential property corresponding to the 4 equations, as below:4-Round Impossible Differential PropertyGiven a pair of X3 which is equal in all bytes except the 3rd byte, then after 4 rounds encryption the ciphertext differences?X7 can't be like this (j,0,j,0,0,0,0,0,j,0,0,j,0,0,0,0), i.e., the ciphertext pair has nonzero equal difference at bytes (0,2,8,11), and no difference at the other bytes. We expressed the property as: (0,0,c,0,0,0,0,0,0,0,0,0,0,0,0,0)(?)(j,0,j,0,0,0,0,0,j,0,0,j,0,0,0,0) where c and j denote arbitrary nonzero values. We present an impossible differential cryptanalysis of ARIA-256 reduced to 7 rounds, using the 4-round impossible differential property, with additional two rounds at the beginning and one round at the end. Our attack needs 2125 chosen plaintexts and 2²³⁸7-round encryptions.(2) Improved impossible differential cryptanalysis of 7-round ARIA-256 On the basis of the above research, we do some further study on the impos-sible differential property. And we find some similar properties of DL. Only this time, we obtain 7 equations, which are used for establishing our 7 round attack. The seven equations are: We also find a 4-round impossible differential property corresponding to these 7 equations, and propose our improved cryptanalysis, with additional two rounds at the beginning and one round at the end. We describe the 4-round impossible differential property as below:4-Round Impossible Differential PropertyGiven a pair of plaintexts (X3, X'3) which is equal in all bytes except bytes (10,15), then after four rounds encryption the ciphertext differences?X7 can't be like this (0,j,0,j,0,0,0,0,0,j,j,0,0,0,0,0), i.e., the ciphertext pair has nonzero equal difference at bytes (1,3,9,10), and no differences at the other bytes. We expressed the property like this: (0,0,0,0,0,0,0,0,0,c,0,0,0,0,0,c)(?) (0,j,0,j,0,0,0,0,0,j,j,0,0,0,0,0) where c and j denote arbitrary nonzero values.(3) Meet-in-the-middle attacks on ARIAThe meet-in-the-middle attack was first developed as an attack on an at-tempted expansion of a block cipher by Diffie and Hellman in 1977[21]. It's useful to attack block ciphers like IDEA[17], AES[18,19,24], etc. Because of the similar structure property to AES, reduced-round ARIA is also vulnerable to this attack.The meet-in-the-middle attack on ARIA was first introduced by Xuehai Tang et al.[60], and they can attack up to 8 round ARIA-256. The data com-plexity of their 8-round attack was 2⁵⁶, the time complexity was 2^251.6, and the precomputing complexity was 2²52. And their 7-round attack needed 2120 cho-sen plaintexts,2^185.3 7-round ARIR-192 encryptions, and 2187 precomputations. The data/time/precomputing complexity of their 6-round attack were 2⁵⁶,2^121.5, 2^122.5 respectively. And their 5-round attack required 25 plaintext,2^65.45-round encryptions, and 2^122.5 precomputations.Based on these results, we establish our improved 4-round/3-round distin-guishers, inspired by the work of Orr Dunkelman, Nathan Keller, and Adi Shamir about the meet-in-the-middle attacks on AES[24] in 2010. We propose our new meet-in-the-middle attacks using these improved distinguishers, and improve the recent work of Tang up to eight rounds.4-Round Distinguisher of ARIAIf the active byte of?-set?X02,X12,...,X2552} is byte 2, encrypt this 5-set through 4-round ARIA. Then the (un-ordered) multiset [?AX06.2,?AX16.2,...,?AX2556.2] is fully determined by the following 30 byte parameters:-Seven bytes 1,4,6,10,11,12,15 of the state X03(IN).-The full 16-byte state X04(IN).-Seven bytes 1,4,6,10,11,12,15 of the subkey k5. Therefore, the multiset is totally determined by 232-bit parameters. This multiset assumes 2232 values. So if the key guess made the corresponding multiset assume one of the above 2232 values, it's highly likely that the key is the right key.We propose our 8-round attack by adding one round before and three rounds after the 4-round distinguisher.Our 8-round attack needs 256 chosen plaintexts,2248.58-round ARIR-256 encryptions, and 2238 precomputations. The data/time/precomputing complexity of our 7-round attack are 2112,2176.7,2182.2. We also reduce the precomputation of 6-round attack from 2122.5 to 2110.5. And we balance the complexities of data/ time/precomputation of 5-round attack to 228.5,285.7,285.7 repectively. Our result is the best one on ARIA as far as we know to date.