# Are there any protocols that are truly secure from active and passive MITM attacks?

Are there are any cryptographic protocols or algorithms that can prevent active MITM attacks or interference when initiating a new connection to a server or someone you have not exchange keys with before?

For example:

Alice's computer ➜ ISP ➜ Internet ➜ ISP ➜ Bob's server


It is known that ISPs are compromised with secret rooms and equipment in use by the NSA/GCHQ especially in USA and UK. New Zealand feeling left out of the spying debacle decided to follow suit in the last few days and they just passed a law forcing ISPs to assist the GCSB in surveillance.

The chain is now really this:

Alice's machine ➜ ISP (hostile) ➜ Internet (hostile) ➜ ISP (hostile) ➜ Bob's machine


Assume either of the ISPs have some device or person which can do an active MITM attack in real-time. For example it detects a key exchange and instead of serving Alice/Bob the real key they give them the attacker's key instead. Which protocol lets Alice or Bob know a forgery has taken place? If they detect a forgery, does this cause a denial of service for Alice or Bob who can no longer communicate without being monitored?

Let's be clear, Certificate Authorities are not the solution. I'm not even sure systems like Perspectives or Convergence would help as Alice's or Bob's machine still need to connect through the hostile ISP to contact a notary or set of notaries to verify the authenticity of the original public key. How can you do that securely if the ISP is compromised? The ISP can simply make a response back to Alice/Bob pretending to be the notary and saying everything is fine.

So how do you solve the authenticity problem in this scenario and prevent active MITM attacks?

What about if Alice and Bob already have a shared secret key (perhaps exchanged in person), does this solve the problem? What protocols can be used then and do they fully prevent active MITM and denial of service?

-
Would a password count as a key for your first sentence? $\;$ – Ricky Demer Nov 8 '13 at 10:03
SSL does solve this problem. It relies on certificates, which can be guaranteed by a CA, or exchanged beforehand, or other methods which you list. You have the solution in your question, so what are you really asking about? – Gilles Nov 8 '13 at 10:24
@user31425 I don't care to watch that video. It's up to you to make the question self-contained. I am aware that CAs are problematic, but if you don't trust them you can simply exchange certificates beforehand, this is a well-known and very simple protocol. Resistance to DoS is a completely different matter and cannot be done by cryptography — your ISP can trivially cut you off. – Gilles Nov 8 '13 at 10:42
If a shared secret is pre-established and there is a guarantee that only Alice and Bob knows the shared secret. Any old symmetrical encryption is good enough... You can even use the shared secret to generate a time-based temporal key for message transmission. If no shared-secret can be established, then no, you are left with nothing... If you think about it logically, with no third party (e.g CA) involved and given the parameter that EVERYTHING can be faked, how can one identify someone else? – initramfs Nov 8 '13 at 11:06
@user31425 You can run your own CA if you don't like the existing commercial services. If your own system is compromised, you can't hope to retain security. – Gilles Nov 21 '13 at 12:24

In short:

If you assume no shared secret, you can not build anything. For some theory on this, a similar assumption is formalized in the Dolev Yao model (all messages are send via the attacker, assumes perfect encryption), where no unauthenticated key exchange is possible.

If you assume a shared secret, then it depends on the kind of secret to run a number of protocols:

• MITM for key exchange like Diffie-Hellman usually results in a different key for the connection between Alice and Eve and the connection between Bob and Eve (due to DLOG still being hard). So you start with a normal key exchange, but don't use this key for your session straight away.
• run a one-way function on both the session key from the first part and the shared secret. For example you could use a key derivation function on the cocatenation. Eve should not be able to calculate this key, since she does not know the secret.
• Use the derived key as session key or MAC key, or whatever you want to do with it. Eve should not know it, and it can be used to check message integrity (or to notice if Eve already tempered with the first key exchange).
-
No!! A shared secret is definitely NOT necessary to protect against MITM!! Trusted public information (public keys), and corresponding non-shared secrets (private keys) is enough, thanks to public key cryptography. – fgrieu Nov 8 '13 at 16:51
In the question it was stated, that certificate authorities are not the solution. The question was about alternatives. Of course you can build authenticated channels from any PKI scheme easily. But if you assume a hostile ISP, you will never get those trusted public keys. – tylo Nov 11 '13 at 15:32
@fgrieu, but how do you get a trusted or true public key in the first place if you have no shared secret to verify the key you are receiving is authentic? If the attacker is at ISP level they can trivially replace any incoming public key with the attacker's key. How do two parties who have not communicated before verify that this is the true public key from the other person? Before you say CA, that doesn't work when NSLs exist or if your browser's trust chain is loaded with a few dodgy CA certificates. – user31425 Nov 21 '13 at 9:50
@tylo Thanks for your answer, regardless of the naysayers. – user31425 Nov 21 '13 at 9:53
@user31425: A standard method to establish Alice's trust in Bob's public key is that Bob reads aloud a hash of his public key in front of Alice (it then does not mater how the aledged public key reached Alice: she can check it using the trusted hash). But if Alice neither has or had any channel from the real Bob to her, assumed safe from alteration; nor trust a third party; then there is no method for her to establish a secure channel with Bob. Proof: assume there's a method; anyone can apply it just as Bob, and will succeed to impersonate as Bob to Alice. – fgrieu Nov 21 '13 at 17:19