How modern SSH key exchange provides (strong) protection against attacks
Sometimes I write blog entries without doing (enough) research, and this results me in getting to be wrong in public. Yesterday I wrote about how I thought SSH had to protect public key authentication against some forms of attacks that are closely related to man in the middle attacks; in comments, David Young noted:
The "challenge" [to prove the client has its keys] is built by the client, not supplied from the server, and part of it is a hash of a string that includes the server's public host key.
This made me pay attention, because such a thing is pretty strong protection against a bunch of attacks. So I figured that this time around I should do my research. The short version is that David Young is completely correct, but the result is more interesting and stronger than I expected.
Our basic potential attack is a man in the middle attacker who is terminating your SSH connection; you connect to them and then they want to authenticate to the real target as you, using your SSH public keys. In the weakest attack they're not pretending to be the real target at all; in the strongest attack they're pretending to be the target host and have its SSH host keys.
As quick background, the SSH protocol is divided into pieces; there's a transport layer that arranges an encrypted connection and authenticates host keys, an authentication layer that authenticates you to the server, and a connection and session protocol where you actually do things. The basics of SSH public key authentication is covered in RFC 4252 on the authentication protocol, specifically in section 7. This spells out the collection of data that the client signs to authenticate that it holds the private key, and the very first thing in the blob of data is this:
string session identifier byte SSH_MSG_USERAUTH_REQUEST [...]
The session identifier is a transport layer concept; it's a shared value that's derived independently by both the server and client from data used during the initial set up of (transport) encryption. This means that you cannot authenticate to a server via public key authentication unless you and the server have the same session identifier for your respective connections; if I connect to mallory.com and mallory.com turns around and connects to Github to re-use my SSH public keys, this can only work if mallory.com can arrange for both connections to have the same session identifier.
In this old entry I wrote that I was reasonably
certain that the session identifier could not be controlled this
way. At the time I wrote that entry I was looking at the basic SSH
key exchange algorithms, which involve straightforward use of
Diffie-Hellman. Specifically, they involve the key exchange methods
you're familiar with modern versions of OpenSSH, you may recognize
those names; they're key exchange mechanisms that are so old that
new OpenSSH servers default to not supporting them because they're
now considered too potentially weak. If you have really old clients
(such as Solaris-derived ones),
this may have recently started causing you heartburn.
Modern OpenSSH key exchange mechanisms are generally built around elliptic curve cryptography, starting with standard NIST curves in RFC 5656 and adding DJB's Curve 25519 in an OpenSSH extension. All of these make a change to the overall key exchange protocol, namely that during key exchange, the server and client generate new ephemeral key pairs and these become part of what is hashed to generate the session identifier. These key pairs are used as part of ECDH to arrange the shared secret key, which also becomes part of the session identifier hash.
As far as I can tell, this kills man in the middle attacks stone cold dead even if the attacker has the server's host keys. Unless you can break elliptic curve cryptography in general, you can't recover the private keys for the client's and the server's ephemeral keys, and you need at least them in order to be able to wind up with the same session identifier on both connections. And with different session identifiers, all public key authentication will fail.
(If I'm understanding both ECDH and Diffie-Hellman correctly, plain D-H key exchange also sends things that are rough analogs to the ephemeral keys and includes them in the session identifier hash.)
In addition, as David Young noted, the session identifier computed in both the original Diffie-Hellman key exchange and these modern elliptic curve key exchanges includes the server's public host key. This serves as a second block on attackers who don't have the server's host keys.
(A useful starting point for this sort of research is the OpenSSH Specifications page.)