Side channel attacks on widespread protocols such as TLS seem to happen with uncomfortable regularity in recent years. We’ve seen compression-related attacks in CRIME and BREACH, timing issues with Lucky13, and downgrade attacks on weak or vulnerable key exchange mechanisms with LogJam and DROWN. As specification changes and implementation changes are rolled out to counter these problems, it would seem that the rate of vulnerability disclosure would decrease. Sadly, based on the results from Blackhat USA this year, this is not the case. In this post, I’ll talk about HEIST  – a brilliant new attack on HTTPS that exploits the properties of TCP.
At its core, HEIST exploits the flow control algorithm. TCP controls the rate at which it sends data by observing the packet acknowledgements sent by the receiver. If a sender transmits 5 packets and all are acknowledged, then the sender concludes that there is little to no congestion on the path to the receiver. It then increases the data window that controls the maximum number of outstanding packets send to the receiver. This process continues to additively increase the window size until such time that a packet acknowledgement does not arrive at the sender within some allotted timeout value. At this time, the window is decreased by a multiplicative factor and the procedure tries to slowly build to the optimal point of congestion. For more details about this and the TCP flow control variants, see .
The size of data that can possibly fit in a single TCP packet is called the Maximum Segment Size (MSS). I’ll denote one MSS as \(d\). If a piece of data is larger than \(d\), then the data is segmented into blocks of size \(d\). The sender then tries to send the entire piece of data in TCP as quickly as possible using the flow control algorithm above.
Assume that the initial window size for TCP is 2. If the data to be sent fits within is less than \(2d\), then, without any packet loss, the entire data can be transmitted in a single round trip. If, however, the data is longer than \(2d\), at least two round trips will be required to transmit the data in total. This key piece of information is the basis of HEIST.
There are three timestamps to consider. \(T_1\) is the time the initial request for data is sent, \(T_2\) is the time the first byte of data is received, and \(T_3\) is the time the entire data is received. If \(T_3 \approx T_2\), then it must be the case that the the data fit within a single window. Otherwise, if \(T_3 > T_2\) by some non-negligible amount, then the data must have required two windows, or round trips, to transfer.
So how can an attacker use this timing information to attack HTTPS? The answer is apparently simple. The adversary only needs to capabilities:
If the adversary can reflect data in a response, it can measure the size of the actual data (non-reflected bytes) carried in a response. It does this by measuring the time taken to receive the response. To explain how, let’s start with a simple example. The attacker starts small by only inserting a single byte into the reflected payload. If \(T_2 \approx T_3\), then the data fit within a single window. So, the attacker increases the reflected payload size and repeats this measurement. It does so until the data requires two RTTs to transfer. Then, knowing the value of \(d\), the initial window size, and the size of the reflected payload, the attacker can determine the amount of actual bytes in the response. (Taking into account header TCP and TLS headers, of course.)
Using this approach, the attacker can learn the size of a response. This is all that’s needed to launch an attack like BREACH or CRIME. Specifically, the attacker carefully chooses his reflected payload contents such that they match secret values in the response and are therefore compressed together. The attacker can then learn, byte-by-byte, the values of these secrets by checking whether his guessed value decreased the response size or not. (This single bit of information leaks whether or not his guess was correct.)