A Computational Analysis of the Needham Schroder Lowe Protocol

The Needham-Schroeder protocol and its repaired due to Lowe are the main test cases used by symbolic methods for cryptographic protocol analysis. In this paper we proved the first \textit{computational} analysis of the protocol. We start by translating Lowe's attack against the original protocol into the computational framework that we use in our analysis. Then we prove that the repaired protocol may not be secure, even when the encryption scheme that is used in its implementation satisfies indistinguishability under chosen-plaintext attack. This shows that symbolic security analysis is not sound for protocols that use this kind of encryption. Our main result is to prove that the Needham-Schroeder-Lowe protocol is secure if it is implemented with an encryption scheme that satisfies the stronger notion of indistinguishability under chosen-ciphertext attack.