0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – kelalaka Nov 11 '19 at 16:02
  • $\begingroup$ 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. $\endgroup$ – user74043 Nov 11 '19 at 19:55
  • $\begingroup$ 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. $\endgroup$ – kub0x Nov 11 '19 at 21:29
  • $\begingroup$ @TriggeredBoomer It is said that it's Bob's secret key that is small. $\endgroup$ – corpsfini Nov 12 '19 at 11:25
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user74043 Nov 12 '19 at 4:39
  • $\begingroup$ @TriggeredBoomer: I have put as much hints as I'm willing to do. $\endgroup$ – fgrieu Nov 12 '19 at 10:58