Key flopping

Idea

Why should protocols like SSH which use public keys for host identification only prove possession of a single public key? (For that matter, much of what can be said about using public keys for identification can be said of certificates, but I'm most interested in using public keys as the example here.)

The typical SSH server may have public keys for a number of algorithms; RSA, DSA, ECDSA, etc. In SSH, client and server both advertise the algorithms they support in order of preference, and the algorithm most preferred by the client and supported by the server is used. There are two issues I would like to address with this scheme, relating to the fact that a single public key with a single algorithm will be chosen and presented.

First, preferences change with time. As changes in algorithmic security, speed, and availability occur, clients and servers will add new algorithms, remove old ones, and change their orders of preference. As a result, a client which has connected to a server using RSA and which now prefers ECDSA will require user intervention to retrieve and authenticate the new ECDSA key even if the RSA one is still available, trusted and believed to be secure.

As a sub-class of that problem, there is the problem that preferences of key length change with time for reasons of security and speed. If a server needs to adopt a RSA-8192 key, it has to get rid of its RSA-1024 key, which is trusted by all previous clients. SSH includes no notion of multiple keys of the same type.

The second problem is that keys may be in some way compromised. This is a large class of problem, and an intractable one, but one worth giving some consideration. Indeed, some kinds of compromise may be mitigated if multiple keys are available and required for verification. If the problem is that e.g. an RSA key may be factored, because an algorithmic weakness has been discovered or because limited entropy was used in generating the key or other similar key-specific weaknesses, then it would be helpful if a man-in-the-middle also had to prove possession of the server's ECDSA key, which it obviously cannot if only the RSA key was compromised.

On the server side, I propose making it possible for a client to ask the server to show proof of possession of all available private keys, and as part of this change to how public keys are verified, to make it possible to show proof of possession of private keys for multiple public keys of the same algorithm. Basically, add a new public key algorithm which is called something like "multikey" or "keyflop" or similar, or provide some other way for a client to enumerate available keys and to ask for proof of possession of any enumerated key.

On the client side, trust-on-first-use (TOFU) should then be expanded to store all verified public keys which the server has proven it possesses the private key material for. On subsequent attempts, clients can choose to either inform the user or automatically make decisions on the basis of new keys appearing, or old ones disappearing, such that possible key compromises can be detected, and support for better algorithms may be phased in without disrupting trust.

Obviously it should be impossible for an attacker to modify the key list by expanding it to include a new key the attacker controls, such that that key would then be chosen and treated as verified by all other keys proven to be available. A list of public keys should be sent, and signatures should be either sent or available on-request for each key, verified the entire, ordered list of keys, e.g. a detached signature on the hash of the public key list concatenated with the preceding session material, in the usual manner of SSH.

This could also be expanded to allow for ephemeral keys to be sent and verified by the other key algorithms, although there is little use in doing so, except for being able to reduce the cost of subsequent key exchanges on the same connection, by using a shorter ephemeral key which was verified stringently early in the connection.

I've referred to this as "key flopping" in the sense of a card game, i.e. that the server is showing its full hand, rather than just a single card. The client thus has more information going forward, and can make a better decision than it would have to make with only a single key, both for this connection and for future connections which may use different key types.

$Id: key-flop.html,v 1.1 2013/11/08 21:02:37 jmallett Exp $