What is Diffie-Hellman?

What is Diffie-Hellman?
November 11, 2019

Communication is one of the fundamental pillars of humanity since its inception.

Terminology

  • K .- Key
  • E .- encryption function
  • D .- decryption function
  • C .- encrypted text
  • M .- plain text message

Introduction

Communication is one of the fundamental pillars of humanity since its inception. However, inherent to it we find that the need to protect our third party messages is also a fundamental requirement. For this historically we have resorted to several methods, for example, the encrypted ones: Atbash, Scytale, Caesar, ROT13.


Table 1. Comparative encryption algorithms

These methods have a common characteristic: it is necessary to know in advance the “key “ with which the original text could be obtained from the encrypted text. For example, the number of characters used for the displacement or the length and width of the wand to roll the tape or the corresponding character by which the original text should be replaced. This was a basic premise of these protocols.

In 1945, Claude E. Shannon (considered by many to be the father of mathematical cryptography), wrote an article called “A mathematical theory of cryptography “ that was published by the Bell System Technical Journal in 1949. It is commonly accepted that this paper was the beginning of modern cryptography, Shanon identified the two main objectives of cryptography: stealth and authenticity. Shannon’s work influenced the crypto research of other authors including Whitfield Diffie and Martin Hellman.

Subsequently, other types of protocols were implemented. Its main division is established as:

  • Symmetric algorithms
  • Public key

The symmetric algorithms also called conventional algorithms are those where the encryption and decryption key is the same. It is important to note that the security of symmetric algorithms lies in the key, since it depends on the encryption of the text. In this way, the key must remain secret so that the communication remains secret. Thus it is fulfilled that:

“Encrypt Key (Message) = Encrypted Text”

“Decrypt Key (Encrypted Text) = Message”

On the other hand, the public key algorithms (also known as asymmetric algorithms ) are designed in such a way that the encryption key is different from the decryption key. These algorithms are called “public-key “ because the encryption key is public, that is, the owner of the public key encrypts the message, and the receiver, with his private key, decrypts it. Suppose Alice want to send an encrypted message to Bob, it is fulfilled that:

“Encrypt Public key Bob (Message) = Encrypted Text”

Taking into account that the encryption and decryption key are different, to decrypt the message Bob will use his private key:

“Decrypt Private key Bob (Encrypted Text) = Message”

The first researchers to find and publish public key cryptography ideas were Whitfield Diffie and Martin Hellman of Stanford University, along with Ralph Merkle of Berkeley University. They were working independently on the same problems until they met and started collaborating.

The first work published in Public Key Cryptography was in the paper called “New Directions in Cryptography” in November 1976, version of IEEE Transactions on Information Theory. This paper represents the main ideas of Public Key Cryptography, including the generation of digital signatures and showed some algorithms for its execution, revolutionizing the world of crypto research, which until then was controlled in the confines of the government. Diffie, Hellman and Merkle subsequently obtained patent number 4,200,770 corresponding to their security method.

Process

Diffie-Hellman is a mathematical algorithm that allows two parties to produce a shared secret even though they have never been communicated before. Diffie-Hellman is widely used in various applications to encrypt data, for example: SSL (Secure Socket Layer), TLS(Transport Layer Security), SSH (Secure Shell) or VPN (Virtual Private Network).

This can be explained in a fairly graphic way through colors:


Image 3. A. J. Han Vinck, Introduction to public cryptography

In this image you can see the following:

  • Alice and Bob agree on a common color.
  • Alice selects a color she keeps secret.
  • Bob, in the same way, selects a color that he keeps secret.
  • Each part (Alice and Bob) mixes the previously agreed common color and generates a new color for each one.
  • The new color is sent to the other party.
  • Alice and Bob mix their “private” color with the one they received from the other party and generate a new color that is the same for both parties. This constitutes the “common secret “.

P is a prime number and G is a predefined non-random number for example:

The parties choose the keys a and b considering that no one discloses it publicly. Ideally, these numbers are memorized and are not written or stored anywhere, then the parties calculate the public keys A and B according to their personal keys.

Example:


Image 4. Diffie-Hellman implementation example

The K secret key is calculated individually for each part.

Man in the middle

The Diffie-Hellman algorithm in its early stages had a notable vulnerability known as Man-In-The-Middle. In this attack, a spy whom we will call “Eve “ intervenes in a communication between Alice and Bob in such a way that he recovers Alice’s public key and sends his own public key (Eve) to Bob (replacing Alice). Performing the same process, intercepts Bob’s public key and sends his own public key (Eve) to Alice (replacing Bob). At this point Alice agrees a secret key with Eve instead of Bob and Bob agrees a secret key with Eve instead of Alice so that Eve will be able to undock messages from the two pairs replacing each one.

The weakness of this algorithm is that the exchange of Diffie-Hellman keys does not implement member authentication. Possible solutions are the inclusion of digital signatures and other protocol variants aimed at peer authentication. This way Alice will be sure to talk with Bob and Bob with Alice. Another possible solution is to discard the keys after using them so that they cannot cause future problems.


Image 5. Man in the middle

Conclusion

The Diffie-Hellman encryption algorithm forms the basis of modern cryptography. It allows the development of various tools and technologies. Additionally, it makes security in the encryption process and not in the key.

References