How do certification authorities store their private root keys?
Serious certification authorities use heavy procedures. At the core, the CA key will be stored in a Hardware Security Module; but that's only part of the thing. The CA itself must be physically protected, which includes proactive and retrospective measures.
Proactive measures are about preventing attacks from succeeding. For instance, the CA will be stored in a vault, with steel doors and guards. The machines themselves are locked, with several padlocks, and nobody holds more than one padlock key. Physical security is of paramount importance; the HSM is only the deepest layer.
Retrospective measures are about recovering after an incident. The HSM will log all signatures. The machine is under 24/7 video surveillance, with off-site recording. These measures are about knowing what has happened (if you prefer, knowing a priori that, should a problem occur, we will be able to analyze it a posteriori). For instance, if "illegal" certificates have been emitted but the complete list of such certificates can be rebuilt, then recovery is as "easy" as revoking the offending certificates.
For extra recovery, the CA is often split into a long-lived root CA which is kept offline, and a short-lived intermediate CA. Both machines are in the cage and bunker; the root CA is never connected to a network. The root CA is physically accessed, with dual control (at least two people together, and video recording) on a regular basis, to emit the certificate for the intermediate CA, and the CRL. This allows revoking an intermediate CA if it got thoroughly hacked (to the point that its private key was stolen, or the list of fraudulently emitted certificates cannot be rebuilt).
Initial setup of a serious root CA involves a Key Ceremony with herds of auditors with prying eyes, and a formalism which would not have been scorned by a Chinese Emperor from the Song dynasty. No amount of auditing can guarantee the absence of vulnerabilities; however, that kind of ceremony can be used to know what was done, to show that security issues have been thought about, and, come what may, to identify the culprit if trouble arises. I have been involved in several such ceremonies; they really are a big "security theater" but have merits beyond the mere display of activities: they force people to have written procedures for everything.
The question is now: are existing CA really serious, in the way described above ? In my experience, they mostly are. If the CA has anything to do with VISA or MasterCard, then you can be sure that HSM, steel and ill-tempered pitbulls are part of the installation; VISA and MasterCard are about money and take it very seriously.
For the CA which are included in Web browsers and operating systems, the browser or OS vendor tends to require a lot of insurance. There again, this is about money; but the insurance company will then require all the physical measures and accounting and auditing. Formally, this will use certifications like WebTrust.
This is true even for infamous CA like DigiNotar or Comodo: note that while they got hacked and fake certificates were issued, the said certificates are known and were revoked (and Microsoft added them to a list of "forbidden certificates" which can be seen as a kind of "revoked, and we really mean it" -- software must go out of his way to accept them nonetheless).
The "weak" CA are mostly the State-controlled root CA. Microsoft can refuse to include a root key from a private venture, if Microsoft feels that enough insurance has not been provided (they want to be sure that the CA is financially robust, so that operations can be maintained); I know of a bank with millions of customers who tried to get their root key included in Windows, and were dismissed on the basis that they were "too small". However, Microsoft is much weaker against official CA from sovereign states; if they want to do business in country X, they cannot really afford to reject the root CA key from government X. Unfortunately, not all governments are "serious" when it comes to protecting their CA keys...
On the physical side they first keep the root CA completely offline. Typically what happens is that they set up the root CA, make subordinates, then take the root CA completely offline and take the hard drives and HSMs (sometimes even the whole server) and essentially lock them in a safe.
Next, they segment the network to keep those subordinate/issuing CAs secure.
Finally, on those subordinates they use HSMs to store the certificates.
OCSP and CRLs are used to revoke certs, but it's not just that simple.
On the procedural side, they have a crazy amount of layers including locked rooms that require multiple people at the same time to revoke/sign subordinates or roots (A Key Signing Ceremony). These are 24/7 recorded (audio and video) and require a person of trust from the CA, in addition to the admins and executives. It's a huge deal. Here's the video.
Edit: Contrary to what Polynomial has said, from what I have seen, HSMs are commonplace for CAs, and even for large implementations of internal CAs.
Not every CA (government, commercial, or private) stores private keys the same way. Most legitimate operators use a HSM. It's possible that the vendor publishes CRL revocation lists using a one way link from the root to the SubCa. (Transmit-only serial cables, audio cables, QR codes, Ethernet with only a few pins connected.... etc.)
To get specific then it really depends on what product you're talking about.
For example, every phone (Android, iPhone, Blackberry), Operating System (Linux, Windows, etc), and even some web browsers (Firefox) maintain independent trust stores.
Each of those vendors has different standards as to which CAs are qualified to be "Root CAs" in that given product. Specifically, each vendor has different certifications, processes and procedures (such a cold storage requirements) each CA must adhere to before being included in that root trust list.
Microsoft has the Root Certificate Program and that requires every CA to follow the following audit standards (which should address all your technical, and procedural questions)
- ETSI 102 042
- ETSI 101 456
- WebTrust for CAs
- WebTrust EV Readiness audits
- ISO 21188 ( Note they do not accept ISO 27001 )
Specifically, the CA must complete an audit and submit audit results to Microsoft every twelve (12) months. The audit must cover the full PKI hierarchy that will be enabled by Microsoft through the assignment of Extended Key Usages (EKUs). All certificate usages that we enable must be audited periodically. The audit report must document the full scope of the PKI hierarchy including any sub-CA that issues a specific type of certificate covered by an audit. Eligible audits include:
WebTrust for Certificate Authorities v1.0 or later, completed by a licensed WebTrust for CAs auditor,
ETSI TS 101 456 v1.2.1 or later,
ETSI TS 102 042 V1.1.1 or later, or
ISO 21188:2006, “Public key infrastructure for financial services -- Practices and policy framework,” completed by either a licensed WebTrust for CAs auditor, or an audit authority operating according to the laws and policies for assessors in the same jurisdiction as the CA.
(Note these audit requirements don't apply to government CAs and may be different)
Read more about the technical and audit guidelines for MSFT roots here
Aside:
It's definitely possible to store a private key in a HSM that never exposes the private key (offloads the requests to that key) and permanently track every usage of that private key. I don't remember if any of those standards require a HSM, but given the relatively minor cost of a HSM I can't imagine why it's not being done.