A proof of revised Yahalom protocol in the Bellare and Rogaway (1993) model

Although the Yahalom protocol, proposed by Burrows, Abadi, and Needham in 1990, is one of the most prominent key establishment protocols analysed by researchers from the computer security community (using automated proof tools), a simplified version of the protocol is only recently proven secure by Backes and Pfitzmann [(2006) On the Cryptographic Key Secrecy of the Strengthened Yahalorn Protocol. Proc. IFIP SEC 2006] in their cryptographic library framework. We present a protocol for key establishment that is closely based on the Yahalorn protocol. We then present a security proof in the Bellare, M. and Rogaway, P. [(1993a). Entity Authentication and Key Distribution. Proc. of CRYPTO 1993, Santa Barbara, CA, August 22-26, LNCS, Vol. 773, pp. 110-125. Springer-Verlag, Berlin] model and the random oracle model. We also observe that no partnering mechanism is specified within the Yahalom protocol. We then present a brief discussion on the role and the possible construct of session identifiers (SlDs) as a form of partnering mechanism, which allows the right session key to be identified in concurrent protocol executions. We then recommend that SlDs should be included within protocol specification rather than consider SIDs as artefacts in protocol proof.