ABSTRACT Analysis of the SPV Secure Routing Protocol

AntonMityagin,SaurabhPanjwani,andBarathRaghavan

UniversityofCalifornia,SanDiego{amityagin,panjwani,barath}@cs.ucsd.edu

ABSTRACT

Weanalyzeasecureroutingprotocol,SecurePathVector(SPV),proposedinSIGCOMM2004.SPVaimstoprovideauthenticityforrouteannouncementsintheBorderGatewayProtocol(BGP)usinganefficientalternativetoordinarydigi-talsignatures,calledconstant-timesignatures.Today,SPViswidelyconsideredthebestcryptographicdefenseforBGP.WefindsubtleflawsinthedesignofSPVwhichleadtoat-tacksthatcanbemountedby60%ofAutonomousSystemsintheInternet.Inaddition,westudyseveralofSPV’sdesigndecisionsandassumptionsandhighlighttherequirementsforsecurityofroutingprotocols.Inlightofouranalysis,wereex-aminetheneedforconstant-timesignaturesandfindthatcer-tainstandarddigitalsignatureschemescanprovidethesamelevelofefficiencyforrouteauthenticity.

1.Introduction

Today’sInternetreliesuponasingleprotocol,theBorderGatewayProtocol(BGP),forwide-arearoutepropagation.Eachautonomoussystem(AS)summarizesitsnetworkasasetofIPprefixesandusesBGPtoinformotherASesofhowtoroutetotheseIPs.Numerousdocumented[18]andun-documentedattacksagainstBGPhighlighttheneedforrout-ingsecurity.IdealsolutionstosecureBGPshouldprotectagainstallknownattacks,beincrementallydeployable,andimposeminimalcomputationalandcommunicationoverheadforBGP-speakingrouters.Ofparticularinterestareprotocolstoproviderouteauthenticity—aguaranteethatallroutesad-vertisedbyallASescorrespondtorealpathsthroughthenet-worklearnedthroughrouteannouncements.

InSIGCOMM2004,Hu,Perrig,andSirbuproposedamechanismforsecuringBGPwiththesedesignconstraintsinmind[12].Theirprotocol,SecurePathVector(SPV),isuniqueinthatitaimstosimultaneouslyprovidestrongrouteauthenticityguaranteesandhighperformance—thisisincon-trasttoseveralotherproposalsforsecuringBGPthatareeithercomputationallyintensive[13]ordonotmakestrongclaimsaboutsecurity[22,23,24].Duetothesequalities,SPVhasenjoyedsubstantialinterestbothfromtheresearchcommunityandfromindustry,andisconsideredbymanytobethebestcryptographicdefenseforBGP[7];indeed,CiscoencouragedandsupportedthedevelopmentoftheSPVprotocol[8].Usinganovelcryptographicmechanisminvolvingconstant-timesig-

naturesandhashchains,thedesignersofSPVaimtopreventattacksinwhichamaliciousASpresentsforgedroutingup-datestoneighboringASesbyillegitimatelyalteringreceivedroutingmessages.Inaddition,SPVismoreefficientthanthesecure,butcomputationallyexpensive,S-BGPprotocol[13].InthispaperweshowthatitispossibletomountattacksonSPVwithhighprobability.WepresentsimplescenariosinwhichanadversarialASreceivesrouteannouncementscor-respondingtotwoormorepathstothesameIPprefixandcombinesthisinformationtoforgeanillegitimaterouteadver-tisement.Forexample,considertheAStopologiesshowninFigure1,whereanASAadvertisesarouteforanIPprefixtoitsneighbors;therouteeventuallypropagatestoamaliciousASMviatwodifferentpaths.Inthesescenarios,ourattacksenableMtoforgerouteadvertisementsfornon-existentpaths(shownbydottedlines).Suchsub-topologiesofASesoftenappearinpractice:ourexperimentsontheAS-levelInternettopologyfromCAIDA’sskitterproject[6]indicatethat60.4%ofallASesareinapositiontomountatleastoneoftheattacksshowninFigure1.

Indeed,itwaspartofSPV’sdesignobjectivetoprotectBGPfromarbitraryrouteforgeriesofthiskind.SecurityagainstsuchforgeriesisimportantinthecontextofBGP.ThoughrouterstypicallyselectshortASpaths,routeselectioninBGPisbasedoncomplexlocalpolicyoftenunrelatedtopathlength.Infact,localpolicyisgivenahigherprioritythanpathlengthintheBGPdecisionprocess[5];ASesoftenselectrouteswithlongerpathsandsometimesselectroutesbaseduponintermediateASnumbersinthereceivedpaths[10]1.Furthermore,BGPpoliciesarekeptconfidentialbymostASes,whichmakesitimpossibletoreasonaboutwhenaroutingprotocolisinvulnerabletocertainforgeries.Ingeneral,itismostdesirablethatprotocolsforsecuringBGPbedesignedwithoutanya-prioriassumptionsontherouteselectionprocess(aswasdoneinthecaseofSPV).

VARIANTSOFSPV.SPV’sunderlyingmechanismhastwovariants:thebasicASPATHprotectorandtheadvanced1

ModernroutersmakeiteasyforASestoimplementsuchpolicies.Forexample,inCiscoroutersthese-quenceofIOScommandsmatchas-path11,setlocal-preference100,andipas-pathaccess-list11permit1234resultsinsettingalocalpreferenceof100forroutescontainingASnumber1234anywhereintheASPATH.

CB(C,B,A)C(B,A)CD(D,C,B,A)BB(C,B,A)(M,B,A)D(M,D,B,A)BCV(M,C,B,A)(M,C,B,A)MA(A)M VA(A)MVA(A)MVA (A)(a)(b)(c)(d)

