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

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!

• What exactly are you trying to prove? Informally and intuitively any key exchange protocol without any form of authentication is vulnerable to MitM attacks. So I interpret that you are assuming that no authentication can be done, and want to prove vulnerability to MitM. You can probably formalize this, but this result should not be surprising. – CurveEnthusiast Dec 2 '16 at 6:11

## 1 Answer

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.

• This is what I was going for, but as a recent entry to cryptography from a very pure mathematical background I haven't quite developed a "feel" for what constitutes a proof in the area. Thanks for giving me a framework to work in for this example. – E. Postlethwaite Dec 2 '16 at 14:05