Cryptanalysis Of CBC-MAC And Hash Function Related Algorithms

Hash function plays a fundamental role in modern cryptology applied in a wide variety of cryptographic applications, including digital signatures, key derivation, hash-based message authentication codes and deterministic random bit generators etc. Be-sides, hash function can be used to construct block cipher, and usually be modelized as the random oracle in the security proof of cryptographic schemes. Message Au-thentication Code (MAC), also called the keyed hash function, is one of the three sym-metric cryptography algorithms. MAC is widely used in the computer network and e-commerce to provide the integrity and original authentication, of which CBC-MAC is a standard algorithm. In 2005, Wang et al. proposed the modular difference method to break most of the MD based hash function, such as MD4, MD5, RIPEMD, SHA-0 and SHA-1 etc. That causes a new upsurge in the study of hash functions. In response to the break of the widely used hash functions MD5 and SHA-1, NIST finished the eval-uation of the security status of the hash function in two years(2005-2006) and started the new hash function algorithm project(SHA-3) from 2007 to 2012. The design and cryptanalysis of hash functions become the focus in the field of modern cryptology.The breakthrough of the hash function improves the research of MAC, which in return leads to the request of new security properties for hash functions. The candidates of the SHA-3 present the achievements of hash function in the recent years and achieve high performance with some new design ideas. The security of MAC and hash func-tion algorithms should be guaranteed in terms of the structure and the iterative building blocks. Under the instructions of my supervisor, we present the new distinguishing and second preimage attacks on CBC-like MACs with birthday attack, considering the properties of CBC mode. Utilizing the properties of Luffa structure and general-ized birthday attack, we analyze the security of Luffa. Thorough to the basic building blocks, we introduce the method of constructing the meaningful collision on MD4 in plain text, and give the related key rectangle-like sandwich attack on SHACAL-2 based on hash function SHA-2.(1) Distinguishing and Second-Preimage Attacks on CBC-like MACsCBC-MAC is based on the block cipher in cipher block chaining(CBC) mode, which is the standards of many international organizations and institutes, such as ANSI X9.9, FIPS PUB 113 and ISO/IEC 9797 etc. CBC-MAC is the most widely used MAC in e-commerce.In 1995, Preneel and van Oorschot proposed a general method to distinguish an iterative MAC algorithm from a random function, which is based on an internal col-lision searched by the birthday attack. However, we note the collision-free property of the CBC-like MACs with only one-block as a variable. This follows from the fact that the built-in block cipher is a permutation. So we utilize the collision-free property to distinguish a block-cipher-based MAC including EMAC, XCBC, TMAC and OMAC from a random function.In 2009, Wang et al. proposed a new method to distinguish the internal near-collision with special differential characteristic by the birthday attack. They collect enough pairs to make the internal near-collision hold by birthday paradox, and recog-nize the internal near-collision by the special differential characteristic.Inspired by the above idea, we present the new second preimage attack on CBC-MAC. Our approach is to utilize the CBC structure, and turn the complexity of the second preimage attack into birthday attack complexity. More specifically, given a two-block message M1||M2, we want to create another messageM'1||M'2 with the same MAC, i.e., EK(M'1)(?)M'2=Ek(M1)(?)M2. From the CBC operation, we get EK(M1)(?) M'2= Ek(M'1)(?)M2. We are able to choose M'1, M'2 at random to get a collision-MACH(M1||M'2)=MACK(M'1||M2).To summarize some MAC constructions, we describe a general statement about the building blocks of MAC constructions, which results in the second preimage attack on more CBC-like MACs. Let gf1,f2:{0,1}b1×{0,1}b2→{0, 1}n, where b1,b2≥n,f1:{0,1}b1→{0,1}" and f2:{0,1}b2→{0,1}n are two maps, x∈{0,1}b1,y∈{0,1}b2 are independent. For notational simplicity, we write g for gf1,f2 hereafter. It is obvious that the function g is a XOR function, with simple exchange, we can use the birthday attack to get its second preimage.If a MAC algorithm C, such that where f is a permutation, g(x,y)=f1(x)(?)f2(y), x and y are independent (block) variables, mf is a concatenation of blocks. Then there exists an algorithm to get the second-preimage for any message of at least two blocks with birthday attack complex-ity.Our second-preimage attack on the CBC-MAC, which is an extension of the attack of Brincat and Mitchell[4]. The attack also covers MT-MAC, PMAC and MACs with three-key enciphered CBC mode.(2) Cryptanalysis of SHA-3 Candidate LuffaLuffa is a candidate of the second round of SHA-3[5], which provides good per-formance on high-end platforms. Luffa is based on sponge construction, which is indif-ferentiable from a random oracle when being used with a random transformation or a random permutation[6]. But the hash function based on sponge construction may have some weakness for the simple permutation. The ways of message input and hash value output for sponge variants are different from the original sponge construction. There are many candidates of SHA-3 based on sponge variants, and their security is worth of further research.In this thesis, we present the pseudo-collision, pseudo-second-preimage and pseudo-preimage attack on Luffa. Luffa is a variant of the sponge construction, and it uses a linear mixing function MI and w fixed 256-bit permutations in place of a sin-gle wider permutation. The function MI maps the 256-bit message and w 256-bit IV to a w 256-bit state, w=3,4,5 for Luffa-224/256, Luffa-384 and Luffa-512 respectively. Let the output difference of the MI is zero, the input difference of△H can be expressed by the difference of△M. Flipping 5 bits of IV for Luffa-256 is enough to get a pseudo-collision or pseudo-second-preimage. For Luffa-384, it needs to change 7 bits of IV to get a pseudo-collision or pseudo-second-preimage. And for Luffa-512, there is a 12-bit difference in the IV to get a pseudo-collision or pseudo-secong-preimage. This can be used to construct the related key attack for the corresponding MACs using the secret key as initial value.The pseudo-preimage of Luffa-256 can be computed easily by inverting the func-tion. However, the hash value of Luffa-384/512 is cascaded by the output of the blank iterate Z0||Z1. There are some difficulties to get the pseudo-preimage. With the proper-ties of Luffa and the extended generality birthday attack, we give the pesudo-preimage attack on Luffa-384/512. Take Luffa-512 as an example. Let (X0,X1,X2,X3,X4) be the output of MI, and the two equations can be deduced by the definition of Luffa, Since the equation(5) can be controlled, we can make a part of the equation hold with some fixed bits. The other part of the equation(5) and equation(6) can be satisfied with the other bits. We found 128 bits of the variables is enough to make the equation (5) and (6) hold together. Let l128(Xi)=CST, i=0,1,2,3, X4=CST(?)l128(0xf(?)Z0). The adversary can search the solution (X0,X1,X2,X3,X4) satisfying the following two equations by the extended generalized birthday attack. We need 264 iteration computations with 267 bytes memory to get the pseudo-preimage for Luffa-384.264 iteration computations with 267 bytes memory are necessary to get the pseudo-preimage for Luffa-512.(3) The Meaningful Collision Attack on MD4MD4 is designed by Rivest in 1990 for the 32-bit computer, which is very effi-cientt[7]. Dobbertin[8] gave a collision attack for the full MD4 in 1996, which could also be used to find meaningful collisions. In 2005, Wang proposed the modular dif-ferential method which is efficient to find collisions on the main hash functions for the MD4 family, including MD4[9], RIPEMD[9], MD5[10], SHA-0[11] and SHA-1[12] etc. Moreover the techniques can be applicable to explore the second-preimage of MD4[10]. Some papers explain how these concrete collisions can be used to obtain meaningful collisions of files with special formats:certificates[13], postscript documents[14], PDF, TIFF and MS Word 97 documents[15], etc. They produce meaningful collisions by inserting some random collisions in the controlling command of the documents (e.g. "if-then-else" in postscript documents). The two documents share the same hash value but display completely different contents. All these collision attacks will lead to a grave threat in practice. Although MD4 is broken, it may be still used in practice for its high performance. In addition it's very important to construct meaningful collisions in terms of the encoding of the character. It's much more complex to find the meaningful collisions than random collisions, as there are many restrictions on the message value. The character can be expressed in computers with a special number, which may be a single-byte or multi-bytes. Our analysis is based on the single-byte encoding.Using the modular difference method and message modification techniques, we study the meaningful collision for MD4 based on ASCII code. Combining the method of encoding, not all the collision paths are available to the meaningful collision based on ASCII code. Firstly, choosing the right difference is very important to construct meaningful collisions. If the difference contains±27,±215,±223,±231, one of M and M is unreadable. Secondly, it's vital for us to make a comprehensive view of all the conditions in the differential path. A message pair is more likely to become a collision when there are more sparse conditions. The path presented by Yu et al. [16] is fit for our cryptanalysis. The modular difference of the message is M=(m0,m1,…,m15), One of M and M'is unreadable when i=7,15,23,31 and there are more conditions when i=17,26. So, it is unnecessary to consider the differential paths, when i=±k,k=7,15,17,23,26,31.We analysis the relations between the conditions of the differential path and the message byte. When the message difference△-m4 is±20+8k and±22+8k,k=0,1,2,3, there is only one condition corresponding to the 8th bit of a byte. Otherwise, it has more conditions corresponding to the 8th bit of a byte. If a condition is refereed to the 8th bit of a byte, we have to use the basic message modification with bit-carry to make the condition hold. That has a low probability to make the word meaningful. Therefore, taking an example for△-m4=1, we show a construction of the sentence. In the sentence, we use some name, price and number, which has freedom degree to vary to make the condition on the first round hold. Then we determine the words from m0 to m15 by modifying the message with checking.1. Choose m0 tO m5 according to the message difference. The character with differ-ence may be number and letter.2. Choose remainder words m6 to m13 front-to-back with simple message modifica-tion and bit-carry method, check the sentence to avoid the unreadable characters, no sense of the words and incoherent sentences.3. Apply the word m14 and m15 to make the 38 conditions in round 2 and 3 hold. The conditions on a5,6,a5,18.a5.29.d5,6,d5,13, C5.13 and c5,18 can be fulfilled with high probability by advanced message modification technique to reduce the com-plexity of collision search.We present the method to make meaningful collisions on MD4 based on ASCII code with a probability 2-33,77, and give a complete meaningful collision on MD4 based on ISO Latin-1 character set. Based on our collision, we show an example of cheating. (4) Improved Related Key Attack on 44-Round SHACAL-2The block cipher SHACAL-2 is a selection of NESSIE, which is designed by Handschuh and Naccache. SHACAL-2 is based on the hash function SHA-256, which is one of the standards of NIST. SHACAL-2 has a 256-bit text and a 512-bit key as the input. The collision path of SHA-2 can be used to the differential path for the block cipher. Wagner introduced boomerang attack in 1999, which used two independent differential characteristics to attack by adaptive chosen plaintexts and ciphertexts. The attack is improved to chosen plaintext attack by Kelsey et al., called amplified boomerang attack(Biham et al. independently introduced as rectangle attack). The local collision of SHA-2 can be used for cryptanalysis of SHACAL-2. The rectangle attack in related key cases is related key rectangle attack. In 2008, Lu et al. presented a 35-round related key rectangle distinguisher with probability 2-460. With the distinguisher, they gave a key recovery attack on 44-round SHACAL-2[21]. In 2009, Wei et al. improved the probability to 16 times of Lu's. Dunkelman et al. introduced sandwich rectangle attack with a middle round attended between the two differential characteristics, which can improving some boomerang attack as its extension.We apply the related key rectangle-like sandwich attack to improve the related key attack on 44-round SHACAL-2 with 35-round related key rectangle-like sandwich distinguisher. The 35-round SHACAL-2 is partitioned into 3 parts E=E1 (?) EM (?) E0. Here E0 is the first 24 rounds (0-24), EM is the round 24-25, and E1 is the rounds 25-35. It is different from the former attack, we use the first 24 rounds as E0 instead of the first 25 rounds. Besides, we use the 25th round as a middle round EM.It is impossible to transform the output difference of the 25th round to the input difference of E1. But with the output difference of the 24th round, the transformation is easy. There is a collision on the 24th round, i.e., the output difference is zero. Because the round function of SHACAL-2 is an unbalanced Feistel structure, we need the updated values at 25th round to satisfy the input difference of E1. The probability for a quarter as a right quarter is 1 when the pair satisfying the input difference of E1 and the output difference of E0, for△A25=0 and△E25=0. With the combination of modular difference, XOR difference and the substituting single difference with more differences, we improve the probability of the differential path E1. The input and output differences of E0 both are XOR difference. The input difference of E1 is XOR difference, and output difference of E1 is modular subtraction difference. With the conditions of the differential path E1, we improve the key recovery attack. we present a 35-round related key rectangle-like sandwich distinguisher with probability 2-430. Applying the distinguisher, the key recovery attack on 44-round SHACAL-2 with related keys is improved, with 2217 chosen plaintexts,2476.92 44-round encryptions and 2222 bytes memory.