6
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – CurveEnthusiast Dec 2 '16 at 6:11
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – E. Postlethwaite Dec 2 '16 at 14:05

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.