Diffie-Hellman: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Sandy Harris
No edit summary
mNo edit summary
 
(32 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{subpages}}
{{PropDel}}<br><br>{{subpages}}
{{TOC|right}}
{{TOC|right}}
The '''Diffie-Hellman key agreement protocol''' (also called Diffie-Hellman key exchange, or just Diffie-Hellman, D-H or DH) <ref name=RFC2631>{{citation
The '''Diffie-Hellman key agreement protocol''' (also called Diffie-Hellman key exchange, or just Diffie-Hellman, D-H or DH) <ref name=RFC2631>{{citation
Line 7: Line 7:
  | date = June 1999
  | date = June 1999
  | url = http://www.ietf.org/rfc/rfc2631.txt
  | url = http://www.ietf.org/rfc/rfc2631.txt
}}</ref> allows two parties without any initial [[shared secret]] to create one in a manner immune to eavesdropping. Once they have done this, they can communicate privately by using that shared secret as a [[cryptographic key]] for a [[block cipher]] or a [[stream cipher]], or as the basis for a further key exchange.
}}</ref>
is a technique of [[cryptography]] that allows two parties without any initial [[shared secret]] to create one in a manner immune to eavesdropping. Once they have done this, they can communicate privately by using that shared secret as a [[cryptographic key]] for a [[block cipher]] or a [[stream cipher]], or as the basis for a further key exchange.


