How to secure your CA's private key?

I worked at a company where the security of the CA key was critical to the continued success of the business. To this end the key was encrypted using a custom protocol that required at least 2 people to be present with physical tokens plugged into terminals to decrypt it(there were at least 5 of these tokens, any 2 combined would work). The terminals were physically separated from the actual machine with the CA key. The interface that the users had who decrypted it was a VT220 terminal that allowed them to input the decryption tokens and then select what they wanted to 'sign' with the key (never giving them access to the decrypted key). This system meant at least 4 people would have to work together to compromise the key, two token holders, the guy who had access to the data center, and another person who had root access on the server (because the decrypted key was never stored on the server only in memory you couldn't just steal the box, and the people with root to this specific server were not allowed DC access).

If you are interested in more details on this sort of setup Bruce Schneier has a great site covering computer security design and implementation:

http://www.schneier.com/

He has also published a really good book Applied Cryptography that I found helped me understand the fundamentals of systems like this and how to architect more secure infrastructures (readable by people who don't wear pocket protectors):

http://www.schneier.com/book-applied.html

One big gain is to keep the private CA key on a dedicated computer completely cut off from the network. You would then sign, and possibly also generate, new certificates on this machine, and then use an physical media to transfer the new certificates off the CA machine.

Such as setup would of course also include considerations regarding the physical availability of the machine, as well as restrictions on allowed medias. A well traveled USB stick is probably not the best of choices...

(This is by the way a very clear example on the trade off between security and convenience.)

I have upvoted the other two answers, and commented thereon, because I think they're both excellent. If you decide to go for both of them, and that might well be appropriate, I strongly advise care in the initial generation of the key, since the best time to compromise a key is not in use (where many standard, repeatable precautions can be applied) but at generation time, which being a once-off is much easier to subvert.

This excellent guide to conducting a key-generation ceremony outlines some of the standard protocols that can help to secure key generation, though they mostly boil down to (a) having everything witnessed by multiple knowledgable auditors, who are (b) making contemporaneous records of everything that is done (c) according to a pre-determined protocol written by someone other than the executor.

Depending on how serious you are, you should consider using FIPS 140-2 (http://en.wikipedia.org/wiki/FIPS_140#Security_levels) hardware to store CA keys and back-ups of those keys. You should have one root CA and one intermediate CA so you can keep your root CA offline and physically secured. The root is only needed to renew or sign new intermediate CAs, whereas the intermediate CAs stay online for day-to-day operations. As others have suggested, secure key generation and key management with n of m control is important.

The VeriSign (now Symantec) CPS is a good reference for how a commercial CA generates and protects its keys. Look at chapters 5 and 6, specifically: http://www.verisign.com/repository/cps/. (I worked at VeriSign for several years)

Also, NIST has several good publications on Key Management (http://csrc.nist.gov/publications/drafts/800-57/Draft_SP800-57-Part1-Rev3_May2011.pdf) and generation, and your company should also have a CPS that specifies the policies and practices you use for managing your CA. The IETF provides a good template: http://www.ietf.org/rfc/rfc2527.txt

Great question and some great answers too.

Keep in mind that you're about 90% ahead of most other people simply by considering this issue rather than blindly charging ahead.

Having kept that in mind and taken the other advice here, I would simply add: don't rest on your laurels; keep an eye on security and cryptography news for both general issues relating to certificate issuing, revocation, cracking, etc. and most definately on vulnerabilites and issues with the specific products you use to generate and manage your keys.

Lastly: physical security. Making something 'hacker proof' is no help if I can just get a job as a contract cleaner in your building and then put the disk containing your root cert in my pocket one day. You'd be surprised how many people miss that one.