Connect with our team of offensive security, AI security and pen testing experts at Black Hat Europe 2023. Learn More

Connect with our team of offensive security, AI security and pen testing experts at Black Hat Europe 2023. Learn More

Managed Detection & Response

Eradicate cyberthreats with world-class intel and expertise

Managed Security Services

Expand your team’s capabilities and strengthen your security posture

Consulting & Professional Services

Tap into our global team of tenured cybersecurity specialists

Penetration Testing

Subscription- or project-based testing, delivered by global experts

Database Security

Get ahead of database risk, protect data and exceed compliance requirements

Email Security & Management

Catch email threats others miss with layered security & maximum control

Co-Managed SOC (SIEM)

Eliminate alert fatigue, focus your SecOps team, stop threats fast, and reduce cyber risk

Microsoft Exchange Server Attacks
Stay protected against emerging threats
Rapidly Secure New Environments
Security for rapid response situations
Securing the Cloud
Safely navigate and stay protected
Securing the IoT Landscape
Test, monitor and secure network objects
Why Trustwave
The Trustwave Approach
Awards and Accolades
Trustwave SpiderLabs Team
Trustwave Fusion Platform
SpiderLabs Fusion Center
Security Operations Centers
Technology Alliance Partners
Key alliances who align and support our ecosystem of security offerings
Trustwave PartnerOne Program
Join forces with Trustwave to protect against the most advance cybersecurity threats
SpiderLabs Blog

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 ( 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
          if item->index == i:
               found = true
          item = item->next
     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&nbsp;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)&nbsp;is required (assuming the fragments are received in order). As such, the entire procedure has the following complexity:

Screen Shot 2017-07-06 at 19.16.07

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:

Screen Shot 2017-07-06 at 19.26.21

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:

Screen Shot 2017-07-06 at 19.26.25

Where Screen Shot 2017-07-06 at 19.26.32 denotes the set Screen Shot 2017-07-06 at 19.26.40. 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:

Latest SpiderLabs Blogs

The 2023 Retail Services Sector Threat Landscape: A Trustwave Threat Intelligence Briefing

The annual holiday shopping season is poised for a surge in spending, a fact well-known to retailers, consumers, and cybercriminals alike. The latter group, however, is poised to exploit any...

Read More

Pwning Electroencephalogram (EEG) Medical Devices by Default

Overall Analysis of Vulnerability Identification – Default Credentials Leading to Remote Code Execution During internal network testing, a document was discovered titled the “XL Security Site...

Read More

Hidden Data Exfiltration Using Time, Literally

I was looking at my watch last week and my attention was moved towards the seconds over at the right of the watch face, incrementing nicely along as you’d expect. Now, I don’t know if I’d just spent...

Read More