As the results of CloudFlare's challenge have demonstrated, a server's private key can be extracted using the Heartbleed vulnerability. Consequently, the 500,000+ certificates used on web servers supporting TLS heartbeat should be urgently replaced and revoked. Whilst the replacement and revocation process has begun — 80,000 certificates have been revoked since the announcement — it is far from over.
Private key extraction is real
CloudFlare, which uses a modified version of the nginx web server, originally thought it would be extremely hard or impossible to use the Heartbleed bug to steal a certificate's private key from an nginx server. However, this was quickly proved wrong last week after CloudFlare set up a vulnerable website and challenged people to steal its private key. Later on the same day, the private key had been successfully stolen by exploiting the Heartbleed bug.
Fortunately, CloudFlare decided to play it safe and planned to reissue and revoke potentially affected certificates anyway. CloudFlare also acknowledges that the revocation process is far from perfect and not suitable at mass scale: "If every site revoked its certificates, it would impose a significant burden and performance penalty on the Internet". CloudFlare's own website at cloudflare.com started using a new SSL certificate yesterday, despite the new certificate being marked as valid from 10 April 2014.
Akamai is also planning to rotate all of its customers' SSL certificates after realising a flaw in its recent patch which it originally believed would protect users against the Heartbleed bug. Akamai is notable for its content delivery network of more than 61,000 servers, which they claim delivers 15-20% of all web traffic.
There are already reports that Heartbleed has been used to compromise secure web sites including Canada's tax agency and popular UK web forum Mumsnet.
Revocation is critical (even if it doesn't always work)
As of this morning (Tuesday 15th April), more than 80,000 certificates have been revoked since the public announcement of the vulnerability on 7th April.
The Heartbleed bug has caused a rise in certificate revocations, but the rate predictably fell over the weekend.
Based on list prices, the cost of replacing all of the potentially-compromised certificates with completely new certificates is more than $100 million, but, helpfully, most (but not all) certificate authorities are allowing their customers to reissue and revoke certificates for free. Nonetheless, plenty of the affected websites (e.g. Etsy, Yahoo, GitHub, Steam) appear to have bought new certificates instead of going through the reissuance process, as the new expiry dates are significantly later than the expiry dates in the previous certificates. Perhaps in the haste of resolving the problem, this seemed the easiest approach, making Heartbleed a bonanza for certificate authorities.
While some companies quickly recognised the need to issue new certificates in response to the Heartbleed bug, the number of revocations has not kept up. This is a mistake, as there is little point issuing a new certificate if an attacker is still able to impersonate a website with the old one.
Yahoo was one of the first companies to deploy new SSL certificates after the Heartbleed bug became public knowledge, but the certificate that was previously used by mlogin.yahoo.com has not yet been revoked — it has not been placed on a CRL, and the certificate's OCSP responder says the certificate is "good".
Yahoo is not the only company to have issued a new certificate without ensuring that the previously vulnerable certificate has been revoked. Other sites which fall into this category include banking websites (such as entry7.credit-suisse.ch), the United States Senate large file transfer system at lfts.senate.gov, and GeoTrust's SSL Toolbox at https://ssltools.geotrust.com/checker/ (GeoTrust is a brand owned by Symantec, the largest certificate authority).
Thousands of certificates could still be misused after being revoked
Critically, some of the certificates affected by the Heartbleed bug will remain usable even if revoked: Nearly 4% of the certificates do not specify a URL for an OCSP responder, which means that they can only be revoked via a CRL. This makes the certificates effectively irrevocable in some browsers — for example, the latest version of Mozilla Firefox no longer uses CRLs at all (previously it would fall back to checking a CRL if an OCSP request failed, but only for Extended Validation certificates).
Worse still, a small number of the certificates that could have been compromised through exploitation of the Heartbleed bug fail to specify either an OCSP or a CRL address. These certificates are therefore completely irrevocable in all browsers and could be impersonated until their natural expiry dates if an attacker has already compromised the private keys.
For example, Telecom Italia (a sub-CA of Verizon Business) is still using an irrevocable certificate on www.cloudpeople.it, which supported the TLS heartbeat extension prior to the disclosure of the Heartbleed bug. The 3-year certificate was issued by I.T. Telecom Global CA at the end of 2011 and will remain valid until the end of 2014 because it does not permit either form of revocation.
CRLs will balloon as a result of the surge of revocations
To obtain the certificate revocation lists (CRLs) used by each publicly trusted certificate authority, a web browser would need to download more than 100MB of data. These CRLs will grow by about 35% if all of the certificates affected by the Heartbleed bug were revoked. Downloading this much data is clearly impractical for many mobile devices, and several CRLs either time-out or take more than a minute to download, even from a desktop machine with a fast internet connection. This goes against the CA/Browser Forum's Baseline Requirements, which expect CAs to provide response times of less than 10 seconds.
The largest CRL (11MB) is operated by the US Department of the Treasury, and despite containing more than 200,000 revocation entries, it is only used by one publicly accessible certificate. Nonetheless, any browser wishing to perform a CRL check for that one site will have to download the whole list. Governments also feature amongst the worst-performing CRLs: For example, the Taiwanese government offers a CRL at http://hcaocsp.nat.gov.tw/repository/HCA/CRL/complete.crl, which would not respond when tested earlier today, and the Brazilian government offers several CRLs from its site at repositorio.icpbrasil.gov.br, but each took 2-3 minutes to download, despite being of relatively modest sizes.