Initial assessment of rogue certificate authority risk
Dave KennedyDecember 31st, 2008
Bottom line up front: Risk has not changed significantly as a result of research into rogue Certificate Authority attacks. This is a significant attack on an obsolete hash algorithm, but there is no known threat, and countermeasures are already taking place to reduce and possibly eliminate the potential that a threat actor will succeed using this attack.
There are numerous explanations of the technical vulnerability announced Tuesday, December 30, 2008 at the Chaos Communications Congress in Berlin. Brian Krebs at the Washington Post has done his customary superb job of making this understandable to the average Internet user. Professor Ed Felten at Princeton University crafted a version for those security professionals not normally earlobe-deep in cryptography and PKI. And Professors Gene Spafford at Purdue University and Steve Bellovin at Columbia University each have perspectives beyond the technical to explain how this happened and what information professionals can and should do now. They explain how this problem has been stalking us since 1996 and how we hit the snooze alarm then, in 2004, 2005, and last year.
“Wake up call,” has become a cliché, and this event is the latest step in the decay of hash algorithms functioning unseen, unappreciated, unchanged and pervasive in today’s technology.
The Verizon Business RISK Team’s first focus is to assess the immediate impact on risk to the information systems and data of our customers and to provide practical recommendations.
Preliminary assessments are:
- The research team who created this attack is a unique collection of talent and expertise who’ve taken about four months to suss this out. They’ve made a significant jump in finding collisions in MD5. Some criminal adversaries are quite skilled but it will still take time for them to replicate this attack.
- The research team has access to hardware and software optimized for this attack package. Comparing this kit to buying US $1,500 - $20,000 worth of cycles from Amazon EC2 is like comparing apples to oranges. It will also take criminals time to replicate, or simulate the PS3 cluster or optimize an alternative source of computational power such as a botnet.
- A precondition for an attack is purchase of an MD5-signed certificate from a Certificate Authority using predictable certificate serial numbering. Randomization of certificate serial numbers and discontinuing issuance of MD5-signed certificates independently make this attack infeasible. VeriSign has reported they have “rendered ineffective” this attack against all of their certificates. It is very likely other Certificate Authorities will also act quickly to reduce the risk of successful attack.
- Speculation some certificates have already been attacked is just that, speculation.
- If this attack is used “in the wild,” it would likely include some network intrusion or manipulation to facilitate a man-in-the-middle attack. Examples include a DNS, ARP poisoning or an “evil twin” wireless attack. These attacks can be detected with existing instrumentation.
- Hash algorithms are both essential and hard. We have known MD5 was becoming obsolete for 12 years. We know SHA-1, the most likely short-term alternative hash algorithm has also been weakened by attacks and the US federal government has declared it will not be relied on after 2010. Thus we’re going to have déjà vu all over again in the near future. Unfortunately, there is currently no widely accepted and widely deployed hash algorithm to leap past SHA-1.
- While the first 24 hours of reaction to the attack announcement focused on website certificates and the potential use in phishing attacks, the impact on other SSL and X.509 certificate implementations are still to come and may appear alarming. Nevertheless, the key component to the risk due to this attack is practical use by threat actors. Improvements in attack efficiency and simplicity will probably affect risk more than newly discovered vulnerability instances.
“Attacks only get better” is doctrine in the art and science of cryptography. Undoubtedly, a practical form of this attack, or a more efficient alternative, is in our future. MD5 is obsolete and SHA-1 is obsolescent. Enterprises should identify where they are being used and draft migration plans. Monitor progress in the US Department of Commerce’ NIST Cryptographic Hash Algorithm Competition. It will likely establish the de-facto international standard to replace MD5 and SHA-1. Favor IEEE/IETF standards-compliance. Expect and plan for the replacement of each succeeding hash algorithm to minimize the cost of migration.
Acknowledgments: Valuable advice and analysis from Darren Hartman, Steve Medin, Robert Moskowitz and William H. Murray helped with the creation of this blog entry and I deeply appreciate their input, but the result and all errors are mine alone.
Disclosure: Verizon Business has a line of business as a Certificate Authority.
Tags: Certificate Authority, cryptography, hash algorithm, Information Security, InfoSec, MD5
The usual response to this kind of attack scenario is “feasible but not efficient.” That is, the cost of attack is higher than the value of success or greater than that of a cheaper alternative attack. This may be true because the attack is computationally intensive and/or because the special knowledge involved is sparsely held and very expensive relative to the value of a successful attack.
My first read of this is that the cost of the computation involved here might be low when compared to the value of success. The special knowledge involved is very expensive and sparsely held but that the potential value of success might justify large bribes or even coercion. (This might be the reason for the large number of authors, an attempt to spread the risk of having one’s children kidnapped. Signing on as an author of such a paper would put a large target on the backs of one’s loved ones. Would you sign?)
My second read is that a successful attack would likely be detected and shut down in days. Said another way, the risk might be acceptable to the victim institutions while the reward to the attacker is still high enough to justify the attack.
While, in the absence of an attack, the cost of the fix might appear to be time consuming and expensive, there is always money enough to fix that which must be fixed. After an attack, we will clearly find the money, and the time taken to implement the fix will prove to be lower than any of the pre-attack estimates. The post attack cost of remediation will be orders of magnitude higher than a pre-attack fix.
While it would seem to be an easy decision to get right, history, even on the specific issue of MD5, says that the decision as to whether to fix or tolerate will take more time than an attack.
Advice to enterprises: it is easier for you to change Authorities than for the Authorities to change hashes.
Posted by: William Hugh Murray, CISSP on December 31st, 2008 at 10:58 pmI wrote:
“The special knowledge involved is very expensive and sparsely held but that the potential value of success might justify large bribes or even coercion. (This might be the reason for the large number of authors, an attempt to spread the risk of having one’s children kidnapped. Signing on as an author of such a paper would put a large target on the backs of one’s loved ones. Would you sign?)”
I have re-thought this in light of someone else’s observation that a much cheaper attack is simply to dupe a legitimate authority to issue a certificate. All too easy. Rest easy, guys; no one is going to kidnap you.
Posted by: William Hugh Murray, CISSP on January 1st, 2009 at 12:39 pmHi Dave, Bill:
If VeriSign has stopped issuing certs with MD5 digests, that’s pretty much the whole ball game. Five of the six CAs listed, by Sotirov et al, as potentially vulnerable to this attack all seem to be under the control of various VeriSign subsidiaries.
The sixth CA listed, RSA Data Security’s “Secure Server Certification Authority,” was legally transferred from RSADSI to VeriSign way back in 1995, when RSA spun off VeriSign as an independent entity.
Sotirov’s team said they saw certs signed by that particular CA in 2008, but the operational lifetime of that root CA was only supposed to be from November, 1994, to December, 1999. Odd, huh?
(RSA itself, now a division of EMC, endorsed and promoted MD5 in 1991. It met a need, and it was yet another brilliant creation from MIT Prof Ron Rivest, the “R” in RSA. In 1996, as the SSL-secured Internet exploded, new issues were raised and RSA Labs publicly urged the industry to shift from MD5 to SHA1. Ancient history. Today, RSA/EMC still controls two root CAs, but I don’t think either has ever used MD5 in their signing procedures. Both default to SHA1, but RSA is upgrading its whole product line for SHA2 hashes.)
The particulars of this rogue CA exploit may be unique, but serious cryptographers have warned that SHA1 could face difficulties similar to MD5, as more computational power becomes generally available. Meanwhile, the online chatter among the titans who have invented new hashes — and submitted them to NIST in the ongoing competition to select SHA3 — is charming and educating a whole new generation of crypto-savvy engineers and mathematicians.
New Year blessings upon all!
_Vin
Posted by: Vn McLellan on January 2nd, 2009 at 7:38 amGreetings, Vin.
You wrote:
“…but serious cryptographers have warned that SHA1 could face difficulties similar to MD5, as more computational power becomes generally available.”
Even cryptographer wannabees know that costs to the attacker rise exponentially while costs to the user rise linearly. While new hashes hold the potential for efficiency, there are a number of alternative ways to dramatically increase the cost of attack using the existing hashes. These include digital time-stamps, longer hash values, and double signing. Perhaps the CAs are too conservative.
Since most of the cost of standardizing a new hash is in measuring its effectiveness, we can be grateful to NIST for absorbing so much of that cost.
All that said, the CAs, not the government, not the “researchers,” should be making the call.
Bill
Posted by: William Hugh Murray, CISSP on January 4th, 2009 at 5:04 pm