# Transmit half the bits of the $g^a$ and $g^b$ as MITM countermeasure in DH key exchange?

I remember this trick from one of my crypto courses way back then, but I can't find the details, and I'm unable to figure out the logic behind it.

I'm talking about a countermeasure to the MITM attack on "plain" (textbook, unauthenticated) DH key exchange. It was something like Alice and Bob compute $g^a$ and $g^b$ (respectively, where $a$ and $b$ are their randomly chosen not-to-be-disclosed values), but first transmit half the bits, and only after receiving the first half bits of the other party, then transmit the remaining half (example, if Alice's $g^a$ is 0x12345678, then transmit first 0x1234, and only after receiving Bob's first half, then transmit 0x5678).

My memory of the description of such trick is that Mallory (the MITM attacker) somehow needed to commit to something based on the first halves, but somehow what Mallory needed required the complete $g^a$ and $g^b$, which, by the time he/she gets those, it is too late and he/she cannot change the value now without being detected.

Does this ring any bells to someone? What part am I missing? I can't see how simply transmitting the first half, and only transmitting the second half after receiving the other party's first half would prevent Mallory to play MITM --- he/she just plays the game with Alice and Bob separately.

Thanks!

• I have to object to your comment that "Nothing cryptographic can" [prevent a MITM attack]. Certainly, real-world cryptographic tools build upon DH and they do provide certain (reasonable) degree of guarantees against MITM or any other known attacks, right? There are certainly tricks that can ensure that one is directly communicating with the other party, with no MITM being able to decrypt one's communication. (right?) Feb 3, 2018 at 18:29
– fgrieu
Feb 4, 2018 at 19:36

The question's technique does not prevent a Man in the Middle attack, for the reasons stated in the question. Nothing cryptographic can, under the question's assumption. Pre-existing trusted material allows that, and is used to that effect in authenticated DH.

What the question's technique achieves is

