ensuringsources.list

FlipFengShui:HammeringaNeedleintheSoftwareStackKavehRazavi,BenGras,andErikBosman,VrijeUniversiteitAmsterdam;BartPreneel,KatholiekeUniversiteitLeuven;CristianoGiuffridaandHerbertBos,VrijeUniversiteitAmsterdamhttps://www.
usenix.
org/conference/usenixsecurity16/technical-sessions/presentation/razaviUSENIXAssociation25thUSENIXSecuritySymposium1FlipFengShui:HammeringaNeedleintheSoftwareStackKavehRazaviVrijeUniversiteitAmsterdamBenGrasVrijeUniversiteitAmsterdamErikBosmanVrijeUniversiteitAmsterdamBartPreneelKatholiekeUniversiteitLeuvenCristianoGiuffridaVrijeUniversiteitAmsterdamHerbertBosVrijeUniversiteitAmsterdam*EqualcontributionjointrstauthorsAbstractWeintroduceFlipFengShui(FFS),anewexploitationvectorwhichallowsanattackertoinducebitipsoverarbitraryphysicalmemoryinafullycontrolledway.
FFSreliesonhardwarebugstoinducebitipsovermemoryandontheabilitytosurgicallycontrolthephysicalmem-orylayouttocorruptattacker-targeteddataanywhereinthesoftwarestack.
WeshowFFSispossibletodaywithveryfewconstraintsonthetargetdata,byimplement-inganinstanceusingtheRowhammerbugandmemorydeduplication(anOSfeaturewidelydeployedinpro-duction).
Memorydeduplicationallowsanattackertoreverse-mapanyphysicalpageintoavirtualpagesheownsaslongasthepage'scontentsareknown.
Rowham-mer,inturn,allowsanattackertoipbitsincontrolled(initiallyunknown)locationsinthetargetpage.
WeshowFFSisextremelypowerful:amaliciousVMinapracticalcloudsettingcangainunauthorizedaccesstoaco-hostedvictimVMrunningOpenSSH.
UsingFFS,weexemplifyend-to-endattacksbreakingOpenSSHpublic-keyauthentication,andforgingGPGsignaturesfromtrustedkeys,therebycompromisingtheUbuntu/Debianupdatemechanism.
Weconcludebydis-cussingmitigationsandfuturedirectionsforFFSattacks.
1IntroductionThedemandforhigh-performanceandlow-costcomput-ingtranslatestoincreasingcomplexityinhardwareandsoftware.
Onthehardwareside,thesemiconductorin-dustrypacksmoreandmoretransistorsintochipsthatserveasafoundationforourmoderncomputinginfras-tructure.
Onthesoftwareside,modernoperatingsystemsarepackedwithcomplexfeaturestosupportefcientresourcemanagementincloudandotherperformance-sensitivesettings.
Bothtrendscomeatthepriceofreliabilityand,in-evitably,security.
Onthehardwareside,componentsareincreasinglypronetofailures.
Forexample,alargefractionoftheDRAMchipsproducedinrecentyearsarepronetobitips[34,51],andhardwareerrorsinCPUsareexpectedtobecomemainstreaminthenearfu-ture[10,16,37,53].
Onthesoftwareside,widespreadfeaturessuchasmemoryorstoragededuplicationmayserveassidechannelsforattackers[8,12,31].
Re-centworkanalyzessomeofthesecurityimplicationsofbothtrends,butsofartheattacksthatabusethesehardware/softwarefeatureshavebeenfairlylimited—probabilisticprivilegeescalation[51],in-browserex-ploitation[12,30],andselectiveinformationdisclo-sure[8,12,31].
Inthispaper,weshowthatanattackerabusingmod-ernhardware/softwarepropertiescanmountmuchmoresophisticatedandpowerfulattacksthanpreviouslybe-lievedpossible.
WedescribeFlipFengShui(FFS),anewexploitationvectorthatallowsanattackertoinducebitipsoverarbitraryphysicalmemoryinafullycon-trolledway.
FFSreliesontwounderlyingprimitives:(i)theabilitytoinducebitipsincontrolled(butnotpredetermined)physicalmemorypages;(ii)theabilitytocontrolthephysicalmemorylayouttoreverse-mapatargetphysicalpageintoavirtualmemoryaddressun-derattackercontrol.
Whilewebelievethegeneralvec-torwillbeincreasinglycommonandrelevantinthefu-ture,weshowthataninstanceofFFS,whichwetermdFFS(i.
e,deduplication-basedFFS),canalreadybeim-plementedontoday'shardware/softwareplatformswithveryfewconstraints.
Inparticular,weshowthatbyabusingLinux'memorydeduplicationsystem(KSM)[6]whichisverypopularinproductionclouds[8],andthewidespreadRowhammerDRAMbug[34],anattackercanreliablyipasinglebitinanyphysicalpageinthesoftwarestackwithknowncontents.
Despitethecompleteabsenceofsoftwarevulnerabili-ties,weshowthatapracticalFlipFengShuiattackcanhavedevastatingconsequencesinacommoncloudset-ting.
AnattackercontrollingacloudVMcanabuse225thUSENIXSecuritySymposiumUSENIXAssociationmemorydeduplicationtoseizecontrolofatargetphys-icalpageinaco-hostedvictimVMandthenexploittheRowhammerbugtoipaparticularbitinthetargetpageinafullycontrolledandreliablewaywithoutwrit-ingtothatbit.
WeusedFFStomountend-to-endcor-ruptionattacksagainstOpenSSHpublickeys,andDe-bian/UbuntuupdateURLsandtrustedpublickeys,allre-sidingwithinthepagecacheofthevictimVM.
Wendthat,whiledFFSissurprisinglypracticalandeffective,existingcryptographicsoftwareiswhollyunequippedtocounterit,giventhat"bitippingisnotpartoftheirthreatmodel".
Ourend-to-endattackscompletelycom-promisewidespreadcryptographicprimitives,allowinganattackertogainfullcontroloverthevictimVM.
Summarizing,wemakethefollowingcontributions:WepresentFFS,anewexploitationvectortoinducehardwarebitipsoverarbitraryphysicalmemoryinacontrolledfashion(Section2).
WepresentdFFS,animplementationinstanceofFFSthatexploitsKSMandtheRowhammerbugandweuseittobit-ipRSApublickeys(Sec-tion3)andcompromiseauthenticationandupdatesystemsofaco-hostedvictimVM,grantingtheat-tackerunauthorizedaccessandprivilegedcodeex-ecution(Section4).
WeusedFFStoevaluatethetimerequirementsandsuccessratesofourproposedattacks(Section5)anddiscussmitigations(Section6).
ThevideosdemonstratingdFFSattackscanbefoundinthefollowingURL:https://vusec.
net/projects/flip-feng-shui2FlipFengShuiToimplementanFFSattack,anattackerrequiresaphys-icalmemorymassagingprimitiveandahardwarevulner-abilitythatallowshertoipbitsoncertainlocationsonthemediumthatstorestheusers'data.
Physicalmem-orymassagingisanalogoustovirtualmemorymassag-ingwhereattackersbringthevirtualmemoryintoanexploitablestate[23,24,55],butinsteadperformedonphysicalmemory.
Physicalmemorymassaging(orsim-plymemorymassaging,hereafter)allowstheattackertosteervictim'ssensitivedatatowardsthosephysicalmem-orylocationsthatareamenabletobitips.
Oncethetar-getdatalandontheintendedvulnerablelocations,theat-tackercantriggerthehardwarevulnerabilityandcorruptthedataviaacontrolledbitip.
Theend-to-endattackallowstheattackertoipabitofchoiceindataofchoiceanywhereinthesoftwarestackinacontrolledfashion.
Withsomeconstraints,thisissimilartoatypicalarbi-trarymemorywriteprimitiveusedforsoftwareexploita-tion[15],withtwokeydifferences:(i)theend-to-endattackrequiresnosoftwarevulnerability;(ii)theattackercanoverwritearbitraryphysical(notjustvirtual)mem-oryontherunningsystem.
Ineffect,FFStransformsanunderlyinghardwarevulnerabilityintoaverypowerfulsoftware-likevulnerabilityviathreefundamentalsteps:1.
Memorytemplating:identifyingphysicalmemorylocationsinwhichanattackercaninduceabitipusingagivenhardwarevulnerability.
2.
Memorymassaging:steeringtargetedsensitivedatatowardsthevulnerablephysicalmemorylocations.
3.
Exploitation:triggeringthehardwarevulnerabilitytocorrupttheintendeddataforexploitation.
Intheremainderofthissection,wedetaileachofthesestepsandoutlineFFS'send-to-endattackstrategy.
2.
1MemoryTemplatingThegoalofthememorytemplatingstepistonger-printthehardwarebit-ippatternsontherunningsys-tem.
Thisisnecessary,sincethelocationsofhardwarebitipsaregenerallyunknowninadvance.
Thisisspeci-callytrueinthecaseofRowhammer;every(vulnerable)DRAMmoduleisuniqueintermsofphysicalmemoryoffsetswithbitips.
Inthisstep,theattackertriggersthehardware-specicvulnerabilitytodeterminewhichphysicalpages,andwhichoffsetswithinthosepagesarevulnerabletobitips.
Wecallthecombinationofavul-nerablepageandtheoffsetatemplate.
Probingfortemplatesprovidestheattackerwithknowledgeofusablebitips.
ThankstoFlipFengShui,anytemplatecanpotentiallyallowtheattackertoexploitthehardwarevulnerabilityoverphysicalmemoryinacontrolledway.
Theusefulnessofsuchanexploit,how-ever,dependsonthedirectionofthebitip(i.
e.
,one-to-zeroorzero-to-one),thepageoffset,andthecontentsofthetargetvictimpage.
Foreachavailabletemplate,theattackercanonlycraftaFlipFengShuiprimitivethatcorruptsthetargetdatapagewiththegivenipandoffset.
Hence,tosurgicallytargetthevictim'ssensitivedataofinterest,theattackerneedstoprobeformatch-ingtemplatesbyrepeatedlyexploitingthehardwarevul-nerabilityoveracontrolledphysicalpage(i.
e.
,mappedinhervirtualaddressspace).
Toperformthisstepef-ciently,ourowndFFSimplementationreliesonavari-antofdouble-sidedRowhammer[51].
Rowhammeral-lowsanattackertoinducebitipsinvulnerablememorylocationsbyrepeatedlyreadingfrommemorypageslo-catedinadjacentrows.
Wediscussthelow-leveldetails2USENIXAssociation25thUSENIXSecuritySymposium3HostPhysicalMemoryVictimVMMemoryAttackerVMMemoryHostPhysicalMemoryVictimVMMemoryAttackerVMMemoryHostPhysicalMemoryVictimVMMemoryAttackerVMMemory(A)(B)(C)Figure1:Memorydeduplicationcanprovideanattackercontroloverthelayoutofphysicalmemory.
oftheRowhammervulnerabilityandourimplementationinSection4.
2.
2.
2MemoryMassagingToachievebitipsoverarbitrarycontentsofthevictim'sphysicalmemory,FFSabusesmodernmemorymanage-mentpatternsandfeaturestocraftamemorymassagingprimitive.
Memorymassagingallowstheattackertomapadesiredvictim'sphysicalmemorypageintoherownvirtualmemoryaddressspaceinacontrollableway.
Givenasetoftemplatesandthememorymassagingprimitive,anidealversionofFFScancorruptanyofthevictim'smemorypagesatanoffsetdeterminedbytheselectedtemplate.
Whilememorymassagingmaybenontrivialinthegeneralcase,itissurprisinglyeasytoabusewidelyde-ployedmemorydeduplicationfeaturestocraftpracti-calFFSattacksthatcorruptanyofthevictim'smem-orypageswithknowncontents(similartoourdFFSim-plementation).
Intuitively,sincememorydeduplicationmergessystem-widephysicalmemorypageswiththesamecontents,anattackerabletocraftthecontentsofanyofthevictim'smemorypagescanobtainamemorymassagingprimitiveandmapthetargetpageintoherad-dressspace.
Figure1showshowanattackercancontrolthephysi-calmemorylocationofavictimVM'smemorypage.
Atrst,theattackerneedstopredictthecontentsofthevic-timVM'spagethatshewantstocontrol(Figure1-A).
Oncethetargetpageisidentied,theattackerVMcre-atesamemorypagewiththesamecontentsasthevictimVM'smemorypageandwaitsforthememorydedupli-cationsystemtoscanbothpages(Figure1-B).
Oncethetwophysicalpages(i.
e.
,theattacker'sandthevictim'spages)areidentied,thememorydeduplicationsystemreturnsoneofthetwopagesbacktothesystem,andtheotherphysicalpageisusedtobackboththeattackerandthevictim's(virtual)pages.
Iftheattacker'spageisusedtobackthememoryofthevictimpage,then,ineffect,theattackercontrolsthephysicalmemorylocationofthevictimpage(Figure1-C).
Thereareadditionaldetailsnecessarytocraftamem-orymassagingprimitiveusingareal-worldimplementa-tionofmemorydeduplication(e.
g.
,KSM).
Section4.
1elaboratesonsuchdetailsandpresentsourimplementa-tionofmemorymassagingonLinux.
2.
3ExploitationAtthisstage,FFSalreadyprovidestheattackerwithtem-platedbitipsoverthevictim'sphysicalmemorypageswithknown(orpredictable)contents.
Theexploitationsurfaceisonlysubjecttotheavailabletemplatesandtheirabilitytoreachinterestinglocationsfortheattacker.
Aswewillsee,theoptionsareabundant.
Whilecorruptingthememorystateofrunningsoft-wareofthevictimiscertainlypossible,wehaveoptedforamorestraightforward,yetextremelypowerfulex-ploitationstrategy.
WeconsideranattackerrunninginacloudVMandseekingtocorruptinterestingcontentsinthepagecacheofaco-hostedvictimVM.
Inparticular,ourdFFSimplementationincludestwoexploitsthatcor-ruptsensitivelecontentsinthepagecacheincompleteabsenceofsoftwarevulnerabilities:1.
FlippingSSH'sauthorized_keys:assumingtheRSApublickeysoftheindividualsaccessingthevictimVMareknown,anattackercanusedFFStoinduceanexploitableipintheirpublickeys,mak-ingthempronetofactorizationandbreakingtheau-thenticationsystem.
2.
Flippingapt'ssources.
listandtrusted.
gpg:Debian/Ubuntu'saptpackagemanagementsystemreliesonthesources.
listletooperatedailyup-datesandonthetrusted.
gpgletochecktheau-thenticityoftheupdatesviaRSApublickeys.
Com-promisingtheselesallowsanattackertomakeavictimVMdownloadandinstallarbitraryattacker-generatedpackages.
Inpreliminaryexperiments,wealsoattemptedtocraftanexploittobit-ipSSH'smodulilecontainingDife-Hellmangroupparametersandeavesdroponthevictim3425thUSENIXSecuritySymposiumUSENIXAssociationVM'sSSHtrafc.
ThemaximumgroupsizeoncurrentdistributionsofOpenSSHis1536.
Whenwerealizedthatanexploittargetingsuch1536-bitparameterswouldre-quireanontrivialcomputationaleffort(seeAppendixAforaformalanalysis),weturnedourattentiontothetwomorepracticalandpowerfulexploitsabove.
InSection3,wepresentacryptanalysisofRSAmod-uliwithabitipasaresultofourattacks.
InSection4,weelaborateontheinternalsoftheexploits,andnally,inSection5,weevaluatetheirsuccessrateandtimere-quirementsinatypicalcloudsetting.
3CryptanalysisofRSAwithBitFlipsRSA[49]isapublic-keycryptosystem:thesenderen-cryptsthemessagewiththepublickeyoftherecipient(consistingofanexponenteandamodulusn)andthere-cipientdecryptstheciphertextwithherprivatekey(con-sistingofanexponentdandamodulusn).
ThiswayRSAcansolvethekeydistributionproblemthatisinher-enttosymmetricencryption.
RSAcanalsobeusedtodigitallysignmessagesfordataoruserauthentication:thesigningoperationisperformedusingtheprivatekey,whilethevericationoperationemploysthepublickey.
Public-keycryptographyreliesontheassumptionthatitiscomputationallyinfeasibletoderivetheprivatekeyfromthepublickey.
ForRSA,computingtheprivateex-ponentdfromthepublicexponenteisbelievedtorequirethefactorizationofthemodulusn.
Ifnistheproductoftwolargeprimesofapproximatelythesamesize,factor-izingnisnotfeasible.
Commonsizesforntodayare1024to2048bits.
Inthispaperweimplementafaultattackonthemodu-lusnofthevictim:wecorruptasinglebitofn,resultinginn.
Weshowthatwithhighprobabilitynwillbeeasytofactorize.
Wecanthencomputefromethecorrespond-ingvalueofd,theprivatekey,thatallowsustoforgesignaturesortodecrypt.
Weprovideadetailedanalysisoftheexpectedcomputationalcomplexityoffactorizingninthefollowing1.
RSAperformcomputationsmodulon,wheretisthebitlengthofn(t=1+log2n).
Typicalvaluesoftliebetween512(exportcontrol)and8192,with1024and2048themostcommonvalues.
Wedenotetheithbitofnwithn[i](0≤ip2>···ps.
IntheRSAcryptosystem,themodulusnistheprod-uctoftwooddprimesp1,p2ofapproximateequalsize,hences=2,andγ1=γ2=1.
Theencryptionoperationiscomputedasc=memodn,withethepublicexpo-nent,andm,c∈[0,n1])theplaintextrespectivelytheciphertext.
Theprivateexponentdcanbecomputedasd=e1modλ(n),withλ(n)theCarmichaelfunction,givenbylcm(p1,p2).
Thebestknownalgorithmtore-covertheprivatekeyistofactorizenusingtheGeneralNumberFieldSieve(GNFS)(seee.
g.
[42]),whichhascomplexityO(Ln[1/3,1.
92]),withLn[a,b]=exp(b+o(1))(lnn)a(lnlnn)1a.
Fora512-bitmodulusn,Adrianetal.
estimatethatthecostisabout1core-year[3].
Thecurrentrecordis768bits[35],butitisclearthat1024bitsiswithinreachofintelligenceagencies[3].
IfweiptheLSBofn,weobtainn=n1,whichisevenhencen=2·nwithnat1-bitinteger.
Ifweipthemostsignicantbitofn,weobtaintheoddt1-bitintegern.
Inalltheothercasesweobtainanoddt-bitintegern.
Weconjecturethattheintegern(fortheLSBcase)andtheintegersn(fortheothercases)havethesamedistributionofprimefactorsasarandomoddinte-ger.
Tosimplifythenotation,weomitinthefollowingtheLSBcase,buttheequationsapplywithnreplacedbyn.
Assumethatanattackercanintroduceabitiptochangenintonwithasfactorizationn=∏sj=1pγii.
Thenc=memodn.
TheCarmichaelfunctioncanbecomputedasλ(n)=lcmpγi1i·(pi1).
Ifgcd(e,λ(n))=1,theprivateexponentdcanbefoundasd=e1modλ(n).
Forprimeexponentse,theprob-abilitythatgcd(e,λ(n))>1equals1/e.
Fore=3,thismeansthat1in3attacksfails,butforthewidelyusedvaluee=216+1,thisisnotaconcern.
Withtheprivateexponentdwecandecryptorsignanymessage.
Hencethequestionremainshowtofactorizen.
Asitisverylikelythatnisnottheproductoftwoprimesofalmostequalsize,wecanexpectthatfactorizingnismucheas-ierthanfactorizingn.
Ourconjectureimpliesthatwithprobability2/lnn,nisprimeandinthatcasethefactorizationistrivial.
Ifniscomposite,thebestapproachistondsmallfactors(sayupto16bits)usingagreatestcommondivisoroper-ationwiththeproductoftherstprimes.
ThenextstepistousePollard'sρalgorithm(orBrent'svariant)[42]:thisalgorithmcaneasilyndfactorsupto40.
.
.
60bits.
AthirdstepconsistofLenstra'sEllipticCurvefactor-izationMethod(ECM)[38]:ECMcanquicklyndfac-torsupto60.
.
.
128bits(therecordisafactorofabout4USENIXAssociation25thUSENIXSecuritySymposium5270bits2).
Itscomplexitytondthesmallestprimefac-torpsisequaltoO(Lps[1/2,√2]).
WhileECMisasymp-toticallylessefcientthanGNFS(becauseoftheparam-eter1/2ratherthan1/3),thecomplexityofECMdependsonthesizeofthesmallestprimefactorpsratherthanonthesizeoftheintegerntofactorize.
Onceaprimefac-torpiisfound,nisdividedbyit,theresultistestedforprimalityandiftheresultiscomposite,ECMisrestartedwithasargumentn/pi.
ThecomplexityanalysisofECMdependsonthenum-berofprimefactorsandthedistributionofthesizeofthesecondlargestprimefactorp2:itisknownthatitsexpectedvaluedis0.
210·t[36].
TheErds–Kactheo-rem[22]statesthatthenumberω(n)ofdistinctprimefactorsofnisnormallydistributedwithmeanandvari-ancelnlnn:fort=1024themeanisabout6.
56,withstandarddeviation2.
56.
Henceitisunlikelythatwehaveexactlytwoprimefactors(probability3.
5%),andevenlesslikelythattheyareofapproximateequalsize.
Theprobabilitythatnisprimeisequalto0.
28%.
Theex-pectedsizeofthesecondlargestprimefactorp2is215bitsandtheprobabilitythatithaslessthan128bitsis0.
26[36].
InthiscaseECMshouldbeveryefcient.
Fort=2048,theprobabilitythatnisprimeequals0.
14%.
Theexpectedsizeofthesecondlargestprimefactorp2is430bits;theprobabilitythatp2haslessthan228bitsis0.
22andtheprobabilitythatithaslessthan128bitsisabout0.
12.
Similarly,fort=4096,theexpectedsizeofthesecondlargestprimefactorp2is860bits.
Theprobabilitythatp2haslessthan455bitsis0.
22.
Themainconclusionisthatifnhas1024-2048bits,wecanexpecttofactorizenefcientlywithaprobabilityof1222%foranarbitrarybitip,butlargermodulishouldalsobefeasible.
AsweshowinSection5,givenafewdozentemplates,wecaneasilyfactorizeany1024bitto4096bitmoduluswithone(ormore)oftheavailabletemplates.
4ImplementationToimplementdFFSreliablyonLinux,weneedtoun-derstandtheinternalsoftwokernelsubsystems,ker-nelsame-pagemerging[6](KSM)andtransparenthugepages[5],andthewaytheyinteractwitheachother.
AfterdiscussingthemandourimplementationoftheRowhammerexploit(Sections4.
1,4.
2,and4.
3),weshowhowwefactorizedcorruptedRSAmoduliinSec-tion4.
4beforesummarizingourend-to-endattacksinSection4.
5.
2https://en.
wikipedia.
org/wiki/Lenstra_elliptic_curve_factorization4.
1KernelSame-pageMergingKSM,theLinuximplementationofmemorydeduplica-tion,usesakernelthreadthatperiodicallyscansmemorytondmemorypageswiththesamecontentsthatarecandidatesformerging.
Itthenkeepsasinglephysicalcopyofasetofcandidatepages,marksitread-only,andupdatesthepage-tableentriesofalltheothercopiestopointtoitbeforereleasingtheirphysicalpagestothesystem.
KSMkeepstwored-blacktrees,termed"stable"and"unstable",tokeeptrackofthemergedandcandidatepages.
Themergedpagesresideinthestabletreewhilethecandidatecontentsthatarenotyetmergedareintheunstabletree.
KSMkeepsalistofmemoryareasthatareregisteredfordeduplicationandgoesthroughthepagesintheseareasintheorderinwhichtheywereregistered.
Foreachpagethatitscans,itchecksifthestabletreealreadycontainsapagewiththesamecontents.
Ifso,itupdatesthepage-tableentryforthatpagetohaveitpointtothephysicalpageinthestabletreeandreleasesthebackingphysicalpagetothesystem.
Otherwise,itsearchestheunstabletreeforamatchandifitndsone,promotesthepagetothestabletreeandupdatesthepage-tableentryofthematchtomakeitpointtothispage.
Ifnomatchisfoundineitheroneofthetrees,thepageisaddedtotheunstabletree.
Aftergoingthroughallmem-oryareas,KSMdumpstheunstabletreebeforestartingagain.
FurtherdetailsontheinternalsofKSMcanbefoundin[6].
InthecurrentimplementationofKSM,duringamerge,thephysicalpageineitherthestabletreeortheunstabletreeisalwayspreferred.
Thismeansthatduringamergewithapageinthestabletree,thephysicalloca-tionofthepageinthestabletreeischosen.
Similarly,thephysicalmemoryofthepageintheunstabletreeischo-sentobackbothpages.
KSMscansthememoryoftheVMsinorderthattheyhavebeenregistered(i.
e.
,theirstartingtime).
ThismeansthattocontrolthelocationofthetargetdataonphysicalmemoryusingtheunstabletreetheattackerVMshouldhavebeenstartedbeforethevictimVM.
Hence,thelongertheattackerVMwaits,thelargerthechanceofphysicalmemorymassagingthroughtheunstabletree.
Thebetterphysicalmemorymassagingpossibilityisthroughthestabletree.
AnattackerVMcanupgradeadesiredphysicalmemorylocationtothestabletreebycreatingtwocopiesofthetargetdataandplacingonecopyinthedesiredphysicalmemorylocationandan-othercopyinadifferentmemorylocation.
Byensuringthattheothercopycomesafterthedesiredphysicalmem-orylocationinthephysicaladdress-space,KSMmergesthetwopagesandcreatesastabletreenodeusingthede-siredphysicalmemorylocation.
Atthispoint,anyother5625thUSENIXSecuritySymposiumUSENIXAssociationFigure2:ASO-DIMMwithitsmemorychips.
pagewiththesamecontentswillassumethesamephys-icalmemorylocationdesiredbytheattackerVM.
Forthistowork,however,theattackerneedstocontrolwhenthememorypagewiththetargetcontentsiscreatedinthevictimVM.
InthecaseofourOpenSSHattack,forexample,theattackercancontrolwhenthetargetpageiscreatedinthevictimVMbystartinganSSHconnectionusinganinvalidkeywiththetargetusername.
Forsimplicity,thecurrentversionofdFFSimplementsthememorymassagingusingtheunstabletreebyassum-ingthattheattackerVMhasstartedrst,butitistrivialtoaddsupportformemorymassagingwithstabletree.
UsingeitherthestableorunstableKSMtreesformem-orymassaging,alldFFSneedstodoiscraftingapagewiththesamecontentsasthevictimpageandplaceitatthedesiredphysicalmemorypage;KSMwillthenper-formthenecessarypage-tableupdatesondFFS'sbehalf!
Inotherwords,KSMinadvertentlyprovidesuswithex-actlythekindofmemorymassagingweneedforsuc-cessfulFlipFengShui.
4.
2RowhammerinsideKVMInternally,DRAMisorganizedinrows.
Eachrowpro-videsanumberofphysicalcellsthatstorememorybits.
Forexample,inanx86machinewithasingleDIMM,eachrowcontains1,048,576cellsthatcanstore128kBofdata.
EachrowisinternallymappedtoanumberofchipsontheDIMMasshowninFigure2.
Figure3showsasimpleorganizationofaDRAMchip.
Whentheprocessorreadsaphysicalmemorylo-cation,theaddressistranslatedtoanoffsetonrowioftheDRAM.
Dependingontheoffset,theDRAMselectstheproperchip.
Theselectedchipthencopiesthecon-tentsofitsrowitotherowbuffer.
Thecontentsatthecorrectoffsetwithintherowbufferisthensentonthebustotheprocessor.
Therowbufferactsasacache:iftheselectedrowisalreadyintherowbuffer,thereisnoneedtoreadfromtherowagain.
EachDRAMcellisbuiltusingatransistorandaca-pacitor.
Thetransistorcontrolswhetherthecontentsofthecellisaccessible,whilethecapacitorcanholdachargewhichsignieswhetherthestoredcontentisaRowi-1RowiRowi+1RowBufferFigure3:DRAM'sinternalorganization.
highorlowbit.
Sincecapacitorsleakchargeovertime,theprocessorsendsrefreshcommandstoDIMMrowsinordertorechargetheircontents.
Ontopoftherefreshcommands,everytimearowisreadbytheprocessor,thechipalsorechargesitscells.
AsDRAMcomponentshavebecomesmaller,theykeepasmallerchargetosignifystoredcontents.
Withasmallercharge,theerrormarginforidentifyingwhetherthecapacitorischarged(i.
e.
,thestoredvalue)isalsosmaller.
Kimetal.
[34]showedthatthesmallerer-rormargin,incombinationwithunexpectedchargeex-changebetweencellsofdifferentrows,canresultinthecellto"lose"itscontent.
TotriggerthisDRAMrelia-bilityissue,anattackerneedsfastactivationsofDRAMrowswhichcausesacellinadjacentrowstoloseenoughchargesothatitscontentiscleared.
Notethatduetotherowbuffer,atleasttworowsneedtoactivateoneaftertheotherinatightloopforRowhammertotrigger.
Ifonlyonerowisreadfrom,thereadscanbesatisedcon-tinuallyfromtherowbuffer,withoutaffectingtherowchargesintheDRAMcells.
Double-sidedRowhammer.
Previouswork[51]re-portedthatifthesetwo"aggressor"rowsareselectedinawaythattheyareonerowapart(e.
g.
,rowi1andi+1inFigure3),thechancesofchargeinteractionbe-tweentheserowsandtherowinthemiddle(i.
e.
,rowi)increases,resultinginpotentialbitipsinthatrow.
ThisvariantofRowhammerisnameddouble-sidedRowham-mer.
Apartfromadditionalspeedforachievingbitips,itprovidesadditionalreliabilitybyisolatingthelocationofmostbitipstoacertain(victim)row.
Toperformdouble-sidedRowhammerinsideKVM,weneedtoknowthehostphysicaladdressesinsidetheVM.
Thisinformationis,however,notavailableintheguest:guestphysicaladdressesaremappedtohostvir-tualaddresseswhichcanbemappedtoanyphysicalpagebytheLinuxkernel.
Similarto[30],werelyontranspar-enthugepages[5](THP).
THPisaLinuxkernelfeature6USENIXAssociation25thUSENIXSecuritySymposium7thatrunsinthebackgroundandmergesvirtuallycontigu-ousnormalpages(i.
e.
,4kBpages)intohugepages(i.
e.
,2MBpages)thatrelyoncontiguouspiecesofphysicalmemory.
THPgreatlyreducesthenumberofpage-tableentriesinsuitableprocesses,resultinginfewerTLB3en-tries.
Thisimprovesperformanceforsomeworkloads.
THPisanother(weak)formofmemorymassaging:ittransparentlyallowstheattackercontroloverhowthesystemmapsguestphysicalmemorytohostphysicalmemory.
OncetheVMisstartedandacertainamountoftimehaspassed,THPwilltransformmostoftheVM'smemoryintohugepages.
OurcurrentimplementationofdFFSrunsentirelyintheuserspaceoftheguestandre-liesonthedefault-onTHPfeatureofboththehostandtheguest.
Assoonastheguestboots,dFFSallocatesalargebufferwith(almost)thesamesizeastheavailablememoryintheguest.
TheTHPinthehostthenconvertsguestphysicaladdressesintohugepagesandtheTHPintheguestturnstheguestvirtualpagesbackingdFFS'sbufferintohugepagesaswell.
Asaresult,dFFS'sbufferwilllargelybebackedbyhugepagesallthewaydowntohostphysicalmemory.
TomakesurethatthedFFS'sbufferisbackedbyhugepages,werequesttheguestkerneltoalignthebufferata2MBboundary.
Thisensuresthatifthebufferisbackedbyhugepages,itstartswithone:onthex86_64architec-ture,thevirtualandphysicalhugepagessharethelowest20bits,whicharezero.
Thesameapplieswhentransi-tioningfromtheguestphysicaladdressestohostphys-icaladdresses.
Withthisknowledge,dFFScanassumethatthestartoftheallocatedbufferisthestartofamem-oryrow,andsincemultiplerowstintoahugepage,itcansuccessivelyperformdouble-sidedRowhammerontheserows.
Tospeedupoursearchforbitipsduringdouble-sidedRowhammeroneachtworows,werelyontherow-conictsidechannelforpickingthehammeringaddresseswithineachrow[44].
WefurtheremployedmultiplethreadstoamplifytheRowhammereffect.
WhileTHPprovidesuswiththeabilitytoefcientlyandreliablyinduceRowhammerbitips,ithasunex-pectedinteractionswithKSMthatwewillexploreinthenextsection.
4.
3MemoryMassagingwithKSMInSection2.
2,wediscussedtheoperationalsemanticsofKSM.
Herewedetailsomeofitsimplementationfea-turesthatareimportantfordFFS.
3TLBortranslationlookasidebufferisageneraltermforprocessorcachesforpage-tableentriestospeedupthevirtualtophysicalmemorytranslation4.
3.
1InteractionwithTHPAswediscussedearlier,KSMdeduplicatesmemorypageswiththesamecontentsassoonasitndsthem.
KSMcurrentlydoesnotsupportdeduplicationofhugepages,butwhathappenswhenKSMndsmatchingcon-tentswithinhugepagesAcarefulstudyoftheKSMshowsthatKSMal-waysprefersreducingmemoryfootprintoverreducingTLBentries;thatis,KSMbreaksdownhugepagesintosmallerpagesifthereisasmallpageinsidewithsimilarcontentstoanotherpage.
ThisspecicfeatureisimportantforanefcientandreliableimplementationofdFFS,buthastobetreatedwithcare.
Morespecically,wecanusehugepagesaswediscussedintheprevioussectionforefcientandre-liabledouble-sidedRowhammer,whileretainingcontroloverwhichvictimpageweshouldmapinthemiddleofourtarget(vulnerable)hugepage.
KSM,however,canhaveundesiredinteractionswithTHPfromdFFS'spointofview.
IfKSMndspagesintheattackerVM'smemorythathavematchingcontents,itmergesthemwitheachotherorwithapagefromapreviouslystartedVM.
Inthesesituations,KSMbreaksTHPbyreleasingoneofitssmallerpagestothesys-tem.
Toavoidthis,dFFSusesatechniquetoavoidKSMduringitstemplatingphase.
KSMtakesafewtensofsecondstomarkthepagesofdFFS'sVMascandidatesfordeduplication.
ThisgivesdFFSenoughtimetoallo-catealargebufferwiththesamesizeasVM'savailablememory(asmentionedearlier)andwriteuniqueintegersatapre-determinedlocationwithineach(small)pageofthisbufferassoonasitsVMboots.
TheentropypresentwithindFFS'spagesthenprohibitsKSMtomergethesepageswhichinturnavoidsbreakingTHP.
4.
3.
2OndFFSChainingInitially,weplannedonchainingmemorymassagingprimitiveandFFStoinduceanarbitrarynumberofbitipsatmanydesiredlocationsofthevictim'smemorypage.
Afterusingthersttemplatefortherstbitip,theattackercanwritetothemergedmemorypagetotrig-geracopy-on-writeeventthatultimatelyunmergesthetwopages(i.
e.
,theattackerpagefromthevictimpage).
Atthisstage,theattackercanusedFFSagainwithanewtemplatetoinduceanotherbitip.
However,theimplementationofKSMdoesnotallowthistohappen.
Duringthecopy-on-writeevent,thevic-tim'spageremainsinthestabletree,evenifitistheonlyremainingpage.
Thismeansthatsubsequentattemptsformemorymassagingresultsinthevictimpagetocontrolthelocationofphysicalmemory,disablingtheattacker'sabilityforchainingFFSattacks.
7825thUSENIXSecuritySymposiumUSENIXAssociationEvenso,basedonoursinglebitipcryptanalysisonpublickeysandourevaluationinSection5,chainingisnotnecessaryforperformingsuccessfulend-to-endat-tackswithdFFS.
4.
4AttackingWeakenedRSAForthetwoattacksinthispaper,wegenerateRSApri-vatekeys,i.
e.
,theprivateexponentsdcorrespondingtocorruptedmodulin(asdescribedinSection3).
Weusedtocompromisetwoapplications:OpenSSHandGPG.
Althoughthespecicsoftheapplicationsareverydif-ferent,thepatterntodemonstrateeachattackisthesameandasfollows:1.
ObtainthelecontainingtheRSApublickey(n,e).
Thisisapplication-specic,butduetothenatureofpublickeycryptosystems,generallyunprotected.
Wecallthistheinputle.
2.
UsingthememorytemplatingstepofSection2.
1weobtainalistoftemplatesthatweareabletoipwithinaphysicalpage.
Weipbitsaccordingtothetargettemplatestoobtaincorruptedkeys.
Forev-erysinglebitip,wesaveanewle.
Wecalltheselesthecorruptedles.
Accordingtothetemplat-ingstep,dFFShastheabilitytocreateanyofthesecorruptedlesinthevictimbyippingabitinthepagecache.
3.
Onebyone,wenowreadthe(corrupted)publickeysforeachcorruptedle.
Ifthecorruptedleisparsedcorrectlyandthepublickeyhasachangedmodulusn=nandthesamee,thisnisacandidateforfactorization.
4.
Westartfactorizationsofallncandidatesfoundinthepreviousstep.
AswedescribedinSection3,thebestknownalgorithmforourscenarioisECMthatndsincreasinglylargefactorinaniterativefashion.
WeusetheSage[19]implementationofECMforfactorizingn.
WeinvokeaninstanceofECMperavailablecoreforeachcorruptedkeywitha1hourtimeout(allavailableimplementationsofECMrunwithasinglethread).
5.
Forallsuccessfulfactorizations,wecomputetheprivateexponentdcorrespondingto(n,e)andgeneratethecorrespondingprivatekeytothecor-ruptedpublickey.
HowtocomputedbasedonthefactorizationofnisdescribedinSection3.
Wecanthenusetheprivatekeywiththeunmodiedappli-cation.
Thisstepisapplication-specicandwewilldiscussitforourcasestudiesshortly.
Wenowdescribeourend-to-endattacksthatputallthepiecesofdFFStogetherusingtwotargetapplications:OpenSSHandGPG.
4.
5End-to-endAttacksAttackermodel.
TheattackerownsaVMco-hostedwithavictimVMonahostwithDIMMssusceptibletoRowhammer.
Wefurtherassumethatmemorydedu-plicationisturnedon—asiscommonpracticeinpubliccloudsettings[8].
Theattackerhastheabilitytousethememorydeduplicationside-channeltongerprintlow-entropyinformation,suchastheIPaddressofthevictimVM,OS/libraryversions,andtheusernamesonthesys-tem(e.
g.
,through/etc/passwdleinthepagecache)asshownbypreviouswork[32,43,56].
Theattacker'sgoalistocompromisethevictimVMwithoutrelyingonanysoftwarevulnerability.
WenowdescribehowthismodelapplieswithdFFSintwoimportantandwidelypopularapplications.
4.
5.
1OpenSSHOneofthemostcommonlyusedauthenticationmecha-nismsallowedbytheOpenSSHdaemonisanRSApub-lickey.
Byaddingauser'sRSApublickeytotheSSHauthorized_keysle,thecorrespondingprivatekeywillallowloginofthatuserwithoutanyotherauthentica-tion(suchasapassword)inadefaultsetting.
Thepublickeybydefaultincludesa2048bitmodulusn.
Thecom-pletekeyisa372-bytelongbase64encodingof(n,e).
TheattackercaninitiateanSSHconnectiontothevic-timwithacorrectvictimusernameandanarbitrarypri-vatekey.
ThisinteractionforcesOpenSSHtoreadtheauthorized_keysle,resultinginthisle'scontentsgettingcopiedintothepagecacheattherighttimeaswediscussedinSection4.
1.
Publickeycryptosystemsbydenitiondonotrequirepublickeystobesecret,there-foreweassumeanattackercanobtainavictimpublickey.
Forinstance,GitHubmakestheusers'submittedSSHpublickeyspubliclyavailable[27].
Withthevictim'spublickeyknownandinthepagecache,wecaninitiatedFFSforinducingabitip.
Wecannotipjustanybitinthememorypagecachingtheauthorized_keys;sometemplateswillbreakthebase64encoding,resultinginacorruptedlethatOpenSSHdoesnotrecognize.
Someips,however,de-codetoavalid(n,e)keythatwecanfactorize.
Were-portinSection5howmanytemplatesareavailableonaverageforatargetpublickey.
Next,weuseascriptwiththePyCryptoRSAcryp-tographiclibrary[39]tooperateonthecorruptedpublickeys.
ThislibraryisabletoreadandparseOpenSSHpublickeyles,andextracttheRSAparameters(n,e).
8USENIXAssociation25thUSENIXSecuritySymposium9ItcanalsogenerateRSAkeyswithspecicparametersandexportthemasOpenSSHpublic(n,e)andprivate(n,d)keysagain.
Alltheattackerneedstodoisfactor-izenaswediscussedinSection4.
4.
Onceweknowthefactorsofn,wegeneratethepri-vatekey(n,d)thatcanbeusedtologintothevictimVMusinganunmodiedOpenSSHclient.
4.
5.
2GPGTheGNUPrivacyGuard,orGPG,isasophisticatedim-plementationof,amongothers,theRSAcryptosystem.
Ithasmanyapplicationsinsecurity,oneofwhichisthevericationofsoftwaredistributionsbyverifyingsigna-turesusingtrustedpublickeys.
Thisisthelargerappli-cationweintendtosubvertwiththisattack.
Specically,wetargettheaptpackagedistributionsystememployedbyDebianandUbuntudistributionforsoftwareinstallationandupdates.
aptveriespackagesignaturesafterdownloadusingGPGandtrustedpub-lickeysstoredintrusted.
gpg.
Itfetchesthepackageindexfromsourcesinsources.
list.
Ourattackrststeersthevictimtoourmaliciousrepository.
TheattackercanusedFFStoachievethisgoalbyinducingabitipinthesources.
listlethatispresentinthepagecacheafteranupdate.
sources.
listholdstheURLoftherepositoriesthatareusedforpackageinstallationandupdate.
Byusingacorrecttemplate,theattackercanipabitthatresultsinaURLthatshecontrols.
Now,thevictimwillseekthepackageindexandpackagesatanattacker-controlledrepository.
Next,weuseourexploittotargettheGPGtrustedkeysdatabase.
Asthisleispartofthesoftwaredistribu-tion,thestockcontentsofthisleiswell-knownandweassumethisleisunchangedorwecanguessthenewchanges.
(Onlythepagescontainingthekeyswedependonneedbeeitherunchangedorguessed.
)Thislere-sidesinthepagecacheeverytimethesystemtriestoupdateasaresultofadailycronjob,sointhisattack,nodirectinteractionwiththevictimisnecessaryforbring-ingtheleinthepagecache.
Ourimplicitassumptionisthatthisleremainsinthepagecacheforthenextupdateiteration.
SimilartoOpenSSH,weapplybitipmutationsinlo-cationswherewecaninducebitipsaccordingtothememorytemplatingstep.
Asaresult,weobtainthecor-ruptedversionsofthisle,andeachtimecheckwhetherGPGwillstillacceptthisleasavalidkeyringandthatoneoftheRSAkeymodulihaschangedasaresultofourbitip.
ExtractingthekeydataisdonewiththeGPG--list-keys--with-key-dataoptions.
Foreverybitiplocationcorrespondingtoacorruptedmodulusthatwecanfactorize,wepickoneofthesemutationsandgeneratethecorresponding(n,d)RSAprivatekey,againusingPyCrypto.
Weexportthispri-vatekeyusingPyCryptoasPEMformattedkeyandusepem2openpgp[26]toconvertthisPEMprivatekeytotheGPGformat.
Herewespecifytheusageagstoin-cludesigningandthesamegenerationtimestampastheoriginalpublickey.
WecanthenimportthisprivatekeyforuseforsigningusinganunmodiedGPG.
ItisimportantthattheKeyIDintheprivatekeyringmatchwiththeKeyIDinthetrusted.
gpgle.
ThisKeyIDisnotstaticbutisbasedonahashcomputedfromthepublickeydata,akeygenerationtimestamp,andsev-eralotherelds.
InorderfortheKeyIDintheprivatekeyringtomatchwiththeKeyIDinthepublickeyring,theseeldshavetobeidenticalandsothesettingofthecreationtimestampissignicant.
OnesignicantremarkabouttheKeyIDchanging(asaresultofabitip)isthatthiscausedtheself-signatureonthepublickeyringtobeignoredbyGPG!
Thesigna-turecontainstheoriginalKeyID,butitisnowattachedtoakeywithadifferentIDduetothepublickeymu-tation.
Asaresult,GPGignorestheattachedsignatureasanintegritycheckofthebit-ippedpublickeyandtheself-signingmechanismfailstocatchourbitip.
Theonlyside-effectisharmlesstoourattack–GPGreportsthatthetrustedkeyisnotsigned.
aptignoresthiswith-outevenshowingawarning.
Afterfactorizingthecor-ruptedpublickeymodulus,wesuccessfullyveriedthatthecorrespondingprivatekeycangenerateasignaturethatveriesagainstthebit-ippedpublickeystoredintheoriginaltrusted.
gpg.
Wecannowsignourmaliciouspackagewiththenewprivatekeyandthevictimwilldownloadandinstallthenewpackagewithoutawarning.
5EvaluationWeevaluateddFFStoanswerthefollowingthreekeyquestions:WhatisthesuccessprobabilityofthedFFSattackHowlongdoesthedFFSattacktakeHowmuchcomputationpowerisnecessaryforasuccessfuldFFSattackWeusedthefollowingmethodologyforourevalua-tion.
WerstusedaRowhammertestbedtomeasurehowmanytemplatesareavailableinagivensegmentofmemoryandhowlongittakesustondacertaintem-plate.
Wethenexecutedtheend-to-endattacksdiscussedinSection4.
5andreportontheirsuccessrateandtheirstart-to-nishexecutiontime.
Wethenperformedanan-alyticallarge-scalestudyofthefactorizationtime,suc-cessprobability,andcomputationrequirementsof20091025thUSENIXSecuritySymposiumUSENIXAssociationFigure4:Requiredtimeandmemoryfortemplating.
RSApublickeysforeachofthe1024,2048and4096-bitmoduliwith50bitipsatrandomlocations(i.
e.
,30,000bitippedpublickeysintotal).
WeusedthefollowinghardwareforourRowhammertestbedandfortheclusterthatweusedtoconductourfactorizationstudy:Rowhammertestbed.
IntelHaswelli7-47904-coreprocessoronanAsusH97-Promainboardwith8GBofDDR3memory.
Factorizationcluster.
Upto60nodes,eachwithtwoIntelXeonE5-26308-coreprocessorswith64GBofmemory.
5.
1dFFSontheRowhammerTestbedMemorytemplating.
OurcurrentimplementationofRowhammertakesanaverageof10.
58secondstocom-pletedouble-sidedRowhammerforeachtargetrow.
Fig-ure4showstheamountoftimeandphysicalmemorythatisnecessaryfordiscoveringacertainnumberoftem-plates.
Notethat,inourtestbed,wecoulddiscovertem-platesforalmostanybitoffset(i.
e.
,29,524outof32,768possibletemplates).
Later,wewillshowthatweonlyneedaverysmallfractionofthesetemplatestosuccess-fullyexploitourtwotargetprograms.
Memorymassaging.
dFFSneedstowaitforacertainamountoftimeforKSMtomergememorypages.
KSMscansacertainnumberofpagesineachwakingperiod.
OnthedefaultversionofUbuntu,forexample,KSMscans100pagesevery20milliseconds(i.
e.
,20MB).
Re-centwork[12]showsthatitispossibletoeasilydetectwhenadeduplicationpasshappens,hencedFFSneedstowaitatmostthesumofmemoryallocatedtoeachco-hostedVM.
Forexample,inourexperimentswithoneFigure5:Numberofusable1-to-0bitipsusableintheSSHauthorized_keysleforvariousmodulussizes.
Figure6:CDFofsuccessfulautomaticSSHattacks.
attackerVMandonevictimVMeachwith2GBofmem-ory,KSMtakesatmostaround200secondsforacom-pletepass.
5.
2TheSSHPublicKeyAttackFigure5showsthenumberofpossibletemplatestoper-formthedFFSattackontheSSHauthorized_keyslewithasinglerandomlyselectedRSApublickey,for1024,2048and4096-bitpublickeys.
Forthisexperi-ment,weassumed1-to-0bitipssincetheyaremorecommoninourtestbed.
ForDRAMchipsthataresus-ceptibletofrequent0-to-1bitips,thesenumbersdou-ble.
Forourexperimentwefocusedon2048-bitpublickeysastheyarethedefaultlengthasgeneratedbythessh-keygencommand.
Todemonstratetheworkingend-to-endattack,mea-sureitsreliability,andmeasuretheelapsedtimedistri-bution,weautomaticallyperformedtheSSHattack300timesfromanattackerVMonavictimVM,creatingthekeysandVM'sfromscratcheachtime.
Figure6showstheCDFofsuccessfulattackswithrespecttothetimetheytook.
In29cases(9.
6%),theRowhammeropera-tiondidnotchangethemodulusatall(theattackerneeds10USENIXAssociation25thUSENIXSecuritySymposium11Table1:Examplesofdomainsthatareonebitipawayfromubuntu.
comthatwepurchased.
ubuftu.
comubunt5.
comubunte.
comubunuu.
comubunvu.
comubunpu.
comubun4u.
comubuntw.
comubuntt.
comtoretry).
In19cases(6.
3%),theRowhammeroperationchangedthemodulusotherthanplanned.
Theremaining252(84.
1%)weresuccessfulthersttime.
Alltheat-tacksnishedwithin12.
6minuteswithamedianof5.
3minutes.
5.
3TheUbuntu/DebianUpdateAttackWetriedfactorizingthetwobit-ipped4096bitUbuntuArchiveAutomaticSigningRSAkeysfoundinthetrusted.
gpgle.
Outofthe8,192trials(wetriedboth1-to-0and0-to-1ips),wecouldfactorize344tem-plates.
WealsoneedtondabitipintheURLoftheUbuntuorDebianupdateservers(dependingonthetar-getVM'sdistribution)inthepagecacheentryforapt'ssources.
listle.
Forubuntu.
com,29templatesre-sultinavaliddomainname,andfordebian.
org,26templatesresultinavaliddomainname.
Table5.
2showsexamplesofdomainsthatareonebitipawayfromubuntu.
com.
PerformingtheupdateattackonourRowhammertestbed,wecouldtriggerabitipinthepagecacheentryofsourcessources.
listin212seconds,con-vertingubuntu.
comtoubunvu.
com,adomainwhichwecontrol.
Further,wecouldtriggerabitipinthepagecacheentryoftrusted.
gpgthatchangedoneoftheRSApublickeystoonethatwehadpre-computedafactorizationin352seconds.
Atthispoint,weman-uallysignthemaliciouspackagewithourGPGprivatekeythatcorrespondstothemutatedpublickey.
Whenthevictimthenupdatesthepackagedatabaseandup-gradesthepackages,themaliciouspackageisdown-loadedandinstalledwithoutwarning.
Sincethecur-rentversionofdFFSrunsthesestepssequentially,theentireend-to-endattacktook566seconds.
Wehavepreparedavideoofthisattackwhichisavailableat:https://vusec.
net/projects/flip-feng-shuiGrowinglyconcernedabouttheimpactofsuchpracti-calattacks,weconservativelyregisteredallthepossibledomainsfromourUbuntu/Debianlist.
5.
4RSAModulusFactorizationFigure7showstheaverageprobabilityofsuccessfulfac-torizationsbasedontheamountofavailablecomputeFigure7:Computepowerandfactorizationtimeouttradeofffor2048-bitRSAkeys.
Figure8:CDFofsuccessratewithincreasingtemplates.
hours.
Wegeneratedthisgraphusing200randomlygen-erated2048-bitRSAkeys,eachwithabitipin50dis-tincttrials(i.
e.
,10,000keys,eachwithabitip).
Forthisexperiment,wereliedontheECMfactorizationtool,dis-cussedinSection3,andvarieditsuser-controlledtime-outparameterbetweenonesecondandonehour.
Forexample,withatimeoutofonesecondforakeywithabitip,weeithertimeoutorthefactorizationsucceedsimmediately.
Inbothcases,wemoveontothenexttrialofthesamekeywithadifferentbitip.
Thisgraphshowsthat,with50bitips,theaveragefactorizationsuccessprobabilityisbetween0.
76foratimeoutofonesecondand0.
93foratimeoutofonehour.
Notethat,forexample,withatimeoutofonesecond,wecantry50templatesinlessthan50seconds,whileachievingasuccessfulfactorizationinasmanyas76%ofthepublickeys.
Atimeoutofoneminuteprovidesareasonabletradeoffandcanachieveasuccessrateof91%for2048-bitRSAkeys.
Figure8showsthecumulativesuccessprobabilityoffactorizationasmoretemplatesbecomeavailablefor1024-bit,2048-bitand4096-bitkeys.
For4096-bitkeys,weneedaround50templatestobeabletofactorizeakeywithhighprobability(0.
85)witha1-hourtimeout.
111225thUSENIXSecuritySymposiumUSENIXAssociationFigure9:Probabilitymassfunctionofsuccessfulfactor-izationswithoneip.
Withbit-ipped2048-bitRSApublickeys,withonly48templates,weachievedasuccessprobabilityof0.
99witha1hourtimeout.
Thisprovesthatfor2048-bitkeys(ssh-keygen'sdefault),onlyaverysmallfractionofthetemplatesfromourtestbedisnecessaryforasuccessfulfactorization.
For1024-bitkeys,wefoundasuccessfulfactorizationforallkeysafterjust32templates.
SomeDRAMmodulesmayonlyhaveasmallnumberofbitips[34],soaninterestingquestionis:whatisthechanceofachievingafactorizationusingonlyasingletemplateFigure9answersthisquestionfor1024-bit,2048-bitand4096-bitmoduliseparately.
Tointerpretthegure,xapointonthehorizontalaxis:thisistheprob-abilityofasuccessfulfactorizationusingasinglebitipwithin1hour.
Nowreadthecorrespondingvalueontheverticalaxis,whichshowstheprobabilitythatapublickeyfollowsthissuccessrate.
Forexample,onaverage,15%of2048-bitRSApublickeyscanbefactoredusingonlyasinglebitipwithprobability0.
1.
Asisexpected,theprobabilitytofactor4096-bitkeyswiththesame1-hourtimeoutislower,andfor1024-bitkeyshigher.
Thefactthatthedistributionsarecenteredaroundroughly0.
22,0.
11,and0.
055areconsistentwithouranalyticalresultsin3,whichpredictthefactorizationcostislinearinthebitlengthofthemodulus.
6MitigationsMitigatingFlipFengShuiisnotstraightforwardashard-warereliabilitybugsbecomeprevalent.
Whilethereisobviouslyneedfornewtestingmethodsandcerti-cationonthehardwaremanufacturer'sside[4],soft-wareneedstoadapttotFlipFengShuiinitsthreatmodel.
Inthissection,werstdiscussconcretemiti-gationsagainstdFFSbeforesuggestinghowtoimprovesoftwaretocounterFFSattacks.
Table2:Memorysavingswithdifferentdedupstrategies.
StrategyRequiredmemorySavingsNodedup506GB0%Zero-pagededup271GB46%Fulldedup108GB79%6.
1DefendingagainstdFFSWediscussbothhardwareandsoftwaresolutionsforde-fendingagainstdFFS.
6.
1.
1InHardwareWerecommendDRAMconsumersperformextensiveRowhammertesting[2]toidentifyvulnerableDRAMmodules.
TheseDRAMmodulesshouldbereplaced,butifthisisnotpossible,reducingDRAMrefreshin-tervals(e.
g.
,byhalf)maybesufcienttoprotectagainstRowhammer[51].
However,thisalsoreducesDRAMperformanceandconsumesadditionalpower.
Anotheroptionistorelyonmemorywitherror-correctingcodes(ECC)toprotectagainstsinglebitips.
Unfortunately,wehaveobservedthatRowhammercanoccasionallyinducemultipleipsinasingle64-bitwordconrmingthendingsoftheoriginalRowhammerpa-per[34].
Thesemulti-ipscancausecorruptioneveninpresenceofECC.
Moreexpensivemulti-ECCDIMMscanprotectagainstmultiplebitips,butitisstillunclearwhethertheycancompletelymitigateRowhammer.
Amorepromisingtechnologyisdirectedrowre-fresh,whichisimplementedinlow-powerDDR4[7](LPDDR4)andsomeDDR4implementations.
LPDDR4countsthenumberofactivationsofeachrowand,whenthisnumbergrowsbeyondaparticularthreshold,itrefreshestheadjunctrows,preventingcellchargesfromfallingbelowtheerrormargin.
NewerIntelpro-cessorssupportasimilarfeatureforDDR3,butre-quirecompliantDIMMs.
WhilethesexesmitigateRowhammer,replacingmostofcurrentDDR3deploy-mentswithLPDDR4orsecureDDR4DIMMs(someDDR4DIMMsarereportedtobevulnerabletoRowham-mer[1]),isnoteconomicallyfeasibleasitrequirescom-patiblemainboardsandprocessors.
Asaresult,asoft-waresolutionisnecessaryformitigatingRowhammerincurrentdeployments.
6.
1.
2InSoftwareThemostobviousmitigationagainstdFFSisdisablingmemorydeduplication.
Infact,thisiswhatwerec-ommendinsecurity-sensitiveenvironments.
Disablingmemorydeduplicationcompletely,however,wastesa12USENIXAssociation25thUSENIXSecuritySymposium13substantialamountofphysicalmemorythatcanbesavedotherwise[6,46,54].
Previouswork[12]showedthatdeduplicatingzeropagesalonecanretainbetween84%and93%ofthebenetsoffulldeduplicationinabrowsersetting.
Lim-itingdeduplicationtozeropagesandisolatingtheirRowhammer-pronesurroundingrowswasourrstmit-igationattempt.
Tounderstandwhetherzero-pagededu-plicationretainssufcientmemorysavingbenetsinacloudsetting,weperformedalarge-scalememorydedu-plicationstudyusing1,011memorysnapshotsofdif-ferentVMsfromcommunityVMimagesofWindowsAzure[48].
Table2presentsourresults.
Unfortunately,zero-pagededuplicationonlysaves46%ofthepoten-tial79%.
Thissuggeststhatdeduplicatingzeropagesaloneisinsufcienttoeradicatethewastefulredundancyincurrentclouddeployments.
Hence,weneedabet-terstrategythatcanretainthebenetsoffullmemorydeduplicationwithoutresultinginamemorymassagingprimitivefortheattackers.
AstrawmandesignApossiblesolutionistorelyonadeduplicationdesignthat,foreverymergeoperation,randomlyallocatesanewphysicalpagetobacktheex-istingduplicatepages.
Whenmergeoperationswithex-istingsharedpagesoccur,suchdesignwouldneedtorandomlyselectanewphysicalpageandupdateallthepage-tablemappingsforallthesharingparties.
Thisstrawmandesigneliminatesthememorymassag-ingprimitivethatisnecessaryfordFFSundernormalcir-cumstances.
However,thismaybeinsufcientifanat-tackercannddifferentprimitivestocontrolthephysicalmemorylayout.
Forexample,theattacker'sVMcancor-nerthekernel'spageallocatorintoallocatingpageswithpredictablepatternsifitcanforcethehostkernelintoanout-of-memory(OOM)situation.
Thisisnotdifcultifthehostreliesonover-committedmemorytopackmoreVMsthanavailableRAM,apracticewhichiscommonincloudsettingsandnaturallyenabledbymemorydedu-plication.
Forexample,theattackercantriggeramassivenumberofunmergeoperationsandcausethehostkerneltoapproachanOOMsituation.
Atthispoint,theattackercanreleasevulnerablememorypagestotheallocator,craftapagewiththesamecontentsasthevictimpage,andwaitforamergeoperation.
Duetothenear-OOMsituation,themergeoperationhappensalmostinstantly,forcingthehostkerneltopredictablypickoneofthepreviouslyreleasedvulnerablememorypages(i.
e.
,tem-plates)tobacktheexistingduplicatepages(thecraftedpageandthevictimpage).
Atthisstage,theattackerhasagain,ineffect,amemorymassagingprimitive.
AbetterdesignToimproveonthestrawmandesign,thehostneedstoensureenoughmemoryisavailablenottogetcorneredintopredictablephysicalmemoryreusepatterns.
Givenadesiredlevelofentropyh,andthenum-berofmergedpagesmiforfortheithVM,thehostneedstoensureA=2h+Max(mi)memorypagesareavail-ableorcaneasilybecomeavailable(e.
g.
,pagecache)tothekernel'spageallocatoratalltimes.
Withanad-equatechoiceofh,itmaybecomedifcultforanat-tackertocontrolthebehaviorofthememorydedupli-cationsystem.
Wehaveleftthestudyoftherightpa-rametersforhandtheprojectedAforrealsystemstofuturework.
Wealsonotethatbalancingentropy,mem-ory,andperformancewhensupportingatrulyrandomanddeduplication-enabledphysicalmemoryallocatorischallenging,andapromisingdirectionforfuturework.
6.
2MitigatingFFSattheSoftwareLayerTheattackspresentedinthispaperprovideworrisomeevidencethateventhemostsecurity-sensitivesoftwarepackagesusedinproductionaccountfornoattacker-controlledbitipsaspartoftheirthreatmodel.
Whilethereiscertainlyroomforfurtherresearchinthisdirec-tion,basedonourexperience,weformulateanumberofsuggestionstoimprovecurrentpractices:Security-sensitiveinformationneedstobecheckedforintegrityinsoftwarerightbeforeusetoensurethewindowofcorruptionissmall.
Inallthecasesweanalyzed,suchintegritycheckswouldbeplacedonaslowpathwithessentiallynoapplicationper-formanceimpact.
CerticatechainformatssuchasX.
509areauto-maticallyintegritycheckedascerticatesareal-wayssigned[17].
Thisisasignicantsidebenetofacerticationchainwithself-signatures.
Thelesystem,duetothepresenceofthepagecache,shouldnotbetrusted.
Sensitiveinformationonstablestorageshouldincludeintegrityorauthen-ticityinformation(i.
e.
,asecuritysignature)forveri-cationpurposes.
Infact,thissimpledefensemech-anismwouldstopthetwodFFSattacksthatwepre-sentedinthispaper.
Low-leveloperatingsystemoptimizationsshouldbeincludedwithextracare.
Muchrecentwork[11,12,29,40,58]showsthatbenignkernelopti-mizationssuchastransparenthugepages,vsyscallpages,andmemorydeduplicationcanbecomedan-geroustoolsinthehandsofacapableattacker.
InthecaseofFFS,anyfeaturethatallowsanuntrustedentitytocontrolthelayoutorreuseofdatainphysi-calmemorymayprovideanattackerwithamemorymassagingprimitivetomountourattacks.
131425thUSENIXSecuritySymposiumUSENIXAssociation7RelatedWorkWecategorizerelatedworkintothreedistinctgroupsdis-cussedbelow.
7.
1RowhammerExploitationPioneeringworkontheRowhammerbugalreadywarnedaboutitspotentialsecurityimplications[34].
Oneyearlater,SeabornpublishedthersttwoconcreteRowham-merexploits,intheformofescapingtheGoogleNativeClient(NaCl)sandboxandescalatinglocalprivilegesonLinux[51].
Interestingly,Seaborn'sprivilegeescalationexploitreliesonaweakformofmemorymassagingbyprobabilisticallyforcingaOOMingkerneltoreusephys-icalpagesreleasedfromuserspace.
dFFS,incontrast,reliesonadeterministicmemorymassagingprimitivetomappagesfromco-hostedVMsandmountfullyreliableattacks.
Inaddition,whilemappingpagesfromkernelspaceforlocalprivilegeescalationispossible,dFFSen-ablesamuchbroaderrangeofattacksovernearlyarbi-traryphysicalmemory.
Furthermore,Seaborn'sexploitsreliedonIntelx86'sCLFLUSHinstructiontoevictacachelinefromtheCPUcachesinordertoreaddirectlyfromDRAM.
Formit-igationpurposes,CLFLUSHwasdisabledinNaClandthesamesolutionwassuggestedfornativeCPUsviaamicrocodeupdate.
Inresponsetothelocalpriv-ilegeexploit,Linuxdisabledunprivilegedaccesstovirtual-to-physicalmemorymappinginformation(i.
e.
,/proc/self/pagemap)usedintheexploittoperformdouble-sidedRowhammer.
Grussetal.
[30],how-ever,showedthatitispossibletoperformdouble-sidedRowhammerfromthebrowser,withoutCLFLUSH,andwithoutpagemap,usingcacheevictionsetsandtranspar-enthugepages(THP).
dFFSreliesonnestedTHP(bothinthehostandintheguest)forreliabledouble-sidedRowhammer.
Inourpreviouswork[12],wetookthenextstepandimplementedtherstreliableRowhammerex-ploitintheMicrosoftEdgebrowser.
OurexploitinducesabitipinthecontrolstructureofaJavaScriptobjectforpivotingtoanattacker-controlledcounterfeitobject.
Thecounterfeitobjectprovidestheattackerswitharbitrarymemoryreadandwriteprimitivesinsidethebrowser.
Alltheattacksmentionedaboverelyononekeyas-sumption:theattackeralreadyownsthephysicalmem-oryofthevictimtomakeRowhammerexploitationpos-sible.
Inthispaper,wedemonstratedthat,byabus-ingmodernmemorymanagementfeatures,itispossi-bletocompletelyliftthisassumptionwithalarmingcon-sequences.
UsingFFS,anattackercanseizecontrolofnearlyarbitraryphysicalmemoryinthesoftwarestack,forexamplecompromisingco-hostedVMsincompleteabsenceofsoftwarevulnerabilities.
7.
2MemoryMassagingSotirov[55]demonstratesthepowerofcontrollingvir-tualmemoryallocationsinJavaScript,bypassingmanyprotectionsagainstmemoryerrorswithatechniquecalledHeapFengShui.
Mandt[41]demonstratesthatitispossibletocontrolreusepatternsintheWindows7kernelheapallocatorinordertobypassthedefaultmem-oryprotectionsagainstheap-basedattacksinthekernel.
Inspiredbythesetechniques,ourFlipFengShuidemon-stratesthatanattackerabusingbenignandwidespreadmemorymanagementmechanismsallowsasinglebitiptobecomeasurprisinglydangerousattackprimitiveoverphysicalmemory.
Memorysprayingtechniques[25,33,47,50]allocatealargenumberofobjectsinordertomakethelayoutofmemorypredictableforexploitationpurposes,similar,inspirit,toFFS.
GovindavajhalaandAppel[28]sprayedtheentirememoryofamachinewithspecially-craftedJavaobjectsandshowedthat70%ofthebitipscausedbyrareeventscosmicraysandsuchwillallowthemtoescapetheJavasandbox.
Thisattackisbyitsnatureprobabilisticand,unlikeFFS,doesnotallowforfullycontrollableexploitation.
Memorydeduplicationsidechannelshavebeenpre-viouslyabusedtocraftincreasinglysophisticatedinfor-mationdisclosureattacks[8,12,29,32,43,56].
Inthispaper,wedemonstratethatmemorydeduplicationhasevenstrongersecurityimplicationsthanpreviouslyshown.
FFScanabusememorydeduplicationtoperformattacker-controlledpage-tableupdatesandcraftamem-orymassagingprimitiveforreliablehardwarebitipex-ploitation.
7.
3BreakingWeakenedCryptosystemsFaultattackshavebeenintroducedincryptographybyBonehetal.
[9];theirattackwashighlyeffectiveagainstimplementationsofRSAthatusetheChineseRemain-derTheorem.
Sincethen,manyvariantsoffaultat-tacksagainstcryptographicimplementationshavebeendescribedaswellascountermeasuresagainsttheseat-tacks.
SeifertwasthersttoconsiderattacksinwhichfaultswereintroducedintheRSAmodulus[52];hisgoalwaslimitedtoforgingsignatures.
Brieretal.
[14]haveextendedhisworktosophisticatedmethodstorecovertheprivatekey;theyconsiderasettingofuncontrollablefaultsandrequiremanyhundredstoeventensofthou-sandsoffaults.
Inourattacksetting,theattackercanchoosethelocationandobservethemodulus,whichre-ducestheoverheadsubstantially.
InthecaseofDife-Hellman,theriskofusingitwithmodulithatarenotstrongprimesorhard-to-factorinte-gerswaswellunderstoodanddebatedextensivelydur-14USENIXAssociation25thUSENIXSecuritySymposium15ingtheRSAversusDSAcontroversyintheearly1990s(e.
g.
,inapanelatEurocrypt'92[18]).
VanOorschotandWienershowedhowagrouporderwithsmallfactorscaninteractbadlywiththeuseofsmallDife-Hellmanexpo-nents[57].
In2015,theLogjamattack[3]raisednewin-terestinthepotentialweaknessesofDife-Hellmanpa-rameters.
Inthispaper,weperformedaformalcryptanalysisofRSApublickeysinthepresenceofbitips.
Ourevalua-tionofdFFSwithbit-ippeddefault2048-bitRSApub-lickeysconrmedourtheoreticalresults.
dFFScanin-ducebitipsinRSApublickeysandfactorize99%oftheresulting2048-bitkeysgivenenoughRowhammer-inducedbitips.
Wefurthershowedthatwecouldfactor4.
2%ofthetwo4096bitUbuntuArchiveAutomaticSigningKeyswithabitip.
Thisallowedustogener-ateenoughtemplatestosuccessfullytrickavictimVMintoinstallingourpackages.
Forcompleteness,wealsoincludedaformalcryptanalysisofDife-Hellmanexpo-nentsinthepresenceofbitipsinAppendixA.
8ConclusionsHardwarebitipsarecommonlyperceivedasavehicleofproductionsoftwarefailureswithlimitedexploitationpowerinpractice.
Inthispaper,wechallengedcom-monbeliefanddemonstratedthatanattackerarmedwithFlipFengShui(FFS)primitivescanmountdevastat-inglypowerfulend-to-endattacksevenincompleteab-senceofsoftwarevulnerabilities.
OurFFSimplementa-tion(dFFS)combineshardwarebitipswithnovelmem-orytemplatingandmassagingprimitives,allowinganat-tackertocontrollablyseizecontrolofarbitraryphysicalmemorywithveryfewpracticalconstraints.
WeuseddFFStomountpracticalattacksagainstwidelyusedcryptographicsystemsinproductionclouds.
Ourattacksallowanattackertocompletelycompromiseco-hostedcloudVMswithrelativelylittleeffort.
Evenmoreworryingly,webelieveFlipFengShuicanbeusedinseveralmoreformsandapplicationspervasivelyinthesoftwarestack,urgingthesystemssecuritycommunitytodevoteimmediateattentiontothisemergingthreat.
DisclosureWehavecooperatedwiththeNationalCyberSecurityCentreintheNetherlandstocoordinatedisclosureofthevulnerabilitiestotherelevantparties.
AcknowledgementsWewouldliketothankouranonymousreviewersfortheirvaluablefeedback.
Thisworkwassup-portedbyNetherlandsOrganisationforScienticRe-searchthroughtheNWO639.
023.
309VICI"Dowsing"project,ResearchCouncilKULeuvenunderprojectC16/15/058,theFWOgrantG.
0130.
13N,andbytheEuropeanCommissionthroughprojectsH2020ICT-32-2014"SHARCS"underGrantAgreementNo.
644571andH2020ICT-2014-645622"PQCRYPTO".
References[1]DDR4Rowhammermitigation.
http://www.
passmark.
com/forum/showthread.
php5301-Rowhammer-mitigation&p=19553.
Accessedon17.
2.
2016.
[2]TroubleshootingMemoryErrors–MemTest86.
http://www.
memtest86.
com/troubleshooting.
htm.
Accessedon17.
2.
2016.
[3]DavidAdrian,KarthikeyanBhargavan,ZakirDu-rumeric,PierrickGaudry,MatthewGreen,J.
AlexHalderman,NadiaHeninger,DrewSpringall,Em-manuelThomé,LukeValenta,BenjaminVander-Sloot,EricWustrow,SantiagoZanellaBéguelin,andPaulZimmermann.
ImperfectForwardSe-crecy:HowDife-HellmanFailsinPractice.
CCS'15,2015.
[4]BarbaraP.
Aichinger.
DDRComplianceTesting-Itstimehascome!
InJEDEC'sServerMemoryForum,2014.
[5]AndreaArcangeli.
Transparenthugepagesupport.
KVMForum,2010.
[6]AndreaArcangeli,IzikEidus,andChrisWright.
IncreasingmemorydensitybyusingKSM.
OLS'09,2009.
[7]JEDECSolidStateTechnologyAssociation.
LowPowerDoubleData4(LPDDR4).
JESD209-4A,Nov2015.
[8]AntonioBarresi,KavehRazavi,MathiasPayer,andThomasR.
Gross.
CAIN:SilentlyBreakingASLRintheCloud.
WOOT'15,2015.
[9]DanBoneh,RichardA.
DeMillo,andRichardJ.
Lipton.
Ontheimportanceofeliminatingerrorsincryptographiccomputations.
J.
Cryptology,14(2),2001.
[10]ShekharBorkar.
DesigningReliableSystemsfromUnreliableComponents:TheChallengesofTran-sistorVariabilityandDegradation.
IEEEMicro,25(6),2005.
151625thUSENIXSecuritySymposiumUSENIXAssociation[11]ErikBosmanandHerbertBos.
Framingsignals—areturntoportableshellcode.
SP'14.
[12]ErikBosman,KavehRazavi,HerbertBos,andCristianoGiuffrida.
DedupEstMachina:MemoryDeduplicationasanAdvancedExploitationVector.
SP'16,2016.
[13]CyrilBouvier,PierrickGaudry,LaurentIm-bert,HamzaJeljeli,andEmmanuelThomé.
DiscretelogarithmsinGF(p)–180digits.
https://listserv.
nodak.
edu/cgi-bin/wa.
exeA2=ind1406&L=NMBRTHRY&F=&S=&P=3161.
June2014.
[14]EricBrier,BenotChevallier-Mames,MathieuCiet,andChristopheClavier.
WhyoneshouldalsosecureRSApublickeyelements.
CHES'06,2006.
[15]NicolasCarlini,AntonioBarresi,MathiasPayer,DavidWagner,andThomasR.
Gross.
Control-owBending:OntheEffectivenessofControl-owIn-tegrity.
SEC'15,2015.
[16]CristianConstantinescu.
TrendsandChallengesinVLSICircuitReliability.
IEEEMicro,23(4),2003.
[17]D.
Cooper,S.
Santesson,S.
Farrell,S.
Boeyen,R.
Housley,andW.
Polk.
RFC5280-Inter-netX.
509PublicKeyInfrastructureCerticateandCerticateRevocationList(CRL)Prole.
Techni-calreport,May2008.
[18]YvoDesmedt,PeterLandrock,ArjenK.
Lenstra,KevinS.
McCurley,AndrewM.
Odlyzko,RainerA.
Rueppel,andMilesE.
Smid.
TheEu-rocrypt'92ControversialIssue:TrapdoorPrimesandModuli(Panel).
Eurocrypt'92,1992.
[19]TheSageDevelopers.
SageMathematicsSoft-ware(Version).
http://www.
sagemath.
org.
Ac-cessedon17.
2.
2016.
[20]KarlDickman.
Onthefrequencyofnumberscon-tainingprimefactorsofacertainrelativemagni-tude.
ArkivforrMatematik,AstronomiochFysik,1930.
[21]WhiteldDifeandMartinE.
Hellman.
Newdi-rectionsincryptography.
IEEETransactionsonIn-formationTheory,22(6),1976.
[22]PaulErdsandMarkKac.
TheGaussianLawofErrorsintheTheoryofAdditiveNumberTheo-reticFunctions.
AmericanJournalofMathematics,62(1),1940.
[23]ChrisEvans.
ThepoisonedNULbyte,2014edition).
http://googleprojectzero.
blogspot.
nl/2014/08/the-poisoned-nul-byte-2014-edition.
html.
Accessedon17.
2.
2016.
[24]JustinN.
Ferguson.
Understandingtheheapbybreakingit.
InBlackHatUSA,2007.
[25]FrancescoGadaleta,YvesYounan,andWouterJoosen.
ESSoS'10,2010.
[26]DanielKahnGillmor.
pem2openpgp-translatePEM-encodedRSAkeystoOpenPGPcerticates.
Accessedon17.
2.
2016.
[27]GitHubDeveloper–PublicKeys.
https://developer.
github.
com/v3/users/keys/.
Ac-cessedon17.
2.
2016.
[28]SudhakarGovindavajhalaandAndrewW.
Appel.
UsingMemoryErrorstoAttackaVirtualMachine.
SP'03,2003.
[29]DanielGruss,DavidBidner,andStefanMangard.
PracticalMemoryDeduplicationAttacksinSand-boxedJavascript.
ESORICS'15.
2015.
[30]DanielGruss,ClementineMaurice,andStefanMangard.
Rowhammer.
js:ARemoteSoftware-InducedFaultAttackinJavaScript.
DIMVA'16,2016.
[31]DannyHarnik,BennyPinkas,andAlexandraShulman-Peleg.
SideChannelsinCloudServices:DeduplicationinCloudStorage.
IEEESecurityandPrivacyMagazine,specialissueofCloudSecurity,8,2010.
[32]GorkaIrazoqui,MehmetSinanIncI,ThomasEisenbarth,andBerkSunar.
KnowThyNeigh-bor:CryptoLibraryDetectioninCloud.
PETS'15,2015.
[33]VasileiosP.
Kemerlis,MichalisPolychronakis,andAngelosD.
Keromytis.
Ret2Dir:RethinkingKer-nelIsolation.
SEC'14,2014.
[34]YoonguKim,RossDaly,JeremieKim,ChrisFallin,JiHyeLee,DonghyukLee,ChrisWilker-son,KonradLai,andOnurMutlu.
FlippingBitsinMemoryWithoutAccessingThem:AnExperimen-talStudyofDRAMDisturbanceErrors.
ISCA'14,2014.
[35]ThorstenKleinjung,KazumaroAoki,JensFranke,ArjenK.
Lenstra,EmmanuelThomé,JoppeW.
Bos,PierrickGaudry,AlexanderKruppa,Pe-terL.
Montgomery,DagArneOsvik,Herman16USENIXAssociation25thUSENIXSecuritySymposium17J.
J.
teRiele,AndreyTimofeev,andPaulZimmer-mann.
Factorizationofa768-bitRSAmodulus.
CRYPTO'10,2010.
[36]DonaldE.
KnuthandLuisTrabb-Pardo.
AnalysisofaSimpleFactorizationAlgorithm.
TheoreticalComputerScience,3(3),1976.
[37]DmitriiKuvaiskii,RashaFaqeh,PramodBhato-tia,PascalFelber,andChristofFetzer.
HAFT:Hardware-assistedFaultTolerance.
EuroSys'16,2016.
[38]HendrikW.
Lenstra.
FactoringIntegerswithEllip-ticCurves.
AnnalsofMathematics,126,1987.
[39]DwayneLitzenberger.
PyCrypto-ThePythonCryptographyToolkit).
https://www.
dlitz.
net/software/pycrypto/.
Accessedon17.
2.
2016.
[40]FangfeiLiu,YuvalYarom,QianGe,GernotHeiser,andRubyB.
Lee.
Last-levelcacheside-channelat-tacksarepractical.
SP'15,2015.
[41]TarjeiMandt.
KernelPoolExploitationonWin-dows7.
InBlackHatEurope,2011.
[42]AlfredMenezes,PaulC.
vanOorschot,andScottA.
Vanstone.
HandbookofAppliedCryptog-raphy.
1996.
[43]R.
OwensandWeichaoWang.
Non-interactiveOSngerprintingthroughmemoryde-duplicationtechniqueinvirtualmachines.
IPCCC'11,2011.
[44]PeterPessl,DanielGruss,ClementineMaurice,MichaelSchwarz,andStefanMangard.
DRAMA:ExploitingDRAMAddressingforCross-CPUAt-tacks.
SEC'16,2016.
[45]StephenC.
PohligandMartinE.
Hellman.
AnimprovedalgorithmforcomputinglogarithmsoverGF(p)anditscryptographicsignicance(cor-resp.
).
IEEETransactionsonInformationTheory,24(1),1978.
[46]ShashankRachamalla,DabadattaMishra,andPu-rushottamKulkarni.
Share-o-meter:AnempiricalanalysisofKSMbasedmemorysharinginvirtual-izedsystems.
HiPC'13,2013.
[47]ParujRatanaworabhan,BenjaminLivshits,andBenjaminZorn.
NOZZLE:ADefenseAgainstHeap-sprayingCodeInjectionAttacks.
SEC'09,2009.
[48]KavehRazavi,GerritvanderKolk,andThiloKiel-mann.
PrebakeduVMs:Scalable,InstantVMStartupforIaaSClouds.
ICDCS'15,2015.
[49]RonaldL.
Rivest,AdiShamir,andLeonardM.
Adleman.
Amethodforobtainingdigitalsignaturesandpublic-keycryptosystems.
Commun.
ACM,21(2),1978.
[50]JurgenSchmidt.
JITSpraying:ExploitstobeatDEPandASLR.
InBlackHatEurope,2010.
[51]MarkSeaborn.
ExploitingtheDRAMRowhammerBugtoGainKernelPrivileges.
InBlackHatUSA,2015.
[52]Jean-PierreSeifert.
OnauthenticatedcomputingandRSA-basedauthentication.
CCS'05,2005.
[53]NoamShalev,EranHarpaz,HagarPorat,IditKei-dar,andYaronWeinsberg.
CSR:CoreSurpriseRemovalinCommodityOperatingSystems.
AS-PLOS'16,2016.
[54]PrateekSharmaandPurushottamKulkarni.
Sin-gleton:System-widePageDeduplicationinVirtualEnvironments.
HPDC'12,2012.
[55]AlexanderSotirov.
HeapFengShuiinJavaScript.
InBlackHatEurope,2007.
[56]KuniyasuSuzaki,KengoIijima,ToshikiYagi,andCyrilleArtho.
MemoryDeduplicationAsaThreattotheGuestOS.
EUROSEC'11,2011.
[57]PaulC.
vanOorschotandMichaelJ.
Wiener.
OnDife-Hellmankeyagreementwithshortexpo-nents.
Eurocrypt'96,1996.
[58]YuanzhongXu,WeidongCui,andMarcusPeinado.
Controlled-ChannelAttacks:DeterministicSide-ChannelsforUntrustedOperatingSystems.
SP'15,2015.
AppendixACryptanalysisofDife-HellmanwithBitFlipsThissectiondescribeshowonecanbreakDife-Hellmanbyippingabitinthemodulus.
SimilartoRSA,Dife-Hellmancryptosystemperformscomputationsmodulon.
IntheDife-Hellmankeyagreementscheme[21],however,themodulusnisprimeors=γ1=1.
Itisverycommontochoosestrongprimes,whichmeansthatq=(n1)/2isalsoprime;thisisalsotheapproachtakenbyOpenSSH.
Subsequentlyageneratorgischo-senoforderq.
IntheDife-Hellmanprotocoltheclient171825thUSENIXSecuritySymposiumUSENIXAssociationchoosesarandomx∈[1,n1]andcomputesgxmodnandtheserverchoosesarandomy∈[1,n1]andcom-putesgymodn.
Afterexchangingthesevalues,bothpar-tiescancomputethesharedsecretgxymodn.
ThebestknownalgorithmtorecoverthesharedsecretistosolvethediscretelogarithmproblemtondxoryusingtheGNFS,whichhascomplexityO(Ln[1/3,1.
92]).
Fora512-bitmodulusn,thepre-computationcostisestimatedtobeabout10core-years;individualdiscretelogarithmsmodncansubsequentlybefoundin10minutes[3].
Thecurrentrecordis596bits[13];again1024bitsseemstobewithinreachofintelligenceagencies[3].
Byippingasinglebitofn,thepartiescomputegxmodnandgymodn.
Itislikelythatrecoveringxoryisnowmucheasier.
IfweiptheLSB,n=n1=2qwithqprimeandgwillbeagenerator.
Intheothercasesnisat-bitor(t1)-bitoddinteger;weconjecturethatitsfactorizationhasthesameformasthatofarandomoddintegerofthesamesize.
Itisnotnecessarilythecasethegisageneratormodn,butwithveryhighprobabil-ityghaslargemultiplicativeorder.
ThealgorithmtocomputeadiscretelogarithminZntorecoverxfromy=gxmodnrequirestwosteps.
1.
Step1istocomputethefactorizationofn.
ThisisthesameproblemastheoneconsideredinSec-tion3.
2.
Step2consistsincomputingthediscretelogarithmofgxmodn:thiscanbedoneefcientlybycom-putingthediscretelogarithmsmodulogxmodpγiiandbycombiningtheresultusingtheChinesere-maindertheorem.
Notethatexceptforthesmallprimes,theγiareexpectedtobeequalto1withhighprobability.
Discretelogarithmsmodpγiicaninturnbecomputedstartingfromdiscreteloga-rithmsmodpi(γistepsarerequired).
Ifpi1issmooth(thatis,itisoftheformpi=∏rj=1qδjjwithqjsmall),thePohlig-Hellmanalgorithm[45]cansolvethisproblemintimeO∑rj=1δj√qj.
Ifnhasprimefactorspiforwhichpi1isnotsmooth,wehavetouseforthoseprimesGNFSwithcom-plexityO(Lpi[1/3,1.
92]).
TheanalysisisverysimilartothatofSection3,withasdifferencethatforRSAwecanuseECMtondallsmallprimefactorsuptothesecondlargestonep2.
Withasimpleprimalitytestweverifythattheremainingintegerisprimeandifsothefactorizationiscomplete.
How-ever,inthecaseofthediscretelogarithmalgorithmwehavetoperforminStep2discretelogarithmcomputa-tionsmodulothelargestprimep1.
Thismeansthatifnwouldprime(orasmallmultipleofaprime),Step1wouldbeeasybutwehavenotgainedanythingwiththebitipoperation.
Itisknownthattheexpectedbitlengthofthelargestprimefactorp1ofnis0.
624·t[36](0.
624isknownastheGolomb–Dickmanconstant).
AsecondnumbertheoreticresultbyDickmanshowsthattheprob-abilitythatalltheprimefactorspiofanintegernaresmallerthann1/uhasasymptoticprobabilityuu[20].
Fort=1024,theexpectedsizeofthelargestprimefactorp1ofnis639bitsandinturnthelargestprimefactorofp11isexpectedtobe399bits(1024·0.
6242).
Notethatp11canbefactoredefcientlyusingECMasintheRSAcase.
Ifp11has639bits,theproba-bilitythatitissmooth(sayhasfactorslessthan80bits)is88=224,hencePohlig-Hellmancannotbeapplied.
WehavetoreverttoGNFSfora399-bitinteger.
How-ever,withprobability22=1/4allthefactorsofnaresmallerthan512bits:inthatcasethelargestprimefac-torofp11isexpectedtobe319bits,butagainwithprobability1/4allprimefactorsaresmallerthan256bits.
Hencewithprobability1/16GNFScouldsolvethedis-cretelogarithminlessthan1corehour.
Fort=2048,theexpectedsizeofthelargestprimefactorp1ofnis1278bitsandthelargestprimefactorofp11isexpectedtobe797bits–thisiswellbeyondthecurrentGNFSrecord.
However,withprobability3·103=0.
037allprimefactorsofnaresmallerthan638bits.
Factoringp11isfeasibleusingECM,giventhattheitssecondlargestprimefactorisexpectedtobe134bits.
Thelargestprimefactorofp11isexpectedtobe398bits.
ThediscretelogarithmproblemmodulothelargestfactorcanbesolvedusingGNFSinabout1core-month.
Withprobability4·104=3.
9·103allprimefactorsofnaresmallerthan512bits,andinthatcasethelargestprimefactorofp11isexpectedtobe319bits,whichmeansthatGNFSwouldrequireafewcore-hours.
Evenifitwouldnotbefeasibletocomputethecom-pletediscretelogarithmtherearespecialcases:ifxoryhavesubstantiallyfewerthantbits,itissufcienttorecoveronlysomeofthediscretelogarithmsmodpiandthehardestdiscretelogarithmp1canperhapsbeskipped;formoredetails,see[3,57].
Themainconclusionisthatbreakingdiscreteloga-rithmswiththebitipattackismoredifcultthanfactor-izing,butfor1024bitsaninexpensiveattackisfeasible,whilefor2048bitstheattackwouldrequireamoderatecomputationaleffort,theresultsofwhicharewidelyap-plicable.
ItisworthnotingthatthisanalysisisapplicabletotheDHkeyagreementalgorithminusebyOpenSSH,defaultingto1536-bitDHgroupmoduliinthecurrentOpenSSH(7.
2),bitippedvariantsofwhichcanbepre-computedbyamoderatelyequippedattacker,andap-pliedtoallOpenSSHserverinstallations.
Theconse-quencesofsuchanattackaredecryptionofasession,includingthepasswordifused,addinganotherattractivefacettoattacksalreadydemonstratedinthispaper.
18