Identity-based Access Control for Ad Hoc Groups

AdHocGroups󰀁

NiteshSaxena,GeneTsudik,JeongHyunYi󰀑󰀑

SchoolofInformationandComputerScience

UniversityofCaliforniaatIrvine

Irvine,CA92697,USA

{nitesh,gts,jhyi}@ics.uci.edu

Abstract.Theproliferationofgroup-centriccomputingandcommuni-cationmotivatestheneedformechanismstoprovidegroupaccesscontrol.Groupaccesscontrolincludesmechanismsforadmissionaswellasrevo-cation/evictionofgroupmembers.Particularlyinadhocgroups,suchaspeer-to-peer(P2P)systemsandmobileadhocnetworks(MANETs),securegroupadmissionisneededtobootstrapothergroupsecurityser-vices.Inaddition,securemembershiprevocationisrequiredtoevictmisbehavingormaliciousmembers.Unlikecentralized(e.g.,multicast)groups,adhocgroupsoperateinadecentralizedmannerandaccommo-datedynamicmembershipwhichmakeaccesscontrolbothinterestingandchallenging.Althoughsomerecentworkmadeinitialprogressasfarastheadmissionproblem,themembershiprevocationproblemhasnotbeenaddressed.

Inthispaper,wedevelopanidentity-basedgroupadmissioncontroltech-niquewhichavoidscertaindrawbacksofprevious(certificate-based)ap-proaches.Wealsoproposeacompanionmembershiprevocationmech-anism.Oursolutionsarerobust,fullydistributed,scalableand,atthesametime,reasonablyefficient,asdemonstratedbytheexperimentalre-sults.

Keywords:accesscontrol,ad-hocgroupsecurity,thresholdsignatures

1Introduction

Adhocgroupsarebecomingincreasinglypopularthesedays.Anumberofpeer-to-peer(P2P)systemsaswellasmobilead-hocnetworks(MANETs)fallintothecategoryofadhocgroups.Thesegroupsarecharacterizedbytwoimportantfeatures,(1)lackoftrustedauthorityand(2)dynamicmembership,whichoftenimpliesdynamictopology.Thesefeaturespromptanumberofchallengesforroutingaswellascontentplacementandretrieval.Theyalsomakeitdifficulttodevelopeffectiveandefficientsecuritymechanisms.Theneedforsecurityin

MANETsandP2Phasbeenwidelyrecognizedbytheresearchcommunityandthebulkofpriorworkhasbeeninthecontextoftraditionalsecurityservicessuchassecuregroupcommunication(groupkeyagreementandkeymanagement)andsecurerouting(inMANETs).Althoughtheseservicesarecertainlyimportant,anotherequallyimportantissue–groupaccesscontrol–hasnotreceiveddueattention.

Inagroupsetting,thetraditionalnotionofaccesscontrolistopreventunauthorizedentitiesfromaccessinggroupresources.However,ifweconsidergroupmembershipitselftobearesource,theproblemofadmissionandrevo-cation/evictionofgroupmemberscanbeviewedasaformofaccesscontrol.Asecureadmissioncontrolisnecessarytopreventunauthorizedusersfromjoin-ingagroup,i.e.,accessingthe“membership”resource.Withoutsuchamech-anism,groupmembershipisopentomalicioususersandthegroupbecomesvulnerable,e.g.,toSybilattacks[1].Moreover,agroupasawholemustbeabletocontendwiththepossibilityofgroupmembersbecomingselfish1orma-licious/compromised.Oncedetected,suchroguemembersneedtoberemovedfromthegroup.Thisnecessitatessecure(andefficient)membershiprevocationmechanisms.

Withouteffectivegroupaccesscontrolmechanisms,othergroupsecurityser-vices:securegroupcommunication[2,3]andsecurerouting(inmobileadhocnetworks),suchasAriadne[4],SPINS[5],etc.,aredifficulttoachieve.

Onefairlyobviousapplicationforthetypeofsecuredistributedgroupac-cesscontrolthatweenvisageisinthedomainofprivateP2Pgroupsformedatopwide-open(essentiallypublic)P2Psystems,suchasKazaa,MorpheusorGnutella.Infact,arecentarticleintheTimeMagazine[6]examinesthepopulartrendofcreatingso-called“Darknets”[7]–secureprivategroupswithinKazaaandMorpheus–inordertoescapetheintensifiedcrackdownonmusicandothercontentsharing.Anotherexampleofasomewhatfuturistic,militaryorientedapplicationofgroupaccesscontrolinamobileadhocnetworkwithunmannedaerialvehicles(UAVs)isdescribedin[8].

2RelatedWorkandMotivation

Previousworkonadmissioncontrolinadhocgroups([9],[10],[11],and[12])em-ployedamenuofcryptographictechniquestoperformsecuregroupadmission.Thepurposeisforacertainthresholdofgroupmemberstomakecollabora-tivedecisionsregardingtheadmissionofaprospectivememberandprovideitwithasignedgroupmembershipcertificate.Amongthesesignatureschemesare:plain(RSAorDSA)signatures,accountablesubgroupmulti-signatures(ASM)[13],thresholdsignatures([14],[9]).Unfortunately,theseschemeshavecertaindrawbacksthatmakethemunfitforpracticalgroupadmissioncontrolscenarios.

Lineageproblemwithplainsignaturesandmultisignatures.Inparticu-lar,admissioncontrolbasedoneitherplainsignaturesoraccountablesub-groupmultisignatureshasalineageproblem.Thisproblemoccurswhenamembershipcertificateisissuedtoanewmember:eachmember(sponsor)whotakespartintheadmissionprocessneedstoconfirm(bysigning)itsagreementtoadmitthisnewmember.Essentially,amembershipcertificatehastobesignedbysomenumberofmembershipsponsors.2However,eachsponsorneedstoattachitsowncertificatetoitssignatureonanewmember’scertificateinordertomakegroupcertificatesuniversallyverifiable.However,asponsor’sowncertificatealsohastobecounter-signedbyitserstwhilesponsors,andsoon,andsoforth.Thisisclearlyunworkablesinceamember’scertificatewouldhavetobeaccompaniedbyanumberofcertificatechainsthataffirmitslineage.

