XML Signature Transform Simplification: Requirements and Design

3.1.1 Current mechanisms to determine what is signed

Applications usually follow one of these mechanisms to determine what is signed

• Trust the signer completely

  Some applications do not inspect the transform chain at all. They expect that signer has sent a meaningful and safe transform chain, and since the transform chain is also signed it assures that the chain has not changed in transit.

  This does not work for scenarios where the verifier has little trust in the signer. As an example, suppose there is a application that expects requests to signed with the user's password, and there are tens of thousands of users. This application will of course not trust all of its users, and given the possibility of DoS attacks, and that some transforms can change which is really signed, it will not want to run a chain of transforms that it doesn't understand.

• Check predigested data

  Some XML signature libraries have a provision to return the predigested data back to the application, i.e. the octet stream that results from running all the transforms, including an implicit canonicalization at the end.

  The predigested data however cannot be easily compared with the expected data. Suppose the application expects XML elements A, B and C to be signed, it cannot just convert A, B, C to octet streams and search for them inside the predigested data octet stream. The predigested data is canonicalized, and so the search might fail. Also this mechanism is subject to wrapping attacks, as there is no information as to which part of the original document produced this predigested data.

• Check nodeset just before canonicalization

  If the transform chain only has nodeset->nodeset transforms (i.e. XPath or EnvelopedSig) in the beginning, followed by one final nodeset->binary transform (i.e. a C14n transform), then an implementation can return the nodeset just before the canonicalization. Unlike the predigested data, this is much easier to compare - DOM specifically has a method to compare nodes for equality, so this method could be used to compare expected nodeset with nodeset just before canonicalization.

  Unfortunately this mechanism does not work if there is any transform that causes an internal conversion from nodeset->binary->nodeset, because in such case the nodes cannot be compared any more. An XSLT transform does this kind of conversion as does the DecryptTransform.

• Put restrictions on transforms

  Many higher level protocols put restrictions on the transforms. For example, ebXML specifies that there should be exactly two transforms, namely XPath and then the EnvelopedSig transform. SAML specifies there should be only one transform, the EnvelopedSig transform. This is not a generic solution, but it works well for these specific cases.

3.1.2 Problems with the XPath Transforms

The XPath transform is a very useful transform to specify what is to be signed. Id based mechanisms are simpler, but they have many problems:

1. An Id identifies a complete subtree, if some parts of the subtree have to be excluded an XPath has to be used.

2. An Id attribute has to be of type ID. If there is no schema/DTD information it is not possible to determine the type. Some implementations get around this by having certain reserved names, e.g. xml:id or wsu:id. These attributes are allowed everywhere and assumed to be of type ID even if there is no schema available.

3. Ids require schema changes usually, i.e. the schema has to identify which elements can have id attributes.

4. Ids can also lead to wrapping attacks.

1. A regular XPath Filter specifies XPaths "inside out". Anything more difficult than the simplest XPath requires using the "count" and other special functions. The XPath is often so complex it almost impossible to determine what is being signed by looking at the XPath expression.

2. An XPath 2.0 filter solves this problem and lets people write regular XPath, but it hasn't gained wide acceptance because it is optional. Also it offers too much unneeded flexibility allowing any number of union, intersect and subtract operations in any order. This flexibility again makes it harder for the verifier.

3. Unlike the ID which can only be once per reference, an XPath transform can be anywhere in the transform chain. For example, a transform chain can have XPath->C14N->XPath. A verifier getting this kind of transform chain would be clueless about the intent of the transform.

3.1.3 Required "declarative selection"

What would be preferable if instead of transforms the signature were more declarative and clearly separated selection from canonicalization. For example it could list out all the URIs, ids, or included XPaths, excluded XPaths of the the elements that are signed. Then it could apply canonicalization. This would make it easier for the verifier to first inspect the signature to determine what is signed and compare against a policy. To give one example, there might be a WS-SecurityPolicy with an expected list of XPaths. Only if this matches, will the verifier do the canonicalization to compute the digests.

3.2.1 Overheads of DOM

