Diffie-Hellman Key Exchange attack on small secret keys 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.
(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&lt;a$ 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&lt;j\le2^k/a$. 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.