A Computational Complexity Attack against Racoon and ISAKMP Fragmentation

Trustwave recently reported a remotely exploitable computational complexity vulnerability in the racoon isakmp daemon that is part of the ipsec-tools open-source project (http://ipsec-tools.sourceforge.net/). The vulnerability is present in the handling of fragmented packets. A computational complexity attack seeks to cause a denial of service condition by exploiting the worst-case algorithmic complexity of an algorithm. This can be done either in terms of space or computation time where the input parameters to the algorithm's complexity are definable by the attacker.  In this case, the algorithm in question is responsible for maintaining a list of fragments making up a request in the Internet Security Association and Key Management Protocol (isakmp) protocol so the complete packet can be reconstructed upon receiving the final fragment.

The algorithm to determine and compute the reassembled packet from the fragments is based on a simple linked list walk. The pseudo-code for the algorithm is given below:

item = fragment-list
last-index = 0
while (item->next)
     if item->is-last:
          last-index = item->index
     item = item->next
item->next = new-item
if last-index == 0:
     return false
for(i = 0; i < last-index; i++)
     item = fragment-list
     found = false
     do
          if item->index == i:
               found = true
               break
          item = item->next
     while(item)
     if !found:
          return false

The complexity of the above algorithm can be split into two distinct phases, the first phase being the insertion of the new item ('new-item') into the fragment-list and the second phase determining if the fragment list is complete. Clearly the complexity of adding a single packet fragment into the list is linear in the number of fragments already in the list, that is for n fragments. This is because the implementation first walks the list to determine the value of 'last-index' (the fragment index corresponding to the last fragment in the chain) when adding the 'new-item' to the end of the list.

The complexity of the remaining part of the procedure is more interesting and involves a simple quadratic walk through the linked list to search for the fragment corresponding to a given index across all fragment indices. This procedure is only performed once the final fragment has been received and added to the fragment list. For each fragment of index 'i' in the fragment list a walk of complexity O(i) is required (assuming the fragments are received in order). As such, the entire procedure has the following complexity:

Fragging Racoon in the Worst Case

In order to cause the most devastating denial of service attack against the racoon daemon by exploiting the complexity of the fragment reassembly procedure we need to know the order in which to send the fragments in order to construct a fragment list resulting in worst case algorithmic behavior.

Again, taking each of the phases in order, the first phase does not utilize the index of the current fragment to be added to the fragment list and as such any order will result in worst-case behavior. In the case of the second phase, worst-case complexity is achieved when the inner-while loop contained in the for-loop body performs worst. Since the for-loop iterates over index values ranging from zero to 'last->index', it follows that it will perform the worst when specifying fragment indexes in order, either ascending or descending. For instance:

The icing on the computational-cake

The attack becomes more explosive when we add in the fact that no attempt is made to prune repeated fragment indices from the 'fragment-list'. This means that a remote attacker is free to repeat a fragment index as many times as they like. As such, the following strategy can be utilized to maintain the attack over time:

Where denotes the set . Finally, in order to ensure the packet fragments cannot be reassembled, it is necessary to ensure a single fragment index is missing from the fragment list. In the above we omit the index 254.

To demonstrate the issue, the following graph plots the number of items in the fragment list against the total number of comparisons performed in the fragment reassembly procedure for the strategy given above,

The explosive increase in complexity coincides with the sending of the fragment with 'last-fragment' flag set in the fragment flags (namely the fragment with index 255).

In conclusion, by manipulating packet fragments sent as a part of an ISAKMP request an attacker can create a worst case complexity scenario in the algorithm used to reassemble those packets. The result is a denial of service condition in the ipsec-tools racoon daemon. Unfortunately ipsec-tools is an unmaintained open-source project, so no patch is currently available for this vulnerability. As a workaround we recommend that admins recompile racoon with ENABLE_FRAG set to false/0 (which compiles racoon without fragmentation support). NetBSD 8 will include a fix when the branch is officially released.

For more information please see the full advisory: https://www.trustwave.com/Resources/Security-Advisories/Advisories/TWSL2017-012/?fid=9774