A History of Hard Choices

Disclaimer: This post represents personal opinions and thoughts, and does not represent the views or positions of my employer, Google.

This past month, CloudFlare and Facebook grabbed tech press headlines with simultaneous posts about the perceived challenges and risks of the upcoming sunset of SHA-1 certificates. In a post by Alex Stamos, Facebook’s Chief Security Officer reported between 3% to 7% of browsers don’t support SHA-256. Meanwhile, CloudFlare’s Chief Executive Officer, Matthew Prince, offered a more detailed breakdown of the 25 countries with the worst SHA-256 support. The conclusion, from both companies, was that there exists a need to continue issuing SHA-1 certificates for sites. CloudFlare went a step further, suggesting that to sunset SHA-1 was akin to isolating vulnerable populations in the poorest, most repressive, and most war-torn countries of the world from secure communications. Following their posts, Michael Coates, Trust and Information Security Officer of Twitter, joined in support the proposal, painting the conversation as a dichotomy between having either no security or no access, with there being absolutely no middle ground.

The conclusion drawn by Stamos, Prince, and Coates was that there is a need to find a way for sites to continue to obtain new SHA-1 certificates. They proposed that the CA/Browser Forum introduce a new type of certificate, called Legacy Verified (LV), as a way of allowing known-insecure practices to continue while ostensibly mitigating the risks such practices pose. The details of this proposal were later forwarded on their behalf to the Forum.

Background

In order to fully understand and appreciate this proposal, it’s necessary to first understand both the technical details and the historical context surrounding SHA-1 certificates and their sunset. This discussion is not new; rather, it is merely the latest milestone in a discussion that spans a decade. Similarly, the upcoming 31 December 2015 sunset of SHA-1 issuance does not represent the end-state for SHA-1; browsers, CAs, and sites will still be discussing, making changes, and debating trade-offs for at least several more years to come.

In this first post, my hope is to frame the conversation regarding SHA-1 into the proper historical context in which it fits. In many ways, the proposal is simply the continuation of an endless cycle of debate about how to handle deprecating known-insecure practices. And yet even though similarities exist, the rhetoric itself has grown both louder and harsher; to support deprecation is to support the oppression of at-risk populations or to deny them basic rights. Though such appeals are moving in isolation, they must not be taken in isolation, but evaluated within the systems and history in which they are being made. Further, though the numbers being published are both headline-grabbing and alarming, what is published lacks scientific rigor, and even conflicts with the data published by other large sites.

In subsequent posts, I hope to explore both the technical merits of the specific proposal, as well as that of suggested alternatives, as well as explore what possible next steps are available — to browsers, to CAs, and to sites themselves.

A Timeline of Woe

It’s important to realize that the story of SHA-1 is tied closely to that of its predecessor, MD5. Beyond the fact that both MD5 and SHA-1 share similar cryptographic constructions, MD5 was previously the de facto hash algorithm for certificates, due to a lack of widespread SHA-1 support, similar to the story of SHA-1 and SHA-2 today. It was the complete breakage of MD5 that hastened the adoption of SHA-1, much like the near-complete breakage of SHA-1 has hastened about the switch to SHA-2.

This past experience with MD5, and its ultimate removal, has informed and significantly shaped how browsers and software vendors have responded to SHA-1; one cannot discuss SHA-1 without first exploring the history of MD5.

Similarly, to understand the dynamics at play between CAs, browsers, and sites, it’s equally important to consider the discussions related to the ultimate deprecation of both 1024-bit RSA certificates and Server Gated Cryptography, as many of the arguments surrounding those deprecations are similar to — or even identical to — the arguments being put forth today.

This timeline is not meant to be exhaustive as to all the unfortunate events that have happened, but merely serves as a representative sample that can be used to show patterns and trends, as well as referred to in the subsequent posts to demonstrate various flaws in the arguments presented by others.

