# Cracking diffie-hellman

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)

• After about a minute on github. Commented May 22, 2020 at 9:26
• @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 Commented May 22, 2020 at 9:28

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.
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.