The TCP "challenge ACK" side channel

Side-channel attacks against various kinds of protocols (typically networking or cryptographic) are both dangerous and often hard for developers and reviewers to spot. They are generally passive attacks, which makes them hard to detect as well. A recent paper [PDF] describes in detail one such attack against the kernel's TCP networking stack; the bug (CVE-2016-5696) has existed since Linux 3.6, which was released in 2012. Ironically, the bug was introduced because Linux has implemented a countermeasure against another type of attack.

There are a number of pieces of information that an attacker needs to interfere with a TCP connection between two hosts. To start with, the so-called four-tuple, which consists of the source IP address, source port number, destination IP address, and destination port number, is needed. Several of those values can be guessed or inferred (e.g. destination IP and port), but there is another piece of information needed to actually interfere with a connection.

TCP has 32-bit sequence numbers that are used to order the packets in the connection stream. They are also an important part of the packets used to establish and break down connections. A packet that could interfere with a connection must have a sequence number that is within the receive window of the target. That window effectively determines the range of sequence numbers that are acceptable.

Once upon a time, in a far more trusting era, sequence numbers were fairly easily predicted, but those days are long gone. These days, sequence numbers are randomized to thwart various kinds of packet-injection and connection-spoofing attacks. An eavesdropper can still observe the sequence numbers in a conversation, but an "off-path" attacker must guess. By randomizing the initial sequence number (ISN) used by a connection, network stacks make guessing difficult enough to stop most off-path attacks.

But if a way can be found to more quickly narrow in on the sequence numbers used in a connection, off-path attackers can be more efficient in their probing—to the point where they can inject packets into an established connection. That is effectively what the researchers found.

But first, there is another obstacle to overcome: according to the paper, off-path attacks have generally been limited by the need to get unprivileged malware running on one of the endpoints to determine whether two hosts are actually communicating. But the researchers found a way to quickly determine whether two hosts are communicating and what port numbers they are using, without any assistance from malware.

Linux is the only operating system vulnerable to this attack because it is the only one that has faithfully implemented RFC 5961, which was proposed to avoid a different kind of packet injection attack. It uses "challenge ACKs" to avoid resetting a connection when a spoofed connection request (SYN) or connection termination (RST) packet with a sequence number within the receive window is received. The challenge ACK will allow long-lived connections to be more resistant to these spoofed packets that are meant to close the connection.

The challenge ACKs require that the original sender reply with the exact sequence number expected for the next packet, not just one within the receive window, which is more difficult for an off-path attacker to arrange. But challenge ACKs also consume resources, so the RFC recommends that a limit be imposed on the number of challenge ACKs sent over a given time frame (Linux used 100/second by default). Since challenge ACKs were expected to be rare occurrences, the counter for rate-limiting them was global for all TCP connections on the system—and the RFC specifically directed that regular ACKs should not be counted. Because of this, challenge ACKs provide a side channel:

The general outlines of an attack are as follows. The attacker establishes an ordinary connection to the server, then sends a stream of bogus RST and SYN packets to force the target to generate the maximum number of challenge ACKs. Some spoofed packets "from" the client of interest are also sent. If all of the expected 100 challenge ACKs are received on the regular connection, then the four-tuple in the spoofed packet does not represent an active connection, but if some are missing, they must have been sent as challenge ACKs in response to spoofed packets, indicating that a connection exists.

Once that is established, in-window sequence numbers need to be determined—challenge ACKs can help there too. Once again, challenge ACKs are provoked using a normal connection and the number received are counted. Spoofed RST packets with a guessed sequence number are also sent; the number of challenge ACKs received on the regular connection allow the attacker to infer whether the sequence number is within the window or not. Further probing with spoofed ACKs can narrow things down to the exact sequence number expected for the next packet.

Two kinds of attacks are described in the paper. The easiest is to simply reset an in-progress connection. The other hijacks the connection to inject content of the attacker's choosing. The paper describes the former being reliably deployed against SSH and Tor connections, while it mentions the latter being targeted at long-lived connections for data like video streams, advertisements, or news sites.

There are some more wrinkles to the attack, of course, including synchronizing with the host's clock so that the one-second boundary can be reliably determined. That, too, uses challenge ACKs. Other hurdles are also discussed in the paper. But the attack can have far-reaching effects as the team's short YouTube video demonstrates. It injects some JavaScript into a web session to display attacker-controlled content.

The research was also highlighted in an article in a University of California, Riverside (UCR) publication as most of the researchers are students or faculty there. Yue Cao, Zhiyun Qian, Zhongjie Wang, Tuan Dao and Srikanth V. Krishnamurthy of UCR were joined by Lisa M. Marvel from the United States Army Research Laboratory in writing the paper, which was presented at the USENIX Security Symposium on August 10.

It is an interesting and clever attack that sadly only lacks a catchy name, colorful logo, and hype-filled web site. Cao did alert kernel developers to the problem, which was fixed in the mainline in July (and appears in the 4.7 kernel). The fix raises the limit to 1000 challenge ACKs per second, but also adds some randomization to the value so that counting will be less effective. In addition, the patch notes per-socket rate-limiting is available, which could lead to the removal of the global challenge ACK count down the road; some work toward that end has been merged as well.

The fix has not made it to the stable kernels yet, but there is a mitigation available in the form of the tcp_challenge_ack_limit sysctl knob. Setting that value to something enormous (e.g. 999999999) will make it much harder for attackers to exploit the flaw.

Spoofing source IP addresses is not technically difficult, though it may be hard to get the packet through routers and the like in some cases. A Center for Applied Internet Data Analysis study shows that nearly half of the autonomous systems on the internet are at least partly spoofable, though. There are, as yet, no reports of attacks using this technique in the wild, though one would guess it won't be long before we do see some.

In the end, challenge ACKs seem a reasonable solution to a real problem, but Linux played the role of a guinea pig here. There are upsides to doing that, such as providing a platform where the researchers could discover the problems in the RFC. There are downsides, as well; Linux is currently getting some bad press about its networking implementation, for example. On the whole, though, these problems needed to be found—and now they are.