billion laughs - DoS attack

Question

<!DOCTYPE root [
 <!ENTITY ha "Ha !">
 <!ENTITY ha2 "&ha; &ha;">
 <!ENTITY ha3 "&ha2; &ha2;">
 <!ENTITY ha4 "&ha3; &ha3;">
 <!ENTITY ha5 "&ha4; &ha4;">
 ...
 <!ENTITY ha128 "&ha127; &ha127;">
 ]>
 <root>&ha128;</root>

supposedly this is called a billion laughs DoS attack.

does anyone know how it works?

Answer 1

It writes "Ha !" 2¹²⁸ times.

Answer 2

One of the XML bombs - http://msdn.microsoft.com/en-us/magazine/ee335713.aspx

An attacker can now take advantage of these three properties of XML (substitution entities, nested entities, and inline DTDs) to craft a malicious XML bomb. The attacker writes an XML document with nested entities just like the previous example, but instead of nesting just one level deep, he nests his entities many levels deep...

There is also code to protect from these "bombs" (in .NET world):

XmlReaderSettings settings = new XmlReaderSettings();
settings.ProhibitDtd = false;
settings.MaxCharactersFromEntities = 1024;
XmlReader reader = XmlReader.Create(stream, settings);

Answer 3

<!ENTITY ha "Ha !"> defines an entity, &ha; that expands to "Ha !". The next line defines another entity, &ha2; that expands to "&ha; &ha;" and eventually, "Ha ! Ha !".

&ha3; turns into Ha ! Ha ! Ha ! Ha !, and so on, doubling the number each time. If you follow the pattern, &haN; is "Ha !", 2^N-1 times, so &ha128, expands to 2¹²⁷ "Ha !"s, which is too big for any computer to handle.