Figure1:ExampleAttackScenarios:AisthesourceAS,Mistheattacker,andVisthevictimAS,towhomMsendsforgedupdates.Dottedlinesindicatenon-existentroutesegmentsthatareforgedbyMinrouteadvertisementsitsendstoV.ASPATHprotector.ThebasicASPATHprotectorwasdesignedtopreventagainstacertainclassofforgeriesbutwasvulnerabletoattacksinsituationswherethemaliciousAShasmultipleroutestothesource(asinourexamplesabove).Inordertofixtheweaknessesinthebasicvariant(andmaketheprotocolsecureagainstallpossibleforgeryattacks),theauthorsofSPVmodifiedittoobtaintheadvancedASPATHprotector.OuranalysisofSPVuncoverssubtleflawsinthemechanismusedinthismodification.Weshowthattheadvancedprotector,whilemorecomplexandlessefficientthanitsbasicvariant,provideslittlesecurityimprovement.Inotherwords,theentireprotocolisassecureasitsbasicvariant.OTHERCONCERNS.Irrespectiveofcryptographicweak-nessesinSPV,wereconsiderseveralofitsdesigntradeoffsinSection5.Particularly,wefindthatconstant-timesignaturesmaynotbenecessaryforhighperformance,andthatSPV’sunderlyingattackmodelmaymakeitunsuitableforreal-worlddeployment.

2.Review

Inthissection,wereviewthesecurityneedsofBGPandthegoalsoftheSPVprotocol.

2.1Wide-arearoutingsecurity

TheBorderGatewayProtocol(BGP)isthesolemechanismforwide-arearoutedisseminationintheInternet.Routingex-istsontwoplanes:thedataplane—alongwhichpacketsareforwarded—andthecontrolplane—alongwhichroutesareup-dated.BGPoperatesonthecontrolplane—routersindifferentAutonomousSystems(ASes)useittodisseminateroutestoeachother.ThekeymechanismusedinroutedisseminationistheBGPUpdatemessage,whichcontainsinformationaboutanIPprefixandaroute,specifiedasanattributecalledAS-PATH,viawhichthatprefixisreachableinthenetwork.EachAS,uponreceiptofanUpdatemessage,canopttoprependitsASnumbertotheASPATHofthemessageand,inturn,sendanUpdate,containingtheprependedASPATH,toitsneigh-boringASes.Decisionsregardingrouteforwarding(whethertopropagatearoutetodownstreamASesortofilterit)andranking(choosingthebestrouteamongmultipleroutestothesameprefix)isgovernedentirelybylocalpolicyconfigura-tionsofASes.

TheproblemofsecuringBGPinthepresenceofmaliciouspartiespresentsmanychallenges,andrequiresaddressinga

widevarietyofattackscenarios.(See[3]forasurveyonthistopic.)Inthispaper,ourfocusisonaspecificclassofattacks,namely,thosethatinvolveforgeryofUpdatemessages.

InBGP,ASesareonlyallowedtoprependtheirASnum-bertotheASPATHattributeofalready-receivedUpdatemes-sages(orofmessagesoriginatebythem).PathforgeryreferstoanyattackinwhichamaliciousAS,sayM,violatesthisrequirement,thatis,createsanUpdatewhoseASPATHisnotobtainedbyprependingMtoASPATHsalreadyknowntoM(andconvincesanotherASofthevalidityofsuchanUp-date)2.Suchaviolationcanadverselyaffectthenormalex-ecutionofdownstreamASesand,consequently,oftheentireprotocol.Pathforgerycaninvolvetruncation(theattackerre-movessomeASnumbersfromareceivedASPATHandprop-agatestheresulting,shortenedpath),ormodification(theat-tackerchangesASnumbersonincomingASPATHsandfor-wardssuchmodifiedpaths),orboth.

2.2GoalsofSPV

SPVisaprotocolprimarilydesignedtoprotectBGPfromanypathforgeriesusingefficientsymmetrickeycryptogra-phy[12].SPV’sattackmodelconsiderssolitarymisbehav-ingASesthatattempttosubvertthenormalexecutionoftheprotocol;thatis,SPVassumesthatmultipleconspiringASescannotmountcoordinatedattacks.SPValsoassumesthatthelinksbetweenanytwoASesareprivateandauthenticated;thatis,theadversarialAScanneithereavesdroponnormakemod-ificationstoanycommunicationbetweentwootherdirectly-linkedASes.

3.DescriptionofSPV

Inthissection,wedescribetheSPVprotocolinbrief.Wehighlightthoseaspectsoftheprotocolwhicharemostrelevanttosecurityagainstpathforgeryattacks.

3.1Constant-timesignatures

Constant-timesignatureschemesarefundamentaltothede-signofSPV.Aconstant-timesignatureschemeisaweakerversionofastandardpublic-keysignatureschemeinwhichsecurityisguaranteedagainstanadversarywhocanacquirethesignaturesofonlyasmall(constant)numberofmessages.Forexample,inaone-timesignaturescheme,itishardtoforgesignaturesgivenonlyasingleexamplemessage-signaturepair,

2

Huetal.[12]usethetermfalsificationinsteadofforgery.

buttheschememaybeinsecuregivenmoresuchpairs.Ingeneral,anm-timesignaturescheme(forsomeconstantm)resistsforgeriesprovidedthatnomorethanmsignaturesforagivenkeyareknownbytheadversary.Suchsignatureschemestypicallyadmitmoreefficientimplementationsthanordinarypublic-keysignatures.

3.1.1M-HORSm-timesignatures

SPVusesamodifiedversionoftheHashtoObtainRandomSubsets(HORS)m-timesignaturescheme[21],whichinturnisanimprovementoftheBiBasignaturescheme[20].WerefertothismodifiedschemeasM-HORS(ModifiedHORS)anddescribeitbelow.(Figure2(a)illustratestheprocess.)Aswithanysignaturescheme,M-HORShasbothpublicandprivatekeys,wheretheprivatekeysareusedforsign-ingandthepublickeysareusedforverifyingsignatures.InM-HORS,keygenerationinvolveschoosingakeyKatrandomandgeneratingNvalues,v0,...,vN−1,witheachvi=FK(i),whereFisablockciphersuchasAESandNisasecurityparameter.Kservesasthesecretkeyofthesignatureschemeandthevi’sarecalledprivatevalues.

PrivatevaluesarehashedusingahashfunctionH(suchasSHA-1)intoNvaluesu0,...,uN−1,referredtoaspublicvalues:eachuiisequaltoH(vi).Finally,ahashtreeisbuilt,usingH,overthepublicvalues(thatis,withthesevaluesasleaves).Therootofthishashtree,R,isthepublickey.

