The XML Signature: Syntax and Usage

The W3C XML Signature defines XML syntax for demonstrating the authenticity of a digital message or document.  If a digital signature is deemed to be a valid signature, it is highly likely that the message was created by a known sender and that the message has not been altered in transit. Therefore, XML Signatures provide a good method to detect a forgery or tampering of important XML data.

XML Signature Definition

XML Signatures are defined in the W3C recommendation XML Signature Syntax and Processing.  The W3C recommendation document defines different resources that an XML signature may be applied to; this article only discusses the XML Signature in context of an enveloped signature in XML data.

An Enveloped XML signature is an XML signature that is computed over XML content that contains the signature as an element.  The XML content provides a root XML document element, which contains the signature element somewhere along the XML tree.  According to the W3C recommendation, the XML signature should not take itself into account when computing the signature value.  Note that there is a difference between an enveloped signature as described above, and an enveloping signature.  In an enveloping signature, the signature is the parent object.

XML Signature Requirements

The requirements for XML signatures can be found in the W3C working draft XML-Signature Requirements.  Some important aspects of the requirements are as follows:

  • XML Signatures are generated from a hash over the canonical form of a signature manifest.
  • The signature manifest is a collection of references to the objects being signed.
  • An XML Signature must be an XML Element.
  • The XML Signature must preserve the XML Tree, except for the addition of the XML Signature Element.

Aside from enveloped XML signatures, W3C requires that detached XML signatures are possible (the signature is not part of the XML tree it is signing), but those are outside of the scope of this document.

XML Signature Syntax

XML Signatures are represented by the Signature XML element.  The Signature element contains exactly one SignedInfo element, and has zero or one ID attributes.  The SignedInfo element contains exactly one CanonicalizationMethod element and exactly one SignatureMethod element.  The SignatureMethod element contains one or more Reference elements.  Each Reference element has zero or one URI attributes.  Each Reference element can contain zero or one Transforms element, and must contain exactly one DigestMethod element, and exactly one DigestValue element.  The Signature element must contain exactly one SignatureValue element.  The Signature element can contain zero or one KeyInfo elements, and zero or more Object elements.  Each Object element has zero or one ID attributes.  Note that the Object element is typically used for enveloping signatures, not enveloped signatures.

A breakdown of the XML Signature XML Tree is described by the following diagram.   The following description of the above is taken from the W3C recommendation for XML Signatures.  In the description “?” denotes zero or one occurrence; “+” denotes one or more occurrences; and “*” denotes zero or more occurrence.

  <Signature ID?> 
     <SignedInfo>
       <CanonicalizationMethod/>
       <SignatureMethod/>
       (<Reference URI? >
         (<Transforms>)?
         <DigestMethod>
         <DigestValue>
       </Reference>)+
     </SignedInfo>
     <SignatureValue> 
    (<KeyInfo>)?
    (<Object ID?>)*
   </Signature>

XML Signature Verification

When an XML Signature is created, the SignedInfo element is the element that is actually signed.  XML Signature validation requires two steps, which are as follows:

  1. Signature Validation – The value of the element SignatureValue must match the result of processing SignedInfo with the CanonicalizationMethod and SignatureMethod.
  2. Reference Validation – All content identified by a Reference object must be transformed if applicable, then processed with the specified DigestMethod.  The result must match the DigestValue for that reference.

These steps can be performed in either order, but for the sake of understanding and convenience, we will delve into Reference Validation first.

Reference Syntax

Each Reference element contains zero or one URI attributes.  The Schema definition for Reference elements also contains optional attributes Id and Type, but we will not consider those in this document.  The URI attribute identifies a data object using a URI-Reference.  The value of this attribute can be any URI, where URI syntax is dictated by RFC 3986.  The URI can also be in the form of an XPointer, which is both a common and useful tool when dealing with enveloped XML Signatures.

Defining a URI with an XPointer