InapplicabilityofknownthresholdRSAsignatures.A(t−1,n)thresholdsignaturescheme[15]enablesanysubgroupoftmembersinagrouptocollabora-tivelysignamessageonbehalfofthatgroup.Thisisachievedbysecret-sharingthesignaturekeyamongthegroupmembers,andallowingthemtocomputeasignatureonsomemessageviaadistributedprotocolinwhichthemembersusethesharesofthesignaturekeyinsteadofthekeyitself.Thresholdsignaturesarenaturallyattractiveforthepurposeofadmissioncontrolsincetheypreventtheaforementionedlineageproblem:amembershipcertificatecanbesignedbyanyset(ofacertainsize)ofsponsorswhilethesignaturelengthisconstantandidentitiesofindividualsponsorsarenotrevealed.

VariousflavorsofthresholdRSAsignaturesexistinliteraturethatmightbeusedtoconstructtheadmissioncontrolprotocol.However,unfortunately,noneoftheseschemesaredirectlyapplicable(referto[16]fordetails).

InanefforttomitigatetheaboveproblemoftheknownthresholdRSAsignatures,Kong,etal.[9]proposedanewthresholdRSAscheme,gearedtowardprovidingsecurityservicesinmobilead-hocnetworks.SubsequentlytheschemeanditsMANETapplicationsweredescribedin[9,8],andmostrecentlyinajournalversion[17].Unfortunately,thisschemeisneitherrobust(i.e.itcannottoleratemaliciousgroupmembers)norsecure.Therobustnessproblemwasfirstpointedoutin[12].Foranexplicitattackexploitingtheinsecurityofthescheme,thereaderisreferredto[18]

LimitationofthresholdDSAsignature.Analternativescheme(calledTS-DSA)[12]isbasedonthethresholdDSSsignaturescheme[19].Thisschemeisrobustandhencetoleratesmaliciousinsiders.However,thepracticalityofthisschemeisquestionablesince,asillustratedbyexperimentsin[11],itisverycostlyduetoO(t2)communicationamongthetsigners.Furthermore,TS-DSAremainssecureaslongastherearelessthan󰀍t+1

2

Thisnumberisdeterminedbythegroupadmissionpolicy;commonexamplesareacertainfractionofcurrentmembersorafixedthreshold.See[10]foradetaileddiscussionofadmissionpolicies.

3

OurContributions.Inadditiontotheabovediscussion,thepreviouslypro-posedadmissioncontrolmechanismsarecertificate-based,makingthemquiteimpractical3formobileadhocnetworkswheretheamountofcommunicationisdirectlyrelatedtothebatterypowerofthemobiledevices(referto[20]).Inthispaper,wedevelopanewgroupadmissioncontroltechnique,whichwerefertoasID-GAC(IDentity-basedGroupAdmissionControl).Asthenamesuggests,ID-GACisanidentity-basedapproach(andthereforemorecommuni-cationefficient),incontrasttoprevious,certificate-basedschemes.Furthermore,wepresentamembershiprevocationmechanismgearedtoworkinconjunctionwithID-GAC.

Organization.AfterspecifyingthenotationinTable1,wedefinethesecuritymodelforagenericgroupaccesscontrolsysteminSection3.InSections4and5,wepresentthenewID-basedadmissioncontrolprotocolanddemonstrateitssecurity.Section6presentsthemembershiprevocationprotocols.Experimen-talresultsareillustratedinSection7andfinally,someoutstandingissuesarediscussedinSection8followedbytheconclusioninSection9.

Table1.Notation

MitnAeˆSKiSi(m)SLissipssj(i)

IDforMi

revocationthreshold

cyclicGDHgroupsoforderqgrouppublickey

membershiptokenforMipublickeyofMi

membershiprevocationlist

hashfunc.suchasSHA-1orMD5hashfunc.s.t.H1:{0,1}∗→G∗1

hashfunc.s.t.H2:{0,1}∗×G1→Z∗q

3SecurityModel

Inthissection,wedefineagenericsecuritymodelforpeer-basedmembership

management.Inotherwords,wedescribewhatwemeanbysecureadmissioncontrolandsecuremembershiprevocation,respectively.Sincethisworkisap-pliedinnature,themodelisspecifiedinformally.3.1

AdmissionControl

Asecureadmissionmechanismisasecureinteractiveprotocolbetweenaprospec-tivememberMnewandasetofcurrentgroupmembers{Mi|1≤i≤s}where

1≤t≤s≤n.(Inotherwords,thenumberofcurrentmemberstakingpartintheadmissionisatleastthenumbernecessaryfortheadmissionthresholdwhichis,inturn,nogreaterthanthenumberofcurrentmembers.)Thisprotocolmustsatisfythefollowingproperties:

1.Completeness.Whentheprotocolcompletes(inpolynomialtime),Mnew

hasagroupmembershiptoken,ifatleasttoutofngroupmembersvoteinfavorofadmission.Inaddition,Mnewalsoacquiresthemembershipre-vocationinformationifany,whichallowsittokeeptrackofrevokedgroupmembers.Optionally4,Mnewisalsoinpossessionofameanstotakepartinfutureadmissiondecisions.

2.Traceability.Ifoneormoremalicioussponsorsdonotprovidecorrectinformationinthecourseoftheadmissionprocess,Mnewcandetect,traceandpubliclyidentifysuchmembers.5

3.ImpersonationResistance.Itiscomputationallyinfeasibleforanyone,whohasnotbeensuccessfullyadmittedviatheadmissionprotocol,toim-personateagenuinegroupmember(whethertomembersornon-members).3.2

MembershipRevocation

Asecuremembershiprevocationmechanismisaprotocolamongthemembersofthegroupwhereinanysetoftr(≥t)membersattempttorevokeacurrentmemberMrwhopossessesamembershiptokenTrand/orasecretsharessr.Thismechanismneedstosatisfythefollowingproperties:

