Jaa

Diffie-Hellman Key Exchange

  • Artikkeli

If you've been reading the previous posts on network security, then you've seen several instances where two parties need a shared secret. We've just been assuming that a shared secret is magically known. How can two parties share a secret without having previously arranged confidential information between them? This is the boot-strapping problem of encryption, because it seems like exchanging a secret requires that you've exchanged secrets before. However, it turns out that two parties can build a shared secret even if all of the communication between them can be intercepted.

Diffie-Hellman (DH) is an algorithm that lets two parties collectively create an encryption key. You can't directly use DH to send data from one party to another. DH lets you create an encryption key, and then you can use that key to send the data. In DH, there are two public numbers for the conversation, a shared public key for each side, and a hidden private key for each side.

To start a key exchange, the two sides first share a large prime number p and a base value g that is between 1 and p - 1. These numbers can be agreed on in public, so there's no need to protect the conversation from eavesdroppers. This allows the exchange to start without having a prearranged secret. Each side then picks a secret value that doesn't get shared. Call the two sides and their corresponding numbers A and B. A sends gA mod p over to side B. B sends gB mod p over to side A. The values sent over the wire are still totally public. This relies on the fact that even when g, p, and the result are publicly known, it's still very difficult to compute A or B.

A knows the value A and gB mod p, making it simple for A to calculate gAB mod p. B knows the value B and gA mod p, making it simple for B to calculate gAB mod p. Anyone else would be unable to compute this value, making it possible to use this shared result as an encryption key. How difficult is it to compute gAB mod p given g, p, gA mod p, and gB mod p? That actually isn't known, although all evidence so far points to it being quite challenging.

Next time: Attacks on Diffie-Hellman

Comments

  • Anonymous
    September 12, 2006
    Maybe I am stupid, but "A and g^B mod p, making it simple for A to calculate g^AB mod p" is not very obvious to me. Can you tell how would you calculate it ?

  • Anonymous
    September 12, 2006
    All fine and good if you have some other way of verifying the identity of the other party, but how do you thwart a man-in-the-middle attack during the key exchange? In a practical working system, I don't see how you can get around the need for a trusted third party who can validate the identity of the party with whom you are trying to establish a secure conversation.

  • Anonymous
    September 12, 2006
    Today’s the final part of the series on the stream upgrade model (StreamUpgradeBindingElement and StreamUpgradeProvider...

  • Anonymous
    September 12, 2006
    Pazu-

    The nice thing about the mod operator is that if you have a series of composable operations, you can take the mod after each step or take the mod just at the end and get the same results.  So what we get is that

    (g^B mod p)^A mod p = (g^AB mod p) = (g^A mod p)^B mod p

    This allows both A and B to compute the same value.

  • Anonymous
    September 12, 2006
    MKane91301-

    Being able to exchange secrets and being able to verify the identify of the other party are independent problems.  When we look at a real system like SSL, we'll see how to put multiple features together to solve problems like man-in-the-middle.

    For pure DH, a partial mitigation of MITM is that even if the attacker gets to pick g and p, it's still hard to compute A and B.  This will factor into one of the security attacks I talk about tomorrow.

  • Anonymous
    September 14, 2006
    PingBack from http://blogs.msdn.com/drnick/archive/2006/09/13/751829.aspx

  • Anonymous
    September 18, 2006
    One of the key points made about the Diffie-Hellman algorithm is that it doesn’t actually allow you to...

  • Anonymous
    October 08, 2006
    Today’s the final part of the series on the stream upgrade model ( StreamUpgradeBindingElement and StreamUpgradeProvider

  • Anonymous
    October 17, 2006
    One of the key points made about the Diffie-Hellman algorithm is that it doesn’t actually allow you to

  • Anonymous
    October 17, 2006
    We’re going to continue looking at the Diffie-Hellman algorithm today by examining how to configure the