The XPointer is a fragment identifier for a URI described by W3C in XML Pointer Language (XPointer) Version 1.0.  A fragment identifier is a short string of characters that refers to a resource that is subordinate to another resource.  According to the XPointer specification version 1.0, an XPointer can act as a fragment identifier for resources with the following Internet media types:

  • text/xml
  • application/xml
  • text/xml-external-parsed-entity
  • application/xml-external-parsed-entity

XPointer is based on the XML Language Path (XPath) and can be used to address internal structures of XML documents.  XPath is described by W3C in XML Path Language (XPath) Version 1.0.

The character “/” is used to represent the root of an XML document.  Since an enveloped XML Signature is usually a Signature over the entire XML document containing the signature, it is common to see a Reference element definition such as:

<ds:Reference URI=”#xpointer(/)”>… </ds:Reference>

You’ll notice that in the previous example the Reference element has a prefix of “ds:”.  This means that the XML Namespace ds contains the element Reference.  XML Namespaces are described in Namespaces in XML 1.0 (Third Edition).  XML Namespaces provide a way to qualify element and attribute names in XML by associating them with namespaces identified by URI resources.  The use of the namespaces ds  or dsig are common, but optional.

Reference Transforms

The Transforms element is optional, and contains an ordered list of Transform elements.  The Transform elements describe how the data object was created before being digested.  The output of each Transform serves as the input to the next Transform.  The input to the first transform is the dereferenced URI attribute of the Reference element.  Transform elements consist of an Algorithm attribute that specifies a URI for the algorithm.  Depending on the algorithm, the content of the Transform element can provide additional data to determine how the algorithm processes the data.

DigestMethod

A Reference element must contain a DigestMethod element.  The required attribute Algorithm specifies a URI to an algorithm that is used to compute the DigestValue over the data object that is the result of the last transform.  If no transforms were performed, the DigestValue is computed over the dereferenced URI of the Reference element.  DigestValue is also a required element.  The DigestValue element contains the encoded value of the digest.  The digest is always encoded using base64.

Reference Validation

Reference validation is the first step of core validation in XML Signature verification.  W3C breaks reference validation into the following ordered steps:

  1. Canonicalize the SignedInfo element based on the Canonicalization Method in SignedInfo.
  2. For each Reference in SignedInfo:
    1. Obtain the data object to be digested.  This involves dereferencing the Reference object’s URI and applying transforms as necessary.
    2. Digest the resulting data object using the DigestMethod specified in the Reference section.
    3. Compare the generated digest value against DigestValue in the Reference.  If the generated digest does not match, validation fails.

Signature Syntax

The Signature element must contain a SignatureValue element.  The SignatureValue element contains the base64 encoded signature computed over the SignedInfo element.  The SignedInfo element must contain a single CanonicalizationMethod element and a single SignatureMethod element.  Both the CanonicalizationMethod element and the SignatureMethod element have the required attribute Algorithm which represents a URI to the algorithm used for canonicalization and signing, respectively.

Signature Validation

The W3C breaks signature validation into the following steps:

  1. Obtain the key information, either from a KeyInfo element or from an external source.  Documentation for the KeyInfo element is available from W3C.
  2. Obtain the canonical form of the SignatureMethod using the CanonicalizationMethod and use the result (and previously obtained KeyInfo) to confirm the SignatureValue over the SignedInfo element.

Verification

After Reference validation and signature validation are completed, the XML Signature has been verified.  If either of these two steps fails, the signature is not verified.  Verification implies that you can be sure beyond a reasonable doubt that the xml originated from a valid source.  Hopefully now you know a little more about XML Signatures.  Happy Security!

Advertisements

XML Security: A Billion Laughs

The Billion Laughs Attack

The Billion Laughs attack is a denial-of-service attack that targets XML parsers.  The Billion Laughs attack is also known as an XML bomb, or more esoterically, the exponential entity expansion attack.  A Billion Laughs attack can occur even when using well-formed XML and can also pass XML schema validation.  For this reason, it may sometimes be tricky to figure out how to mitigate the threat of the Billion Laughs attack when working with different XML parsers.

Background

