File: sys/netinet/tcp_input.c
Function: tcp_sack_option()

In OpenBSD implementation of Selective-ACK handling of incoming packets, the SACK holes sorted list is bounded in the TCP established state of the connection by (1) the size of the pool (up to 32K entries), and (2) by the TCP retransmit timer (whose interval could be up to 64 seconds). This means that an attacker could manipulate the connection’s window scaling and RTT, forcing the victim to send a large amount of not-ACKed data and increase its retransmission timeout. This in turn enables the attacker to send a large number of SACKs. As the sorted list of SACK holes becomes larger, inserting additional elements becomes more expensive, resulting in higher and higher CPU consumption that may eventually lead to a denial of service. (The complexity of inserting a new element to a sorted list of n entries so it remains sorted is O(n). The complexity of inserting n elements to the list in a sorted way is O(n^2)).

Adding a new element to the middle of the sorted SACK ranges list:

if (SEQ_LT(cur->start, sack.start) &&
    SEQ_GT(cur->end, sack.end)) {
	 * ACKs some data in middle of a hole; need to
	 * split current hole
	temp = (struct sackhole *)
	    pool_get(&sackhl_pool, PR_NOWAIT);
	if (temp == NULL)
		goto done; /* ENOBUFS */
	temp->next = cur->next;
	temp->start = sack.end;
	temp->end = cur->end;
	temp->dups = cur->dups;
	temp->rxmit = SEQ_MAX(cur->rxmit, temp->start);
	cur->end = sack.start;
	cur->rxmit = SEQ_MIN(cur->rxmit, cur->end);
	if (((sack.end - cur->end)/tp->t_maxseg) >=
		cur->dups = tcprexmtthresh;
	cur->next = temp;
	p = temp;
	cur = p->next;

Adding a new element to the end of the sorted SACK ranges list:

/* At this point, p points to the last hole on the list */
if (SEQ_LT(tp->rcv_lastsack, sack.start)) {
	 * Need to append new hole at end.
	 * Last hole is p (and it's not NULL).
	temp = (struct sackhole *)
	    pool_get(&sackhl_pool, PR_NOWAIT);
	if (temp == NULL)
		goto done; /* ENOBUFS */
	temp->start = tp->rcv_lastsack;
	temp->end = sack.start;
	temp->dups = min(tcprexmtthresh,
	    ((sack.end - sack.start)/tp->t_maxseg));
	if (temp->dups < 1)
		temp->dups = 1;
	temp->rxmit = temp->start;
	temp->next = 0;
	p->next = temp;
	tp->rcv_lastsack = sack.end;