A Logic of Authentication Michael Burrows hhrtiu Abstract Autllcnt icntioii protocols a re the basis of seciuity iii many clisti il utetl systems mid it is therefore esseiitial to eiisure t lia t t liese prot ocols function correctly Uufortuiia tely t licir tlcsign 1 s beeii estremcIy xotocols found iii the literature security flaws Abacli R oger Needham tocols found ii1 the litera ture contain retlunda iicies or security flaws To a dcl to tl ie cotifusion protocols use differeut cryptosystems e g DES R SA a ud ca ter for a wide ra uge of a pplicakious it is seldom c1ea r liow these protocols error prone hbst of the coutniii redundancies or The goa of a utllentication ply thougll tioii A siinple of trustworthy logic 1ia s aHowed us to describe the beliefs parties involved iii a utllentica tioil proto cols alit1 the evol11tioii of conliiiunicat ioii of these beliefs as a consequence We lia ve been able to esplain a va riety of lut lieiit icatic ii protocols foriiially couipa re iii tlie guaraiitees to discover subtleties a nd errors in tliein and to suggest iiiiprovenieiits Iii this p l rr we pleseut the logic al rl t lleil give the results of 011r aimlysis of four l l lisl etl 1xotocols clxxxzii either liecilllsc of their pract ica l iinpc rtance or Ixcn use they serve t o illust rate 0111 lllctllcKl lx etititletl ca u be stated rather a ncl imprec isely peollle to believe that coiuputers tliey sim After autllcxticaservices slio ild are comiiuuiica tiiig with ea cll other ailcl not witli intruders Iii t liis ya per we defiiie a logic of a lt lieiitica tion to express such beliefs precisely snd to captlue the reasoning a re examples of questions tlmt lexls to them These t1la t we woi ltl like t o lx able t o a iiswer wi tli the help of formal iiie tliods Does this Ixotocol work Exactly 1 Iiltroductioil lit li iit ic akil plotocols a re t lie hasis of securit y iii iiaiiy tlistrilxikd systems ant1 it is therefore esseubial to eiisllre t11 1t t hcse p t ocols fuuctbu correctly NS UnfortuIla tcsly their design has been estremel error prone Al informally two yrinciyals they offer work Ca 11 it be ma w1la t does this protocol to achieve Does this protocol ailotlier one ueed more assunlptiolls Does this protocol do aalythiug tha 11 unnecessary In la ter sections we sl10w 110 t lle logic 11il seiia l 11sto answer these questions for a iiuinl er of pullislietl protocols It is worth iiotirig tlia t we have iiot tried to auswcr soiiie otller questions Siuce we operate at au a bstra ct level we t l oq ut lient icat ic il protocols t ypically have few messagrs t lle coiulxxi bion of cn cli message cn ii be subtle tlo ilot coiisitler and the iilternst ions I etwecn the messages ca u be tomplc s I rcovcr protocol designers often iiiisuiitletstnii l inapproprin te 11seof cryptosystcnls as in VI Furtllcrmore while we allow for t lie possibility of hostile iiit rliclcrs t lle arxilable there is 110 at tempt to deaJ wi tli tile a utlimitica tioil of r7 i teclliiiques lxot occ ls inal l lopliately col ying features 4s a result from esistiilg maiiy of the l ro Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage the ACM copyright notice and the title of the publication and its date appear and notice is given that copying is by permission of the Association for Computing Machinery To copy otherwise or to republish requires a fee and or specific permission 0 1989 ACM 089791 338 3 89 0012 0001 1 50 tatioiis errors iiitrotlucetl of a l rotocol untrustworthy principal fmws siicli by concrete iiiilk iueiia s tlcatlloclis or CV IJ iior to detect weakiiesscs of eil Michael Burrows and Martin Aba di a rewith Digital Equipment Corpora t ion Systems Research Center 130 Lytton Avenue Palo Alto Cabfornia 94301 USA Roger Needham is with the Universit y of Cambridge Computer Labora tory Corn Exchange Street Cambridge CD2 3QG UK The three al thors conipleted and part of this work at Digital pa rt a t the University Equipment of Cambridge Corpora tion 2 The Formalisnl Iii this section n e cl 5cril r t lir sy1h i s a iitl sriimntics 0f logic it S lulVS illltl tllC t llSfO lllil t iOll Ill l t WC iIl l lJ to 1nx tocols hfore tllcir fomial analysis 0111 Basic llot ation Simila rly Logical for public keys we poshla te postulates P believes t Q P belie For slmwl P sees Y lc t Q said S secrets we postulat e I believes Q k P believes P sees LY Lr Q said S That is if P believes tllat the secret I is shared wit 11 Q n ntl sees 5 tllen P believes that Q olicc mid X This post k is sound Ixca use the rules for sees given Ixlowv guarantee S wn s not just uttered by P l iinself l The it rule expresses he check that no7 ce oeri cn tio7t is llleSSil e that ITCCllt EUlct IlellW tallilt the sender stiIl 1 elieves iii it 17 believes fresh X P believes P believes Q said S Q believes X That is if P Ideves tht X coultl hve hell ut t erecl IWxllt ly ill the rmxmt R ll l that Q oiicc sid Y eitlier in the past or iii the lxesmt thn P lxlievcs tlmt Q L eves S For the sa 1 of simplicity X must lx clea rtext that is it sliould llot include ally sl1l foL llllllil of the fom 1 h 0lllJ l The juTidi ti07 rule skates that if P lxlieves that Q lms jurisc1ic tic m over S tlleu I trusts Q on the hut11 of A P believes Q controls lr P believes Q believes S P believes I 0 If a lwincipl sees a formula then lie dso sees its coin1 tnlruts 1m vidwI lie l iiows the iiccesmry lays P sees 5 Y P sees Y P believes P believes P believes Q said Y P sees S P sees I Q P P sees S I P sees X P P sees YJ 1 P se S P believes where Q controls S is the u5sult of iiista nt ia tiiig mriables I I in Q controls X siinulta iicously L P sees S Ii t P sees S foriiinl Re lll tllat Y I stnntls for 21 fc rllltila of t l le f Ynl S 1 fr om R As a sitlc concli tion it is recpkxl tht R P that is S 1 is not from F hinlsclf In the li tcmture then P the 011 l i11 t 11111st I believes Of il fO lllllli is fldl also lx flWl1 thll P believes P believes fresh Y fresh Y I …