TosignamessageM,thesigner(whoknowsthese-cretkeyand,thus,alltheprivatevalues)picksasetS={s1,s2,...,sn}ofnnumbersintherange0toN−1,basedonthevalueH(M);nisanothersecurityparameter.Thesig-natureofMconsistsoftwoparts:thesetofprivatevaluescorrespondingtosetS(thesetvS={vi}i∈S)andthesmall-estsetUofvaluesinthehashtreerequiredtoverifyvS(tocomputeRgivenvS).ToverifyasignatureonamessageM(whichconsistsofprivatevaluesvSandhashtreevaluesU),theverifierre-computesthehashtreebasedonthevaluesvSandUandthencomparestheroottothepublickeyR3.

Figure2(a)illustratesthiswithanexamplewhereN=4andn=2.SupposethatamessageMhashestoasetS={0,2}.ThesignatureofMconsistsofthesetofprivatevaluesvS={v0,v2}(blackdots)andthevaluesU={u1,u3}ofthehashtree(graydots).Toverifythesignature,onere-computesthehashtreeandchecksthattherootmatchesthepublickeyR.

3.2SPVsetup

AspartofsetupintheSPVprotocol,everyASAconstructsasequenceofsecretvaluess1,s2,...,sl(wherelequalsthelengthofthelongestpossibleAS-levelpaththatanyroutean-nouncementwilltraverse)usingaone-wayhashfunctionH1.Thatis,Apickss1atrandomandcomputessi+1=H1(si)fori=1,...,l−1.EachsiistreatedasasecretkeyoftheM-HORSschemeofSection3.1.Letpidenotethepublickeycorrespondingtothesecretkeysi.Aalsobuildsahashtree3

IntheoriginalHORSscheme[21],thesecretkeyconsistsofallprivatevaluesandthepublickeyofallpublicvalues;nohashtreeorPRFapplicationsareinvolved.SecurityisprovenundertheassumptionthatHsatisfiesthe“subset-resilience”property,introducedanddefinedin[21].

overthesepublickeysandtherootofthistreeislabeledR(thisnodeisusedintheverificationprocess).Theentireconstruc-tioniscalledthebasicASPATHprotector;anexamplewithl=4isshowninFigure2(b).InSPV,asinglefunctionHisusedforallhashoperations;soH1≡H.(WechoosetouseaspecialnotationforH1forreasonsthatwillbecomeclearinSect.4.)SPVsuggeststoinstantiateHwiththeMatyas,Meyer,andOseashashfunctionconstruction[16]usingtheAESblockcipher.

3.3Basicrouteforwarding

WefirstpresentasimplifiedversionofSPV’srouteforward-ing.UpdatemessagesinSPVinclude,besidestheusualat-tributesofBGPUpdates,signaturescreatedusingtheAS-PATHprotector.SupposethatAwantstosendanannounce-mentforaprefixtoaneighborB.Asignsthepath󰀊B,A󰀋usingthesecretkeys1togetasignatureσ1.ThenAsendsanUpdatemessagehavingASPATH=󰀊A󰀋,taggedwithσ1andthesecretkeys2,toB.

Onreceiptofthismessage,Bvalidatesitbyre-computingthewholeASPATHprotector.Namely,itfirstcomputesthese-cretkeyss3,...,slfroms2,usesthemtocomputethecorre-spondingpublickeysandthenre-computestherootpublickeyusingthepublickeysp1,...,pl(andmultipleapplicationsofH).Verificationconsistsofcomparingthere-computedrootpublickeywiththeoriginalrootpublickeyR,whichisas-sumedtobeknowntoallASes4.

Aftervalidatingthemessage,ifBdecidestoforwardin-formationaboutthepath󰀊B,A󰀋toaneighbor,sayC(basedonitslocalpolicies),itfirstsignstheASPATH󰀊C,B,A󰀋un-dersecretkeys2(usingM-HORS),thuscreatingasignatureσ2.TheUpdatemessagefromBtoCconsistsofASPATH=󰀊B,A󰀋,taggedwithσ1,σ2ands3.(Figure2(b)showsthesevalues;weusegraydotstorepresentthesignaturesσ1,σ2andablackdotforthesecretvalues3.)CvalidatesthemessageinthesamewayasB,whilealsoensuringthatthepathisloop-freeandthatBisthelastASintheASPATH.FurtherUpdatemessagesarecreatedandpropagatedsimilarly.

IfroutestoAarepropagatedalonganotherpath(say,AsendsanupdatetosomeASB󰀁andB󰀁forwardsittoanotherASC󰀁,andsoon),thesamechainofkeyss1,...,slisusedfortaggingthecorrespondingUpdates,whichmeansthatasecretkeysicouldbeknowntomultipleASesinthenetwork(inourexample,BandB󰀁bothpossesss2,s3,···andCandC󰀁bothpossesss3,s4,···).Thissharingofkeysisanunde-sirablefeatureofSPV,and,infact,itformsthebasisofallourattacks.

3.4Postmodification

ThefullSPVprotocolismoreinvolvedthanthebasicmech-anismpresentedabove.InordertocounterforgeriesthatcouldariseduetothesharingofkeysbetweenASes,theauthorsofSPVmodifythebasicASPATHprotector(Fig.2(b))intowhatiscalledtheadvancedASPATHprotector(Fig.2(d)).TheadvancedprotectorusesaslightvariantoftheM-HORS4

Infact,Rservesasashort-termpublickeyoran“epoch”publickeyandmultiplesuchpublickeysareauthenticatedus-inga“multi-epoch”publickey.Seetheoriginalpaperforde-tails[12].

RRU01U23U0U1U2U3p1p2p3p4V0V1V2V3Ks1s2s3s4(a)AM-HORSsignature

RU01U23(b)ThebasicASPATHprotector

RU0U1U2U3Public valuesSemi-Private valuesp1p2p3p4V0V1V2V3Private valuesKs1s2s3s4(c)M-HORSwithpostmodification(d)TheadvancedASPATHprotector

Figure2:Theuseofconstant-timesignaturesinSPV.

