# Methodology of Testing the Security of Cryptographic Protocols Using the CMMTree Framework
## 3 Needham Schroeder Public Key Protocol  
In recent decades, numerous communication protocols have been proposed and developed. Security or cryptographic protocols are part of large and complex communication protocols that aim to authenticate, establish, or exchange symmetric keys. The most known and tested security protocol is probably the Needham Schroeder Public Key protocol [7]. It is well-known that its original version is not a perfect protocol, and it can be broken. Nevertheless, in our opinion, it is very useful. It is like the fruit flies used in countless studies by biologists, geneticists, and other scientists.  
This protocol is the best research example because it shows the main ideas of security protocols. It allows tracking the process and progress of protocol breaking, which is very useful in testing solutions for protocol analysis.  
The NSPK protocol aims for mutual authentication with public keys.  
\[\begin{array}{llll}\alpha_{1}&A\to B:&\langle N_{A},i(A)\rangle_{K_{B}},\\ \alpha_{2}&B\to A:&\langle N_{A},N_{B}\rangle_{K_{A}},\\ \alpha_{3}&A\to B:&\langle N_{B}\rangle_{K_{B}}.\end{array}\]  
In this notation:  
* \(\langle M\rangle_{K}\) means the message \(M\) encrypted by key \(K\), for example, \(\langle N_{A},i(A)\rangle_{K_{B}}\) means the message composed by nonce \(N_{A}\) and identifier \(i(A)\) encrypted by key \(K_{B}\).
* \(A\) and \(B\) mean the honest protocol participants.
* \(i(u)\) means the text identifier of the user \(u\), for example, \(i(A)\) means user \(A\)'s identifier.  
\(N_{u}\) means the nonce generated by user \(u\), for example, \(N(A)\) means the nonce generated by user \(A\).
* \(K_{u}\) means a public key of user \(u\), for example, \(K_{A}\) means a public key of user \(A\).  
During this protocol, users \(A\) and \(B\) authenticate to each other. Authentication takes place with the use of users' nonces.  
The NSPK protocol was widely used and acknowledged as secure for almost two decades. In 1995, [PERSON] found an attack upon this protocol [33]. This attack involves two concurrent executions, during which the Intruder tries to cheat honest users. The attack upon the NSPK protocol can be represented in Alice-Bob notation:  
\[\begin{array}{ccc}\alpha_{1}&A\to I:&\langle N_{A},i(A)\rangle_{K_{I}}\\ \beta_{1}&I(A)\to B:&\langle N_{A},i(A)\rangle_{K_{B}},\\ \beta_{2}&B\to I(A):&\langle N_{A},N_{B}\rangle_{K_{A}},\\ \alpha_{2}&I\to A:&\langle N_{A},N_{B}\rangle_{K_{A}},\\ \alpha_{3}&A\to I:&\langle N_{B}\rangle_{K_{I}},\\ \beta_{3}&I(A)\to B:&\langle N_{B}\rangle_{K_{B}}.\end{array}\]  
We added to the earlier notation the following designations that refer to the Intruder's role in the protocol:  
* \(I\) means the Intruder that occurs as himself;
* \(I(u)\) means the Intruder that impersonates user \(u\) during the protocol's execution, for example, \(I(A)\) means that the Intruder impersonates user \(A\) during communication.  
In this attack, the Intruder sends during \(\beta\) execution messages received from user \(A\) in \(\alpha\) execution. The Intruder impersonates user \(A\) in \(\beta\) execution. User \(B\) thinks he is communicating with user \(A\), and both users are unaware of the dishonest user between them.  
Next, in [34], [PERSON] proposed a corrected version of the NSPK protocol. The author suggested that an additional identifier in the second step would prevent honest users from engaging in dishonest activities. The structure of the corrected second step in Alice-Bob notation is as follows:  
\[\alpha_{2}\quad B\to A:\quad\langle N_{A},N_{B},i(B)\rangle_{K_{A}}.\]  
To date, no documented attacks have been reported against the revised iteration of the NSPK protocol.