ImperfectForwardSecrecy:HowDiffie-HellmanFailsinPracticeDavidAdrian¶KarthikeyanBhargavan∗ZakirDurumeric¶PierrickGaudry†MatthewGreen§J.AlexHalderman¶NadiaHeninger‡DrewSpringall¶EmmanuelThomé†LukeValenta‡BenjaminVanderSloot¶EricWustrow¶SantiagoZanella-BéguelinkPaulZimmermann†∗INRIAParis-Rocquencourt†INRIANancy-GrandEst,CNRS,andUniversitédeLorrainekMicrosoftResearch‡UniversityofPennsylvania§JohnsHopkins¶UniversityofMichiganForadditionalmaterialsandcontactinformation,visitWeakDH.org.ABSTRACTWeinvestigatethesecurityofDiffie-HellmankeyexchangeasusedinpopularInternetprotocolsandfindittobelesssecurethanwidelybelieved.First,wepresentLogjam,anovelflawinTLSthatletsaman-in-the-middledowngradeconnectionsto“export-grade”Diffie-Hellman.Tocarryoutthisattack,weimplementthenumberfieldsievediscretelogalgorithm.Afteraweek-longprecomputationforaspecified512-bitgroup,wecancomputearbitrarydiscretelogsinthatgroupinaboutaminute.Wefindthat82%ofvulnerableserversuseasingle512-bitgroup,allowingustocompromiseconnectionsto7%ofAlexaTopMillionHTTPSsites.Inresponse,majorbrowsersarebeingchangedtorejectshortgroups.WegoontoconsiderDiffie-Hellmanwith768-and1024-bitgroups.Weestimatethateveninthe1024-bitcase,thecom-putationsareplausiblegivennation-stateresources.Asmallnumberoffixedorstandardizedgroupsareusedbymillionsofservers;performingprecomputationforasingle1024-bitgroupwouldallowpassiveeavesdroppingon18%ofpopularHTTPSsites,andasecondgroupwouldallowdecryptionoftrafficto66%ofIPsecVPNsand26%ofSSHservers.AclosereadingofpublishedNSAleaksshowsthattheagency’sattacksonVPNsareconsistentwithhavingachievedsuchabreak.WeconcludethatmovingtostrongerkeyexchangemethodsshouldbeapriorityfortheInternetcommunity.1.INTRODUCTIONDiffie-HellmankeyexchangeiswidelyusedtoestablishsessionkeysinInternetprotocols.ItisthemainkeyexchangemechanisminSSHandIPsecandapopularoptioninTLS.WeexaminehowDiffie-Hellmaniscommonlyimplementedanddeployedwiththeseprotocolsandfindthat,inpractice,itfrequentlyofferslesssecuritythanwidelybelieved.Therearetworeasonsforthis.First,asurprisingnumberofserversuseweakDiffie-Hellmanparametersormaintainsupportforobsolete1990s-eraexport-gradecrypto.Morecritically,thecommonpracticeofusingstandardized,hard-Permissiontomakedigitalorhardcopiesofpartorallofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcita-tiononthefirstpage.Copyrightsforthird-partycomponentsofthisworkmustbehonored.Forallotheruses,contacttheOwner/Author(s).Copyrightisheldbytheowner/author(s).CCS’15,October12–16,2015,Denver,Colorado,USA.ACM978-1-4503-3832-5/15/10.DOI:http://dx.doi.org/10.1145/2810103.2813707.coded,orwidelysharedDiffie-Hellmanparametershastheeffectofdramaticallyreducingthecostoflarge-scaleattacks,bringingsomewithinrangeoffeasibilitytoday.ThecurrentbesttechniqueforattackingDiffie-Hellmanreliesoncompromisingoneoftheprivateexponents(a,b)bycomputingthediscretelogofthecorrespondingpublicvalue(gamodp,gbmodp).Withstate-of-the-artnumberfieldsievealgorithms,computingasinglediscretelogismoredifficultthanfactoringanRSAmodulusofthesamesize.However,anadversarywhoperformsalargeprecomputationforaprimepcanthenquicklycalculatearbitrarydiscretelogsinthatgroup,amortizingthecostoveralltargetsthatsharethisparameter.Althoughthisfactiswellknownamongmathematicalcryptographers,itseemstohavebeenlostamongpractitionersdeployingcryptosystems.Weexploitittoobtainthefollowingresults:ActiveattacksonexportciphersinTLS.WeintroduceLogjam,anewattackonTLSbywhichaman-in-the-middleattackercandowngradeaconnectiontoexport-gradecryp-tography.ThisattackisreminiscentoftheFREAKattack[7]butappliestotheephemeralDiffie-HellmanciphersuitesandisaTLSprotocolflawratherthananimplementationvulner-ability.Wepresentmeasurementsthatshowthatthisattackappliesto8.4%ofAlexaTopMillionHTTPSsitesand3.4%ofallHTTPSserversthathavebrowser-trustedcertificates.Toexploitthisattack,weimplementedthenumberfieldsievediscretelogalgorithmandcarriedoutprecomputationfortwo512-bitDiffie-Hellmangroupsusedbymorethan92%ofthevulnerableservers.Thisallowsustocomputeindividualdiscretelogsinaboutaminute.Usingourdiscretelogoracle,wecancompromiseconnectionstoover7%ofTopMillionHTTPSsites.Discretelogsoverlargergroupshavebeencomputedbefore[8],but,asfarasweareaware,thisisthefirsttimetheyhavebeenexploitedtoexposeconcretevulnerabilitiesinreal-worldsystems.WewerealsoabletocompromiseDiffie-Hellmanformanyotherserversbecauseofdesignandimplementationflawsandconfigurationmistakes.Theseincludeuseofcomposite-ordersubgroupsincombinationwithshortexponents,whichisvulnerabletoaknownattackofvanOorschotandWiener[51],andtheinabilityofclientstoproperlyvalidateDiffie-Hellmanparameterswithoutknowingthesubgrouporder,whichTLShasnoprovisiontocommunicate.Weimplementtheseattackstooanddiscoverseveralvulnerableimplementations.Risksfromcommon1024-bitgroups.Weexploretheim-plicationsofprecomputationattacksfor768-and1024-bitgroups,whicharewidelyusedinpracticeandstillconsidered ppolynomialselectionsievinglinearalgebralogdbprecomputationy,gdescentxindividuallogFigure1:Thenumberfieldsievealgorithmfordiscretelogconsistsofaprecomputationstagethatdependsonlyontheprimepandadescentstagethatcomputesindividuallogs.Withsufficientprecomputation,anattackercanquicklybreakanyDiffie-Hellmaninstancesthatuseaparticularp.secure.Weprovidenewestimatesforthecomputationalre-sourcesnecessarytocomputediscretelogsingroupsofthesesizes,concludingthat768-bitgroupsarewithinrangeofaca-demicteams,and1024-bitgroupsmayplausiblybewithinrangeofstate-levelattackers.Inbothcases,individuallogscanbequicklycomputedaftertheinitialprecomputation.WethenexamineevidencefrompublishedSnowdendocu-mentsthatsuggestsNSAmayalreadybeexploiting1024-bitDiffie-HellmantodecryptVPNtraffic.Weperformmeasure-mentstounderstandtheimplicationsofsuchanattackforpopularprotocols,findingthatanattackerwhocouldperformprecomputationsforten1024-bitgroupscouldpassivelyde-crypttraffictoabout66%ofIKEVPNs,26%ofSSHservers,16%ofSMTPservers,and24%ofpopularHTTPSsites.Mitigationsandlessons.Asashort-termcountermeasureinresponsetotheLogjamattack,allmainstreambrowsersareimplementingamorerestrictivepolicyonthesizeofDiffie-Hellmangroupstheyaccept.WefurtherrecommendthatTLSserversdisableexport-gradecryptographyandcarefullyvettheDiffie-Hellmangroupstheyuse.Inthelongerterm,weadvocatethatprotocolsmigratetostrongerDiffie-Hellmangroups,suchasthosebasedonellipticcurves.2.DIFFIE-HELLMANCRYPTANALYSISDiffie-Hellmankeyexchangewasthefirstpublishedpublic-keyalgorithm[14].Inthesimplecaseofprimegroups,AliceandBobagreeonaprimepandageneratorgofamultiplicativesubgroupmodulop.Alicesendsgamodp,Bobsendsgbmodp,andeachcomputesasharedsecretgabmodp.WhilethereisalsoaDiffie-Hellmanexchangeoverellipticcurvegroups,weaddressonlythe“modp”case.ThesecurityofDiffie-Hellmanisnotknowntobeequiva-lenttothediscretelogproblem(exceptincertaingroups[13,33,34]),butcomputingdiscretelogsremainsthebestknowncryptanalyticattack.Anattackerwhocanfindthediscretelogxfromy=gxmodpcaneasilyfindthesharedsecret.Textbookdescriptionsofdiscretelogcanbemisleadingaboutthecomputationaltradeoffs,forexamplebybalancingparameterstominimizeoveralltimetocomputeasinglediscretelog.Infact,asillustratedinFigure1,asinglelargeprecomputationonpcanbeusedtoefficientlybreakallDiffie-Hellmanexchangesmadewiththatprime.ThetypicalcaseDiffie-Hellmanistypicallyimplementedwithprimefieldsandlargegrouporders.Inthiscase,themostefficientdiscretelogalgorithmisthenumberfieldsieve(NFS)[21,24,43].1Thereisacloselyrelatednumberfieldsievealgorithmforfactoring[12,31],andinfactmanypartsoftheimplementationscanbeshared.Thegeneraltechniqueiscalledindexcalculusandhasfourstageswithdifferentcompu-tationalproperties.Thefirstthreestepsareonlydependentontheprimepandcomprisemostofthecomputation.Firstispolynomialselection,inwhichonefindsapolyno-mialf(z)defininganumberfieldQ(z)/f(z)forthecomputa-tion.(Forourcases,f(z)typicallyhasdegree5or6.)Thisparallelizeswellandisonlyasmallportionoftheruntime.Inthesecondstage,sieving,onefactorsrangesofintegersandnumberfieldelementsinbatchestofindmanyrelationsofelements,allofwhoseprimefactorsarelessthansomeboundB(calledB-smooth).Modernimplementationsusespecial-qlatticesieving,whichforeachspecialqexploresasievingregionof22Icandidates,whereIisaparameter.Sievingparallelizeswellsinceeachspecialqishandledindependentlyoftheothers,butiscomputationallyexpensive,becausewemustsearchthroughandattempttofactormanyelements.ThetimeforthisstepdependsonheuristicestimatesoftheprobabilityofencounteringB-smoothnumbersinthissearch;italsodependsonIandonthenumberofspecialqtoconsiderbeforehavingenoughrelations.Inthethirdstage,linearalgebra,weconstructalarge,sparsematrixconsistingofthecoefficientvectorsofprimefactorizationswehavefound.Anonzerokernelvectorofthematrixmodulotheorderqofthegroupwillgiveuslogsofmanysmallelements.Thisdatabaseoflogsservesasinputtothefinalstage.Thedifficultydependsonqandthematrixsizeandcanbeparallelizedinalimitedfashion.Thefinalstage,descent,actuallydeducesthediscretelogofthetargety.Were-sieveuntilwecanfindasetofrelationsthatallowustowritethelogofyintermsofthelogsintheprecomputeddatabase.Thisstepisaccomplishedinthreephases:aninitializationphase,whichtriestowritethetargetintermsofmedium-sizedprimes,amiddlephase,inwhichthesemedium-sizedprimesarefurthersieveduntiltheycanberepresentedbyelementsinthedatabaseofknownlogs,andafinalphasethatactuallyreconstructsthetargetusingthelogdatabase.Crucially,descentistheonlyNFSstagethatinvolvesy(org),sopolynomialselection,sieving,andlinearalgebracanbedoneonceforaprimepandreusedtocomputethediscretelogsofmanytargets.1Recentspectacularadvancesindiscretelogalgorithmshaveresultedinaquasi-polynomialalgorithmforsmall-characteristicfields[3],buttheseadvancesarenotknowntoapplytotheprimefieldsusedinpractice.2 TherunningtimeofthisalgorithmisLp(1/3,(64/9)1/3)=exp(cid:0)(1.923+o(1))(logp)1/3(loglogp)2/3(cid:1).Thisisobtainedbytuningmanyparameters,includingthedegreeoff,thesievingregionparameterI,and,mostimportantly,thesmoothnessboundB.Earlyarticles(e.g.[21])encounteredtechnicaldifficultieswithdescentandreportedthatthecom-plexityofthisstepwouldequalthatoftheprecomputation;thismayhavecontributedtomisconceptionsabouttheperfor-manceoftheNFSfordiscretelogs.MorerecentanalyseshaveimprovedthecomplexityofdescenttoLp(1/3,1.442)[10],andlatertoLp(1/3,1.232)[2],whichismuchcheaperthantheprecomputationinpractice.Thenumerousparametersofthealgorithmallowsomeflexibilitytoreducetimeonsomecomputationalstepsattheexpenseofothers.Forexample,sievingmorewillresultinasmallermatrix,makinglinearalgebracheaper,anddoingmoreworkintheprecomputationmakesthefinaldescentstepeasier.In§3.3,weshowhowexploitingthesetradeoffsallowsustoquicklycompute512-bitdiscretelogsinordertoperformaneffectiveman-in-the-middleattackonTLS.ImproperlygeneratedgroupsAdifferentfamilyofalgorithmsrunsintimeexponentialingrouporder,andtheyarepracticalevenforlargeprimeswhenthegrouporderissmallorhasmanysmallprimefactors.Toavoidthis,mostimplementationsuse“safe”primes,whichhavethepropertythatp−1=2qforsomeprimeq,sothattheonlypossiblesubgroupshaveorder2,q,or2q.However,asweshowin§3.5,improperlygeneratedgroupsaresometimesusedinpracticeandsusceptibletoattack.Thebaby-stepgiant-step[45]andPollardrho[42]algo-rithmsbothtake√qtimetocomputeadiscreteloginany(sub)groupoforderq,whilePollardlambda[42]canfindx