scheme:eachpublicvalueuiisobtainedbyhashingthecorre-spondingprivatevaluevitwiceratherthanonce,asshowninFigure2(c);thatis,ui=H(H(vi)).Theintermediatehashvalue,H(vi),isreferredtoasasemi-privatevalue.Signaturesarecreatedasinbasicforwarding,exceptthatnowanyparty,giventhesignatureonapath,canmodifyitby“degrading”someofthenrevealedprivatevaluestosemi-privatevalues(byapplyingHonceonthem).ThedegradedsignaturecanstillbeverifiedbutsincethefunctionHisassumedtobeone-way,noadversarycanrecovertheoriginalsignature.

Tounderstandhow“degrading”isusedinSPV,consideragainthethree-ASexamplefromtheprevioussubsection,asshowninFigure2(d).WhenAwishestosendanUpdatetoB,itsendsthesamemessage,taggedwithσ1ands2,asbefore.However,beforeforwardingtheannouncementtoC,Bmodi-fiesσ1bydegradingoneoftheprivatevaluescontainedinitto

󰀃C,B,A󰀄

getanewsignature,sayσ1;thisiscalledpostmodifica-tionofσ1.Theprivatevaluetodegradeisdeterminedbasedonthehashof󰀊C,B,A󰀋,H(󰀊C,B,A󰀋]).Themotivationforpost-modificationistopreventadownstreamAS,sayD,fromtrun-catingavalidrouteoftheform󰀊D,C,B,A󰀋to󰀊D,B,A󰀋evenwhenitknowss2(viasomeotherpath),sincethiswouldmost

󰀃C,B,A󰀄

likelyrequirerecoveringσ1fromσ1,which,essentially,meansinvertingthehashfunctiononasemi-privatevalue.WhenCforwardstheinformationabouttheroute󰀊C,B,A󰀋to

D,itmaydegradeanothervalueinσ1togetasignature󰀃D,C,B,A󰀄󰀃D,C,B,A󰀄σ1aswellassomevalueinσ2togetσ2.

Huetal.don’tlaydownanystrictrulesfordecidingwhichprivatevalueshouldbedegradedbasedonagivenhash.Inourattacks,weusethefollowingnaturalconvention:ifasignatureσcontainskprivatevalues(andn−ksemi-privatevalues)andaprivatevalueneedstobedegradedinσbasedonthehashh:=H(p)(pbeinganASPATH),thenthefirst󰀆log2(k)󰀇bitsofharemappedtoanumberi∈{1,2,···,k}andtheithprivatevalueischosenfordegrading.Inthesequel,weusethenotation[h]ktodenotethenumberiderivedfromthehashhinthismanner.Weremarkthatourattacksareindependentoftheconventionusedfordegrading;anyotherconventionwouldresultinthesame(orpossiblyworse)attackprobabilities.

󰀃C,B,A󰀄

3.5Concreteparameters

SPVusesaninstantiationofM-HORS(withpostmodifica-tion)suchthatitis15-timesecure.ThisisjustifiedsinceitisunlikelythatanyASintheInternetwillreceivemorethan15Updatesforthesameroute.15-timesecurityisachievedbysettingN(numberofprivatevalues)to256andn(numberofprivatevaluesrevealedpersignature)to6.Thevalueofl(lengthoftheASPATHprotector)ischosentobe14.Numer-ousparameters,denotedµ0≥µ1≥···≥µ14,governhowprivatevaluesaredegradedwhilerouting:whenasignatureσ

hastraversedihops,itcontainsµiprivatevaluesandn−µisemi-privatevalues.(Inourexample,theUpdatethatCsends

toDcontainsasignatureσ󰀃D,C,B,A󰀄

1,thathasµ2privatevalues,

andasignatureσ󰀃D,C,B,A󰀄

2,thathasµ1privatevalues.)Ingen-eral,anysignatureσp

icontainsµ|p|−i−1privatevalues.SPVsetsµ0=6,µ1=µ2=5andµ3=4.(Therestarenotrelevanttotheattacks).

4.Attacks

NextwepresentourattacksonSPV,allofwhichusethesamegeneralapproach:amaliciousASMreceivesUpdatemessagescorrespondingtotwopaths,p1andp2,originatedbyASA,withpathlengthsl1andl2respectivelysuchthatl2>l1.Mthenusesthesecretkeysl1+1(obtainedfromtheUpdatemessageforp1)to“signin”asuitably-chosenASintothelastpositionofp2.TheASnumbertoforgeisselectedinamannersuchthatthesignaturesreceivedalongp2canbeusedtoauthenticatetheforgedpathtothevictimAS.(Particularly,thiscanbedoneevenwithoutinvertingthehashfunctionHorbreakingM-HORS.)Usingthisapproach,Mcanperformavarietyofmodificationortruncationattacksonp2.

Werefertosuchattacksasmulti-pathforgeries.Aswewilldiscuss,inmostscenarios,thelongerthepathp2isthanp1,thegreaterthechanceofattacksuccess.Also,ifmorethanonepathlongerthanp1isavailable,theprobabilityofattackingallpathsincreases.

Figures1(a)and(b)showexampleattackscenariosinwhichtheforgeryisamulti-pathmodification;theseforgeriesaresuccessfulwithhighprobabilityifMhasasufficientnum-berofchoicesfortheASnumberDthatitwantstoforge.Figures1(c)and(d)showscenariosinwhichmulti-pathtrun-cationcanbecarriedout;thesecanoccurwithprobability1/6and1/5respectively.

ItisimportanttonotethatourattackssucceedagainstSPVeveninthepresenceofpostmodification.SPVusespostmod-ificationwiththesoleobjectiveofcounteringmulti-pathforg-eries;ourfindings,however,establishthattheprotocolisstillweakagainsttheseattacks.

4.1Multi-pathmodificationattacks

ConsiderthescenarioshowninFigure1(a).SupposeMreceivesUpdatescorrespondingtobothroutestoA:󰀊M,A󰀋and󰀊M,C,B,A󰀋.TheUpdatefor󰀊M,A󰀋containsthesecret

keys2;thatfor󰀊M,C,B,A󰀋containsasignatureσ󰀃M,C,B,A󰀄

1

onthemessage󰀊B,A󰀋.(Thissignatureis,infact,thesame

asσ󰀃C,B,A󰀄1sinceSPV’sparametersdictatethatthatµ1andµ2beequal.)Combiningthesetwopiecesofinformation,McansendtothevictimVavalid(yetforged)Updateforapathoftheform󰀊M,D,B,A󰀋.First,MselectstheASnumberDina

