An idea came to me today for a protocol for exchanging keys point-to-point (inspired by the Robert Cain messages). The protocol is a just combination of the Interlock Protocol described on page 44 of "Applied Cryptography" and Diffie-Hellman, describe on page 275. Keeping with the terminology of the book, Alice will attempt to exchange a key with Bob, and Mallet will attempt to sit in the middle without being detected. As has been demonstrated in the past, I haven't read a lot of the cryptography papers that are out there, so for all I know, this is a well known protocol (or simple variation). However, I haven't seen it, and it seems interesting. Anyways, on with the show... 1) Alice sends Bob her public key. (ala Interlock Protocol) 2) Bob sends Alice his public key. 3) Alice generates a Diffie-Hellman "n" value, encrypts "n" with Bob's public key and sends half of the "n" message to Bob. 4) Bob generates a Diffie-Hellman "g" value, encrypts "g" with Alice's public key and sends half of the "g" message to Alice. 5) Alice sends other half of "n" message to Bob. 6) Bob puts the two halves of Alice's "n" message together and decrypts it with his private key. Bob sends the other half of his "g" message to Alice. 7) Alice puts the two halves of Bob's "g" message together and decrypts it with her private key. Alice and Bob's each now have an "n" and a "g". Below, I try to show that they can only have the same "n" and "g" if there is no man-in-the-middle. Alice chooses a random large integer x and computes: X = (g**x) mod n Bob chooses a random large integer y and computes: Y = (g**y) mod n Standard Diffie-Hellman stuff. 8) Alice encrypts X with Bob's public key and sends half of X message to Bob. 9) Bob encrypts Y with Alice's public key and sends half of Y message to Alice. 10) Alice sends other half of X message to Bob. 11) Bob puts the two halves of Alice's X message together and decrypts it with his private key. Bob sends the other half of his Y message to Alice. 12) Alice puts the two halves of Bob's Y message together and decrypts it with her private key. Now Alice and Bob's each have an X and a Y. Alice computes k = (Y**x) mod n. Bob computes k' = (X**y) mod n. 13) Alice encrypts a message using k and sends it to Bob. Bob decrypts message using k' and validates success of protocol. 14) Bob encrypts a message using k' and sends it to Alice. Alice decrypts message using k and validates success of protocol. ---------- What can Mallet do to this protocol? Mallet can substitute his own public keys for Alice's and Bob's in steps 1 and 2. Mallet can then capture "n" (from Alice) and "g" (from Bob), although not immediately. Mallet forward Bob bogus "n" message halves and Alice bogus "g" message halves. Thus Alice will get a bogus g, call it g', and Bob will get a bogus n, call it n'. Mallet cannot forward the real "n" to Bob because of the interlock protocol. Similarly, Mallet cannot forward the real "g" to Alice. Mallet only learns "n" in step 5 and "g" in step 6. However, he must forward half of a bogus "n" to Bob in step 3), half of a bogus "g" to Alice in step 4. At the end of step 6, Alice will have n and g' and Bob will have n' and g. Alice and Bob continue with the protocol and calculate X and Y. Alice and Bob use the interlock protocol to exchange X and Y. As with n and g, Mallet will eventually get X and Y, but not before having to forward a bogus X to Bob and a bogus Y to Alice (call them X' and Y'). Alice and Bob, still unaware of Mallet, compute k and k'. However, since they are using different values for n, g, X, and Y, they will compute different values. The encrypted messages in steps 13 and 14 will expose Mallet. I've only spent about fifteen minutes thinking about this protocol. I can't say that it is without holes or even that it does what I say it does. However, I think it might have potential. What to the professionals think? Jim_Miller@suite.com