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?
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?