1.Completeness.Attheendofthisprotocol,i.e.whentrrevocationrequestsarelodgedagainstMr,thelatterisunableto:(1)provegroupmembershipand(2)participateinfutureadmissiondecisions(incaseMrpreviouslyhadvoting/admissionrights).

2.ImpersonationResistance.Onlyagenuinegroupmember(possessingavalidmembershiptoken)cantakepartintherevocationprocess.Inotherwords,non-groupmembersandpreviouslyrevokedgroupmemberscannotlodgevalidrevocationrequests.

3.CollusionResistance.Attheendoftheprotocol,Mr(ifshepossessedasecretshare)isunabletocollaboratewithanysetofpreviouslyrevokedmembersandrecoverthegroupsecretx.Inotherwords,anysetofrevokedshare-holdingmemberscannotcolludetointerpolatethegroupsecret.Remark:AswillbediscussedinSection6,everygroupmembermaintainsanupdatedlistoftherevokedmemberswhichwerefertoasmembershiprevocationlist(MRL).

4ID-basedGroupAdmissionControl(ID-GAC)

Inthissection,wepresentournewadmissioncontrolmechanismID-GAC.Themechanismisbasedonthethresholdversion[21]ofBLSsignaturescheme[22].Thedescriptionincludes:set-up,admissionprocessandsecurityargumentsfol-lowingthemodelinSection3.ID-GACisanidentity-basedmechanismsincethemembershiptokenusedtoprovemembershipisderivedfromthegroupmember’sidentity.4.1

Setup

ID-GACcanbeinitializedbyeither:(1)atrusteddealeror(2)agroupof2t−1ormorefoundingmembers.Ineithercase,thedealerfirstinitializesandgeneratestheappropriateellipticcurvedomainparameters(p,Fp,a,b,A,q).Theellipticcurveisrepresentedbytheequation:y2=x3+ax+b.G1issettobeagroupoforderqgeneratedbyA,G2isasubgroupofF∗ˆ:G1×G1→G2p2oforderq,ande

isdefinedtobeapublicbilinearmapping.Also,H1:{0,1}∗→G∗1isthehashfunctionthatmapsbinarystringstonon–zeropointsinG1.Allofthisinformationispublishedandallgroupmembers(aswellasprospectivemembers)areassumedtohaveaccesstoit.

Initializationbydealer.TDselectsarandompolynomialf(z)=f0+f1z+···+ft−1zt−1overZqofdegreet−1,suchthatthegroupsecretisf(0)=f0=x.Inordertoenableverifiablesecretsharing(VSS)[23],TDcomputesandpublishesthewitnessesWi=fiAfor(i=0,···,t−1).ThewitnessvalueW0=xA,alsodenotedbyB,isactuallythegrouppublickey.Next,foreachMi,TDcomputesthesecretsharessiandtheidentity-basedmembershiptokenTi(validuntilthetimeexp6)suchthat:ssi=f(idi)(modq)andTi=xH1(idi||exp).NotethatTDisnotrequiredhereafter.

Self-initializationbyfoundingmembers.tormorefoundingmembersMi-sselectindividualpolynomialsfi(z)overZqofdegreet−1,suchthatfi0=xi.Then,usingtheDKGprotocol[24],eachMicomputesitsownsecretsharessi,

󰀁l

suchthatssi=j=1fj(idi)(modq)(l≥2t−1).OnceMigetsitsshare,itisrathereasytorecoverthesecretusingLagrangeinterpolation.Also,thedealingprocesssupportsVSS.Now,inordertoprovideeachmemberwithamembershiptoken,anysetoftfoundingmembersmustcollaborate.Forexample,group

membersM2,M3,···,Mt+1maycollaborateandprovideM1withamembership󰀁t+1

tokenasT1=j=2(ssjlj(0))H1(id1||exp)[=xH1(id1||exp)].4.2

AdmissionProcess

Letn(≥t)bethenumberofcurrentgroupmembers.Inordertobeadmittedtothegroup,aprospectivememberMnewmustcollectatleasttvotesfromcurrentgroupmembers.Figure1showsprotocolmessageflowsfortheadmissionprocess.ThegoalisforMnewtoobtainamembershiptokenTnewwhichcanthenbeusedtoprovemembership.(Inpractice,Mnewalsoneedstoobtainthecurrentmembershiprevocationlist–MRL–tokeeptrackofrevokedgroupmembers.)

REQ=idnew,m,Snew(idnew,m)

idi,Si(idi,H(REQ))

1:Mnew2:Mnew3:Mnew4:Mnew

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−→←−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−→←−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

Fig.1.ID-GACProtocol

Tj(new),[pssj(new)],Sj(Tj(new),SLnew,[pssj(new)])

SLnew,Snew(SLnew)

MiMiMjMj

1.Mnewsendsasignedjoinrequestmessagemaswellasitsidentityidnewto

atleasttcurrentgroupmembers7.

2.Groupmemberswhowishtoparticipateintheadmissionreplywiththeirrespectiveid-stoMnewalongwiththesignatureonthepreviousmessagesentbyMnew.

3.Mnewpicks(perhaps,atrandom)tsponsorsMj-s,formsasignerlistSLnew

whichcontainstheid-softresponders,signsit,andsendsittoeachMj.4.EachsigningmemberMjsendsbacktoMnewthepartialmembershiptokenTj(new)and(optionally)thepartialshareofthesecretpssj(new)suchthat

Tj(new)=(ssj·lj(0))H1(idnew||exp)

and

pssj(new)=ssj·lj(idnew)+rj(modq)

t󰀃x−idi

where,lj(x)=

i=1

7

Inordertosecuretheprotocolagainstcommonreplayattacks[25],wenotethatitisnecessarytoincludetimestamps,noncesandprotocolmessageidentifiers.However,inordertokeepourdescriptionsimple,weomitthesevalues.

7

canderivessjfrompssj(new).Thiscanbepreventedusingtheshufflingtechniqueproposedin[9]byaddingextrarandomvaluerj-stoeachshare.Theserj-saresecretrandomvaluesandmustsumuptozerobyconstruction.TheymustbesecurelysharedamongthetsponsoringMj-s.

