Distinguishing Attack On LPMAC Instantiated With Reduced SHA-1 And Partial Key Recovery Attack On SHA-0-MAC

With the advent of information age, information has become an important re-source for social development, which leads the development of the world. Information security plays a very important role in the information society, which is directly re-lated to national security, regularity of finance, commerce, public security, military, and government, as well as our daily life. With the rapid development of informa-tion industry, requirements on global information security improves, particularly, the rise of e-commerce makes message encryption, authentication and security protocol particularly important.Message Authentication Code (MAC) algorithm, accepts as input a secret key and an arbitrary-length message to be authenticated, and outputs a fixed-length MAC value. The MAC algorithm guarantees both data integrity and data origin authenticity, where the verifiers can detect who send the message and whether the message is tampered during the transformation. It is important in internet communication and is widely used in security protocols such as IPSec, SSL, SSH, SNMP, etc.There are 3 popular ways to construct MAC algorithms-based on block ci-phers, based on hash functions, or based on universal hash family. This article focuses on the security of hash-based MAC algorithms.Hash Function accepts as input an arbitrary length message, and outputs a fixed length string, which is called Message Digest, as well as Hash Value. Attacks on hash functions are Collision Attack, Preimage Attack and Second Preimage Attack, Length Extentsion Attack, etc.Modern collision-resistent hash function can provide data integrity protection, which is the key technology of digital signatures. It is used to construct pseudo-random number generator and message authentication code as well. A series of related hash functions have been developed, such as MD4, MD5, SHA-0, SHA-1 and the SHA-2 family, (which includes 224,256,384 and 512-bit variants); all of which follow the Merkle-Damgard construction. NIST(National Institute of Standards and Technology) began the standardization of the hash functions in 1993, with a specifi-cation of SHA-0 in the Federal Information Processing Standards Publication (FIPS PUBS) 180 as the Secure Hash Standard, subsequent revisions of the FIPS have re-placed SHA-0 with SHA-1 and added the SHA-2 family in FIPS 180-1 and FIPS 180-2, respectively. Recently, Xiaoyun Wang, et. al. had brought out a series of collision attacks on MD4, MD5, SHA-0 and SHA-1 algorithms, although there is no specific reason to believe that a practical attack on any of the SHA-2 family of hash functions is imminent, a successful collision attack on an algorithm in the SHA-2 fam-ily could have catastrophic effects for digital signatures. NIST has decided that it is prudent to develop a new hash algorithm to augment and revised FIPS 180-2. The new hash algorithm will be referred to as "SHA-3".A series of attacks on hash functions also affect the security of its related appli-cations. Cryptologists have found that these collision paths directly lead to differential attacks on MAC algorithms. The security of MAC algorithms based on hash functions become a research hotspot. There are three kinds of attacks on MACs as follows:Distinguishing Attack, including Distinguishing-R Attack which distin-guishes MAC algorithm from Random Functions, and Distinguishing-H Attack which distinguishes MAC algorithm based on specific cryptographic component from MAC algorithm based on random function.Forgery Attack, including Existential Forgery, Selective Forgery, and Univer-sal Forgery Attack. Key Recovery Attack, or Partial Key Recovery if only part of the key can be recovered, by this way the unrecovered key bits can be recovered by exhaustive search, and the complexity of the attack is lower than the ideal complexity. Under the guidance of our tutor, this thesis analyzes the security of MAC algo-rithms based on SHA-0 and SHA-1. The results are as follows:(1)Distinguishing attack on LPMAC instantiated with 63-step(8-70) SHA-1Based on the in-depth analysis of relations between disturbance vectors and the probability of the differential path of SHA-1, combined with the new distinguisher pro-posed by Xiaoyun Wang et. al on FSE 2009, we selected start point of the differen-tial path properly, and finally extend the distinguishing attack on LPMAC instantiated with 61-step SHA-1 to 63 steps(8-70). The complexity of this attack is 2157 queries, with the success rate 0.70.MACs can be recognized as keyed hash functions, so it is natural to use hash functions with secret keys to build MAC algorithm. The way to use secret keys can be Secret Prefix Method, Secret Surfix Method, and Envelope Method. The se-cret prefix method is to prepend the secret key k to the message before the hashing operation, and it is a basic design unit and commonly used. The original secret pre-fix MAC is defined as MACk(m)= H(k||m), but this is not secure because we have HIV(m1||m2)= HH(m1)(m2) when applied in iterated chaining hash structures such as Merkle-Damgard structure. Then if the adversary obtains the MAC value of the mes-sage m1, he is able to obtain the MAC value of the message m1||m2 without knowing the key. One suggestion to guarantee a secure secret prefix MAC is to prepend the message length to the message before hashing, MACk(m)-H(k||l|| padding||m), k||l||padding is a full message block. Where'l' denotes the length of the message, and'padding'de-notes the message padding. This kind of MAC algorithm is called LPMAC(Length Prefixed MAC).Wang et.al's distinguishing attack makes use of a 61-step SHA-1 differential path, trying to distinguish an inner near-collision occurring in the first round, precisely the 14th step, and distinguishes the MAC algorithm accordingly. As we know, in the col-lision path of SHA-1, the situation in the first round is the most complicated and the number of conditions are as maximum. By this method, the conditions on the first 14 steps can be ignored, and replaced with a collision, thereby the difficulty of the problem is reduced. Under the instructions of my tutor, we find this distinguishing attack can be extended to LPMAC instantiated with more steps, if we don't start from the first step of SHA-1, but from a certain step in round 1.First we research into collision attacks on SHA-1, based on the attacks on Se-cure Hash Functions (SHA-family) by Xiaoyun Wang, the collision of SHA-1 is made of certain partial collisions. There are two kinds of partial collisions:single partial collision and compound partial collision.Single partial collision refers to a pair of messages M, M', although the corre-sponding extended message blocks in the adjacent 6 steps are different, but the output value matches after computing the i-th step operation of H(M), H(M').Compound partial collision refers to multiple single partial collisions compound together, it's properties are different when occurs in different round of SHA-1. The probability of a single partial collision hold in the first round is 1/25, that is to say, 5 conditions are needed to guarantee the collision. For the second round, the number of conditions is 2, for the third round, the number of conditions is 4, and for the last round is 2. The situation on the compound partial collisions are slightly complicated, for example, in round 1,2 consecutive single partial collisions can not compose a com-pound partial collision, and the number of conditions needed to guarantee a compound partial collision is usually lower than the sum of number of conditions for the corre-sponding single partial collision under certain conditions; while for round 2 and round 4, the number of conditions to guarantee a compound partial collision equals sum of the number of conditions for the corresponding single partial collisions.Then, design a program to search for the appropriate Disturbance Vectors. We found that this distinguishing attack can be extended to further steps when we reduce the number of conditions in the 1st round, and avoid the situation which is unable to construct compound partial collisions, in the same time, the total number of conditions in the differential path should be at least. By setting different start value, we design programs according to message expansion of SHA-1, obtain a table of Disturbance Vectors with certain length, and choose a suitable one according to our analysis. In Wang's method, the total conditions after the 14th step should be less than 40, this restriction limits the choice of Disturbance Vectors. The Disturbance Vector we decide to use has the same start value with the one Wang et al. used, but shifted to different position. By this way, we can reach up to 63-step SHA-1, while the total number of conditions is 37. Once the near collision differential path is selected, according to Wang's method, the distinguishing attack can be applied to LPMAC instantiated with 63-step SHA-1, while the complexity of the attack is 2157 queries, and success rate is 0.70.(2)Distinguishing attack on LPMAC instantiated with 65-step(12-76) SHA-1On further analysis of the differential path of SHA-1, we find it is possible to construct a new distinguisher by making use of a single differential path instead of the doubled differential path. In this way, we can surpass the restriction of 40 conditions, and extend it to 80, so that the distinguishing attack on LPMAC instantiated with re-duced SHA-1 can be extended from 63 steps to 65 steps(12-76), and the complexity of the new attack is reduced from 2157 quires to 280.9.Wang's method avoids the complicated situation that might happen in the first round effectively, but limits the total number of conditions, this attack can hardly be extended further, so we try to distinguish LPMAC instantiated with further steps of SHA-1 using different method. The first problem is to get rid of the limit of number of conditions, and we decide to try to use a single differential path, by this way, the number of conditions can reach up to no more than 80, and the complexity of the attack does not exceed 2160 queries. But we can not replace the conditions in the first round with an inner near collision by this way, thus we have to explore a new method to avoid the complicated situation in the first round. Our method is to explore a suitable differential path, which can avoid the situation that two single partial collisions can not make a compound partial collision, and the number of conditions in the first round as well as the third round should be at least, and try to reduce the number of conditions in the third round according to the characteristics in the third round. Since we get rid of 40-condition limit, the choice of Disturbance Vector is relatively more. The start value we select is (0x00000002,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), and adjust the position of it to meet the requirements. By this way, the pseudo near collision we selected can reach up to 65 steps (12-76) SHA-1, while the number of conditions is 78. Based on this differential path, we construct our distinguisher.For messages with 2 blocks, according to Birthday Paradox, we first guarantee the local collision happens after the first iteration, then choose a proper second block to identify the specific collision, and finally apply the selected near collision path to com-plete out distinguisher to distinguish LPMAC instantiated with 65-step SHA-1 with LPMAC instantiated with random function. The idea of our distinguisher is as follows:1. Select enough one block messeges x, and concatenate one block message y to each x, query all MAC values of x||y.2. Apply birthday attack to search all the collision pairs (x||y, x'||y) which satisfy LPMAC(x||y)= LPMAC(x'||y). Then the collision might happen after the first itera-tion, or the second iteration, where we refer the former one to internal collision, and the latter one external collision.3. We filter out all external collisions, and for each internal collision, we concate-nate 278 message pairs which satisfy the selected near collision differential path.4. Query all (x||y1, x'||y2) and see if we can find a collision pair satisfies the chosen collision path, if we can find such a pair, then the LPMAC has a high probability to be instantiated with 65-step SHA-1, otherwise, the LPMAC should be instantiated with random function.We apply this attack on LPMAC instantiated with 65-step (12-76) SHA-1, the complexity of our attack is 280.9 queries, with success rate 0.51.(3)Partial key recovery attack on SHA-0-MACCombined with Contini et. al's partial key recovery attack on HMAC-MD5 and Wang et. al's key recovery attack on MD5-MAC, by making use of existed SHA-0 pseudo collision differential path and deducing the necessary and sufficient conditions that the differential path holds, we bring out the first partial key recovery attack on SHA-0-MAC. Subkey K0 and 128 bits out of the 160-bit subkey K1 can be recovered with the complexity of 2125.58 quires. MDx-MAC is another kind of MAC construction proposed by Preneel and Oorschot in Crypto'95, which converts MDx-family hash functions into MAC algo-rithms. The underlying hash function can be any of MD5, RIPEMD, SHA, or sim-ilar algorithms (MD4 is omitted). The secret key k was transformed into 3 subkey K0,K1, K2, where K0 and K2 are used similar with envelope method, and K1 is split into four 32-bit words which is added to the constants used in each round of the under-lying hash function. We refer MDx-MAC instantiated with SHA-0 as SHA-0-MAC. Under the suggestion of our tutor, we analyze the security of SHA-0-MAC, and present a partial key recovery attack on SHA-0-MAC.In order to deploy this attack, first we need to search for a kind of special pseudo collision. Pseudo collision is a special kind of collision with the format: H(IV,M)= H(IV',M'). M refers to message, and IV is the initial value, where IV≠IV. We have analyzed several differential path and found the best one which holds with high probability 2-64 just as had shown. We deduce the sufficient con-ditions of the differential path, and based on this differential path, then we apply our attack using similar method with MD5-MAC key recovery attack. First we make use of birthday attack to search for collisions, and identify the collisions which satisfy differential path, then we can apply partial key recovery attack on SHA-0-MAC.The secret keys K0, K1 and K2 of SHA-0-MAC appear at IV, each iteration, and the end of the message. Because the middle key K1 takes part in the intermediate iter-ation, we can recover some bits of K1 by verifying the relationship between intermedi-ate variable and subkey K1 . First we need to recover some bits of intermediate states, since there is no rotation associated with the message word in SHA-0, we can use the bit flipping algorithm directly to recover the register a_i. Then we recover subkey K1 by recovering 4 parts of it K1[0], K1 [1], K1[2],K1 [3] separately, and the complexity of this attack is mainly dominated by searching for collisions which satisfy special differential path.Finally, since for SHA-0-MAC, subkey K0 is used as IV, and we have already re-covered K1, we can choose another differential path, and recover K0 directly by making use of the method given in's section 6.2. The complexity of this attack is 284 queries and 260 SHA-0 compression function computations.