Computer Security lecture notes Copyright © 2004 Mark Dermot Ryan
The University of Birmingham
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License,

Secure protocols

This lecture is about authentication and key exchange protocols. Alice and Bob want to communicate with each other. But first, they need to
There have been several proposed protocols, and the topic has turned out to be very subtle. For example, one protocol proposed in 1978 was thought correct for nearly 20 years, until a flaw was discovered in 1995 (see below).  Nevertheless, as an attacker you have a much better chance of breaking the protocol (i.e. the way the crypto is used) than breaking the crypto itself.

The protocols may be based on symmetric-key or public-key crypto. In all cases, the authentication part of the protocol involves a trusted third party, Trent. We look at attacks on the protocols, and their fixes. None of the attacks involve breaking the crypto; they all exploit weaknesses in the protocol. We assume the following powers for an attacker Mallory:
What is a protocol? Generally, it's an agreed way, or convention, for several parties to achieve a goal. In this context, it fixes the number, order and format of messages between two or more (typically three: A, B, T), in order to achieve authentication and key exchange between A,B. The rules of the protocol are known to all (including the intruder).

Protocols using symmetric key encryption

Alice and Bob use a trusted key server Trent to establish a secret key for them to use. We assume that A and B each share a secret key with Trent, so that they can communicate securely (i.e. privately and authentically) with him. A design principle is that Trent should not be expected to maintain state; we have to imagine he gets hundreds of requests per second for keys, and doesn't keep records. The protocol should try to minimise the load on Trent.

Protocol 1

  1. Alice requests from Trent a session key to communicate with Bob.
  2. Trent generates a random session key. He encrypts two copies of it: one with Alice's key, and one with Bob's key. He sends both copies to Alice.
  3. Alice decrypts her copy of the session key, and sends Bob's copy to him.
  4. Bob decrypts his copy of the session key.
  5. Alice and Bob use this key to communicate securely.

1.

A
 --A,B--> T
2.

A
 <--{K}A, {K}B--
 T
3.
 B
 <--{K}B-- A


Attack. (Man in the middle.)

1

A
 --A,B--> M
 --M,A-->
 T
2.2



M
 <--{K1}M, {K1}A-- T
3.1



M
 --M,B--> T
3.2



M
 <--{K2}M, {K2}B-- T
1.2

A <--{K1}A, {K2}B-- M(T)

1,3
 B
 <--{K2}B-- A




This is a legitimate attack according to our ground rules, since M can intercept the message to T and fake the reply. T is very simple: it just accepts arguments  X,Y and generates a new key K, returning {K}X, {K}Y.

A and B are now ready to communicate, but they have been duped into using different keys. M stands in the middle, converting the keys and reading the messages.

A
 -- {m}K1 --> M
 -- {m}K2 --> B
A
 <-- {m}K1 -- M
 <-- {m}K2 -- B


Other attacks on the protocol include replay attacks: Mallory can replay messages from old runs of the protocol. For example, if M has discovered a key K through A or B's carelessness, and has previously recorded the message {K}A, {K}B, then he can impersonate T and replay the message
{K}A, {K}B, thus convincing A and B to use a key that he knows.

Protocol 2. [R. Needham, M. Schröder, 1978]

1.

A
 -- A,B,NA --> T
2.

A
 <--{NA, B, K, {K, A}B }A--
 T
3.
 B
 <-- {K, A}B -- A

4.
 B
 -- {NB}K -->
 A

5.
 B
 <-- {NB-1}K --
 A


This protocol uses nonces (fresh random numbers) NA and NB to avoid replay attacks. T's message includes the names of the participants who are intended to use they key, preventing M from tricking other people into using it. It also encrypts the ticket for B with A's key, preventing M from tampering with it.

Vulnerability of Needham-Schröder symmetric key protocol

M might get hold of a previously used session key K2, through A's and B's carelessness much later or through off-line cryptanalysis. He has also previously stored the corresponding ticket, {K2, A}B. Mallory can now trick Bob, by impersonating Alice.

1.

A
 -- A,B,NA --> T
2.

A
 <--{NA, B, K, {K, A}B }A--
 T
3.
 B
 <-- {K2, A}B -- M(A)

4.
 B
 -- {NB}K2 -->
 M(A)

5.
 B
 <-- {NB-1}K2 --
 M(A)


B thinks he is talking to A, but actually he is talking to M.

Protocol 3

Like Needham-Schröder, but using timestamps to prevent replay attacks like the one above. The authentication system Kerberos uses this, However, timestamps come with their own problems: how to synchronise clocks, what delays should be allowed to account for network delays, etc.

Protocol 4 [Needham-Schröder-Mullender, 1987]

It adds some new bits (in red) to Needham-Schröder.

0.1
 B
 <-- A --
 A