5.Finally,Mnewcalculatesitssecretsharessnew(ifprovided)andthemem-bershiptokenTnewbyaddingupthevaluesobtainedinthelaststep.Theshareacquisitionandmembershiptokenacquisitionproceduresarediscussednext.4.3

MembershipTokenAcquisition

Themembershiptokenacquisitionprocedureisalsoperformedaspartofthe4-thmessageoftheaboveprotocol.EachsponsorMjcomputesapartialmembershiptokenTj(new)forMnewandthensendsittoMnew.(ItisimportanttonotethatthepartialmembershiptokenTj(new)isactuallyaBLS[22]signatureonidnewusing(ssj·lj(0))asthesecretkeyforMj.)Then,MnewcomputesitsmembershiptokenTnewbysummingupTj(new)(j=1,···,t)andverifiesthecorrectnessbycheckingeˆ(B,H1(idnew||exp))=eˆ(A,Tnew).Thisequationcanbeeasilyshowntobecorrectusingthepropertiesofthebilinearmapeˆ.4.4

ShareAcquisition

Theshareacquisitionprocedure–wherebyMnewobtainsitssharessnewfromsponsors–isperformedaspartofthe4-thmessageintheID-GACprotocol(asshowninFigure1).

Thetsponsoringmembers(Mj-s)computetheshuffledpartialsharepssj(new)forMnewaspssj(new)=ssj·lj(idnew)+rj(modq)usingtheshufflingtech-nique[9].EachMjsendspssj(new)toMnew.Then,Mnewcomputesitssharessnewbysumminguppssj(new)(j=1,···,t)andverifyingthecorrectnessusingVSS[23].

Byverifyingthesecretshareandthemembershiptokenasdescribedabove,Mnewisassuredofpossessingcorrectcredentials.ArmedwiththemembershiptokenTnew,Mnewcanprovemembership.Also,usingasecretsharessnew,Mnewcanusethegroupsecretxincollaborationwithother(t−1)groupmembersandtakepartinfutureadmissionprotocols.InSection5,wediscusstwoschemesthatcanbeusedtoprovemembership.

Next,wediscussthesecurityoftheproposedID-GACscheme.4.5

SecurityConsiderations

Inthissection,wearguethesecurityoftheproposedscheme,basedonthesecuritymodelofSection3.

1.Completeness.Thispropertyfollowsbyinspection.Attheendoftheprotocol,MnewreceivesthemembershiptokenTnewwhichisverifiedas:

8

eˆ(B,H1(idnew||exp))=eˆ(A,Tnew).UsingTnew,Mnewcanprovemember-ship.MnewalsoreceivesasecretsharessnewwhichisverifiedusingVSS󰀁t−1

as:ssnewA=i=0idnewiWi.Usingssnew,Mnewcantakepartinfutureadmissiondecisionsandcanalsorecoverthegroupsecretxincollaborationwithanyothert−1members.Ofcourse,Mnewcanobtainthesecredentialsinpolynomialtime.

2.Traceability.IncasetheverificationofTnewand/orssnewfails,Mnew

mustidentify(trace)sponsorsthatsentinvalidpartialtoken(s)and/orpar-tialsecretshare(s).Toverifyeachpartialsecretshare,MnewcanperformtheVSSprocedure.CorrectnessofeachmembershiptokenshareTj(new)canbeverifiedasfollows:

t−1󰀂

eˆ(Tj(new),A)=eˆ(H1(idnew||exp),lj(0)idjiWi).

i=0

Iftheaboveverificationfails,MnewconcludesthatMjischeating.

3.ImpersonationResistance.InordertomakesurethatMnewiscommuni-catingwithonlygenuinegroupmembers,itcanverifythepartialcredentialsasintraceabilityaboveandintheprocesscantraceanyimpersonatingnon-member.

5ProvingMembership

Weemploytwoschemesthatcanbeusedbyagroupmembertoprovemem-bership.Weconsiderprovingmembershiptointernalparties(members)andexternalparties(non-members).Theinternalmembershipproof(IMP)isapairing-basedsecrethandshakeschemeproposedin[26].Theexternalmember-shipproof(EMP)istheidentity-basedsignatureschemeinGDHgroupsasproposedin[27].

6MembershipRevocation

Inadditiontoimplicitlyrevokingmembershiptokensviaexpiration(seefootnote6),roguemembersneedtobeexplicitlyrevoked,e.g.,forreasonsofselfishness,maliciousnessorcompromise.

Asecuremembershiprevocationmechanismshouldsatisfyallpropertiesout-linedinSection3.2.Onetrivialsolutionistohaveasetoftshareholdinggroupmembers(revokers)collaborateandrenewmembershiptokensforallmembers,excepttheonebeingrevoked.Therevokersalsoneedtoupdatethesecretsharesusingproactivityincasetherevokedmemberpossessedanoldshare.Thisap-proachisclearlyveryinefficient.

InthissectionwepresentapracticalrevocationmechanismbasedonMem-bershipRevocationLists(MRLs).Thisisanalogoustothesimpleandwide-spreadcertificaterevocationtechnique(CRLs[28])usedintraditionalPKIs.However,unlikeCRLs,oursolutionisfullydistributed.

9

6.1MRLUpdate

Uponeveryrevokeoperation,eachgroupmemberneedstoupdateitscopyoftheMRL.Also,anentryneedstoberemovedfromtheMRLoncethecorrespondingmember’smembershiptokenexpires.6.2

MembershipValidation

IfandwhenauserVreceivesasignedmessagefromanotheruserMuclaimingtobethegroupmember(ofagroupwithpublickeyB),VneedstofirstverifythevalidityofMu’smembershipandthenthesignature(usingEMPsignatureverfication).Thevalidationprocedureswillbedifferent(internalorexternal)basedonwhetherVisagroupmemberoranon-member.

