untrustedhosts
DaveSingel´ee,BartPreneel
COSICInternalReport
May,2004
Abstract
Thispaperinvestigateshowmobileagentscansecurelycollectinformation,protectthecollectedinformationagainstuntrustedhosts,andhowtheycandigitallysigntransactionsinanuntrustedenvironment.Wepresentanagent-basedscenarioformobilecommerceanddiscusstechniquesusingmultipleagentsthathavebeenimplementedtoprovidesecurityinthissce-nario.Theunderlyingtechniquesarebasedonexistingtheoreticalschemes.Theseschemesgenerallyhaveasignificantoverheadwhichiscausedbytheuseofmultipleagents.However,thisoverheadcanbecompensatedbythefunctionalityofferedinourproposedscenario.Theschemesrequirenoin-teractionoftheoriginatoroncethemobileagentsaresentout.Theyarethereforeparticularlysuitedforsituationsinwhichausercannotstayonlineforalongtime.Wealsoaddresssomepossiblesecuritythreatswhichleadtonewobservationsonusingthresholdsignatureschemesinthecontextofmobileagents.
Chapter1Introduction
Theprocessofbuyingsomethingonlinecanbedividedintwomajorphases:firstonehastofindthebestplace(host)tobuycertaingoodsorservices,thenonehastopayforthegoodsorservicesthatarebought.Thispaperinvestigateshowbothphasescanbeconductedsecurelyandefficientlybymobileagentsusingcertaincryptographictechniques.
1.1Mobileagentsande-commerce
Inthemodernsociety,informationandaccesstoinformationisgettingmoreandmoreimportant.Duringthelastcoupleofyears,thereisastrongten-dencytowardsmobility.Thisimpliesanincreasingneedforbeingonlineandhavingaccesstoinformationallthetime.Thistrendisalsopresentintheworldofe–commerce.Peoplewanttousetheirmobilephone,PDAorlaptoptodoonlineshopping.Thesedevicescannotbeonlineallthetime(withoutcost).Thiscanbealimitationforsomemobilecommerceapplications.Fortunately,theconceptofmobileagentscanpotentiallysolvetheafore-mentionedproblem.Mobileagentsaresoftwareprogramsthatcantravelautonomouslyfromhosttohosttoperformoneormoretasksonbehalfofacertainuser.Theycancommunicate(andevennegotiate)withotheragents,withhosts,...Usingmobileagentshassomeinterestingadvantages[1,2,3,4]:Theusercangoofflineaftertheagentissentoutandcancomeonlineagainwhentheagenthasperformedhistasks.Thisisveryusefulforsituationsinwhichtheusercannotstayonlineforalongtime.Anotherimportantadvantageisthefactthatthemobileagentperformshistaskslocally(i.e.,atthehost).Thismeansthatthedevicethatsendsthemobileagents(e.g.,aPDAoramobilephone)canhaveverylimitedcomputingpowerandwillnotneedexcessivepowerconsumption.Aswillbecomeclear
1
fromthispaper,mobileagentsmayinparticularbeveryinterestingifmanygoodshavetobebought.Ifonlyonethinghastobepurchased,thenothertechniquesmaybemoreefficient.
Inthediscussionabove,wecanidentifytwodifferentkindsofmobilityconcepts.Thefirstkindofmobilityarethemobiledevices.Thesedevicesareusuallybatteryfedanddonothavealotofcomputationalpower.Thesetwoconstraintsplacesevererestrictionstothecodethathastobeexecutedonmobiledevices.Thesecondkindofmobilityismobilecode.Mobilecodeisveryusefulforsituationsinwhichausercannotstayonlineforalongtime(e.g.,becauseofalackofbandwidth).Wewillprimarilyfocusonthislastkindofmobilityinthispaper.Notethatmobilecodeisofparticularinterestwithrespecttothefirstkindofmobilityaswell.
Takingintoaccounttheadvantagesofmobileagents,onecouldwonderwhymobileagentsarenotfrequentlyusedine-commerce.Oneofthemainreasonsisthattherearesomesecurityproblemswhichareverydifficulttosolve.
1.2Contributionsofthispaper
Thecontributionofthispaperistwofold.Firstly,itpresentsapracticalagent-basedscenarioformobilecommercewhichcanbemadesecurebyusingexistingtechniques.Thesetechniquesareusedinsuchawaythattheentireschemebecomesefficientandfeasibletobedeployed.Secondly,somenewobservationsonusingthesetechniquesinthecontextofmobileagentsystemsaremade.Theseobservationsarebothinatheoreticalandinapracticalsenseimportantbecausetheyimposesomelimitationsonusingcryptographicthresholdschemesinthecontextofmobileagents.
1.3Organizationofthepaper
Thispaperconsistsofsevensections.Inthissection,wehavepointedouttheadvantagesanddisadvantagesofusingmobileagentsine–commerce.Sec-tion2proposesamobileagent-basedscenariofore–commerce,describesthedifferentstagesinthisscenario,andgivesanoverviewofthespecificsecuritythreatsinthisscenario.Theremainderofthispaperpresentstechniqueswhichcanbeusedtomakethisscenariosecure.Section3discusseshowcryptographichashchainscanbeusedbyamobileagenttosecurelycollectinformation(price,nameofthehost,...)fromdifferenthosts.Apaymentprotocolconductedbymultipleagentsispresentedinsection4.Thissection
2
alsogivesashortsecurityanalysisofthepaymentprotocolandaddressessomeimportantobservationsconcerningthresholdschemesinthecontextofmobileagentsystems.Aninterestingextensioninthescenario,environmen-talkeygeneration,isdiscussedinsection5.Section6describesthepracticalimplementationofthescenario.Finally,section7concludesthepaper.
3
Chapter2
Mobileagent-basedscenario
Figure2.1showsanoverallviewofapracticalandsecuremobileagentsys-tem.Wewillnowillustratethedifferentstagesinapossibleagent-basedscenario[5]andmotivateourchoiceofthisspecificscenario.Wewillalsodiscussthesecuritythreatspresentinthisscenario.Thetechniquesthathavebeenimplementedtoprovidesecurityinthisscenariowillbedescribedinthenextsections.
2.1
2.1.1
Differentstagesinthescenario
Usersendsmobileagents
TheuserhasaPDAwithwhichhecanperiodicallyconnecttothenetworkforarelativelyshorttime.Hewantstoorganizeacompleteholidaytrip,includingflightreservation,hotelbooking,carrental,daytriparrangements,etc.Foreachofthesedifferentpartsofhisholiday,hesendsacustomizedmobileagenttothenetwork,thatwillfindthebestbargains.Obviously,theagentswillhavetoexchangeinformationtobeabletojointlyorganizetheholidayaccordingtotheoverallrequirementsoftheuser.Aftertheagentsaresenttothenetwork,theuserdisconnectshisPDAfromthenetwork.Thereisalsoasemi-trustedplatformwhichkeepstrackofthedifferentmobileagents.Thisplatformisgiven(public)informationneededduringthesignaturegen-erationprocess(seesection2.1.3).Thisplatformcanbeadministeredbytheuserorbyaserviceprovider.
2.1.2Agentstravelandsecurelycollectdata
Themobileagentstravelsecurelyfromagentplatformtoplatform.Onlytheagentparametersandcollecteddataaresecurelytransferredbetweenthe
4
Figure2.1:Anagent-basedscenarioformobilecommerce
5
agentplatforms,theactualprogramcodeoftheagentisretrievedeachtimefromitsoriginallocation(e.g.,thesemi-trustedplatformoranagentcodeprovider).Weassumethecodeisgenericandcanbeusedbymanycustomers.Theagentparametersconstitutethepersonalizationandcustomizationofthecode.
Themobileagentswillcollectoffersandotherinformationateachagentplatform.
2.1.3Agentsconductasecurepaymenttransaction
Atsomepointintime,anagentwilldecideorneedtoconductafinancialtransaction.Itwillthenaskthecooperationoftheotheragentsinordertogenerateadigitalsignature.Togethertheycangenerateanewsignatureon(forexample)aparticularofferofanagentplatform.Acombiningentityisrequiredtocombineanappropriatesetofthecontributionsoftheagentsintotheresultingsignature.Inparticular,toselectthisset,thevalidityofeachcontributionshouldbechecked.Thistaskcanbeperformedbythesemi-trustedplatformthatkeepstrackofthemobileagentsorbyanothersemi-trustedplatformdedicatedtohandlingagenttransactions.
2.1.4Verifycollecteddata
Attheendofitsjourney,theagentwillreturntothesemi-trustedplatform.Thisplatformcanverifytheauthenticityofthecollecteddata.Thedatapossiblyincludestransactionsconductedbythisagent.
WhentheuserreconnectshisPDAtothenetwork,hecanrequestthestatusofhismobileagentsandretractthereturnedagentsfromthenetwork.Hecanthendisconnectagainandinterpretthecollecteddataoftheagents.
2.2Motivation
Themostinterestingfactofourscenarioisthatmultipleagentsareusedinsteadofonemobileagent.Aswillbeexplainedinsection4,usingmultipleagentstoconductatransactionhasthebigadvantagethatthetransactioncanbevalidevenifsomemobileagentshavebeentamperedwith.Thiswouldcertainlynotbethecaseifonlyonemobileagentwouldhavebeenused!Sothebigsecurityadvantageofusingmultipleagentsisrobustness.Theuseofmultipleagentshasgenerallyhoweveralsothebigdisadvan-tageofcreatingasignificantoverhead:nmobileagentshavetobeexecutedtoconductonly1transaction.Thisiscertainlynotveryefficientatfirst
6
sight.Fortunately,thisoverheadiscompensatedinourproposedscenario.Differenttransactionsareconductedinparallel.E.g.,oneormoreagentscanbuyaplaneticketwhileoneormoreotheragentscanrentacar.Thismeansthatagroupofnagentscanconductanarbitrarynumber(i.e.,morethann)oftransactionssuchthat,incontrasttothresholdschemesintra-ditionalscenarios,alltheoverheadcausedbytheuseofmultipleagentsiscompensated.
Onecouldwonderwhythemobileagentsdonotreturntothehostoftheuseraftertheyhavecollectedtheiroffers.Thiswouldbeamucheasierscenario.Therearehoweversomesituationsinwhichdifferentgoodshavetopurchasedthataredependentofeachother.Atypicalexampleisaholidaytrip.Whenausergoesonholiday,hehastobookahotel,rentacar,buyairplanetickets,...Ifthemobileagentsdonotcooperate,thenitispossiblethattheybookahotelinaperiodinwhichnocheapairplaneticketsareavailable.Thisisofcoursenotwhattheuserswants,sothetransactionwouldhavetostartalloveragain.Theeasiestsolutionforthisproblemistoletthedifferentmobileagentsworktogetherwithouttheuser’sintervention.Anotherreasontodothisisthefactthattheuserisnotonlineallthetime.Thatiswhyinourscenariothemobileagentsonlyreturntotheoriginalhostafterthetransactionisfinished.
2.3
2.3.1
Securitythreats
Securityproblems
Ingeneral,onecandistinguishfourdifferentsortsofsecurityproblemswhenusingmobileagents,somealotmoredifficulttosolvethanothers[6,7].Thefirstchallengeistoprotectamobileagentintransit.Thisiseasytoaccomplishwithstandardsecuritytechniques.ByusingthetransportlayersecurityprotocolSSL/TLS[8],nobody(exceptthehostthatsendsthemobileagentandthehostthatreceivesit)caneavesdroponthemobileagentortamperwithitwithoutthisbeingdetected.Intherestofthepaper,weassumethatSSL/TLSisusedeverytimeagentsorotherinformationaresentbetweendifferenthosts.
Asecondsecurityproblemistoprotectahostagainstvisitingmobileagents.ThisproblemissimilartoprotectingaPCagainstvirusesormali-ciousmobilecodeandshouldthereforenotbeverydifficulttosolve.Mobileagentsareruninsandboxedenvironments.Inaddition,mobileagentscanbedigitallysigned.Anagentplatform’ssecuritypolicycanthendeterminetheprivilegestheplatformwillgranttotheagent.
7
Amobileagentalsohastobeprotectedagainstothermobileagents.Thiscanbeaccomplishedbymakingthemobileagentonlyaccessibleviaalimitedsetof(harmless)publicmethods.
Thelastandbyfarmostdifficultsecurityproblemistoprotectthemo-bileagentagainstthehostwhereitisbeingexecuted.Themobileagentiscompletelyundercontrolofthishostandalmostanyimaginableattackispossible[9]:thehostcaneavesdroponthemobileagent,itcantamperwiththeagentorjustrefusetoexecuteit,etc.Anoverviewofpossiblesolutionstothisproblemhasbeengivenin[10].
2.3.2Threatanalysisofourscenario
Ourmobile-agentbasedscenariohassomeveryspecificsecuritythreatswhichfallintothelastcategoryofgeneralmobileagentsecurityproblems.Thissectiongivesanoverviewofthemostimportantones.
Modificationofotheroffers:Amalicioushostcouldtrytomodifyor
deleteoffersfromotherhostssothatitsofferwouldbecomethebestone(e.g.,theonewiththelowestprice).Thismeansthatwehavetosearchfortechniqueswhichcanpreservetheintegrityoftheofferscollectedbythemobileagents.Section3discussesatechniquethataddressesthisthreat.Denialofanoffer:Amalicioushostcouldtrytomakeaverygoodoffer
(e.g.,makeanofferwithaverylowprice)suchthatitsofferwouldcertainlybecomethebestofferandafterwardstrytodenythatithasmadethatoffer.Toenforcenon-repudiation,everyhosthastosignitsownoffer.Theftoftheprivatekey:Amalicioushostcouldtrytostealtheprivate
keyofthemobileagents.Ifitsucceeds,thenitcansignarbitrarydocuments.Thisattackisverythreatening.Todecreasetheriskincaseofaneventualtheftoftheprivatekey,techniqueshavetobeusedtorestrictthepowerofthemobileagents.E.g.,themobileagentscanonlyspenduptoacertainamountofmoney.Inaddition,theprivatekeyisdistributedamongmultipleagents,asdiscussedinsection4.Signingofotheroffers:Amalicioushostcouldtrytoletthemobileagents
signanotherofferthantheyfirstintendedto.Thisnewoffercanbechosenbytheattackerorcanbeanarbitrarynewone.Thisattackisverysimilartothepreviousone.Theonlydifferenceisthatthemali-cioushostdoesnotknowtheprivatekeyinthisattack.Thetechniquediscussedinsection4alsoaddressesthisthreat.
8
Denialofserviceattacks:Alotofdenialofserviceattacksarepossible.
Theeasiestoneforamalicioushostissimplynottoexecutethemobileagent.Fortunately,thiscanbeeasilysolvedbyusingmultipleagents(aswehavedoneinourscenario).Aslongasthemajorityofthemobileagentsisexecutedcorrectly,thetransactionwillbevalid.Notehoweverthatalsothesemi-trustedplatformhastoexecuteeverythingcorrectly(seealsosection4.2).Inthenextsections,wediscusstheexistingtechniquesthataremostsuitabletoaddressthesecuritythreatsinourproposedscenario.
9
Chapter3
Securedatacollectionbyhashchaining
Whenauserwantstopurchasesomethingonline,heprobablydoesnotim-mediatelyknowwheretobuyit.Typically,therearealotofhoststhatsellthedesireditemandtheydonotallaskthesamepriceorgivethesameconditions.Thatiswhytheuserwillsendamobileagenttothedifferenthosts.Theagentwillasktheprice(andotherimportantinformation)andwillusethatinformationtodecidefromwhichhosttheusershouldbuythedesireditem(e.g.,thehostthatasksthelowestprice).Ofcourse,malicioushostscouldtrytochangetheinformationthatavisitingagenthasalreadycollectedfromotherhosts(e.g.,itcouldincreasethepricesoftheotherhostsinsuchamannerthatitspricewouldbecomethelowest).
Therearedifferentsolutionstothisproblem.Theeasiestsolutionistosendasmanymobileagentsastherearehoststhathavetobevisited.Inthisway,everyagentonlyvisitsonehost.Amalicioushostwillhaveabsolutelynoadvantageoftamperingwiththeagentbecausethemobileagentdoesnotcontaininformationofotherhosts.Thismethodissecure,butitisalsothemostexpensivesolution.Moreover,inmostcasesitisnotknowninadvancehowmanyandwhichhostshavetobevisited.Protocolsbasedonhashchainingaresuitablehere.WedescribeaspecificsolutionofKarjothetal[11].
3.1Descriptionoftheprotocol
Supposethatauser(denotedbyS0)sendsamobileagenttonhosts(denotedbyS1toSn).Theindexinthisnotationindicatestheorderinwhichthehostsarevisited(i.e.,thefirsthostintheitineraryisS1,thesecondisS2,
10
etc).Toprotectthedatathatiscollectedfromthesedifferenthosts,themobileagentperformsthefollowinghashchainingprotocol:Protocol1(HashChaining).•EncapsulatedOffer:
Oi=SIGi(ENC0(ri,oi),hi),0≤i≤n
•ChainingRelation:
h0=H(o0,S1)
hi=H(Oi−1,Si+1),1≤i≤n
•Protocol:
Si→Si+1:{Ok|0≤k≤i},0≤i≤n
ThenotationusedinthisprotocolisexplainedinTables3.1and3.2.
Table3.1:Symbolsusedinprotocol1
S0=Sn+1Si,1≤i≤no0
oi,1≤i≤nOi,1≤i≤nO0,O1,O2,...,On
Identityoftheuser(originator)IdentityofhostiInitialinformation(e.g.theidentityoftheagent)OfferfromhostiEncapsulatedofferfromhostiChainofencapsulatedoffersTable3.2:Cryptographicnotationusedinprotocol1ri
ENC0(m)SIGi(m)H(m)Si→Si+1:mRandomnumbergeneratedbyhostiMessagemencryptedwiththepublickeyofS0
MessagemdigitallysignedbyhostiHashvaluecalculatedonmessagemMessagemissentfromhostitohosti+1Letusnowhavealookhowthisprotocolworks.Theownerofthemobileagentfirstmakesadummyoffero0thatcontainsinitialinformationliketheidentityoftheowner,theIDoftheagent,...Next,hecomputesthe
11
Figure3.1:Chaining
hashvalueh0byapplyingH()overthisdummyofferandtheidentityofthefirsthostS1.Thenhepicksarandomnumberr0andencryptsthisrandomnumberandthedummytokenwithhisownpublickey(thisisequivalenttoencryptingthedummytokenusingrandomizedencryption).Finally,heconstructstheencapsulatedofferO0bysigningtheencryptionandh0.O0isthensenttohostS1.
Allthehostswillperformalmostexactlythesamesteps.First,hostSiwillcomputeahashvaluehiovertheencapsulatedofferOi−1oftheprevioushost(Si−1)andtheidentityofthenexthost(Si+1).ThisisthechainingrelationanditisillustratedinFigure3.1.Nextitwillpickarandomnumberriandencryptsthisrandomnumberanditsownofferoiwiththepublickeyoftheoriginator(S0)(thisisequivalenttoencryptingtheofferoiusingrandomizedencryption).Finally,itconstructstheencapsulatedofferOibysigningtheencryptionandhi.Oiisthensenttothenexthost(Si+1)togetherwithalltheencapsulatedoffersO0toOi−1fromtheprevioushosts.Thisprocedureisrepeatedateveryhost.Attheendofitsitinerary,themobileagentwillgobacktotheoriginator(Sn+1=S0).
3.2Discussionoftheprotocol
Thehashchainingprotocolhassomeinterestingsecurityproperties[11]:Confidentiality:Thedatacollectedbythemobileagentisencryptedwith
12
thepublickeyoftheoriginatorandtherefore,nobodyelsethantheoriginatorcanreadthedata1.
Non-Repudiation:EveryhostSisignsitsencryptedoffer.Ifthesignature
schemeissecure,SicannotrepudiateOi.StrongForwardIntegrity:Strongforwardintegritymeansthatnoneof
theencapsulatedoffersOkcanbemodifiedbyanattacker(wherekissmallerthanacertainnumberm).Theproofofthispropertycanbefoundin[11].PubliclyVerifiableChain:Everybodyiscapableofverifyingthechain
O0,O1,...,Oi.EachOkisoftheformOk=SIGi(Xk,hk)whereonlyXkisanuninterpretablebitstring.ThustheexaminercanverifywhetherthechainingrelationholdsandwhethereachsignatureonOkisvalid.InsertionResilience:Itisverydifficultforanattackertoinsertanencap-
sulatedofferOiintoavalidchainO0,O1,...,Om.DeletionResilience:Itisverydifficultforanattackertodeleteanencap-sulatedofferOifromavalidchainO0,O1,...,Om(i≤m).TruncationResilience:EverytruncationofavalidchainofencapsulatedoffersO0,O1,...,Omatk(withk Weassumethattherandomizedencryptionschemeusedintheprotocolissecure. 13 Chapter4 UndetachableThresholdSignatures Therearedifferentmethodstopaysomething:youcanuseelectronicmoney,youcancalculateadigitalsignatureonaspecificdocument,...Theprotocolexplainedinthispaperwilldothelatter.Itexistsof6phases:aninitializa-tionphase,adistributionphase,aphaseinwhichtheagentsaresentout,apartialsigningphase,areconstructionphaseandafinalizationphase.AllthesephasesarediscussedinSection4.1.Wealsomakesomeimportantob-servationsinsection4.2onusingthresholdschemesinthecontextofmobileagents.ReaderswhoarenotfamiliarwiththeprinciplesofsecretsharingshouldfirstreadappendixA. 4.1PaymentProtocol Thetechniqueofverifiablesecretsharingwillbeusedtocalculateadigitalsignature.Moreconcrete,auserGwillsendnmobileagentsAitodifferenthosts.Theseagentswillfirstfindthebestoffer.Then,theywillsignthisofferusingtheRSAsignaturescheme[12].Theywilldothiswiththehelpofasemi-trustedpartyT.WedescribetheschemeofBorseliusetal[13]whichisbasedon[14].Weincludethenotionofaproxycertificate[15]andfittheprotocolintoouragent-basedscenario.Thecompleteprotocoloffindingthebestofferandsigningitwillbeperformedin6consecutivephases.These6phaseswillbeexplainedinthefollowingsubsections. 14 4.1.1InitializationPhase TheuserGhastoperformalotofinitializationsteps.FirstGchooses2safeprimenumbers1penqofequalsize(let’ssay512bitseach).Sop=2p+1andq=2q+1.TheRSAmodulusNisthenequaltoN=pq.GalsocalculatesthesecretnumberM=pq.Next,Gchoosesarandomprimenumbereandcalculatesd=e−1modM.2(d,e)isatemporarykeypairthatwillbeusedbythemobileagentsAitosignthebestoffer.Aftercreatingthetemporarykeypair,Gformulatesrestrictions(denotedbyR)aboutthetransactionthathastobeperformed.Theserestrictionscontainthemaximumamountofmoneythatcanbespent,informationaboutthegoodsthathavetobepurchased,... Gnowhasenoughinformationtocreateaproxycertificate.Aproxycertificate[15]isacertificatethatisparticularlydesignedformobileagents.ItcontainspublicinformationliketheidentityoftheoriginatorG,thepublickeyeoftheagent,themodulusN,therestrictionsR,...anditissignedbyG.Apurchasewillonlybevalidifitcomplieswiththisproxycertificate.Thisisaverysimpletechniquetodelegateresponsibilitytothemobileagentandatthesametimedecreasetheriskbyapossibletheftofthesecretkeyd.Aproxycertificatehasaveryshortlifetime(thesamelifetimeasthepublickeye)andthereforedonotneedberevoked.Italsoassuresnon-repudiationtosomeextendbecauseGhassignedthecertificate.SoGcannotdenythathehassentmobileagentsforaparticularacquisition.Aproxycertificateisthusasortofprocuration. Afterthecreationofthisproxycertificate,GcalculatesH=h(R,G)2(h()isahashfunctionwithoutputinZ∗N).Andfinally,Gchoosesarandomnumberaandcalculatesthenumberbasfollows: b=d·(1−4a∆2)modM (4.1) Informula4.1,∆isequalto∆=nA!modMwithnAthenumberofmobileagentsAithatwillbesentout. 4.1.2DistributionPhase Aftertheinitializationphase,Gusesa(kA,nA)verifiablesecretsharingscheme(seeappendixA)todividethesecretkeydinnAsharessi.Gthenpicksoutarandomnumberv(∈QN)andcalculatestheverificationkeysvi=vsimodN.Theseverificationkeyswillbeusedlaterintheprotocolto pisasafeprimenumberifp=2p+1withpalsoaprimenumber.2 AllcalculationsinthisprotocolwillbeperformedinthesubfieldofsquaresinZ∗N(denotedbyQN).Z∗isthegroupofintegersamodNwithacoprimetoN.N 1 15 calculateacommitment.Finally,GchoosesasemitrustedplatformT.Gthensendstheproxycertificate,thenumbersaandb,H,∆,vandalltheverificationkeysvitoT.EachmobileagentAigetsH,∆,si,vandvi. 4.1.3BroadcastingPhase ThemobileagentsAiarenowsentouttothedifferenthosts(thismeansthatGcangoofflinenow).Thefirsttaskthattheywillperform,istocollecttheoffersfromthedifferenthostsanddecidewhichoneisthebest.Theywillusehashchainingtoaccomplishthis(seesection3).Thereishoweveronemodificationthatwehavetomaketothisprotocol.InsteadofencryptingeverythingwiththepublickeyofthehostG(insection3,GiscalledS0),thepublickeyofTisused!Anothersmallmodificationisthatthedummyoffero0willcontaintheidentityoftheoriginatorGandtherestrictionsR.Whentheoffershavebeencollected,theyaresenttoT.Tthenchoosesthebestoffer.Notethatafterwards,Tcanbeaskedtoprovethatithasdonethiscorrectly(Tcannotmodifythechainofencapsulatedoffers).Tcalculatesthenumberxs=h(G,B,offer)withofferthebestofferandBthehostthathaspresentedthisbestoffer.WeassumethatTwillperformthistaskcorrectly.Finally,TsendsxstoeverymobileagentAi. 4.1.4PartialSigningPhase Afterreceivingthenumberxs,themobileagentsAiwillconstructapartialsignature(whichwillcontaininformationaboutthebestoffer).Theywilldothisbycalculatingthenumberhi(∈QN): hi=H2∆·xs·si (4.2) Thispartialsignaturehiisashareoftheultimatesignature(Hxs)d(thisvaluecanbeconsideredasacontractthatcontainsallthenecessaryinformation(G,B,Randtheoffer)andthatissignedbytheprivatekeyd).ThemobileagentsAialsoneedtocalculateacommitmenttoprovethathiiscorrect(withoutrevealingsi).Aiwilldothisbymakinguseofthehashfunctiong()whichisknownbyallparties.Letussupposethattheoutputofg()is128bits.Tocalculatethecommitment,Aichoosesarandomnumberrof1280bits3andcomputesthecouple(ci,zi): r4∆·xs·r ci=g(v,H4∆·xs,vi,h2)i,v,H 3 (4.3) ThenumberrhasL(N)+2L1bitswhereL(N)isequaltothenumberofbitsofthe modulusNandL1isequaltothenumberofbitsoftheoutputofg(). 16 zi=si·ci+r (4.4) Thiscouple(ci,zi)isthecommitmentonthepartialsignaturehi.Itlooks 4∆·xs·si verycomplicated,butitisjustaproofthatthediscretelogofh2)i(=HtothebaseH4∆·xsisequaltothediscretelogofvi(=vsi)tothebasev.Ainowsendsthesharehiwiththecommitment(ci,zi)toT.Tchecksallincomingshareshibycomputingthevaluesci(notethatTpossessesallthevaluesvi): −ci2cizi4∆·xs·zi ·h−)ci=g(v,H4∆·xs,vi,h2i,v·vi,Hi (4.5) Ifthisvalueciisequaltoci,thenthecommitmentonthepartialsignature hiiscorrect.BecausethereareatleastkAagentsAiwhicharenotaffectedbyamalicioushost,TwillalwaysgetatleastkAcorrectshareshi.IftherearemorethankAshareshiwithcorrectcommitment,thenTpicksout(randomly)kAofthem.LetuscallthisgroupofkAagentsAithegroupS.SoSisasubsetoftheset{0,1,...,nA}. 4.1.5ReconstructionPhase Twillnowreconstructthesignature(Hxs)dfromthekAshareshi.WewillderivehowTcandothis(insteadofjustgivingtheformula). LetusstartfromformulaA.2.BecausetheprimefactorsofM(pandq)arebiggerthannA,xicanbereplacedbyiandeverythingcanbecalculatedmodM(seealsoappendixA).Theresultisthefollowingformula: f(x)= i∈S (x−j) modMf(i) (i−j)j∈S,j=i i∈S (4.6) Letustakex=0andmultiplybothtermswith∆: d·∆=f(0)·∆= f(i)·∆ j modM (j−i)j∈S,j=i (4.7) Therightpartofformula4.7willbedenotedbyλSi: λSi =∆ j (j−i)j∈S,j=i (4.8) TcomputesallthesekAvaluesλSi.Thiscannotbedoneinadvancebecause Sisonlyknownattheendofthepartialsigningphase(section4.1.4).AveryimportantremarkisthatthevaluesλSiarenotcalculatedmodM(T S doesnotknowM)!Alsonoticethatλi=∆·ci,S(seeformulaA.3). 17 AftercreatingthevaluesλSi,itisveryeasytoconstructthesignature(Hxs)d.Tfirstcomputesavaluew: 2λS w=hiimodN(4.9) i∈S Ifonecombinesformula4.2andformula4.9,onegets:S w=H4∆·xs·si·λimodN i∈S (4.10) Finally,ifonetakesintoaccountformula4.7andthefactthatf(i)=si, formula4.10becomes: w=H4∆ 2·xs·d modN=(Hxs)4∆ 2·d modN(4.11) Byusingthenumbersaandb(seeformula4.1),Tcomputesthedigitalsignature(Hxs)dasfollows: (Hxs)d=wa(Hxs)bmodN (4.12) 4.1.6FinalizationPhase (xs,(Hxs)d,proxycertificate) (4.13) Tofinalizethepaymentprotocol,TsendsthefollowingtupletoB:Bsendsthistupletothebanktovalidateit.Thiswillonlyhappenifthetupleisvalid(i.e.ifthesignatureisvalid,iftheoffercomplieswiththeproxycertificate,...).Ifthetupleisvalidated,thebankwilltransferthespecifiedamountofmoneyfromGtoB.Afterwards,thetupleisnotdestroyedbutkeptasproofthattheuserGboughtcertaingoodsfromB. 4.2 4.2.1 Shortanalysis Securityparameters Itwouldtakefartomanypagestocompletelyanalyzethepaymentprotocoloftheprevioussection.Shoup[14]provesthesecurityofthetechniqueofundetachablethresholdsignaturesusedinthisprotocol.Therearethreeimportantsecurityparametersintheprotocol:kA,L(N)(thenumberofbitsofN)andL1(thesizeoftheoutputofg()).Thelastone,L1,determinesthedifficultyofanattackertoforgeacommitment.Shoupsuggeststhat128bitsaresufficient[14].L(N)dependsonthelifetimeofthesignature.Thiswillprobablynotbeverylong(maximallyacoupleofyears),so1024bitsaresufficient. 18 4.2.2Upperlimitonthenumberofmobileagents Aninterestingquestionisifthereisanupperlimitonthenumberofmobileagentsthatareusedinthepaymentprotocol.Atfirstsight,thisisaverystrangequestiontoask.Intuitively,onewouldthinkthatthemoreagentsonesuses,themoresecuretheschemebecomes.Thisishoweveronlytrueuntilthenumberofagents(nA)reachesacertainlimit.Ifthatlimitisexceeded,thentheattackercanperformasocalled‘∆–attack’. Recallthatthenumber∆(whichisknownbyallparties)usedinthepaymentprotocolisequalto∆=nA!modM.Thisformulacanberewrittento(nA!−∆)=m·MwheremisasmallnumberandMaverybignumber(L(N)−2bits).Soifthenumberofagents(nA)isnotverybig,thenmiszeroandtheattackerlearnsnothing.IfnAincreases,thennA!willincreaseveryfastandwillsoonbecomelargerthanM.Ifthisisthecase,thenmisnotzeroanymore,butstillquitesmall.Theattackercanthenjusttrysomem(heknowsnAand∆)untilhefindsM.IftheattackerpossessesM,thenhecaneasilydeterminethesecretkeyd(d=e−1modM).Thismeansthatthefollowingformulamustalwayshold: nA! Letuscalculatetheupperlimitofformula4.14forthecasethatthesizeofNis1024bits.ThismeansthatMisa1022bitnumberandthusalwayssmallerthan21022(butlargerthan21021).Onecancalculatethat170!<21021<21022<171!.SotheupperlimitfornAis170.Notethatthislimitisprobablynotproblematicinrealisticscenarios. 4.2.3Updatingthesecretkey TheprotocolofBorseliusetal[13]issecure,butalsoveryefficientwhenitisusedinourscenario.Mostofthecomputationsaredoneintheinitializationphase,butthisphasehastobeexecutedonlyonce.Afterthatthetemporarykeypair(d,e)hasbeencreatedanddistributedamongthenAmobileagentsAi,itcanbeusedformanypurchases(foreverydifferentgoodthathastobebought,theuserGhastomakeadifferentproxycertificateandadifferentnumberH).Thisisveryimportant,becauseifthemobileagentscouldonlybeusedtomake1acquisition,thenitwouldbebetternottousemobileagents! Thetemporarykeypair(d,e)canhowevernotbeusedinfinitely!Weobservethatproblemsarisewhenthemobileagentsaretravellingfromhosttohost,incontrasttothresholdschemesinthetraditionalscenariosproposedintheliterature!Onceamobileagentisundercontrolofanattacker,itcan 19 notbetrustedanymore.Everytimetheagentstraveltoanotherhost,some“benignant”agentswillvisitamalicioushostandwillfallintothehandsoftheattacker.SothenumberofuntrustedagentswillcontinuouslyincreaseandwilleventuallybecomelargerthankA(andtheassumptionthatthereatleastkAbenignantmobileagentsbecomesinvalid).Thismeansthatsecretsharingusingmobileagentsisadynamicprobleminsteadofastaticoneasassumedintraditionalscenarios.Thepaymentschemeshouldthusbeextendedwithanupdatemechanism.Onecouldforexampleuseproactivethresholdschemes[16]inwhichthesharessiofthesecretkeydareupdatedregularly. 4.2.4Denialofserviceattacks Asalreadymentionedinsection2.3,agoodcountermeasurefordenialofserviceattacksisusingmultipleagents.ThepaymentprotocolwillgenerateavalidsignatureaslongaskAmobileagentsareexecutedcorrectly.Thisishoweveronlytrueifthesemi-trustedhostTexecutestheprotocolcorrectly.Tobemoreprecise,weassumethatTonlyperformspassiveattacks(likeeavesdropping),butnoactiveattacks(likemodifyingdata).ThisistheonlyassumptionthathastobemadeaboutTanditcancertainlyberealizedinpractice.Theconclusionisthatourschemeisquiterobustagainstdenialofserviceattacks. 20 Chapter5 Extension:EnvironmentalKeyGeneration Apossibleextensioninourscenarioisthetechniqueofenvironmentalkeygeneration[17].Thistechniquecanbeusedinsituationswheretheagentshavetokeepsecretwhattheyarelookingfor.Theywillonlyrevealittothehoststhatsellthedesireditem.Alltheotherhostswillnotknowwhattheagentswanttopurchase(theywillonlyknowthattheydonotsellit). Theaimofenvironmentalkeygenerationistoencrypttheagentinsuchawaythatitcanonlybedecryptedwhenacertainconditionisfulfilled.Letusassume,asstatedabove,thattheconditionthatneedstobefulfilledisthefactthatthehostsellsacertainitem.Sothemobileagentmayonlybedecryptedifthisconditionistrue.Averysimplemethodtoaccomplishthis,istoencrypttheagentwiththekeyK=h(ITEM)whereITEMisthestringrepresentationofthedesireditem(e.g.,ITEMcouldbe“planeticket”iftheagenthastobuyaplaneticket)andh()acryptographichashfunction.TheagentalsocarriesthevalueX=h(h(ITEM)).Whentheagentvisitsahost,itlooksintothedatabaseofgoodsthatthehostsellsandchecksforeveryitemIifh(h(I))=X.Ifthisconditionistrue(thismeanswithveryhighprobabilitythatI=ITEM),thentheagentisdecryptedwiththekeyh(I).Iftheconditionisnotfulfilled,thentheagentcannotbedecryptedanditisimpossibleforthehosttoknowwhattheagentwaslookingfor.Other,verysimilarmethodscanbefoundin[17]. 21 Chapter6 Practicalimplementation Asaproofofconcept,theentiremobileagent-basede–commercescenariohasbeenimplementedinthescopeofthreeMaster’stheses[18,19,20]onaPersonalDigitalAssistant(PDA)withaclockfrequencyof206MHz(32bitRISCprocessor).Morespecifically,wehavedemonstratedthepracticalfeasabilityofthefollowingmechanisms:•hashchaining •paymentsbymultipleagents•environmentalkeygeneration First,ourPDAsendsmobileagentstodifferenthosts(weusedordi-naryworkstations).Toprotecttheagentsagainsthoststhatdonotselltherequiredgoods,weusedenvironmentalkeygeneration.Theencryptedagentsareexecutedinasandboxonthedifferenthostsandareonlyde-cryptedcorrectlyifacertainstringITEMispresentinacertainfile(e.g.,thefilegoods.txtcontainsthestring“planeticket”).Afterthisdecryption,theagentscollectinformationabouttherequiredgoods.Inoursimulations,wecollectedthenameofthehost,thepriceofthegoodsandthenumberofgoods.Thismeansthatthebestofferissimplytheofferwiththelowestprice.Thisinformationisprotectedusinghashchaining.Afterthemobileagentshavevisitedthedifferenthosts,theysendthecollectedinformationtoatrustedhostT.WehavesimulatedthebehaviorofTbyanothermobileagentonacertainhost.Tdecideswhichoftheoffersisthebestoneandperformstogetherwiththemobileagentsthepaymentprotocolasdescribedinsection4.1. Thesepracticalproofsofconcept,whichareillustratedinfigure6.1,weremadeintheAgletsmobileagentframework[21],aplatformbasedonJava 22 Figure6.1:Simulationoftheagent-basedscenario andespeciallydesignedforimplementingmobileagentsystems.AlternativeplatformsareTelescript[22],Sumatra[23],Grashopper[24],...Referencestootheragentframeworkscanbefoundin[25].TheadvantageofAgletsisthatthecodeisopensourceandcaneasilybeadjusted.InAglets,anagentexecutionenvironmentiscalledacontext.Mobileagentscantravelfromonecontexttoanothercontext.Therecanbemultiplecontextsononephysicalhost.Inadditiontotheimplementationofthethreemechanisms,SSL/TLS[8]hasbeenincorporatedintoAgletsinordertosecurethecommunicationbetweenAgletcontexts[18].Thecommunicationinanyagentframework,whetherornotsupportingmobileagents,canbesecuredinthisway. PDAshavelesscomputingpowerandmemorythanaworkstation.ThatiswhyweneedtousePersonalJavainsteadofthestandardJavaedition.WithPersonalJava,allmobiledeviceslikeaPDA,digitalset-topboxes,navigationsystems,...havethesameJavaplatform.Thismakesitveryeasytotransfersoftwarefromonedevicetoanother.MostpackagesofPer-sonalJavaoriginatefromversion1.1oftheJavaarchitecture.Newpackagesfromversion2arenotincludedinPersonalJava.PersonalJavaishoweverbuiltonthesamesecurityarchitectureasinJava2.Thismeansthatmostapplications-inourcasetheAgletsplatform-thataredevelopedforver-sion1.1areinprincipletransferabletoPersonalJavawithoutanyproblemsandthattheseapplicationscanmakeuseofcryptographicprimitives.Iftheapplicationiswrittenforversion2,thensomeproblemscouldariseiftheapplicationusesmethodswhichdonotyetexistinversion1.1. 23 Chapter7Conclusion Oneofthemajorapplicationsofmobileagentswillbee-commerce.Agentsareverymobileandcanactcompletelyautonomousandarethereforeaperfecttechniquetouseonmobiledevices.Thereishoweveroneseriousdrawbackonusingmobileagentsine-commerceandthatistheproblemofprotectinganagentfrommalicioushosts. Thispaperhaspresentedasetofpossiblesolutionstothisproblem.Theschemethathasbeendiscusseduseshashchainingtosecurelycollectinfor-mation(protectionoftheintegrity)fromdifferenthosts.Inanextphase,thetechniqueofundetachablethresholdsignaturesisusedtosignacontractwiththehostthathaspresentedthebestoffertotheagents.Thisschemecanbeextendedwithanupdatingmechanismandwithenvironmentalkeygenera-tion.Wehaveproposedapracticalmobileagent-basedscenarioinwhichthepresentedschemecanbeusedefficiently.WehaveimplementedthisschemeonaPDAbyusingAglets,aplatformdesignedformobileagents.Finally,wehavemadesomeimportantobservationsonusingthresholdschemesinthecontextofmobileagents. 24 Acknowledgements DaveSingel´eeisfundedbyaresearchgrantoftheInstituteforthePromotionofInnovationbyScienceandTechnologyinFlanders(IWT).Partofthisworkhasappearedin[5].Forthiswork,JorisClaessenswasfundedbyaresearchgrantofthesameinstitute.ThisworkwasalsosupportedinpartbytheFWO-VlaanderenprojectG.0358.99onOpenSecuritySystemsforAgent-basedApplications(OSABA),andbytheConcertedResearchAction(GOA)Mefisto-2000/06oftheFlemishGovernment.TheauthorswouldfinallyliketothankFrankPiessens,DriesIndesteege,VincentJacobsandVincentTouquetfortheircontributionsoftheirmasterthesistothispaper. 25 Bibliography [1]DavidM.Chess,BenjaminGrosof,ColinG.Harrison,DavidLevine, ColinParris,andGeneTsudik.ItinerantAgentsforMobileComputing.IBMResearchReportRC20010,March1995.[2]DavidM.Chess,ColinG.Harrison,andAaronKershenbaum.Mobile Agents:Aretheyagoodidea?InJanVitekandChristianTschudin,editors,ProceedingsoftheSecondInternationalWorkshoponMobileObjectSystems:TowardstheProgrammableInternet,LectureNotesinComputerScience,LNCS1222,pages25–45.Springer-Verlag,April1997.[3]DavidKotzandRobertS.Gray.MobileAgentsandtheFutureofthe Internet.ACMSIGOPSOperatingSystemsReview,33(3):7–13,July1999.[4]DannyB.LangeandMitsuruOshima.SevenGoodReasonsforMobile Agents.CommunicationsoftheACM,42(3):88–89,March1999.[5]JorisClaessens.Analysisanddesignofanadvancedinfrastructurefor secureandanonymouselectronicpaymentsystemsontheInternet.PhDthesis,KatholiekeUniversiteitLeuven,December2002.220pages.[6]WilliamM.Farmer,JoshuaD.Guttman,andVipinSwarup.Security forMobileAgents:IssuesandRequirements.InProceedingsofthe19thNationalInformationSystemsSecurityConference,1996.[7]WayneJansenandTomKarygiannis.MobileAgentSecurity.NIST SpecialPublication800-19,October1999.[8]TimDierksandEricRescorla.TheTLSProtocolVersion1.1.IETF InternetDraft,March2003.[9]FritzHohl.AModelofAttacksofMaliciousHostsAgainstMobile Agents.InProceedingsofthe4thECOOPWorkshoponMobileOjectSystems:SecureInternetMobileComputation,July1998. 26 [10]JorisClaessens,BartPreneel,andJoosVandewalle.(How)canmobile agentsdosecureelectronictransactionsonuntrustedhosts?–Asurveyofthesecurityissuesandthecurrentsolutions.ACMTransactionsonInternetTechnology,3(1):28–48,February2003.[11]G¨unterKarjoth,N.Asokan,andCekiG¨ulc¨u.ProtectingtheCompu-tationResultsofFree-RoamingAgents.InKurtRothermelandFritz Hohl,editors,ProceedingsoftheSecondInternationalWorkshoponMo-bileAgents,LectureNotesinComputerScience,LNCS1477,pages195–207.Springer-Verlag,September1998.[12]AlfredJ.Menezes,PaulC.vanOorschot,andScottA.Vanstone.Hand-bookofAppliedCryptography.CRCPress,October1996.[13]NiklasBorselius,ChrisJ.Mitchell,andAaronWilson.Undetachable ThresholdSignatures.InBahramHonary,editor,Proceedingsofthe8thIMAInternationalConferenceonCryptographyandCoding,LectureNotesinComputerScience,LNCS2260,pages239–244.Springer-Verlag,December2001.[14]VictorShoup.PracticalThresholdSignatures.InBartPreneel,editor, AdvancesinCryptology–EUROCRYPT2000,LectureNotesinCom-puterScience,LNCS1807,pages207–220.Springer-Verlag,May2000.[15]ArturRom˜aoandMiguelMiradaSilva.Proxycertificates:amechanism fordelegatingdigitalsignaturepowertomobileagents.InYimingYeandJimingLiu,editors,ProceedingsoftheWorkshoponAgentsinElectronicCommerce,pages131–140,December1999.[16]AmirHerzberg,MarkusJakobsson,StanislawJarecki,HugoKrawczyk, andMotiYung.ProactivePublicKeyandSignatureSystems.InPro-ceedingsofthe4thACMConferenceonComputerandCommunicationsSecurity,April1997.[17]JamesRiordanandBruceSchneier.EnvironmentalKeyGeneration TowardsCluelessAgents.InGiovanniVigna,editor,MobileAgentsandSecurity,LectureNotesinComputerScience,LNCS1419,pages15–24.Springer-Verlag,1998.[18]DriesIndesteegeandVincentJacobs.Securityaspectsofmobileagents andPDAs(inDutch).Master’sthesis,K.U.Leuven,2002.[19]DaveSingel´ee.Securedigitalsignaturesusingmobileagentsonun-trustedplatforms(inDutch).Master’sthesis,K.U.Leuven,2002. 27 [20]VincentTouquet.Protectingmobileagentsinhostileenvironments(in Dutch).Master’sthesis,K.U.Leuven,2002.[21]DannyB.LangeandMitsuruOshima.ProgrammingandDeploying JavaMobileAgentswithAglets.Addison-Wesley,September1998.[22]J.E.White.TelescriptTechnology:TheFoundationfortheElectronic MarketPlace.Whitepaper,GeneralMagicInc,1994.[23]AnuragAcharya,M.Ranganathan,andJoelSalz.Sumatra:ALanguage forResource–awareMobilePrograms.InJ.VitekandC.Tschudin,editors,ProceedingsoftheSecondInternationalWorkshoponMobileObjectSystems:TowardstheProgrammableInternet,LectureNotesinComputerScience,LNCS1222,pages111–130.Springer-Verlag,April1997.[24]IVK++Technologies.AGGrasshopper2.http://www.grasshopper. de.[25]Cetus.MobileAgents. agents.html. http://www.cetus-links.org/oo_mobile_ [26]YvoDesmedt.Societyandgrouporientedcryptography.InC.Pomer-ance,editor,AdvancesinCryptologyCrypto’87,LectureNotesinCom-puterScience,LNCS293,pages120–127.Springer-Verlag,1987.[27]SusanK.Langford.ThresholdDSSSignatureswithoutaTrustedParty. InDonCoppersmith,editor,AdvancesinCryptology–CRYPTO’95,LectureNotesinComputerScience,LNCS963,pages397–409.Springer-Verlag,August1995.[28]AdiShamir.Howtoshareasecret? 22(11):612–613,November1979. CommunicationsoftheACM, 28 AppendixASecretSharing Theprincipleofsecretsharingistodivideasecret(e.g.,theprivatekeytocalculateadigitalsignature)amongnparties(e.g.,mobileagents)suchthateverygroupofkormorepartiescanreconstructthesecret,butthateverygroupoflessthankpartieshasabsolutelynoinformationaboutthesecret.ThiscanbeaccomplishedbyusingthethresholdschemeofShamir[26,27,28]. A.1Shamir’sThresholdScheme ThethresholdschemeofShamirisbasedontheinterpolationofpolynomials.Toconstructapolynomialofdegreembyinterpolation,oneneedsatleastm+1distinctpointsofthatpolynomial.Ifonlymorlesspointsareavailable,onecannotuniquelydeterminethepolynomial.Thisisexactlythepropertythatweneedforsecretsharing. SupposewehaveafinitefieldGF(q)withqaverylargeprimenumber.Theuserwhowantstodivideasecretdamongnpartieschoosesk−1randomnumbersaiinthefieldGF(q)andtakesa0=d.ThenheconstructsthefollowingpolynomialinthefieldGF(q): f(x)= k−1i=0 aixi (A.1) Noticethatf(0)=d.Itfollowsthatwhenoneknowsthefunctionf(x),one alsoknowsthesecretd.Thefunctionf(x)hasdegreek−1,soatleastkpoints(xi,f(xi))arenecessarytoreconstructf(x)(andthustodeterminethesecretd).Ifonehaslessthankpoints,onecannotreconstructf(x).Thisisexactlywhatweneed!Itisquiteobviousthateverymobileagentwill 29 getsuchacouple(xi,f(xi)).AgroupSofkmobileagentswillreconstructf(x)byinterpolation: f(x)= i∈S f(xi) (x−xj) modq (x−x)ij j∈S,j=i (A.2) Ifwereplacexby0informulaA.2,wegetf(0).SowecancalculatethesecretdbyusingformulaA.3: d=f(0)=ci,Sf(xi)modq(A.3) i∈S ci,Sisaconstantthatcanbecalculatedinadvanceifoneknowswhichgroup ofkagentswillbeusedtocalculated.Thisconstantdoesnotdependonthesecretd. FormulaA.3canbesimplifiedincertaincircumstances.Itissometimespossibletocalculateeverythingmodulom(mdoesnothavetobeaprimenumber)insteadofworkinginGF(q).Thisisthecasewhenthevalues(xi−xj)haveaninverseforeveryvalueofiandj.Ifeveryagentgetsthecouple(i,f(i))(soxi=i),thentheaforementionedconditioniscompletelyanaloguetotherequirementthatmdoesnothaveprimefactorssmallerthann(thenumberofmobileagents)[27]. A.2VerifiableSecretSharing Howdoesoneknowwhichkvalueshavetobeusedtoreconstructthesecretd?Anattackercouldtrytopresentawrongvaluef(i)sothatthesecretdwon’tbereconstructed.Toavoidthisattack,everyagenthastoprovethatitgivesthecorrectvaluef(i).Thisproofmusthowevernotrevealanyin-formationaboutf(i),soaspecialzero-knowledgeproof(calledcommitmentintherestofthispaper)isneeded.Therearedifferentmethodstoconstructsuchacommitment.IfoneextendsShamir’ssecretsharingschemewiththetechniqueofcommitments(whichwillalwaysbedoneinpractice),thenthisextendedtechniqueiscalledverifiablesecretsharing. A.3Choiceoftheparameterk Theprevioussectionshaveexplainedhowagroupofkmobileagents(outofatotalofnagents)canreconstructasecretd.Howdoesonechoosetheparameterk?Thisisanimportproblem,becausethesecurityofthesecretsharingschemedependsonthischoice. 30 First,onedeterminesanupperboundonthenumberofmobileagentsthatareundercontrolofanattacker.Letscallthisupperboundt.kcertainlyhastobelargerthant,becauseotherwisetheattackercouldcalculated.Sokhastobeaslargeaspossible!Onecanhowevernotchooseklargerthann−t,becausethiswouldmeanthattherearenotenough“benignant”mobileagentstocalculated.Inmostcases,tisverydifficulttodetermine,soone .choosesklargerthan(orequalto)n2 31 因篇幅问题不能全部显示，请点此查看更多更全内容