1
$\begingroup$

This might sound pointless at first, but I want to know if it's computationally feasible to generate the same resulting session key in 2 different DH key exchanges. The purpose would be for a man-in-the-middle attack where both of the unsuspecting target users check to make sure they're using the same session key.

The way I am thinking it would work is that Eve establishes a normal DH key exchange with Alice. She then does a key exchange with Bob where she uses specially-crafted responses to end up with the same session key she generated with Alice.

Is it possible, and how would this work in practice? I'm guessing it would either be impossible or extremely time-consuming with large primes, etc., but that's just a quick assessment. Thanks!

$\endgroup$
  • 2
    $\begingroup$ Note that the nom de guerre of the standard adversary who can modify packets in transit and server as a (hu)man in the middle is Mallory; Eve is normally restricted to eavesdropping. $\endgroup$ – Squeamish Ossifrage Sep 8 '17 at 0:54
1
$\begingroup$

If you're doing Diffie–Hellman in a group $G$ written multiplicatively with identity element $e$, say $G = (\mathbb Z/p\mathbb Z)^\times$ for some standard large safe prime $p$ and $e = 1$, then Eve/Mallory can simply supply $e$ as their public key to both Alice and Bob. Then the shared secret group element is $e^a = e = e^b$.

There is a way for Alice and Bob to thwart this, by simply checking whether the peer's public key is the identity element. But it's usually pointless because Alice and Bob will normally authenticate the entire transcript of the session—this thwarts the attack anyway because they will authenticate $g^a$ and $g^b$ as their public keys, not $e$.

$\endgroup$
  • $\begingroup$ In $(\mathbb Z/p\mathbb Z)^\times$, supplying $p+1$, or $0$, or $p$ as the alleged $g^b$ could also work. Supplying $-e$ (that is $p-1$ in $\mathbb (Z/p\mathbb Z)^\times$ ) might also work, with probability 50% (if $a$ and $b$ have the same polarity). Other solutions welcome, I wonder if they are blocked or not by this practice. $\endgroup$ – fgrieu Feb 5 '18 at 7:02
  • $\begingroup$ Well. Yes, you should verify the alleged input is in $(\mathbb Z/p\mathbb Z)^\times$, which (the cosets of) $0$ and $p$ are not; and if you distinguish $1$ from $p + 1$ rather than treating them as representatives of the same coset which is the identity element, then you should check for that too. More generally, a protocol (unlike a casual crypto.se post!) should be defined in terms of the bit string representations of everything involved, and should be prescribed as total functions so there's no leeway for implementation variance—and errors. $\endgroup$ – Squeamish Ossifrage Feb 6 '18 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.