MD5 CollisionsDescription of MD5Continued DescriptionHash ChainingOne small stepThe RoundsThe Non-Linear FunctionsFinding CollisionsRecall: Differential CryptanalysisDifferentialsRound differentialsProbabilityThe AttackMessage ModificationSufficient ConditionsConditions for biTechnique for M0Technique for M1Creating More CollisionsActual CollisionsReferencesMD5 CollisionsIsabelle StantonChalermpong WorawannotaiDescription of MD5Takes any message and outputs an 128-bit hash.A message is padded so the length is a multiple of 512 by concatenating a 1 then 0’s and it’s length as a 64 bit number.Each 512 bit block is compressed individuallyContinued DescriptionThe 512-bit block is divided into 16 32-bit wordsThere are 4 32-bit registers a, b, c and d. These are initially loaded with IV0 and carry the hash values from one 512-bit block to the nextIt works in an iterative (chaining) process:Hi+1 = f(Hi,Mi) IV0=H0where Mi is a 512 bit block.Hash Chainingf H0=IV0fixedM1H1fH2…fHn = HM2MnMi512 bitsHi128 bitsOne small stepFor each f there are 4 rounds and each round has 16 stepsTi and Si are fixed constant and depend only on the steps.Courtesy of www.wikipedia.orgThe RoundsMi=(w0,…,w15)For fixed i, 4 consecutive steps will yieldai+4 =bi +((ai +Fi (bi,ci,di)+wi+ti)<<<si)di+4=ai+((di+Fi+1 (ai,bi,ci)+wi+1+ti+1)<<<si+1)ci+4=di+((ci+Fi+2 (di,ai,bi)+wi+2+ti+2)<<<si+2)bi+4=ci+((bi+Fi+3 (ci,di,ai)+wi+3+ti+3)<<<si+3)ti and si are predefined step dependant constantsThe Non-Linear FunctionsFi changes every 16 stepsFi(X,Y,Z)=(X^Y)ν(~X^Z) 0≤i ≤15Fi(X,Y,Z)=(X^Z) ν(Y^~Z) 16 ≤i ≤31Fi(X,Y,Z)=X  Y  Z 32 ≤i ≤47Fi(X,Y,Z)=Y  (X ν ~Z) 48 ≤i ≤63This provides non-linearity so you can not extract the message from the hashFinding CollisionsMD5 has a 128 bit hash so a brute force attack to find a collision requires at most 2128 applications of MD5 and 264 by the birthday paradoxXiaoyun Wang and Hongbo Yu have an attack that requires 239 operationsThis attack takes at most an hour and 5 minutes on a IBM P690 (supercomputer)Recall: Differential CryptanalysisFind a particular ∆M such that a particular ∆H occurs with high probabilityIn collision case, want ∆H = 0.DifferentialsThe attack uses two types of differentialsXOR differential: ΔX=X  X’Modular differential: ΔX=X-X’ mod 232For M=(m0,…,mn-1) and M’=(m’0,…m’n-1) the full hash differential is for a message of length 512n bitsΔH0 -> ΔH1 ->…-> ΔHn= ΔHIf M and M’ are a collision pair ΔH=0Round differentialsΔHi -> ΔHi+1 can be split into round differentials as wellΔHi ΔR0 ΔR1 ΔR2 ΔR3=ΔHi+1P0P1P2P3ProbabilityEach of these differentials has a probabilistic relationship with the next.Ideally, we’d like to be able to set up 2 messages where we can guarantee with probability 1 that ΔH=0This can be assured by modifying M so the first round differential will be what you wantMore modifications will improve the probability for the second, third and fourth round differentialsΔM0 has been picked to improve this as wellThe AttackFind M=(M0,M1 ) and M’=(M’0,M’1)ΔM0=M’0-M0=(0,0,0,0,231,0,0,0,0,0,0,215,0,0,231,0)ΔM1=M’1-M1=(0,0,0,0,231,0,0,0,0,0,0,-215,0,0,231,0)ΔH1=(231,231+225,231+225,231+225)i.e. M0 and messages that does this is not a collisionΔM0 has been picked to improve the probability that the round differentials will holdM’0 differ in the 5th, 12th and 15th words onlySame for M1 and M’1.Every set of messages that does this is not a collisionΔM0 has been picked to improve this as wellMessage ModificationIt is easy to modify a message word so that the first non-zero step differential (after the 5th step) is anything you want with probability 1Modify multiple words to guarantee the round differentials with high probabilityEach modification to make one condition hold may make another not holdSufficient ConditionsΔw5 is first non-zero differentialAt the 8th step Δw5 has affected a, d and c so (Δc2, Δd2, Δa2, Δb1 )-> Δb2 since Δb1=0There are 13 conditions on a2, c2 and d2 that will guarantee Δb2 to be whatever you like with high probabilityEach characteristic has between 1 and 28 conditions for 30 characteristics for M0 and 29 characteristics with between 2 and 25 conditions for M1 for well over 200 conditionsConditions for bib1,7 = 0 b1,8 = c1,8 b1,9 = c1,9b1,10 = c1,10b1,11 = c1,11b1,12 = 1b1,13 = c1,13 b1,14 = c1,14 b1,15 = c1,15 b1,16 = c1,16b1,17 = c1,17b1,18 = c1,18b1,19 = c1,19 b1,20 = 1 b1,21 = c1,21 b1,22 = c1,22b1,23 = c1,23b1,24 = 0b1,32 = 1Technique for M0Select random M0Modify M0 so as many of the conditions hold as possibleCreate M0’=M0+ ΔM0This will result in ΔH1 with probability 2-37Test this worksThis doesn’t require more then 239 MD5 operationsTechnique for M1Select a random message M1Modify M1 so it meets the conditionsM1’ =M1+ ΔM0Starting with ΔH1 as IV the probability that H(M1)=H(M1’) is 2-30Test the pair of messages for collisionsCreating More CollisionsThere are many M1s that will collide with any properly crafted M0You can also change the last two words of M0 and maintain the conditionsThis reduces the amount of work neededActual CollisionsM0 = 2dd31d1 c4eee6c5 69a3d69 5cf9af98 87b5ca2f ab7e4612 3e580440 897ffbb8 634ad55 2b3f409 8388e483 5a417125 e8255108 9fc9cdf7 f2bd1dd9 5b3c3780M1=d11d0b96 9c7b41dc f497d8e4 d555655a c79a7335 cfdebf0 66f12930 8fb109d1 797f2775 eb5cd530 baade822 5c15cc79 ddcb74ed 6dd3c55f d80a9bb1 e3a7cc35M0’=2dd31d1 c4eee6c5 69a3d69 5cf9af98 7b5ca2f ab7e4612 3e580440 897ffbb8 634ad55 2b3f409 8388e483 5a41f125 e8255108 9fc9cdf7 72bd1dd9 5b3c3780M1’=d11d0b96 9c7b41dc f497d8e4 d555655a 479a7335 cfdebf0 66f12930 8fb109d1 797f2775 eb5cd530 baade822 5c154c79 ddcb74ed 6dd3c55f 580a9bb1 e3a7cc35Hash: 9603161f a30f9dbf 9f65ffbc f41fc7efReferencesHow To Break MD5 and Other Hash Functions – Xiaoyun Wang and Hongbo Yu (they did the SHA-1 break as well)Guide to Hash Functions http://unixwiz.net/techtips/iguide-crypto-hashes.htmlCryptographic Hash Lounge (lists what functions have been broken and links to how)