Fatally weak MD5 function torpedoes crypto protections in HTTPS and IPSEC

If you thought MD5 was banished from HTTPS encryption, you'd be wrong. It turns out the fatally weak cryptographic hash function, along with its only slightly stronger SHA1 cousin, are still widely used in the transport layer security protocol that underpins HTTPS. Now, researchers have devised a series of attacks that exploit the weaknesses to break or degrade key protections provided not only by HTTPS but also other encryption protocols, including Internet Protocol Security and secure shell.

The attacks have been dubbed SLOTH—short for security losses from obsolete and truncated transcript hashes. The name is also a not-so-subtle rebuke of the collective laziness of the community that maintains crucial security regimens forming a cornerstone of Internet security. And if the criticism seems harsh, consider this: MD5-based signatures weren't introduced in TLS until version 1.2, which was released in 2008. That was the same year researchers exploited cryptographic weaknesses in MD5 that allowed them to spoof valid HTTPS certificates for any domain they wanted. Although SHA1 is considerably more resistant to so-called cryptographic collision attacks, it too is considered to be at least theoretically broken. (MD5 signatures were subsequently banned in TLS certificates but not other key aspects of the protocol.)

"Notably, we have found a number of unsafe uses of MD5 in various Internet protocols, yielding exploitable chosen-prefix and generic collision attacks," the researchers wrote in a technical paper scheduled to be discussed Wednesday at the Real World Cryptography Conference 2016 in Stanford, California. "We also found several unsafe uses of SHA1 that will become dangerous when more efficient collision-finding algorithms for SHA1 are discovered."

Impersonation attacks

The most practical SLOTH attack breaks what's known as TLS-based client authentication. Although it's not widely used, some banks, corporate websites, and other security-conscious organizations rely on it to ensure an end user is authorized to connect to their website or virtual private network. It works largely the same way as TLS server authentication, except that it's the end user who provides the certificate rather than the server.

When both the end user and the server support RSA-MD5 signatures for client authentication, SLOTH makes it possible for an adversary to impersonate the end user, as long as the end user first visits and authenticates itself to a site controlled by the attacker. The so-called credential forwarding attack is carried out by sending carefully crafted messages to both the end user and the legitimate server. To impersonate the end user, an attacker must complete some 2³⁹ (about 5.75 billion) hash computations, an undertaking that requires about an hour using a powerful computer workstation with 48 cores.

The impersonation attack is made possible by the susceptibility of MD5 to collision attacks, in which the two different message inputs generate precisely the same cryptographic hash. Because MD5 is a 128-bit function, cryptographers once expected to find a collision after completing 2⁶⁴ computations (a phenomenon known as the birthday paradox reduces the number of bits of security of a given function by one half). Weaknesses in MD5, however, reduce the requirement to just 2¹⁵ (or 32,768) for a collision or 2³⁹ for more powerful chosen-prefix collisions, in which an attacker can choose different message inputs and add values that result in them having the same hash value. Such an attack would be infeasible if MD5 hadn't been added to TLS in 2008.

SLOTH can also be used to cryptographically impersonate servers, but the requirements are steep. An attacker would first have to make an astronomically large number of connections to a server and then store the results to disk. If the attacker made 2^X connections, it would then require making 2^(128-X) computations. If the number of connections, for example, was 2⁶⁴, the attack would require 2⁶⁴ computations. The precomputation requirements are high enough to be outside the capability of most attackers, but they remain feasible for government-sponsored adversaries or those with similarly deep pockets.

Once again, the same attack would be orders of magnitude harder if TLS didn't allow MD5 to be used to sign message transcripts. SHA1 increases the burden of such attacks, but given current estimates that the function is perilously close to being broken, it doesn't provide sufficient protection, the researchers said. Besides compromising the security of TLS, the design can also undermine protections provided by the secure shell protocol and Internet Key Exchange. In a blog post explaining their technical paper, the researchers wrote:

In response to recent high-profile attacks that exploit hash function collisions, software vendors have started to phase out the use of MD5 and SHA1 in third-party digital signature applications such as X.509 certificates. However, weak hash functions continue to be used in various cryptographic constructions within mainstream protocols such as TLS, IKE, and SSH, because practitioners argue that their use in these protocols relies only on second preimage resistance, and hence is unaffected by collisions. We systematically investigate and debunk this argument.

The researchers behind SLOTH have been privately working with developers of vulnerable software to come up with a fix. A partial list of protocols that were identified as vulnerable included TLS versions 1.1, 1.2, and 1.3; IKE versions 1 and 2; and SSH version 2. Vulnerable software included various versions of OpenSSL, NSS, Oracle Java, BouncyCastle Java, and PolarSSL/mbedTLS. (See the "Affected Software and Responsible Disclosure" section of the blog post linked above for specific versions.) The researchers cited this Internet scan indicating 32 percent of TLS servers supported RSA-MD5 signatures.

SLOTH works by exploiting a new class of class of transcript collision attack that significantly reduces the presumed security of protocols that still use MD5 and SHA1. It was devised by Karthikeyan Bhargavan and Gaëtan Leurent of France's INRIA research institute. The findings generate yet another compelling reason why technical architects should wean themselves off the SHA1 and MD5 functions, even if it generates short-term pain for people who still use older hardware that aren't capable of using newer, more secure algorithms.