TL;DR

Challenge 35 in Cryptopals.

I know, I know. It says “implement” and I should implement it. But it seems that we’re able to negotiate an alternative value for $g$, and the alternatives call for very insecure results that boil down to settling to a specific and trivial value for the shared secret $s$.

So… well, it’s basically the same code as the last time, only with a different value of the not-so-secret $s$. Let’s start with a little recap about it:

\[s = A ^ m \pmod p \\ s = (g ^ a) ^ m \pmod p \\ s = g ^ {a \cdot m} \pmod p \\ s = g ^ e \pmod p\]

where $m$ is our private key as man-in-the-middle and $e = a \cdot m > 0$.

In case we manage to force $g = 1$, we end up with $s = 1$ because elevating it to whatever non-zero power always yields itself:

\[g = 1 \Rightarrow s = 1 ^ e \pmod p = 1\]

When we trick the peer to accept $g = p$, instead, we’re setting to a zero value for $s$, because whatever the value of the two (non-zero) private parts, the result will surely be divisible by $p$:

\[g = p \Rightarrow s = p ^ e \pmod p = 0\]

Last, when we trick the peer to accept $g = p - 1$, which is the same as $g = -1 \pmod p$:

\[g = p - 1 \Rightarrow s = -1 ^ e \pmod p\]

that is:

\[s = \begin{cases} 1, & \text{if $e$ is even} \\ p - 1, & \text{if $e$ is odd} \end{cases}\]

If we can also trick the peer into giving the public key first, we can adjust our value of $m$ so that we end up with an even value for $e$ and always use $s = 1$. Otherwise, we can just try both possible values to see which of them allows us decripting the peer’s message.

Stay safe and secure!