Entity expansion

from Wikipedia, the free encyclopedia

The billion laughs (also XML-bomb ) is a type of DoS -attack based on XML - Parser aims.

description

The exemplary entity expansion attack consists of defining ten XML entities , each made up of ten entities from the previous entity. The document ultimately consists of a single instance of the top-level entity, which then expands into a billion copies of the first entity.

In the example below, the string " lol " is chosen as the entity name . Hence the English term billion laughs , which stands for "(one) billion laughs". The difference between billion and billion is based on the long and short scales , two different systems for naming large numbers.

The aim is for the amount of memory required to exceed the memory available to the process that is parsing the XML. This was more likely at the time this vulnerability became known than at the present.

While the actual form of the attack specifically targeted XML parsers, the terms can also be applied to comparable scenarios.

The problem of entity expansion was first reported back in 2003, but it was not fully taken into account until 2008.

Defense

There are several ways to counter this type of attack:

  • Limitation of the allocated memory for the respective parser (if the loss of the document due to incomplete processing is acceptable)
  • Problem detection by the parser when entities are resolved to entities and the evaluation stops with exception handling
  • Treatment of entities as symbols (without evaluation)
  • Lazy evaluation

Some web browsers interrupt the evaluation of entity expansions with an error message, for example Google Chrome ( detected an entity reference loop " entity reference loop ") or Mozilla Firefox (XML processing error "recursive entity reference ").

Code example

When an XML parser loads the following document, it recognizes a root element ( lolz ) that contains the text "& lol9;".

The entity & lol9; is defined as a string that contains ten "& lol8;" strings. Each one of these “&” strings contains ten “” strings, and so on.

After all entity expansions have been processed, this small XML block (less than 1  kB ) would consist of 10 9 = 1,000,000,000 lol , which require almost three gigabytes of memory. 

<?xml version="1.0"?>
<!DOCTYPE lolz [
    <!ENTITY lol "lol">
    <!ELEMENT lolz (#PCDATA)>
    <!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;">
]>
<lolz>&lol9;</lolz>

See also

Individual evidence

  1. ^ Bryan Sullivan: XML Denial of Service Attacks and Defenses . In: Microsoft Corporation (Ed.): MSDN Magazine . November 2009. Retrieved May 31, 2011.
  2. ^ A b Elliotte Rusty Harold : Tip: Configure SAX parsers for secure processing . In: IBM developerWorks . May 27, 2005. Archived from the original on March 4, 2011. Retrieved on March 4, 2011.
  3. ↑ CVE-2003-1564. In: Common Vulnerabilities and Exposures. The MITER Corporation, February 2, 2003, accessed June 1, 2011 .
  4. ^ Bryan Sullivan: XML Denial of Service Attacks and Defenses . Retrieved December 21, 2011.