mannersuchthatσ󰀃C,B,A󰀄

1canbeusedtoobtainanotherpost-modifiedversionofσ1,namelyσ󰀃V,M,D,B,A󰀄1.Inotherwords,itpicksDsuchthattheprivatevaluedegradedwhilemodifying

σ1toσ󰀃C,B,A󰀄

1(basedonh1:=[H(󰀊C,B,A󰀋)]n)isthesameasoneofthetwovaluesthatwouldbedegradedwhilemod-ifyingσ1toσ󰀃V,M,D,B,A󰀄

1(basedonh2:=[H(󰀊D,B,A󰀋)]n

andh󰀁

2:=[H(󰀊V,M,D,B,A󰀋)]n−1).Thus,agoodchoice

forDisonethatensuresthateitherofthehashvaluesh2orh󰀁2equalsh1.OnceanASnumberDwiththispropertyhasbeen

chosen,Mcanmodifyσ󰀃C,B,A󰀄

1(bysuitablydegradingoneof

theprivatevaluesinit)togetσ󰀃V,M,D,B,A󰀄

1.Then,Musesthesecretkeys2(receivedvia󰀊M,A󰀋)toforgetheremainingsig-naturesfor󰀊M,D,B,A󰀋.

HowmanychoicesofDaregoodfortheattacktowork?Ifthehashfunctionisperfectlyrandom(whichis,infact,thehardestscenarioforourattacks),theprobabilitythath1equalseitherh2orh󰀁2foranyfixedvalueofDisexactly2/n=2/6=1/3.Thisprobabilityisobtainedusingaslightlystrongerassumption,namelythatthemapfromAS-PATHstoelementsin{1,···,n}usedinSPVisperfectlyrandom.ThismeansthatoutofallpossiblechoicesforD,sayx,aboutx/3wouldbeeffectiveintheattack.

Pathlengtheningattackscanbemountedsimilarly.Con-siderthescenarioshowninFigure1(b)andsupposethatMwishestolengthenthepath󰀊M,B,A󰀋toadvertiseanew(forged)path󰀊M,C,B,A󰀋.IfMreceivesUpdatemes-sagesfromboth󰀊M,A󰀋and󰀊M,B,A󰀋,thiscanbeachievedquiteeasily.Theformercontainsthesecretkeys2(fromwhichotherkeyss3,s4,...canbecomputed)andthelat-tercontainsthesignatureσ󰀃M,B,A󰀄

1on󰀊B,A󰀋whichispost-modifiedbyBaccordingtoh1:=[H(󰀊M,B,A󰀋)]n.TheUpdatemessagefor󰀊M,C,B,A󰀋senttoVshouldcontain

asignatureσ󰀃V,M,C,B,A󰀄

1

,postmodifiedaccordingtoh2:=[H(󰀊C,B,A󰀋)]nandtoh󰀁2:=[H(󰀊V,M,C,B,A󰀋)]n−1.Asinthepreviousattack,McancreatesuchasignatureifCisselectedtoensureh1∈{h2,h󰀁2},whichoccurswithproba-bilityatleast1/3.So,ifMhasxdifferentchoicesfortheASnumberC,thenaboutx/3ofthemworkfortheattack.

4.2Multi-pathtruncationattacks

Wenowshowthefeasibilityofmulti-pathtruncationat-tacksagainstSPV.ConsiderthescenarioinFigure1(c)(thesameasthatinFigure1(a)).Wearguethatinthissetting,McanconvinceVoftheASPATH󰀊M,B,A󰀋(whichdoesn’texistinthenetwork)withprobability1/6.M’saimisto

beabletoforgeσ󰀃C,B,A󰀄

1

—thepostmodificationofA’ssigna-tureon󰀊B,A󰀋,σ1—asadifferentpostmodificationσ󰀃M,B,A󰀄

1

ofthesamesignature.AsufficientconditionforthisisthatH(󰀊M,B,A󰀋)selectsthesamevaluetodegradeinσ1asdoesH(󰀊C,B,A󰀋).Theprobabilitythatthisconditionistrueisatleast1/n=1/6.(Itisexactly1/nifthemapfromASPATHstotheset{1,···,n}isperfectlyrandom.)ThismeansthatofallpossiblesubgraphsoftheAS-levelInternettopologyofthekindillustratedinFigure1(c),atleast1/6willsuccumbtothisattack.

IfthedifferencebetweenthelengthsofthepathsbywhichMislinkedtoAisgreaterthan2,thechanceofsuc-cessisgreater.Figure1(d)showssuchascenario—twopathsconnectingMtoAare󰀊M,A󰀋and󰀊M,D,C,B,A󰀋.ThemessagefromAcontainss2asbeforewhilethatfrom

Dcontainsσ󰀃M,D,C,B,A󰀄

1.Thehopenowisthatthevalue

[H(󰀊M,D,C,B,A󰀋)]5(whichdetermineshowσ󰀃C,B,A󰀄

1is

postmodifiedtoσ󰀃M,D,C,B,A󰀄

1)equals[H(󰀊V,M,C,B,A󰀋)]5.Thishappenswithprobability1/5sincethereare5private

valuesinσ󰀃C,B,A󰀄oneisdegradedtogetσ󰀃M,D,C,B,A󰀄

1(and1).

Intheevaluationofpostmodificationwithrespecttomulti-pathtruncationattacks,Huetal.presentseveralattackproba-bilitiesforparticularscenariosintheInternet’sAS-leveltopol-ogy[12];toourknowledge,theydonotconsidertheattackscenarioswepresent.Ourattacksshowthatpostmodifica-tioncanmitigatetheriskofmulti-pathforgeriesonlytoaverysmallextent,byreducingattackprobabilitiesbyasmallcon-stantfactor.

4.3Topologicalanalysis

