Diffie–Hellman key exchange

The Diffie -Hellman key exchange or Diffie -Hellman - Merkle key exchange is a protocol in the field of cryptography. With him two communication partners generate a secret key that only these two know. This key is usually used to transmit encrypted messages using a symmetric cryptosystem.

In the Diffie -Hellman key exchange, the two communication partners send over an insecure channel to one message. The problem to calculate from these two messages is the secret key, referred to as the Diffie-Hellman problem. From this it is believed that it is virtually not soluble. Therefore, someone who listens in both messages, it generally does not compute the secret key. However, the Diffie -Hellman key exchange is no longer sure if an attacker between the two communication partners to interrupt and change messages. This gap include protocols such as the station -to- station protocol by using additional digital signatures and message authentication codes.

The long tradition of string lists and codebooks put the Diffie- Hellman method to an end. Even during the Second World War had the users of sophisticated encryption and machinery ( for example, the Enigma ) codebooks to carry with them to know for each day of the year, what key the sender used. If such a code book stolen, encryption was invalid. Especially in the military and the allocation of transport such highly secret code books was always the biggest problem child.

The Diffie -Hellman key exchange belongs to the class of key exchange protocols and forms the basis of the ElGamal encryption method.

The implementation of elliptic curve is known as the Elliptic Curve Diffie -Hellman ( ECDH ).

History

The algorithm was developed by Martin Hellman together with Whitfield Diffie and Ralph Merkle at Stanford University ( California ) and published in 1976.

As recently as 1997 it was announced the British Government Communications Headquarters ( GCHQ ) had already been granted in the 1960s commissioned to find another way for key distribution to avoid the high costs of the then usual key distribution. The doubts expressed by James H. Ellis, Clifford Cocks and Malcolm J. Williamson ideas were similar to the Diffie - Hellman method. The GCHQ has one hand on the other hand never applied for a patent on the grounds of secrecy, because of the question for the British from the perspective of the early 1970s benefit.

Operation

Two communication partners ( in the figure, these are Alice and Bob) will communicate over an unsecured medium such as a cable or radio link encrypted. For this, a symmetric cryptosystem is to be used for both but first need a shared secret key. About the Diffie -Hellman key exchange, they get both to such a key.

The fact that both communication partners charge the same value for showing the following two equations:

Example

The communication partners are Alice and Bob. The example uses very small numbers. In actual application numbers with several hundred points are used.

Although a possibly existing eavesdropper could listen to the numbers 13, 2, 6 and 9, the actual shared secret of Alice and Bob remains for him but hidden. can be used as a key for subsequent communication.

Security

Diffie-Hellman Problem

As a ( computational ) Diffie -Hellman problem is referred to the following task:

Since this problem is in certain groups can only be solved with an enormous computational effort, an attacker from the two transferred during the Diffie -Hellman key exchange messages can not calculate the generated key.

A variant of the above search problem is the Decisional Diffie -Hellman problem. This problem does not have to be calculated, but ( given the same group elements) are only decide whether it is or to a randomly chosen group element for a given element. This problem is difficult, so an attacker who has overheard a transmission, no information about the exchanged key. This is a stronger security property, not to calculate as the key.

The Diffie -Hellman problem is closely related to the discrete logarithm problem. Who can compute discrete logarithms, can solve the Diffie- Hellman problem. There is no known way to solve the Diffie- Hellman problem without having to compute discrete logarithms. Ueli Maurer has shown that both problems are equivalent under certain conditions.

Man- in-the -middle attack

The Diffie -Hellman key exchange is no longer sure if the attacker ( in the following example: the attacker " Mallory " ) may modify data packets in a man-in- the-middle attack. The attacker then intercepts the messages sent by Alice and Bob and instead sends each his own message

Next, it is calculated from a random number, and the publicly-known numbers and.

After the key exchange, the two communication partners Alice and Bob have different keys and. In principle twice a Diffie -Hellman key exchange was carried out: one between Alice and the attacker Mallory and once between Mallory and Bob. Here, Mallory becomes aware of the two keys and.

Since Alice and Bob go out in the course of it, to communicate with each other, Mallory can intercept the following symmetric encrypted communication. Circulating them to continue to about themselves. Data from Alice decrypts with Mallory and encrypts it with again, before passing them to send to Bob. Here, Mallory can read the message content as well as change unnoticed. The same procedure applies them for the opposite direction.

To exclude such a man-in- the-middle attack, the exchanged messages need to be authenticated. For this we use digital signatures.

Other groups

For the Diffie -Hellman key exchange, other groups may be used in addition to the reduced residue class groups. There are suitable for all groups in which one can calculate powers efficiently and is the Diffie -Hellman problem is difficult to solve, for example, groups on certain elliptic curves.