In order to understand how to mitigate the Billion Laughs attack, it is important to understand the processes to lead the denial-of-service that this attack causes.  I will assume that you have a basic knowledge of XML, and if you don’t it isn’t hard to understand.  A quick search engine query or a quick look at Wikipedia, should provide you with all you need.  The topic that is important to understand the Billion Laughs attack is the XML entity.

An XML entity is a symbolic representation of information, just like a variable in a computer program.  In XML, entities must be declared in the Document Type Definition (DTD), just like an element or an attribute.  There are multiple types of entities; entities are either parsed or unparsed, general entities or parameter entities, and internal or external entities.  In this explanation we will deal primarily with general entities, of both the internal and external type.

To define an XML entity in the DTD, simply use the XML entity syntax:

<!ENTITY entityName "Text Value">

Then to use the entity in the XML document content section, you use an ampersand (&) followed by the entityName you specified in the DTD followed by a semicolon (;).  This may seem familiar to you as there are five pre-defined XML entities lt, gt, amp, apos, and quot.  To use these entities in XML or HTML you would type &lt;, &gt;, &amp;, &apos;, and &quot; respectively.

To use the XML entity created above, you would add the following to the document content section:

&entityName;

When a DOM or SAX implementing XML parser encounters XML entities while parsing, it tries to expand them.  How this is done depends on whether or not the entity is a parsed or unparsed entity, but the concept is the same.  The parser will replace the entity in the document content with the entity definition and continue parsing.  If the entity definition contains references to other entities, these will also have to be expanded.  That is the key to the Billion Laughs attack.

Exploit

The vanilla Billion Laughs attack is illustrated in the XML file represented below.

<?xml version="1.0"?>
<!DOCTYPE lolz [
<!ENTITY lol "lol">
<!ENTITY lol2 "&lol;&lol;&lol;&lol;&lol;&lol;&lol;&lol;&lol;&lol;">
<!ENTITY lol3 "&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;">
<!ENTITY lol4 "&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;">
<!ENTITY lol5 "&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;&lol4;">
<!ENTITY lol6 "&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;&lol5;">
<!ENTITY lol7 "&lol6;&lol6;&lol6;&lol6;&lol6;&lol6;&lol6;&lol6;&lol6;&lol6;">
<!ENTITY lol8 "&lol7;&lol7;&lol7;&lol7;&lol7;&lol7;&lol7;&lol7;&lol7;&lol7;">
<!ENTITY lol9 "&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;&lol8;">
]>
<lolz>&lol9;</lolz>

In this example, there are 10 different XML entities, lol – lol9. The first entity, lol is defined to be the string “lol”.  However, each of the other entities are defined to be 10 of another entity.  The document content section of this XML file contains a reference to only one instance of the entity lol9.  However, when this is being parsed by a DOM or SAX parser, when lol9 is encountered, it is expanded into 10 lol8’s, each of which is expanded into 10 lol7’s, and so on and so forth.  By the time everything is expanded to the text lol, there are 100,000,000 instances of the string lol.  If there was one more entity, or lol was defined as 10 strings of “lol”, there would be a Billion “lol”s, hence the name of the attack.  Needless to say, this many expansions consumes an exponential amount of resources and time, causing the DOS.

Attack Variations

The above attack is known esoterically as the Exponential Entity Expansion XML Bomb.  A variation on it is known as the Quadratic Blowup attack.  In this attack, instead of defining multiple layers of entity expansion, the attacker just defines one very large entity and refers to it many times.

<?xml version="1.0"?><!DOCTYPE payload [
<!ENTITY A "AAAAAAAAAAAAAAAAAAA...">
]>
<payload>&A;&A;&A;&A;&A;&A;...</payload>

In this example, imagine that the entity A contains tens to hundreds of thousands of ‘A’s and that payload contains tens or hundreds of thousands references to A.  This can consume a large amount of resources with fewer expansions than the Exponential Entity Expansion Attack.