• Give more insurance to Alice that the shared secret that she will use can't have been chosen to have certain properties, because the other party's secret exponent $b$ can't be chosen with knowledge of the full $g^a$ chosen by Alice. When doing the normal way (where Alice reveals $g^a$ in full before receiving $g^b$), the party communicating with Alice (no matter who) could chose $b$ such that $(g^a)^b$ has (for example) its low-order 20 bits set to zero, then send the corresponding $g^b$ to Alice; exploring $b$ sequentially, this require only about a million multiplications.
• Make it harder or impossible to tell if Alice has chosen a somewhat poor value of $a$ before going as far as the second message sent by Alice, so that analysis of logs of failed connections will have more chance to reveal an attack forcing repeated connections until such poor choice (no answer from Bob on the first message can simply mean that Bob is offline; no answer on the second message, repeatedly, can't have this simple explanation and should raise alarm).
• More generally, lessens the asymmetry in timing of information disclosure between the originator that sends the first message, and the other party.

That might guard against some attacks, or make some security proofs possible.

For example, the question's technique might at least partially mitigate an attack where Mallory, actively performing MitM during key exchange, tries to make Alice and Bob compute a common shared secret that Mallory also knows, which then allows Mallory to passively eavesdrop later direct communication between Alice and Bob, encrypted under a symmetric key derived from the shared secret. There's an illustration in the second section.

If additionally the convention exists that the originator sends the high half first, while the other party sends the low half first, then:

• Assuming authenticated symmetric encryption from the shared DH secret, this blocks a denial of service by reflection attack where Alice is made to communicate with herself by always sending back to Alice whatever message she sends.
• This could have some (hopefully strengthening) effect on protocol attacks that attempt to change originator/target roles.

Half-baked construction where the question's practice mitigates MitM even so slightly.

Start with naive Diffie-Hellman key exchange to establish an encryption key in $\mathbb Z_p^*$ with prime $p$ and $g\in\mathbb Z_p^*$ with $g\ne1$ (perhaps a generator). Normally the protocol goes:

• Alice draws random secret $a$ and sends $m_a=g^a\bmod p$ towards Bob
• Bob draws random secret $b$ and sends $m_b=g^b\bmod p$ towards Alice
• Alice receives alleged $\hat m_b$, computes $s_a={\hat m_b}^a\bmod p$, then $k_a=\operatorname{SHA-256}(s_a)$ used as a secret shared key for a symmetric cryptosystem.
• Bob does similarly and ends with $k_b=\operatorname{SHA-256}(s_b={\hat m_a}^b\bmod p)$, which if everything went well is the same as $k_a$.

Mallory playing active attacker could perform a classic MitM (where he plays as Bob to Alice, and as Alice to Bob), and have Alice and Bob use $k'_a$ and $k'_b$ that Mallory knows. But that leads to different $k'_a$ and $k'_b$, and Mallory has to decipher then re-encipher all symmetrically-enciphered messages between Alice and Bob. That's at least a chore for Mallory, and might lead to his active snooping to be detected.

Thus Mallory wants $k'_a=k'_b$. With the basic protocol above, he can achieve this my making $\hat m_a=\hat m_b=1$, $\hat m_a=\hat m_b=p+1$, or $\hat m_a=\hat m_b=p$, which will lead to $s_a=s_b=1$ or $s_a=s_b=0$, hence $k'_a=k'_b$ and known to Mallory. The question's countermeasure won't help against that, but the simpler countermeasure that Alice checks $s_a>1$ will block it. We assume that from now on.

Mallory can still succeed with fairs odds by sending $\hat m_b=p-1$. With odds about 25%, $a$ and $b$ will both be odd, giving $s_a=s_b=p-1$. If $g$ is a generator of $\mathbb Z_p^*$, Mallory can even force Alice to use odd $a$, by having Alice retry until ${m_a}^{(p-1)/2}\bmod p\ne1$ (which insures $a$ odd); same for Bob. The question's technique starts helping, even so little: Mallory can no longer determine the parity of $a$ from what Alice first sends, and must allow the protocol to advance to the second step for Alice before Mallory aborts it, or not.

Note: I tried to find attacks that work even if further it is checked $s_a<p-1$ or something similar intended to block the above, but so far found none. I welcome these (there's an open question), and vaguely conjecture that the question's countermeasure is likely to mitigate such other attack, if any.

What you are describing sounds like a variation on the interlock protocol, which is a strange creature that

• is completely useless for anything except for a club of chess grandmasters whose criterion for admission is to defeat an existing grandmaster in the club, and yet
• persistently remains seductively alluring to passersby who are not yet convinced that it is fundamentally impossible for two parties who know nothing about each other a priori to establish an authenticated shared secret.

To wit, how does Alice know whether to do the interlock protocol with Bob on Monday or on Tuesday, if Mallory can initiate the protocol on whichever day they like?

• The reference to the interlock protocol is spot-on!
– fgrieu
Feb 6, 2018 at 9:33
• I don't think it is completely useless (in practice yes, due to the alternative approaches that work much better for a wider range of scenarios) --- two parties that do know about each other still have no way to guarantee that there is no MITM using DH, but they can with this interlock protocol (unless I'm still missing something?). Either Monday or Tuesday without prior agreement, once the communication is established, they can authenticate each other based on challenges that rely on their a priori knowledge of each other, no? Feb 6, 2018 at 20:34
• If you can share knowledge a priori, then that is what provides the authentication, not the interlock protocol. Feb 6, 2018 at 21:49
• The question never was about authentication, it was about ensuring that there isn't an eavesdropper. (With authenticated public keys, that comes for free, sure). But the parties authenticating each other based on prior knowledge but without any prior arrangement for the communication does not guarantee the absence of a MITM (and that is a reasonable/realistic scenario: we know each other and once we're communicating we can tell each other from any, or say most adversaries, but one of us asynchronously decided to contact the other without having arranged for that communication) Feb 7, 2018 at 1:44
• If your hash-based challenge-response protocol using a prior shared secret can't detect a MITM, then it's not a very good authentication protocol, is it? If your authentication protocol does work, like many password-based key agreement protocols or like the socialist millionaire protocol on top of DH key agreement (provided it covers both the prior shared secret and the DH session key), you don't need the interlock protocol. Feb 7, 2018 at 17:58