Trustwave SpiderLabs Exposes Unique Cybersecurity Threats in the Public Sector. Learn More

Trustwave SpiderLabs Exposes Unique Cybersecurity Threats in the Public Sector. Learn More

Managed Detection & Response

Eliminate active threats with 24/7 threat detection, investigation, and response.

Co-Managed SOC (SIEM)

Maximize your SIEM investment, stop alert fatigue, and enhance your team with hybrid security operations support.

Advisory & Diagnostics

Advance your cybersecurity program and get expert guidance where you need it most.

Penetration Testing

Test your physical locations and IT infrastructure to shore up weaknesses before exploitation.

Database Security

Prevent unauthorized access and exceed compliance requirements.

Email Security

Stop email threats others miss and secure your organization against the #1 ransomware attack vector.

Digital Forensics & Incident Response

Prepare for the inevitable with 24/7 global breach response in-region and available on-site.

Firewall & Technology Management

Mitigate risk of a cyberattack with 24/7 incident and health monitoring and the latest threat intelligence.

Offensive Security
Solutions to maximize your security ROI
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
About Us
Awards and Accolades
Trustwave SpiderLabs Team
Trustwave Fusion Security Operations Platform
Trustwave Security Colony
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

Important Security Defenses to Help Your CISO Sleep at Night

This is Part 13 in my ongoing project to cover 30 cybersecurity topics in 30 weekly blog posts. The full series can be found here.

Read More

2024 Public Sector Threat Landscape: Trustwave Threat Intelligence Briefing and Mitigation Strategies

Trustwave SpiderLabs’ 2024 Public Sector Threat Landscape: Trustwave Threat Intelligence Briefing and Mitigation Strategies report details the security issues facing public sector security teams as...

Read More

How to Create the Asset Inventory You Probably Don't Have

This is Part 12 in my ongoing project to cover 30 cybersecurity topics in 30 weekly blog posts. The full series can be found here.

Read More