Tounderstandthefeasibilityofourattacks,weperformedseveralsimulationstodeterminehowoftensubgraphssuchasthoseinFigure1appearintheInternet’sASconnectivitygraph.ToensurethattheASgraphweconsideredreflectedrealInternetpaths,weoptedtouseASconnectivityextractedfromCAIDA’sskitterproject[6];thisdatareflectsactualpathsratherthanadvertisedroutes.WetreatedeachASasanodeandeachvisibleASconnectionasanedgeinagraph;weperformedadepth-limitedbreadth-firstsearchfromeachnodeandcountedthenumberoftimesthatoneofourattacksce-nariosappearedasasubgraph.Fromthis,wedeterminedthat60.4%ofallASesareinapositiontomountatleastoneoftheattacksshowninFigure1.

4.4Attacksummary

WestressthatthesusceptibilityofSPVtoourattacksisnotbasedonweaknesses,ifany,intheunderlyingcryptographicprimitives,butratherinthemannerinwhichtheseprimitivesarecomposedinSPV.Forexample,ourattacksneverusethefactthattheM-HORSschemeinuseis15-timesecureratherthansecureinthestandardsenseofdigitalsignatures;infact,theattacksneverinvolveforgingasignatureforanunknownkey.

OurtechniquescanbeeasilygeneralizedtoascenarioinwhichthemaliciousASMreceivesUpdatesforseveral(morethantwo)pathstoA(ofvariouslengths)anditsgoalistoforgeUpdatesbyillegitimatelymodifyingsomereceivedpath.ThetechniquesarenotapplicableinthespecificcasewhereinMwantstoattack(thatis,modifyortruncate)onlythesingleshortestreceivedpath;SPVmaybesecureagainstsuchat-tacks.However,rigorouslyarguingaboutSPV’ssecurityevenagainstsuchspecificattacksisdifficult.Forexample,hashchainsareusedintheASPATHprotectorinanon-standardmanner:eachsecretvaluesiinthehashchainisusednotonlyasaninputtoahashfunctionbutalsoforsigningmessages(inM-HORS),whichcouldaffectthesecurityofboththehashchainandthesignaturescheme.Itiscommonlyacceptedthatasinglekeyshouldnotbeusedasinputtomultiplecrypto-graphicoperations.Inprinciple,itispossibletoinstantiatethehashfunctionH1usedinthehashchainandM-HORSinawaysuchthattheformerisone-wayandcollision-resistant,thelatterisasecurem-timesignatureschemeandstill,anat-tackerwhoisgivenonlyH1(sj),isabletosuccessfullyforgesignaturesundersj.

WhileitispossibletofixthisparticularweaknessinSPV’sdesignquiteeasily5,suchafixwouldstillnotrecoversecurity5

Onepossibleimplementationwouldbetoreplacethehashchainwithkeysgeneratedusingaforward-securepseudo-againstourforgeryattacks.ModifyingSPV’sconcreteparam-eterscandolittletoimproveitssecurity,butcansignificantlydecreaseefficiency:wecouldincreasethevalueofntoreducethesuccessprobabilityinourattacks,butthatwouldrequireraisingNtomaintainsecurityofM-HORS.Thus,webelievethatthedesignoftheASPATHprotector(withorwithoutpost-modification)isunsuitabletopreventagainstpathforgeries,andmustbereplacedifstrongsecurityagainstforgeryattacksisdesired.

5.Discussion

ThusfarwehavedetailedseveralspecificweaknessesofSPV’sASPATHprotector.WhilethesealoneindicatethatSPVisunsafefordeployment,wealsoconsideramoreholis-ticviewofSPVnext,andreconsiderseveralofSPV’sdesigndecisions.

5.1

Reconsideringtures

constant-timesigna-Inthepast,protocolssuchasS-BGPusedasymmetricsig-naturesschemestoprovidestrongunforgeability;unfortu-nately,thiscomesatthepriceofhighcomputationaloverhead.Motivatedbythisbottleneck,Huetal.useconstant-timesig-naturesinSPVduetotheirsignificantlybetterperformance.Irrespectiveoftheirsecurity,M-HORSandotherconstant-timesignatureschemestradeoffcommunicationoverheadforthisspeedup.ThiswasaknownconsequencetoSPV’sdesign-ers;SPVincursanetworkbandwidthoverheadthatisafactor2.731greaterthanthatofS-BGP[12].

Inpractice,itmaybeacceptabletotradeoffbandwidthforperformance.Unfortunately,anotherhiddentrade-offofus-ingsuchsignatureschemesistheirimplementationcomplex-ity.Unlikeseveralasymmetricsignatureschemesthatareselfcontainedandstandardized,M-HORSisnotstandard,anditsuseinSPVisintegraltotheASPATHprotector.

Furthermore,theparametersforM-HORSusedinSPVtradeoffsecurityforspaceandperformance,withnaturalcon-sequences:(i)brute-forceforgeriesinSPVcanbecarriedoutwithprobabilityashighas2−22byanyadversary(whoisgiven15signaturesunderthesamesigningkey)6;and(ii)duetolimitsonthesizeofBGPUpdatemessages,atmost14M-HORSsignatures(usingthesuggestedparameters)canbecommunicatedinanysinglemessage.Thatis,SPVcanrandomgenerator(FS-PRG)[1].Thiswouldsimultaneouslyguaranteethe“one-wayness”propertyrequiredbytheappli-cationandpreservethepseudorandomnessofthekeys(whichisneededforM-HORStobesecure).Krawczyk’sapproachtobuildingforward-securesignatures(FSS)[14]usesthesameideas;indeed,itmightbepossibletoexploitspecificconstruc-tionsofFSSschemestogetmoresecuredesignsfortheAS-PATHprotector.6

ThisforgeryprobabilitypresentedinSection5.1.1oftheoriginalSPVpaper[12]isbasedontheassumptionthatthehashfunctionusedinM-HORSbehavesasaperfectlyran-domfunction.ThisassumptionisstrongerthanthatusedtoprovesecurityofM-HORSintheoriginalpaperofReyzinetal.[21],wherethehashfunctionisassumedtosatisfyonlysubset-resilience(aweakerpropertythanthatofbeingaper-fectlyrandomfunction)

onlyauthenticaterouteswithlessthan14hops.Whilethislatterconstraintisminor—fewInternetpathsarelongerthan14hops—itsconsequenceinthedesignofSPVismoreim-portant:SPVmust,byitsconstruction,computeahashchainandcorrespondingM-HORSsignaturesforall14hops(evenifthepathinquestionisonly,say,2hops)becausethepub-lickeymustbecomputedoverthelongestpossibleASPATHprotector.