DOM parsers have a large overhead. Suppose there is a 1MB XML document. If this loaded into memory as a byte array it remains as a 1MB byte array. But if it is parsed into a DOM it explodes to 5-10x in size. This is because in DOM, each XML node has to become an object. Objects have overheads of memory book keeping, virtual function tables etc. Also each XML node needs parent, next sibling, previous sibling pointers, and it also needs prefix, namespaceURI etc, which could be objects themselves. All these eat up memory and it is a popular misconception that memory is very cheap. Even if this memory were temporary allocation only it would still be expensive - in garbage collected languages allocating and freeing too much of memory triggers then garbage collector too often which drastically slows down the system. Also this 10x DOM explosion can result in physical memory getting exhausted and requiring more pages to be swapped from disk. That is why web services often use streaming XML parsers on the server side. DOM parsers will croak and groan if asked to process multiple large XML documents simultaneously, whereas streaming XML parsers will happily chug along because of their low memory consumption.

3.2.2 One Pass

It is important to distinguish between one-pass and streamability. Streamability means not requiring to have the whole document in a parsed form available for random access, i.e. not requiring a DOM. While one pass is desirable, two pass doesn't take away all the merits of streaming. Suppose the signature value is before the data to be signed. This means that the signature value cannot be updated in the first pass, but only in the second pass - this is not really bad from the performance point of view. Let us the say the document is being streamed out into 1MB byte array, then in the first pass write some dummy bytes for this signature value and remember the location, and in the 2nd pass just update this location with the actual signature bytes, so the 2nd pass is very quick.

Also streamability does not require the ordering between the subelements of signature element. It can be assumed that the entire Signature element (assuming it is detached or enveloped signature) will be loaded up into a java/c++ object, so the order of the elements inside the Signature element does not affect streamability.

Verification in particular cannot be 1 pass - let us say you have a signed 1GB incoming message, which you need to verify first and then upload to a database. So you have to make two passes on this data - a first pass to verify and second pass to upload to the database. One cannot combine these two into 1 pass because verification result is determined only after reading the last byte.

3.2.3 Nodeset

The main impediment to streamability is the transform chain, because many of the transforms are defined on nodesets and nodeset requires a DOM. An XPath transform is the biggest culprit as there are many XPath expressions which cannot be streamed. It is necessary to define a streamable subset of XPath.

Nodesets have another big problem. This nodeset concept was borrowed from XPath 1.0, and an XPath nodeset introduces a new kind of XML node - the namespace node. Namespace nodes are different from namespace declarations in an important way - they are not inherited. This means they need to be repeated for every node for which they are applicable. To give an example, if there is a document with 100 namespace declarations at the top element and with 99 child elements of the top element, a regular DOM will only have 200 (1 top element node + 99 child element nodes + 100 attribute nodes), whereas a nodeset will have 10,100 nodes (1 top element + 99 child element + 100*100 namespace nodes).

A naive implementation which uses the nodeset as defined will therefore be very slow, and be also be subject to various denial of service attacks. A smart implementation can try to not expand the nodeset fully and use inheritance, but they it won't be fully compliant with the XML Signature spec. This is because an XPAth filter can address each of namespace nodes individually and filter them out, even though it is meaningless in XML. The Y4 test vector in the first interop has example of this. Because of these performance problems some implementations do not support this Y4 test vector or support it conditionally.

3.4.1 Historical requirements

The basic idea of a canonical XML is to have a representation of an XML document (the output being a concrete string of bytes) that captures some kind of "essence" of the document, while disregarding certain properties that are considered artifacts of the input document (thought of, again, as an octet stream), and deemed to be safely ignorable.

The historic Canonical XML Requirements [C14N-REQS] include:

• The specification for Canonical XML shall describe how to derive the canonical form of any XML document. Every XML document shall have a unique canonical form.

• The canonical form of an XML document shall be a well formed XML document with the following invariant property:

  • Any XML document, say X, processed by a canonicalizer, will produce an XML Document X'.

  • X' passed through the same canonicalizer must produce X'.

  • X' passed through any other conforming canonicalizer should produce X', or else one of them in not conformant.