InternalMembershipValidation.IfVisagroupmember,validationinvolvesonlyalookupofitsMRLandcheckingthestatusofMu.IfMRLcontainsnoentrycorrespondingtoidu,VconcludesthatMuisamemberingoodstanding.ExternalMembershipValidation.Annon-memberVneedstoperformthefol-lowingprotocoltovalidateMu’sstatus.

1.VsendstothegroupamembershipvalidationrequestforMu’smembership.2.Shareholdinggroupmembersinterestedinansweringthisrequest,replywiththeirIDstoV.

3.Vwaitsforatleasttsuchresponses,createsasigners’listSLvcontainingtheIDsoftheinterestedmembersandsendsittothem.

4.ThesemembersthenlookupthestatusofMuintheirrespectiveMRLsandprovideVwithasignedresponse.

5.VverifiesthesignatureonthestatusofMu.

Theabovevalidationprocedureisquitesimilartotheadmissionprocessde-scribedinSection4.2.Moreover,itcouldalsobeviewedasadistributedversionoftheOnlineCertificateStatusProtocol(OCSP)[29]inthecontextofcertificaterevocation.6.3

RevocationProcess

TorevokeanallegedlymaliciousormisbehavingmemberMr,anycurrentmem-berMacanbootstraptherevocationprocess.Thefollowingstepsneedtobeperformed.

1.MabroadcastsarevocationrequestmessagereferencingMr,usingEMPsignaturegeneration.

10

2.AllothergroupmembersMj-s(j=r)performtheinternalmembershipvalidationforMaasinSection6.2.8TheythenperformtheMRLupdate(asdiscussedinSection6.1)toaddMatotherevokerlistforMr.ThestatusofMristhensetto“under-review”.Oncethenumberofrevokersinthislistreachtr,thestatusofMrisupdatedto“revoked”.

ˆ(th)(tˆ≤t−1)membertoberevoked9,thetrrevokerscollaborate3.IfMristhet

andupdatethesharesusingtheproactivemethod.Iflessthantoutoftrrevokerspossessedthesecretshares,thegroupfoundingmembersneedtoperformtheshareupdate.

4.AllavailablegroupmembersMi-s(i=r)possessingvotingrights,thencontacttherevokers(orfoundingmembers)andrenewtheirshares.6.4

SecurityConsiderations

Inthissection,wearguethattheaboverevocationmechanismissecurebasedonthesecuritymodelsketchedinSection3.2.

1.Completeness.Byinspection:AssoonastrvalidrevocationrequestsarelodgedagainstMr,eachgroupmemberrecordstheminitslocalcopyoftheMRLandsetsthestatuscorrespondingtoidras“revoked”.Now,MrcannotprovemembershipviaeitherIMPorEMPprotocoland/ortakepartintheadmissionprocesssinceitsmembershipvalidation(asdescribedinSection6.2)wouldfail.

2.ImpersonationResistance.AspartofStep1oftherevocationprocessabove,arevocationrequestsubmittedbyMaagainstMrissignedusingEMPsigning.Uponreceivingsucharequest,eachgroupmember(exceptMa)firstvalidatesMa’sstatusbydoinganMRLlookupandthenvalidatesMa’smembershipbyverifyingthesignatureontherequestmessage(viaEMPverification).TheformerguaranteesthatMaisitselfnotrevokedandthelatterensuresthatMaisindeedagroupmember.Therefore,itisimpossibleforarevokedmemberandcomputationallyinfeasibleforanon-membertolodgevalidrevocationrequests.Thus,theproposedrevocationmechanismisimpersonationresistant.

3.CollusionResistance.Therevocationprocedureinvolvesthesecretshareupdatesatleastaftereveryt−1membersarerevoked.Therefore,theshareofthetthrevokedmemberwillnotcorrespondtothesharesoft−1pre-viouslyrevokedmembersinyieldingthegroupsecretusingthepolynomialinterpolation.Thisimpliesthatnosetofrevokedmemberscancollude.6.5

Discussion

TheMRL-basedsolutionrequiresgroupmemberstosynchronizeinordertomaintainup-to-dateMRLs.However,itiscertainlyunrealistictoexpectall

memberstobeonlineallofthetime.AnymembercanestablishthefreshnessofitsMRLbyperformingaproceduresimilartomembershipvalidation(inSection6.2).Asetoftinterestedmembers(possessingthesecretshares)respondwiththecompleteandsignedMRL,asopposedtothemembershipvalidationprocedure,wheretheyrespondwiththestatusofaparticularmember.Thisprocedurecanalsobeperformedperiodically.

DiscrepanciesinMRLsmightariseforanumberofreasons.Agroupmembermightgooff-lineorbecomeunreachabletemporarily.Sucheventsarecommoninasynchronousgroups,suchasmostP2PsystemsandMANETs.Moregenerally,agroupcanbecomepartitionedduetosomenetworkevent,e.g.,arouterfailure.SupposeapartitionoccursandagroupissplitintotwosubgroupsGAandGB.ThetwosubgroupsoperateindependentlyandtheirMRLsevolveseparately.Ifatalatertime,GAandGBmergebackintoasinglegroup,thetwoMRLs:MRLAandMRLB,needtobeappropriatelymerged.Thisparticularscenariopresentsamajorchallengesincethetechniquesdescribedabovewillnotwork.Considerwhathappensif,whilethegroupispartitioned,membersofGAdecidetorevoketheircounterpartsinGB,andviceversa.(Notsurprisingly,thisremainsamajoritemforfuturework.)

7PerformanceAnalysis

Wenowpresentanddiscusstheperformancemeasurementresultsforthepro-posedID-GACadmissionandevictiontechniques.Inparticular,wedescribeourexperiencewiththeimplementationoftheseschemesandexperimentsinP2PandMANETsettings,focusingontherespectivecostsofadmission,trace-ability,membershipproofsandrevocation.WealsocompareourresultswiththepreviouslyproposedDSA-basedadmissionmechanism[12],[11],whereverapplicable.7.1

Implementation

