# Needham–Schroeder (protocol)

## Foreword

This name is used for both symmetrical (using a trusted third party) and asymmetrical schemes of authentication and session key generation. They were invented by M.Schroeder and R.Needham in 1978.

## Symmetric version

### Description

This protocol is used for a mutual authentication and shared secret key generation for establishing a secure connection with the use of trusted third party. Later this protocol became a base for a range of symmetric authentication protocols, in particular Kerberos.

### Setup

The protocol is used by two users ${\displaystyle A}$ and ${\displaystyle B}$ and a trusted party ${\displaystyle KDC}$ (Key Generator Center), which has shared symmetric keys with users (${\displaystyle K_{AC}}$ and ${\displaystyle K_{BC}}$ respectively).

### Work

1. ${\displaystyle A}$ sends a plaintext information about the requested connection to the trusted party: his ID, ${\displaystyle B}$'s ID and a random number ${\displaystyle R_{A}}$:
${\displaystyle A: [A,B,R_A]\to KDC}$
2. ${\displaystyle KDC}$ generates a session key ${\displaystyle k}$ and forms a package for ${\displaystyle A}$, which contains the random ${\displaystyle R_{A}}$, generated by ${\displaystyle A}$, ${\displaystyle B}$'s IS, session key ${\displaystyle k}$ and a package for ${\displaystyle B}$: a session key and ${\displaystyle A}$'s ID, encrypted with ${\displaystyle K_{BC}}$. KDC encrypt the whole package with a key, shared between him and ${\displaystyle A}$ and sends it to ${\displaystyle A}$:
${\displaystyle KDC: E_{K_{AC}}(R_A, B, k, E_{K_{BC}}(K,A))\to A}$
3. ${\displaystyle A}$ decrypts the package and checks ${\displaystyle R_{A}}$ and ${\displaystyle B}$'s ID. This makes impossible for malefactor to spoof ${\displaystyle KDC}$ or impersonate ${\displaystyle B}$, by changing the recepient ID in ${\displaystyle A}$'s first message. Then ${\displaystyle A}$ resends to ${\displaystyle B}$ his part of the package:
${\displaystyle A: E_{K_{BC}}(K,A)\to B}$
4. Having decrypted the message, ${\displaystyle B}$ discovers the session key and interlocutor's ID. After that the checking happens: ${\displaystyle B}$ generates a random ${\displaystyle R_{B}}$ and sends it, encrypted with a session key, to ${\displaystyle A}$:
${\displaystyle B: E_k(R_B)\to A}$
5. ${\displaystyle A}$ decrypts a message and sends to ${\displaystyle B}$ the confirmation of the successful session establishment: ${\displaystyle R_{B}}$, decreased by 1 and encrypted with the session key:
${\displaystyle A: E_k(R_B-1)\to B}$

## Asymmetric version

### Description

This protocol version uses asymmetric cryptography, which means that shared secrets between users and a trusted third party are not needed. It allows users to discover each others's public keys and perform a mutual authentication of each other and the third party.

### Setup

Two users participate the process: ${\displaystyle A,B}$ and also a trusted key generator center: ${\displaystyle KDC}$. All of them have public/private key pairs: ${\displaystyle Kp_A, Ks_A, Kp_B, Ks_B, Kp_C, Ks_C}$ respectively. ${\displaystyle KDC}$ knows public keys of the users and users know ${\displaystyle KDC}$'s public key.

### Work

1. ${\displaystyle A}$ sends ${\displaystyle KDC}$ a request for establishing a secure messaging channel with ${\displaystyle B}$:
${\displaystyle A: [A,B]\to KDC}$
2. ${\displaystyle KDC}$ sends to ${\displaystyle A}$ a message with ${\displaystyle B}$'s public key and ${\displaystyle A}$'s ID, signed with his digital signature (encrypted with a secret key):
${\displaystyle KDC: E_{Ks_C}(Kp_B,A)\to A}$
3. ${\displaystyle A}$ verifies ${\displaystyle KDC}$ (by decrypting the message with ${\displaystyle KDC}$'s public key) and gets ${\displaystyle B}$ public key. After that ${\displaystyle A}$ forms a package for ${\displaystyle B}$: ${\displaystyle A}$'s ID and a random number ${\displaystyle R_{A}}$, encrypts it with ${\displaystyle B}$'s public key and sends to ${\displaystyle B}$:
${\displaystyle A: E_{Kp_B}(A, R_A)\to B}$
4. ${\displaystyle B}$ decrypts the package and finds out ${\displaystyle A}$'s desire to start communication. Then ${\displaystyle B}$ makes a similar request for ${\displaystyle A}$'s public key:
${\displaystyle B: [B,A]\to KDC}$
5. ${\displaystyle KDC}$ sends to ${\displaystyle B}$ a signed ${\displaystyle A}$'s public key:
${\displaystyle KDC: E_{Ks_C}(Kp_A, B)\to B}$
6. Now all the participants know public keys of each other. They need to authenticate and make sure that the connection is set up correctly. ${\displaystyle B}$ generates a random number ${\displaystyle R_{B}}$ and sends it and ${\displaystyle R_{A}}$, he got earlier, to ${\displaystyle A}$ in encrypted form:
${\displaystyle B: E_{Kp_A}(R_B, R_A)\to A}$
7. ${\displaystyle A}$ decrypts ${\displaystyle B}$'s package and checks ${\displaystyle R_{A}}$. If everything is all right, ${\displaystyle A}$ encrypts ${\displaystyle R_{B}}$ with ${\displaystyle B}$'s public key and sends back to ${\displaystyle B}$:
${\displaystyle A: E_{Kp_B}(R_B)\to B}$

## References

В. Мао Современная криптография: теория и практика. — "Вильямс", 2005. — С.76-84 — ISBN 5-8459-0847-7

Roger M. Needham, Michael D. Schroeder Using encryption for authentication in large networks of computers. — Commun. ACM. — New York, NY, USA: ACM, 1978. — Vol. 21, fasc. 12. — P. 993—999.

Bruce Schneier Applied Cryptography. — Wiley, 1996. — pp. 47 et seq. — ISBN 978-0-471-11709-4.