• 1993: den Boer and Bosselaers demonstrate the first proto-attack on MD5, two years after it is first introduced.
• 1996: Dobbertin announces an attack on the compression function of MD5, an event significant enough to cause the cryptographic community to recommend that software switch to other algorithms, such as SHA-1.
• 1997: Microsoft adds support for Server Gated Cryptography to Internet Explorer 3, as a way of working within the US regulatory framework for the export of cryptography. In order to use strong cryptography, websites must obtain a special certificate from a CA that indicates they meet the criteria set forth by the US export controls. Netscape introduces similar support, under the name International Step-Up, which works slightly different under the hood but is conceptually equivalent.
• 2000: Completing a relaxation begun in 1999, US export controls are altered, obsoleting the need for SGC certificates. Internet Explorer 5 no longer has a need for such certificates.
• 2004: A group of researchers demonstrate the first collision in MD5.
• 2005: Lenstra, Wang, and de Weger demonstrate collisions in certificates with different public keys, highlighting the risk of using MD5-based signature algorithms in certificates.
• 2005: The CA/Browser Forum is formed with the goal of developing a set of standards for Extended Validation SSL certificates.
• 2006: Rob Stradling of Comodo, a founding CA member of the CA/Browser Forum, attempts to garner interest in the IETF PKIX working group, which is the group responsible for developing standards related to certificates, for a way to safely and securely support multiple signatures. The responses are largely tepid, with the conclusion seeming to be that PKIX feels it “can afford to wait until the very last minute, i.e. when SHA1 is actually broken, rather than to upgrade to some fix like SHA256 before SHA1 is broken.”
• 2007: The CA/Browser Forum adopts and publishes the first version of the EV SSL guidelines.
• 2008: Stevens, Sotirov, Appelbaum, Lenstra, Molnar, Osvik, and de Weger exploit MD5 to create a fraudulent intermediate certificate by getting a certificate from RapidSSL. This fraudulent certificate allows them to issue certificates for, and thus intercept, any HTTPS website on the Internet.
• ~2008–2009: The Microsoft Root Program Technical Requirements, v1.0, requires that CAs stop issuing MD5 certificates, effective 15 January 2009. CAs are required to make SHA-2 available, on request, effective 31 December 2011. Further, all 1024-bit RSA certificates must expire before 31 December, 2013; Microsoft makes no guarantees that such certificates will keep working after that point.
• 2009: Johnathan Nightingale, then working on Firefox at Mozilla, releases an analysis of MD5 usage of the Alexa top million sites. At the time of publication, 14% of these sites still use MD5 certificates.
• 2009: The Chrome team explores removing support for MD5. Based on their research, removing support for MD5 would affect 6% of users globally.
• 2010: In light of growing concern with SHA-1, Microsoft requires that all CAs participating in their program include 8 bytes (64 bits) of entropy in either the certificate serial number or in the first component of the certificate subject name (i.e. before any attacker-controlled data). In the event that there is absolutely no other way, Microsoft allows CAs to include 6 bytes of random data in the Hour:Minutes:Seconds of the validity period; due to encoding limitations, this only offers 86400 possible values, or around 16 bits of entropy each for the notBefore and notAfter fields.
• February 2010: The authors of the Flame malware exploit an MD5 collision against a Microsoft-operated Certificate Authority to obtain a malicious code-signing certificate.
• May 2010: VeriSign (later acquired by Symantec) announces their 1024-bit root transition plan. Thawte branded certificates will transition on June 2010, GeoTrust in July 2010, VeriSign in October 2010, RapidSSL in December 2010. All new certificates will come off the stronger roots.
• August 2010: Symantec acquires VeriSign.
• October 2010: Mozilla announces that, as of December 31, 2010, CAs must stop issuing any certificate from 1024-bit root certificates, and must stop issuing certificates for RSA key sizes less than 2048 bits. On June 30, 2011, they will stop validating MD5 signatures. Both of these deadlines are missed; in particular, Symantec Corporation indicates to Mozilla they will not comply until 2013, despite having announced a transition plan only 5 months prior.
• October 2011: Apple releases iOS 5, the first mainstream client to disable support for MD5.
• November 2011: The CA/Browser Forum adopts the first version of the Baseline Requirements. This first version includes text that survives to this day, stating that Certificate Authorities SHOULD include at least 20 bits of entropy within the Certificate serial number. The SHOULD language is inherited from RFC 2119, which defines it as “there may exist valid reasons in particular circumstances to ignore a particular item, but the full implications must be understood and carefully weighed before choosing a different course.” The Baseline Requirements also indicate that SHA-1 certificates MAY be issued with validity periods extending beyond 31 December 2013, but only until SHA-256 is “supported widely by browsers used by a substantial portion of relying-parties worldwide.”
  The Baseline Requirements do not permit the issuance of MD5 certificates.
