Paper 2011/406

Composition Theorems Without Pre-Established Session Identifiers

Ralf Kuesters and Max Tuengerthal


Canetti's universal composition theorem and the joint state composition theorems by Canetti and Rabin are useful and widely employed tools for the modular design and analysis of cryptographic protocols. However, these theorems assume that parties participating in a protocol session have pre-established a unique session ID (SID). While the use of such SIDs is a good design principle, existing protocols, in particular real-world security protocols, typically do not use pre-established SIDs, at least not explicitly and not in the particular way stipulated by the theorems. As a result, the composition theorems cannot be applied for analyzing such protocols in a modular and faithful way. In this paper, we therefore present universal and joint state composition theorems which do not assume pre-established SIDs. In our joint state composition theorem, the joint state is an ideal functionality which supports several cryptographic operations, including public-key encryption, (authenticated and unauthenticated) symmetric encryption, MACs, digital signatures, and key derivation. This functionality has recently been proposed by Küsters and Tuengerthal and has been shown to be realizable under standard cryptographic assumptions and for a reasonable class of environments. We demonstrate the usefulness of our composition theorems by several case studies on real-world security protocols, including IEEE 802.11i, SSL/TLS, SSH, IPsec, and EAP-PSK. While our applications focus on real-world security protocols, our theorems, models, and techniques should be useful beyond this domain.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
universal composition theoremscomposition with joint statereal-world security protocols
Contact author(s)
tuengerthal @ uni-trier de
2011-08-11: revised
2011-07-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ralf Kuesters and Max Tuengerthal},
      title = {Composition Theorems Without Pre-Established Session Identifiers},
      howpublished = {Cryptology ePrint Archive, Paper 2011/406},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.