Proof that any key exchange protocol is vulnerable to MitM attacks in the absence of shared information or trust

Question

Today I realised that every key exchange protocol I know, without a priori any shared information or trust relations (i.e. any ability to sign anything), is utterly broken by an active man in the middle attack.

I asked a professor of mine today whether there a proof of this in a formal setting and he said "yes, it's something information theoretic but I can't quite remember what..."

I looked in (what I believe to be) the relevant chapters of a couple of textbooks I have to hand, and done some google-ing and turned up nothing. I was wondering if someone could point me in the direction of either a paper or a text book containing such a proof. Thanks!

Answer 1

It has nothing to do with information theoretic. You just need to construct an adversary and argue that it works. In this case, the adversary is simple. Let $A$ and $B$ 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.

Since there is no initial secret, $A$ and $B$ see exactly the same thing as they would see in a key exchange that is not under attack. However, $C$ learns everything communicated.

The difference between this and a full proof is minimal.