This protocol, first presented in [820] and corrected in [1162] attempts to counter the suppress-replay attack. It is an enhancement to Yahalom and is an excellent protocol.

(1)  Alice concatenates her name and a random number and sends it to Bob.

A,R_A

(2)  Bob concatenates Alice’s name, her random number, and a timestamp, and encrypts with the key he shares with Trent. He sends it to Trent along with his name and a new random number.

B,R_B,E_B(A,R_A,T_B)

(3)  Trent generates a random session key. Then he creates two messages. The first is Bob’s name, Alice’s random number, a random session key, and the timestamp, all encrypted with the key he shares with Alice. The second is Alice’s name, the session key, and the timestamp, all encrypted with the key he shares with Bob. He sends these both to Alice, along with Bob’s random number.

E_A(B,R_A,K,T_B),E_A(A,K,T_B),R_B

(4)  Alice decrypts the message encrypted with her key, extracts K, and confirms that R_A has the same value as it did in step (1). Alice sends Bob two messages. The first is the message received from Trent, encrypted with Bob’s key. The second is R_B, encrypted with the session key.

E_B(A,K,T_B),E_K(R_B)

(5)  Bob decrypts the message encrypted with his key, extracts K, and confirms that T_B and R_B have the same value they did in step (2).

Assuming both random numbers and the timestamp match, Alice and Bob are convinced of one another’s identity and share a secret key. Synchronized clocks are not required because the timestamp is only relative to Bob’s clock; Bob only checks the timestamp he generated himself.

One nice thing about this protocol is that Alice can use the message she received from Trent for subsequent authentication with Bob, within some predetermined time limit. Assume that Alice and Bob completed the above protocol, communicated, and then terminated the connection. Alice and Bob can reauthenticate in three steps, without having to rely on Trent.

(1)  Alice sends Bob the message Trent sent her in step (3) and a new random number.

E_B(A,K,T_B),R’_A

(2)  Bob sends Alice another new random number, and Alice’s new random number encrypted in their session key.

R’_B,E_K(R’_A)

(3)  Alice sends Bob his new random number, encrypted in their session key.

E_K(R’_B)

The new random numbers prevent replay attacks.

DASS

The Distributed Authentication Security Service (DASS) protocols, developed at Digital Equipment Corporation, also provide for mutual authentication and key exchange [604,1519,1518]. Unlike the previous protocols, DASS uses both public-key and symmetric cryptography. Alice and Bob each have a private key. Trent has signed copies of their public keys.

(1)  Alice sends a message to Trent, consisting of Bob’s name.

B

(2)  Trent sends Alice Bob’s public key, K_B, signed with Trent’s private key, T. The signed message includes Bob’s name.

S_T(B,K_B)

(3)  Alice verifies Trent’s signature to confirm that the key she received is actually Bob’s public key. She generates a random session key, and a random public-key/private-key key pair: K_P. She encrypts a timestamp with K. Then she signs a key lifetime, L, her name, and K_P with her private key, KA. Finally, she encrypts K with Bob’s public key, and signs it with K_P. She sends all of this to Bob.

E_K(T_A),S_KA(L,A,K_P),S_KP(E_KB(K))

(4)  Bob sends a message to Trent (this may be a different Trent), consisting of Alice’s name.

A

(5)  Trent sends Bob Alice’s public key, signed in Trent’s private key. The signed message includes Alice’s name.

S_T(A,K_A)

(6)  Bob verifies Trent’s signature to confirm that the key he received is actually Alice’s public key. He then verifies Alice’s signature and recovers K_P. He verifies the signature and uses his private key to recover K. Then he decrypts T_A to make sure this is a current message.

(7)  If mutual authentication is required, Bob encrypts a new timestamp with K, and sends it to Alice.

E_K(T_B)

(8)  Alice decrypts T_B with K to make sure that the message is current.

SPX, a product by DEC, is based on DASS. Additional information can be found in [34].