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 passphrase, 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], SHA0 [16], RIPEMD [15], SHA1 [23], RIPEMD128 [26], RIPEMD160 [26], SHA2 [36]. MD5 and SHA1 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 RIPEMD128 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 2^{22} 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 oneway [31]. B. den Boer [20], A. Bosselaers [20] and F. Chabaud [32], A. Joux [32, 44] presented the attack results on MD5 and SHA0 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 HAVAL128 [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], HAVAL128 [53, 54], SHA0 [48] and SHA1 [49], and the computational complexities to find the collisions of MD4 and RIPEMD are about 28 and 2^{18} hash computations respectively. The modular method can be used to search the secondpreimage 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. SHACAL1 [35] is a 160bit block cipher based on the hash function SHA1. 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 SHACAL1 can be referred to [38, 59, 41, 45, 46, 57]. [57] presented a relatedkey rectangle attack on the full SHACAL1 with the data complexity of 2^{159.8} (2^{153.8}) chosen plaintexts, and time complexity of 2^{420.0} (2^{501.2}, respectively) SHACAL1 encryptions. The attack is applicable to one out of 2^{14} keys. SHACAL2 [39] is a 256bit block cipher based on the hash function SHA2. It was submitted to the NESSIE project and was recommended as one of the NESSIE projection selections. The previous analysis of SHACAL2 can be referred to [40, 42, 58]. As far as the round concerned, the best published attack on SHACAL2 is in [58], which presented a relatedkey rectangle attack on 42round SHACAL2 with the data complexity of 2^{243.38} chosen plaintexts, and the time complexity of 2^{488.37}. The block ciphers SHACAL1 and SHACAL2 are based on SHA1 and SHA2 respectively. Finding the characteristics with high probability plays a crucial role in the process of attacking SHACAL1 and SHACAL2, and finding the "good" characteristics relies on the properties of hash functions SHA1 and SHA2. The contents of the thesis includes three parts.1. Cryptanalysis of the first 2round reduced RIPEMD128In chapter 4, by using the modular method, we propose a collision attack on the first 2round of RIPEMD128 which has a computational complexity of 2^{28}. This is the best published analytic result for RIPEMD128. It is very difficult to attack RIPEMD128. Since the publication of RIPEMD128, there is no any published papers to analyze the full algorithm. Even for the first n (n< 64) steps reduced RIPEMD128, there is also no any other published analytic result. The only published analysis of RIPEMD128 is in [60], and it gave a collision attack on the last three rounds of RIPEMD128 with the probability of 2^{55}. We propose the collision attack on the first 2round RIPEMD128 for the first time.Considering the specialties of RIPEMD128, by searching the nearcollision characteristics of the first 2round Linel and Line2, we give a collision attack of the first 2round reduced RIPEMD128. The modular differential attack search the collision of the first 2round reduced RIPEMD128 in the following four parts:Denote the first 2round reduced RIPEMD128 by H_{32}. For any message M, denote the hash value after H_{32} by H_{32} (M). Because the initial value of RIPEMD128 can't meet the requirements of the initial value of the nearcollision characteristics of the first 2round Line1 and Line2, so we find a message M_{0} such that the outputs of H_{32} (M_{0}) meet the above requirements. Thereby, the nearcollision contains two message blocks (M_{0}M,M_{0}M').After analyzing the properties of the round functions in RIPEMD128, 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 = (m_{0}, m_{1},...,m_{15}), here AM = (0,..., 0,2^{24},0). Find two nearcollision differential characteristics respectively for the first 2round Linel and Line2 operations . If M and M' satisfy the nearcollision differential characteristic of the first 2round Linel, and also satisfy the nearcollision differential characteristic of the first 2round Line2, then, after the combination of the algorithm, we get a collision (M_{0}M, M_{0}M') of H_{32}. The differential characteristics for the first 2round Linel and Line2 operations can be found in Table 3 and Table 4 respectively. The output differences of H_{32} are:â–³a =â–³cc +â–³ddd = 0,â–³d =â–³bb +â–³ccc = 0,â–³c =â–³aa +â–³bbb = 0,â–³b =â–³dd +â–³aaa = 2^{31} + 2^{31}(mod2^{32}) = 0.Derive two sets of sufficient conditions which ensure the nearcollision differentials hold. There are only 21 sufficient conditions in total that ensure the nearcollision of the first 2round 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 (singlestep modification) to decrease the conditions in the first round and use the advanced modification (multistep modification ) to decrease other conditions.One of the difficulties of the attack is to select proper message difference: because RIPEMD128 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 SHACAL1In Chapter 5, illuminated by the technique of searching local collision in the modular method, we find some flaws of all the previous analysis of SHACAL1. In [57], the relatedkey 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 relatedkey rectangle attack on the full SHACAL1, which is applicable to one out of 256 keys (rather than one out of 2^{14} for the previously best result). The new attack uses 2^{146} chosen plaintexts (or 2^{144} chosen plaintexts) and has a time complexity of 2^{465} SHACAL1 encryptions (or 2^{494} SHACAL1 encryptions, respectively). The memory requirements are about 2^{150.33} memory bytes. We first propose a 66round relatedkey 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], 2^{13}  2^{10}  2^{6}), and the output difference isÎ²= (e_{10,0},e_{5},e_{30},0,0) under key differenceâ–³K^{*} with probability 2^{35}. The input difference for the second distinguisher isÎ³= (e_{1}, e_{1}, 0, e_{30,31}, e_{31}), and the output difference isÎ´= (0, e_{3},0,0, e_{0}) under key differenceâ–³K' with probability 2^{36}. The second differential defines a weak key class which contains one out of 2^{8} keys, for these weak keys, the probability of the second differential is increased to 2^{28}(= 2^{36}Â·2^{8}). The probability of the first three rounds of the first differential can be increased by a factor of 2^{9} 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 SHACAL2In Chapter 6, we find new differential characteristic and some properties of the algorithm, and present an improved relatedkey rectangle attack on SHACAL2 with 2^{240.38} relatedkey chosen plaintexts and 2^{480.4} 43round SHACAL2 encryptions. The memory requirements are about 2^{245.38} memory bytes. We use the differential characteristics based on [58], and our differential in Step 0 is(0, e_{M}, e_{31}, 0,e_{9,13,19}, e_{18,29},e_{31},â–³_{i,j})â†’(0,0, e_{M}, e_{31},0,e_{9,13,19}, e_{18,29}, e_{31})where g_{1}(E^{0}âŠ•e_{9,13,19})  g_{1}(E^{0}) +â–³_{i,j} = 0. The probability of Step 0 will be 1 if we fix some bits conditions presented in Table 6.2. Since D^{2} = B^{0}, H^{2} = F^{0}, according to the encryption algorithm, the probability of Step 2 will be increased up to 2^{10} by the conditions B_{0,i} = F_{0,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 35round relatedkey 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), Pr_{X}[X> 5]â‰ˆ0.8.