• December 2011: Chrome disables support for MD5, two years after originally desired. In doing so, reports begin to emerge that a variety of “security” software products are broken, including products from TrendMicro and WebSense products, making Chrome wholly unusable in a variety of environments that were still actively using MD5.
• March 2012: Firefox disables support for MD5, nine months after originally scheduled.
• July 2012: The Baseline Requirements come into effect. According to the Baseline Requirements, all certificates issued after 1 July 2012 should conform to these requirements.
• 2013: Microsoft updates their Root Program Requirements to remove the Validity Period clause for entropy. Entropy MUST now appear within the certificate serial number or first field of the certificate subject.
• February 2013: Mozilla adopts Version 2.1 of their CA Certificate Policy, becoming the first Root Program to require conformance to the Baseline Requirements. However, this requirement only applies to new CAs requesting inclusion; for existing roots, their first audit after February 2013 must be performed to the Baseline Requirements, but the CA is allowed to violate them, provided they document the violation and the audit the following year resolves those violations. For a CA that was audited on January 2013 for the issuance period of 2012, this means that they can continue to issue non-compliant certs throughout 2013, as their first BR audit would be January 2014 and cover the prior year. When they are audited on January 2015, for the issuance period of 2014, they are expected to be compliant.
• May 2013: Stevens describes a set of new attacks on SHA-1 that make chosen-prefix attacks more feasible.
• August 2013: Stevens describes a means of attempting to mitigate the risk of SHA-1 collisions by describing how verification software can attempt to probabilistically detect whether or not there’s a chance of collision.
• August 2013: Microsoft provides a security update, but only for Windows Vista and later, that disables support for MD5 within certificates, over three years after the Flame malware and nearly four years after they forbid issuance of such certificates.
• October 2013: Apple releases OS X 10.9, which removes support for MD5 in certificates, bringing it in line with iOS 5 released two years earlier.
• June 2013: Six months before CAs are required by the Baseline Requirements to stop issuing certificates with RSA keys less than 2048 bits, Rick Andrews of Symantec proposes such issuance be allowed indefinitely, for existing customers, so long as CAs follow a documented process. This proposal is quite similar to the Legacy Verified proposal offered by Facebook and CloudFlare — it relies on specific business processes to prevent misissuance, and includes an OID marker (or, more aptly, the lack thereof) within the Certificate Policies extension as a way to protect modern clients.
• October 2013: Symantec requests that their 1024-bit roots be included indefinitely in Mozilla products, as they have issued and will continue to issue certificates from them in order to support older browsers and enterprises who will be negatively affected.
• November 2013: Microsoft announces that, effective 1 January 2016, CAs must stop issuing SHA-1 certificates. This decision is taken unilaterally, after the CA/Browser Forum is unable to progress on the matter after months of debate.
• January 2014: Symantec notifies Mozilla that they knowingly violated multiple provisions of the Baseline Requirements — issuing a 1024-bit certificate directly off a 1024-bit root, and with the validity period backdated to begin in 2010 — in order to satisfy a customer request.
• August 2014: Mozilla begins the first wave of removals of 1024-bit root certificates.
• September 2014: Chrome announces that SHA-1 deprecation UI will begin to be shown, coming into effect mid-November, for certificates that extend past the two Microsoft sunset dates— issuance (1/1/2016) and validity (1/1/2017).
• October 2014: After nearly a year of debate, the CA/Browser Forum ratifies Ballot 118, which sets the SHA-1 deprecation date to be the same as in the Microsoft policy announced the year prior.
• October 2014: Three years after the Microsoft Root Program required that all CAs make SHA-2 certificates available, Gandi.net, a small CA based in Paris, is finally able to offer SHA-2. They were unable to provide such certificates as the Root CA they partnered with — Comodo — did not offer such certificates. They were not unique; the problems and inability of people to get SHA-2 certificates due to CA issues were widespread.
• January 2015: Mozilla completes the second wave of 1024-bit root certificate removals.
• April 2015: Mozilla attempts to remove the trust bits for the remaining 1024-bit root, the Symantec-operated Equifax root. Due to considerable breakage, this decision is reverted.
• May 2015: Symantec stops attempting to upsell sites into purchasing SGC certificates, 15 years after they were no longer needed.
• September 2015: Apple releases iOS 9 and OS X 10.11, which enables by default a feature called App Transport Security (ATS) for new applications. When enabled, it forces the use of TLS 1.2; if RSA keys less than 2048 bits long are encountered while connecting, the connection will fail — effectively deprecating 1024-bit RSA keys. However, applications can and do disable this for compatibility reasons.
• September 2015: On behalf of the Chief Security Office of AT&T Services, Rick Andrews of Symantec posts a request to postpone the deprecation of SHA-1. In this request, AT&T notes that in 2014, Symantec confirmed “… that we would retain the option to issue SHA-1 certificates in 2016 with expiration no later than 12/31/2016 …” AT&T’s challenges in deployment were, in part, caused by this commitment, as plans and resource allocations were committed to 2016 and could not be advanced sooner.
• October 2015: Symantec proposes a ballot, with the support of Entrust, Microsoft, and TrendMicro, to extend the SHA-1 certificate issuance date for the duration of 2016; Under this proposal, issuance would not cease until 1/1/2017.
• October 2015: Stevens, Karpman, and Peyrin announce “The SHAppening,” a freestart collision attack on SHA-1. Their research indicates that previous estimates about the economic viability of SHA-1 attacks were significantly underestimated, and they recommend transitioning off SHA-1 as soon as possible. Symantec subsequently withdraws their SHA-1 ballot.
• October 2015: Symantec is detected to be routinely misissuing Extended Validation Certificates. These certificates require the most stringent of controls, including manual review and approval at two separate points during the issuance process. After an initial investigation reveals Symantec underestimated the misissuance, it is subsequently determined that Symantec misissued at least 2,600 certificates spanning the course of several years, at all levels of validation (DV, OV, EV).
• November 2015: Symantec finally stops issuing SHA-1 certificates with sequential serial numbers, five years after Microsoft forbade the practice. When pressed for explanation, Symantec indicates they placed entropy in the date fields — two years after Microsoft forbade the practice — and only half the recommended amount.
• December 2015: With only one week’s notice, Symantec requests that a root certificate trusted on billions of devices be revoked, so that Symantec will no longer be obligated to abide by the Baseline Requirements for that root. Without this notice, Symantec’s use of their root in this manner would have been in violation of their agreements with root programs, putting at risk every other root certificate they operate and every single customer of theirs. Yet, even with this notice, it will likely take years to reduce the number of users and devices at risk from certificates issued by Symantec from this root to a something quantified in the tens of millions.
• January 2016: Mozilla is scheduled to complete the removal of Symantec’s last 1024-bit root certificate, two years after originally scheduled.

