降低 Hash 函数复杂度---以 MD5和 SHA-1为例(IJMSC-V5-N1-1)

I.J.MathematicalSciencesandComputing,2019,1,1-17PublishedOnlineJanuary2019inMECS()DOI:10.5815/ijmsc.2019.01.01Availableonlineat:MD5andSHA-1asExamplesDr.YousefAliAl-Hammadi1,MohamedFadlIdrisFadl21UnitedArabEmiratesUniversity,UAE2IslamicUniversity,SudanReceived:21April2018;Accepted:09August2018;Published:08January2019AbstractHashfunctionsalgorithmsalsocalledmessagedigestalgorithms,compressamessageinputofanarbitrarylength,andproduceanoutputwithafixedlengththatisdistributedrandomly.SeveralhashalgorithmsexistsuchasMd5andSHA1.Thesealgorithmsverifydataintegrityandrestrictunauthorizeddatamodification.However,theyexperiencesomecomplexities,especiallywhenimplementedinbitcoinmining,andlowcomputationdevices,inparticularlyIoTdevices.Asaremedy,thispapersuggestsanewcompressionfunctionthatreducesthecomplexityofthehashfunctionalgorithmssuchasMD5andSHA-1.Also,provesthatwecanobtainthesameresultswhichareachievedbytheoriginalcompressionfunction.IndexTerms:Hashfunctionscomplexity,SHA1,MD5,Bitcoinmining,Energyconsumptioninbitcoinmining.©2019PublishedbyMECSPublisher.Selectionand/orpeerreviewunderresponsibilityoftheResearchAssociationofModernEducationandComputerScience1.IntroductionAsaforementioned,Hashalgorithmscompressamessageinputofanarbitrarylengthandproduceanoutputwithafixedlengththatisdistributedrandomly.Thehashfunctionmusthavethefollowingproperties:first,thehashvaluemustbeeasytocompute.Second,itishardtocalculatethemessagefromthegivenhashvalue(thefunctionisone-wayfunctiononly)and,third,itisalsohardtofindtwodifferentmessageswiththesamehashvalueoutput[1].Ingeneralterms,wecanusehashfunctioninvarioussecurityapplicationsincludeMessageAuthentication,DigitalSignatures,IntrusionDetection,VirusDetection,Pseudo-randomNumberGeneratorandPassword*Correspondingauthor.E-mailaddress:[e-mail],[e-mail]2ReducingHashFunctionComplexity:MD5andSHA-1asExamplesverification,buttheprimaryusageofthehashfunctionsistoverifydataintegrityandrestrictunauthorizeddatamodification.Inthispaper,weareinterestedinasingleblockofahashfunctionsuchaspasswordverification.2.PasswordVerificationPasswordverificationisinventedbyRogerNeedham,whostatedthatinsteadofsavingallpasswordsasaplain-textformat,wecouldsavethehashdigestofthepasswordonly.Intherecentpastyears,mostofthesecureonlinebusinessisbasedontheusername/passwordauthenticationscheme.Thisschemeusesthestaticpasswordidentificationthathasavulnerabilitywhichenablespeopletorevealthepasswordeasily.Alternatively,theresearchersproposedtousesingleblockhashfunctionsasanauthenticationscheme.Inthisscheme,thesystemsavestheuserpasswordasahashvalueformat.Thepasswordisoftenconcatenatedwitharandom,non-secretsaltvaluebeforethehashfunctionisapplied.Thenthesystemcanauthenticatetheuserbycomparingtheenteredhashedpasswordwiththestoredone.Therefore,ifthesystemverifiestheusersuccessfully,then,hecanaccessthesystem.Otherwise,thesystemrejectstheuser.Incasetheuserforgetshispassword,then,thesystemcanallowhimtoreplacethepasswordwithanewone.Thesingleblockofhashfunctionlengthis512bitsifweremovethepaddingandthemessagesize,theremaininglengthis440bits(55characters),whichisproperforpasswordbecauseinmostcasesthepasswordlengthcannotexceedthe55characters.3.RelatedWorkTheresearchershaveexaminedthehashfunctionsalgorithmstoreducethecomplexityofthesealgorithms.[2]ProposedanarchitectureleveloptimizationtechniqueforuniversalHashFunctionsbyusingDivide-and-Concatenateapproach.Theyfoundthatthedivide-and-concatenatetechniquecannotspeed-upsoftwareimplementationsbutcanonlyimprovetheresistanceofcollision.[3]HavepresentedapipelinedserializedarchitecturefortheSHA-3candidateKeccak,whichoffersverylowareaandpowerconsumptionwithacceptablethroughput.TheirarchitectureisespeciallyattractiveforlightweightapplicationswhenimplementedwithcompactversionsofKeccak[4]Havedescribedanewfamilyofuniversalhashfunctionsgearedtowardshigh-speedmessageauthentication.Theyalsointroducedadditionaltechniquesforspeedinguptheirconstructionsbyignoringcertainpartsofthecomputation,whilestillretainingthenecessarystatisticalpropertiesforsecuremessageauthentication.[7]Theauthorshaveproposedalightweighthashfunctionwithreducedcomplexityintermsofhardwareimplementation,capableofachievingstandardsecurity.Itusesspongeconstructionwithpermutationfunctioninvolvingtheupdateoftwonon-linearfeedbackshiftregisters.Thus,intermsofspongecapacityitprovidesatleast80bitsecurityagainstgenericattackswhichisacceptablecurrently.[8]haveestablishedtheexistenceoflow-complexitycryptographichashfunctionsthatcompresstheinputby(atleast)aconstantfactor.TheyconstructCRHwithlinearcircuitsize,constantlocality,oralgebraicdegree3overZ2underdifferentflavorsofthenewlyintroducedbinarySVP(bSVP)assumption.[9]Theauthorshaveproposedalightweighthashfunctionwithreducedcomplexityintermsofhardwareimplementation,capableofachievingstandardsecurity.Itusesspongeconstructionwithpermutationfunctioninvolvingtheupdateoftwonon-linearfeedbackshiftregisters.Thu