In other words, Canonicalization is historically thought of as a well-defined, idempotent mapping from the set of XML documents into itself.

In its main use case, XML Signature, Canonical XML [C14N] (and its cousin, Exclusive Canonicalization) is actually used to fulfill a number of distinct functions:

• Canonical XML is used as the canonical mapping from a node-set to an octet stream whenever such a mapping is required to connect distinct transforms to each other.

• Canonical XML is used to serialize the ds:SignedInfo element before it is hashed as part of the signing process; note that this element does not necessarily exist as a serialization.

• Canonical XML is used to discard artifacts of a specific representation before that representation is hashed in the course of either signature generation or validation.

3.4.2 Modified Requirements

This section summarizes a number of design options that arise when some of the requirements listed above are relaxed.

3.5.1 Binary Portions Use Case

A digital image file contains the raw image data and optional metadata. This metadata contains information like the date the photo was taken, exposure information, search info, general description, etc. Now a photographer wants to use an XML signature to digital sign their photo to ensure it isn't modified by someone, but still wants allows other users to add new meta-data to their photo. This can only be done if the photographer only signs the raw image data and excludes the metadata.

3.5.2 Binary Portions Requirements

The XML Signature 1.0 specification allows authors of XML signatures to sign a subset of an XML document, but doesn't define any grammar that allows a subset of a non XML resource to be signed. The requirement for the next version of the XML signature specification is to define some grammar that allows a subset of a non XML resource to be signed.

3.5.3 Binary Portions Proposal

Add a new ByteRange transform that produces as output, a subset of the input octet stream. Note that byte ranges are used instead of bit ranges because the XML Signature specification defines transforms for octet streams and not bit streams. The ByteRange transform contains a collection of byte ranges defined by a starting byte offset and an optional length value. When the ranges are concatenated together it describe the exact set of bytes from the input octet stream to be used in the digest calculation of the signatures.

<Signature xmlns="http://undefined.namespace">
   <SignedInfo>
      ...
      <Reference URI="./image.jpeg">
         <Transforms>
           <Transform Algorithm="undefined.namespace#ByteRange">
             <ByteRange>
               <Range offset="0" length="20"/> <!-- first 20 bytes of the image -->
               <!-- bytes 21 to 219 are excluded -->
               <Range offset="220" length="50"/>  <!-- bytes 220 to 270 -->
               <!-- bytes 271 to 319 are excluded -->
               <Range offset="320" />  <!-- bytes 320 to end of file -->
             </ByteRange>
           </Transform>
         </Transforms>
         <DigestMethod Algorithm="http://www.w3.org/2000/09/xmldsig#sha1"/>
         <DigestValue>...</DigestValue>
      </Reference>
  </SignedInfo>
  <SignatureValue>...</SignatureValue>
</Signature>

4.2.1 The XPath attributes

In the current transform model, there are three ways of specifying XPath - 1) in XPath Filter which uses an "inside-out" XPath, 2) in XPath Filter 2 which uses regular XPath, 3) as XPointer URIs.

The new syntax settles on one model, a subset of the XPath Filter 2 transform. The reason for this choice is that the alternatives are problematical. XPath Filter 1 uses very complex and unreadable XPaths. XPointer cannot do exclusions. XPath Filter 2 allows any number of Intersect, Subtract, Union filters in any order, but we restrict it down to just one of each in that order.(Refer email chain with John Boyer).

1. First evaluate the URI to get a subtree (or entire document if URI is not present).

2. Then evaluate the includedXPath and take the intersection of the previous subtree and the subtrees identified by this XPath.

3. Then evaluate the excludedXPath and subtract away these subtrees from the previous result.

4. Finally evaluate the reincludedXPath and do a union of these subtrees with the precious result.

4.2.2 Subset of XPath for performance

Only a subset of XPath expressions are allowed. This is a subset that can be easily evaluated by a streaming XPath implementation. Here are the restrictions:

• The XPath expression can only select elements. It cannot select namespace nodes as they are extremely detrimental for performance. Text nodes are also disallowed because text nodes can be very long, and so expressions using text nodes values can be very slow. Attributes are disallowed because they can result in attributes without their parent element, which cannot be represented in a streaming parser like StAX. However we can choose to allow attributes in the excludedXPath expression, but not namespace attributes and not xml: attributes, as excluding these really complicates canonicalization.

• The XPath expression can only use self, child, descendant and attribute axis. That is because a streaming parser only knows the current node, its attributes and ancestors.

• The XPath expression can have a predicate only at the last step. There are many restrictions on this predicate - it can only have an expression using the element name or attribute values, it cannot use any functions, especially the pos function. Simple expressions are allowed, however.

Here is an algorithm for Streaming XPath. For simplicity this algorithm assumes that excludedXPath and reincludedXPath are not present:

For parsing:

1. Split up the union expression by "|". i.e. break up the locationPath | locationPath | .. into individual location paths.

2. Split up each location paths to get individual steps and the final predicate. i.e. break up the / step / step / step .. / step [ predicate ] to get the steps and optional predicate. Two slashes together indicates descendant axis.

3. The predicate will have an expression involving attribute names e.g. @a = "foo" and @b > "bar" You need to have an expression parsing and evaluating engine to do this.

For executing:

1. A streaming XML Parser (e.g. StAX), reads an XML document and produces "events" like StartElement, EndElement, TextNode etc. At any point this parser only remembers the current node. If the current node is an start element, then it also reads all the attributes for that element. To execute a streaming XPath you maintain a stack of ancestor element names, i.e whenever you get a StartElement tag, you need to push the element QName onto this stack, and when you get an EndElement tag you need to pop it off.

2. As you stream through the nodes, you need to execute this XPath expression for every node. I.e. utilize the current element, the current element's attributes and the stack of ancestors to evaluate the XPath expression.

   For each locationPath, match up the steps to the ancestor stack, If they match, evaluate the predicate with the current element's expression. If that passes too, this element and all its descendants are included.

4.3.1 Sign what is seen

While Web services do not have the requirement to sign what is seen, document signing often has this requirement. Suppose the document is derived from data residing in a database, instead of signing the raw data, the data is transformed to HTML using an XSLT and resulting HTML is signed. This is because the raw data is not something that the user sees, but the HTML and associated stylesheets.

The decrypt transform is kind of a similar, instead of signing the encrypted data, it is decrypted and the resulting plaintext data is signed.

From the security point of view, signing the raw data is probably as secure as signing the transformed data. Also doing these transforms is expensive - decryption and XSLT are expensive operations, and result is thrown after digest computation. So the document needs to be transformed again to be displayed to the user - (intermediate results from a transform chain are not available).

Apart from being expensive XSLT can also be very insecure. XSLT is a complete programming language and it can have infinite loops leading to denial of service attacks. It can also have use extension mechanisms to call into other code. However XSLT can be safely used in certain scenarios - it could be a well known XSLT, or maybe the signer and verifier are the same entity, so implicitly trust the XSLT.

So we propose a modified XSLT transform which only supports well known XSLT.

 <Transforms>
    <Transform Algorithm="...xslt.." xsltName="foo.xsl" />
  </Transforms>

4.5.1 The WS-Security STR-Transform

This STR Transform [WSS_STRTransform] is a way to sign tokens that are not part of the message. Suppose a signature is signed with a X509 certificate, and the KeyInfo contains only the IssuerSerial of the certificate. If the signature includes a Reference to the KeyInfo, it is only signing the IssueSerial of the certificate, not the actual certificate. This is where an STR-Transform comes in - it is a transform that "resolves" token references and replaces them with actual tokens, i.e. it will replace the IssuerSerial with the actual certificate. So if this signature contains an STR-Transform, it will sign the actual certificate even though the actual certificate is not in the message.

STR-Transform can be viewed as a combination of two transforms, because it

1. at first replaces token references by actual tokens in the nodeset