Conclusions

While this is an admittedly long and detailed timeline, such length is necessary to see that the debate reignited this month is not new, but simply a continuation in the cycle of debates that occurs with each and every deprecation. The concerns raised for compatability are not new — application developers and platform vendors face hard choices each and every step of the way towards securing the Internet, with two notable examples being it be the deprecation of MD5 certificates and the still-ongoing deprecation of certificates with key sizes less than 2048 bits (which all systems continue to trust, with the exception of newly-compiled iOS 9/OS X 10.11 apps that do not disable ATS).

Though this timeline explores the context of MD5, 1024-bit, and SGC, it doesn’t even begin to touch on the challenges of removing support for RC4, removing support for SSLv3, or in removing support for weak Diffie-Hellman keys, all of which have affected the ability of users to get online and accomplish day-to-day tasks, and yet failed to evoke similar hand-wringing concern from those advocating for SHA-1 to continue.

In this timeline of events, it becomes obvious that many examples selected were of a specific CA’s failures. This CA was intentionally chosen to show that these concerns are not isolated one-off incidents from a variety of unrelated CAs, but a long-term pattern of behavior. Unfortunately, a number of CAs have similarly problematic histories, so these issues are by no means limited to this single CA. The most vocal critics of the SHA-1 deprecation in the CA industry, and the most vocal advocates of ways in which to extend the dates, have repeatedly abused the concessions and delays afforded in the past, to the point of causing serious and long-lasting harm to the security of the Internet.

With this timeline, patterns begin to emerge that are both telling and damning for the industry. Leading CAs routinely underestimate the risks to users, overestimate the costs, and delay migrating or mitigating for as long as possible. The timeline for deprecating SHA-1 was first finalized in November 2013, despite having been debated for months before, and continued to be debated for years after. Had CloudFlare, Twitter, or Facebook wished to participate in the debate, the door was long open. PayPal previously participated for years in the CA/Browser Forum. Even if these organizations were unable to agree to the IPR policies necessary to join the Forum, the opportunity for “informal” participation had existed for years as well, and was explicitly reiterated in March, 2015:

The failures of the CA industry are profoundly important when discussing the LV proposal by Facebook, CloudFlare, and Twitter . The ways in which these companies propose to mitigate risk hinges upon a reliance on CA policies and practices which can neither be independently evaluated nor technically enforced by browsers. Each of the proposed solutions have been tried before, have been violated before, and unfortunately, but undoubtedly, will be violated again. To ignore this historic context is not just short-sighted, but puts billions of users at risk.

It is within this framework, both of technical concerns and historical context, that the proposal by Facebook, CloudFlare, and Twitter must be evaluated, and ultimately, rejected. As indicated at the start, this will hopefully be the first in a series of posts that examine the risks that Legacy Verified certificates pose, the challenges in finding solutions, the problems with the data being provided in support of this proposal. Hopefully the conclusion of this series can identify possible paths forward — preferably ones which do not put Internet security as a whole at risk.

This is a post in an ongoing series regarding SHA-1 and the CA ecosystem; the next post is Legacy Verified: Legacy Solutions.

An earlier version of this referred to 1996 as the introduction of SGC certificates; as pointed out on Twitter, this was actually mid-1997, rather than late 1996.

While the opinions, conclusions, and inaccuracies are wholly my own, my thanks to the many people who reviewed draft versions of this post and offered feedback and advice.