There are several news stories now appearing (e.g., Security News) about a serious flaw in how certificates used in online authentication are validated. Ed Felten gives a nice summary of how this affects online WWW site authentication in his Freedom to Tinker blog posting. Brian Krebs also has his usual readable coverage of the problem in his Washington Post article. Steve Bellovin has some interesting commentary, too, about the legal climate.

Is there cause to be concerned? Yes, but not necessarily about what is being covered in the media. There are other lessons to be learned from this.

Short tutorial

First, for the non-geek reader, I’ll briefly explain certificates.

Think about how, online, I can assure myself that the party at the other end of a link is really who they claim to be. What proof can they offer, considering that I don’t have a direct link? Remember that an attacker can send any bits down the wire to me and may access to faster computers than I do.

I can’t base my decision on how the WWW pages appear, or embedded images. Phishing, for instance, succeeds because the phishers set up sites with names and graphics that look like the real banks and merchants, and users trust the visual appearance. This is a standard difficulty for people—understanding the difference between identity (claiming who I am) and authentication (proving who I am).

In the physical world, we do this by using identity tokens that are issued by trusted third parties. Drivers licenses and passports are two of the most common examples. To get one, we need to produce sufficient proof of identity to a third party to meet its standards of proof. Then, the third party issues a document that is very difficult to forge (almost nothing constructed is impossible to forge or duplicate—but some things require so much time and expenditure it isn’t worthwhile). Because the criteria for proof of identity and strength of construction of the document are known, various other parties will accept the document as “proof” of identity. Of course, other problems occur that I’m not going to address—this USACM whitepaper (of which I was principal author) touches on many of them.

Now, in the online world we cannot issue or see physical documents. Instead, we use certificates. We do this by putting together an electronic document that gives the information we want some entity to certify as true about us. The format of this certificate is generally fixed by standards, the most common one being the X.509 suite. This document is sent to an organization known as a Certificate Authority (CA), usually along with a fee. The certificate authority is presumably well-known, and performs a check (to their own standards) that the information in the document is correct, and it has the right form. The CA then calculate a digital hash value of the data, and creates a digital signature of that hash value. This is then added to the certificate and sent back to the user. This is the equivalent of putting a signature on a license and then sealing it in plastic. Any alteration of the data will change the digital hash, and a third party will find that the new hash and the hash value signed with the key of the CA don’t match. The reason this works is that the hash function and encryption algorithm used are presumed to be so computationally difficult to forge that it is basically not possible.

As an example of a certificate , if you visit “https://www.cerias.purdue.edu” you can click on the little padlock icon that appears somewhere in the browser window frame (this is browser dependent) to view details of the CERIAS SSL certificate.

You can get more details on all this by reading the referenced Wikipedia pages, and by reading chapters 5 & 7 in Web Security, Privacy and Commerce.

Back to the hack

In summary, some CAs have been negligent about updating their certificate signing mechanisms in the wake of news that MD5 is weak, published back in 2004. The result is that malicious parties can generate and obtain a certificate “authenticating” them as someone else. What makes it worse is that the root certificate of most of these CAs are “built in” to browser and application trust lists to simplify look-up of new certificates. Thus, most people using standard WWW browsers can be fooled into thinking they have connected to real, valid sites—even through they are connecting to rogue sites.

The approach is simple enough: a party constructs two certificates. One is for the false identity she wishes to claim, and the other is real. She crafts the contents of the certificate so that the MD5 hash of the two, in canonical format, is the same. She submits the real identity certificate to the authority, which verifies her bona fides, and returns the certificate with the MD5 hash signed with the CA private key. Our protagonist then copies that signature to the false certificate, which has the same MD5 hash value and thus the same digital signature, and proceeds with her impersonation!

What makes this worse is that the false key she crafts is for a secondary certificate authority. She can publish this in appropriate places, and is now able to mint as many false keys as she wishes—and they will all have signatures that verify in the chain of trust back to the issuer! She can even issue these new certificates using a stronger hash algorithm than MD5!

What makes this even worse is that it has been known for years that MD5 is weak, yet some CAs have continued to use it! Particularly unfortunate is the realization that Lenstra, Wang and de Weger described how this could be done back in 2005. Methinks that may be grounds for some negligence lawsuits if anyone gets really burned by this….

And adding to the complexity of all this is the issue of certificates in use for other purposes. For example, certificates are used with encrypted S/MIME email to digitally sign messages. Certificates are used to sign ActiveX controls for Microsoft software. Certificates are used to verify the information on many identity cards, including (I believe) government-issued Common Access Cards (CAC). Certificates also provide identification for secured instant messaging sessions (e.g., iChat). There may be many other sensitive uses because certificates are a “known” mechanism. Cloud computing services , software updates, and more may be based on these same assumptions. Some of these services may accept and/or use certificates issued by these deficient CAs.

Fixes

Fixing this is not trivial. Certainly, all CAs need to start issuing certificates based on other message digests, such as SHA-1. However, this will take time and effort, and may not take effect before this problem can be exploited by attackers. Responsible vendors will cease to issue certificates until they get this fixed, but that has an economic impact some many not wish to incur.

