On The Security Of Hash Functions And Their Applications

Hashfunction, mappinginput message with arbitrary lengthsto fixed lengthsoutput,is a one-way cryptographic primitive. Hash functions are mainly used to generate digitalfingerprint, and widely applied in the area of Random Number Generation (RNG), mes-sage integrity check, password shadow, challenge-and-response, Message AuthenticationCode (MAC), digital signature, digital certification, et al.This paper focuses on the security of MD5family of iterated hash functions, and thesecurity of their some applications, such as challenge-and-response, Message Authenti-cation Code (MAC). We propose the most efficient collision attack against MD5using asystematic differential cryptanalysis, and then we discuss how to use collision attack tobreak practical systems in use such as Authentication Post Office Protocol (APOP). Wealso analyze how to use the general attack of Merkle-Damg rd construction hash functionto break Challenge and Handshake Authentication Protocol (CHAP) like challenge andresponse protocol; finally, we show how to use extension attack and birthday attack withtwo groups to break H2-MAC, which is provable secure.WeproposeamethodhowtochoosetheoptimalinputdifferenceforgeneratingMD5collisionpairs. First,wedividethesufficientconditionsintotwoclasses: strongconditionand weak condition, according to the degree of difficulty for condition satisfactory. Sec-ond, we prove that there exist strong conditions in only24steps (one and a half rounds)under specific conditions, by utilizing the weaknesses of compression functions of MD5,which are difference inheriting and message expanding. Third, there exists no differencescaling after state word q25for the least number of strong conditions for each differentialpath, so we deduce the distribution of strong conditions for each input difference pattern.Finally, we choose the input difference with the least strong conditions and the most freemessage words. We further apply the divide-and-conquer strategy to cut the MD5colli-sionsearchingintostages,tomakesuretherelationsofeachstage’scomplexityisadditioninstead of multiplication. We also propose a named group satisfaction scheme—to deter-minately satisfy the strong conditions of the first three steps of the last tunnel under thedivide-and-conquer strategy and randomly satisfy other strong conditions using the restof the free bits of the tunnel, to greatly reduce the complexity of MD5collision searching.Hence, we should construct differential paths with most free bits to support the divide- and-conquer strategy and tunnel technique. Applying the above methods, we implementthe most efficient MD5collision attack, which only needs about218MD5compressionsto find a collision pair. These methods are also applicable to other hash functions withMD (Merkle-Damg rd) construction.We propose two new tunnels q′1and q1to generate MD5collision pairs with320and352fixed bits, respectively, to control more input messages of collision pairs. Wecan freely set the contents of m5to m15, and then modify m0to m4to generate collisionpairs fast, by using q1tunnel. Combined with divide-and-conquer strategy and groupsatisfaction scheme, we can greatly reduce the complexity of MD5collision searchingwith plenty of fixed bits. APOP hashes the secret password in the form of MD5(C P),andthesimplifiedDigestAccessAuthenticationprotocol(DAA)appliesthehashfunctionin the form of MD5(MD5(C P)), whereC is a challenge and P is the shared key betweena user and the authentication server. In an ordinary personal computer (PC) with2G CPU,the average time to generate the MD5collision pairs for recovering the first11charactersof APOP is about0.08second. We can recover the contents of the password as longas11characters in a minute, by implementing the “slice-by-slice” key recovery attack toAPOPinlocalPC.SuchresultsfurtherconfirmthatthesecurityofAPOPiscompromised.Since the outer application of hashing can not hide the collision of the inner hashing, the“slice-by-slice”attackisalsoapplicabletoDAA.Afterabout8084on-linequeriesand235off-line hash computations, the passwords with48characters of DAA can be recovered.Therefore, the security of DAA is also destroyed. We discuss the security of R H(C P)with secret suffix approach, where H is an arbitrary hash function with MD construction.Weprovethateventhesecretkeyisaslongasthelengthofhashresultof H,thesecurityofR istotallydependentonthecollisionresistanceoftheunderlyinghashfunction H,insteadof the strength of the used key, from the aspect of “slice-by-slice” key recovery attack.To resist the “slice-by-slice” attack, we propose a message alignment scheme, which willnot modify the underlying hash function, to guarantee that the whole password residesexactly on the last block, hence the key can not be cut into any slice and the security ofH(C P) isstrengthened, eventually. Applyingthemessagealignmentscheme, anattackerhas to do brute force attack against the key of H(C pad(x)P), even if the underlying hashfunction is not collision resistant.Since there exists a security hole in the padding procedure of MD construction hash functions, we propose a fast password crack method for the known length passwords tobreak CHAP, which is on behalf of the secret prefix approach systems instantiated withMD construction hash functions. We first recover the password length through on-linequery, and then we use probabilistic context-free grammar to crack the passwords off-line. Combined with server compromised impersonation attack and extension attack ofthe MD construction hash functions, the password length in the secret prefix approachH(P C) can be recovered, where P is the password and C is the challenge. The attackersends a challenge C and gets the response R. If the guess of the password length l is cor-rect, and the padding bits of P C is pad0, then for an arbitrary message r, the equationH(P C pad0r) h(R r pad1) always holds, by the extension attack principle. For apassword with l characters, the attacker should send l1on-line queries. Combiningwith the known password length and the probabilistic context-free grammar, we imple-ment a fast password cracking for the known length passwords. First, we collect the basestructures of the fixed length passwords and their corresponding probabilities from pub-licly disclosed password lists (the training sets). Second, based on these base structuresand their corresponding probabilities, we automatically create a group of probabilisticcontext-free grammars, each grammar is based on fixed length passwords. Finally, basedon the known challenge C, response R, the recovered password length l and a chosen dic-tionary file, we use probabilistic context-free grammar to generate word-mangling rulesin the highest probability order to greatly improve the password cracking.Combining with the general extension attack of iterated hash functions and the birth-day attack with two groups, we propose a general and efficient method to recover theequivalent key of H2-MAC, which is suitable to all kinds of H2-MAC instantiated withany MD construction hash function. H2-MAC, a variant of HMAC without the outer key,is designed to remedy the drawback of key management of HMAC and achieve more ef-ficiency. H2-MAC is provable secure as HMAC. Suppose that the secret key of H2-MACis K, we store r different n-bit (without padding bits) messages x and their correspondingH(x) values, whicharecomputedoff-line, ingroup G1; andwestore sdifferentb-bit(withpaddingbits)messages M andtheircorresponding H2-MACvalues,whicharereturnedbyon-line queries, in groupG2. If r s2nholds, there exists a solution (x′M′) with goodprobability, which satisfies H(x′) H2-MAC(K)(M′) and H(M′pad0) H(x)(pad1)for any messages, where pad0and pad1are the padding bits of M′and M′pad0. Therefore, x′is the equivalent key of H2-MAC. We notice that the on-line queries mustbe done in sequence while the off-line computations can be completed in parallel. There-fore, wecandecreasethenumberofon-linequeriesbyincreasingoff-linecomputationstokeep the success probability of the attack unchanged, to make the attack more practicable.Our results prove that H2-MAC instantiated with any MD construction hash function isnot a secure message authentication code.