Tuesday 17 February 2015

Hostkey rotation, redux

A couple of weeks ago I described the host key rotation support forthcoming in OpenSSH 6.8. Almost immediately after smugly declaring "mission accomplished", the bug reports started rolling in. First Mike Larkin noticed an interaction with ssh's CheckHostIP option that would cause host key warnings, then Theo de Raadt complained about the new code unnecessarily rewriting known_hosts when no changes needed to be made, finally Philipp Kern and Jann Horn pointed out a way for a hostile server to abuse the extension.

Given all this, I disabled the feature and went back to the drawing board. Host keys handling has long been one of my least favourite parts of OpenSSH - the code is poorly tested, mistakes might catastrophically break host authentication and there are lots of overlapping and interacting features (e.g. host key hashing, the aforementioned CheckHostIP, host with port specifiers, CA / revocation markers). So my first task was to improve the API to make it possible to solve the CheckHostIP interactions and add some sorely-needed unit tests for it (well, at least of the code that I was going to be fiddling with).

The abuse problem was more tricky - the attack was:

a malicious server (say, "host-a") could advertise the public key of another server (say, "host-b"). Then, when the client subsequently connects back to host-a, instead of answering the connection as usual itself, host-a could proxy the connection to host-b. This would cause the user to connect to host-b when they think they are connecting to host-a, which is a violation of the authentication the host key is supposed to provide.
The fix for this is to have the server prove to the client that it has the private keys that correspond to the public keys that it offers. Unfortunately, this is a little fiddly since we don't want to have to calculate and send signatures for each of a server's host keys on every connection (it's slow and expensive) and we can't precompute the signatures (otherwise a hostile server could just replay them and the above attack is back on). So I settled on a way for a client to ask the server to prove ownership of particular keys, allowing a flow like this:

S->C: hostkeys@openssh.com; list of public hostkeys
Client: Check known_hosts, see which keys are new
C->S: hostkeys-prove@openssh.com; new keys server must prove ownership of
S->C: (reply); private key signature for each key

The signatures proving ownership of the private keys are bound to the specific connection instance, so they cannot be replayed. Unfortunately, this means that the hostkeys rotation support is a little less useful: it is not longer possible to offer public keys without having their private halves online to complete the proofs. I hope to bring this capability back in a future release, perhaps by (ab)using the certificate format to allow pre-computed proofs that are tied to specific hostnames.

The host key proof extensions are now committed to HEAD. I also added a UpdateHostKeys=ask mode that prompts the user for confirmation before modifying known_hosts, since that seemed reasonable and symmetric with StrictHostkeyChecking=yes. Anyway, if you are interested in this then please try out HEAD and/or review the code or protocol specification.


  1. Could you use some cross-signing kind of method to introduce new keys without having them online? S advertises two keys, A and B, and is in possession of A. During connection S proves to C the possession of A. In order to convince C that it should also associate B with this S, S sends Sig_B(A) (in a channel that's authenticated with A).

    1. That's possible, but is more fiddly in an area that I don't want to introduce more fiddlyness. The scheme I was thinking of in the future was adding another certificate type that was self-signed, proving ownership of a private key and binding it to one or more hostnames.

      A client could receive these in a hostkeys@openssh.com public key advertisment and, if the hostname therein matched the target host, treat the public key as trusted.

      A hostile server could replay these certs to its clients, but it wouldn't do it any good because they would only be valid for the names listed inside them.

    2. I'm a bit unsure whether I understand this correctly:

      So the prove of having the private key would be made by having the public key selfsigned with that.
      And that signature would also go over the host's name(s).

      So while an attacker might get into posession of that cert... and could try to use it for the same attack described by Philipp and Jan, it would be noticed because of the signed host name.


      Some questions:

      a) What's the big benefit of having the private keys offline?
      - If the node is compromised and this is noticed... well we don't have really a CRL like system... so even while the attacker couldn't use the new (offline) priv/pub key pair, for attacking, he could still use the old one (because when he was on the system, he likely has them).

      - If it's not noticed, than you're screwed anyway, because the attacker just waits until you place the offline keys online.

      - And, if an attacker gains root, he can always just distribute new keys with that mechanism,... maybe he does it just for a few weeks and removes his traces then, the clients store these keys automatically, and in the future they can be used by him.
      This in particular makes the whole auto-distribution even a bit more questionable.

      b) If you plan for some more powerful key type anyway,... why creating now more fiddlyness with the traditional host keys?
      I think they were never really meant to be in a certificate-fashioned fully automated way.
      And actually that's one of their strengths, to my mind. Every key must be securely exchanged (unless one is dumb and just accepts the key blindly), no hidden surprises with things like CAs, that a rouge CA can do many evil things etc.

      And you say that most things can be done with SSH certificates anyway? So if people need such features like key rolling, then they should use these.

      Last but not least:
      c) If really a new auth key type was added... some brainstorming (of really not fully ended thoughts):

      - can existing PKI systems (NOT X.509!) be somehow utilised... thinking of OpenPGP, which would provide strong authentication and at least some form of redundant directory with key revocation capabilities (the SKS keyserver network)... the downside... people may start to hate us, when we start placing our server keys to their networks thereby polluting them

      - which opens another (perhaps dumb) idea: right now we trusts hosts... could it make sense to start trusting people?
      Something like "OpenSSH shall trust any server host keys for *.kernel.org when signed by the OpenPGP key from Linus Torvalds".
      (Guess I should have better made an deRaadt example here *sry*)
      Of course this brings back the problem of how to properly revoke keys.


    3. Perhaps a further word about the issue that an attacker could misuse that feature to spread his own keys via a compromised host:
      Even it it's noted that such host was compromised and if the admins may notify all people about that.... it could be still difficult to remove all such "eastereggs" distributed by an attacker.
      Just consider when hostkey hashing is enabled.

  2. Maybe I'm just paranoid, but I'm a bit concerned about the possibility that a key exchange message might also be a valid host key proof. As far as I can tell, during the key exchange, the server signs a message that starts with the client's version string.
    Aside from nullbyte issues, this looks to me as if it might nearly allow an attacking server to send fake host key proofs on something around 2^(-60) of all its incoming connections (those with a session ID that matches "SSH-%d.%d-%[^\n]") by forwarding a key exchange message he got from another server when using the victim client's session ID followed by "hostkeys-prove@openssh.com" as his version string.
    (He wouldn't be able to control all the key material, but at least in RSA, being able to specify garbage as the modulus or so should make it fairly easy to break the key, right?)

    This is a fairly theoretical attack, I guess, but how about moving the unique string "hostkeys-prove@openssh.com" to the front of the signed data so that it's easy to prove that no string can both be a valid plaintext for the key exchange and for host key proofs?

    1. I think the framing is too different, compare https://tools.ietf.org/html/rfc4253#page-23 and https://anongit.mindrot.org/openssh.git/tree/PROTOCOL?#n310

      The hash format is different too - in KEX, the signature is computed over a hash of the above fields (in addition to the signature scheme's internal hashing). For hostkey proofs, the signature is calculated over the fields directly.

      You'd also have to smuggle the entirety of the client and server KEXINIT packets into the key material somehow. If you do this then you are only advertising a broken key for yourself.

    2. Ah, ok. Thanks for the clarification!

    3. I had to rename the protocol extension to avoid compat problems for people running HEAD as I fiddled with it, and took the opportunity to reorder the signed data so the string is first too.