Security protocol notation

In cryptography, security (engineering) protocol notation, also known as protocol narrations^[1] and Alice & Bob notation, is a way of expressing a protocol of correspondence between entities of a dynamic system, such as a computer network. In the context of a formal model, it allows reasoning about the properties of such a system.

The standard notation consists of a set of principals (traditionally named Alice, Bob, Charlie, and so on) who wish to communicate. They may have access to a server S, shared keys K, timestamps T, and can generate nonces N for authentication purposes.

A simple example might be the following:

A\rightarrow B:\{X\}_{{K_{{A,B}}}}

This states that Alice intends a message for Bob consisting of a plaintext X encrypted under shared key K_A,B.

Another example might be the following:

B\rightarrow A:\{N_{B}\}_{{K_{A}}}

This states that Bob intends a message for Alice consisting of a nonce N_B encrypted using public key of Alice.

A key with two subscripts, K_A,B, is a symmetric key shared by the two corresponding individuals. A key with one subscript, K_A, is the public key of the corresponding individual. A private key is represented as the inverse of the public key.

The notation specifies only the operation and not its semantics — for instance, private key encryption and signature are represented identically.

We can express more complicated protocols in such a fashion. See Kerberos as an example. Some sources refer to this notation as Kerberos Notation.^[2] Some authors consider the notation used by Steiner, Neuman, & Schiller^[3] as a notable reference. ^[4]

Several models exist to reason about security protocols in this way, one of which is BAN logic.

References

^ Briais, Sébastien; Nestmann, Uwe (2005). "A formal semantics for protocol narrations" (PDF). Lecture Notes in Computer Science. 3705: 163–181. Bibcode:2005LNCS.3705..163B. doi:10.1007/11580850_10. ISBN 978-3-540-30007-6.
^ Chappell, David (1999). "Exploring Kerberos, the Protocol for Distributed Security in Windows 2000". Microsoft Systems Journal. Archived from the original on 2017-08-15.
^ Steiner, J. G.; Neuman, B. C.; Schiller, J. I. (February 1988). "Kerberos: An Authentication Service for Open Network Systems" (PDF). Proceedings of the Winter 1988 Usenix Conference. Usenix. Berkeley, CA: USENIX Association. pp. 191–201. Retrieved 2009-06-10.
^ Davis, Don; Swick, Ralph (1989-03-17). Workstation Services and Kerberos Authentication at Project Athena (PS). p. 1. Retrieved 2009-06-10. …our notation follows Steiner, Neuman, & Schiller,…

[1] Briais, Sébastien; Nestmann, Uwe (2005). "A formal semantics for protocol narrations" (PDF). Lecture Notes in Computer Science. 3705: 163–181. Bibcode:2005LNCS.3705..163B. doi:10.1007/11580850_10. ISBN 978-3-540-30007-6.

[2] Chappell, David (1999). "Exploring Kerberos, the Protocol for Distributed Security in Windows 2000". Microsoft Systems Journal. Archived from the original on 2017-08-15.

[3] Steiner, J. G.; Neuman, B. C.; Schiller, J. I. (February 1988). "Kerberos: An Authentication Service for Open Network Systems" (PDF). Proceedings of the Winter 1988 Usenix Conference. Usenix. Berkeley, CA: USENIX Association. pp. 191–201. Retrieved 2009-06-10.

[4] Davis, Don; Swick, Ralph (1989-03-17). Workstation Services and Kerberos Authentication at Project Athena (PS). p. 1. Retrieved 2009-06-10. …our notation follows Steiner, Neuman, & Schiller,…

[1]

[2]

[3]

[4]