0.2
 B
 -- {A, N'B }B -->
 A

1.

A
 -- A,B,NA, {A, N'B}B --> T
2.

A
 <--{NA, B, K, {K, A, N'B}B }A--
 T
3.
 B
 <-- {K, A, N'B}B -- A

4.
 B
 -- {NB}K -->
 A

5.
 B
 <-- {NB - 1}K --
 A


Probably messages 4 and 5 are not necessary, since N'B already prevents M from inserting a replay key (observation by Alan Sexton).
 

Protocols using public-key encryption

The obvious protocol is this one:
  1. A sends B her public key.
  2. B sends A his public key.
  3. A sends a message to B, encrypting it with B's public key.  B decrypts it.
  4. B sends a message to A, encrypting it with A's public key.  A decrypts it.
As already observed, tt is easier to find slip-ups in the way public-key cryptography is used, than to try to break the cryptography. Public-key cryptography is subtle, and it's very easy to implement a protocol which doesn't use it properly.

Man-in-the-middle attack

  1. A sends B her public key. Mallory intercepts this key and sends B his own one instead.
  2. B sends A his public key. M again intercepts it and sends A his own one instead.
  3. A sends a message to B, encrypting it with what A thinks is B's public key. M intercepts it. Since it is encrypted with his own key, he decrypts it using his private key, re-encrypts it with B's public key, and sends it on to B. B decrypts it.
  4. B sends a message to A, encrypting it with what B thinks is A's public key. M intercepts it. Since it is encrypted with his own key, he decrypts it using his private key, re-encrypts it with A's public key, and sends it on to A. A decrypts it.

The interlock protocol avoids this attack:
  1. A sends B her public key
  2. B sends A his public key
  3. A encrypts her message using B's key, and sends half of the encrypted message (e.g., the odd numbered bits) to B.
  4. B encrypts his message using A's key, and sends half of the encrypted message to A.
  5. A sends the second half of the encrypted message (the even numbered bits) to B
  6. B puts the two halves together, decrypts it. He sends the other half of his encrypted message to A.
  7. A puts the two halves of B's message together, and decrypts them.
But this protocol is subject to a replay attack....

A
 --KA-->
 M


A
 <--KM--
 M


A
 --b1-->
 M


A
 <--b2--
 M


A
 --b3-->
 M

b1b3 = {mA}KM. Now M forms b5 and b6 such that b5b6={mA}KB.
A
 <--b4--
 M
 --KM-->
 B


M
 <--KB--
 B


M
 --b5-->
 B


M
 <--b7--
 B


M
 --b6-->
 B


M
 <--b8--
 B

Two runs of the protocol have taken place. The one between A and M is OK. A knows he is talking to M. But in the one between M and B, B is duped. He thinks he's talking to A. He thinks KM is A's public key, and the messages he gets, b5b6, decrypt to mA, a message from A.

Needham-Schöder public key authentication protocol

This protocol was proposed in 1978, and is quite separate from the secret key protocol described in the previous section. It aims to authenticate A and B to each other, and to provide them with a shared secret which they can use to form a session key. NA and NB are "nonces": random numbers made up by A and B, respectively. We assume that A and B already know (correctly) each other's public key. (The original version of the protocol included some steps in which they obtained this from a trusted source, encrypted with the symmetric key of that source.)

1.
 A
 --{NA,A}KB-->
 B
2.
 A
 <--{NA,NB}KA--
 B
3.
 A
 --{NB}KB-->
 B

At the end of this protocol, it is claimed that A and B are certain they are talking to each other, and the pair of nonces is known only to them. Indeed, the authors used a logic called BAN logic to prove the protocol correct.

However, in 1995 Gavin Lowe [5] found a man-in-middle attack, using the FDR model checking tool. In the following, the intercepter M participates in two runs of the protocol, one with A and one with B.

1.1
 A
 --{NA,A}KM-->
 M


2.1

M
 --{NA,A}KB-->
 B
    To B, this looks like it came from A
2.2

M
 <--{NA,NB}KA--
 B
1.2
 A
 <--{NA,NB}KA--
 M


1.3
 A
 --{NB}KM-->
 M


2.3

M
 --{NB}KB-->
 B

A knows she is talking to M. But B thinks he is talking to A. Thus, B is duped.

It is easy to fix the protocol. Just replace message 2: {NA,NB}KA by: {NA,NB,B}KA. This prevents M from using this in message 1.2.

Other ways of breaking the way RSA is used [3].

References

[1] Bruce Schneier, Applied Cryptography. Second Edition, J. Wiley and Sons, 1996.
[2] William Stallings, Cryptography and Network Security, Principles and Practice,  Prentice Hall, 1999.
[3] PGP Attack Faq describes some attacks against the way RSA is used.
[4] The PKI page contains links to various sites and documents which are related to Public Key Infrastructure.
[5] Gavin Lowe, Breaking and Fixing the Needham-Schroeder Public-Key Protocol using FDR, 1996.