TheID-GAClibraryisbuiltusingOpenSSL[30]andMIRACL[31](optimizedusingCombamethod)libraries.Thelatterwasneededtoimplementvariousidentity-basedfunctions.Currently,ID-GACconsistsofapproximately10,000linesofC/C++sourcecodeandsupportsLinux2.4.

WeusedtheellipticcurveEdefinedbytheequation:y2=x3+1overFpwithp>3aprimesatisfyingp=2(mod)3andqbeingaprimefactor10ofp+1.Thesizeofqissettobe160bitsandpisa512-bitprime.ThegroupG1isasubgroupofpointsgeneratedbyAsuchthatA∈E(Fp).ThegroupG2isasubgroupofF∗ˆ:G1×G1→G2isthewell-knownp2oforderq.Thebilinearmape

Tatepairing.Notethatthepairingvaluebelongstofinitefieldof1024bits.

7.2BasicOperations

ToestimatetheperformanceofID-GAC,wefirstpresentthecostsoftheprim-itiveoperationsinTable2.FormeasuringthecostsofbasicoperationsinID-GAC,weusedamachinewithanIntelP3800MHzprocessorand384MBmem-ory.Allexperimentswererepeated1,000timesforeachmeasurementinordertogetfairlyaccurateaverageresults.

Table2.CostsofPrimitiveOperations(P3-800MHz)Function

10241024512512512

exponent(bits)

4.785.743.138.9137.24

7.3ExperimentalSetup

WenowdescribetheexperimentalsetupusedfortheexperimentsinbothP2P(Gnutella[32])andMANETsettings.WeusedtwolaptopsandtwoPDAs,eachconfiguredwith802.11binad-hocmode.Forroutingpurposes,weusedtheOptimizedLinkStateRoutingProtocol(OLSR)[33].Thetwolaptops(runningLinux2.4)areequippedwith800/900-MHzP-IIIprocessorsand384/256MBRAM,respectively.ThetwoPDAs(runningLinuxFamiliar)eachhavea400MHzXSCALEprocessorand64MBRAM.Inallexperiments,weranequalnumberofprocesses(currentgroupmembers)onboththelaptops.ThePDAswereusedforroutingpurposesonly.

NotethatbothP2PandMANETexperimentsweredoneontheequipmentwithsamecomputingpower.ThemainpurposeofourexperimentsistomeasurethecomputationandcommunicationcostsinwirelessaswellaswirednetworksandtodemonstratethepracticalityofID-basedadmissionandrevocationmech-anisms.ForID-GACexperiments,themodulussize(|p|)wassetto512-bitsand1024-bitmoduluswasusedforTS-DSAexperiments11.

Remark:Inallexperimentsbelow,weusedamember/authorizerparadigm.Amember,inthiscontext,isagroupmemberwhohasnovoting/admissionrights(i.e.,nosecretshare),whereasanauthorizerhasthem.Sincetheirrespectivecostssometimesvarysubstantially,theyaregraphedseparately.

7.4NodeAdmission

Figure2showstheadmissioncostwithvaryingthreshold(forbothmemberandauthorizer)forID-GACandTS-DSAschemesin(a)MANETand(b)Gnutellaexperiments.Theadmissioncostsalsoincludetheverificationofthemembershiptokenand/orthesecretshare.

AsshowninFigure2,ID-GACexhibitsappreciablybetterperformancethatTS-DSAinMANET,aswellasinP2Psetting.TheresultsimplythattheamountofcommunicationinTS-DSAcontributessignificantlytotheoverallcostofadmission,althoughcomputation-wiseitisstillquiteefficient(seeTable2).ThecommunicationoverheadforTS-DSAisevenhigherinMANET,thaninGnutellaexperiments.Thisisclearlyduetotheerror-prone,low-bandwidthwirelesschannel.

6 3.5TS-DSA (authorizer) 5TS-DSA (member)ID-GAC (authorizer)ID-GAC (member) 4 3TS-DSA (authorizer)TS-DSA (member)ID-GAC (authorizer)Average Processng Tme (seconds)Average Processng Tme (seconds) 2.5ID-GAC (member) 2 3 1.5 2 1 1 0.5 0234567Admission Threshold (t)8910 0234567Admission Threshold (t)8910(a)MANET

Fig.2.NodeAdmissionCost

(b)Gnutella

7.5BandwidthConsumption

Table3comparestherespectivebandwidthcosts.(RefertoTable1fornotation.)WhileTS-DSAusescertificates,ID-GACisidentity-basedwhichobviatesanyneedforexplicitmembershipcertificates.Certificatesizeisrelativelylarge,e.g.,5KBwith1024-bitDSAparameters.Forexample,ifaprospectivememberwantstojointhegroupasamember,(2t−1)∗5K∗8bitsmustbetransfered,whereas,onlyt∗512bitsareneededinID-GAC.

Table3.BandwidthComparison

Admission(member)

(2t−1)∗|GMCj|+t∗|pssj|

ID-GACt∗|Tj|

bitnumbers,intermsofbatterypowerconsumption[20].Forexample,incaseoft=3,thebandwidthcostwithTS-DSAisabout133timeshigherthanID-GAC.Inotherwords,TS-DSAconsumes133timesmoreenergythanID-GACforthecommunication.Hence,weexpectID-GACtobemoresuitableforMANETscenarioswhichofteninvolvespower-constraineddevices.7.6

Traceability

TraceabilitycostsarepresentedinFigure3.DuetothecostlycomputationofTatepairings,ID-GACperformspoorly,ascomparedtoTS-DSA.

However,sincethemisbehaviorintheadmissionprotocolleadsultimatelytotheevictionofthecorrespondinggroupmember,wearguethattraceabilityisarareexceptionalmeasure;thusweconsideritscoststoberelativelyunimportant.

3 3 2.5TS-DSA (authorizer)TS-DSA (member)ID-GAC (member) 2.5TS-DSA (authorizer)TS-DSA (member)ID-GAC (authorizer)ID-GAC (member)Average Processng Tme (seconds) 2Average Processng Tme (seconds)567Admission Threshold (t)8910ID-GAC (authorizer) 2 1.5 1.5 1 1 0.5 0.5 0234 0234567Admission Threshold (t)8910(a)MANET

