Everyday Cryptography This page intentionally left blank Everyday Cryptography Fundamental Principles and Applications KEITH M. MARTIN ProfessorofInformationSecurity InformationSecurityGroup RoyalHolloway,UniversityofLondon 3 3 GreatClarendonStreet,OxfordOX26DP OxfordUniversityPressisadepartmentoftheUniversityofOxford. ItfurtherstheUniversity’sobjectiveofexcellenceinresearch,scholarship, andeducationbypublishingworldwidein Oxford NewYork Auckland CapeTown DaresSalaam HongKong Karachi KualaLumpur Madrid Melbourne MexicoCity Nairobi NewDelhi Shanghai Taipei Toronto Withofficesin Argentina Austria Brazil Chile CzechRepublic France Greece Guatemala Hungary Italy Japan Poland Portugal Singapore SouthKorea Switzerland Thailand Turkey Ukraine Vietnam OxfordisaregisteredtrademarkofOxfordUniversityPress intheUKandincertainothercountries PublishedintheUnitedStates byOxfordUniversityPressInc.,NewYork ©KeithM.Martin2012 Themoralrightsoftheauthorhavebeenasserted DatabaserightOxfordUniversityPress(maker) Firstpublished2012 Allrightsreserved.Nopartofthispublicationmaybereproduced, storedinaretrievalsystem,ortransmitted,inanyformorbyanymeans, withoutthepriorpermissioninwritingofOxfordUniversityPress, orasexpresslypermittedbylaw,orundertermsagreedwiththeappropriate reprographicsrightsorganization.Enquiriesconcerningreproduction outsidethescopeoftheaboveshouldbesenttotheRightsDepartment, OxfordUniversityPress,attheaddressabove Youmustnotcirculatethisbookinanyotherbindingorcover andyoumustimposethissameconditiononanyacquirer BritishLibraryCataloguinginPublicationData Dataavailable LibraryofCongressCataloginginPublicationData LibraryofCongressControlNumber:2011944049 TypesetbyCenveoPublisherServices PrintedinGreatBritain onacid-freepaperby ClaysLtd,StIvesplc ISBN978-0-19-969559-1 1 3 5 7 9 10 8 6 4 2 Preface Cryptography is a subject whose relevance to everyday life has undergone a dramatic transformation. Cryptography used to manifest itself in the public imagination through its historical use, primarily to protect military communications,andthroughrecreationalpuzzles.However,largelyduetothe developmentofcomputernetworks,particularlytheInternet,mostofusnowuse cryptographyonadailybasis. Cryptographyisfundamentaltotheprovisionofawidernotionofinformation security.Electronicinformationcaneasilybetransmittedandstoredinrelatively insecureenvironments.Thishasresultedinfundamentalchangestotherisksto which information is exposed. As the financial impact of information security incidentsrises,sodoestheneedforinformationsecurityprotectionandcontrol. Cryptography is a vital technology that underpins many of these controls. It provides a suite of basic mechanisms for implementing the security services that protect electronic information, such as confidentiality, data integrity and authentication. Cryptography does not secure information on its own, but many technical mechanisms for protecting information have cryptography at theircore. Cryptography is thus an important subject for anyone with an interest in information security. Other reasons for the wide interest in cryptography as a subjectare: • Cryptography plays an interesting political role. It is a key technology during timesofconflict.Itsmodernusepresentssocietywithseveralintriguingmoral andpoliticaldilemmas. • Cryptographyhasawideintrinsicappealtothegeneralpublic.Manypeople arefascinatedby‘secrets’and‘codes’.Thishasbeensuccessfullyexploitedby themainstreammedia. Whoshouldreadthisbook? Therehavebeenmanybookswrittenaboutcryptography,butwhatdistinguishes theapproachtakeninthisbookisthecombinationofthefollowing: FundamentalprinciplesItisintendedtobebothrelevantandrelativelytimeless. Itiseasytowriteacryptographybookthatisquicklyoutofdate.Thisbookis intendedtobejustasrelevantintenyearstimeasitwouldhavebeenrelevant PREFACE tenyearsago.Thisisbecauseitisprimarilyconcernedwiththefundamental principlesratherthantechnicaldetailsofcurrenttechnology. Application-focussedItisprimarilyconcernedwiththecryptographythatauser orpractitionerofinformationsecurityneedstoknow.Whilethereisagreat dealofcontemporarytheoreticalresearchoncryptography,fewoftheseideas make it through to real-world applications, which tend to deploy only well- tested and understood techniques. This book focusses on cryptography for everydayapplications. Widely accessible It is intended to be suitable as a first read on cryptography. It focusses on core issues and provides an exposition of the fundamentals of cryptography. Note that it deliberately does not concentrate on the mathematicaltechniquesunderpinningcryptographicmechanisms.Thisbook isintendedtobeintroductory,self-containedandwidelyaccessible. Wewillexplainwhycryptographyisimportant,howitcanbeused,andwhat the main issues are regarding its implementation. The main requirements that guidedthewritingofthisbookwerethatitshould: 1. assumenopriorknowledgeofcryptography; 2. requirealmostnopriorknowledgeofmathematics; 3. focus on the principles behind cryptography, rather than the mathematical detailsofhowitworks; 4. stressthepracticalissuesthataccompanytheuseofcryptography; 5. presentcryptographywithinthecontextofitbeinganunderlyingtechnology thatsupportsinformationsecurity,ratherthanasatopicinitsownright. It can either be read as a self-contained introduction to cryptography or can be used to support an educational course on cryptography. To this end, some supporting activities have been linked to the main chapters. The intended audiencesareprimarily: Users and practitioners of information security Cryptography is a subject of relevancetoanyonewhoneedstosecuredigitaldata.Thisbookisintendedto beofinterestto: • generalusersofinformationtechnologywhoseekanunderstandingofhowto protecttheirdata; • informationtechnologyprofessionalswhoneedtoapplysecuritytechniques todata; • informationsecurityprofessionalswhoseroleistoprotectinformation; • managers of organisations who seek an understanding of issues concerning datasecurity. Students of cryptography It could form the basis for an undergraduate or postgraduatecoursethatcoverstheprinciplesofcryptographywithoutdelving into the mathematical detail of the underlying algorithms. Indeed this book vi PREFACE has been developed from precisely such a course. It may also be of interest tostudentsstudyingthemathematicsofcryptography,sinceitcomplements more mathematical treatises by providing a ‘bridge’ between the theory of cryptography and the real-world problems that it attempts to solve. For studentswhoalreadyknowthe‘how’,thisbookwillexplainthe‘why’. General interest audience It has been written in order to appeal to a general science or engineering audience who seek a greater understanding of what cryptographyisandhowitworks. Backgroundtothisbook This book has grown from a cryptography course offered by the Information Security Group at Royal Holloway, University of London. Royal Holloway has been a research centre for cryptography since the early 1980s and has a longassociationwithindustrialandgovernmentalapplicationsofcryptographic techniques. In1992,RoyalHollowaylaunchedanMScinInformationSecurity,whichwas one of the first qualifications of its kind in the world. This provides a broad introduction to the wide discipline of information security. The core of this programmeconsistsofinformationsecuritymanagement,cryptography,network security and computer security. The module on cryptography is significant because the students who attend it do not necessarily have a mathematical background,andneitheraretheyparticularlyinterestedinacquiringone.What theyneedtoknowispreciselywhatcryptographydoes(anddoesnotdo)andhow itcanbeused.Theydonotneedtoknowexactlyhowitworks.Manystudents commencethismodulewithadegreeoftrepidation,butalmostallemergewith agreatfeelingofachievement(andperhapsrelief!),whichstronglysuggeststhat thepitchisrightforthisintendedaudience. The original cryptography module at Royal Holloway was designed by Professor Fred Piper, who co-authored one of the first academic books on cryptography[29]in1982andhasplayedanenormouslysignificantroleinthe developmentofacademicandindustrialinformationsecurityactivitiesintheUK. Along with Professor Sean Murphy, he published the popular Cryptography: A VeryShortIntroductionin2002[157],whichpresentsasignificant‘contraction’ ofthematerialcoveredbytheRoyalHollowaymoduletoageneralaudience. I took over the main teaching of the Royal Holloway module in 2004. Ihavespentmuchofthelastdecadeteachingcryptographytonon-mathematical students, including industrial courses and presentations to young audiences. Ihavealsotaughtcryptographyboth‘face-to-face’and‘online’,sincetheRoyal Holloway MSc in Information Security is also offered to distance learning students.Thisbook,whichcouldtoanextentberegardedasamuchexpanded andmore‘academic’versionof[157],hasarisenfromthejoysandchallengesof alloftheseexperiences. vii PREFACE Structure Thebookisdividedintofourparts: PartI:SettingtheScene.Chapters1to3providefundamentalbackground.The needforcryptographyismotivatedinChapter1andsomeofthecoresecurity servicesthatcanbeprovidedbycryptographyareidentified.Thebasicmodel ofacryptosystemisintroducedandtheuseofcryptographyisdiscussed.We lookbackatanumberofhistoricalencryptionalgorithmsinChapter2.Most oftheseareunsuitableformodernpracticaluse,buttheyillustratemanyofthe coreideas,aswellassomebasicencryptionalgorithmdesignprinciples.The differencesbetweensecurityintheoryandpracticearediscussedinChapter3. Itisshownthatunbreakablecryptosystemsexist,butarenotpractical,andthat mostpracticalcryptosystemsarebreakableintheory.Therealworldisalways about compromise. We argue that the study of cryptography is essentially the study of a ‘toolkit’ of cryptographic primitives that can be assembled in differentwaysinordertoachievedifferentsecuritygoals. PartII:TheCryptographicToolkit.Chapters4to9explorethevariouscompo- nents that make up the cryptographic toolkit. This includes cryptographic primitives and the cryptographic protocols that combine them. We begin with the provision of confidentiality. There are two types of cryptosystem, and we look at the first of these with respect to providing confidentiality in Chapter 4, which deals with symmetric encryption. Different types of symmetric encryption algorithms are discussed, as are the different ways in whichtheycanbeused.InChapter5welookatpublic-keyencryption.The motivationforpublic-keyencryptionisexplainedandtwoimportantpublic- keycryptosystemsarestudiedinsomedetail.InChapter6welookattheway inwhich(symmetric)cryptographycanbeusedtoprovidedataintegrityand thestrongernotionofdataoriginauthentication.WethenlookinChapter7at cryptographictechniquesforprovidingnon-repudiation,focussingondigital signature schemes. Chapter 8 explains how cryptography can be used to provide entity authentication. This chapter also considers random number generation, which is often required for entity authentication mechanisms. Finally, in Chapter 9 we look at how these cryptographic primitives can be combinedtoformcryptographicprotocols. PartIII:KeyManagement.InChapters10and11weexplorewhatisarguablythe mostimportant,andoftenoverlooked,areaofcryptographyfromapractical perspective:keymanagement.Thisunderpinsthesecurityofanycryptographic systemandistheaspectofcryptographywhereusersandpractitionersaremost likelytobecomeinvolvedindecisionsconcerningcryptography.InChapter10 wediscusskeymanagementingeneralterms,focussingonthemanagement ofsecretkeys.Thelifecycleofacryptographickeyisstudiedandsomeofthe mostcommontechniquesforconductingthevariousphasesofthislifecycle arediscussed.InChapter11welookatfurtherissuesofkeymanagementthat particularlyrelatetopublic-keycryptography. viii PREFACE Part IV: Applications. In Chapter 12 we ‘tie up’ the previous material by examining some applications of cryptography. Since many of the issues that were raised in the previous chapters require decisions that are application- dependent, we demonstrate how several important applications actually addressthem.Inparticular,wediscusswhyparticularcryptographicprimitives are used and how key management is conducted. While the cryptographic applicationsthatwediscussareofinterestintheirownright,themainpurpose istolinkupthepreviouslydiscussedideas.Thischapteris,inevitably,slightly moredetailedthanthepreviousones. Additionalfeaturesofthebookare: Furtherreading.Eachchapterincludesabriefsummaryofresourcesthatcouldbe usedinordertofurtherpursuethetopicsdiscussed.Theseareonlyintended to be starting points, and are by no means comprehensive. These resources arenormallyamixofaccessiblereading,importantresearcharticles,relevant standards and useful web links. Carefully directed web searches should also proveaneffectivemeansoffindingfurtherinformation. Activities.Eachchapteralsohasalistofactivities,whicharedesignedtoenhance the understanding of the chapter material. Some activities have definitive answers,whilemanyareopen-ended.Whiletheseactivitiesmaybeskipped, theyarealldesignedtostructurefurtherexplorationofthechaptermaterial. Laterchaptersdonotrelyontheactivitiesofpreviouschaptershavingbeen completed. Mathematics Appendix. A short appendix containing some elementary back- ground mathematics is included. It is intended that the book can be comfortablyreadwithoutconsultingthisappendix.However,inordertohave adeeperappreciationofsomeoftheissuesconcerningcertaincryptographic primitives,particularlypublic-keycryptosystems,itwillhelptohavedigested thismaterial. Howtousethisbook Thebookhasanongoingnarrativeand,asaresult,thematerialismosteffectively readintheorderinwhichitispresented.Thatsaid,itiscertainlypossibletodip intotopicsasrequired. The chapters could well (and do) form the outline of a course on practical cryptography.Tothisend,‘learningoutcomes’areidentifiedatthestartofeach chapter.Whileitisveryhardtoimaginethatsuchacoursecouldbeconsidered completeifanyofthechaptertopicswereomitted,thebookcontainsabitmore material than can be comfortably covered in a typical semester-based course. A balanced course on practical cryptography should pay attention to all the core security services and illustrate them by discussing a range of appropriate mechanisms,however,someofthechaptermaterialcouldselectivelybeomitted ix