Managing and storing lots of SSH keys in the cloud

You have to make important distinctions: there are public keys and private keys. When "stored securely", they call for different notions of "securely".

Each SSH server owns a public/private key pair. Each server should generate its own key pair, and the private key should never leave the server itself. The public key is public, meaning that everybody can learn it. When you connect to the server, that's one of the first things that the server tells you: its public key. It shouts it all over the network. When dealing with SSH public keys and their storage, the question is really that of integrity: a given SSH client must remember the public keys of all the servers that it wants to talk to (the $HOME/.ssh/known_hosts file with usual Linux SSH clients); the attacker may want to include a fake public key in there, in order to run a fake server.

Each SSH client may own a public/private key pair: such a key pair will be used for client authentication by the server. If you use password-based client authentication, then the clients don't have such key pairs. If you use key-based client authentication, then each server must know the public keys of "authorized clients" (the $HOME/.ssh/authorized_keys for Linux SSH implementations).

In your case, you have 50 SSH clients talking to 4000 SSH servers. Therefore, using the normal SSH model, you would have to ensure that:

• Each of the 50 clients knows a copy of the public keys for all 4000 servers.
• If using key-based client authentication, each of the 4000 servers must know a copy of the 50 client public keys.

Given these figures, the relevant files will be bulky, and key management will be a problem (if you add a new client, the new client's public key must be imported into 4000 servers, with protected integrity). Public-Key Infrastructures were invented to solve that problem. A raw, "official" OpenSSH instance does not know how to use X.509 certificates; however, a modified version exists (see also that previous question). With an X.509-aware SSH code base, you could run your own Certification Authority (e.g. the open-source EJBCA), and issue certificates for your clients and servers. That way, SSH client and servers will send each other their certificates when needed, dynamically. Each machine will only have to store its own private key and certificate, and also "know" the CA certificate (in the relevant "trust store"). Adding a new client or a new server to the mix then is just issuing a certificate, and the management problem is solved (or, rather, moved around: now you have a PKI to handle).

This is a job for a configuration management software like Puppet, Chef, etc. It was created to handle exactly this kinds of problems. I strongly recommend you use configuration management software if you have so many servers.

In regards to the part about storing keys securely one option is to store the private keys in an HSM (hardware security module). There are a few well known vendors that offer these but there are alternatives. See for example Cryptostick.

The advantage of using an HSM is that the private keys can only be used while the hardware device is present on the system and one cannot copy the private keys elsewhere.

This type of solution would also require proper auditing and management of authorized SSH keys on the SSH servers. Otherwise nothing would prevent an intruder of generating and placing their own set of keys in the SSH server.

Managing those keys however, is a problem. There are commercial products out there for managing SSH keys but I'm not aware of any good open source solution.

As Thomas said one option is moving to a PKI based approach, however this would require updating all your SSH clients and servers.

Disclaimer: I work for a company that sells a commercial SSH key management product.