We can try to educate end-users about this, but the problem is so complicated with technical details, the average person won’t know how to actually make a determination about valid certificates. It might even cause more harm by leading people to distrust valid certificates by mistake!

It is not possible to simply say that all existing applications will no longer accept certificates rooted at those CAs, or will not accept certificates based on MD5: there are too many extant, valid certificates in place to do that. Eventually, those certificates will expire, and be replaced. That will eventually take care of the problem—perhaps within the space of the next 18 months or so (most certificates are issued for only a year at a time, in part for reasons such as this).

Vendors of applications, and especially WWW browsers, need to give careful thought about updates to their software to flag MD5-based certificates as deserving of special attention. This may or may not be a worthwhile approach, for the reason given above: even with a warning, too few people will be able to know what to do.

Bigger issue

We base a huge amount of trust on certificates and encryption. History has shown how easy it is to get implementations and details wrong. History has also shown how quickly things can be destabilized with advances in technology.

In particular, too many people and organizations take for granted the assumptions on which this vast certificate system is based. For instance, we assume that the hash/digest functions in use are computationally difficult to reverse or cause collisions. We also assume that certain mathematical functions underlying public/private key encryption are too difficult to reverse or “brute force.” However, all it takes is some new insight or analysis, or maybe new, affordable technology (e.g., practical quantum computing, or massively parallel computing) to violate those assumptions.

If you look at the way our systems are constructed, too little thought is given to what happens to existing infrastructure when something breaks. Designs can include compensating and recovery code, but doing so requires some cost in space or time. However, all too often people are willing to avoid the investment by putting off the danger to “if and when that happens.” Thus, we instance such as the Y2K problems and the issues here with potentially rogue CAs.

(I’ll note as an aside, that when I designed the original version of Tripwire and what became the Signacert product, I specifically included simultaneous use of several different message digest functions in different families for this very reason. I knew it was a matter of time before one or two were broken. I still believe that it is beyond reason to find files that will match multiple, different algorithms simultaneously.)

Another issue is the whole question of who we trust, and for what. As noted in the USACM whitepaper, authentication is always relative to a third party. How much do we trust those third parties? How much trust have we invested in the companies and agencies issuing certificates? Are they properly verifying identities? How good is there internal security? How do we know, and how much is at risk from our trust in those entities?

Let me leave you with a final thought. How do we know that this problem has not already been quietly exploited? The basic concept has been in the open literature for years. The general nature of this attack on certificates has been known for well over a decade, if not two. Given the technical and infrastructure resources available to national agencies and organized criminals, and given the motivation to use this hack selectively and quietly, how can we know that it is not already being used?

[Added 12/31/2008]: A follow-up post to this one is available in the blog.

History

Back in 1997, the year before CERIAS was formally established, I testified before Congress on the state of cyber security in academia. In my testimony, I pointed out that there were only four established research groups, and their combined, yearly PhD production was around 3 per year, not counting cryptography.

Also in that testimony, I outlined that support was needed for new centers of expertise, and better support of existing centers.

As a result of that testimony, I was asked to participate in some discussions with staff from OSTP, from some Congressional committees (notably, the House Science Committee), and Richard Clarke's staff in the Executive Office of the President. I was also invited to some conversations with leadership at the NSA, including the deputy director for information security systems (IAD) (Mike Jacobs). Those discussions were about how to increase the profile of the area, and get more people educated in information security.

Among the ideas I discussed were ones expanded from my testimony. They eventually morphed into the Scholarship for Service program, the NSF CyberTrust program, and the NSA Centers of Academic Excellence (CAE). [NB. I am not going to claim sole or primary credit for these programs. I know I came up with the ideas, briefed people about them, discussed pros & cons, and then those groups took them and turned them into what we got. None of them are quite what I proposed, but that is how things happen in DC.]

The CAE program was established by the NSA in late 1998. The CAE certification was built around courses meeting CNSS requirements. Purdue was one of the first seven universities certified as CAEs, in May of 1999. We remained in the CAE program until earlier this year (2008). In 2003, DHS became a co-sponsor of the program.

Why Purdue is No Longer a CAE

In 2007, we were informed that unless we renewed our CNSS certifications by the end of August, we would not be eligible for CAE renewal in 2008. This prompted discussion and reflection by faculty and staff at CERIAS. As noted above, the mapping of CNSS requirements to our classes is non-trivial. The CAE application was also non-trivial. None of our personnel were willing to devote the hours of effort required to do the processing. Admittedly, we could have "faked" some of the mapping (as we know some schools have done in the past), but that was never an option for us. We had other objections, too (see what follows).As a result, we did not renew the certifications, and we dropped out of the CAE program when our certification expired earlier this year.

Our decision was not made lightly -- we nearly dropped out in 2004 when we last renewed (and were not grandfathered into the new 5 year renewal cycle, much to our annoyance), and there was continuing thought given to this over intervening years. We identified a number of issues with the program, and the overhead of the mapping and application process was not the only (or principal) issue.

