Font Size: a A A

Cryptanalysis Of Hash Function And Block Ciphers

Posted on:2009-05-01Degree:DoctorType:Dissertation
Country:ChinaCandidate:G L WangFull Text:PDF
GTID:1118360245494141Subject:Information security
Abstract/Summary:PDF Full Text Request
Hash functions and block ciphers play an important role in many cryptographic and security protocols. Hash functions have been designed in the first place to protect the authenticity of information. When efficient and secure hash functions became available, it was realized that under "random" assumptions (there is no correlation between input and output bits, no correlation between output bits, etc.) they can be used for many other applications such as: protection of pass-phrase, construction of efficient digital signature schemes, building blocks in practical protocols including entity authentication protocols, key distribution protocols, and bit commitment, construction of encryption algorithms. Block ciphers are used to conceal confidential information, not only during its broadcast over a public channel, but also when it is stored. The security of these protocols and storing procedures relies on the security of the underlying block ciphers against various attacks. The field of cryptanalysis of block ciphers focuses on assessing the security of block ciphers. The process of assessment of the security of a given block cipher is mostly concerned with applying various cryptanalytic techniques to the block cipher. Each of these techniques has a different attack model and aims at exploiting different design flaws.There are many methods to construt hash functions. In 1991, Rivest presented the first dedicated hash function MD4 [8]. In the following more than ten years, according to the design ideas of MD4, many dedicated hash functions are introduced: MD5 [13], HAVAL [14], SHA-0 [16], RIPEMD [15], SHA-1 [23], RIPEMD-128 [26], RIPEMD-160 [26], SHA-2 [36]. MD5 and SHA-1 are the most popular hash functions. RIPEMD was devised in the framework of the EU project RIPE [15]. In 1996, H. Dobbertin, A. Bosselaers and B. Preneel proposed the hash function RIPEMD-128 instand of RIPEMD. It includes two parallel and independent operations which are called Linel and Line2 respectively. Each operation has four rounds (64 steps) and every round use different round functions. Furthermore, the order of message words are different in the two operations.Along with the MD4 family hash functions are widely used in many fields, more and more analytic results of the security of the hash functions are proposed, among which the most important problem is searching the collision, i.e., to find two different messages which have the same hash values. In 1996, H. Dobbertin gave a collision attack of MD4 [24], the computational complexity of which is 222 MD4 computations. In 1996, H. Dobbertin proposed a collision of MD5 under another initial value [25]. In 1997, H. Dobbertin found the collision of the first two rounds of RIPEMD [28]. In 1998, H. Dobbertin proved that two rounds MD4 algorithm is not one-way [31]. B. den Boer [20], A. Bosselaers [20] and F. Chabaud [32], A. Joux [32, 44] presented the attack results on MD5 and SHA-0 respectively.In 1997, X. Y. Wang proposed the bit tracing method [29], which is also called the modular method in Eurocrypt'05 [51, 52]. In the rump session of Crypto'04 Wang proposed the collisions of MD4, MD5, RIPEMD and HAVAL-128 [43]. The modular method is the theoretic foundation to attack the MD4 family hash functions. By using the modular method, most MD4 family hash functions have been broken: MD4 [51], MD5 [52], RIPEMD [51], HAVAL-128 [53, 54], SHA-0 [48] and SHA-1 [49], and the computational complexities to find the collisions of MD4 and RIPEMD are about 28 and 218 hash computations respectively. The modular method can be used to search the second-preimage of hash functions [50], and to attack HMAC and NMAC(forgery attack and key recovery attak) [55].With the broken of some MD4 family hash functions, the analysis of the block ciphers based on the hash functions becomes a hot topic. SHACAL-1 [35] is a 160-bit block cipher based on the hash function SHA-1. It was submitted to the NESSIE (New European Schemes for Signatures, Integrity, an Encryption) project and was accepted as a finalist for the second phase of evaluation. The previous analysis of SHACAL-1 can be referred to [38, 59, 41, 45, 46, 57]. [57] presented a related-key rectangle attack on the full SHACAL-1 with the data complexity of 2159.8 (2153.8) chosen plaintexts, and time complexity of 2420.0 (2501.2, respectively) SHACAL-1 encryptions. The attack is applicable to one out of 214 keys. SHACAL-2 [39] is a 256-bit block cipher based on the hash function SHA-2. It was submitted to the NESSIE project and was recommended as one of the NESSIE projection selections. The previous analysis of SHACAL-2 can be referred to [40, 42, 58]. As far as the round concerned, the best published attack on SHACAL-2 is in [58], which presented a related-key rectangle attack on 42-round SHACAL-2 with the data complexity of 2243.38 chosen plaintexts, and the time complexity of 2488.37. The block ciphers SHACAL-1 and SHACAL-2 are based on SHA-1 and SHA-2 respectively. Finding the characteristics with high probability plays a crucial role in the process of attacking SHACAL-1 and SHACAL-2, and finding the "good" characteristics relies on the properties of hash functions SHA-1 and SHA-2. The contents of the thesis includes three parts.1. Cryptanalysis of the first 2-round reduced RIPEMD-128In chapter 4, by using the modular method, we propose a collision attack on the first 2-round of RIPEMD-128 which has a computational complexity of 228. This is the best published analytic result for RIPEMD-128. It is very difficult to attack RIPEMD-128. Since the publication of RIPEMD-128, there is no any published papers to analyze the full algorithm. Even for the first n (n< 64) steps reduced RIPEMD-128, there is also no any other published analytic result. The only published analysis of RIPEMD-128 is in [60], and it gave a collision attack on the last three rounds of RIPEMD-128 with the probability of 2-55. We propose the collision attack on the first 2-round RIPEMD-128 for the first time.Considering the specialties of RIPEMD-128, by searching the near-collision characteristics of the first 2-round Linel and Line2, we give a collision attack of the first 2-round reduced RIPEMD-128. The modular differential attack search the collision of the first 2-round reduced RIPEMD-128 in the following four parts:Denote the first 2-round reduced RIPEMD-128 by H32. For any message M, denote the hash value after H32 by H32 (M). Because the initial value of RIPEMD-128 can't meet the requirements of the initial value of the near-collision characteristics of the first 2-round Line1 and Line2, so we find a message M0 such that the outputs of H32 (M0) meet the above requirements. Thereby, the near-collision contains two message blocks (M0||M,M0||M').After analyzing the properties of the round functions in RIPEMD-128, the order of the message words in Linel and Line2, and taking into account the message modification, we select the difference between two messages AM = M' - M as follows : M = (m0, m1,...,m15), here AM = (0,..., 0,224,0). Find two near-collision differential characteristics respectively for the first 2-round Linel and Line2 operations . If M and M' satisfy the near-collision differential characteristic of the first 2-round Linel, and also satisfy the near-collision differential characteristic of the first 2-round Line2, then, after the combination of the algorithm, we get a collision (M0||M, M0||M') of H32. The differential characteristics for the first 2-round Linel and Line2 operations can be found in Table 3 and Table 4 respectively. The output differences of H32 are:△a =△cc +△ddd = 0,△d =△bb +△ccc = 0,△c =△aa +△bbb = 0,△b =△dd +△aaa = 231 + 231(mod232) = 0.Derive two sets of sufficient conditions which ensure the near-collision differentials hold. There are only 21 sufficient conditions in total that ensure the near-collision of the first 2-round Linel hold, which is very helpful for the attack. The sufficient conditions are shown in Table 5 and Table 6.Modify the message to fulfill most of the variable conditions. For any random message M, we use basic modification (single-step modification) to decrease the conditions in the first round and use the advanced modification (multi-step modification ) to decrease other conditions.One of the difficulties of the attack is to select proper message difference: because RIPEMD-128 contains two parallel and independent operations, and the round functions and the order of message words both are different in Linel and Line2, so it is crucial and hard to select proper message difference in order to search the colli- sion characteristic with high probability. The other difficulty of the attack is message modification: because the order of message words are different in Line1 and Line2, changing one of the message words only leads to implement the message modification for one of the two operations Line1 and Line2. It's very hard to implement the message modification to both Line1 and Line2 simultaneously by changing one message word. It's much worse that after implementing the message modification to one of the two operations (e.g. Line1), the characteristic of the other operation (Line2) maybe be destroyed.2. Cryptanalysis of SHACAL-1In Chapter 5, illuminated by the technique of searching local collision in the modular method, we find some flaws of all the previous analysis of SHACAL-1. In [57], the related-key differential holds only if the key satisfies some conditions, so these flaws prevent the attacks from being applicable to all keys. In [46], the attack is impossible because the differentials which are used in the attack can not hold. In [57], there are some wrong keys which suggest the same number of "right" pairs/quartets as the right key. We show that the same pairs suggest even wrong keys.We present an improved related-key rectangle attack on the full SHACAL-1, which is applicable to one out of 256 keys (rather than one out of 214 for the previously best result). The new attack uses 2146 chosen plaintexts (or 2144 chosen plaintexts) and has a time complexity of 2465 SHACAL-1 encryptions (or 2494 SHACAL-1 encryptions, respectively). The memory requirements are about 2150.33 memory bytes. We first propose a 66-round related-key rectangle distinguisher based on the differentials in Table 7 and Table 8. The input difference for the first distinguisher isα= ([-8,1], [3], [3, -20], [16,31], 213 - 210 - 26), and the output difference isβ= (e10,0,e5,e30,0,0) under key difference△K* with probability 2-35. The input difference for the second distinguisher isγ= (e1, e1, 0, e30,31, e31), and the output difference isδ= (0, e3,0,0, e0) under key difference△K' with probability 2-36. The second differential defines a weak key class which contains one out of 28 keys, for these weak keys, the probability of the second differential is increased to 2-28(= 2-36·28). The probability of the first three rounds of the first differential can be increased by a factor of 29 by fixing the equivalent of 9 plaintext bits (presented in Table 5.5) in each of the plaintexts of the pair, and after the increase the probability of the first differential is 2-35.3. Cryptanalysis of SHACAL-2In Chapter 6, we find new differential characteristic and some properties of the algorithm, and present an improved related-key rectangle attack on SHACAL-2 with 2240.38 related-key chosen plaintexts and 2480.4 43-round SHACAL-2 encryptions. The memory requirements are about 2245.38 memory bytes. We use the differential characteristics based on [58], and our differential in Step 0 is(0, eM, e31, 0,e9,13,19, e18,29,e31,△i,j)→(0,0, eM, e31,0,e9,13,19, e18,29, e31)where g1(E0⊕e9,13,19) - g1(E0) +△i,j = 0. The probability of Step 0 will be 1 if we fix some bits conditions presented in Table 6.2. Since D2 = B0, H2 = F0, according to the encryption algorithm, the probability of Step 2 will be increased up to 2-10 by the conditions B0,i = F0,i(i = 18,29). From [58] we know that the probability from Step 2 to Step 24 is 2-37, so the probability of our first differential characteristic is 2-46. As stated in [58], the second differential characteristic is 2-63.38. So the 35-round related-key rectangle distinguisher holds with probability 2-474.76. The success rate of this attack (i.e., the probability that the number of remaining quartets for the right key pair is at least 6) is about 0.8 by the Poisson distribution X - Poi(λ= 8), PrX[X> 5]≈0.8.
Keywords/Search Tags:hash function, block cipher, collision attack, modular differential attack, related-key rectangle attack
PDF Full Text Request
Related items