Asaresultofthisbandwidthincrease,itisnaturaltoconsidersignatureaggregationschemes,sinceithasbeenshown[25]thatusingsuchtechniques,thecommunicationoverheadofS-BGPcanbereducedtoalmostconstant(asop-posedtolinear)inthelengthoftheASPATHbeingsigned.Unfortunately,unlikethoseproposedforRSA-basedsignatureschemes[15],therearenoknownsignatureaggregationtech-niquesforconstant-timesignatureschemes.

InsteadofattemptingtoremedythissituationbytweakingM-HORSortheASPATHprotector,webelievethatproto-coldesignersshouldreconsidertheuseofconstant-timesig-natures.OneoftheprimarymotivationsfortheuseofM-HORSinSPVwasitsperformance.However,wenotethattherearesignatureschemesthataresecureinthestandardsenseandaresimultaneouslymoreefficientthanthosemostcommonlyused.OnecandidateistheESIGNschemeofOkamotoetal.[11,19].ESIGNisaconventionalsignatureschemethatissignificantlyfasterthanandhascomparablese-curitytoRSA—astudyconductedaspartoftheCRYPTRECprojectbyMenezesetal.foundthatESIGNandRSAprovidethesamesecurityatequalkeylengths[17]—thoughitdoesnotdoubleasapublic-keyencryptionschemeasRSAdoes.7ApreliminaryexperimentalanalysisindicatesthatusingES-IGN,itmaybepossibletoachieveefficiencybetterthanthatoftheinstantiationofM-HORSusedinSPVwhilealsoassuringmuchbettersecurity.InTable1,weconsidertheefficiencyof15-timesecureM-HORSasusedinSPVandconventionaldig-italsignatureschemes.Weobtainedthesebenchmarksusingastandardcryptographiclibrary,Crypto++5.2.1[9],onaPen-tium42.8GHzmachineusingGCC4.0withstandardcom-pileroptimizations(-O2)enabled.WebrieflyconsiderhowtouseESIGNtobuildafastBGPsecurityprotocolinSection6.

5.2CollusionandEavesdroppingAttacks

SPV’sattackmodelassumesthatmultiplemaliciousASesdonotcolludewitheachotherinanattempttoperformforg-eries.Whilethismayholdforsomesubsetofdeployments,thisassumptiondoesnotcorrespondwellwithpracticalthreatstoBGP.Forexample,thereareseveralinstancesinwhichnu-merousASesareownedandoperatedbyasingleorganizationandsuchASescantriviallymountcoordinatedattacksontheprotocol.(EvenifsuchASeswerenotthemselvesmalicious,iftheirrouterswerecompromised,anattackercouldwieldsub-stantialpower.)Bycolluding,ASescansharekeys,signatures,andanytopologicalinformationthattheyknow.Suchanex-changeispotentiallyusefultoforgeroutesthatarecompletelynon-existentinthenetwork.

CollusionattacksaresimpletomountagainstSPV.Forex-7

ESIGNwaspatentedin1986byNTT;however,thispatenthasrecentlyexpiredandtheschemeisnowunencumbered.

OperationTimeAES(perblock)0.287µsecM-HORS(1278AEScalls)366µsec1024-bitESIGN(sign/verify)469µsec/175µsec2048-bitESIGN(sign/verify)1131µsec/457µsec1024-bitRSA(sign/verify)6172µsec/185µsec2048-bitRSA(sign/verify)34482µsec/472µsecTable1:ComparisonofM-HORSandstandarddigitalsig-natures.InSPV,M-HORSisalwayscalledonceforeachhopintheASPATHprotector,whichisofafixedsize;thedefaultis14.ESIGN,incontrast,wouldonlyneedtobecalledonceperactualhopintheASPATH,whichisusu-allymuchlessthan10.

ample,itispossiblefortwomaliciousASesM1andM2(thatarecolludingwithoneother)tointroduce(or“sandwich”)ar-bitraryASnumbersbetweenthemselvesandtopropagateAS-PATHsoftheform󰀊M1,X,M2,∗󰀋evenwhenXisnotcon-nectedtoeitherM1orM2.Notethatsuch“sandwiching”attacksdonotworkagainstS-BGP[13],soBGP[24],orps-BGP[23],whichrequirethateveryASsignUpdatesusingitsownsecretkey(andnotasecretkeysenttoitbyaneighbor).Whilesuchcollusionattackswereexpectedtobepossi-blebySPV’sdesigners,anotherassumptioninSPV’smodelismoreinsidious:itsrelianceonencrypted,authenticatedAS-to-ASchannels.Clearly,ifSPVisimplementedwith-outsecureAS-to-ASlinks,anyeavesdroppercanusethese-cretkeyssentbetweenASestoitsadvantageandforgeal-mostarbitraryASPATHs.CombinedwithaTCPhijackingattack[2],amaliciousentityeavesdroppingonalink(A,B)couldevenconvinceanotherASXofthevalidityoftheAS-PATH󰀊X,Y,B,A󰀋whereYisaneighborofX,eventhoughthereisnosuchpath—again,suchattacksarenotpossibleagainstotherprotocols[13,23,24]becausetheydonotsendsecretkeysbetweenASes.Huetal.[12]suggestthatapro-tocollikeIPSecbeusedtosecureAS-to-ASchannels.Thisrequirementseemsreasonable,butwenotethatittoohasasubtleconsequence:AS-to-ASauthenticationandkeydistri-butionarerequired.AnimportantdesigngoalofSPVwastosimplifykeymanagement.Unfortunately,asaresultofIPsec,ASesmustperformpairwiseauthenticationwitheachneighborandestablishasecretkey,andthus,fortier1ISPs,thiswouldrequirethousandsofsecurityassociations.Alter-natively,theycouldhavesimplyreceivedauthenticatedpublickeysforthousandsofotherASesandusedS-BGP.

6.Futuredirections

