CryptographyandNetworkSecurityVariousHashAlgorithm密码学与网络安全不同的散列算法

CryptographyandNetworkSecurity

(VariousHashAlgorithms)FourthEditionbyWilliamStallingsLectureslidesbyLawrieBrown(ChangedbySomeshJha)1BirthdayAttacksmightthinka64-bithashissecurebutbyBirthdayParadoxisnotbirthdayattackworksthus:opponentgenerates2m/2

variationsofavalidmessageallwithessentiallythesamemeaningopponentalsogenerates2m/2variationsofadesiredfraudulentmessagetwosetsofmessagesarecomparedtofindpairwithsamehash(probability>0.5bybirthdayparadox)haveusersignthevalidmessage,thensubstitutetheforgerywhichwillhaveavalidsignatureconclusionisthatneedtouselargerMACs2HashFunctionPropertiesaHashFunctionproducesafingerprintofsomefile/message/data

h=H(M)condensesavariable-lengthmessageMtoafixed-sizedfingerprintassumedtobepublic3RequirementsforHashFunctionscanbeappliedtoanysizedmessageMproducesfixed-lengthoutputhiseasytocomputeh=H(M)foranymessageMgivenhisinfeasibletofindx

s.t.H(x)=hone-waypropertygivenxisinfeasibletofindy

s.t.H(y)=H(x)weakcollisionresistanceisinfeasibletofindanyx,y

s.t.H(y)=H(x)strongcollisionresistance4BlockCiphersasHashFunctionscanuseblockciphersashashfunctionsusingH0=0andzero-padoffinalblockcompute:Hi=EMi[Hi-1]andusefinalblockasthehashvaluesimilartoCBCbutwithoutakeyresultinghashistoosmall(64-bit)bothduetodirectbirthdayattackandto“meet-in-the-middle〞attackothervariantsalsosusceptibletoattack5HashAlgorithmssimilaritiesintheevolutionofhashfunctions&blockciphersincreasingpowerofbrute-forceattacksleadingtoevolutioninalgorithmsfromDEStoAESinblockciphersfromMD4&MD5toSHA-1&RIPEMD-160inhashalgorithmslikewisetendtousecommoniterativestructureasdoblockciphers6MD5designedbyRonaldRivest(the“R〞inRSA)latestinaseriesofMD2,MD4producesa128-bithashvalueuntilrecentlywasthemostwidelyusedhashalgorithminrecenttimeshavebothbrute-force&cryptanalyticconcernsspecifiedasInternetstandardRFC13217MD5Overviewpadmessagesoitslengthis448mod512appenda64-bitlengthvaluetomessageinitialise4-word(128-bit)MDbuffer(A,B,C,D)processmessagein16-word(512-bit)blocks:using4roundsof16bitoperationsonmessageblock&bufferaddoutputtobufferinputtoformnewbuffervalueoutputhashvalueisthefinalbuffervalue8MD5Overview9MD5CompressionFunctioneachroundhas16stepsoftheform:a=b+((a+g(b,c,d)+X[k]+T[i])<<<s)a,b,c,drefertothe4wordsofthebuffer,butusedinvaryingpermutationsnotethisupdates1wordonlyofthebufferafter16stepseachwordisupdated4timeswhereg(b,c,d)isadifferentnonlinearfunctionineachround(F,G,H,I)T[i]isaconstantvaluederivedfromsin10MD5CompressionFunction11MD4precursortoMD5alsoproducesa128-bithashofmessagehas3roundsof16stepsversus4inMD5designgoals:collisionresistant(hardtofindcollisions)directsecurity(nodependenceon"hard"problems)fast,simple,compactfavorslittle-endiansystems(egPCs)12StrengthofMD5MD5hashisdependentonallmessagebitsRivestclaimssecurityisgoodascanbeknownattacksare:Berson92attackedany1roundusingdifferentialcryptanalysis(butcan’textend)Boer&Bosselaers93foundapseudocollision(againunabletoextend)Dobbertin96createdcollisionsonMDcompressionfunction(butinitialconstantspreventexploit)conclusionisthatMD5looksvulnerablesoon13SecureHash

Algorithm(SHA-1)SHAwasdesignedbyNIST&NSAin1993,revised1995asSHA-1USstandardforusewithDSAsignatureschemestandardisFIPS180-11995,alsoInternetRFC3174note:thealgorithmisSHA,thestandardisSHSproduces160-bithashvaluesnowthegenerallypreferredhashalgorithmbasedondesignofMD4withkeydifferences14SHAOverviewpadmessagesoitslengthis448mod512appenda64-bitlengthvaluetomessageinitialise5-word(160-bit)buffer(A,B,C,D,E)to(67452301,efcdab89,98badcfe,10325476,c3d2e1f0)processmessagein16-word(512-bit)chunks:expand16wordsinto80wordsbymixing&shiftinguse4roundsof20bitoperationsonmessageblock&bufferaddoutputtoinputtoformnewbuffervalueoutputhashvalueisthefinalbuffervalue15SHA-1CompressionFunctioneachroundhas20stepswhichreplacesthe5bufferwordsthus:(A,B,C,D,E)<-(E+f(t,B,C,D)+(A<<5)+Wt+Kt),A,(B<<30),C,D)a,b,c,d,erefertothe5wordsofthebuffertisthestepnumberf(t,B,C,D)isnonlinearfunctionforroundWtisderivedfromthemessageblockKtisaconstantvaluederivedfromsin16SHA-1CompressionFunction17SHA-1versesMD5bruteforceattackisharder(160vs128bitsforMD5)notvulnerabletoanyknownattacks(comparedtoMD4/5)alittleslowerthanMD5(80vs64steps)bothdesignedassimpleandcompactoptimisedforbigendianCPU's(vsMD5whichisoptimisedforlittleendianCPU’s)18RevisedSecureHashStandardNISThasissuedarevisionFIPS180-2adds3additionalhashalgorithmsSHA-256,SHA-384,SHA-512designedforcompatibilitywithincreasedsecurityprovidedbytheAEScipherstructure&detailissimilartoSHA-1henceanalysisshouldbesimilar19KeyedHashFunctionsasMACshavedesiretocreateaMACusingahashfunctionratherthanablockcipherbecausehashfunctionsaregenerallyfasternotlimitedbyexportcontrolsunlikeblockciphershashincludesakeyalongwiththemessageoriginalproposal:KeyedHash=Hash(Key|Message)someweaknesseswerefoundwiththiseventuallyledtodevelopmentofHMAC20HMACspecifiedasInternetstandardRFC2104useshashfunctiononthemessage:HMACK=Hash[(K+XORopad)|| Hash[(K+XORipad)||M)]]whereK