[OTR-users] Re: Perfect Forward Secrecy

[Ian Goldberg]

On Mon, Mar 28, 2005 at 06:47:59PM -0500, Jason Cohen wrote:
> I actually have read the paper, and OTR does indeed seem very clever. I
> suppose my problem is that I don't fully understand how Diffie Hellman
> Agreement can do what it does. I can understand RSA/DSA which creates a
> public/private keypair on one machine and then distributes the public
> key (I understand how PGP works), but the concept of realtime key
> generation over an insecure network is baffling. I suppose it would be
> nice if I could better understand the math involved. Could someone
> explain how Diffie Hellman works to a social-science undergraduate? It
> would be greatly appreciated.

[Since you indicate you know how PGP works, I'll also include the math
bits, in brackets.]

DH works in almost the same way, except *both* Alice and Bob need a
public/private keypair.  Alice sends her public key to Bob, and Bob
sends his to Alice. [Math bits: Alice's private key is "a", and her
public key is "A" = "g^a mod p", where g and p are specified in advance
(in the OTR spec in this case, which uses the standard ones from IPSec).
Similarly, Bob's private key is "b", and his public key is "B" =
"g^b mod p".]

Alice then knows Bob's public key "B", as well as her own private key "a".
Bob knows Alice's public key "A", as well as his own private key "b".
Eve the easvesdropper only knows Alice and Bob's public keys, "A" and "B".

Now comes the magic of Diffie-Hellman: it turns out Alice can combine
her own private key with Bob's public key in such a way, so as when Bob
combines his own private key with Alice's public key, they get *the same
answer*.  Moreover, Eve, who knows both public keys, but neither private
key, has no (known) way of calculating this answer.

[Math bits: Alice calculates "B^a mod p", and Bob calulates "A^b mod p".
Note that:

   B^a mod p = (g^b mod p)^a mod p
             = g^(ba) mod p
	     = g^(ab) mod p
	     = (g^a mod p)^b mod p
	     = A^b mod p
]

This common value is called the Diffie-Hellman shared secret, and is
used in various ways to encrypt the message.  Since Alice and Bob both
know it, and Eve doesn't, this is secure.

In OTR, Alice and Bob change their keys *often* (as often as every
message), so each message ends up being encrypted with a brand-new DH
shared secret.

Does that help?

   - Ian