I want to implement a network of HSMs to secure millions of private keys. To increase fault tolerance and speed, I would want this network to run RAID 50 (striping, parity and duplication). As I understand, one of the key point of HSMs is that they never share their keys. Does this mean that I just cannot run RAID (because I cannot replicate keys)? Or that “normal” server network with some crypto software would be just as good as a HSM network for this purpose?
Yeah, don't. That is to say, don't assume you will be storing 1m+ keys on an HSM, regardless of who made it. HSMs are not hard drives. Don't use them like one.
Some HSMs support external keys. These are keys which are encrypted/wrapped using a specific AES-256 (for example) key, derived from some other key. This 'master' key derivation key remains in the HSM.
Store your 1m+ keys on a raid array, or using an RDBMS, or hadoop, or whatever. It. Does. Not. Matter. from the viewpoint of the HSM. What matters is the latency on searching, finding, reading and sending the key to the HSM for decryption and use.
Most HSMs provide a way to cluster, so that if one HSM isn't fast enough for your use case, you can gang a second (or third, or fourth, or Nth) next to it. These cluster machines use the same master key derivation key, so any one of them can decrypt the key, use it and discard it, without ever exposing it or risking compromise.
I've generated 1m keys (RSA 2048) on a cluster of HSMs of different speeds (I think there were 10, but it was what was in the lab at the time, and it was on a lark so I wasn't keeping notes). It took 10 hours to generate them. Used a MySQL instance in a VM for storage.
Do the keys need to be in the HSM?
Scenarios like this often are solved by not having a million separate secrets in HSM, but by having a million encrypted secrets and having a HSM decrypt them if needed.
In your mind, what's the conceptual difference between secure storage and use of a million keys versus a million passwords (assuming that they need to be recoverable for some reason), or a million creditcard entries?
HSMs are available that are built for this usage, look up "clustered HSM".
Another option is to have a regular security database that is protected by the HSM (either a card in a slot, or available on the network). You could then use one or more HSMs to protect your high availability certificate storage servers. Of course depending on your actual requirements for key storage this might not be acceptable, but it should be less expensive than clustered HSMs.
Keep in mind that you can duplicate HSMs. Consult the manufacturer, but they have procedures for doing this for a variety of circumstances. In fact you may want to simply consult with several manufacturers regarding your needs entirely, they may have solutions you've overlooked.
There are purpose built HSMs in the market for this very requirement. With these HSMs you only store your KEKs (key encryption key) in the HSMs, the actual key / customer data is encrypted by the KEK and stored in a relational database - outside of the HSMs. Whenever the data needs to be decrypted, the request to the HSM is sent along with the data (from the database, encrypted under the KEK) and the handle / identifier of the KEK to be used for decryption. The operation is completed by the HSM in its secure environment and the response sent back to the requesting application.
Thales nShield HSM is one such device available and you are only limited by the size of your database, enabling you to store as many keys / data encrypted under the protection of a master key (KEK) on the HSM.