Denning-Sacco

This protocol also uses public-key cryptography [461]. Trent keeps a database of everyone’s public keys.

(1)  Alice sends a message to Trent with her identity and Bob’s identity:

A,B

(2)  Trent sends Alice Bob’s public key, K_B, signed with Trent’s private key, T. Trent also sends Alice her own public key, K_A, signed with his private key.

S_T(B,K_B),S_T(A,K_A)

(3)  Alice sends Bob a random session key and a timestamp, signed in her private key and encrypted in Bob’s public key, along with both signed public keys.

E_B(S_A(K,T_A)),S_T(B,K_B),S_T(A,K_A)

(4)  Bob decrypts Alice’s message with his private key and then verifies Alice’s signature with her public key. He checks to make sure that the timestamp is still valid.

At this point both Alice and Bob have K, and can communicate securely.

This looks good, but it isn’t. After completing the protocol with Alice, Bob can then masquerade as Alice [5]. Watch:

(1)  Bob sends his name and Carol’s name to Trent

B,C

(2)  Trent sends Bob both Bob’s and Carol’s signed public keys.

S_T(B,K_B),S_T(C,K_C)

(3)  Bob sends Carol the signed session key and timestamp he previously received from Alice, encrypted with Carol’s public key, along with Alice’s certificate and Carol’s certificate.

E_C(S_A(K,T_A)),S_T(A,K_A),S_T(C,K_C)

(4)  Carol decrypts Alice’s message with her private key and then verifies Alice’s signature with her public key. She checks to make sure that the timestamp is still valid.

Carol now thinks she is talking to Alice; Bob has successfully fooled her. In fact, Bob can fool everyone on the network until the timestamp expires.

This is easy to fix. Add the names inside the encrypted message in step (3):

E_B(S_A(A,B,K,T_A)),S_T(A,K_A),S_T(B,K_B)

Now Bob can’t replay the old message to Carol, because it is clearly meant for communication between Alice and Bob.

Woo-Lam

This protocol also uses public-key cryptography [1610,1611]:

(1)  Alice sends a message to Trent with her identity and Bob’s identity:

A,B

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

S_T(K_B)

(3)  Alice verifies Trent’s signature. Then she sends Bob her name and a random number, encrypted with Bob’s public key.

E_KB(A,R_A)

(4)  Bob sends Trent his name, Alice’s name, and Alice’s random number encrypted with Trent’s public key, K_T.

A,B,E_KT(R_A)

(5)  Trent sends Bob Alice’s public key, K_A, signed with Trent’s private key. He also sends him Alice’s random number, a random session key, Alice’s name, and Bob’s name, all signed with Trent’s private key and encrypted with Bob’s public key.

ST(KA),EKB(ST(RA,K,A,B))

(6)  Bob verifies Trent’s signatures. Then he sends Alice the second part of Trent’s message from step (5) and a new random number—all encrypted in Alice’s public key.

E_KA(S_T(RA,K,A,B),R_B)

(7)  Alice verifies Trent’s signature and her random number. Then she sends Bob the second random number, encrypted in the session key.

E_K(R_B)

(8)  Bob decrypts his random number and verifies that it unchanged.

Other Protocols

There are many other protocols in the literature. The X.509 protocols are discussed in Section 24.9, KryptoKnight is discussed in Section 24.6, and Encrypted Key Exchange is discussed in Section 22.5.

Another new public-key protocol is Kuperee [694]. And work is being done on protocols that use beacons, a trusted node on a network that continuously broadcasts authenticated nonces [783].

Lessons Learned

There are some important lessons in the previous protocols, both those which have been broken and those which have not:

— Many protocols failed because the designers tried to be too clever. They optimized their protocols by leaving out important pieces: names, random numbers, and so on. The remedy is to make everything explicit [43,44].

— Trying to optimize is an absolute tar pit and depends a whole lot on the assumptions you make. For example: If you have authenticated time, you can do a whole lot of things you can’t do if you don’t.

— The protocol of choice depends on the underlying communications architecture. Do you want to minimize the size of messages or the number of messages? Can all parties talk with each other or can only a few of them?

It’s questions like these that led to the development of formal methods for analyzing protocols.

3.4 Formal Analysis of Authentication and Key-Exchange Protocols

The problem of establishing secure session keys between pairs of computers (and people) on a network is so fundamental that it has led to a great deal of research. Some of the research focused on the development of protocols like the ones discussed in Sections 3.1, 3.2, and 3.3. This, in turn, has led to a greater and more interesting problem: the formal analysis of authentication and key-exchange protocols. People have found flaws in seemingly secure protocols years after they were proposed, and researchers wanted tools that could prove a protocol’s security from the start. Although much of this work can apply to general cryptographic protocols, the emphasis in research is almost exclusively on authentication and key exchange.