First, and foremost, we do not believe it is possible to have 94 (most recent count) Centers of Excellence in this field. After the coming year, we would not be surprised if the number grew to over 100, and that is beyond silly. There may be at most a dozen centers of real excellence, and pretending that the ability to offer some courses and stock a small library collection means "excellence" isn't candid.

The program at this size is actually a Centers of Adequacy program. That isn't intended to be pejorative -- it is simply a statement about the size of the program and the nature of the requirements.

Some observers and colleagues outside the field have looked at the list of schools and made the observation that there is a huge disparity among the capabilities, student quality, resources and faculties of some of those schools. Thus, they have concluded, if those schools are all equivalent as "excellent" in cyber security, then that means that the good ones can't be very good ("excellent" means defining the best, after all). So, we have actually had pundits conclude that cyber security & privacy studies can't be much of a discipline. That is a disservice to the field as a whole.

Instead of actually designating excellence, the CAE program has become an ersatz certification program. The qualifications to be met are for minimums, not for excellence. In a field with so few real experts and so little money for advanced efforts, this is understandable given one of the primary goals of the CAE program -- to encourage schools to offer IA/IS programs. Thus, the program sets a relatively low bar and many schools have put in efforts and resources to meet those requirements. This is a good thing, because it has helped raise the awareness of the field. However, it currently doesn't set a high enough bar to improve the field, nor does it offer the resources to do so.

Setting a low bar also means that academic program requirements are being heavily influenced by a government agency rather than the academic community itself. This is not good for the field because it means the requirements are being set based on particular application need (of the government) rather than the academic community's understanding of foundations, history, guiding principles, and interaction with other fields. (E.g., Would your mathematics department base its courses on what is required to produce IRS auditors? We think not!) In practice, the CAE program has probably helped suppress what otherwise would be a trend by our community to discuss a formal, common curriculum standard. In this sense, participation in the CAE program may now be holding us back.

Second, and related, the CNSS standards are really training standards, and not educational standards. Some of them might be met by a multi-day class taught by a commercial service such as SANS or CSI -- what does that say about university-level classes we map to them? The original CNSS intent was to provide guidance for the production of trained system operators -- rather than the designers, researchers, thinkers, managers, investigators and more that some of our programs (and Purdue's, in particular) are producing.

We have found the CNSS standards to be time-consuming to map to courses, and in many cases inappropriate, and therefore inappropriate for our students. Tellingly, in 9 years we have never had a single one of our grads ask us for proof that they met the CNSS standards because an employer cared! We don't currently intend to offer courses structured around any of the CNSS standards, and it is past the point where we are interested in supporting the fiction that they are central to a real curriculum.

Third, we have been told repeatedly over the years that there might be resources made available for CAE schools if only we participated. It has never happened. The Scholarship for Service program is open to non-CAE schools (read the NSF program solicitation carefully), so don't think of that as an example. With 100 schools, what resources could reasonably be expected? If the NSA or DHS got an extra $5 million, and they spread it evenly, each would get $50,000. Take out institutional overhead charges, and that might be enough for 1 student scholarship...if that. If there were 10 schools, then $500,000 each is an amount that might begin to make a difference. But over a span of nearly 10 years the amount provided has been zero, and any way you divide that, it doesn't really help any of us. Thus, we have been investing time and energy in a program that has not brought us resources to improve. Some investment of our energy & time to bolster community was warranted, but that time is past.

Fourth, the renewal process is a burden because of the nature of university staffing and the time required. With no return on getting the designation, we could not find anyone willing to invest the time for the renewal effort.

Closing Comments

In conclusion, we see the CAE effort as valuable for smaller schools, or those starting programs. By having the accreditation (which is what this is, although it doesn't meet ISO standards for such), those programs can show some minimal capabilities, and perhaps obtain local resources to enhance them. However, for major programs with broader thrusts and a higher profile, the CAE has no real value, and may even have negative connotations. (And no, the new CAE-R program does not solve this as it is currently structured.)

The CAE program is based on training standards (CNSS) that do not have strong pedagogical foundations, and this is also not appropriate for a leading educational program. As the field continues to evolve over the next few years, faculty at CERIAS at Purdue expect to continue to play a leading role in shaping a real academic curriculum. That cannot be done by embracing the CAE.

We are confident that people who understand the field are not going to ignore the good schools simply because they don't have the designation, any more than people have ignored major CS programs because they do not have CSAB accreditation. We've been recognized for our excellence in research, we continue to attract and graduate excellent students, and we continue to serve the community. We are certain that people will recognize that and respond accordingly.

More importantly, this goes to the heart of what it means to be "trustworthy." Security and privacy issues are based on a concept of trust and that also implies honesty. It simply is not honest to continue to participate in (and thereby support) a designation that is misleading. There are not 94 centers of excellence in information and cyber security in the US. You might ask the personnel at some of the schools that are so designated as to why they feel the need to participate and shore up that unfortunate canard.

The above was originally written in 2008. A few years later, the CAE requirements were changed to add a CAE-R designation (R for research), and several of our students did the mapping so we were redesignated. Most of the criticisms remain accurate even in 2012.