0
$\begingroup$

I want am making an application, demonstrating an attack on a weakly performed diffie-hellman. I need to implement an algorithm that can use the shared variables in order to compute the key. Searching for resources, I keep running into the logjam attack. However I can't really filter out the number crunching from all the HTTP protocol information.

If anyone could provide som resources to point me in the right direction, or a formula to how to successfully compute the key from the known variables. It would be greatly appreciated!

Edit


I have found this resource, which seems really promising. http://index-of.es/Miscellanous/How%20To%20Backdoor%20Diffie-Hellman.pdf

page 6 it says

To attack a Diffie-Hellman key exchange, one could extract the secret key a from one of the peer's public key ya = g a (mod p). One could then compute the shared key g ab (mod p) using the other peer's public key yb = g b (mod p).

The naive way to go about this is to compute each power of g (while tracking the exponent) until the public key is found. This is called trial multiplication and would need on average q 2 operations to find a solution (with q the order of the base). More efficiently, algorithms that compute discrete logarithm in expected √q steps

I translate this to

compute each power of g g^1 mod(p), g^2 mod(p), g^3 mod(p)..g^n mod(p)

This would work, however it requires to isolate the exponent from the formula to work. Which is pretty difficult to me.

How would you isolate a from p^a mod(p)

$\endgroup$
  • $\begingroup$ After about a minute on github. $\endgroup$ – DannyNiu May 22 at 9:26
  • $\begingroup$ @DannyNiu I have seen that repo, it is bloated and I could not find the algorithm in there. I am not interested in making a server that can sniff the variables, I just want to provide them to an algorithm $\endgroup$ – Jonas Grønbek May 22 at 9:28
1
$\begingroup$

An interesting cryptanalytic attack on Diffie-Hellman is the small subgroup confinement attack. The attack works if the DH parameters are chosen without caution. Here is a brief explanation on how it works.

DH works in multiplicative groups. Say we are working in $Z^*_p$. As $p$ is prime, the order of this group ($p-1$) is composite, therefore by Lagrange's Theorem there exists subgroups. The attacker basically reduces the key space to one of these subgroups having much smaller orders by interfering the communication and modifying it.

Let our DH group to be $(Z_p^*,*)$ and $\alpha$ to be the primitive root used. Normally Alice computes a random $s_a$ and keeps it secret. Alice sends $\alpha^{s_a}$ to Bob, but the attacker Eve receives it first. Eve looks up for possible subgroups by searching through factors of $(p-1)$ and finds a small factor $q$. By Lagrange's Theorem she knows there exists a subgroup of order $q$. She computes $t=\frac{p-1}{q}$ and sends Bob $(\alpha^{s_a})^t$. Bob also computes his secret random value $s_b$ and computes the shared secret $(\alpha^{ts_a})^{s_b}$. Bob then sends Alice $\alpha^{s_b}$ but Eve intercepts. Eve sends Alice $(\alpha^{s_b})^t$ and Alice also computes the shared secret as $(\alpha^{ts_b})^{s_a}$. Both have the shared secret, yes, but their shared secret is of form $(\alpha^t)^x$. Numbers of this form are generated by the subgroup with generator $\alpha^t$ which is known to be of order $q$. As $q$ is small (by our hypothesis of DH parameters have been selected poorly), Eve can simply compute the DH discrete logarithm problem by bruteforce as there are much less trials.

How to protect?

Pick $p$ such that $p=2q+1$ where $q$ also is a prime (see Sophie-Germain primes). Having this property, the group order will be $p-1=2q$. As $q$ is prime, only factors of $p-1$ are 2 and $q$. So when setting up shared secrets with DH, check if your group order is 2. If this is the case you know that you've been attacked.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I have marked as answer, since I know it answers the question. But my math skills is not nearly sufficient to understanding fully. The notation is really confusing to me $\endgroup$ – Jonas Grønbek May 23 at 20:20
  • $\begingroup$ @JonasGrønbek If you'd like to truly understand this attack any many other cryptanalytic attacks, what you need are the essentials of number theory and abstract algebra. You can acquire the skills on your own trust me. I only hold a BS of CS no MSc or PhD. There are great textbooks covering the topic. $\endgroup$ – Oran Can Ören May 24 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.