Security Models and Proofs for Key Establishment P

SecurityModelsandProofsforKeyEstablishmentProtocolsbyEddieM.NgAthesispresentedtotheUniversityofWaterlooinful¯llmentofthethesisrequirementforthedegreeofMasterofMathematicsinCombinatoricsandOptimizationWaterloo,Ontario,Canada,2005c°EddieM.Ng,2005Author'sdeclarationforelectronicsubmissionofathesisIherebydeclarethatIamthesoleauthorofthisthesis.Thisisatruecopyofthethesis,includinganyrequired¯nalrevisions,asacceptedbymyexaminers.Iunderstandthatmythesismaybemadeelectronicallyavailabletothepublic.iiAbstractInthisthesiswestudytheproblemofsecurekeyestablishment,motivatedbytheconstruc-tionofsecurechannelsprotocolstoprotectinformationtransmittedoveranopennetwork.Inthepast,thepurportedsecurityofakeyestablishmentprotocolwasjusti¯edifitcouldbeshowntowithstandpopularattackscenariosbyheuristicanalysis.Sincethisapproachdoesnotaccountforallpossibleattacks,thesecurityguaranteesarelimitedandofteninsu±cient.Thisthesisexaminestheprovablesecurityapproachtotheanalysisofkeyestablishmentprotocols.Wepresentthesecuritymodelsandde¯nitionsdevelopedin2001and2002byCanettiandKrawczyk,critiquetheappropriatenessofthemodels,andprovideseveralsecurityproofsunderthede¯nitions.Inaddition,weconsidertheimportanceofthekeycompromiseimpersonationresiliencepropertyinthecontextofthesemodels.Welistsomeopenproblemsthatwereencounteredinthestudy.iiiAcknowledgementsIwouldliketosincerelythankmysupervisor,AlfredMenezes,forhisadvice,guidance,patienceandsupport.Iwouldalsoliketothankmytworeaders,DougStinsonandEdlynTeske,forcarefullyreviewingmythesis.Theirvaluablefeedbacksandsuggestionsaregreatlyappreciated.Iwouldliketothankthefacultyandsta®membersoftheC&ODepartmentformakingmygraduateexperiencetrulystimulatingandrewarding.AspecialthanksgoestoMargFeeneyforassistingmewithvariousadministrativetasksfarbeyondherduties.ThankstoWes,Patrick,Yi,Max,Bobby,Luis,James,Omran,Jenny,LemmusandotherfriendsandcolleaguesformakingmystayatWaterlooenjoyableandmemorable.Finally,Iwouldliketothankmyfamilyfortheirloveandencouragement.ivContents1Introduction11.1TheKeyDistributionProblem.........................21.2ASolution:KeyEstablishmentProtocols...................31.3MathematicalPreliminaries..........................41.3.1AlgorithmsandComplexity......................41.3.2Polynomial-timeDistinguishability...................51.3.3IntractabilityAssumptions.......................101.4TheProvableSecurityApproach........................121.5Notations....................................171.6StructureoftheThesis.............................182KeyEstablishmentProtocols192.1BasicConcepts.................................202.2ExamplesofProtocols.............................222.2.1Keytransportusingsymmetriccryptography.............222.2.2Keytransportusingpublickeycryptography.............222.2.3Keyagreementusingsymmetriccryptography............232.2.4Keyagreementusingpublickeycryptography............232.3DesirableAttributesofKeyEstablishmentProtocols............252.3.1Fundamentalattributes.........................252.3.2Attributesconcerningcompromisedkeys...............27v2.3.3Otherdesirableattributes.......................292.3.4Theimportanceoflistingdesirableproperties............303TheCanetti-KrawczykSecurityModelforKeyEstablishmentProtocols333.1RelatedWork..................................343.2CommunicationModel:CK01Model.....................353.3AttackCapabilities...............................383.4AdversarialGoals................................423.5De¯nitionofSecurity:SK1-Security......................433.6ProvingSecurity................................444CritiqueoftheCanetti-KrawczykModel524.1Su±ciencyoftheModel............................534.1.1Propertiessatis¯ed...........................534.1.2Unknownkeyshareresilience.....................554.1.3Securechannelsguarantee.......................584.1.4Propertiesnotguaranteed.......................594.2Modi¯cationstotheModel...........................614.2.1Forwardsecrecy.............................614.2.2Keycompromiseimpersonationresilience...............624.3ComparisonswithOtherModels........................674.3.1Thepost-speci¯edpeer(CK02)model................674.3.2TheBellare-Rogawaymodel......................784.3.3TheUniversalComposabilitymodel..................835ApplicationsoftheCanetti-KrawczykModel875.1BasicDi±e-HellmanProtocols.........................875.1.1PartialinformationaboutDi±e-Hellmankeys............875.1.2SK1-Securityintheauthenticated-linksmodel............895.1.3SK1-Securityintheunauthenticated-linksmodel...........91vi5.2IKE/SIGMAProtocols.............................935.2.1SIGn-and-MAcdesign.........................945.2.2SK2-SecurityintheCK02model...................955.2.3Identityprotectingvariants......................976Conclusion996.1KeyEstablishmentBestPractices.......................996.2OpenQuestionsandFutureWork.......................100Bibliography101viiListofFigures1.1TheSoloway-StrassenprimalitytestSS:f0;1gk!f0;1g..........93.1Adversarialactionsunderdi®erentprotocolstates..............413.2Thedistinguishin