The protocol is secure against all [[passive attack]]s, but it is not at all resistant to active [[man-in-the-middle attack]]s. Conventionally, the two communicating parties are A and B or [[Alice and Bob]]. If a third party can impersonate Bob to Alice and vice versa, then no useful secret can be created. Authentication of the participants is a prerequisite for safe Diffie-Hellman key exchange. There are several ways to do the required authentication. For example, in [[Internet Key Exchange]] (IKE),<ref name=RFC4306>{{citation
The Diffie-Hellman method is based on the [[discrete logarithm]] problem and is secure unless someone finds an efficient solution to that problem. It can use any of several variants of discrete log; common variants are over a field modulo a large prime (1536 bits for one heavily used group in [[IPsec]]) or a field defined by an [[elliptic curve]].
| id = RFC4306
| title = Internet Key Exchange (IKEv2) Protocol
| editor =  C. Kaufman,
| date = December 2005
| url = http://www.ietf.org/rfc/rfc4306.txt}}</ref>  authentication can be done with a shared secret or with any of several [[public key]] techniques. In [[Transport Layer Security]] (TLS),<ref name=>{{citation
| id = RFC5246
| title = The Transport Layer Security (TLS) Protocol Version 1.2.
| author = T. Dierks, E. Rescorla
| date = August 2008
| url = http://www.ietf.org/rfc/rfc5248.txt}}</ref>it is done by exchange of [[X.509]] Certificates.


The Diffie-Hellman method is based on the [[discrete logarithm]] problem and is secure unless someone finds an efficient solution to that problem. It can use any of several variants of discrete log; common variants are over a field modulo a large prime (1536 bits for one heavily used group in [[IPsec]]) or a field defined by an elliptic curve.
Conventionally, the two communicating parties are A and B or [[Alice and Bob]].


Given a prime p and generator g (see [[discrete logarithm]]), Alice:
Given a prime p and generator g (see [[discrete logarithm]]), Alice:


     * generates a random number a
     * generates a random number a
     * calculates A = g^a modulo p
     * calculates A = g<sup>a</sup> modulo p
     * sends A to Bob
     * sends A to Bob


Line 32: Line 23:


     * generates a random number b
     * generates a random number b
     * calculates B = g^b modulo p
     * calculates B = g<sup>b</sup> modulo p
     * sends B to Alice
     * sends B to Alice


Now Alice and Bob can both calculate the shared secret s = g^(ab). Alice knows a and B, so she calculates s = B^a. Bob knows A and b so he calculates s = A^b.
Now Alice and Bob can both calculate the shared secret S = g<sup>ab</sup>. Alice knows a and B, so she calculates S = B<sup>a</sup>. Bob knows A and b so he calculates S = A<sup>b</sup>.
 
An eavesdropper can intercept A and B. We assume he will know p and g; by [[Kerckhoffs' Principle]] he may know everything about the system except the current keys, a and b. However, short of solving the discrete log problem, this does not let him discover the secret S.
 
== Passive attacks ==
 
If the attacker finds an efficient solution to the [[discrete logarithm]] problem, then all bets are off &mdash; the Diffie-Hellman protocol is secure only if discrete log is intractable. Discrete log is a well-studied problem and no efficient solution has been published; it seems likely that none exists. On the other hand, no proof that an efficient solution does not exist has been published either. It is at least conceivable that an efficient method will be published next week, or even that some intelligence agency has one already and is keeping it secret.
 
There are pitfalls in the choice of the prime and generator
<ref name=AV>{{citation
| author=Ross Anderson & Serge Vaudenay
| title=Minding your p’s and q’s
| conference=Asiacrpyt'96
| publisher= LNCS 1163
| date=1996
| url=http://www.cl.cam.ac.uk/~rja14/Papers/psandqs.pdf
}}</ref>; poor choices make the discrete log problem much simpler.
 
If either Alice or Bob uses a weak [[random number generator]], or uses a good pseudo-random generator but does not provide it with a good truly random seed, then the protocol can be subverted. The attacker can make guesses at a or b; a correct guess breaks the system. If the random number generator is sufficiently weak, or uses a weak seed, then the number of guesses required for this attack may not be prohibitive. An early version of Netscape SSL was broken because of poor seeding practices
<ref>{{citation
| title = Randomness and the Netscape Browser
| author = Ian Goldberg and David Wagner
| journal = Dr. Dobb's Journal
| date = January 1996
| url=http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html
}}</ref>.
However with large p, a good generator, and a good seed this attack is wildly impractical.
 
With the exceptions mentioned above, the protocol is secure against all [[passive attack]]s.
 
== Active attacks ==
 
However, the protocol itself is not at all resistant to an [[active attack]], in particular a [[man-in-the-middle attack]]. If a third party can impersonate Bob to Alice and vice versa, then no useful secret can be created. '''Authentication of the participants is a prerequisite for safe Diffie-Hellman key exchange.''' Without authentication, neither Alice nor Bob know who they are talking to; they may think they are talking to each other, but actually both be talking to the man in the middle.
 
There are several ways to do the required authentication. For example, in [[Internet Key Exchange]] (IKE),
<ref name=RFC4306>{{citation
| id = RFC4306
| title = Internet Key Exchange (IKEv2) Protocol
| editor =  C. Kaufman,
| date = December 2005
| url = http://www.ietf.org/rfc/rfc4306.txt}}</ref>
authentication can be done with a shared secret or with any of several [[public key]] techniques. In [[Transport Layer Security]] (TLS),
<ref name=RFC5246>{{citation
| id = RFC5246
| title = The Transport Layer Security (TLS) Protocol Version 1.2.
| author = T. Dierks, E. Rescorla
| date = August 2008
| url = http://www.ietf.org/rfc/rfc5248.txt}}</ref>it is done by exchange of [[X.509]] Certificates. How to do it securely when the only authentication available is a password short and simple enough for humans to remember is an active area of current research.


An eavesdropper will know p and g since these are made public, and can intercept A and B but, short of solving the discrete log problem, these do not let him or her discover the secret s.
[[Better than nothing security]], or BTNS, is basically [[IPsec]] done without authentication
<ref name=RFC5386>{{citation
| id = RFC5386
| title = Better-Than-Nothing Security: An Unauthenticated Mode of IPsec
| editor = N. Williams, M. Richardson
| date = November 2008
| url = http://www.ietf.org/rfc/rfc5386.txt
}}</ref>,
<ref name=RFC5387>{{citation
| id = RFC5387
| title = Problem and Applicability Statement for Better-Than-Nothing Security (BTNS)
| editor = J. Touch, D. Black & Y. Wang
| date = November 2008
| url = http://www.ietf.org/rfc/rfc5387.txt
}}</ref>.
Setting up and managing a secure authentication infrastructure is not a trivial task and unauthenticated encryption does at least protect against all [[passive attack|passive eavesdropping]].


If either Alice or Bob uses a weak [[random number]] generator, then the protocol can be subverted. The attacker can make guesses at a or b; a correct guess breaks the system. If the random number generator is sufficiently weak, or if it is badly seeded as in an early version of [http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html Netscape SSL], then the number of guesses required for this attack may not be prohibitive. However with large p and a good generator, this attack is wildly impractical.
There are variants of a man-in-the-middle attack which involve the attacker choosing specific values for a and b that help him break the system<ref name=AV />


==References==
==References==
{{reflist|2}}
{{reflist|2}}[[Category:Suggestion Bot Tag]]

Latest revision as of 07:01, 7 August 2024

This article may be deleted soon.
To oppose or discuss a nomination, please go to CZ:Proposed for deletion and follow the instructions.

For the monthly nomination lists, see
Category:Articles for deletion.


This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

The Diffie-Hellman key agreement protocol (also called Diffie-Hellman key exchange, or just Diffie-Hellman, D-H or DH) [1] is a technique of cryptography that allows two parties without any initial shared secret to create one in a manner immune to eavesdropping. Once they have done this, they can communicate privately by using that shared secret as a cryptographic key for a block cipher or a stream cipher, or as the basis for a further key exchange.

The Diffie-Hellman method is based on the discrete logarithm problem and is secure unless someone finds an efficient solution to that problem. It can use any of several variants of discrete log; common variants are over a field modulo a large prime (1536 bits for one heavily used group in IPsec) or a field defined by an elliptic curve.

Conventionally, the two communicating parties are A and B or Alice and Bob.

Given a prime p and generator g (see discrete logarithm), Alice:

   * generates a random number a
   * calculates A = ga modulo p
   * sends A to Bob

Meanwhile Bob:

   * generates a random number b
   * calculates B = gb modulo p
   * sends B to Alice

Now Alice and Bob can both calculate the shared secret S = gab. Alice knows a and B, so she calculates S = Ba. Bob knows A and b so he calculates S = Ab.

An eavesdropper can intercept A and B. We assume he will know p and g; by Kerckhoffs' Principle he may know everything about the system except the current keys, a and b. However, short of solving the discrete log problem, this does not let him discover the secret S.

Passive attacks

If the attacker finds an efficient solution to the discrete logarithm problem, then all bets are off — the Diffie-Hellman protocol is secure only if discrete log is intractable. Discrete log is a well-studied problem and no efficient solution has been published; it seems likely that none exists. On the other hand, no proof that an efficient solution does not exist has been published either. It is at least conceivable that an efficient method will be published next week, or even that some intelligence agency has one already and is keeping it secret.

There are pitfalls in the choice of the prime and generator [2]; poor choices make the discrete log problem much simpler.

If either Alice or Bob uses a weak random number generator, or uses a good pseudo-random generator but does not provide it with a good truly random seed, then the protocol can be subverted. The attacker can make guesses at a or b; a correct guess breaks the system. If the random number generator is sufficiently weak, or uses a weak seed, then the number of guesses required for this attack may not be prohibitive. An early version of Netscape SSL was broken because of poor seeding practices [3]. However with large p, a good generator, and a good seed this attack is wildly impractical.

With the exceptions mentioned above, the protocol is secure against all passive attacks.

Active attacks

However, the protocol itself is not at all resistant to an active attack, in particular a man-in-the-middle attack. If a third party can impersonate Bob to Alice and vice versa, then no useful secret can be created. Authentication of the participants is a prerequisite for safe Diffie-Hellman key exchange. Without authentication, neither Alice nor Bob know who they are talking to; they may think they are talking to each other, but actually both be talking to the man in the middle.

There are several ways to do the required authentication. For example, in Internet Key Exchange (IKE), [4] authentication can be done with a shared secret or with any of several public key techniques. In Transport Layer Security (TLS), [5]it is done by exchange of X.509 Certificates. How to do it securely when the only authentication available is a password short and simple enough for humans to remember is an active area of current research.

Better than nothing security, or BTNS, is basically IPsec done without authentication [6], [7]. Setting up and managing a secure authentication infrastructure is not a trivial task and unauthenticated encryption does at least protect against all passive eavesdropping.

There are variants of a man-in-the-middle attack which involve the attacker choosing specific values for a and b that help him break the system[2]

References

  1. Rescorla, E. (June 1999), Diffie-Hellman Key Agreement Method, RFC2631
  2. 2.0 2.1 Ross Anderson & Serge Vaudenay (1996), Minding your p’s and q’s, LNCS 1163
  3. Ian Goldberg and David Wagner (January 1996), "Randomness and the Netscape Browser", Dr. Dobb's Journal
  4. C. Kaufman,, ed. (December 2005), Internet Key Exchange (IKEv2) Protocol, RFC4306
  5. T. Dierks, E. Rescorla (August 2008), The Transport Layer Security (TLS) Protocol Version 1.2., RFC5246
  6. N. Williams, M. Richardson, ed. (November 2008), Better-Than-Nothing Security: An Unauthenticated Mode of IPsec, RFC5386
  7. J. Touch, D. Black & Y. Wang, ed. (November 2008), Problem and Applicability Statement for Better-Than-Nothing Security (BTNS), RFC5387