Weaknesses in Diffie-Hellman
The Diffie-Hellman Protocol is a widely used key agreement protocol, also called a key exchange protocol, used to establish a shared secret key between two parties. That secret key will then be used to encrypt the data that is to be transmitted, using a symmetric encryption algorithm like the Advanced Encryption Standard (AES). Diffie-Hellman solved one of the most significant problems with symmetric encryption: how to share the symmetric key.
In Diffie-Hellman, two parties, in this example user A and user B, agree on shared non-zero integer values, a prime number (p) and a generator (g) that is a prime factor of p. Each party then randomly selects a secret integer (s), which must not be shared with anyone else. Both parties then calculate a public value (A or B) to share with the other through the formula gs mod p.
Once each party’s public value has been shared, the secret key (K) can be calculated through the formula K = Bs mod p for user A and K = As mod p for user B. Now both users have a shared secret key, K, that even an eavesdropper cannot calculate without knowing the secret integers, s, which is known as the Computational Diffie-Hellman assumption.
The problem with Diffie-Hellman arises when the value for p is not sufficiently large. With small values for p, it is possible to iterate through possible values for each user’s s until the correct values are found. This is a known weakness of Diffie-Hellman, which is addressed by extremely large values for p.
For demonstration purposes, I wrote a Python script that, given small values, will take in only the public values p, g, A, and B, and calculate each user’s secret integers, s, and the shared secret key, K.
To give an example, assume a scenario where user A and B agree on the value of p as 21101 and g as 174. User A’s public integer is 18258 and user B’s is 11535. We do not know each user’s secret integer, s, or the shared secret, K.
The script iterates through possible solutions until it finds values for each user’s s that create the same K and the correct values for A and B. In this example, the script discovered that the shared secret key is 9213. User A’s secret integer is 12 and user B’s is 37.
I hope this is a good example how it is critical to select sufficiently large values when using Diffie-Hellman. It is important to note that selecting a large prime for p does not make it impossible to break Diffie-Hellman, but it makes it computationally infeasible, at least with current technology.