# modfied man in the middle attack diffie hellman

I have been given a problem in preparation for my cryptography final that I'm not sure how to solve. It asks me to suppose a scenario where instead of where an attacker would intercept some message from Alice ($g^a$) mod p and ($g^b$) mod p from bob, and then replacing each of these with $g^e$, the attacker would replace it with $g^q$ where $p=mq+1$, $p$ is the large prime upon which Alice and bob have agreed, $m$ is a small even number, and $q$ is another prime.

1. Why are there exactly $m$ values for $k$?
2. Why is this attack any better than the attacker simply raising $g$ to their own value ($e$)?

Why are there exactly $m$ values for $k$?

Well, assuming $k$ is the value of the shared secret that either Alice and Bob derive, well, that's not true; there are at most $m$ possible values, however it may be fewer. There will be exactly $m$ values if $g$ is a primitive root modulo $p$; however when we use Diffie-Hellman in practice, we generally avoid using a primitive root.

To understand why there are at most $m$ possible values, we need to look at Fermat's Little Theorem; one way of expressing it is:

$g^x \equiv g^{x \ \bmod\ p-1} (\bmod\ p)$

(This isn't the standard way of writing it; this formulation works out fairly well for this purpose).

The other thing to look at the Diffie-Hellman operation with the modified messages, where Alice computes:

$k = g^{aq} (\bmod\ p)$

And we ask ourselves "how many distinct values can $aq \bmod\ p-1$ take on?" (Hint: consider the Chinese Remainder Theorem).

You're supposed to be learning, hence I'm not giving you the full answer; I hope these hints are enough for you to fill in the missing pieces.

Why is this attack any better than the attacker simply raising $g$ to their own value $e$?

Well, in practice, it won't be any better; any secure protocol that uses Diffie-Hellman must have a story why an attacker who modifies the messages cannot gain an advantage; such protection will foil both attacks.

However, I believe the answer they're looking for starts with "if the attacker replaces both values with his own value $g^e$, then both sides will always derive different shared secrets (and hence different session keys); to continue the attack, the attacker must decrypt each sides messages, and reencrypt them with the keys shared with the other side. However, if the attacker replaces both values with $g^q$, then with probability $\ge 1/m$, [fill in details here]

• That second part was what I've come up with so far. But I have no idea how to show that aq mod p can actually only take on m values. Shouldn't it be able to take on a mod p values? – user979616 Nov 13 '13 at 17:29
• @user979616: Again, consider the Chinese Remainder Theorem, with $p-1 = mq$; and how many distinct values can $aq \bmod m$ take on, and how many distinct vlaues can $aq \bmod q$ take on? – poncho Nov 13 '13 at 17:31
• aq mod m should only be able to take on m values correct? The Chinese remainder theorem talks about solving a system of equations. I seem to be missing why its applicable here. – user979616 Nov 13 '13 at 17:36
• @user979616: If $a$ and $b$ are relatively prime, and $x$ is an unknown value that is within a known set, and $x \bmod a$ can take on $c$ different values, and $x \bmod b$ can take on $d$ different values, how many values can $x \bmod ab$ take on? – poncho Nov 13 '13 at 17:44
• My assumption is that it takes on the smaller of the two, since that would give me that aq mod(qm) takes on m values, which is what I require. Thanks so much for the help :). – user979616 Nov 13 '13 at 17:48