Expose you to well-known or typical flaws found in these protocols.
| A,B | principals |
| S | trusted server |
| Z | intruder |
| M | message |
| Kab | key shared by A and B |
| {M}k | encryption of message M with key K |
| Na | nonce generated by A |
| A->B: X,Y | A sends to B message with X, Y components |
| A->Z(B): M | Z intercepts M sent from A to B |
| Z(A)->B: M | Z masquerading as A sends M to B |
Authentication goal: To prove A and B's identity with each other.
Key exchange goal: A and B will use a shared session key.
Nonce: A number used only once (a sequence #, large random #, timestamp, etc.)
Ref: Schneider Section 3.3 (pp 58-59)
The Needham-Schroeder protocol utilizes symmetric cryptography and a trusted server.
1) A->S: A, B, Na
"I am Alice and here is a nonce for future exchanges, and I would like to talk with Bob." Alice provides a random number Na.
2) S->A: {Na, B, Kab, {Kab, A}Kbs}Kas
The trusted server creates a session key Kab for Alice to use with Bob, and encrypts the return message with the secret key the server shares with Alice. The server includes Bob since an intruder could have substituted his name in for Bob and Alice would get from the server a key not for Bob, but for the intruder. This way, Alice has a way of verifying that the server received her request of Bob. Note that Alice cannot read {Kab, A}Kbs- she just sees bits to send to Bob (this double encryption has fallen under criticism!)
3) A->B: {Kab, A}Kbs
Alice sends the server created message to Bob. He decrypts the message, retrieving Kab. Now we have achieved the key exchange part of the protocol since a shared session key has been exchanged.
4) B->A: {Nb}Kab
Now for a challenge-response type message, Bob generates a nonce and encrypts it with their shared key, sending it to Alice. Note that Alice and Bob must agree a priori what exactly Alice does with the nonce, however this could be common knowledge (in the protocol, etc.)
5) A->B: {Nb - 1}Kab
Alice responds with the appropriate response, Nb - 1,
which Bob verifies. Having successfully authenticated with each other, A
and B can use Kab to communicate in subsequent communications.
Ref: D.E. Denning, G.M. Sacco. Timestamps in Key Distribution Protocols. Communication of the ACM, August 1981
Ref: Schneider Section 3.3 (pp 63)
Assumption in Needham-Schroeder protocol is that session keys are used only once and then discarded. However, if this is not the case, then old session keys become valuable and subject to replay attack. Thus, the Denning-Sacco attack assumes an attacker can break into one of the principle's computers and get hold of an old session key, Kold, to use in the replay attack.
PROBLEM: An intruder can trick Bob by replaying a message in step 3 of the protocol, and Bob will just think they are continuing an old conversation with Alice- they cannot tell the difference. Explicitly:
3) Z(A)->B: {Kold, A}Kbs
4) B->Z(A): {Nb}Kold
5) Z(A)->B: {Nb - 1}Kold
In this manner, an intruder could replay a previous message many times, like "transfer 10K to Doug's account", etc.
FIX: Use a timestamp, T, in steps 2 and 3 of the Needham-Schroeder protocol:
1) A->S: A, B
2) S->A: {B, Kab, T, {Kab, A, T}Kbs}Kas
3) A->B: {Kab, A, T}Kbs
Timestamping, however, requires a secure and accurate system clock a difficult task requiring that the local clock's difference is bounded by normal clock skew and the time difference created by the required time of propagation:
| local clock - T | < Delta t + tprop
Since the steps 4 and 5 are used to demonstrate that both parties are indeed there, these steps could be dropped if timestamping is used. Let J be a new nonce that is standing in for the old T:
-1) A->B: A
0) B->A: {A, J}Kbs
1) A->S: A, B, Na, {A, J}Kbs
2) S->A: {Na, B, Kab, {Kab, A, J}Kbs}Kas
3) A->B: {Kab, A, J}Kbs
Note this provides the required authentication in steps -1 and 0.
PROBLEMS: There still exist some problems with this protocol that can be exploited:
Crypto-level: nonces [Boyd90] - we note that the difference between steps 4 and 5 is 1 bit; this can be analyzed and exploited.
Public-key protocol: interleaved runs [Lowe96] - years later, exploitations are still being discovered and flaws are pointed out; "Are we uneasy yet?"
NOTE: Needham-Schroder's fix to their own protocol is essentially the same as the Otway-Rees protocol, and was published in the same issue of Operating Systems Review!
Ref: Schneider Section 3.3 (pp 59-60)
Published in the same journal that the Needham-Schroeder fix was published. The Otway-Rees protocol was inspired by Needham's creed "a suspicious party should always issue a challenge." The protocol similarly uses symmetric cryptography, does not utilize a timestamp and consists of only 4 steps:
1) A->B: M, A, B, {Na, M, A, B}Kas
Alice sends to Bob her name, Bob's name, some M and a nonce, encrypted with the key the trusted server shares with Alice. Also sent to Bob is her name, Bob's name and M. The encrypted part of the message will be sent to the server.
2) B->S: M, A, B, {Na, M, A, B}Kas, {Nb, M, A, B}Kbs
Bob sends to the server the encrypted part of the last message from Alice, his name, Alice's name and M. Also sent are a new nonce, M, A and B, encrypted with the key the trusted server shares with Bob.
3) S->B: M, {Na, Kab}Kas, {Nb, Kab}Kbs
The trusted server will create a session key for Bob and Alice. This session key along with Alice's nonce is encrypted with the Alice/server shared key, and the session key along with Bob's nonce is encrypted with the Bob/server shared key. These along with M are sent to Bob.
4) B->A: M, {Na, Kab}Kas
Bob will extract Kab, and send M and the last encrypted part to Alice, who will also extract Kab. Both parties can verify that their nonce's have not been changed, and now Alice and Bob are convinced of their identity (authentication) and they also have a shared session key with which to communicate (key-exchange).
PROBLEM: We may note 2 redundancies in the protocol:
1) Nonce M is not really needed. (We will look at this next week.)
2) In step 2, {Nb, M, A, B}Kbs does not need to be encrypted.
This is an advantage of formal analysis of protocols- we can discover bugs as well as spotting redundancies that may well exist in the protocol.
FLAW: Type attack
Example:
RUN 1:
1) A->B: 007, A, B, {Na, 007, A, B}Kas
1') Z(A)->B: 008, A, B, garbage
2) B->S: 008, A, B, garbage, {Nb, 008, A, B}Kbs
3) S rejects B's message
RUN 2:
A->B: 008, A, B, {Na, 008, A, B}Kas
Z(B)->S: 008, A, B, {Na, 008, A, B}Kas, {Nb, 008, A, B}Kbs
S->Z(B): 008, {Na Kab}Kas, {Nb, Kab}Kbs
Z(B)->A: 008, {Na, Kab}Kas
The key exchange failed, but can be used to spoof authentication.
Ref: Schneider Section 3.3 (pp 56-57)
This protocol is probably the simplest protocol utilizing a trusted server. The assumption that is made is that Alice is the party to generate the session key (rather than the trusted server.)
We are basically saying, "use this key to communicate with me."
1) A->S: A, {Ta, B Kab,}Kab
2) S->B: {Ts, A, Kab}Kab
The timestamps Ta and Ts are used for freshness.
FLAWS:
We do have some weaknesses associated with this protocol.
An intruder can use S as a "timestamp oracle" and run the protocol continuously in order to gain information:
1) A->S: A, {Ta, B, Kab}Kas
2) S->B: {Ts, A, Kab}Kbs
1') Z(B)->S: B, {Ts, A, Kab}Kbs
2') S->Z(A): {Ts', B, Kab}Kas
1'') Z(A)->S: A, {Ts', B, Kab}Kas
2'') S->Z(B): {Ts'', A, Kab}Kbs
With this sequence of messages, now the intruder Z can replay appropriate messages to Alice and Bob:
2''') Z(S)->A: {Ts', B, Kab}Kas
2''') Z(S)->B: {Ts'', A, Kab}Kbs
We have only succeeded in spoofing authentication, but this in itself is a significant advantage to an attacker- think of a smart card that is used exclusively for authentication!