Fig.3.TraceabilityCost

(b)Gnutella

7.7MembershipProof

WenowdiscussmeasurementresultsforthemembershipproofsinID-GAC,asoutlinedinSection5.TherespectivecostsofIMPandEMPcomputations(includingbothsigningandverifying)areshowninFigure4,withvaryingkeysizes.RecallthatIMPisneedediftwomemberswanttoauthenticateeachothersecretlyandestablishasharedsecretkey;incontrast,EMPcan(also)beusedtoprovemembershiptooutsiders.7.8

Revocation

ThegraphinFigure5representstheaveragecostneededtorevokeaparticu-largroupmemberforthevaryingthresholdusingthemechanismdescribedinSection6.Inthiscontext,thethreshold(tr)istherevocationthreshold.Costsinclude:generationofsignedrevocationrequests,broadcasttothegroupandvalidationoftheserequests.Delaybetweentwoconsecutiverevocationrequestsisnottakenintoaccount.

15

0.8󰀀Average Processing Time (seconds)󰀀1.4󰀀0.7󰀀0.6󰀀0.5󰀀0.4󰀀0.3󰀀0.2󰀀0.1󰀀0󰀀IMP󰀀EMP󰀀Average Processiong Time (seconds)󰀀1.2󰀀1󰀀0.8󰀀0.6󰀀0.4󰀀0.2󰀀0󰀀MANET󰀀Gnutella󰀀512󰀀768󰀀1024󰀀2󰀀4󰀀6󰀀8󰀀Key Size (bits)󰀀Revocation Threshold󰀀Fig.4.MembershipProofCostFig.5.MembershipRevocationCost

8DiscussionandFurtherImprovement

Inthissection,wediscusssomeoftheoutstandingissuesconcerningID-GAC,focusingprimarilyontheperformance.

Thebilinearmappingoperationisanelegantprocedurethatformsthebasisfortheverificationintheadmissionprocessandthemembershipproof.However,itisanexpensivecomputationwhichdominatestheoverallrunningtimeoftheprotocol.Moreover,itisonlybecauseoftheTatepairingoperationinourprotocolthatthekeysize,i.e.thesizeoftheprimepneedstobeatleast512-bits;althoughitiswell-knownthata160-bitsECCsystemisassecureasa1024-bitsRSAbasedsystem.Barreto,etal.[34]suggestsomemodificationsandoptimizationsfortheTatepairingoperation,mostofwhichareimplementedintheMIRACLlibrary[31]thatweused.Inordertofurtherimproveperformance,weneedtoparallelizetheseoperationsandpre-computeasmuchaspossible.AsdiscussedinSection4.5,thetraceabilityofmalicioussponsorsisanoptionalprocedurethatinvolvesverificationofindividualsponsor’ssignatures,whichcoststwopairingsperverification.Thiscostcanbesignificantlyloweredbyusingpre-computationsasdescribedin[31].

Thechoiceoftheellipticcurvebeingusedcancertainlyinfluencetheoverallcostofthescheme.BLSshortsignaturescheme[22]usesasupersingularcurvedefinedbytheequationy2=x3+2x±1overF3lwherelisapositiveexponent.Barreto,etal.[34]specifythecostofgeneratingaBLSsignatureonsuchacurve(definedinF397)tobejust3.57msonaP31GHzmachine,aftersomeoptimiza-tionsandpreprocessing.Thisseemslikeasignificantimprovementoverthecostsincurredinourmeasurementswhichwerebasedonadifferentcurvedefinedinaprimefield.Therefore,portingourprotocolforthesecurvesappearstobeanattractivewaytoreducecosts.Sincethesignaturegenerationhereischeaperthoughtheverificationisstillcostly,thisinfactcouldbeanidealcandidateforanadmissioncontrolmechanism,whereonewouldpreferthecomputationloadtobehighontheprospectivemember,muchlessersoonthecurrentgroupmembers.Inaddition,thesesignaturesareveryshort,only154-bitsinlength,

16

whichwillgiverisetoshortmembershiptokensinID-GAC;anotherseeminglyattractiveprospect.

9Conclusion

Inthispaper,weproposedID-GAC,anidentity-basedschemeforsecureadmis-sioncontrolindynamicadhocgroupsalongwithadistributedmembershiprevo-cationmechanismbasedonthemembershiprevocationlists.ID-GACborrowsideasfromthresholdsecretsharingandID-basedcryptography.AsdemonstratedbyextensiveexperimentationinbothP2PandMANETsettings,theproposedschemeisfarmoreefficientthanthepreviouslyproposedsolution,TS-DSA[11],[12].ThemeasurementresultsandperformanceanalysisfurtherindicatethatID-GACisevenmoreapplicableinMANETdeviceswherebandwidthandbat-terypowerareofprimeconcern.

References

1.Douceur,J.R.:TheSybilAttack.In:InternationalWorkshoponPeer-to-PeerSystems(IPTPS’02).(2002)

2.Steiner,M.,Tsudik,G.,Waidner,M.:KeyAgreementinDynamicPeerGroups.In:IEEETransactionsonParallelandDistributedSystems.(2000)

3.Steiner,M.,Tsudik,G.,Waidner,M.:Cliques:Anewapproachtogroupkeyagreement.IEEETransactionsonParallelandDistributedSystems(2000)

4.Hu,Y.C.,Perrig,A.,Johnson,D.B.:Ariadne:Asecureon-demandroutingprotocolforadhocnetworks.In:ProceedingsoftheEighthACMInternationalConferenceonMobileComputingandNetworking(Mobicom2002).(2002)

5.Perrig,A.,Szewczyk,R.,Wen,V.,Culler,D.,Tygar,J.D.:Spins:Securityprotocolsforsensornetworks.In:MobileComputingandNetworking.(2001)

6.Hamilton,A.:Playinginthedark:Theheatison,andmusicswappersaretakingtheirbusinessunderground.TIMEMagazine(2003)

