CRIME, TIME, BREACH and HEIST: A brief history of compression oracle attacks on HTTPS

The HEIST vulnerability was presented at Black Hat USA 2016 by Mathy Vanhoef and Tom Van Goethem. In this presentation, new techniques were presented that enhanced previously presented padding oracle attacks on HTTPS, making them more practical.

In a padding oracle attack, the attacker has partial control of part of a message that contains secret information, and is compressed, then encrypted before being sent over the network. An example of this is a web page that contains a CSRF token and echoes an attacker’s message.

This type of attack is not new, it was originally proposed by John Kelsey in 2002, then practically demonstrated by Juliano Rizzo and Thai Duong as CRIME in 2012 at ekoparty. CRIME worked by exploiting TLS compression on messages sent from the client to the server. This technique required a man-in-the-middle position.

In March 2013 at Black Hat EU, Tal Be’ery presented an extension of CRIME called TIME that introduced two new enhancements:

1. Using CRIME for server-to-client messages.

2. Exploiting TCP window sizes to allow the attack to take place without a man-in-the-middle position.

Later in 2013 at Black Hat USA, Angelo Prado, Neal Harris and Yoel Gluck presented BREACH, an attack that reproduced enhancement 1. from the TIME attack.

BREACH got more press than TIME did, and was generally much more well-known in the infosec community (for example, the Wikipedia article on CRIME mentions BREACH but not TIME).

The HEIST presentation in 2016 re-introduced the forgotten enhancement 2. from TIME, but used a slightly different technique (the Fetch API, which did not exist in 2013), and applied the attack in a novel way to HTTP/2 (also did not exist in 2013).

It turns out that each of these presentations introduced something that was previously discovered as if it were new.

1. The original CRIME presentation described the server-to-client attack that was presented as new in both TIME and BREACH. Note: the BREACH team retroactively added references to TIME and the original CRIME slides that introduced the attack in the final version of their paper.

2. TIME described the TCP window timing side-channel that was re-discovered in HEIST.

In conclusion, it’s hard to find truly original ideas in information security. When presenting results that build on previous research, it occasionally happens that other people may have found the same results. The information security community should try to be as thorough as possible when researching prior art and crediting existing research.