Cracking diffie-hellman

Question

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)

Answer 1

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.