Home

Automated analysis of security protocols with global state

Contents

1. Proposition 3 Let Tr be a set of traces and p a well formed trace formula We have that Tr E y iff hide Tr E o where x is either V or 3 Proof We start with the case x J and show the stronger statement that for a trace tr V0 30 if tr 0 E y then hide tr 0 e v and V0 30 if hide tr 0 E y then tr 0 Fy We will show both statements by a nested induction on tr and the structure of the formula The underlying well founded order is the lexicographic ordering of the pairs consisting of the length of the trace and the size of the formula If tr 0 then tr and tr hide tr which allows us to directly conclude letting 0 0 If tr n we define tr and F such that tr tr F By induction hypothesis we have that v0 30 if tr 0 E y then hide tr 8 E y and V0 30 if hide tr 0 E y then r 8 E y We proceed by structural induction on y ev 1 9p i lt j p t f or ty t In these cases we trivially conclude as the truth value of these formulas does not depend on the trace and for both statements we simply let 0 0 e p f Qi We start with the first statement Suppose that tr 0 F f Qi If 0 i lt n then we have also that tr 0 f i By induction hypothesis there exists 0 such that tr 9 FE f i Hence we also have that tr 8 E f i and letting 6 6 allows us to conclude If 0 i n we know that f trn As q is well formed
2. Insert t t state We can extend the previous execution by one step using ri therefore F F Fu Insert t t Jom 0 Psp St Pg py Sn Sa esc LP with S41 Sr 4 V state U state 1 It is left to show that Conditions I to B hold for n This step is labelled F f n Insert t t hence Condition 8 holds To see that Condition 2 holds we let j f n for which both conjuncts trivially hold Since by induction hypothesis Condition 7 holds i e F1 Fw F a it holds for this step too In particular if F3 Fw F ain and Fi Fw F Qnotin We also have that F1 Fw Ffin F o and Fi Fawr Fy n F Qnotin as the Insert action was added at the last position of the trace it appears after any InIn or IsNotSet action and by the semantics of the logic the formula holds Since P P 4 insert t t Q U Q and O state 1 by definition of P _ p W have that Condition 4 holds Condition T Condition 3 Condition 5 and Condition 6 hold wb 36 Case pur cu unm m NET SE L SMS P U Q on 1 s By induction hypothesis P 4 p Sw Let p and be such that delete t O p state t By Definition 20 there is a ri ginsts P _ such that state is part of its premise By definition of P _ we can choose ri statep t Delete t JI statej 1 We can extend the previous execution by one step using ri therefore Delete
3. M Bond and R Anderson API level attacks on embedded systems IEEE Computer Magazine pages 67 75 October 2001 M Bortolozzo M Centenaro R Focardi and G Steel Attacking and fixing PKCS 11 security tokens In Proc 17th ACM Conference on Computer and Communications Security CCS 10 pages 260 269 ACM Press 2010 CCA Basic Services Reference and Guide Oct 2006 Available online S Delaune S Kremer M D Ryan and G Steel Formal analysis of protocols based on TPM state registers In Proc 24th IEEE Computer Security Foundations Symposium CSF 11 pages 66 82 IEEE Press 2011 S Delaune S Kremer and G Steel Formal analysis of PKCS 11 and proprietary extensions Journal of Computer Security 18 6 1211 1245 Nov 2010 S Escobar C Meadows and J Meseguer Maude npa Cryptographic protocol analysis modulo equational properties In Foundations of Security Analysis and Design V volume 5705 of LNCS pages 1 50 Springer 2009 S B Fr schle and N Sommer Reasoning with past to prove PKCS 11 keys secure In Proc 7th International Workshop on Formal Aspects in Security and Trust FAST 10 volume 6561 of LNCS pages 96 110 2010 J A Garay M Jakobsson and P D MacKenzie Abuse free optimistic contract signing In Advances in Cryptology Crypto 99 volume 1666 of LNCS pages 449 466 Springer 1999 J D Guttman State and progress in strand spaces Proving fair exchange J Autom Reasoning
4. S exec P such that K t eg S and Sg 1 R S for R MDOvT MDPUB MDFRESH MDAPPLj Let p and t such that out t t Q amp p state 1 By Definition 20 there is a ri ginsts P such that state f is part of its premise From the definition of P _ we see that we can choose ri statep t In t InEvent t gt Out state 1 To apply this rule we need the fact In t Since v i c F t as mentioned Fy before we can apply It follows that there is an execution id m Sn S E exec P such that K t g S and Sw gt R S for R MDOUT MDPus MDF REsH MDAPPL J From S we can now go two steps further using MDIN and ri F Fu InEvent t sn 0 spp S1 py Sy Peppy S Sn ts 3 S 1 s LU 14s exec TP where S 4 SUF In t and Spin S Vf state t U Out t state 1 Taking k n s 1 we immediately obtain that holds Note first that since Su gt R S set S Fr t Out t t M C set S and set S IK t t M C set S Since P Pn 1 out t t O U Q and O amp p state 1 t by definition of P p we have that Pn OP Spm Le Condition 4 holds Condition 5 holds since t was added to 0 1 and Out t added to Sf n 1 Condition holds since K t appears right before InEvent t 3 and Condition 6 hold trivially Case En 1 Sn 1 SM P 4 epu in t N CO 0n 1 La En 1
5. and Sy45 Spin Sw Uf statep r a fresh We define f i f i for i lt n and f n f n 1 2 We now show that holds As by induction hypothesis va Q p state 1 t we also have that P o va Qp for some o and p Extending p with a aj it is easy to see from definition of P _ that Q a op state a As Pn Pn 1 V va Q U Q a V we also immediately obtain that P op Syn Since a is fresh and therefore a En V 41 and F ProtoNonce a holds Condition 2 and hold trivially Case a 1 One 1 SMS Pr 1 9n ee 1 E En 1 Sn 1 SMS Pr 1 0n aue D This step re Fy quires that v 1 0n 1 F t From Lemma 8 follows that there is an execution 05 Ne 2e Sy 2 S ezec h P such that K t g S and Sw gt h S for R EUN vh TE Ad MDAPPr From S we can go one further step using MDIN since K t S Fu K t msr 0 5 p1 1 5 SEP P Sw P Rc p 9 Sa Ss erec TP where Sws SU In t From the fact that Sy jj gt R Sym S and the induction hypothesis we can conclude that holds holds since Pa P _1 and no state facts where neither removed nor added and hold trivially Case Eg 1 On 1 Spats Pr 1 P U out t t 0 Q On 1 L n pe ee ee P i TO Las au Iak Ln 1 This step requires that x is fresh and vEn 1 0 H t Using Lemma 8 we Ffin have that there is an execution 04558 2 S ai
6. g E and there is no j such that i lt j lt n and Delete ti Em Ej or and Insert t1 t2 Em T Ej Since Ej E 0 we know that i lt m Hence by induction hypothesis Sw t1 ta We therefore chose the following transition MS A E41 Sw SMS Prit On La Ena Sn 41 Sip Pad On 4 1 Eua with 441 En Sy Sy ou RA SM S Pritt Pw lookup t as v in Qj else Q P Uf Qul 5 2 oua ow and Luti Ln We define f as on page 5I Therefore Conditions I to 8 hold for i lt n 1 It is left to show that Conditions I to 8 hold for n By definition of P and P _ we have that 01 4 statep t2 for r r v gt te and p p Therefore and since lookup t as v in Q else Q c statep t Prvi Pw lookup t as v in Q else Qo U Q and Sn n 1 V state t Uf statep 1 t t2 holds Conditions 6 and 7 hold trivially Case ri state t IsNotSet ti state o t for some p t and t M By induction hypothesis we have P p Sm and thus as previously established Pj ep 4 1 Let O P such that O p state f Let 0 be a grounding substitution for state Z prems P _ such that t 0 Then 0 induces a substitution 7 and a bijective renaming p for fresh but not bound names in Q such that P 7p Q see Definition 22 From the form of the rule R and since Q P pTp we can deduce that Q lookup t as v in Q else Q
7. if M N then P else Q p X event F P p insert s t P p 3 delete s P p 3 lookup M as v in P else Q p X lock s P p unlock s P p Ll ab r P p z state 2 gt state z state 1 Z state z gU P p 1 4 U Q p 2 2 Istate 2 state 1 Z U P p 1 a state 1 Fr na fresh ProtoNonce n fresh amp na fresh P p 1 state z In M MInEvent M Hog Cannan state 1 Z na fresh Out V state 1 Z state Z Msg M N state 3 state z Ack M N statep 1 U P p 1 2 In M N 4InEvent M N gt state 1 U vars N state Z Msg M N U P p 1 2 U vars N state z 4 Eg M N state z M NotEq M N gt U P p t 2 U Q p 2 state 4 Event F state 4 Insert s state 2 Delete s gt state z IsIn M v state 2 state 1 Z U vars N Ack M N Y state 1 4 istatep 2 state 1 U P p 1 2 state 1 U P p 1 states 3 U P p 1 21 state M v IsNotSet M state 2 U P p 1 5 v U Q p 2 2 Fr lock state 2 Lock lock s Br R state 1 lock U P p 1 4 state lt Unlock lock s 5 statey 1 2 Ng U P p 1 i state z 1 Event a r statej 1 4 U vars 1 U P p
8. lineis lpersistent E T for some lpersistent pm Dg Note that linear En and r uniquely identify which rule in P ri is an instance of with exactly one exception Ha P p z event a P p z Luckily we can treat the last as a special case of the first If R is uniquely determined we fix some ri ginsts R Case R INIT or R MD MDIN In this case 025 29 is not a well formed msr execution J gt In t Case R MDIN Let t M such that ri Rr xL dK t we have that From the induction hypothesis and since j41 En Ex a FN ProtoNonce a g U Bk 1 jen From the induction hypothesis and since no rule producing Out facts is applied between step m and step n we have that zon x D o p Out t Upen Sy Let 7 a FN RepNonce a g Uizjzn Pj Then by Lemma 8 and Lemma 9 we have that v T 05 F t Therefore v y o FH t This allows us to chose the following transition FE K t En Oils S Tu On Luwu En 1 Ond S ds Pwi On 4 1 Ly 41 with TOTEM Dal Su Paiti On 4 1 LwH En Sw oP fnis On Lw Conditions I to S hold trivially Case ri state t 4 for some p and t By induction hypothesis we have P ep Sin and thus as previously established P ep S 4 Let O Ef P such that Q ep state 1 Let 0 be a grounding substitution for state 2 prems P _ such th
9. 48 2 159 195 2012 J Herzog Applying protocol analysis to security device interfaces IEEE Security amp Privacy Magazine 4 4 84 87 July Aug 2006 R K nnemann and G Steel YubiSecure Formal security analysis results for the Yubikey and YubiHSM In Proc 8th Workshop on Security and Trust Management STM 12 volume 7783 of LNCS pages 257 212 2012 D Longley and S Rigby An automatic search for security flaws in key management schemes Computers and Security 11 1 75 89 March 1992 22 21 G Lowe Breaking and fixing the Needham Schroeder public key protocol using FDR In Proc 2nd International Workshop on Tools and Algorithms for Construction and Analysis of Systems TACAS 96 volume 1055 of LNCS pages 147 166 Springer 1996 22 S M dersheim Abstraction by set membership verifying security protocols and web services with databases In Proc 17th ACM Conference on Computer and Communications Security CCS 10 pages 351 360 ACM 2010 23 RSA Security Inc v2 20 PKCS 11 Cryptographic Token Interface Standard June 2004 24 B Schmidt Formal Analysis of Key Exchange Protocols and Physical Protocols PhD thesis ETH Z rich November 2012 25 B Schmidt S Meier C Cremers and D Basin Automated analysis of Diffie Hellman protocols and advanced security properties In Proc 25th IEEE Computer Security Foundations Symposium CSF 12 pages 78 94 IEEE Press 2012 26 B Schmidt S
10. t T and f Init Insert Delete IsIn IsNotSet state Lock Unlock Out Fr In Msg ProtoNonce Eq NotEq Event InEvent Similar to 3 for our translation to be sound we require that for each process there exists an injective mapping assigning to every unlock in a process a lock t that precedes it in the process syntax tree Moreover given a process lock t P the corresponding unlock in P may not be under a parallel or replication These conditions allow us to annotate each corresponding pair lock t unlock t with a unique label l The annotated version of a process P is denoted P The formal definition of P is given in Appendix A In case the annotation fails i e P violates one of the above conditions the process P contains l Definition 12 well formed A ground process P is well formed if e no reserved variable nor reserved fact appear in P e any name and variable in P is bound at most once and e P does not contain L For each action I a r that appears in the process the following holds for each l a gt r g ginsts l a r we have that 5 names r FN C Dizzy names l O FN A trace formula p is well formed if no reserved variable nor reserved fact appear in q The two first restrictions of well formed processes are not a loss of generality as processes and formulas can be consistently renamed to avoid reserved variables and a converted to avoid binding names or variables several time
11. the backward search eventually reaches the matching lock including the annotation which is determined to be a and hence appears in the Fr premise 3 Because of the Fr premise any existing subgraph that already contains the first of the two original locks would be merged with the subgraph resulting from the backwards search that we described in the previous step as otherwise Fr a would be added at two different points in the execution 4 The result is a sequence of nodes from the first lock to the corresponding unlock and graph constraints restricting the second lock to not take place between the first lock and the unlock We note that the axiom Wock is only instantiated once per pair of locks since it requires that i lt j thereby fixing their order In summary the annotation helps distinguishing which unlock is expected between to locks vastly improving the speed of the backward search This optimisation however required us to put restrictions on the locks 16 6 3 Correctness of the translation The correctness of our translation is stated by the following theorem Theorem 1 Given a well formed ground process P and a well formed trace formula p we have that traces P E p iff traces LPI F v where x is either V or 3 We here give an overview of the main propositions and lemmas needed to prove Theorem To show the result we need two additional definitions We first define an operation that allows to restrict a s
12. with 41 Ew ET Sw SU SNS Pai P ur P Q On 1 On and Lua Lw Conditions 1 to 8 hold for i lt n 3 It is left to show that Conditions I to B hold for n As established before we have 7 such that N7 p r p t Let state t t be the state variable added to S 4 Then g U vars N V g r t By definition of P we have that state t t prems ginsts P 4 for a grounding substitution 09 1 6 7 Since 7 and p are induced by 6 0 induces 7 7 and the same p We have that Q 7 Plqit p T P g177 p and therefore Q r p state t t Similarly we have P ep state 1 8 We conclude that Condition 4 holds Conditions Condition 1 6 and 7 hold trivially 51 Case ri state t Eq t1 t2 state 1 t for some p t and t t2 M By induction hypothesis we have P p Sm and thus as previously established Py ep S 4 Let O P such that O p state t Let 0 be a grounding substitution for state 2 prems P _ such ibo t 0 Then 0 induces a substitution T and a bijective renaming p for fresh but not ad names in Q such that P 7p O see Definition 22 From the form of the rule R and since Q P pTp we can deduce that Q if t t2 then Q else Q for a process Q P p 1 Tp Since E1 En F a and thus Ei Em F Qeq we have that t g t2 We therefore chose the following transition F MS gt Ew
13. 1 to i must be ground instances of rules P _ and P such that P and P start with unlock commands that are labelled the same and have the same parameter since every variable lock in P appears in a Fr fact in the translation for the corresponding lock command By definition of P this means q and q have a common prefix q that starts with a lock with this label Let q lt q denote that q is a prefix of q Since P gives L if there is a replication or a parallel between q and q or q and since P is well formed does not contain L we have that every state fact state for q lt r g or qu r q appearing in P is a linear fact since no replication is allowed between q and q or q This implies that g q Furthermore every rule in Ug lt r lt qvq lt r lt q P _ adds at most one fact state and if it adds one fact it either removes a fact state where r r 1 or r 2 or removes a fact states mi where r r 1 which in turn requires removing state see translation of out Therefore either q lt g or g lt q But this implies that both have different labels and since P requires Fr I and E distinguishes fresh names we have a contradiction A similiar observation is possible for locks For any 1 u 41 42 if Lock l u g F and Lock l u Eg Fip then 71 i2 since by definition of the translation the transition from i 1 to i or i 2 1 to ig removes fact Fr I From the first observatio
14. Definition 20 there is a ri ginsts P _ such that state t is part of its premise By definition of P _ we can choose ri Fr I state Lock I t state 1 1 for a fresh name J that never appeared in a Fr fact in U lt f n 1 Sj We can extend the previous execution by s 2 steps using an instance of FRESH for l and ri Fi F Fpi Lock l t wer PI S p e IP Bst unu e R exec LPI with Syr4s 1 Sp 4 V states t U Fr l and Sws Spin 1 statep t WF Uf statep It is left to show that Conditions I to S hold for n The step from S to Sr is labelled Fr Lock l t hence and hold Fin also preserves Condition 6 for the new set of active locks Lf n E f n 1 U t In the following we show by contradiction that Qjoc z and therefore holds ojo held in the previous step and F 4 4 is empty so we assume by contradiction that F p Lock I t violates Wyock If this was the case then Ji lt f n l Lock l4 t g F A Vj i j f n Unlock h t g Fj Vdl k ick j Lock le t Ep Fk V Unlock lg t CR FX 2 Since the semantics of the calculus requires that for all t p t t 4 4 by induction hypothesis Condition 6j we have that Vi lt f n 1 li Lock l t Eg lb Jj i lt j lt f n 1 A Unlock h t g F Since Fr 144 and f n f n 1 2 we have Vi lt f n l Lock l1 t Eg F Jj i
15. Letting k n s 1 we immediately have that Condition 8 holds We now show that holds Since by induction hypothesis in t N Q p state t we have that P r in t N Qp for some 7 and p Therefore we also have that P p 17 U 0p Qp 0p and it is easy to see from definition of P _ that Q89 p statey 1 t vars N 0 Since Pn Pn 1 Vf in t N QM U Q we have that P op S Anis 1 6 Condition 4 holds Condition 7 holds since K t N0 appears right before InEvent t N0 Condition d Condition 2 Condition 3 and Condition 7 hold trivially Case S SMS PU out c m QYU in c N Ro L gt E S SMS PU Q R0 c This step requires that 0 grounding for N t g N0 and c g c Let p p and t N such that out c m P amp p statep t in c N Q amp p statey i and there are ri ginsts P _ and ri ginsts P _ such that state and statey t are part of their respective premise From the definition of P _ and the fact that 0 is grounding for N we have rii state t Msg t N8 state 1 rig statey 1 Msg t N0 statey i t U vars N 0 Ack t N6 riz state 1 Ack t N8 statep 1 This allows to extend the previous execution by 3 steps Fa Ti Ti ri Dy D ecc IP Sy Eur S n s 2 E Sn s 1 are Plies exec P where Sw s 2 Sy state t Uf Msg t NO states t D yf e Sw
16. Vi y ici lt f n 2 Insert t y p Fy Iju i lt j f n Insert t vu g Fj v Delete t p Fy which simplifies to Ji f n y Insert t y ee F Vi y i f n 2 Insert t y Fy 3j i j f n Delete t g Fy Now we weaken the statement by dropping the first conjunct and restricting the quantification Vi i lt i f n to Vij i f n since i lt J Ji f n 3j i j f n Vi j lt i f n 2 Insert t y Fy A Delete t g Fj We further weaken the statement by weakening the scope of the existential quantification 47 i lt j lt f n to 37 j f n Afterwards i is not needed anymore Ij i f n Vi j i f n 2 Insert t y Fy Delete t p Fy This statement was obtained under the hypothesis that Ji lt f n y Insert t y g F Hence we have that Vi lt f n y Insert t y g Fi V3j f n Delete t g Fy Vi j lt i f n 2 Insert t y Fy This shows that Condition 7 in particular notin holds Since Pa Pn 1 lookup t as z in Q else Q Y Uf Q and Q state 1 t by definition of P _ we have that holds Condition 1 Condition 3 and hold trivially 38 Case 5 38 410575 13 P U lock t O as dai gt oS PLUTO On 1 n 1U t This step requires that for all t t t 4 1 Let p and t such that lock t O p state t By
17. contains only Fr facts and Out facts Therefore 4 and 5 hold for all n 3 Since Ej 1 En 1 6 and 7 hold for all i n 3 Fix a bijection such that Pa ep Sm We will abuse notation by writing P p state 1 if this bijection maps P to state Since MDOvT MDPuB MDFRESH MDAPPL and FRESH do not add or remove state facts Py ep S 3 Let P Ef P such that P ep statej 5 Let Q Ef p such that Q ep state f Let 0 be a grounding substitution for stateg y prems P _ such that t p 90 Then 6 induces a substitution 7 and a bijective renaming p for fresh but not bound names in Q such that P 7T p Q see Definition 22 From the form of the rules Ry and Rg and since P g P yrp for T and p induced by the grounding substitution for state Z we can deduce that P out t4 t P for a process P P 17p Similarly from the form of R2 we can deduce Q p in ti N Q for N a term that is not necessarily ground and a process Q Pli Since 5 5 p Sn 1 we have that there is a substitution 7 such that Nr p r p tz and g U vars N Vi r z T where f such that stateg 1 f 0 S 1 V S 5 Given that Q p in t1 N Q and P g out t1 t P have that P P Uf out ti to P in t4 N Q V with t p t and t2 p NT Therefore we chose the following transition Fi MS K t1 MS E En Sw S Pu On Ly 9 w 43 Outils Sup Pus On 4 1 Eu
18. e If Py Gp 1 and P 4p S2 then Pi UF Pz Op Si Ut So e If Pi p S and Q p state t for Q P and state t S i e Q and state t are related by the bijection defined by Pa amp p 1 then P1 V O Gp S1 Vf state t Proposition 4 Let A be a finite set lt a strict total order on A and p a predicate on elements of A We have that Vic Apli e Vic A p i vdje A i 3 ow e Wie A i 2 dje A i 3 op j and dic Apli HE Apli AVje A d j pj 30 0 p z _ P Q p pt P p z _ va P p Out M N P p 2 In M N P p Zap lif M N then P else Q D pt event F P p x Sa insert s t P p 3 ij delete s P p 3 lookup M as v in P else Q p i Lm pi 3 lock s P p La state 2 state Z state 1 Z statep 2 Z Pi U P p 1 U Q 2 Istate z statey 1 4 ESA U P p 1 2 statep 2 Fr na fresh A ProtoNonce n fresh statep 1 Z na fresh n U P p 1 na fresh state z In M InEvent M Out N state 1 2 state z Msg M N state 3 semi state Ack M N statep 2 2 U P p 1 2 p 2 state 2 In M N InEvent M N gt statep 1 U vars N statep Z Msg M N state 4 U vars N Ack M N Ts C P p 1 U vars N _ state z 4 Eq M N J
19. for a variable v and two processes Q P 17Tp and Q2 P yoTp Since F4 En F Qnotin there is no lt n such that Insert t t2 g E and there is no j such that i lt j lt n and Delete t Em E or and Insert t1 t3 g T Ej Since Em En 0 we know that holds j lt m Hence by induction hypothesis Sw t is undefined We therefore chose the following transition Fi MS MS ume 2 E fs Sw S Pal On Ly Ena Sn 1 Sy ip Pals On 4 1 Lag with 41 En Sy Sy SMS Pura Py lookup t as v in Q1 else Qo UF 22 F On 1 On and Lyi L 53 We define f as on page 5I Therefore Conditions 1 to S hold for i lt n 1 It is left to show that Conditions 1 to 8 hold for n By definition of P and P _ we have that Q2 state o t Therefore and since lookup t as v in Q else Qz state t Pw 1 Pw lookup t as v in Q1 else Qo V Uf Qo and S 8 1 V state t U state o t Condition 4 holds Conditions 6 and 7 hold trivially Case ri state t Fr lock Lock lock t state 1 t lock for some p t lock FN and t M By induction hypothesis we have Pa ep Sm and thus as previously established P ep S 1 Let O Ef Pw such that Q p state t Let 0 be a grounding substitution for state Z prems P _ such that t 0 Then 0 induces a substitution 7 and a bijective renaming p for fresh but not bou
20. k lt n and Unlock n t Em Ex Therefore E1 En Y atock Lock nj t Lock u t Unlock n t i j n Figure 19 Visualisation of Case 2 Conditions and 7 hold trivially Case ri state t a Event gt statej 1 t t for some p t t and l r a G By induction hypothesis we have Py p Sm and thus as previously established Pw ep S4 4 Let O Pw such that Q ep state t Let 0 be a grounding substitution for state Z prems P _ such that t 20 Then 0 induces a substitution 7 and a bijective renaming p for fresh but not bound names in Q such that P 7p Q see Definition 22 From the form of the rule R and since Q P rp we can deduce that Q l a r Q for a process Q P p 1 Tp Since ri g ginsts R we have that there is a substitution 7 such that l a r r i Salo r Ifacts l C S 1 pfacts l Cg S 1 and from the definition of P for embedded msr rules vars l r t Since P is well formed no fact in Fres appears in neither nor r so from Condition 3 in the induction hypothesis we have that lfacts l c SMS SMS and pfacts l c SMS SMS We therefore chose the following transition f Fa MS a MS S En Sy S Pu On Ly En 41 Sua Shi Pri i On 1 Ead with y41 y Sy 41 Sy SMS SMS Pacts l Uf r Parga Py V 0 Ha nr Q F Uf DO mua Cw adus Lw We define f as on page BI Therefore Condition
21. set the attribute to wrap in a concurrent process and produce a wrapping After resuming operation at line 4 he can set the key s attribute to dec even though the attribute is set to wrap Hence the attacker is allowed to decrypt the wrapping he has produced and can obtain the key Such subtleties can produce attacks that our modeling allows to detect If locking is handled correctly we show secrecy of keys produced on the device proving the property introduced in Example 5 If locks are removed the attack described before is found 18 7 2 Yubikey The Yubikey 28 is a small hardware device designed to authenticate a user against network based services Manufactured by Yubico a Swedish company the Yubikey itself is a low cost 25 thumb sized USB device In its typical configuration it generates one time passwords based on encryptions of a secret value a running counter and some random values using a unique AES 128 key contained in the device The Yubikey authentication server accepts a one time password only if it decrypts under the correct AES key to a valid secret value containing a counter larger than the last counter accepted The counter is thus used as a means to prevent replay attacks To date over a million Yubikeys have been shipped to more than 30 000 customers including governments universities and enterprises e g Google Microsoft Agfa and Symantec 29 Besides the counter values used in the one
22. we have that Condition 4 holds Condition 1 Condition 3 and Condition 5 hold trivially Case En tSn 1 SMS P _1 P U lJal r Q tact eas En 1 Sn 1 SMS Yacts V U mset r P uF Q Grech En 1 ns step requires that l a r Ep ginsts l y r and lfacts l C SMS pfacts l C mset SMS Let 0 be a substitution such that l Ja r V a 5 r Since by uo hypothesis SMS S V Fres we therefore have Ifacts I C Sw pfacts l C mset S By induction hypothesis P _1 Gp Sw Let p and t be such that aj r Q p statep t By Definition 20 there is a ri ginsts P such that state is part of its premise By definition of P _ we can choose ri state 1 I a Event r state 1 U vars 1 0 We can extend the previous execution by one step using ri therefore F F a Event mem Py 1 gt py ei s Pati 141 exec LPI 41 with Sw 1 S f n 1 state t V V facts V UF statep 1 tU vars 1 0 V U mset r It is left to show that Conditions I to 8 hold for n holds since SMS SMS Ifacts l Uf mset r Sy V Fres V lfacts l U mset r induction hypothesis S Vf Ifacts l Uf mset r state t V Uf state i1 U vars 1 0 V V Fres since state 1 statej i U vars 1 0 Fres S f n Fres The step from S to Sx n is labelled F a and does not contain actions in
23. 0 1P S statey yt We chose n 0 and thus o So SM Po oo Lo 0 0 0 P V 0 0 We define f 1 gt 0 such that f 1 To show that Condition 4 holds we mn to show that Po p statey s fresh Vf Note that Po P Lud We i the bijection such that P p statey s fresh By Definition 19 P P U We see from Figure 12 that for every P we have that staten s fresh rena Bol for R P p and 9 This induces r and p Since T P we have P ep statep and therefore Po ep S1 and hold trivially Inductive step Assume the invariant holds for n 1 gt 1 We have to show that the lemma holds for n transitions i e we assume that 0 n Sy pj ee LP Sn exec LP is normal and E En F a Then it is to show that there is o So SM Po co Lo Ei E1 S1 SMS Pi 01 L1 5 m F u Sn sMs Pais Ont Lnr fulfilling Conditions I to 8 Assume now for the following argument that there is not fact with the symbol Ack in 1 V Sn This is the case for all cases except for the case where rule instance applied from S _ to Sn has the form ri statese 5 Ack t1 t2 state 1 5 This case will require a similiar but different argument which we will present when we come to this case Since 0 ee p Sn exec P is normal and n gt 2 there exists m lt n such that Sm Sn for R MDOvT MDPUB MDFnESH M
24. 1 U vars Figure 7 Translation of processes definition of P p 13 Init gt state dns Istater1 dn state A Patel states Fr state 1 Fr state 111 state 111 stater i114 state 11111 h k 4 statej111 k h k h Event NewKey h k gt state 1111 k h k h Insert key h k gt state 11111 k h Insert att h dec state 111111 k h k h d Out h state 111111 k A ei 2 Figure 8 The set of multiset rewrite rules Ppew omitting the rules in MD this reason when the second rule of the translation of out is fired the state fact is substituted by an semi reflecting that the sending process can only execute the next intermediate semi state fact state step if the message was successfully received The fact Msg M N models that a message is present on the synchronous channel Only with the acknowledgement fact Ack M N resulting from the second rule of the translation of in is it possible to advance the execution of the sending process using the third rule in the translation of out which transforms the semi state and the acknowledgement of receipt into state 1 Only now the next step in the execution of the sending process can be executed The remaining rules essentially update the position in the state facts and add labels Some of these labels are used to restrict the set of exec
25. EQ py pp 8 P 3 3 Since no rule moved during the procedure has an action hide E4 En hide EX you a and EO TR EON E a If the last transition is in MDOuT MDPUB MDFRESH MDAPPL FRESH we remove it Repeat until fixpoint is reached and call the resulting trace EM EY So ne ep St Since no rule removed during the procedure has an action hide E En hide E By and Ef9 E ka If there is In t UNT then there is a transition where In t is produced and never consumned until n 1 The only rule producing In t is MDIN We can move this transition to just before n 1 and call the resulting trace 5 E EO SP spp pp 8 Since B es EM E a especially Qjney there is no action that is not in Fres between the abovementioned instance of MDIN therefore hide F1 En hide EO me a holds Since Qjney is the only part of a that mentions K and since the tranformation preserved Qinev we have that EO Dl Fa We will show that 6 and 7 hold for 5 EP Sy IP pp Sf 5 in one step If n9 gt 2 and there is no Ack fact in so jos a 8 a then we chose the largest m lt n such 5 that s ee II LIMES or if there is an Ack fact in a F i we will chose the po e i IP l ie DA This trivially fulfills 4 so gt R su and se gt R B s since otherwise there would be a larger m or m This also implies 2 as none of th
26. Fr t gt S Sn U IK t DFRAME We have that zc t for some x D oc that is t t1 tm By definition of t1 tm Out t S for some i n If Out t Sn we have that Sp gt S Sn Out t U K applying rule MDOvr If Out u Sn the fact that the only rule in P that allows to remove an Out fact is MDOUT suggests that it was applied before and thus K u S 29 Inductive case We proceed by case distinction on the last deduction rule which was applied e DAPPL In this case t f t1 t such that f EF and vaf o tj for every i 1 k Applying the induction hypothesis we obtain that there are k transition sequences 5 gt R S for 1 lt i k which extend the execution such that t S All of them only add K facts which are persistent facts If any two of these extensions remove the same Out t fact or the same Fr a fact it also adds the persistent fact K t respectively IK a and we simply remove the second occurrence of the transition Therefore applying the same rules as for the transitions S and removing duplicate rules we have that Sn S and IK t4 K ti S Applying rule MDAPPL we conclude e DEQ By induction hypothesis there exists S as required with K t p S and t p t which allows us to immediately conclude that K t g S L1 Lemma 9 Jf vi o t i 2g o g and t p t then vn o H t Proof Assume vn o F t
27. Fres since P is well formed Hence Condition 6 and hold Since P P4 4 1 al r Q U Q and Q state 1 U vars 1 0 by definition of P _ we have that holds Condition 1 and hold trivially Li Definition 21 normal msr execution A msr execution 0251 ee pp Sn exzec P for the multiset rewrite system P defined by a ground process P is normal if 1 The first transition is an instance of the INIT rule i e 1 state and there is at least this transition 2 4 neither contains any fact with the symbol states for any p nor any fact with symbol Ack 3 if for some i and t1 t9 M Ack t1 t2 Si 1 V S then there are p and q such that Si 3 R Si 2 n3 Si 1 R46i T where e Ri state 1 gt Msg ty t2 states Z e R state y Msg t1 t2 statey 1 y Uy Ack t1 t2 e R3 states 7 Ack ty t2 state 1 Z En 4 Sp 1 gt PI J MDIN Iurr n 5 if In t S 1 V S for some i and t M then CONES EM E 6 if n gt 2 and no Ack fact in S 1 V S then there exists m lt n such that Sm PR n 1 for R MDOvr MDPus MDFRESH MDAPPL U FRESH and 055 Pp exec TP is normal 7 if for some t4 t3 M Ack t1 t3 S 4 V Sp then there exists m lt n 3 such that Sm R Sn 3 for R MDOUT MDPUB MDFRESH MDAPPL U FRESH and 0p ee Fy pp Sim ezec P is normal Lemma 11 Normali
28. K t Ak gt k jVi kVvhks j Figure 10 Definition of a in between unless it is the first lock This again would cause tamarin to loop because an unlock is typically preceeded by yet another lock The axiom Wyocx avoids this caveat because it only applies to pairs of locks carrying the same annotations We will outline how Wiock is applied during the constraint solving procedure 1 If there are two locks for the same term and with possibly different annotations an unlock for the first of those locks is postulated more precisely an unlock with the same term the same annotation and no lock or unlock for the same term in between The axiom itself contains only one case so the only case distinction that takes place is over which rule produces the matching Unlock action However due to the annotation all but one are refuted immediately in the next step Note further that ojo postulates only a single node namely the node with the action Unlock 2 Due to the annotation the fact state contains the fresh name that instantiates the annota tion variable Let a fresh be this fresh name Every fact state for some position p that is a prefix of p and a suffix of the position of the corresponding lock contains this fresh name Furthermore every rule instantiation that is an ancestor of a node in the dependency graph corresponds to the execution of a command that is an ancestor in the process tree Therefore
29. K x b In x MDIN db K x pub MDPUB Fr z fresh d IK z fresh MDFRESH IK zi K z The K f ai 2 for f EEF MDAPPI Figure 6 The set of rules MD 6 A translation from processes into multiset rewrite rules In this section we define a translation from a process P into a set of multiset rewrite rules P and a translation on trace formulas such that P HY y if and only if P e Note that the result also holds for satisfiability as an immediate consequence For a rather expressive subset of trace formulas see for the exact definition of the fragment checking whether P H v can then be discharged to the tamarin prover that we use as a backend 6 1 Definition of the translation of processes To model the adversary s message deduction capabilities we introduce the set of rules MD defined in Figure 6 In order for our translation to be correct we need to make some assumptions on the set of processes we allow These assumptions are however as we will see rather mild and most of them without loss of generality First we define a set of reserved variables that will be used in our translation and whose use we therefore forbid in the processes Definition 11 Reserved variables and facts The set of reserved variables is defined as the set containing the elements na for any a FN and lock for any l N The set of reserved facts Fres is defined as the set containing facts f ti tn whereti
30. Q for a process Q P y4Tp We therefore chose the following transition Eny En Sy OM MS n 3 Pai On Ly En 41 Sn 41 Oud Pug On 1 Latji with 41 En w 1 Sw ti gt t Sem SM Pt Py VE delete t e y Ut 0C v 05 41 On and Lwi Ly We define f as on page BI Therefore Conditions I to S hold for i lt n 1 It is left to show that Conditions 1 to 8 hold for n By definition of P and P _ we have that Q amp state 1 t Therefore and since delete t1 Q state 1 P 1 P M delete t1 Q V UT Q V and Sn S 1 V states t V U statep 1 t V Condition 4 holds Condition 2 holds since E Delete t4 t2 is the last element of the trace Conditions 6 and 7 hold trivially Case ri state t AIsIn t t2 state p t t2 for some p t and t ta M By induction hypothesis we have 7 p Sm and thus as previously established P ep 4 1 Let O P such that Q p state t Let 0 be a grounding substitution for state a prems P _ such that t 40 Then 0 induces a substitution 7 and a bijective renaming p for fresh but not Dots names in Q such that P 7p O see Definition 22 From the form of the rule R and since Q P pTp we can deduce that Q lookup t as v in Q else Q for some variable V and two processes Q1 P p itp and Q2 P p 2Tp Since Ei En F ain there is an 4 lt n such that nsert t1 t2
31. S n 1 We will abuse notation by writing P p state 1 if this bijection goes from P to state 1 We now proceed by case distinction over the type of transition from j 1 54 1 e Pasis Gni Ln 1 to En Sn SMS Pn Cn Ln We will unless stated otherwise extend the previous execution by a number of steps say s from Sp to some Sn s and prove that Conditions I to 8 hold for n since by induction hypothesis they hold for all i lt n and a function f Nn gt Nw s that is defined as follows mes fa ifie Na n s ifi n 32 Case En 15 n 1 St Pai P U 0 0n 1 Lai Enis Sn 1 oe P On 1 Laus By in duction hypothesis P 1 p Sw Let p and t be such that 0 p state t By Definition 20 there is a ri ginsts P such that state t is part of its premise By definition of P we can choose ri state 4 gt We can extend the previous execution by one step using ri therefore F F Fy msr PI 1 5 iP e gt P Sa pp Sn 1 exec LPI with Sj 41 Sp n 1 state t It is left to show that Conditions I to S hold for n Condition 1 Condition 2 Condition 3 Condition 5 Condition 6 Condition 7 and hold trivially holds because P Pp_1 0 Spin Sp n 1 state t and 0 p state t see Remark 2 Case EAs S41 SMS Pa zx T U Q R On 1 bgt En 1 S44 SMS P U Q R S On 1 n 1 By induction hy
32. Sw SMS Pr On Ew 3 n 44 Sni Saga Pai On 1 La with Engi y S y a1 Sn a ME Iu S Psi PM if ti tothen Q else Qo V UT Q4 V Onw 41 On and Lwi Ly We define f as on page BI Therefore Conditions I to S hold for i lt n 1 It is left to show that Conditions I to 8 hold for n By definition of P and P _ we have that Q1 state 1 Therefore and since if t ta then Q else Qz o state Phy Pw if ti te then Q else Qo V Uf Q1 V and Sn Sn 1 V state t J Uf statep 1 t V Condition 4 holds Conditions 6 and 7 hold trivially Case ri state t NotEq t1 t3 state 1 for some p t and t t2 M In this case the proof is almost the same as in the previous case except that o5 44 is the relevant axiom Q is chosen instead of Q and and S S 4 state 1 y U statep o t Case ri state t F Event statep i t for some p t This is a special case of the case t where ri states 4 1 Ja statep 1 t r for L r and a F Case ri state t Insert t t2 statey 1 for some p t and t1 t M By induction hypothesis we have P p Sm and thus as previously established P p S 4 Let O P such that O e p state t Let 0 be a grounding substitution for siste s prems P _ such ihal t 0 Then 0 induces a substitution 7 and a bijective renaming p for f
33. a second key Pwrap in hi h2 lookup att h1 as aq in if a wrap then lookup key h1 as k in lookup key hg as kg in event Wrap kj k2 out senc ka k1 The bound names of a process are those that are bound by vn We suppose that all names of sort fresh appearing in the process are under the scope of such a binder Free names must be of sort pub A variable x can be bound in three ways i by the construct lookup M as x or ii x vars N in the construct in M N and z is not under the scope of a previous binder iii x vars L in the construct L HA R and x is not under the scope of a previous binder While the construct lookup M as x always acts as a binder the input and L 3A R constructs do not rebind an already bound variable but perform pattern matching For instance in the process P in c f x in c g z x is bound by the first input and pattern matched in the second It might seem odd that lookup acts as a binder while input does not We justify this decision as follows as Pec and Pywrap in the previous 5 vh cF t t gt ac FNUPN OER NAME E DEQ v cl a vi c H t x D o vho tievi tn feX BE Via F mw ens vn o fius im Figure 2 Deduction rules zi D o z D a vn o F senc ko ki vho F ky vh c F sdec senc ko ki ki sdec senc k2 ki k1 g ko RQ Figure 3 Proof tree witnessing that vn o F ko example show lookups appear often after input was r
34. difficult to model a protocol ad equately Encoding private channels nested replications and locking mechanisms directly as multiset rewrite rules is a tricky and error prone task As a result we observed that in practice the protocol models tend to be simplified For instance locking mechanisms are often omitted modeling protocol steps as a single rule and making them effectively atomic Such more abstract models may obscure issues in concurrent protocol steps and increase the risk of implicitly excluding attacks in the model that are well possible in a real implementation e g race conditions Using a more high level spec ification language such as our process calculus arguably eases protocol specification and overcomes some of these risks 2 Preliminaries Terms and equational theories As usual in symbolic protocol analysis we model messages by abstract terms Therefore we define an order sorted term algebra with the sort msg and two incompa rable subsorts pub and fresh For each of these subsorts we assume a countably infinite set of names FN for fresh names and PN for public names Fresh names will be used to model cryptographic keys and nonces while public names model publicly known values We furthermore assume a countably infinite set of variables for each sort s Y and let Y be the union of the set of variables for all sorts We write u s when the name or variable u is of sort s Let be a signature i e a set of function symb
35. execution is normal we have that there p q Z y y such that Sn 3 R n 2 mj 9n 1 m 4S95s where 50 e Rj state 2 gt Msg t1 t2 states z e R state Msg t1 t2 stateg 1 y U 9 Ack t t2 e R3 statese 3 Ack t1 t2 state 1 Z Since in this case there is a fact with symbol Ack removed from 1 to Sn we have to apply a different argument to apply the induction hypothesis Since 035p ppp Sn exec P is normal n gt 2 and ti t2 M Ack ti te S 4 V Sn there exists m lt n 3 such that Sm gt k 5 3 for R MDOutT MDPUB MDFRESH MDAPPL U FRESH and 025 1p ee Fe pS exec P is normal This allows us to apply the induction hypothesis on ET ees hy pp Sm erzec IP Hence there is a monotonically increasing function from Nm N and an execution such that Conditions I to S hold Let f be this function and note that n fy m In the following case distinction we extend the previous execution by one step from Ew Sw a Tuta to Eni Sa e SM s Pura eua uti and prove that Conditions 1 to 7 hold for n 1 By induction hypothesis they hold for all i lt n We define a function f N gt N44 as follows int ifd c Na fa n ifm lt i lt n 3 n 1 ifi n Since Sm gt k Sn for R MDOvT MDPUB MDFRESH MDAPPL FRESH only S MP Sm contains only Fr facts and K facts and Sm V S
36. f Fres and hence f hide tr where n hide tr The proof of the other statement is similar 26 e p Y Y qi qa or y Ar s p We directly conclude by induction hypotheses on the structure of q From the above statements we easily have that Tr F7 y iff hide Tr F v The case of x V now easily follows Tr EY p iff Tr EP p iff hide Tr iff hide Tr FY I G Li In order to prove Lemma I we need a few additional lemmas We say that a set of traces Tr is prefix closed if for all tr Tr and for all tr which is a prefix of tr we have that tr Tr Lemma 4 filter is prefix closed Let Tr be a set of traces If Tr is prefix closed then filter Tr is prefiz closed as well Proof It is sufficient to show that for any trace tr tr a we have that if V0 tr 0 F a then V0 tr 0 E a This can be shown by inspecting each of the conjuncts of a O We next show that the translation with dummy facts defined in Definition 18 produces the same traces as P excluding traces not consistent with the axioms For this we define the function d which removes any dummy fact from an execution i e F 1 eee E y F5 Fro ow gt Si tae By where S S V User Dum t Lemma 5 Given a ground process P we have that filter exec P f tter d exec LP P U MD Proof The only rules in P P that differ from P are translations of insert and loo
37. fact that the rules in P do not satisfy the third condition of multiset rewrite rules trace execs P UMD Fox ai V v trace execs P UMD Epu oi V Lemma 3 7 unaltered trace execs P U MD gps r4 Oin V Definition of Epy trace dgraphs py P U MD RDH EDH 70i V Lemma 3 10 unaltered trace dg dg dgraphs cc LP UMD s dg rox normal Epy oi V Q Lemma 3 11 unaltered trace ndgraphs P Fou oi V A Lemma A 12 trace ndgraphs P Face main V Lemma 3 7 and A 20 both unaltered It is only in Lemma A 12 where the third condition is used The proof to this lemma applies Lemma A 14 which says that all factors or their inverses are known to the adversary We will quote Lemma A 14 here Lemma 3 Lemma A 14 in 24 For all ndg ndgraphs P conclusions i u in ndg with conclusion fact f and terms t afactors f there is a conclusion j v in ndg with j i and conclusion fact K4 m such that m Acc t t1 Lrep If there is ndg ndgraphs P such that trace ndg F Acc Qin then trace ndgraphs P Face os V gt eVndg ndgraphs P s t trace ndg FACC Qin trace ndg Face Q Since for the empty trace FACC Qin we only have to show that Lemma A 14 holds for ndg ndgraphs P such that trace ndg FACC Qin For every ndg ndgraphs P such that trace ndg F Acc Qin there is a tr
38. for N E S S 8 P U if M N then P else Q S SMS PU P o L if M g N E S S 8 P U if M N then P else Q E 8 8M5 PU Q 0o if M ZEN E S SMS P U event F P o mg E S SMS P U P 0 L E S SMS P 0 L ifvE x M E S SMS P U in M Ny P o p ZOET Operations on global state E S SMS P Uf insert M N P o L E S M N SMS P U Plo E S SMS P Uf delete M P o L S M 1 SMS P U Pho E S SMS P Uf lookup M as x in P else Q o E S SMS P Uf P V x 0 if S N z V is defined and N 2g M E S SMS P Uf lookup M as z in P else Q 0 L E S S 8 P U QY o if S N is undefined for all N 2g M E S SMS P U lock M P o L E S SMS PU Pe CU LM if MEgL E S SMS P Uf unlock M P o L E S S 5 PU P 0 M M 2g M S SMS P U ll Jako r P o gt E S SMS V Ifacts i Uf r P U Pr o L if Jr l a r 7 grounding for a 2 r a gt r 2g l Ma r r lfacts l C SMS pfacts l C SMS Figure 4 Operational semantics e L C Vy is the set of currently acquired locks The transition relation is defined by the rules described in Figure 4 Transitions are labelled by sets of ground facts For readability we omit empty sets and brackets around singletons i e we write for and 5 for un We write
39. for the reflexive transitive closure of the transitions that are labelled by the empty sets and write d for 2 We can now define the set of traces i e possible executions that a process admits Definition 2 Traces of P Given a ground process P we define the set of traces of P as tracesP P TP Fa 0 0 0 P 0 0 A E1 S1 SMS Py 01 1 Pa BA En Sn SMS Pas on Ln Example In Figure 5 we display the transitions that illustrate how the first key is created on the security device in our running example and witness that NewKey h k traces P 0 0 0 Prews Pset Paec Purap 0 0 0 0 0 Prew y Uf P 0 0 Se ieee ee ee P 0 0 0 vh vk event NewKey h k Uf P 0 0 en k V 0 0 event NewKey h k V U P 0 0 h k 0 0 insert key h k Uf P 0 0 Wk 8 0 out h 0 U P 0 0 5 5 0 P 7 5 0 where S key h k and S att h dec y NewKey h k zn SED m Figure 5 Example of transitions modelling the creation of a key on a PKCS 11 like device 4 Labelled multiset rewriting We now recall the syntax and semantics of labelled multiset rewriting rules which constitute the input language of the tamarin tool 25 Definition 3 Multiset rewrite rule A labelled multiset rewrite rule ri is a triple l a r l a r F wri
40. from security APIs many other protocols need to maintain databases key servers need to store the status of keys in optimistic contract signing protocols a trusted party maintains the status of a contract RFID protocols maintain the status of tags and more generally websites may need to store the current status of transactions Our contributions We propose a tool for analyzing protocols that may involve non monotonic global state relying on Schmidt et al s tamarin tool as a backend We designed a new process calculus that extends the applied pi calculus by defining in addition to the usual constructs for specifying concurrent processes constructs for explicitly manipulating global state This calculus serves as the tool s input language The heart of our tool is a translation from this extended applied pi calculus to a set of multiset rewrite rules that can then be analyzed by tamarin which we use as a backend We prove the correctness of this translation and show that it preserves all properties expressible in a dedicated first order logic for expressing security properties As a result relying on the tamarin prover we can analyze protocols without bounding the number of sessions nor making any abstractions Moreover it allows to model a wide range of cryptographic primitives by the means of equational theories As the underlying verification problem is undecidable tamarin may not terminate However it offers an interactive mode with a GUI wh
41. fst z y x and snd z y y are in E We will sometimes use 21 2 n as a shortcut for x1 2 sin diia ees We also use the usual notion of positions for terms A position p is a sequence of positive integers and t denotes the subterm of t at position p Facts We also assume an unsorted signature X4 disjoint from X The set of facts is defined as F F t tk ti Ts F Vjfact Of arity kj Facts will be used both to annotate protocols by the means of events and for defining multiset rewrite rules We partition the signature X fact into linear and persistent fact symbols We suppose that X fact always contains a unary persistent symbol K and a linear unary symbol Fr Given a sequence or set of facts S we denote by lfacts S the multiset of all linear facts in S and pfacts S the set of all persistent facts in S By notational convention facts whose identifier starts with will be persistent G denotes the set of ground facts i e the set of facts that does not contain variables For a fact f we denote by ginsts f the set of ground instances of f This notation is also lifted to sequences and sets of facts as expected Substitutions A substitution c is a partial function from variables to terms We suppose that substitutions are well typed i e they only map variables of sort s to terms of sort s or of a subsort of s We denote by a x the substitution whose domain is D a z1
42. in P that produces a state named state for a non empty p is such that it requires a fact with name statey for p p 1 or p p 2 in case of the translation of out it might require state which in turn requires statey This means that since state t Sy there is an i such that state S and state t S 1 for a prefix to t This rule is an instance of P _ and thus labelled F Lock I t We proceed by case distinction Lock l t Lock l t Unlock I t y a n 1 Figure 16 Visualisation of Case 1 Case 1 j lt i see Figure 16 By induction hypothesis holds for the trace up to n But F1 F tock Since we assumed that for all k such that j lt k lt n Unlock l t g Fk Lock I t Lock I t Unlock I t a j n 1 Figure 17 Visualisation of Case 2 Case 2 i lt j see Figure 17 As shown in the lock case any k such that Unlock l f g Fy is k n 1 This contradicts Condition 7 for the trace up to j since F1 Fj Q1ock because there is not k such that i lt k lt j such that Unlock l t g Fy This concludes the proof that Condition 6 holds for n 1 Condition 7 holds since none of the axioms in particular not o5 become unsatisfied if they were satisfied for the trace up to f n 1 and an Unlock is added Since P P 4 unlock t Q Man AEN and Q state 1 t by definition of the transla tion
43. key then if the intruder learns the first key he can deduce the second For k ka and o 5 2 5 Ji Je vit o H ko as witnessed by the proof tree given in Figure Operational semantics We can now define the operational semantics of our calculus The semantics is defined by a labelled transition relation between process configurations A process configuration is a 6 tuple S S P c L where e C FN is the set of fresh names generated by the processes S Myg gt My is a partial function modeling the functional store e SMS C G is a multiset of ground facts and models the multiset of stored facts P is a multiset of ground processes representing the processes executed in parallel e c is a ground substitution modeling the messages output to the environment Standard operations E S SMS P Uf 0 0 E S SMS Pur EPIQY a E S SMS Pur P 0 E S SMS P U va P 0 E S SMS P o L E S SMS P U P Q 0 E S SMS P Uf PP o L EU a S SMS PUT P a a 0 if a is fresh EE S SMS P T E S SMS p UF out M N P a E S SMS P Uf P y gU N L if x is fresh and vE a M E S SMS P Uf Pr o L if Jr T is grounding for N v o M v o Nr E S SMS P Uf out M N P in M N Q o 8 8 PU LB QT 0 L if M p M and dr N g N r and 7 grounding
44. lt j lt f n Unlock l1 t CE F We apply Proposition 4 for the total order gt on the integer interval i 1 f n 1 Vi lt f n l Lock l t Ep Fi gt Jj i lt j lt f n Unlock h t g Fj Vk i lt k lt jo Unlock lj t ZE Fk Combining this with 2 we obtain that di lt f n h Lock li t g F Jj i lt j lt f n Unlock l5 t g Fj Adi k i k j Lock le t Eg Fk V Unlock le t Eg FE A lo AR l Fix i lt f n j such that i lt j lt f n and l such that Lock l1 t g F and Unlock l1 t g Fj Then there are la and k such that i lt k lt j and either Lock l2 t g Fk or Unlock lo t g Fk but lo Ap li We proceed by case distinction Case 1 there is no unlock in between i and j i e for all m i lt m lt j Unlock l t Fm Then there is a k and lg such that Lock lo t g FR In this case ojo is already invalid at the trace produced by the k prefix of the execution contradicting the induction hypothesis Case 2 there are and m i lt m lt j such that Unlock t Fm see Figure 17 We first observe that for any l u i1 i9 if Unlock l u g Fj and Unlock l u Eg Fiz then i i2 We proceed by contradiction By definition of P and well formedness of P the steps from i 1 to i4 39 Lock l t Unlock I t Unlock t i m j Figure 13 Visualisation of Case 2 and from i
45. ns a and have state f a statey 1 a 6 Since Q P rp for r and p induced by 0 Q Plpt p for 7 and p induced by 6 i e 7 7 and p plat a Therefore Q ep statey f a Condition 4Jholds since furthermore v a Q state t P 41 Pu VE v al Q FURL QH a Vf and S S44 Fr a state t V Uf state 1 t a fresh holds since 44 Ew Ua and E ProtoNonce a holds since ProtoNonce a Fres Conditions and 5 hold trivially Case ri state t In t InEvent t gt state 1 Out t2 for some p t and t t M 7 K t E n Since the msr execution is normal we have that CS T Since So P mE p Sn is normal so is Soy igs Sp Sat and therefore Soy TE SE Sad Hence there is an m n 2 such So p Fe pp Sim is a normal trace and Sm gt h S4 for R MDOuT MDPuB MDFnESH MDAPPL FRESH By induction hypothesis we have Pw p Sm and thus since MDOuT MDPUB MDFRESH MDAppt jand FRESH do not add or remove state facts P ep S Let O Pw such that Q p state t Let 6 be a grounding substitution for state Z prems P _ such that t 26 Then 0 induces a substitution 7 and a bijective renaming p for fresh but not bound names in Q such that P jrp Q see Definition 22 From the form of the rule R and since Q P rp we can deduce that Q out t1 t2 Q for a process Q P y47p From the induction h
46. s 1 Sy Vf statep t statey t U state 1 statey 4 t U vars N 0 Ack t NO Vf Sns Sw Vf state t state t Uf statep 1 f statey f U vars N 0 We have that Pa P 4 V out c m Q in c t R U Q R0 V Exactly as in the two previous cases we have that Q state i t as well as RO amp as Hence we have that Condition 4 Condition 4 holds Condition 1 Condition 2 Condition 3 Condition 5 Condition 6 Condition 8 and C hold trivially 35 Case OMEN Sn 1 SS Py P U if t t then Q else Q h On 1 n 1 En 1 95 1 SMS P U Q on 1 Ln 1 This step requires that t g t By induction hypothesis P _1 Gp Sw Let p and t be such that if t t then O else Q ep state t By there is a ri ginsts P _ such that state t is part of its premise By definition of P _ we can choose state 1 Eal t state 1 We can extend the previous execution by one step using ri HAE E am 0 Dy 1 DPI T p poe uis exec UP with S 1 Sw Vf state t V U state 1 It is left to show that Conditions I to B hold for n The last step is labelled Ffin Eq t i V As t p t Condition 7 holds in particular Oleg is not violated Since Eq is reserved holds as well As before since P P 1 if t t then O else Q UF O and O state 1 t a by definition of the translation we have that Pn p
47. 0111111 K h state 01111111 k h Out h state 01111111 K h Figure 9 Example trace for the translation of Phew e Qinit ensures that the init rule is only fired once e Qeg and Anoteg ensure that we only consider traces where all dis equalities hold Qin and Anotin ensure that a successful lookup was preceded by an insert that was neither revoked nor overwritten while an unsuccessful lookup was either never inserted or deleted and never re inserted e Qlock Checks that between each two matching locks there must be an unlock Furthermore between the first of these locks and the corresponding unlock there is neither a lock nor an unlock Qiney ensures that whenever an instance of MDIN is required to generate an In fact it is generated as late as possible i e there is no visible event between the action K t produced by MDIN and a rule that requires In t We also note that Tr FY p iff Tr Pola The axioms in the translation of the formula are designed to work hand in hand with the translation of the process into rules They express the correctness of traces with respect to our calculus semantics but are also meant to guide tamarin s constraint solving algorithm Qin and o5 illustrate what kind of axioms work well when a node with the action IsIn is created by definition of the translation this corresponds to a lookup command The existential translates into a graph constraint that postulat
48. 1 We proceed by case analysis on the rule used to extend the execution MDOvt Suppose that Out u 9 K u ginsts MDOuT is the rule used to extend the execution Hence Out u 1 and by definition of there exists x such that zo u We can apply deduction rule DFRAME and conclude that vi o H u If K t Sn andt Z u we conclude by induction hypothesis as i o o MDPuB Suppose that gt K a pub ginsts MDPUB is the rule used to extend the execution As names of sort pub are never added to we can apply deduction rule DNAME and conclude that vn o F a If K t S and t Z a we conclude by induction hypothesis as fj A o o MDFRESH Suppose that Fr a fresh K a fresh ginsts MDFRESH is the rule used to extend the execution By definition of an execution we have that Fr a fresh A S41 S for any j A n 1 Hence n We can apply deduction rule DNAME and conclude that vn c F a If K t S and t Z a we conclude by induction hypothesis as MDAPPL Suppose that K t1 K tk 4 J2 K u ginsts MDAPPL is the rule used to extend the execution We have that K t K t S 1 and u p f t1 tx By induction hypothesis vf o t for 1 X i k Asn fi c o we have that vio F t for 1 i k We can apply deduction rule DAPPL and conclude that vn o F f ti tx Hence vn o H u by rule DEQ If K t Sn and t Z f t1 t we conclude
49. 2014 arXiv 1403 1142v2 cs CR 12 May 2014 X e e Automated analysis of security protocols with global state Full version Steve Kremer INRIA Nancy Grand Est amp Loria France Robert Kiinnemann Department of Computer Science TU Darmstadt Germany Abstract Security APIs key servers and protocols that need to keep the status of transactions require to maintain a global non monotonic state e g in the form of a database or register However most existing automated verification tools do not support the analysis of such stateful security protocols sometimes because of fundamental reasons such as the encoding of the protocol as Horn clauses which are inherently monotonic A notable exception is the recent tamarin prover which allows specifying protocols as multiset rewrite msr rules a formalism expressive enough to encode state As multiset rewriting is a low level specification language with no direct support for concurrent message passing encoding protocols correctly is a difficult and error prone process We propose a process calculus which is a variant of the applied pi calculus with constructs for manipulation of a global state by processes running in parallel We show that this language can be translated to msr rules whilst preserving all security properties expressible in a dedicated first order logic for security properties The translation has been implemented in a prototype tool which uses the ta
50. 4 P op Sra j p t 3j f i u Lock u t Em Fj AVJ lt k f i Unlock u t g Fx 3 4 5 x0 x D c Out t Upc say Sk 6 7 Fy Fw F a where a is defined as in Definition 14 Proof We proceed by induction over the number of transitions n Base Case For n 0 we let f n 1 and S be the multiset obtained by using the Rule INIT 0 95 state Condition 1 Condition 2 Condition 3 Condition 5 Condition 6 Condition 7 and Condition 8 hold trivially To show that holds we have to show that Pp p istatej Vf Note that Po P 1f We choose the bijection such that P xp statej For r and p 0 we have that P yr Pr Pp By Definition 19 Pl g P 1 ag We see from Figure 12 that for every P we have that statep prems P _ Hence we conclude that there is a ground instance ri g ginsts P _ with statey prems rt Inductive step Assume the invariant holds for n 1 gt 0 We have to show that the lemma holds for n transitions o So S S Po co Lo B 151 515 P104 1 tee e En Sn SYS Pn On Ln By induction hypothesis we have that there exists a monotonically increasing function from N 1 gt N and an execution Fi Fz E P 1 P OP Sw exec TP such that Conditions to B hold Let fp be this function and note that n fp n 1 Fix a bijection such that P _1 gt P
51. 9 state 1 state z _NotEq M N statep 2 Z U P p 1 Z _ U Q p 2 z _ state z Event F state 1 rm P Pt 2 J 2 V P gt p 1 21 state z Insert s t state 1 Z 7 JU P p 1 l state z Delete s state 1 2 a U P pcs state state UIP p 1 v l p UIQ p 2 lp Fr lock state Lock lock s statep 1 Z lock Prs U P p 1 z _ HisIn M v state 1 M v IsNotSet M statep o 2 2 2 unlock s P p p statep Unlock locki s statey 1 2 pe U P p 1 pt I Ha r P p la state 2 7 Event a r statey 1 4 U vars Pas U P p 1 U vars l Figure 12 Definition of P p Z _ where E if a b and 0 otherwise a 31 Lemma 10 Le P be a well formed ground process If Eo So SQ 5 Po co Lo E1 S1 St P1 01 1 Ex tee 2m En Sn SYS Prs On Ln where Eo So SYS Po co Lo 0 0 0 P Y 0 0 then there are F1 S1 Far Sn such that Fy 0 Psp S Pap pp Sw exec P and there exists a monotonic strictly increasing function f Ny Nw such that f n n and for all i E Nn 1 Ei a ProtoNonce a Uizjz gy Fi u ify lt f i Insert t u Fj 2 Yt M S t AYJ uj lt j f i Insert t u g Fy A Delete t gp Fj L otherwise a Sta Fres
52. DAPPL FRESH and 0 ee Pm ppSim ezec TP is normal too This allows us to apply the induction hypothesis on 05 ee Phy Sm ezec P Hence there is a monotonically increasing function from Nm Nw and an execution such that Conditions I to B hold Let fp be this function and note that n fp m In the following case distinction we will unless stated otherwise extend the previous execution by one step from Ey Sw SMS Prr On Ln to Enti Sari SMS Parti Onti Dura and prove that Conditions 1 to 7 hold for n 1 By induction hypothesis they hold for all i lt n We define a function f Nn gt N 4 as follows foli dieN fO n ifm lt i lt n n 1 ifi n 46 Since Sm gt h S for R MDOuT MDPUB MDFREsH MDAPPL FRESH only S V Sm contains only Fr facts and K facts and Sm V Sn contains only Fr facts and Out facts Therefore Condition 34 and Bl hold for all i lt n 1 Since Ej 4 En 1 0 Condition 1 BIG and 7 hold for all i n 1 Fix a bijection such that Py ep Sm We will abuse notation by writing P p state t D if this bijection maps P to state 1 We now proceed by case distinction over the last type of transition from 4 41 to Sn Let liinear E S5 1 N Sn and r 2g Sn N S4 4 linear can only contain linear facts while r can contain linear as well as persistent facts The rule instance ri used to go from Sn 1 to Sn has the following form
53. F FQi iff 0 i idz tr and F0 g tro tr Ei j df Ol 0 j 3 Fi j iff Oli 6 7 E ty Sto iff 110 F t20 E y iff not tr 0 F Eqi qa iff tr 0 E p and tr E p2 Fdr s p iff there isu D s such that tr 8 x u Fy RS cK 3 D SD oo oo fo SD WS SYS HS SS ww ir ir When y is a ground formula we sometimes simply write r F p as the satisfaction of is independent of the valuation Definition 10 Validity satisfiability Let Tr C P G be a set of traces A trace formula p is said to be valid for Tr written Tr EY o if for any trace tr Tr and any valuation 0 we have that tr 0 Fy A trace formula y is said to be satisfiable for Tr written Tr F 9 if there exist a trace tr Tr and a valuation 0 such that tr 0 E q Note that Tr E y iff Tr E y Given a multiset rewriting system R we say that g is valid written RE qo if traces R EY p We say that q is satisfied in R written R F y if traces R F o Similarly given a ground process P we say that q is valid written P EY y if traces P EY y and that y is satisfied in P written P F y if tracesP P F v Example The following trace formula expresses secrecy of keys generated on the security API which we introduced in Section 3 3h k msg i j temp NewKey h k i A K k Q j 10 Out x d IK a MDOvuT IK r
54. M as v in P else Q and P insert s t P where it is defined as follows lookup M as v in P else Q p z P state 2 Dum v 4IsIn M v gt statep 1 M v state 2 IsNotSet M state 2 Z U IP p 4 1 2 v U I2 p 2a insert s t P p state Insert s t statep 1 IDum t U P p 1 4 The only difference between P and P is therefore that P P produces a permanent fact Dum for every value v that appears in an action insert k v which is a premise to every rule instance with an action IsIn k v We see that P contains now only valid multiset rewrite rules In the following we would like to show that the tamarin prover s solution algorithm is correct for P To this end we make use of the proof of correctness of tamarin as presented in Benedikt Schmidt s Ph D thesis 24 We will refer to Lemmas Theorems and Corollaries in this work by their numbers We will use the notation of this work to make it easier to the reader to compare our statements against the statements there In particular trace execs R is traces R in our notation We have to show that Lemma 2 For all well formed process P and guarded trace properties trace ezecs P UMD Fox oi V 24 if and only f trace ndgraphs P Face oi V 9 Proof The proof proceeds similar to the proof to Theorem 3 27 We refer to results in 24 whenever their proofs apply despite the
55. Meier C Cremers and D Basin The tamarin prover for the symbolic analysis of security protocols In Proc 25th International Conference on Computer Aided Verification CAV 13 volume 8044 of LNCS pages 696 701 Springer 2013 27 Trusted Computing Group TPM Specification version 1 2 Parts 1 3 revision 103 http www trustedcomputinggroup org resources tpm main specification 2007 28 Yubico AB Kungsgatan 37 111 56 Stockholm Sweden The YubiKey Manual Usage configuration and introduction of basic concepts Version 2 2 available at http www yubico com documentation June 2010 29 Yubico AB Yubico customer list 2013 Accessed Wed 17 Jul 2013 11 40 50 CEST A Definition of the process annotation Definition 17 Process annotation Given a ground process P we define the annotated ground process P as follows 0 0 P Q P O IP P if ti te then P if t ta then P else O else Q lookup M asx _ lookup M as x in P else O in P else O a P a P where a lock t unlock t t T lock t P lock t au P t 1 where l N is a fresh label unlock t P unlock t P unlock t P L 23 where au P t l annotates the first unlock that has parameter t with the label l i e au P O t l L au P t l L au if t ta then _ ifti ta then au P t l P else Q t l else au Q t 1 au lookup M asx lookup M as x in in P else Q t l au P t 1 else au Q t 1 aula
56. P1 D a au P t l where a unlock t au unlock t P t 1 unlock t P au 0 t l 0 B Correctness of tamarin s solution procedure for translated rules The multiset rewrite system produced by our translation for a well formed process P could actually contain rewrite rules that are not valid with respect to Definition 4 because they violate the third condition which is for each l a gt r R g ginsts l a r we have that Qy 5 names r O FN C fra ynames l N FN This does not hold for rules in Pl_ where p is the position of the lookup operator The right hand side of this rule can be instantiated such that assuming the variable bound by the lookup is named v this variable v is substituted by a names that does not appear on the left hand side In the following we will show that the results from still hold In practice this means that the tamarin prover can be used for verification despite the fact that it outputs well formedness errors for each rule that is a translation of a lock We will introduce some notation first We re define P to contain the INIT rule and P J but not MD which is different to Definition 13 We furthermore define a translation with dummy facts denoted P that contains INrr and P 11 which is defined as follows Definition 18 We define P InrrU P where P is defined just as P J with the exception of two cases P lookup
57. Since an application of DEQ can be appended to the leafs of its proof tree we have v1 0 t Since DEQ can be applied to its root we have vn o H t Since consist only of names and thus vn o H t O To state our next lemma we need two additional definitions Definition 19 Let P be a well formed ground process and p a position in P We define the set of multiset rewrite rules generated for position p of P denoted P 4 as follows Pl_ 12 I U is defined in Figure 1 where ep The next definition will be useful to state that for a process P every fact of the form state f in a multiset rewrite execution of P corresponds to an active process in the execution of P which is an instance of the subprocess P Definition 20 Let P be a ground process P be a multiset of processes and S a multiset of multiset rewrite rules We write P xp S if there exists a bijection between P and the multiset state t Jp t state f S such that whenever O P is mapped to state t S we have that 1 P yr Qp for some substitution T and some bijective renaming p of fresh but not bound names in Q and 2 dri p ginsts P _ state t prems ri When P p S O f P and state t S we also write O p state t if this bijection maps Q to state t Remark 2 Note that p has the following properties by the fact that it defines a bijection between multisets
58. Sn 1 SD E P Uf QO on 1 n 1 This step requires that 0 is grounding for N and that v 4 04 1 t N0 Using Lemma 8 we have that there is an execution 0 e SE ezecy P such that K t g S and Sg 1 gt R S for R MDOUT MDPUB MDFRESH MDAPPL The same holds for NO We can combine those executions by removing duplicate instantiations of FRESH MDFRESH and MDOut This is possible since K is persistent Let E E SEK EL MC i 258 rin 1 gt h S erecy P this combined execution and K t K N g S Let p e t be such that in t N Q op state t t By Definition 20 there i isaric ginsts P such that state 1 is part of its premise From the definition of P _ and the fact that 0 is grounding 34 for NO we have state f in their premise namely ri state 4 In t N InEvent t N0 statep 1 t U vars N 0 From Sw we can first apply the above transition Sw S and then since K t K N6 state z S MDAPPL for the pair constructer MDIN and ri F Ey 0 PI 51 EP Sw 7 RC P S Sn s 3 MDAPPL K t N0 InEvent t N0 pda ea P Sn s exec P where e since Sw gt r S S is such that set S Fr t Out t t M Y set S set S K t t M Y set S and IK t IK N0 e S e Sw s 2 S Uff UK N8 jur e Sy4s 1 S Uf 1 In t N e Sws S Vf state t U state i tU vars N 0
59. Sn and therefore Condition 4 holds Condition 1 and hold trivially Case Enci S uis is Poh P U if t t then Q else Q On 1 Lai 85159515 SMS P U Q o a4 4 1 This step requires that t m t This proof step is similar to the previous case except ri is chosen to be state t NotEq t t statep 2 t The condition in Qnoteq holds since t Z g t F Case Eni 41 SN Pn 1 P U event F Q h On 1 n 1 n Sn 1 S P U Q os 1 4 1 By induction hypothesis P 1 lt p Sw Let p and t be such that event F Q op state t By Definition 20 there is a ri ginsts P _ such that state t is part of its premise By definition of P _ we can choose ri state F Event state 1 We can extend the previous execution by one step using ri therefore vent msr 0 Dy 1 Hy ML S ee 41 exec LPI with Sj 1 Sm V statep t U statep t It is left to show that Conditions I to B hold for n holds because P P 4 V event F O Q jut aca is and une e rH a t 2 of P Taking k f n MM and hold trivially Case Enci Suet Pep insert t t Q h On 1 Es Es ds Sn n ilt a t SMS P U Q on 1 Ln 1 By induction hypothesis P p Sw Let p and be such that insert t t Q lt p state t By there is a ri ginsts P _ such that state t is part of its premise By definition of P _ we can choose ri state
60. Y mor On and 44 y We define f as on page BI Therefore Conditions I to 8 hold for i lt n 1 It is left to show that Conditions I to 8 hold for n By definition of P and P _ we have that Q state 1 t and d state o t Therefore and since O 4 state t Pj 41 Pw Q1 Q2 V Uf Qi Qo and Sn S 4 Vt statept UF statey 1 statep o t V holds Conditions and 7 hold trivially Case ri state t T state 1 t for some p t By induction hypothesis we have P ep Sm and thus as previously established Py ep S Let O Pw such that O ep state t Let 0 be a grounding substitution for state z prems P such that t 20 Then 0 induces a substitution 7 and a bijective renaming p for fresh but not bound names in Q such that P rp O see Definition 22 From the form of the rule R and since Q P rp we can deduce that Q Q for a process Pup We therefore chose the following transition F n MS Ew Sy Bn Pu On Eu y Saa S ip Pri 1 On 1 Laga with Ewy En Sui Sw SMSa SMS Purga Pu U 0 ou ow and Lwy Ln We define f as on pase Therefore Conditions I to 8 hold for 1 lt n 1 It is left to show that Conditions 1 to 8 hold for n By definition of P and P we have that Q ep state 1 Therefore and since P 1 P Uf Q V while S S 4 Uf statep 1 t Condition 4 holds C
61. ace equivalent ndg ndgraphs P P since the only difference between P and P lies in the dummy conclusion and premises and Qin requires that any v in an action IsIn u v appeared previously in an action Insert u v equivalence modulo ACC Therefore ndg has the same K conclusions ndg has and every conclusion in ndg is a conclusion in ndg We have that Lemma A 14 holds for P since all rules generated in this translation are valid mul tiset rewrite rules Therefore Lemma A 14 holds for all ndg ndgraphs P such that trace ndg F Acc Qin too concluding the proof by showing the marked step Li C Proofs of Section 6 Proposition 1 Let Tr be a set of traces and a trace formula We have that Tr E v iff filter Tr o where x is either V or 3 25 Proof We first show the two directions for the case x V We start by showing that Tr EY y implies filter Tr E 9 Tr E v gt filter Tr E vly since filter Tr C Tr S filter Tr FX a gt y by definition of y y filter Tr EY o since filter Tr FY a We next show that filter Tr FY p implies Tr FY y y filter Tr EY y gt filter Tr E a q since filter Tr EY a S Tr EY a V a q since filter Tr C Tr and Tr filter Tr VY o S TE as p e Tr EY v y by definition of v The case of x d now easily follows TrE3 e if Try ly iff filter Tr EN iff filter Tr F3 o
62. act that it defines a bijection between mvultisets e If Py p 4 and Py p So then Pi Uf Po ep Si UF 5 e If P1 p S and Q p state t for O P and state t S i e Q and state t are related by the bijection defined by Py ep S1 then P V O ep S1 V state t Lemma 12 Le P be a well formed ground process If E E En msr So Py 1 5i e IP Sn exec LPI is normal see and E1 En F a see Definition 12 then there are Eo So S S Po T0 Lo 3 En Sw SMS Prw On y and Fj Fw such that o So SM Po co Lo EN E1 S1 SMS P01 1 EL D ni Eni Sm SMS Bu seg Ln n where o So SAS Po co o 0 0 0 P 1 0 0 and there exists a monotonically increasing surjec tive function f Nn N 0 Ny such that f n n and for all i Ny 1 Esa a FN ProtoNonce a g Uy lt j lt Ej u ifdj amp ilInsert t u g Ej 2 Vt EM Stal AYJ uj lt j i Insert t u gp Ey A Delete t gp Ej L otherwise J S HE Sj Freg 45 4 Pia p Si 5 oa Dope r Out t Ug Ss 6 Za e t dj S du Lock u t g E Vj lt k i Unlock u t g Ex j Furthermore 7 hide E4 E4 e Fi F7 Proof We proceed by induction over the number of transitions n Base Case A normal msr execution contains at least an application of the init rule thereby the shortest normal msr execution is
63. at t 0 Then 0 induces a substitution 7 and a bijective renaming p for fresh but not bound names in Q such that P rp O sce Definition 22 From the form of the rule R and since Q P yrp we can deduce that Q 0 We therefore chose the following transition FL MS K t MS n On Si Py On Lt v Sn 41 Sis Pul On 1 Lugad with Ey En ouam Sw SHS mST Parga PS 0 owg ey and Lygi Lw We define f as on page 5I Therefore Conditions I to 8 hold for i lt n 1 It is left to show that Conditions 1 to 8 hold for n Condition 4 holds since Q state t Pw 1 Pw V 0 and S S 4 V state t Conditions and 7 hold trivially Case ri state t 4 statey 1 state 2 t for some p and t By induction hypothesis we have P sep Sm and thus as previously established P p S4 4 Let O Pp such that Q p state t Let 0 be a grounding substitution for state 7 i prems P _ such that t 0 Then 0 induces a substitution 7 and a bijective renaming p for fresh but not hound names in Q such that P rp O see Definition 22 From the form of the rule R and since Q P ptp we can deduce that O Q1 Q for some processes Q P p 17p and Q2 P p 2Tp We therefore chose the following transition FI MS MS En Sw S Pu On Ly Engi Ouais REP Pug On 4 1 Larga with Ewy En Sny Sw SME S Pargi Pu F Q1 Q2 UT Q1 Q2
64. by induction hypothesis as 5j f o o If 1 Sn we have that Fr a S 1 By Lemma 6 we obtain that if K t S 1 then there exist t and o such that t p t o p c and a st t and a st o For each K u Sn there is K u S and by induction hypothesis vii o H u By Lemma 7 and the fact that o p o we have that vfi a o u As f a i and o o we conclude ProtoNonce a 5 All other rules do neither add K facts nor do they change and may only extend c Therefore we conclude by the induction hypothesis 2 Suppose that vn o F t We proceed by induction on the proof tree witnessing vn o F t Base case The proof tree consists of a single node In this case one of the deduction rules DNAME or DFRAME has been applied DNAME We have that t If t PN we use rule MDPUB and we have that Sn S Sn U IK t In case t FN we need to consider 3 different cases i K t Sn and we immediately conclude by letting S Sn ii Fr t Sn and applying rule MDFRESH we have that Sn gt S Sn U IK t iii Fr t Z Sn By inspection of the rules we see that Fr t g S for any 1 i n the only rules that could remove Fr t are MDFRESH which would have created the persistent fact K t or the ProtoNonce rules which would however have added t to Hence applying successively rules FRESH and MDFRESH yields a valid extension of the execution Sn gt Sn U
65. ck u t Em E Vj lt k lt n Unlock u t ZE Ej and since Ej E41 0 and E Unlock n t a contradiction to Condition 6 would constitute of j and u p n such that Lock u t g Ej and Vj lt k lt n Unlock u t g Ex We will show that this leads to a contradiction with E4 En F o Fix j and u By definition of P and well formedness of P there is a p that is a prefix of p such that P lockt Q for the same annotation l and parameter t The form of the translation guarantees that if statep t Sn then for some there is i lt n such that statey Sj if p is a prefix of p We therefore have that there is i lt n such that E p Lock nj t V We proceed by case distinction Case 1 j lt i see Figure 18 Since Vj lt k n Unlock u t g Ex E4 En Y Qtock Lock u t Lock n t Unlock n t I 1 Figure 18 Visualisation of Case 1 Case 2 i j see Figure 19 By definition of P there is no parallel and no replication between pi and p Note that any rule in P that produces a state named state for a non empty q is such that it requires a fact with name state for q q 1 or q g 2 in case of the translation of out it might require state which in turn requires statey Therefore there cannot be a second k n such that Unlock n t Eg Ej since n was added in a Fr fact in to S This means in particular that there is not k such that i lt
66. de filter traces P tr is normal C traces P Hence l hide filter traces P traces P 56
67. e Stat Verif is the only comparable tool that models locks explicitly and it has stronger restrictions Definition 13 Given a well formed ground process P we define the labelled multiset rewriting system P as MD U INIT U P D e where the rule INIT is defined as INIT Init 5 state e P p i is defined inductively for process P position p N and sequence of variables 3 in Figure l e For a position p of P we define state to be persistent if P Q for some process Q otherwise state is linear In the definition of P p we intuitively use the family of facts state to indicate that the process is currently at position p in its syntax tree A fact state will indeed be true in an execution of these rules whenever some instance of P i e the process defined by the subtree at position p of the syntax tree of P is in the multiset 7 of the process configuration The translation of the zero process parallel and replication operators merely use state facts For instance P Q p i defines the rule state 2 statey 1 4 state 2 which intuitively states that when a process is at position p modelled by the fact state being true then the process is allowed to move both to P putting state 2 to true and Q putting state 2 Z to true The translation of P O p i also contains the set of rules P p 1 3 U Q p 2 z expressing that after this transition the process
68. e P P 1 V lock t QYUf Q and O state 1 t by definition of the translation we have that holds and hold trivially Case Eis Sacs Pn 1 P U unlock t Q t On 1 Eni Eas Sac SP P Uf Q on 1 Ln 1 tU t p t By induction hypothesis P 1 amp p Sw Let p and t be such that unlock t Q p state By Definition 20 there is a ri ginsts P such that state t is 40 part of its premise By definition of P _ we can choose ri state t Unlock l t state We can extend the previous execution by one step using ri therefore Unlock 1 t 0 Ay 1 Ape cel Sp eis 141 ezec P with S 4 Sp 3 statep t U statep t It is left to show that Conditions I to S hold for n The step from S j to Spin is labelled Fg Unlock I t hence Condition 8 and Condition 2 hold In order to show that Condition 6 holds we perform a case distinction Assume t gE 4 4 Then L f n 1 C f n In this case Condition 6 holds by induction hypothesis In the following we assume t g 44 Thus there is j n l such that Lock l t g Fj and for all k such that j lt k lt n Unlock I t g Fr Since P is an unlock node and P is well formed there is a prefix q of p such that P is a lock with the same parameter and annotation By definition of P there is no parallel and no replication between q and p Note that any rule
69. e absence of replay attacks and the property that a successful login invalidates previously emitted one time passwords All three properties follow more or less directly from a stronger invariant which itself can be proven in 295 steps To find theses steps tamarin needs some additional human guidance which can be provided using the interactive mode This mode still allows the user to complement his manual efforts with automated backward search The example files contain the modelling in our calculus the complete proof and the manual part of the proof which can be verified by tamarin without interaction Our analysis makes three simplifications First in Pseryer we use pattern matching instead of decryption as demonstrated in the process Pee we introduced in Section 3 Second we omit the CRC checksum and the time stamp that are part of the one time password in the actual protocol since they do not add to the security of the protocol in the symbolic setting Third the Yubikey has actually two counters instead of one a session counter and a token counter We treat the session and token counter on the Yubikey as a single value which we justify by the fact that the Yubikey either increases the session counter and resets the token counter or increases only the token counter thereby implementing a complete lexicographical order on the pair session counter token counter A similar analysis has already been performed by Kiinnemann and Steel using
70. e insert construct the other manipulating state using the embedded multiset rewrite rules For this example the second model turned out to be more natural and more convenient allowing for a direct automated proof without any additional typing lemma We furthermore modeled the contract signing protocol by Garay et al and a simple security device which both served as examples in 8 In the contract signing protocol a trusted party needs to maintain a database with the current status of all contracts aborted resolved or no decision has been taken In our calculus the status information is naturally modelled using our insert and lookup constructs The use of locks is indispensable to avoid the status to be changed between a lookup and an insert Arapinis et al showed the crucial property that the same contract can never be both aborted and resolved However due to the fact that Stat Verif only allows for a finite number of memory cells they have shown this property for a single contract and provide a manual proof to lift the result to an unbounded number of contracts We directly prove this property for an unbounded number of contracts Finally we also illustrate the tool s ability to analyze classical security protocols by analyzing the Needham Schroeder Lowe protocol 21 8 Conclusion We present a process calculus which extends the applied pi calculus with constructs for accessing a global shared memory together with an encoding of this calcu
71. e rules in R MDOvT MDPUB MDFRESH MDAPPL FRESH remove Ack or state facts and the chain of rules R1 R2 R3 consumes as many as it produces Thus if they where in gm they would be in BS too Since n gt 2 largest m lt n 2 such that S 44 m gt 1 and therefore B holds for all parts of the trace and therefore also for the m prefix Similar for 5 Since we can literally apply the same argument for the largest M lt m such that BY se VL Inm MDIN SE or in case that there is an Ack fact in so N s for the largest m m 2 can show that 6 and 7 hold for the trace up to m or m concluding it is normal Li Definition 22 Let P be a ground process P be a multiset of processes and S a multiset of multiset rewrite rules We write P p S if there exists a bijection between P and the multiset state t Jp t state t S such that whenever O P is mapped to state t S then 1 statep t g prems R for R ginsts P _ 2 Let 0 be a grounding substitution for state x prems P such that t 0 Then Plot p E O for a substitution T and a bijective renaming p of fresh but not bound names in Q defined as follows T x 0 x if x not a reserved variable p a a if OM a When P ep S O P and state t S we also write Q p state t if this bijection maps Q to state 1 Remark 3 Note that p has the following properties by the f
72. eceived If lookup were to use pattern matching the following process P in c x lookup store as x in P might unexpectedly perform a check if store contains the message given by the adversary instead of binding the content of store to x due to an undetected clash in the naming of variables A process is ground if it does not contain any free variables We denote by Po the application of the homomorphic extension of the substitution e to P As usual we suppose that the substitution only applies to free variables We sometimes interpret the syntax tree of a process as a term and write P to refer to the subprocess of P at position p where if and lookup are interpreted as binary symbols all other constructs as unary 3 2 Semantics Frames and deduction Before giving the formal semantics of our calculus we introduce the notions of frame and deduction A frame consists of a set of fresh names fi and a substitution o and is written vn o Intuitively a frame represents the sequence of messages that have been observed by an adversary during a protocol execution and secrets generated by the protocol a priori unknown to the adversary Deduction models the capacity of the adversary to compute new messages from the observed ones Definition 1 Deduction We define the deduction relation vn o t as the smallest relation between frames and terms defined by the deduction rules in Example If one key is used to wrap a second
73. ent approaches for protocol analysis Bistarelli et al 6 also proposed a translation from a process algebra to multiset rewriting they do however not consider private channels have no support for global state and assume that processes have a particular structure These limitations significantly simplify the translation and its correctness proof Moreover their work does not include any tool support for automated verification Obviously any protocol that we are able to analyze can be directly analyzed by the tamarin prover as the rules produced by our translation could have been given directly as an input to tamarin Indeed tamarin has already been used for analyzing a model of the Yubikey device 19 the case studies presented with M dersheim s abstraction as well as those presented with StatVerif It is furthermore able to reproduce the aforementioned results on PKCS 11 13 and the TPM 12 moreover it does so without bounding the number of keys security devices reboots etc Contrary to ProVerif tamarin sometimes requires additional typing lemmas which are used to guide the proof These lemmas need to be written by hand but are proved automatically In our case studies we also needed to provide a few such lemmas manually In our opinion an important disadvantage of tamarin is that protocols are modeled as a set of multiset rewrite rules This representations is very low level and far away from actual protocol implementations making it very
74. es 5s Running times on Intel Core2 Duo 2 66Ghz with 4GB RAM little interaction 7 manual rule selections Figure 11 Case studies 7 1 Security API la PKCS 11 This example illustrates how our modelling might be useful for the analysis of Security APIs in the style of the PKCS 11 standard 23 We expect studying a complete model of PKCS 11 such as in 13 to be a straightforward extension of this example In addition to the processes presented in the running example in Section 3 the actual case study models the following two operations i encryption given a handle and a plain text the user can request an encryption under the key the handle points to ii unwrap given a ciphertext senc k2 k and a handle Ai the user can request the ciphertext to be unwrapped i e decrypted under the key pointed to by h If decryption is successful the result is stored on the device and a handle pointing to ko is returned Moreover contrary to the running example at creation time keys are assigned the attribute init from which they can move to either wrap or unwrap see the following snippet 1 in set_dec h lock att h 2 lookup att h as a in 3 if a init then 4 insert att h dec unlock att h Note that in contrast to the running example it is necessary to encapsulate the state changes between lock and unlock Otherwise an adversary can stop the execution after line 3
75. es an insert node for the value fetched by the lookup and three formulas assuring that a this insert node appears before the lookup 6 is uniquely defined i e it is the last insert to the corresponding key and c there is no delete in between Due to these conditions Qnotin only adds one Insert node per Isin node the case where an axiom postulates a node which itself allows for postulating yet another node needs to be avoided as tamarin runs into loops otherwise Similarly a naive way of implementing locks using an axiom would postulate that every lock is preceeded by an unlock and no lock or unlock 15 Q init N eg A Onoteg A Qin A Anotin A Clock Qinev and Qinit Vi j Init i A Init Qj i j eg ENS i Eq z y Qi rey Cnoteg 1725 Y i NotEq z y 7 a amp y Qin Vr y tz IsIn x y Gta gt te Insert z y Gto te lt t3 Vt4 y Insert z y Gt gt t4 lt ta V tq te V ta lt ty Vt Delete x t gt t lt te V tz lt t1 Qnotin Vz y t3 IsNotSet z Ot4 Vti y Insert z y Gt gt t3 lt t1 V 3t4 Delete zx QOt t1 lt t3 Vio y Insert z y Qt t2 lt t3 gt te lt t1 lock Va l l i j Lock l z Gi Lock l z 85 lt j Jk Unlock l z Qk i k k j Vl m Lock l x Qm gt a i m m lt k VI m Unlock I x Am gt 7 i m m lt k One ME d InEvent t i 3j K t 8j Vk Event Gk gt k lt j Vi lt k Vk t
76. et of traces to those that satisfy the trace formula w as defined in Definition Definition 15 Let o be the trace formula as defined in Definition 14 and Tr a set of traces We define filter Tr tr Tr V0 tr 0 F a The following proposition states that if a set of traces satisfies the translated formula then the filtered traces satisfy the original formula Proposition 1 Let Tr be a set of traces and q a trace formula We have that Tr v iff fiter Tr v where x is either V or 3 The proof detailed in Appendix follows directly from the definitions Next we define the hiding operation which removes all reserved facts from a trace Definition 16 hide Given a trace tr and a set of facts F we inductively define hide and hide tr if F C Fres hide F tr F Fres hide tr otherwise Given a set of traces Tr we define hide Tr hide t t Tr As expected well formed formulas that do not contain reserved facts evaluate the same whether reserved facts are hidden or not Proposition 2 Let Tr be a set of traces and p a well formed trace formula We have that Tr E p iff hide Tr F o where x is either V or 3 We can now state our main lemma which is relating the set of traces of a process P and the set of traces of its translation into multiset rewrite rules proven in the full version Lemma 1 Let P be a well formed ground process We have that traces P hide fil
77. f a global memory the abstractions performed by ProVerif introduce false attacks In the ProVerif user manual 8 Section 6 3 3 such an encoding of memory cells and its limitations are indeed explicitly discussed Due to the abstractions performed by ProVerif such a cell is treated in an approximate way all values written in the cell are considered as a set and when one reads the cell Pro Verif just guarantees that the obtained value is one Most of this work was carried out when the author was affiliated to INRIA Paris Rocquencourt France of the written values not necessarily the last one and not necessarily one written before the read Some work has nevertheless used ingenious encodings of mutable state in Horn clauses but these encodings have limitations that we discuss below A prominent example where non monotonic global state appears are security APIs such as the RSA PKCS 11 standard 23 IBM s CCA 11 or the trusted platform module TPM 27 They have been known to be vulnerable to logical attacks for some time 9 and formal analysis has shown to be a valuable tool to identify attacks and find secure configurations One promising paradigm for analyzing security APIs is to regard them as a participant in a protocol and use existing analysis tools However Herzog already identified not accounting for mutable global state as a major barrier to the application of security protocol analysis tools to verify security APIs Apart
78. ght be compromised We model the device by the following process we use out m as a shortcut for out c m for a public channel c lPrew Pset Paec Pwrap where Panew vh vk event NewKey h k insert key h k insert att h dec out h In the first line the device creates a new handle h and a key k and by the means of the event NewKey h k logs the creation of this key It then stores the key that belongs to the handle by associating the pair key h to the value of the key k In the next line att h is associated to a public constant dec Intuitively we use the public constants key and att to distinguish two databases The process Pet in h insert att h wrap allows the attacker to change the attribute of a key from the initial value dec to another value wrap If a handle has the dec attribute set it can be used for decryption Pec in h c lookup att h as a in if a dec then lookup key h as k in if encCor c k true then event DecUsing k sdec c k out sdec c k The first lookup stores the value associated to att h in a The value is compared against dec If the comparison and another lookup for the associated key value k succeeds we check whether decryption succeeds and if so output the plaintext If a key has the wrap attribute set it might be used to encrypt the value of
79. h name We define the set of traces in a similar way as for processes Definition 7 Traces The set of traces is defined as traces r R EUER VO0 lt i lt n A 40 and e ivi E Sn E exec R A A 0 where p is defined as ud gt R RR Note that both for processes and multiset rewrite rules the set of traces is a sequence of sets of facts 5 Security Properties In the tamarin tool security properties are described in an expressive two sorted first order logic The sort temp is used for time points Viemp are the temporal variables Definition 8 Trace formulas A trace atom is either false L a term equality t4 t2 a timepoint ordering i lt j a timepoint equality i j or an action FQi for a fact F F and a timepoint i A trace formula is a first order formula over trace atoms As we will see in our case studies this logic is expressive enough to analyze a variety of security properties including complex injective correspondence properties To define the semantics let each sort s have a domain D s D temp O D msg M D fresh FN and D pub PN A function 0 Y gt MU Q is a valuation if it respects sorts that is 0 V C D s for all sorts s If t is a term t is the application of the homomorphic extension of 0 to t Definition 9 Satisfaction relation The satisfaction relation tr 0 F p between trace tr valuation 0 and trace formula is defined as follows tr 0 EL never tr 0
80. ich allows to manually guide the tool in its proof Our specification language includes support for private channels global state and locking mechanisms which are crucial to write meaningful programs in which concurrent threads manipulate a common memory The translation has been carefully engineered in order to favor termination by tamarin We illustrate the tool on several case studies a simple security API in the style of PKCS 11 a complex case study of the Yubikey security device as well as several examples analyzed by other tools that aim at analyzing stateful protocols In all of these case studies we were able to avoid restrictions that were necessary in previous works Related work The most closely related work is the StatVerif tool by Arapinis et al 3 They propose an extension of the applied pi calculus similar to ours which is translated to Horn clauses and analyzed by the ProVerif tool Their translation is sound but allows for false attacks limiting the scope of protocols that can be analyzed Moreover StatVerif can only handle a finite number of memory cells when analyzing an optimistic contract signing protocol this appeared to be a limitation and only the status of a single contract was modeled providing a manual proof to justify the correctness of this abstraction Finally Stat Verif is limited to the verification of secrecy properties As illustrated by the Yubikey case study our work is more general and we are able to analy
81. it is also possible to apply the same instance of FRESH to the prefix by Definition 6 and therefore 0 s 05 Si SU Fr a filter d exec LP P UMD contradicting the induction hypothesis Li Lemma 7 For any frame vn c t M and a FN if a Z st t a Z st c and vn o F t then vf a c Ft Proof In I Proposition 1 it is shown that vi o F t if and only if 3M fn M n i 0 and Mo p t Define M as M renaming a to some fresh name i e not appearing in 51 0 t As a st o t and the fact that equational theories are closed under bijective renaming of names we have that M o p t and fn M n a 0 Hence vn a c F t L1 Lemma 8 Let P be a ground process and GP ME TE futer ezec P Let n a fresh ProtoNonce a U Fj 1 lt j lt n ti ned iim t Out t E1 lt j lt n S Let o Ba i m am We have that 1 if IK t Sn then vn o F t 2 ifvn o Ft then there exists S such that sd 5g 55 5 9 8 filter exech LP e IK t Ex S and e S S for R MDOvT MDPUB MDFRESH MDAPPL FRESH Proof We prove both items separately 1 The proof proceeds by induction on n the number of steps of the execution 28 Base case n 0 This case trivially holds as S 0 Inductive case n0 By induction we suppose that if K t S 4 then vn c t where n o are defined in a similar way as fi 0 but for the execution of size n
82. kup The first one only adds a permanent fact which by the definition of d is removed when applying d The second one requires a fact IDum t whenever the rule is instantiated such the actions equals IsIn s t for some s Since the translation is otherwise the same we have that filter d exec P P U MD filter exec P For any trace in filter d exec p U MD and any action Isln s t in this trace there is an earlier action Insert s t such that s s and t t as otherwise ain would not hold Therefore the same trace is part of filter d exec p P U MD as this means that whenever Dum t is in the premise Dum t for t t has previously appeared in the conclusion Since it is a permanent fact it has not disappeared and therefore filter d exec LP P U MD f ter exec P Li We slightly abuse notation by defining filter on executions to filter out all traces contradicting the axioms see Definition 15 Lemma 6 Let P be a ground process and 0 an S i EC S filtler ezec P For all 1 lt i lt n ifFr a S and F ty th S for any F Xia Fr then a C 5g names t for any t t1 tk 27 Proof The translation with the dummy fact introduced in will make this proof easier as for P UMD we have that the third condition of holds namely W 4a r Ex ginsts l a r Qa 5 names r FN C Dis gpnames I N FN 1 We will
83. lus in labelled msr rules which enables automated verification using the tamarin prover as a backend Our prototype verification tool au tomating this translation has been successfully used to analyze several case studies As future work we plan to increase the degree of automation of the tool by automatically generating helping lemmas To achieve this goal we can exploit the fact that we generate the msr rules and hence control their form We also plan to use the tool for more complex case studies including a complete model of PKCS 11 and a study of the TPM 2 0 standard currently in public review Finally we wish to investigate how our constructs for manipulating state can be used to encode loops needed to model stream protocols such as TESLA Acknowledgements The research leading to these results has received funding from the European Research Council under the European Union s Seventh Framework Programme FP7 2007 2013 ERC grant agreement no 258865 project ProSecure and was supported by CASED http www cased de References 1 M Abadi and V Cortier Deciding knowledge in security protocols under equational theories Theoretical Computer Science 387 1 2 2 32 2006 2 M Abadi and C Fournet Mobile values new names and secure communication In Proc 28th ACM Symp on Principles of Programming Languages POPL 01 pages 104 115 ACM Press 2001 3 M Arapinis E Ritter and M Ryan Statverif Verification of sta
84. marin prover as a backend We apply the tool to several case studies among which a simplified fragment of PKCS711 the Yubikey security token and an optimistic contract signing protocol 1 Introduction Automated analysis of security protocols has been extremely successful Using automated tools flaws have been for instance discovered in the Google Single Sign On Protocol 5 in commercial security tokens implementing the PKCS 11 standard 10 and one may also recall Lowe s attack on the Needham Schroeder public key protocol 17 years after its publication While efficient tools such as ProVerif 7 AVISPA 4 or Maude NPA exist these tools fail to analyze protocols that require non monotonic global state i e some database register or memory location that can be read and altered by different parallel threads In particular ProVerif one of the most efficient and widely used protocol analysis tools relies on an abstraction that encodes protocols in first order Horn clauses This abstraction is well suited for the monotonic knowledge of an attacker who never forgets makes the tool extremely efficient for verifying an unbounded number of protocol sessions and allows to build on existing techniques for Horn clause resolution However Horn clauses are inherently monotonic once a fact is true it cannot be set to false anymore As a result even though ProVerif s input language a variant of the applied pi calculus 2 allows a priori encodings o
85. may behave as P and Q i e the processes at positions p 1 respectively p 2 in the process tree Also note that the translation of P results in a persistent fact as P always remains in 7 The translation of the construct v a translates the name a into a variable Na as msr rules must not contain fresh names Any instantiation of this rule will substitute ng by a fresh name which the Fr fact in the premise guarantees to be new This step is annotated with a reserved action ProtoNonce used in the proof of correctness to distinguish adversary and protocol nonces Note that the fact state in the conclusion carries na so that the following protocol steps are bound to the fresh name used to instantiate na The first rules of the translation of out and in model the communication between the protocol and the adversary and vice versa In the case of out the adversary must know the channel M modelled by the fact In M in the rule s premisse and learns the output message modelled by the fact Out N in the conclusion In the case of in the knowledge of the message N is additionally required and the variables of the input message are added to the parameters of the state fact to reflect that these variables are bound The second and third rules of the translations of out and in model an internal communication which is synchronous For 12 0 p 4 P Q p E p 2 Iva P p d Out M N P p In M N P p 3 state
86. n and which maps z to t As usual we homomorphically extend to apply to terms and facts and use a postfix notation to denote its application e g we write to for the application of to the term t A substitution is grounding for a term t if to is ground Given function g we let g x L when x D x When g x L we say that g is undefined for x We define the function f gla b with D f D g U a as f a b and f x g x for x a Sets sequences and multisets We write N for the set 1 n Given a set S we denote by S the set of finite sequences of elements from S and by S the set of finite multisets of elements from S We use the superscript to annotate usual multiset operation e g S1 U Sz denotes the multiset union of multisets 1 5 Given a multiset S we denote by set S the set of elements in S The sequence consisting of elements e1 n will be denoted by e1 en and the empty sequence is denoted by We denote by S the length i e the number of elements of the sequence We use for the operation of adding an element either to the start or to the end e g e1 e2 e3 e1 2 e3 e1 e2 es Given a sequence S we denote by idx S the set of positions in S i e N when S has n elements and for i idz S S denotes the ith element of the sequence Set membership modulo E is denoted by p and defined as e g S if de S e p e Cg and p are defined for se
87. n we learn that l Zg l for any l and m i lt m lt j such that Unlock l t Fm We now choose the smallest such m By definition of P the step from S _1 to Sm must be ground instance of a rule from P i for P starting with unlock Since P is well formed there is a q such that P starts with lock with the same label and parameter as the unlock As before since P is well formed and therefore there are no replications and parallels between q and q there must be n such that Lock t Fn and n lt m We proceed again by case distinction Case 2a n lt i see Figure 14 By the fact that m gt i we have that there is no o such that n lt o lt i and Unlock l t g Fo see first observation Therefore the trace produced by the i prefix of this execution does already not satisfy Qjgcx i e Fi Fi Z Qiock Lock I t Lock I t Unlock I t Unlock l t i u Figure 14 Visualisation of Case 2a Case 2b i lt n see Figure 15 Again aj is not satisfied i e F1 Fn Z Qlock since there is no o such that i lt o lt n and Unlock l t Eg Fo Lock l t Lock l t Unlock I t Unlock l t i i Figure 15 Visualisation of Case 2b Since we could under the assumption that Condition to Condition S hold for i lt n reduce every case in which Fi Fj 44 IZ Glock to a contradiction we can conclude that holds for n 4 1 Sinc
88. nd names in Q such that P rp Q see Definition 22 From the form of the rule R and since Q P pTp we can deduce that Q lock t Q for Q Pl 1Tp Since E1 En F Qicck for every i lt n such that Lock l5 t g Ej there a j such that i lt j lt n and Unlock lj t Eg Ej and in between i and j there is no lock or unlock i e for all k such that i k lt j and all lj Lock l t g Ej and Unlock l t g Ex Since E4 E we know that this holds for i lt m and j lt m as well By induction hypothesis this implies that t Zp Lw We therefore chose the following transition FS MS MS dc gt Ew Sn S Pu On Ly Ew 41 Sua Oni PwW 1 On 1 Lisa with 44 Ew 6 41 Sn SU SMS Pwi Pw VE lock t Q y Ut Q yF On 41 On and Lwy le U t We define f as on page BI Therefore Conditions I to S hold for i lt n 1 It is left to show that Conditions 1 to 8 hold for n By definition of P and P _ we have that Q statep 1 t Therefore and since lock t Q amp state Pw 1 Pw V lock t Q V Uf Q Y and S 8 4 state f Fr lock Yf Uf statey 1 t lock holds Condition 6 holds since E Lock lock t is added to the end of the trace Conditions and 7 hold trivially Case ri state t Unlock n t statep 1 t for some p t n FN and t M By induction hypothesis we have Pw p Sm and thus as p
89. nd repeat this for all t1 t2 such that Ack t t2 p Then SO pst and so does not contain Ack facts anymore If S o contains a fact statem we remove the last transition that produced this fact i e for i such that S S 1 V states f U Msg ty t2 states t V we define s EN ijzi l j su semi Ax ipo 41 Msg ti t2 statese t V Uf state f ifi l lt j lt n The resulting execution is valid since state emi f t S and since Msg t1 t2 sa The latter is the case because if Msg t1 t2 would be consumned at a later point say j j 1 would contain Ack t4 t2 but since SU does not contain Ack facts they can only be consumned by a rule of type R3 which would have consumned state em t t We repeat this procedure for every remaining state f S and call the resulting trace 2 E EO 2 SP py pp S n Since no rule added or removed or removed has an action hide Ej En hide EC Ead By c EC Dea Ee EQ We transform go 2 Py P PI s U as follows all equalities are modulo E Let us call instances of Ri R or Ra that appear outside a chain Si 3 Ry Si 2 R2 Si 1 FB Si for some t4 t9 M unmarked Do the following for the smallest that is an unmarked instance of Rg we will call the instance of R3 rig and suppose it is applied from 1 to Apply riz after j lt i such that Sj to 5 is the first unmarked instance
90. ne whether one counter value is smaller than another To this end our modelling employs a feature added to the development version of tamarin as of October 2012 a union operator U for multisets of message terms The operator is denoted with a plus sign We model the counter as a multiset only consisting of the symbols one and zero The multiplicity of one in the multiset is the value of the counter A counter value is considered smaller than another one if the first multiset is included in the second A test a b is included by adding the event Smaller a b and an axiom that requires that a is a subset of b QSmaller Vi temp a b msg Smaller a b i gt dz msg a z b We incorporate this axiom into the security properties just like in Definition Intuitively we are only interested in traces where a is indeed smaller than b The process we analyse models a single authentication server that may run arbitrary many threads and an arbitrary number of Yubikeys i e Pserver Pyubikey Among other properties we show by the means of an injective correspondence property that an attacker that controls the network cannot perform replay attacks and that each successful login was preceded by a user pressing the button formally V pid k x to Login pid k z Gto gt Jsid t1 YubiPress pid sid k x Qt t4 lt t2 A Vt3 Login pid k x Qt3 gt t3 t2 Besides injective correspondence we show th
91. of Rz for some q and y i e this instance produces a fact statey 1 y y and a fact Ack t t2 Since there is no rule Me j and i that might consume Ack t t2 only rules of form Rg do and rig is the first unmarked instance of such a rule and since rig does not consume statey 1 y y we can move rig between j and j 1 adding the conclusions of ria and removing the premises of rig from every Sj41 5 Note that unmarked instances of Fi and R3 are guaranteed to be preceeded by a marked R1 and therefore only remove facts of form Ack or Msg that have been added in that preceeding step Since the transition at step j requires a fact Msg t t2 there is an instance of R prior to j say at k lt j since only rules of form R produces facts labelled Msg t1 t2 Since riz is now applied from Sj to S 4 we have that an instance ri of a rule of 43 form R that produces states 1 must appear before j i e rij ginsts P Therefore it produces a fact Msg t1 t2 indeed We choose the largest k that has an unmarked R that produces Msg t1 t2 and states 1 t and move it right before j resulting in the following msr execution se ift lt k SC U Msg t1 t2 state V state ifk lt t lt j 1 si i fj 1 lt t lt j 1 Bu a state emi t Ack t1 t2 V Uf state i Q ifj 1 lt t lt i 1 s ifitl lt t We apply this procedure until it reaches a fixpoint and call the resulting trace ge
92. ols each with an arity We write f n when function symbol f is of arity n We denote by 7 the set of well sorted terms built over X PN FN and V For a term t we denote by names t respectively vars t the set of names respectively variables appearing in t The set of ground terms i e terms without variables is denoted by My When is fixed or clear from the context we often omit it and simply write 7 for 75 and M for Ms We equip the term algebra with an equational theory E that is a finite set of equations of the form M N where M N T From the equational theory we define the binary relation p on terms which is the smallest equivalence relation containing equations in F that is closed under application of function symbols bijective renaming of names and substitution of variables by terms of the same sort Furthermore we require E to distinguish different fresh names i e Va b FN a b a p b Example Symmetric encryption can be modelled using a signature E senc 2 sdec 2 encCor 2 true 0 and an equational theory defined by sdec senc m k k m encCor senc zx y y true The last equation allows to check whether a term can be correctly decrypted with a certain key For the rest of the paper we assume that E refers to some fixed equational theory and that the signature and equational theory always contain symbols and equations for pairing and projection i e fst snd X and equations
93. onditions and 7 hold trivially Case ri state t Fr a fresh ProtoNonce a fresh gt state t a fresh for some p t and a FN By induction hypothesis we have P p Sm and thus as previously established Pa 9p Sia Let O Pw such that Q ep state t Let 9 be a grounding substitution for state 7 prems P such that t 0 Then 0 induces a substitution 7 and a bijective renaming p for fresh but not bound names in Q such that P 7p O see Definition 22 From the form of the rule R and since Q P pTp we can deduce that Q va Q for a name a FN and a process Q P ya7p By definition of ezec the fact Fr a can only be produced once Since this fact is linear it can only be consumed once Every rule in P that produces a label ProtoNonce x for some z consumes a fact Fr x Therefore a a FN ProtoNonce a g U Es 1 lt j lt n 1 The induction hypothesis allows us to conclude that a Ewi e a is fresh We therefore chose the following transition Fg Sy SM MS n B On Eu Eni Sua On Li Pri 1 On 1 Laga 48 with u En Ue Su Sy SE SP Pu V qao ut QT 05 41 On and 44 Ly We define f as on page 5I Therefore Conditions I to 8 hold for i lt n 1 It is left to show that Conditions I to 8 hold for n By definition of P statej 1 2 a prems R for an R P _ We can choose 4 0
94. ons in a similar way to events The purpose of this construct is to provide access to the underlying notion of state in tamarin but we stress that it is distinct from the previously introduced functional state and its use is only advised to expert users We allow this low level form of state manipulation in addition to the functional state as it offers a great flexibility and has shown useful in one of our case studies This style of state manipulation is similar to the state extension in the strand space model and the underlying specification language of the tamarin tool 26 Note that even though those stores are distinct which is a restriction imposed by our translation data can be moved from one to another for example as follows lookup storel as z in H gt store2 z In the following example which will serve as our running example we model a security API that even though much simplified illustrates the most salient issues that occur in the analysis of security APIs such as PKCS 11 Example We consider a security device that allows the creation of keys in its secure memory The user can access the device via an API If he creates a key he obtains a handle which he can use to let the device perform operations on his behalf For each handle the device also stores an attribute which defines what operations are permitted for this handle The goal is that the user can never gain knowledge of the key as the user s machine mi
95. ookup t as z in Q else Q o 3 Ln 1 gt n 1 Sn 1 SMS P U Q u z on 1 n 1 This step requires that S _1 t g v for some t 2g t By induction hypothesis P 1 p Sw Let p and t be such that lookup t as v in O else Q p state t By Definition 20 there is a ri ginsts P _ such that state 4 is part of its premise By definition of P _ we can choose ri state IsIn t v state 1 v We can extend the previous execution by one step using ri therefore IsIn t Dy 1 Hp a S MIU 141 ezec JPJ with Sj 1 Sr 1 statep t Uf statep t It is left to show that Conditions I to 8 hold for n This step is labelled F IsIn t v hence Condition 8 holds From the induction hypothesis we have that there is a j such that Insert t t g Fj j lt n and Vj uw j j xn gt Insert t u gp Fy Delete t g Fy This can be strengthened since Fyn IsIn t v Mj ou ug s Insert t u g Fj Delete t g Fj This allows to conclude that Condition 2 holds From it also follows that in particular oj holds We now show that Condition 4Jholds By induction hypothesis we have that lookup t as z in Q else Q 4p state and hence P 7 lookup t as x in Q else Q p for some 7 and p Therefore we also have that Plpit U U 5 0p and it is easy to see from definition of P _ that 0 2P statep 1 t v Since P P 4 V lookup t a
96. pothesis P 1 p Sw Let p and t be such that Q R p state t By Definition 20 there is a ri ginsts P _ such that state t is part of its premise By definition of P _ we can choose ri state t 4 state state 2 t We can extend the previous execution by one step using ri therefore dus nj SS msr P gt ja 1 pj pp Su py Sn 41 exec LP with Sj 41 Spa 1 V statep t U statep 1 state o t It is left to show that Conditions I to 8 hold for n and hold trivially We now show that Condition 4 holds Condition 4 holds because 7 Pn i V Q R Uf Q R O Gp state 1 Z and R op statep 2 by definition of the translation see Remark 2 Case s 1 851 518 P 1 P U IQ os 1 3 En 1 Sn 1 SMS P U IQ Q On 1 n 1 Let p and t such that O p state t By Definition 20 there is a ri ginsts P _ such that state t is part of its premise By definition of P _ we can choose ri state 4 Jo state t state 1 We can extend the previous execution by 1 step using ri therefore Fu ri mer 0 Dy 1 yn e gt P Sn 35 Sy 441 exec P with S 44 Sr U state 1 Condition 4 holds because P P 1 U O and O op state 1 by definition of P _ Condition 1 Condition 2 Condition 3 Condition 5 Condition 6 Condition 7 and hold trivially Case 4 1 95 3 9 P
97. r k can be used to authenticate against a server that shares the same secret key which we model in the process Pseryer The process receives the encrypted one time password along with the public id pid of a Yubikey and a nonce that is part of the protocol but is irrelevant for the authentication of the Yubikey on the server The server looks up the secret id and the AES key associated to the public id i e to the Yubikey sending the request as well as the last recorded counter value otc If the key and secret id used in the request match the values retrieved from the database then the event Smaller otc tc is logged along with the event Login pid k tc which marks a successful login of the Yubikey pid with key k for the counter value tc Afterwards the old tuple secretid k otc is replaced by secretid k tc to update the latest counter value received Pserver in pid nonce senc secretid tc npr k lock pid lookup Server pid as tuple in if fst tuple secretid then 19 if fst snd tuple k then event Smaller snd snd tuple tc event Login pid k tc insert Server pid secretid k tc unlock pid Note that in our modelling the server keeps one lock per public id which means that it is possible to have several active instances of the server thread in parallel as long as all requests concern different Yubikeys An important part of the modelling of the protocol is to determi
98. ra P U va Q on 1 Ln 1 gt Put da SS P U Q a 051 C41 for a fresh a Let p and be such that va Q p state f There is a ri ginsts P _ such that statep t is part of its premise By definition of P _ there is a ri ginsts P _ ri state Fr a fresh ProtoNonce a fresh gt statey 1 t a fresh Assume there is an i lt n such that Fr a S If Fr a Sn then we can remove the application of the instance of FRESH that added Fr a while still preserving Conditions 1 to S If Fr a is consumned at some point by the definition of P the transition where it is consumned is annotated either ProtoNonce a or Lock a t for some t In the last case we can apply a substitution to the execution that substitutes a by a different fresh name that never appears in U lt n S The conditions we have by induction hypothesis hold on this execution too since Lock Fres and therefore Condition 8 is not affected The first case implies that a 1 contradicting the assumption that a is fresh with respect to the process execution Therefore without loss of generality the previous execution does not contain an i lt n such that Fr a S and we can extend the previous execution by two steps using the FRESH rule and ri therefore i FE F T 0 Ay Si Sii Kate IP S S Sua au S 42 erec P 33 with S41 Sw Uf Fr a fresh
99. resh but not pond names in Q such that P 7p O see Definition 22 From the form of the rule R and since Q P pTp we can deduce that Q insert t ta Q for a process Q P p 1 Tp We therefore chose the following transition Fn MS MS ewe Ew Sw S Pals On Ly Ena Sn Swi Pri tis On 4 1 Esta with 41 y w41 Sy h e tol SMY SME Dua Pn VE insert t to Q U Q jos On 41 On and Ly y We define f as on page 5I Therefore Conditions to S hold for i lt n 1 It is left to show that Conditions I to S hold for n By definition of P and P _ we have that Q statep 1 t Therefore and since insert ty t2 Q 4 state 1 Pri Pw V insert tj t5 Q V Uf Q and S S 4 state t Uf states i 0 holds Condition 2 holds since Ej Insert t4 t2 is the last element of the trace Conditions 6 and 7 hold trivially Case ri state t Delete t t2 gt state 1 t for some p t and t t M By induction hypothesis we have Pa p Sm and thus as previously established Py ep S 4 Let O P such that O p state t Let 0 be a grounding substitution for state Z prems P _ p Such hal t 0 Then 0 induces a substitution T and a bijective renaming p for fresh but not Bound names in Q such that P rp Q see Definition 22 52 From the form of the rule R and since Q P pTp we can deduce that Q delete t1
100. reviously established Pw ep S 4 Let O Ef Pw such that Q ep statep t Let 0 be a grounding substitution for state Z prems P _ such that t 20 Then 0 induces a substitution 7 and a bijective renaming p for fresh but not bound names in Q such that P rp O see Definition 22 From the form of the rule R and since Q P pTp we can deduce that Q unlock t Q for Q Plp1rp We therefore chose the following transition Fn MS MS en En Sv S Pw On Ew 3 w 1 Ov44 Ond Py On 41 La with 41 En w 41 Sn SNRs sS Pritt Pw V unlock t Q UF Q V On 4 On aud ag Lw t We define f as on page BI Therefore Conditions I to 8 hold for i lt n 1 It is left to show that Conditions I to 8 hold for n By definition of P and P _ we have that Q state 1 Therefore and since unlock t Q amp state 1 Pri P V unlock t Q V Uf Q y and Sn 8 1 V states UF statep 1 t Condition 4 holds We show that Condition 6 holds for Lw41 Lw t For all t p t t g Lw St Ex u by induction hypothesis If t g Lw then Vj m u Lock u t Eg E dj lt k n Unlock u t Eg Ey Since we have Ej En 1 0 and E Unlock nj t V we can strengthen this to Vj lt n u Lock u t Ep Ej gt Aj lt k n Unlock u t g Ek which means that the condition holds in 54 this case If t Eg Lw then dj n u Lo
101. rivially Case ri state t In lt t t2 gt InEvent t t2 statez 1 0 77 for some p t t and K t1 t9 M Since the msr execution is normal we have that CR NL US ANE DN Since So pq yl Sin En En is normal so is So p EE P 95 1 and therefore So p QE P 9n 2 Hence there is an m lt n 2 such So pq m Pa is a normal trace and Sm 5 S4 for R MDOUT MDPUB MDFnEsH MDAPPL FRESH By induction hypothesis we have Pw ep Sm Since MDOUT MDPuB MDFRESH MDAPPL FRESH and MDIN do not add or remove state facts Pa p 2 Let O P such that Q p statep t Let 0 be a grounding substitution for state Z prems P such that t 0 Then 0 induces a substitution 7 and a bijective renaming p for fresh but not bound names in Q such that P yrp Q see Definition 22 From the form of the rule R and since Q P 7p we can deduce that Q in t1 N Q for N a term that is not necessarily ground and a process Q P p 17p Since ri Ep ginsts R we have that there is a substitution 7 such that Nr p t From the induction hypothesis and since E5 4 Zn 2 9 we have that En a ProtoNonce a U Big 1 lt j lt n 2 From the induction hypothesis and since no rule producing Out facts is applied between step m and step n 2 we have that zow x D o y Out t Uxzn 25 M 4 Let 7 a fresh RepNonce a U12 2 4 Fj Since K lt
102. s Also note that the second condition is not necessarily preserved during an execution e g when unfolding a replication P and P may bind the same names We only require this condition to hold on the initial process for our translation to be correct 11 The annotation of locks restricts the set of protocols we can translate but allows us to obtain better verification results since we can predict which unlock is supposed to close a given lock This additional information is helpful for tamarin s backward reasoning We think that our locking mechanism captures all practical use cases Using our calculus low level multiset manipulation construct the user is also free to implement locks himself e g as NotLocked code NotLocked In this case the user does not benefit from the optimisation we put into the translation of locks Obviously locks can be modelled both in tamarin s multiset rewriting calculus this is actually what the translation does and M dersheim s set rewriting calculus 22 However protocol steps typically consist of a single input followed by several database lookups and finally an output In practice they tend to be modelled as a single rule and are therefore atomic Real implementations are however different as several entities might be involved database lookups could be slow etc In this case such simplified models could e g miss race conditions To the best of our knowledg
103. s I to 8 hold for i lt n 1 It is left to show that Conditions 1 to 8 hold for n Condition 7 holds since hide E1 E4 Fy n and Eg1 Eni 0 while E F Event a note that Event Fres As established before we have 7 such that J a r r g l dal r By the definition of P _ we have that state 1 t t g ginsts P p 1 and a 6 0 7 that is grounding for state 1 t t Since T and p are induced by 0 6 induces 7 7 and the same p We have that Q r P p 17p T P yrT p 55 and therefore Q r p statej4 f t Thus and since a r Q ep state t Praia Pw 1 Aa r Q UF Q r V and Sn S 1 V Ifacts l U r statep t Uf statep 1 t t Condition 4 holds holds since Sn Fres Sn 1 Vf Ifacts U Uf r NF statep t V U statep 1 T Fres Sp 1 lfacts U Uf v Fres S a Vf Fres V ifacts I Uf r SMS lfacts l Uf pl Sii Conditions 6 and 7 hold trivially Lemma 1 Let P be a well formed ground process We have that traces P hide filter traces P Proof From Lemma 10 we can conclude that traces P C hide t tr traces LP and tr F a hide filter traces LP From Lemma 11 we have that hide filter traces IP tr hide filter traces LP tr is normal From Lemma 12 we can conclude that tr hi
104. s z in O else Q U Q we have that P Gp S f n i e Condition 4 holds and hold trivially 37 Case En 1 Sn 1 SM Pe P U lookup t as x in Q else Q on 1 4 1 gt En 1 Sn 1 SMS P U Q ou a 4 This step requires that S t is undefined for all t p t By induction hypothesis P 1 p Sw Let p and t be such that lookup t as x in Q else Q p statep t By Definition 20 there is a ri ginsts P such that state is part of its premise By definition of P _ we can choose ri state t IsNotSet t gt state 1 t We can extend the previous execution by one step using ri therefore F F Fu IsNotSet t mier PI 1 PI e SIP S O T exec LP with S 4 Sr 4 statep t U statep 1 1 It is left to show that Conditions I to B hold for n This step is labelled F y IsNotSet t hence holds also holds trivially and will be used to show Since this step requires that S t is undefined for all t z t we have by that Vj f n u Insert t u g Fj gt 3j u j lt j f n Insert t v g Fy v Delete t g Fy Now suppose that Ji lt f n y Insert t y g F As there exists an insert there is a last insert and hence we also have Ji f n y Insert t y g F Vi y i i f n gt Insert t y g Fy Applying Condition 2 cf above we obtain that Ji f n y Insert t y eg F
105. sation Le P be a well formed ground process If So 0 Dy 1 DPI T Dy Sn exec P and E4 En F a then there exists a normal msr execution To 0 Ay Ti Ay TT Le T exec LP such that hide E4 En hide Fi Fy and Fy Fw Fa Proof We will modify So Dy np Dy S by applying one transformation after the other each resulting in an msr execution that still fulfills the conditions on its trace 42 1 3 If an application of the INIT rule appears in So Dy d Dy 4 we move it to the front Therefore S statej This is possible since the left hand side of the INIT rule is empty If the rule is never instantiated we prepend it to the trace Since Init Fres the resulting msr execution 1 Ei Ew 1 Sj Sie p Sen is such that Aide Ei En hide E EY Ma so HE Since Init is only added if it was not present before B EO Fa EST Quinit For each fact Ack t1 t2 contained in Br it also contains a fact states 1 t for some p and t such that there exists a rule of type R3 that consumes both of them since Ack t4 t2 can only be produced by a rule of type Rg which consumes Msg t1 t2 which in turn can only be produced along with a fact states t t and by definition of P there exists a rule in P _ of form R3 that consumes Ack t t2 and states 1 t We append as many applications of rules of type R3 as there are facts Ack t t2 s a
106. show that the statement holds for all 5 S1 7 4 Sn filter exec P P U MD which implies the claim by Lemma 5 We proceed by induction on n the length of the execution e Base case n 0 We have that So and therefore the statement holds trivially e Inductive case n gt 1 We distinguish two cases 1 A rule that is not FRESH was applied and there is a fact F t t Sn such that F ti tk S 1 and Fr a S such that a y 4e names t for some t If there are no such F t1 tx and Fr a we immediately conclude by induction hypothesis By a t for some F t5 tj S 1 Since FRESH is the only rule that adds a Fr fact and Fr a Sn it must be that Fr a S 1 contradicting the induction hypothesis Therefore this case is not possible 2 The rule FRESH was applied i e Fr a S and Fr a S If there is no a P2 5 names t for some tj and F t1 t Sn then we conclude by induction hy pothesis Otherwise if there is such a F t4 ty Sn then by Equation 1 a t for some F t t S for i lt n We construct a contradiction to the induction hypothesis by taking the prefix of the execution up to 7 and appending the instantiation of the FRESH rule to its end Since d erec P U MD is prefix closed by Lemma 4 we have that rs 1 c filter d exec r P P U MD Moreover as rule FRESH was applied adding Fr a S
107. t 6 Pop S Po iD s D Sua ere P with S 4 Sp 3 state f U statep t It is left to show that Conditions I to B hold for n This step is labelled Fyn Delete t hence Condition 8 holds Since by induction hypothesis Condition 7 holds i e F Fy E a it holds for this step too In particular if F Fw E ain and Fi Fw F Anotin we also have that F Fw Fm F Qin and Fi Fr Ffin F Qnotin as the Insert action was added at the last position of the trace it appears after any InIn or IsNotSet actions and by the semantics of the logic the formula holds We now show that holds We have that Sn S 4 t L and therefore for all t ZE Tt S x S 1 x Hence for all such t we have by induction hypothesis that for some u 3j n Insert t u Fj AVG uj lt j n 2 Insert t vw dg Fy Delete t g Fy As Fy41 ZE Delete z u and for all u M Fw 1 p Insert z u we also have that j n LInsert t u Fj A Vj u j j n 1 Insert t v g Fy A Delete t g Fy For t p t the above condition can never be true because F Delete t which allows us to conclude that Condition 2 holds Since Pp P 1 Vf C cie EE i Qj a ERAS and P e state 1 by definition of P p We have that Condition 4 holds Condition 1 Condition 3 Condition 5 and Condition 6 hold trivially Case En 1 Spies Paci P U l
108. tamarin s multiset rewriting calculus 19 However the model in our new calculus is more fine grained and we believe more readable Security relevant operations like locking and tests on state are written out in detail resulting in a model that is closer to the real life operation of such a device The modeling of the Yubikey takes approximately 38 lines in our calculus which translates to 49 multiset rewrite rules The model of 19 contains only four rules but they are quite complicated resulting in 23 lines of code More importantly the gap between their model and the actual Yubikey protocol is larger in our calculus it becomes clear that the server can treat multiple authentication requests in parallel as long 20 as they do not claim to stem from the same Yubikey An implementation on the basis of the model from K nnemann and Steel would need to implement a global lock accessible to the authentication server and all Yubikeys This is however unrealistic since the Yubikeys may be used at different places around the world making it unlikely that there exist means of direct communication between them While a server side global lock might be conceivable albeit impractical for performance reasons a real global lock could not be implemented for the Yubikey as deployed 7 3 Further Case Studies We also investigated the case study presented by M dersheim 22 a key server example We encoded two models of this example one using th
109. teful processes In Proc 24th IEEE Computer Security Foundations Symposium CSF 11 pages 33 47 IEEE Press 2011 21 4 5 l6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 A Armando D A Basin Y Boichut Y Chevalier L Compagna J Cu llar P H Drielsma P C H am O Kouchnarenko J Mantovani S M dersheim D von Oheimb M Rusinowitch J Santiago M Turuani L Vigan and L Vigneron The AVISPA tool for the automated validation of internet security protocols and applications In Proc 17th International Conference on Computer Aided Verification CAV 05 LNCS pages 281 285 Springer 2005 A Armando R Carbone L Compagna J Cuellar and L T Abad Formal analysis of saml 2 0 web browser single sign on Breaking the saml based single sign on for google apps In Proc 6th ACM Workshop on Formal Methods in Security Engineering FMSE 08 pages 1 10 2008 S Bistarelli I Cervesato G Lenzini and F Martinelli Relating multiset rewriting and process algebras for security protocol analysis Journal of Computer Security 13 1 3 47 2005 B Blanchet An Efficient Cryptographic Protocol Verifier Based on Prolog Rules In Proc 14th Computer Security Foundations Workshop CSFW 01 pages 82 96 IEEE Press 2001 B Blanchet B Smyth and V Cheval ProVerif 1 88 Automatic Cryptographic Protocol Verifier User Manual and Tutorial 2013
110. ter traces P Our main theorem can now be proven by applying Lemma 1 Proposition 3 and Proposition 1 Proof of Theorem U traces P E o hide f ter traces P F e by Lemma 1 amp filter traces P F ve by Proposition 3 traces P Ie by Proposition 1 17 7 Case studies In this section we briefly overview some case studies we performed These case studies include a simple security API similar to PKCS 11 23 the Yubikey security token the optimistic contract signing protocol by Garay Jakobsson and MacKenzie GJM and a few other examples discussed in Arapinis et al 3 and M dersheim 22 The results are summarized in Figure 11 For each case study we provide the number of typing lemmas that were needed by the tamarin prover and whether manual guidance of the tool was required In case no manual guidance is required we also give execution times We do not detail all the formal models of the protocols and properties that we studied and sometimes present slightly simplified versions All files of our prototype implementation and our case studies are available at http sapic gforge inria fr Example Typing Lemmas Automated Run Security API la PKCS 11 1 yes 51s Yubikey Protocol 3 no GJM protocol 0 yes 36s M dersheim s example locks inserts 0 no M dersheim s example embedded msr rules 0 yes 1s Security Device 1 yes 21s Needham Schroeder Lowe 1 y
111. ti t2 gt prems MDINo for a x lt ty to gt we have K lt t1 19 g 4 By Lemma 8 and Lemma 9 we have v y f o F lt ti ta gt Therefore v o F lt t4 t2 gt Using DEQ and DAPPL with the function symbols fst and snd we have vEn onw F ty and v y oy F t2 Therefore we chose the following transition oe EUM Oy B Pw In PT MN Sn 1 SNS is Pus On H1 E41 With 44 En yag Sw SMO e Pri Pri VE in t1 N Q FUH Q r F On 41 On and 44 Ly We define f as follows foli if i E Nm FO 4 7 ifm lt i lt n 1 n 1 ifi n Therefore Conditions I to 8 hold for i lt n 1 It is left to show that Conditions I to 8 hold for n holds since hide EF4 Ej F3 n and Em4i Fn 1 Fw since E44 K f Let 6 such that ri 0 R As established before we have 7 such that Nr p t By definition of P we have that statep 1 t p ginsts P 1 and that 6 0 7 Since T and p are induced by 0 0 induces 7 7 and the same p We have that Q 7 P 1rp r P yrT p and therefore Q r ep state 1 t Thus and since in t1 N Q ep statep t Paar Pw V in ti N Q UF Q r and S S 4 V In lt ti ta gt states U state t t Condition 4 holds Conditions and 5 hold trivially Case ri statese 5 Ack t1 t2 state 1 5 for some p t and t t2 M Since the msr
112. time password the Yubikey stores three additional pieces of information the public id pid that is used to identify the Yubikey a secret id secretid that is transmitted as part of the one time password and only known to the server and the Yubikey as well as the AES key k which is also shared with the server The following process Pyubikey models a single Yubikey as well as its initial configuration where an entry in the server s database for the public id pid is created This entry contains a tuple consisting of the Yubikey s secret id AES key and an initial counter value P yubikey v k v pid v secretid insert Server pid secretid k zero insert Yubikey pid zero one out pid PPlugin PButtonPress Here the processes Ppjygin and PButtonPress model the Yubikey being unplugged and plugged in again possibly on a different computer and the emission of the one time password We will only discuss PnButtonPress here When the user presses the button on the Yubikey the device outputs a one time password consisting of a counter tc the secret id secretid and additional randomness npr encrypted using the AES key k PButtonPress lock pid lookup Yubikey pid as tc in insert Yubikey pid tc one v nonce v npr event YubiPress pid secretid k tc out pid nonce senc secretid tc npr k unlock pid The one time password senc secretid tc np
113. ts in a similar way Application of substitutions are lifted to sets sequences and multisets as expected By abuse of notation we sometimes interpret sequences as sets or multisets the applied operators should make the implicit cast clear 3 A cryptographic pi calculus with explicit state 3 1 Syntax and informal semantics Our calculus is a variant of the applied pi calculus 2 In addition to the usual operators for concurrency replication communication and name creation it offers several constructs for reading and updating an explicit global state The grammar for processes is described in Figure I M N x y z E V p E PN n FN f M Mn f X of arity n P Q 0 P Q P vn P out M N P in M N P if M N then P else Q event F P FEF insert M N P delete M P lookup M as z in P else Q lock M P unlock M P L JA R P L R Ae F Figure 1 Syntax 0 denotes the terminal process P O is the parallel execution of processes P and Q and P the replication of P allowing an unbounded number of sessions in protocol executions The construct vn P binds the name n in P and models the generation of a fresh random value Processes out M N P and in M N P represent the output respectively input of message N on channel M Readers familiar with the applied pi calculus 2 may note that we opted for the possibility of pattern matching in the input construct rather than merel
114. tself this is not the case for the translation of the lookup operator i e it violates the well formedness condition from Definition Tamarin s con straint solving algorithm requires all rules with the exception of FRESH to be well formed We show however that under these specific conditions the solution procedure is still correct See Appendix B for the proof 6 2 Definition of the translation of trace formulas We can now define the translation for formulas Definition 14 Given a well formed trace formula p we define lo a gt and ly 5 o where a is defined in Figure HO The formula uses the actions of the generated rules to filter out executions that we wish to discard 14 state O Istate 01 Y Istate 01 Istate 01 r h F state_011 h state_011 h state_011 h state_011 h state_0111 k h state_0111 k h state_0111 k h Event NewKey h k state 01111 k h state_01111 k h Insert lt key h gt k state 011111 k h state 011111 k h Insert att h gt dec state 0111111 k h state_0111 k h Event NewKey h k state 01111 K h state 01111 K h Insert key h gt K state 011111 K h state_011111 k h Insert att h gt dec state O111111 K h state 0111111 k h state
115. tten alo r We call prems ri the premises a actions ri the actions and r conclusions ri the conclusions of the rule Definition 4 Labelled multiset rewriting system A labelled multiset rewriting system is a set of labelled multiset rewrite rules R such that each rule 4a gt r R satisfies the following conditions e l a r do not contain fresh names e r does not contain Fr facts A labelled multiset rewriting system is called well formed if additionally e for each l 4a gt r g ginsts l a r we have that N names r YFN C Npr vnames I N FN We define one distinguished rule FRESH which is the only rule allowed to have Fr facts on the right hand side FRESH gt Fr a fresh The semantics of the rules is defined by a labelled transition relation Definition 5 Labelled transition relation Given a multiset rewriting system R we define the labeled transition relation gt pC G x P G x G as S r S Vf Ifacts l U r if and only if Ja r p ginsts R U FRESH lfacts I C S and pfacts l C S Definition 6 Executions Given a multiset rewriting system R we define its set of executions as ezec R o Lo Ed Va i gj 0 lt tAg lt n Sita Si Fr a Sii 5 A Fr a The set of executions consists of transition sequences that respect freshness i e for a given name a the fact Fr a is only added once or in other words the rule FRESH is at most fired once for eac
116. utions For instance the label Eq M N will be used to indicate that we only consider executions in which M g N As we will see in the next section these restrictions will be encoded in the trace formula Example Figure Blillustrates the above translation by presenting the set of msr rules Pew omitting the rules in MD already shown in Figure 6 A graph representation of an example trace generated by the tamarin tool is depicted in Figure P Every box in this picture stands for the application of a multiset rewrite rule where the premises are at the top the conclusions at the bottom and the actions if any in the middle Every premise needs to have a matching conclusion visualized by the arrows to ensure the graph depicts a valid msr execution This is a simplification of the dependency graph representation tamarin uses to perform backward induction 26 Note that the machine notation for state predicates omits brackets in the position p and denotes the empty sequence by 0 We also note that in the current example statej j is persistent and can therefore be used multiple times as a premise As Fr facts are generated by the FRESH rule which has an empty premise and action we omit instances of FRESH and leave those premises but only those disconnected Remark 1 One may note that while for all other operators the translation produces well formed mul tiset rewriting rules as long as the process is well formed i
117. y binding the input to a variable x The process if M N then P else Q will execute P if M p N and Q otherwise The event construct is merely used for annotating processes and will be useful for stating security properties For readability we sometimes omit to write else Q when Q is 0 as well as trailing 0 processes The remaining constructs are used for manipulating state and are new compared to the applied pi calculus We offer two different mechanisms for state The first construct is functional and allows to associate a value to a key The construct insert M N binds the value N to a key M Successive inserts allow to change this binding The delete M operation simply undefines the mapping for the key M The lookup M as z in P else Q allows to retrieve the value associated to M binding it to the variable x in P If the mapping is undefined for M the process behaves as Q The lock and unlock constructs allow to gain exclusive access to a resource M This is essential for writing protocols where parallel processes may read and update a common memory We additionally offer another kind of global state in form of a multiset of ground facts as opposed to the previously introduced functional store This multiset can be altered using the construct L 4 A R P which tries to match each fact in the sequence L to facts in the current multiset and if successful adds the corresponding instance of facts R to the store The facts A are used as annotati
118. ypothesis and since E5 44 Zn 2 0 we have that Ey a FN ProtoNonce a g U Ej 1 lt j lt n 2 From the induction hypothesis and since no rule producing Out facts is applied between step m and step n 2 we have that zon z D o yf p Out t Uyzs 2i Y 3 Let f a fresh RepNonce a Uj lt lt n_2 Fj Since K t1 prems MDINo for o x ti we have K t g 5 5 By emma Sl sad ama we have vE 7 0 F t Therefore v o F t We chose the following transition DENS em a On S Tw On TEM Cie O4 RN Py On 41 Catia with Ent 41 En Sua S e x SM Pu Pu VE out ti t3 Q U Q v On on U z and Zug Ly for a fresh z We define f as follows foli ifie Ns FO 4 n ifm lt i lt n 1 n l ifi n Therefore Conditions I to hold for i lt n 1 It is left to show that Conditions I to 8 hold for n Condition 7 holds since hide E1 Em g Fi n and Emii En 1 g Fw since E41 K ti holds since 9 44 o U and therefore zova z D ew41 ton 2 D ou Y UF ta F g Out t Uses 2S Uf t9 by 4 f Out t UpenSe yt 49 By definition of P and P _ we have that Q ep state t Therefore and since out t1 t2 Q ep state t Pj 41 Pw V out t1 t2 Q Uf Q Yf and Sn 2g S44 V In a state Uf statep 1 t Out t2 holds Conditions and 3 hold t
119. ze complex injective correspondance properties M dersheim 22 proposed a language with support for sets together with an abstraction where all objects that belong to the same sets are identified His language which is an extension of the low level AVISPA intermediate format is compiled into Horn clauses that are then analyzed e g using ProVerif His approach is tightly linked to this particular abstraction limiting the scope of applicability M dersheim also discusses the need for a more high level specification level which we provide in this work There has also been work tailored to particular applications In 13 Delaune et al show by a dedicated hand proof that for analyzing PKCS 11 one may bound the message size Their analysis still requires to artificially bound the number of keys Similarly in spirit Delaune et al give a dedicated result for analyzing protocols based on the TPM and its registers However the number of reboots which reinitialize registers needs to be limited Guttman also extended the strand space model by adding support for state While the protocol execution is modeled using the classical strand spaces model state is modeled by a multiset of facts and manipulated by multiset rewrite rules The extended model has been used for analyzing by hand an optimistic contract signing protocol As of now protocol analysis in the strand space model with state has not been mechanized yet In the goal of relating differ

Download Pdf Manuals

Related Search

Related Contents

X7SBi 1.0.indb  i iBAQS S-FX リ リリースノ ート  rasaerba con conducente seduto tondeuse a conducteur assis ride  ez-Lap(イージーラップ)取扱説明書(保証書) − 特徴  Genius Traveler 8000  American DJ Fan-1000 User's Manual  Newstar LED-W040 flat panel wall mount  English catalogue GHL 2015 EN  MANUAL DEL USUARIO RECORTADORA DE  

Copyright © All rights reserved. Failed to retrieve file