It seems that the SSH designers cared a great deal about man in the middle attack.
Their approach was, to save server's public key finger print at the first time you're connected to the server (and hope that the user doesn't connect from a poisoned network in the first time, for instance if he has a virus in the computer). The user then uses the fingerprint to verify the server's public key next time he'll connect to this server.
In practice, I found out that many user simply ignores warnings about unmatched fingerprints, and assume it's due to server re-installation. It's just MITM attack is so difficult to conduct and rare, you never worry about it. Moreover, many times a user wants to use ssh many different computers, and he wouldn't bother importing all the fingerprints to any computer he might want to use SSH with (hey, can you look why my site is down, I'm panicked! I'm not in the office, I'll drop to the nearest internet cafe and have a look).
To be fair, one can use DNSSEC and use the DNS servers as the CA. However I never saw that used in practice. And anyhow, it's not a mandatory part of the protocol.
Many years I thought one cannot avoid MITM without preshared secret, but I've been recently reading Bruce Schneir's excellent "Practical Cryptography", there he mentions the interlock protocol.
- Alice sends Bob her public key.
- Bob sends Alice his public key.
- Alice encrypt her message using Bob's public key. She sends half of the encrypted message to Bob.
- Bob encrypts his message using Alice's public key. He sends half of the encrypted message to Alice.
- Alice sends the other half of her encrypted message to Bob.
- Bob puts the two halves of Alice's message together and decrypts it with his private key. Bob sends the other half of his encrypted message to Alice.
- Alice puts the two halves of Bob's message together and decrypts it with her private key.
Now, Mallory has to send something to Bob in step (3) of the protocol, after he receives half of Alice's message, even though he can't decrypt it until he gets everything from Alice in (5). He must fabricate a message to Bob, and Bob is likely to notice he's fabricating, say, after he ls his home directory.
Why didn't SSH use such a scheme? It seems to really fit its goals. It doesn't require any other entity, and it makes MITM attacks substantially more difficult.
Is it something inherent? A flaw in my understanding of the problem? Or just the designer thought the extra security doesn't worth complicating the protocol?
PS:
If you think that it would cause too much overhead, you can force the users of the protocol to use interlock only for the first 10K of data in the connection, so in practice it wouldn't matter too much, but MITM would be more difficult never the less.
Update: The attack on the interlock protocol described here, does not mean a MITM attack is possible, it does mean that if a single password is sent during the communication the MITM can intercept it and the user would only see a time out error.
Update 2:
The point Eugene, raise is valid. The interlock protocol doesn't allow authentication. That is, you still can't be sure that if you're connecting to example.com, it is indeed example.com, and not malicious.com impersonating to example.com. You can't know that for sure without, say, DNSSEC. So for example, if you're SSHing to the missles silos, and write launch_missile -time now (without, say, using ls to verify the server is indeed the server in the missiles silos), it might be that you actually wrote that in a malicious server, and now the enemy know you're about to launch missiles against him. This type of attack indeed won't be prevented by the interlock protocol.
However if I understand the protocol correctly, a much more dangerous attack, and very practical attack, might be prevented. If the interlock protocol is used, even if you don't know anything about example.com, it is impossible that you would SSH to your server, and someone would eavesdrop to the entire SSH session. I think that this type of attack is much more likely.
Maybe SSH don't care about MITM attack? I think not, see for instance Putty FAQ:
Those annoying host key prompts are the whole point of SSH. Without them, all the cryptographic technology SSH uses to secure your session is doing nothing more than making an attacker's job slightly harder; instead of sitting between you and the server with a packet sniffer, the attacker must actually subvert a router and start modifying the packets going back and forth. But that's not all that much harder than just sniffing; and without host key checking, it will go completely undetected by client or server.
He's clearly talking about MITM attack and not about server authentication. I think using the interlock protocol will clearly prevent the attack mentioned in the Putty FAQ and I still don't understand why didn't they use it.
I don't see how interlock protocol prevents MITM.
The problem is not how to exchange keys, but how to trust them. You correctly point out, that people ignore warnings that the keys don't match. This is really the biggest flaw, but the protocol you describe doesn't solve the problem of verification of key origin. SSL uses X.509 certificates and PKI to verify trust. SSH can also use certificates, but almost no SSH software supports them.