Inthispaper,wehavepresentedasecurityanalysisoftheSPVprotocol[12]forsecuringBGP,andhaveuncoveredat-tacksthatwebelieveshouldbeguardedagainstbeforeSPVisconsideredfordeployment.InlightofouranalysisofSPVanditsuseofconstant-timesignatures,webelievethatasimplestepcanbemadetoimproveSPV,albeitinitscurrentrestrictedsecuritymodel.Particularly,wecanmodifyanalternativepro-

tocolsuggestedbyHuetal.(thatcombinedelementsofSPVandS-BGPtoincreasethedeployabilityofS-BGP[12])asfollows.Insteadofusingahashchain,wecanuseacertifi-catechainofdigitalsignaturesthatisgeneratedon-the-flytoproviderouteauthenticity;eachASgeneratesanasymmetrickeypairforthenexthopandcertifiesthepublickey.Sincethesekeypairsarerelativelyshortlived,1024-bitESIGNismorethansufficient;2048-bitESIGNcanbeusedforlongerlivedprefixkeys.Suchaprotocolwouldhavesuperiorsecu-rityandperformancetoSPV.

WhileitmaybepossiblepatchSPVinthismanner,webe-lieveroutingsecuritymustbeformalizedusingappropriatecryptographicdefinitionstoenableanalysisofthesecurityofexistingprotocols,includingSPV.Despitetheextensiveliter-atureonsecuringBGP,thereseemstohavebeenlittleworkonthissubject(thoughButty´anetal.havetakenasteptowardtheprovablesecurityofad-hocwirelessroutingprotocols[4]).Thisgapmayexistduetotheinherentdifficultyofmodel-ingBGPsecurityaccurately.Forexample,cooperationbe-tweenmultiplemaliciousASescannotbeneglected:inprac-tice,sincesomeorganizationspossessmultipleASnumbers,collusionbetweenASesistrivial.Furthermore,ASescannotbetreatedasatomicroutingentities,asmostASesarecom-posedofmanyrouters,eachadvertisingdifferentBGProutestoneighbors.Whiletheseareonlyexamplesofcomplicatingfactors,theyindicatethatdevelopinganadequatemodelofroutingsecurityisalargetaskinitself,thoughsuchamodelisnecessaryifwearetohaveconfidenceinsecureroutingpro-tocolsinthefuture.

7.References

[1]M.BellareandB.Yee.Forwardsecurityinprivatekey

cryptography.InProceedingsofCT-RSA,Apr.2003.[2]S.M.Bellovin.Securityproblemsinthetcp/ipprotocol

suite.ComputerCommunicationsReview,2(19):32–48,19.

[3]K.Butler,T.Farley,P.McDaniel,andJ.Rexford.A

surveyofBGPsecurity:Issuesandsolutions.TechnicalReportTD-5UGJ33,ATTResearch,Apr.2005.[4]L.Butty´anandI.Vajda.Towardsprovablesecurityfor

adhocroutingprotocols.InProceedingsofACMSASN,Oct.2004.

[5]M.CaesarandJ.Rexford.BGProutingpoliciesinISP

networks.TechnicalReportUCB/CSD-05-1377,UniversityofCalifornia,Berkeley,Mar.2005.

[6]CAIDASkitterProject.http://www.caida.org/

tools/measurement/skitter/.

[7]H.Chan,D.Dash,A.Perrig,andH.Zhang.Modeling

adoptabilityofsecureBGPprotocols.InProceedingsofACMSIGCOMM,Sept.2006.

[8]CiscoSystems.Personalcommunication,Apr.2006.[9]Crypto++library.http://www.eskimo.com/

˜weidai/cryptlib.html.

[10]N.Feamster.Personalcommunication,Oct.2005.

[11]A.Fujioka,T.Okamoto,andS.Miyaguchi.ESIGN:An

efficientdigitalsignatureimplementationforsmartcards.InProceedingsofEUROCRYPT,Apr.1991.

[12]Y.-C.Hu,A.Perrig,andM.Sirbu.SPV:securepath

vectorroutingforsecuringBGP.InProceedingsofACMSIGCOMM,Sept.2004.

[13]S.Kent,C.Lynn,andK.Seo.Securebordergateway

protocol(S-BGP).IEEEJournalonSelectedAreasinCommunications,18(4),2000.

[14]H.Krawczyk.Simpleforward-securesignaturesfrom

anysignaturescheme.InProceedingsofACMCCS,Nov.2000.

[15]A.Lysyanskaya,S.Micali,L.Reyzin,andH.Shacham.

Sequentialaggregatesignaturesfromtrapdoor

permutations.InProceedingsofEUROCRYPT,May2004.

[16]S.Matyas,C.Meyer,andJ.Oseas.Generatingstrong

one-wayfunctionswithcryptographicalgorithms.IBMTechnicalDisclosureBulletin27:5658-5659,1985.[17]A.Menezes,M.Qu,D.Stinson,andY.Wang.

Evaluationofsecuritylevelofcryptography:Esignsignaturescheme.CRYPTRECProject,Japan,Jan.2001.

[18]O.Nordstr¨omandC.Dovrolis.Bewareofbgpattacks.

SIGCOMMCCR,34(2),2004.

[19]T.OkamotoandJ.Stern.Almostuniformdensityof

powerresiduesandtheprovablesecurityofESIGN.InProceedingsofASIACRYPT,Nov.2003.

[20]A.Perrig.TheBiBaone-timesignatureandbroadcast

authenticationprotocol.InProceedingsofACMCCS,Nov.2001.

[21]L.ReyzinandN.Reyzin.BetterthanBiBa:Short

one-timesignatureswithfastsigningandverifying.InProceedingsofACSIP,July2002.

[22]L.Subramanian,V.Roth,I.Stoica,S.Shenker,and

R.Katz.Listenandwhisper:SecuritymechanismsforBGP.InProceedingsofUSENIX/ACMNSDI,Mar.2004.

[23]T.Wan,E.Kranakis,andP.vanOorschot.Prettysecure

BGP(psBGP).InProceedingsofISOCNDSS,Feb.2005.

[24]R.White.SecuringBGPthroughSecureOriginBGP

(soBGP).TheInternetProtocolJournal,Sept.2003.[25]M.Zhao,S.W.Smith,andD.M.Nicol.Aggregated

PathAuthenticationforEfficientBGPSecurity.InProceedingsofACMCCS,Nov.2005.