2. then canonicalizes this nodeset with the replaced references

Splitting up the STR-Transform gives a big benefit. One of the goals of the new transform model is to accurately determine what is signed, and the current STR-Transform does not let one do that easily because it combines and replacement and canonicalization into one step, so it is very hard for an application to stop the STR-Transform in the middle and get the value of the replaced tokens. But with the new model, an application can just execute the Selection step and get the value of the replaced tokens, and check the policy to determine if the tokens that were supposed to be signed, and really signed.

Note the new model is declarative - this means that the signature syntax itself doesn't say the exact steps to be followed. e.g if the signature has a envelopedSignature="true" attribute, and a wsse:replaceSTRWithST="true", the engine has to know which one to do first - removing the signature or STR replacement. Actually in this particular case the results are the same, whichever way one does it, but the point is that engine has to know all possible combinations that can be thrown at it, and be able to process them correctly, and disallow meaningless combinations.

So in the new model, the implementation pluggability will have to be very different. The current model is based on a "transform engine", anybody can plugin a tranform, and the engine just loops over whatever transforms are defined. The problem with this is that the engine does not understand what it is doing, it just does it. A transform is just a piece of code that it executes.

But in the new model all possible combinations of existing and new attributes need to be precisely defined. From the implementation point of view, this new model is not based on a plugging in a transform, rather each specification that adds a transform, has to build its own engine (which could share code from the base engine, by utility functions or class derivation). i.e.a WS-Security implementation would be required to implement a new transform engine, but for that is can use the help of an underlying XML Security transform engine.

4.5.2 The WS-Security SWA Attachment transforms

The WS-Security SWA profile [WSS_SWA] defines new transforms for signing SOAP attachments. These are referenced using "cid:..." URIs. Normally the input to a transform is an "octet stream" or a "nodeset". But a SOAP attachment is neither, because it has a two parts - mime headers and body. Of the attachment transforms, the "Attachment content" transform is simpler because it only signs the body, and body can be represeted as an octet stream, with just one additional bit of information - the Content-Type mime header , which is used to determine the type of attachment: xml, text or binary. Xml attachments are canonicalized using exclusive canonicalization, text attachments using special line ending normalization, other attachments are considered binary not canonicalized.

The "Attachment Complete transform" is more complex, because it signs both the mime headers and body. To canonicalize the body it follows a nineteen step process (See Section 5.4.1 of that spec). Then it canoncalizes the body depending on the Content-type, and finally appends the canonicalized body and headers into one octet stream.

These transforms assume that they are the first transform in the transform chain, because they need to interact with the URI resolving process so that they can get both the mime headers and body.

To map these transforms to the new model, again we split up the transform into a Selection and Canonicalization step. Recall the canonicalization of the body is different depending on that Content-Type, this can be cleanly represented using the type/subtype attributes. type should be "...xml", "...binary" or "...text" to indicate xml, binary or text attachments. Subtype should be "...soapAttachment" to indicate the special URI resolving that needs to be done for soap attachments. So an "Attachment content tranform" can be represented by <Selection URI="cid:..." type="...xml" subtype="...soapAttachment> Then use the regular Canonicalization section to canonicalize xml data. There also need to be a variant of Canonicalization for canonicalizing text data.

"Attachment Complete Transform" is more complex. This is really signing two separate pieces of data - so maybe it should be represented as two separate references - the first reference will select the mime headers, and the second reference will select the body. And we would also need to define a Canonicalization variant for signing mime headers.

4.5.3 Extension points in new model

Summarizing, in the old syntax the extension points were two - defining new URI schemes and defining new Transforms.

But in the new proposed syntax, there are more possibilities. First thing is type/subtype - if a different type of data is being signed, then new type/subtypes should be defined. Whereas if it is a modification to selection process or the canonicalization process, then the new attributes/subelements should be defined under Selection or Canonicalization. Note - the above examples use attribute extensibility because it is simpler. However attribute extensibility but more limiting, because attributes are simple scalar types - for complex extensions subelements are better.