So far, all of the attacks mentioned have utilized internal entities.  An interesting variation on this attack uses external entities.  External entities can be defined as follows
<!ENTITY stockprice SYSTEM "http://www.website.com/dos_util">

In this example the implementation of dos_util can vary.  The first type of attack would be a resource that never returns, stalling the parser infinitely.  This would DOS one thread of execution, but wouldn’t consume many resources.  Another example could be a dos_util that wrote an infinite amount of data when accessed.  A less obvious example would simple be a very large, legitimate looking file.

Mitigating the Threat of a Billion Laughs

Because the behavior of each XML parser may be different based on implementation, there is no one way to prevent Billion Laughs attacks.  However, there are a few main techniques used to prevent this denial-of-service attack.

  • Turn off entity expansion.
  • Limit the number of Entity Reference Nodes that the parser can expand.
  • Limit the number of characters entities can expand to.

All, some, or none of these options may be available to you depending on what XML parsing API you are using.  Each method also has its pros and cons.  For example, you might require entity expansion in your code, so in that case, obviously turning off entity expansion is not a good choice.  Methods for mitigating the Billion Laughs threat in some common XML parsers are described below.

Xerces

Vulnerable Code:

#include <xercesc/parsers/XercesDOMParser.hpp>
#include <xercesc/dom/DOM.hpp>
#include <xercesc/sax/HandlerBase.hpp>
#include <xercesc/util/XMLString.hpp>
#include <xercesc/util/PlatformUtils.hpp>
#include <iostream>

using namespace std;
XERCES_CPP_NAMESPACE_USE

int main (int argc, char* argv[]) {

try {
XMLPlatformUtils::Initialize();
}
catch (const XMLException& toCatch) {
return EXIT_FAILURE;
}

XercesDOMParser parser;
parser.setValidationScheme(XercesDOMParser::Val_Always);
parser.setDoNamespaces(true);
parser.setDoSchema(true);

HandlerBase errHandler;
parser.setErrorHandler(&errHandler);

if (argc != 2) {
cerr << "Usage: lol_vuln lol.xml" << endl;
return EXIT_FAILURE;
}

const char* xmlFile = argv[1];
try {
parser.parse(xmlFile);
}  catch (...) {
return EXIT_FAILURE;
}
return 0;
}

Fixed Code:

#include <xercesc/parsers/XercesDOMParser.hpp>
#include <xercesc/dom/DOM.hpp>
#include <xercesc/sax/HandlerBase.hpp>
#include <xercesc/util/XMLString.hpp>
#include <xercesc/util/PlatformUtils.hpp>

// Include the security manager
#include <xercesc/util/SecurityManager.hpp>

#include <iostream>

using namespace std;
XERCES_CPP_NAMESPACE_USE

int main (int argc, char* argv[]) {
try {
XMLPlatformUtils::Initialize();
} catch (const XMLException& toCatch) {
return EXIT_FAILURE;
}

XercesDOMParser parser;
parser.setValidationScheme(XercesDOMParser::Val_Always);
parser.setDoNamespaces(true);
parser.setDoSchema(true);

SecurityManager sm;
sm.setEntityExpansionLimit(100);
parser.setSecurityManager(&sm);

HandlerBase errHandler;
parser.setErrorHandler(&errHandler);

if (argc != 2) {
cerr << "Usage: lol_no_vuln lol.xml" << endl;
return EXIT_FAILURE;
}

const char* xmlFile = argv[1];
try {
parser.parse(xmlFile);
} catch (...) {
}
return 0;
}

Explanation:

In Xerces, the way to mitigate the Billion Laughs attack is to create a SecurityManager and set an Entity Expansion Limit, which is the number of entities an entity can expand to.  If the number of entity expansions bypasses this limit, Xerces throws a SAXParserException.  This easily prevents the Exponential Entity Expansion Attack, and if set low enough, will prevent crippling Quadratic Blowup attacks, although this is not as effective at preventing Quadratic Blowup Attacks as it is Exponential Entity Expansion Attacks.  The Entity Expansion Limit does not protect against external entity attacks.