Defending MITM attacks during key exchange

As far as I know, key exchanging algorithms are vulnerable to an active MITM attack.

Let A (Alice) and B (Bob) be parties with no secret information. An adversary C playing man-in-the-middle interacts with A pretending to be B, and interacts with B pretending to be A. At the end, C establishes a separate channel with A and with B. Then, any message sent by is decrypted by C (using the key generated with A) and then re-encrypted (using the key generated with B) and sent to B. Likewise, in the other direction. (source)

In this case, both Bob and Alice are unaware of the MITM attack. However, since the public key are modified, they can ensure that they are having a secure channel by ensuring their (alicePubKey + bobPubKey), or simplier, hash(alicePubKey + bobPubKey), is same.

Given that Alice and Bob have no pre-shared secret, C can always pretend to be A or B because there is no way to confirm who they are talking to. However, it is possible to detect the relaying of the message using some hash-and-signing magics, like attaching authentication tags for the messages?

The public key of Alice and Bob have to be modified by C, so I think this could be a good place to start. I am looking for existing implementation that meet such requirement or an explanation of such thing is impossible to achieve.

However, since the public key are modified, they can ensure that they are having a secure channel by ensuring their (alicePubKey + bobPubKey), or simplier, hash(alicePubKey + bobPubKey), is same.

Given that at this point we are talking about DH key shares, hashing the shares as a means of key MITM detection doesn't quite work. The Machine-In-The-Middle attacker is able to fool MITM detection.

However, is it possible to detect the relaying of the message using some hash-and-signing magics, like attaching authentication tags for the messages?

This is a good starting point. In fact, the well-known authenticated key exchange protocol in TLS 1.3, does something along those lines. That is, each participant signs the hash of all messages so far. Since it is based on the SIGMA that I described here, the key exchange also includes a "key confirmation" step done with a MAC over the signature. But one has to be careful how you combine things, since there are a lot of variants that would be insecure.

This is a high-level description and there are many pitfalls, so I recommend reading the SIGMA paper as it discusses a lot of the possible issues. I can also recommend this seminal paper by Bellare & Rogaway on formalizing key exchange protocols.