7.Biddle,P.,England,P.,Peinado,M.,Willman,B.:Thedarknetandthefutureofcontentdistribution.In:ACMWorkshoponDigitalRightsManagement.(2002)8.Kong,J.,Luo,H.,Xu,K.,Gu,D.L.,Gerla,M.,Lu,S.:AdaptiveSecurityforMulti-levelAd-hocNetworks.In:JournalofWirelessCommunicationsandMobileComputing(WCMC).Volume2.(2002)533–547

9.Kong,J.,Zerfos,P.,Luo,H.,Lu,S.,Zhang,L.:ProvidingRobustandUbiquitousSecuritySupportforMANET.In:IEEE9thInternationalConferenceonNetworkProtocols(ICNP).(2001)

10.Kim,Y.,Mazzocchi,D.,Tsudik,G.:AdmissionControlinPeerGroups.In:IEEE

InternationalSymposiumonNetworkComputingandApplications(NCA).(2003)11.Saxena,N.,Tsudik,G.,Yi,J.H.:AdmissionControlinPeer-to-Peer:Designand

PerformanceEvaluation.In:ACMWorkshoponSecurityofAdHocandSensorNetworks(SASN).(2003)104–114

12.Narasimha,M.,Tsudik,G.,Yi,J.H.:OntheUtilityofDistributedCryptographyin

P2PandMANETs:TheCaseofMembershipControl.In:IEEE11thInternationalConferenceonNetworkProtocol(ICNP).(2003)336–345

13.Ohta,K.,Micali,S.,Reyzin,L.:AccountableSubgroupMultisignatures.In:ACM

ConferenceonComputerandCommunicationsSecurity.(2001)245–254

17

14.Gennaro,R.,S.Jarecki,H.Krawczyk,T.Rabin:RobustThresholdDSSSignatures.

InMaurer,U.,ed.:EUROCRYPT’96.Number1070inLNCS,IACR(1996)354–371

15.Desmedt,Y.,Frankel,Y.:Thresholdcryptosystems.InBrassard,G.,ed.:CRYPTO

’89.Number435inLNCS,IACR(1990)307–315

16.Saxena,N.,Tsudik,G.,Yi,J.H.:AccessControlinAdHocGroups.In:Interna-tionalWorkshoponHotTopicsinPeer-to-PeerSystems(HOT-P2P).(2004)

17.Luo,H.,Kong,J.,Zerfos,P.,Lu,S.,Zhang,L.:URSA:UbiquitousandRo-bustAccessControlforMobileAdHocNetworks,availableon-lineathttp://www.cs.ucla.edu/wing/publication/publication.html.In:IEEE/ACMTrans-actionsonNetworking(ToN),toappear.(2004)

18.Jarecki,S.,Saxena,N.,Yi,J.H.:AnAttackontheProactiveRSASignature

SchemeintheURSAAdHocNetworkAccessControlProtocol.In:ACMWork-shoponSecurityofAdHocandSensorNetworks(SASN).(2004)

19.Gennaro,R.,Jarecki,S.,Krawczyk,H.,Rabin,T.:RobustandEfficientSharingof

RSAFunctions.InKoblitz,N.,ed.:CRYPTO’96.Number1109inLNCS,IACR(1996)157–172

20.Barr,K.,Asanovic,K.:EnergyAwareLosslessDataCompression.In:International

ConferenceonMobileSystems,Applications,andServices(MobiSys).(2003)

21.Boldyreva,A.:Efficientthresholdsignatures,multisignaturesandblindsignatures

basedonthegap-diffie-hellman-groupsignaturescheme.In:ProceedingsofInter-nationalWorkshoponPracticeandTheoryinPublicKeyCryptography.Volume2567ofLNCS.(2003)31–46

22.Boneh,D.,Lynn,B.,Shacham,H.:ShortSignaturesfromtheWeilPairing.In

Boyd,C.,ed.:ASIACRYPT’01.Number2248inLNCS,IACR(2001)514–53223.P.Feldman:APracticalSchemeforNon-interactiveVerifiableSecretSharing.In:

28thSymposiumonFoundationsofComputerScience(FOCS).(1987)427–43724.Gennaro,R.,Jarecki,S.,Krawczyk,H.,Rabin,T.:SecureDistributedKeyGen-erationforDiscrete-LogbasedCryptosystems.In:Eurocrypt99.(1999)

25.Menezes,A.J.,vanOorschot,P.C.,Vanstone,S.A.:HandbookofAppliedCryp-tography.CRCPressseriesondiscretemathematicsanditsapplications.(1997)ISBN0-8493-8523-7.

26.Balfanz,D.,Durfee,G.,Shankar,N.,Smetters,D.,Staddon,J.,Wong,H.C.:Se-cretHandshakesfromPairing-BasedKeyAgreements.In:IEEESymposiumonSecurityandPrivacy.(2003)180–196

27.Cha,J.,Cheon,J.:AnID-basedsignaturefromGap-Diffie-HellmanGroups.In:

ProceedingsofInternationalWorkshoponPracticeandTheoryinPublicKeyCryptography.Volume2567ofLNCS.(2003)18–30

28.Kocher,P.C.:OnCertificateRevocationandValidation.In:ProceedingsofInter-nationalConferenceonFinancialCryptography.Volume1465ofLNCS.(1998)29.Myersand,M.,Ankney,R.,Malpani,A.,Galperin,S.,Adams,C.:OnlineCertifi-cateStatusProtocol-OCSP.RFC2560,IETF(1999)30.OpenSSLProject:(http://www.openssl.org/)31.MIRACLLibrary:(http://indigo.ie/~mscott/)32.TheGnutellaProtocolSpecificationv0.4:(http://www.clip2.com/

GnutellaProtocol04.pdf)

33.OLSR:(http://hipercom.inria.fr/olsr/)

34.Barreto,P.S.L.M.,Kim,H.Y.,Lynn,B.,Scott,M.:EfficientAlgorithmsforPairing-basedCryptosystems.InYung,M.,ed.:CRYPTO’02.Number2442inLNCS,IACR(2002)354–369

18