Black Hat USA 2009 brought us the latest release of Moxie Marlinspike’s sslstrip tool. sslstrip is a tool for performing man-in-the-middle (MITM) attacks against TLS/SSL sessions. The previous version simply terminated the TLS connection at the MITM point and forwarded on an unencrypted connection to the client. While this attack was effective, observant users could tell what was happening. Marlinspike’s new version still terminates the TLS connection at the man in the middle point, but then uses a specially crafted X.509 certificate to create a TLS session to the client. The trick here is in the certificate itself; in order to pull this attack off the certificate must appear to be issued to the original website, not from the attacker. Marlinspike was able to circumvent this protection by exploiting a vulnerability present in many web browser. This vulnerability relies on the fact that character strings within X.509 certificates are ASN.1 encoded, but software written in the C programming language typically manipulates character strings as null terminated character arrays. ASN.1 strings are stored using a form of Type-Length-Value (TLV) encoding. C strings are simply terminated by a null byte (\x00). Here’s what this looks like in memory:


X.509 Certificate:
\x15www.bigbank.com


"C String" (char*):
www.bigbank.com\x00


Marlinspike determined that he could purchase a certificate from a major Certificate Authority (CA) with a Common Name (CN) of www.bigbank.com\x00thoughtcrime.org. Since commercial CAs only look at the root domain name and not the subdomains (i.e., thoughtcrime.org) when validating domain ownership and Marlinspike was the legitimate owner of the thoughtcrime.org domain, he was issued a signed certificate containing his specially crafted Common Name.

Things really start getting interesting when a vulnerable web browser attempts to validate a certificate that has been specially crafted in this fashion. For example, a user browses to www.bigbank.com and uses a DNS server whose cache has been poisoned such that www.bigbank.com resolved to an IP address controlled by an attacker. The attacker has a server at this IP address running sslstrip and using a specially crafted certificate with a Common Name of www.bigbank.com\x00evil.com. The user’s vulnerable web browser will perform a C string comparison (i.e., the strcmp() function from the standard <string.h> header file) between the domain being visited (www.bigbank.com) and the Common Name in the certificate presented by the attacker’s server (www.bigbank.com\x00evil.com). Since the browser is using a C string comparison it will assume it hit the end of the string when in encounters the null byte in the Common Name. Thus it will only compare the “www.bigbank.com” preface of the certificate’s Common Name against the domain being browsed to, www.bigbank.com. The end result is that the browser is tricked into thinking that it has made negotiated a valid TLS connection to www.bigbank.com.

Things gets worse. There is nothing a user can do besides inspect the X.509 certificate as it comes across the wire to detect an attack of this type. This is because vulnerable browsers use the same C string functions to display details of a certificate to the user. It’s quite an elegant attack.

Luckily, Marlinspike has been working with vendors to fix this vulnerability. Mozilla Firefox was updated within the week and a security update to Microsoft Internet Explorer should be available via Microsoft update channels soon. If you haven’t updated your browser in some time, we strongly recommend that you do so immediately to protect yourself from this attack and many others.

Summary:

Eurocrypt 2009 was recently held from April 26-30 in Cologne, Germany. Sponsored by the International Association for Cryptologic Research (IACR), the website states that "It is devoted to all aspects of cryptology." This year’s Eurocrypt rump session was held on April 28, which featured a talk entitled "Automatic Differential Path Searching for SHA-1". Authored by researchers at Macquarie University in Sydney, Australia, their work reveals a collision attack on SHA-1 with a complexity of 2⁵² operations (the previous fastest known SHA-1 collision attack had required 2⁶³ operations). This is a significant improvement in finding SHA-1 collisions.

Hash Function Attacks:

A cryptographic hash function is an algorithm that takes a message as an input and computes a fixed-size digest. SHA-1 generates 160-bit digests. The generated digest is used for a variety of applications related to information security, information assurance, and digital trust relationships. When designing new algorithms, designers of cryptographic hash functions aim to fulfill three basic properties:

• Pre-image Resistance:
  Given a hash digest, it is difficult to find any message that will hash to the specified digest value.
• Second Pre-image Resistance:
  Given a message, it is difficult to find a different message that hashes to the same digest value as the original message.
• Collision Resistance:
  It is difficult to find any two unique messages that hash to the same digest value.

In this case, the SHA-1 attacks affect collision resistance, not pre-image or second pre-image resistance. This means that after 2⁵² operations, the researchers are able to generate two unique messages that hash to the same digest value. Obtaining a SHA-1 collision via brute force would require 2⁸⁰ operations. To date, it remains computationally infeasible to perform pre-image and second pre-image attacks on SHA-1. At the time of writing, I am unaware of a practical collision that has been found.

One iteration of the SHA-1 function:

Until recently, SHA-1 was widely regarded as the standard in cryptographic hash functions, and remains widely used in a variety crypto systems and as a normative reference in other RFCs and standards. The transition to the stronger SHA-2 functions presents the potential for interoperability issues, as SHA-2 signatures generated by updated systems may be unsupported by older systems. Adoption of the stronger hash functions must be carefully planned in order to reduce disruption to critical business functions.

The Digital Signature Algorithm (DSA) is an example of an important standard that relies in part on SHA-1. It specifies the use of a 160-bit hash function for the signatures used in 1024-bit DSA keys. The SHA-1 algorithm is nearly always the one used to sign these 1024-bit DSA keys. In order to eliminate reliance on SHA-1, users of 1024-bit DSA keys will need to transition to 2048-bit or larger DSA keys.

The OpenPGP Message Format (RFC 4880) also presents a challenge to the transition away from SHA-1. Section 13.3.2 states that SHA-1 is "the MUST-implement algorithm," and that even "if it is not explicitly in the list [of hash functions configured to be supported], it is tacitly at the end. However, it is good form to place it there explicitly." The GNU Privacy Guard (GnuPG) gnupg command-line tool will automatically reenable SHA-1 if you removed it from a key’s list of supported hash functions, visibly adding it to the end of the list just as suggested in RFC 4880. On the bright side, both GnuPG and the proprietary PGP have supported SHA-256 for well over 5 years now, making interoperability during the transition must less of an issue for users of those popular implementations.

The OpenPGP Web of Trust (WOT) is almost exclusively made up of SHA-1 signatures. Abandoning SHA-1 signatures today would immediately "evaporate" the Web of Trust. Because of the decentralized nature of the WOT, transitioning off SHA-1 will require a collective and distributed effort on the part of WOT users. There is much work to be done to eliminate reliance on the SHA-1 hash function.

The Debian Project uses OpenPGP and the WOT extensively, and has begun the process of transitioning Debian Developers and Debian Maintainers onto stronger crypto algorithms. That link contains some valuable guidance on making the switch as non-distruptive as practicable. Debian’s transition might well serve as an example for other organizations they rely heavily PGP-based cryptgraphic infrastructure.

A centralized, Certificate Authority (CA) based chain-of-trust Public Key Infrastucture (PKI) forms the basis for SSL/TLS authentication, and with that, the trust needed for secure use of the Web. Such a system offers a different set of challenges for a transition to the SHA-2 familiy of hash functions. CAs will need to recreate their intermediate chains-of-trust using SHA-2 signatures and make plans to revoke their SHA-1 signed certificate chain. (Will someone please explain to me how you revoke a root CA certificate?). Users and system administrators with certificates signed using SHA-1 will need to be issued SHA-2 replacements, or more likely will receive a new SHA-2 certificate when they go to renew their certificate with a CA. OS and web browser makers will need to build in support for SHA-2 hash functions if they have not already, and update their lists of trusted root CAs. And of course, users will need to update their OSes and web browsers to support SHA-2 and to receive the updated lists of trusted root CAs.

Every actor has a role to play: end users, organizations, software makers, Certificate Authorities, standards bodies, and of course let’s not forget the system administrators.