Selecting Theories and Nonce Generation for Recursive Protocols

In recent years, formal methods have been developed to analyze and verify cryptographic protocols. We will focus on protocols that rely on iteration or recursion. These protocols typically use special security tokens - such as numbers used only once, called nonces, or keys generated by a principal - to achieve their security assertions. The recursion depth of the computations in such protocols and thus the number of fresh tokens occurring in a run of a protocol is not explicitly bounded by the protocol's description. Therefore, we need a mechanism to provide the protocol's principals with the ability to generate an unbounded number of fresh tokens. In this report we will extend the model of selecting theories introduced by Truderung - in this model recursive protocols can be analyzed in the presence of a Dolev-Yao intruder. We will present an extended model that allows the principals to generate fresh tokens, and we will show decidability with respect to a bounded number of sessions. In the proof, attacks on such protocols will be represented by a special graph structure introduced by Truderung called ADAG; we will prove our decidability result by bounding the size of ADAGs. In the protocol model and in the ADAGs the modeling of fresh tokens will be based on an infinite set of constants in the signature