Must/should I fetch all CRLs of the complete chain to check the certificates validity?
Absolutely. A CA builds a CRL only for the certificates it issues. Status of the CA itself must be checked via the CRL of the issuing CA. Note: This is a recursive search. When writing code, or testing systems, remember that there can be more than one "generation" of issuing CAs and check all certificates except the self signed root. A root CA will not have an associated CRL - if the root is compromised, that root must be manually removed from any trust stores.
What should I do when an Intermediate CA is revoked?
Do not trust anything signed by the CA. A certificate is only as good as the CA that issued it. If the CA is becomes untrustworthy, the certificates issued by that CA are no longer trustworthy.
Do not expect to get a CRL from the revoked CA saying that all certificates issued by the CA are not valid. If the CA is active, this will create a prohibitively large CRL that will be extremely painful to transport, parse, and generally do anything with. Also - if the CA's key has been lost - it may not be possible to create this CRL.
In practice, the smart thing would be to remove the CA from any trust stores. Removing the CA from trust stores will cause any application that builds it's CA chain from trust stores to fail the certificate verification quickly. Building the certificate chain is usually done prior to any OCSP/CRL checking, so you save your application from extra steps and potentially bandwidth by trimming the revoked CA from your stores.
An intermediate CA being revoked is also a fairly major event - honestly, I've never experienced it in the real world. If I was working on a highly secure system, I'd also publish as far and wide as I could that the CA was revoked. Particularly any systems that may be working off CRLs that are cached for a long time.
And if I held certificates signed by this CA, I'd start formulating my re-certification strategy ASAP.
Will all it's certificates be added to the CRL as well?
No. Note, there are two different CRLs in play: - the issuing CA's CA (either a root CA or another CA in the chain) - issues a CRL which verifies the status of
the issuing CA's cert - the issuing CA - issues a CRL which verifies the status of the certs this CA has issued.
If you have a CA chain that is n certificates from root to end entity, you will have n-1 CRLs involved.
Can the certificate be replaced by a new (uncompromised) version?
Yes. sort of. The compromise reflects the untrustworthiness of the private key of the CA. The CA will need a new private key, which essentially makes it a new CA.
It is, technically, possible to rename the CA with the same Distinguished Name - if there is an operational value to that. But in practice, my temptation would be to standup a new CA, with a new DN, just so that all humans were clear on the difference.
This will be a major pain in the rear end. The users of the new CA will need to: - remove the compromised cert, and replace it with the new CA cert - recertify all End Entity certificates with certificates that are signed by the new CA.
Note that it's a matter of security policy as whether you recertify or rekey your end entities. If the compromised system did not have access to the private keys of any end-entities, you can re-sign the same private key with a new CA key. If you kept a store of certificate requests on file, you could resubmit them to the new CA and save yourself a whole bunch of key generation.
However, in some cases, the CA system may put some private keys in escrow - this means that in some central location (usually near the CA system), the private keys are stored securely in case the users loose their keys and need an update. This is particularly prevalent in the case of encryption certificates, since you may need to retrieve encrypted data even after an encryption key has been revoked.
In these cases, if the CA is compromised, there's a decent chance the key escrow has been compromised. That means that all users of keys in the escrows should generate new key pairs and request a new certificate.
Past that - its a matter of policy as to whether re-certification is allowed. Since a new certificate will have a new validity period, it may be that the security powers that be say "no renew/recertification" because they can't limit the validity period sufficiently.