# Diffie-Hellman Key Exchange attack on small secret keys [closed]

The question as the title suggests is based on the key exchange with Diffie-Hellman protocol and is something like this:

*"We have intercepted a communication between Alice and Bob: intercepted-communication

We also have read out the code Alice was using to communicate: alice.py

Unfortunately, the flag is no longer in the code. Can you reconstruct it from the communication between Alice and Bob?

Usually, the Diffie-Hellman key exchange can not be broken easily. However, our analysts told us that Bob used a small secret key that can be brute-forced."*

I am having a really hard time understanding this. Any help with this will be helpful.

• Welcome to Cryptography. This is clearly homework. Where did you stuck? Did you learn that you can solve the small instance of discreate log by brute-force? – kelalaka Nov 11 '19 at 16:02
• Haha this indeed is homework! I'm just trying out all possibilities of pow(g, x, p) with the given p and g and continuously incrementing x until that matches the intercepted value from Alice (2318...). It is taking way too long. This might give the answer but I am looking for an optimal solution. – user74043 Nov 11 '19 at 19:55
• Or you just can solve by using the self power map, for small prime modulus is a viable method. Take $g^x$ and exponentiate $g^{g^x}, g^{g^{g^x}}, \cdots$ in $F_p$ until you hit $g^x$ again, recovering $x$. In the other hand you can use Shank's, Pohlig-Hellman, Index calculus or Pollard's kangaroo which are well known in literature. However, the final methods cannot be applied in your task as you need to brute-force. – kub0x Nov 11 '19 at 21:29
• @TriggeredBoomer It is said that it's Bob's secret key that is small. – corpsfini Nov 12 '19 at 11:25

(in DH) Bob used a small secret key that can be brute-forced.

If the private key is $$k$$-bit, a meet in the middle attack allows private key recovery with cost $$O(2^{k/2})$$ group operations (here, multiplication in the modulo $$p$$ group $$\Bbb Z_p^*$$).

In its simplest form: we know Bob's public key $$y=g^x\bmod p$$ and want the $$k$$-bit $$x$$. We choose $$a$$ with $$\log_2(a)\lesssim k/2$$, compute and enter in a hash table the $$a$$ values $$y\;g^{-a\;i}\bmod p$$ with $$0\le i and the corresponding $$i$$ (each additional value is computed with a single multiplication modulo $$p$$ by $$g^{-a}$$). Then we search in this table the $$g^j\bmod p$$ with $$0. When we have a match, $$x=a\;i+j$$.

There are various optimizations: we can make the table more compact by perusing the near uniform distribution of the values in the hash table, truncate these values to below $$k$$ bits and filter out any false positives. For more time/memory tradeoffs see Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.

Update: but now that I have seen the linked files, this general method (while working) is way overkill.

We have Bob's public key (or "contribution") $$y$$ that is much shorter than $$p$$ is, and $$g=3$$. The simplest way (and in fact, the only known way for a good choice of $$p$$) to have such a small $$y$$ is that $$x$$ is very, very small and $$g^x\bmod p$$ is $$g^x$$. We thus we want to check if $$y=g^x$$ has a solution $$x$$ in $$\Bbb N$$ (hint: take an approximation of the logarithm on both sides to get an approximation of $$x$$, then check that guess). If we get Bob's secret $$x$$, then we can proceed the way he did to decipher the flag.

• Hey! Thanks for the answer, but I am kind of a beginner with cryptography and this actually looks way too difficult to implement. Any other input would be of great help. – user74043 Nov 12 '19 at 4:39
• @TriggeredBoomer: I have put as much hints as I'm willing to do. – fgrieu Nov 12 '19 at 10:58