W3C

Canonical XML Version 2.0

W3C Working Draft 21 April 2011

This version:
http://www.w3.org/TR/2011/WD-xml-c14n2-20110421/
Latest published version:
http://www.w3.org/TR/xml-c14n2/
Latest editor's draft:
http://www.w3.org/2008/xmlsec/Drafts/c14n-20/
Previous version:
http://www.w3.org/TR/2010/WD-xml-c14n2-20100831/
Latest recommendation:
http://www.w3.org/TR/xml-c14n2/
Editors:
John Boyer, IBM (formerly PureEdge Solutions Inc.) ( Version 1.0 )
Glenn Marcy, IBM ( Version 1.1 )
Pratik Datta, Oracle
Frederick Hirsch, Nokia

Abstract

Canonical XML Version 2.0 is canonicalization algorithm for XML Signature 2.0. It addresses issues around performance, streaming, hardware implementation, robustness, minimizing attack surface, determining what is signed and more.

Any XML document is part of a set of XML documents that are logically equivalent within an application context, but which vary in physical representation based on syntactic changes permitted by XML 1.0 [XML10] and Namespaces in XML 1.0 [XML-NAMES]. This specification describes a method for generating a physical representation, the canonical form, of an XML document that accounts for the permissible changes. Except for limitations regarding a few unusual cases, if two documents have the same canonical form, then the two documents are logically equivalent within the given application context. Note that two documents may have differing canonical forms yet still be equivalent in a given context based on application-specific equivalence rules for which no generalized XML specification could account.

Canonical XML Version 2.0 is applicable to XML 1.0. It is not defined for XML 1.1.

Status of This Document

This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications and the latest revision of this technical report can be found in the W3C technical reports index at http://www.w3.org/TR/.

This is a W3C Last Call Working Draft of "Canonical XML Version 2.0".

A diff-marked version of this specification that highlights changes against the previous version is available. Major changes in this version:

This document was published by the XML Security Working Group as a Last Call Working Draft. This document is intended to become a W3C Recommendation. If you wish to make comments regarding this document, please send them to public-xmlsec@w3.org (subscribe, archives). The Last Call period ends 31 May 2011. All feedback is welcome.

Publication as a Working Draft does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.

This is a Last Call Working Draft and thus the Working Group has determined that this document has satisfied the relevant technical requirements and is sufficiently stable to advance through the Technical Recommendation process.

This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.

Table of Contents

1. Introduction

1.1 Terminology

The key words "must", "must not", "required", "shall", "shall not", "should", "should not", "recommended", "may", and "optional" in this document are to be interpreted as described in RFC 2119 [RFC2119].

See [XML-NAMES] for the definition of QName.

document subset
A document subset is a portion of an XML document that may not include all of the nodes in the document.
canonical form
The canonical form of an XML document is physical representation of the document produced by the method described in this specification
canonical XML
The term canonical XML refers to XML that is in canonical form. The XML canonicalization method is the algorithm defined by this specification that generates the canonical form of a given XML document or document subset. The term XML canonicalization refers to the process of applying the XML canonicalization method to an XML document or document subset.
subtree
Subtree refers to one XML element node, and all that it contains. In XPath terminology it is an element node and all its descendant nodes.
DOM
DOM or Document Object Model is a model of representing an XML document in tree structure. The W3C DOM standard [DOM-LEVEL-2-CORE] is one such DOM, but this specification does not require this particular set of DOM APIs; any similar model can be used as long as it has a tree representation of the XML document, whose root is a document node, and the document node's descendants are element nodes, attribute nodes, text nodes etc.
DOM parser
An software module that reads an XML document and constructs a DOM tree.
Stream parser
A software module that reads an XML document and constructs a stream of XML events like "beginElement", "text", "endElement". StAX [XML-PARSER-STAX] is an example of a stream parser.

1.2 Applications

Since the XML 1.0 Recommendation [XML10] and the Namespaces in XML 1.0 Recommendation [XML-NAMES] define multiple syntactic methods for expressing the same information, XML applications tend to take liberties with changes that have no impact on the information content of the document. XML canonicalization is designed to be useful to applications that require the ability to test whether the information content of a document or document subset has been changed. This is done by comparing the canonical form of the original document before application processing with the canonical form of the document result of the application processing.

For example, a digital signature over the canonical form of an XML document or document subset would allow the signature digest calculations to be oblivious to changes in the original document's physical representation, provided that the changes are defined to be logically equivalent by the XML 1.0 or Namespaces in XML 1.0. During signature generation, the digest is computed over the canonical form of the document. The document is then transferred to the relying party, which validates the signature by reading the document and computing a digest of the canonical form of the received document. The equivalence of the digests computed by the signing and relying parties (and hence the equivalence of the canonical forms over which they were computed) ensures that the information content of the document has not been altered since it was signed.

Note: Although not stated as a requirement on implementations, nor formally proved to be the case, it is the intent of this specification that if the text generated by canonicalizing a document according to this specification is itself parsed and canonicalized according to this specification, the text generated by the second canonicalization will be the same as that generated by the first canonicalization.

1.3 Limitations

Two XML documents may have differing information content that is nonetheless logically equivalent within a given application context. Although two XML documents are equivalent (aside from limitations given in this section) if their canonical forms are identical, it is not a goal of this work to establish a method such that two XML documents are equivalent if and only if their canonical forms are identical. Such a method is unachievable, in part due to application-specific rules such as those governing unimportant whitespace and equivalent data (e.g. <color>black</color> versus <color>rgb(0,0,0)</color>). There are also equivalencies established by other W3C Recommendations and Working Drafts. Accounting for these additional equivalence rules is beyond the scope of this work. They can be applied by the application or become the subject of future specifications.

The canonical form of an XML document may not be completely operational within the application context, though the circumstances under which this occurs are unusual. This problem may be of concern in certain applications since the canonical form of a document and the canonical form of the canonical form of the document are equivalent. For example, in a digital signature application, it cannot be established whether the operational original document or the non-operational canonical form was signed because the canonical form can be substituted for the original document without changing the digest calculation. However, the security risk only occurs in the unusual circumstances described below, which can all be resolved or at least detected prior to digital signature generation.

The difficulties arise due to the loss of the following information not available in the data model:

  1. base URI, especially in content derived from the replacement text of external general parsed entity references
  2. notations and external unparsed entity references
  3. attribute types in the document type declaration

In the first case, note that a document containing a relative URI [URI] is only operational when accessed from a specific URI that provides the proper base URI. In addition, if the document contains external general parsed entity references to content containing relative URIs, then the relative URIs will not be operational in the canonical form, which replaces the entity reference with internal content (thereby implicitly changing the default base URI of that content). Both of these problems can typically be solved by adding support for the xml:base attribute [XMLBASE] to the application, then adding appropriate xml:base attributes to document element and all top-level elements in external entities. In addition, applications often have an opportunity to resolve relative URIs prior to the need for a canonical form. For example, in a digital signature application, a document is often retrieved and processed prior to signature generation. The processing should create a new document in which relative URIs have been converted to absolute URIs, thereby mitigating any security risk for the new document.

In the second case, the loss of external unparsed entity references and the notations that bind them to applications means that canonical forms cannot properly distinguish among XML documents that incorporate unparsed data via this mechanism. This is an unusual case precisely because most XML processors currently discard the document type declaration, which discards the notation, the entity's binding to a URI, and the attribute type that binds the attribute value to an entity name. For documents that must be subjected to more than one XML processor, the XML design typically indicates a reference to unparsed data using a URI in the attribute value.

In the third case, the loss of attribute types can affect the canonical form in different ways depending on the type. Attributes of type ID cease to be ID attributes. Hence, any XPath expressions that refer to the canonical form using the id() function cease to operate. The attribute types ENTITY and ENTITIES are not part of this case; they are covered in the second case above. Attributes of enumerated type and of type ID, IDREF, IDREFS, NMTOKEN, NMTOKENS, and NOTATION fail to be appropriately constrained during future attempts to change the attribute value if the canonical form replaces the original document during application processing. Applications can avoid the difficulties of this case by ensuring that an appropriate document type declaration is prepended prior to using the canonical form in further XML processing. This is likely to be an easy task since attribute lists are usually acquired from a standard external DTD subset, and any entity and notation declarations not also in the external DTD subset are typically constructed from application configuration information and added to the internal DTD subset.

1.4 Requirements for 2.0

Canonical XML 2.0 solves many of the major issues that have been identified by implementers with Canonical XML 1.0 [XML-C14N] and 1.1 [XML-C14N11].

1.4.1 Performance

A major factor in performance issues noted in XML Signature is often Canonical XML 1.1 processing. Canonicalization will be slow if the implementation uses the Canonical XML 1.1 specification as a formula without any attempt at optimization. This specification rectifies this problem by incorporating lessons learned from implementation into the specification. Most mature canonicalization implementations solve the performance problem by inspecting the signature first, to see if it can be canonicalized using a simple tree walk algorithm whose performance is similar to regular XML serialization. If not they fall back to the expensive nodeset-based algorithm.

The use cases that cannot be addressed by the simple tree walk algorithm are mostly edge cases. This specification restricts the input to the canonicalization algorithm so that implementations can always use the simple tree walk algorithm.

C14N 1.x uses an "XPath 1.0 Nodeset" to describe a document subset. This is the root cause of the performance problem and can be solved by not using a nodeset. This version of the specification does not use a nodeset, visits each node exactly once, and only visits the nodes that are being canonicalized.

1.4.2 Streaming

A streaming implementation is required to be able to process very large documents without holding them all in memory; it should be able to process documents one chunk at a time.

1.4.3 Robustness

Whitespace handling was a common cause of signature breakage. XML libraries allow one to "pretty print" an XML document, and most people wrongly assume that the white space introduced by pretty printing will be removed by canonicalization but that is not the case. This specification adds three techniques to improve robustness:

  1. Optionally remove leading and trailing whitespace from text nodes,
  2. Allow for QNames in content, particularly in the xsi:type attribute,
  3. Optionally rewrite prefixes

1.4.4 Portability

It should be possible to canonicalize a subdocument in such a way, that the signature doesn't break when the subdocument moved into a completely different XML document. This is the goal of Exclusive canonicalization [XML-EXC-C14N] that mostly satisfies this requirement except for the case of namespace prefixes embedded in content. This specification builds on exclusive canonicalization and solves the problem of namespaces in content.

1.4.5 Simplicity

C14N 1.x algorithms are complex and depend on a full XPath library. This increases the work required for scripting languages to use XML Signatures. This specification addresses this issue by not using the complex nodeset model, and therefore not relying completely on XPath.

2. Canonical XML 2.0

2.1 Data Model

The input to the canonicalization algorithm consists of an XML document subset, and set of options. The XML document subset can be expressed in two ways, with a DOM model or a Stream model.

In the DOM model the XML subset is expressed as:

The XML subset consists of all the nodes in the Inclusion list and their descendant, minus all the nodes that are in the Exclusion list and their descendants.

The element nodes in the Inclusion list are also referred as apex nodes.

Note: This input model is a very limited form of the generic XPath Nodeset that was the input model for Canonical XML 1.x. It is designed to be simple and allow for a high performance algorithm, while still supporting the most essential use cases. Specifically:

Note: Canonical XML 2.0, unlike earlier versions, does not support direct input of an octet stream. The transformation of such a stream into the input model required by this specification is application-specific and should be defined in specifications that reference or make use of this one.

2.2 Parameters

Instead of separate algorithms for each variant of canonicalization, this specification takes the approach of a single algorithm subject to a variety of parameters that change its behavior to address specific use cases.

The following is a list of the logical parameters supported by this algorithm. The actual serialization that expresses the parameters in use may be defined as appropriate to specific applications of this specification (e.g., the <ds:CanonicalizationMethod> element in [XMLDSIG-CORE2]).

NameValuesDescriptionDefault
IgnoreCommentstrue or false whether to ignore comments during canonicalization true
TrimTextNodestrue or false whether to trim (i.e. remove leading and trailing whitespaces) all text nodes when canonicalizing. Adjacent text nodes must be coalesced prior to trimming. If an element has an xml:space="preserve" attribute, then text node descendants of that element are not trimmed regardless of the value of this parameter. true
PrefixRewritenone, sequential with none, prefixes are left unchanged, with sequential, prefixes are changed to "n0", "n1", "n2" ... except the special prefixes "xml" and "xmlns" which are left unchanged. none
QNameAwarean enumeration of qualified element names, element names that contain XPath 1.0 expressions, qualified attribute names, and unqualified attribute names (identified by name, and parent qualified name) set of nodes whose entire content must be processed as QName-valued for the purposes of canonicalization, including prefix rewriting and recognition of prefix "visible utilization" empty set

All of these parameters must be implemented.

Note: Before Canonical XML 2.0, there were two separate canonicalization algorithms - Inclusive Canonicalization [XML-C14N11] and Exclusive Canonicalization [XML-EXC-C14N]. The major differences between these two algorithms is the treatment of namespace declarations and inherited attributes in xml: namespace. Earlier draft versions of Canonical XML 2.0 had combined Inclusive and Exclusive into a single algorithm, with parameters to control how namespaces and inherited xml: attributes were treated. Effectively one could set these parameters to make Canonical XML 2.0 emulate either C14n 1.0 or C14N 1.1 or Exc C14n 1.0. But in the current version of Canonical XML 2.0, Inclusive canonicalization has been removed completely.

Exclusive canonicalization has been far more popular than inclusive, because of its "portability" property. I.e. if a subdocument is signed with exclusive canonicalization, and then this subdocument is moved off to a different XML context, the signature on that subdocument still remains valid. Inclusive canonicalization doesn't have this portability property, however inclusive canonicalization has an advantage over exclusive canonicalization 1.0, when it comes to qnames in content. Exclusive canonicalization 1.0 only emits namespaces declarations that it considers are visibly utilized, so if there is qname embedded in text node or an attribute node, it doesn't recognize it. For example in this attribute xsi:type="xsd:string", the "xsd" prefix is embedded in the content, and so Exclusive canonicalization 1.0 will not consider the "xsd" prefix to be visibly utilized and hence not emit the xsd namespace declaration. Not emitting the declaration, makes it susceptible to certain wrapping attacks. Exclusive canonicalization 1.0 offers the "InclusiveNamespace" mechanism to deal with these kinds of prefixes. Any prefixes mentioned in this list will be treated inclusively, i.e. their namespace declarations will be emitted even if they are not used.

Canonical XML 2.0 overcomes the shortcomings of Exclusive Canonicalization 1.0, with the QNameAware parameter. This parameter can be used to list element or attribute nodes that are expected to have qnames. Canonical XML 2.0 will scan for prefixes in these elements and attributes and consider them to be visibly utilized too. With the introduction of this parameter, there is really no need for Inclusive canonicalization any more, so it has been completely removed from Canonical XML 2.0.

Note: The algorithm for prefix scanning doesn't cover all kinds of prefix embedding. For example if a text node's value is a space separate list of qnames, this algorithm will not detect the prefixes of these qnames. It will only detect two kinds of embedding, a) when the entire text node or attribute is a qname, and b) when a text node is an XPath expression containing prefixes.

Inclusive canonicalization also preserves the values xml: attributes in context. I.e. it looks at the ancestors of the subdocument to be signed, and collects the value of any inheritable xml attributes, specifically xml:lang, xml:space and xml:base, from these ancestor elements and emits them at the root of the subdocument. Exclusive canonicalization does not do this as it this violates the portability requirement. Likewise, Canonical XML 2.0 ignores these attributes as well.

2.3 Processing Model

The basic canonicalization process consists of traversing the tree and outputting octets for each node.

Input: The XML subset consisting of an Inclusion list and an Exclusion list.

Processing

During traversal of each subtree, generate the canonicalized text depending on the node type as follows:

Note although some XML models such as DOM don't distinguish namespace declarations from attributes, Canonicalization needs to treat them separately. In this document, attribute nodes that are actually namespace declarations are referred as "namespace nodes", other attributes are called "attribute nodes".

2.4 The Need for Exclusive XML Canonicalization

In some cases, particularly for signed XML in protocol applications, there is a need to canonicalize a subdocument in such a way that it is substantially independent of its XML context. This is because, in protocol applications, it is common to envelope XML in various layers of message or transport elements, to strip off such enveloping, and to construct new protocol messages, parts of which were extracted from different messages previously received. If the pieces of XML in question are signed, they need to be canonicalized in a way such that these operations do not break the signature but the signature still provides as much security as can be practically obtained.

2.4.1 A Simple Example

As a simple example of the type of problem that changes in XML context can cause for signatures, consider the following document:

<n1:elem1 xmlns:n1="http://b.example">
     content
     </n1:elem1>

this is then enveloped in another document:

<n0:pdu xmlns:n0="http://a.example">
     <n1:elem1 xmlns:n1="http://b.example">
     content
     </n1:elem1>
     </n0:pdu>

The first document above is in canonical form. But assume that document is enveloped as in the second case. The subdocument with elem1 as its apex node can be extracted from this second case with an XPath expression such as:

/descendant::n1:elem1

The result of performing inclusive canonicalization to the resulting xml subset is the following (except for line wrapping to fit this document):

<n1:elem1 xmlns:n0="http://a.example"
     xmlns:n1="http://b.example">
     content
     </n1:elem1>

Note that the n0 namespace has been included by inclusive canonicalization because it includes namespace context. This change would break a signature over elem1 based on the first version.

2.4.2 General Problems with re-Enveloping

As a more complete example of the changes in canonical form that can occur when the enveloping context of a document subset is changed, consider the following document:

<n0:local xmlns:n0="foo:bar" xmlns:n3="ftp://example.org">
     <n1:elem2 xmlns:n1="http://example.net">
     <n3:stuff xmlns:n3="ftp://example.org"/>
     </n1:elem2>
     </n0:local>

And the following which has been produced by changing the enveloping of elem2:

<n2:pdu xmlns:n1="http://example.com" xmlns:n2="http://foo.example">
     <n1:elem2 xmlns:n1="http://example.net">
     <n3:stuff xmlns:n3="ftp://example.org"/>
     </n1:elem2>
     </n2:pdu>

Assume an xml subset produced from each case by applying the following XPath expression:

/descendant::n1:elem2

Applying inclusive canonicalization to the xml subset produced from the first document yields the following serialization:

<n1:elem2 xmlns:n0="foo:bar" xmlns:n3="ftp://example.org" 
xmlns:n1="http://example.net">
<n3:stuff></n3:stuff>
        </n1:elem2>

However, although elem2 is represented by the same octet sequence in both pieces of external XML above, the Canonical XML version of elem2 from the second case would be as follows:

<n1:elem2 xmlns:n1="http://example.net" xmlns:n2="http://foo.example">
<n3:stuff xmlns:n3="ftp://example.org"></n3:stuff>
        </n1:elem2>

Note that the change in context has resulted in lots of changes in the subdocument as serialized by the inclusive canonicalization. In the first example, n0 had been included from the context and the presence of an identical n3 namespace declaration in the context had elevated that declaration to the apex of the canonicalized form. In the second example, n0 has gone away but n2 has appeared, n3 is no longer elevated. But not all context changes have effect. In the second example, the presence of the n1 prefix namespace declaration have no effect because of existing declarations at the elem2 node.

On the other hand, using Exclusive canonicalization the physical form of elem2 as extracted by the XPath expression above is as follows:

<n1:elem2 xmlns:n1="http://example.net">
     <n3:stuff xmlns:n3="ftp://example.org"></n3:stuff>
     </n1:elem2>

in both cases.

2.5 Namespace Processing

As part of the canonicalization process, while traversing the subtree, use the following algorithm to look at all the namespace declarations in an element, and decide which ones to output.

2.5.1 Namespace concepts

The following concepts are used in Namespace processing:

Explicit and Implicit namespace declarations

In DOM, there is no special node for namespace declarations, they are just present as regular attribute nodes. An "explicit" namespace declaration is an attribute node whose prefix is "xmlns" and whose localName is the prefix being declared.

DOM also allows declaring a namespace "implicitly", i.e. if a new DOM element or attribute is constructed using the createElementNS and createAttributeNS methods, then DOM adds a namespace declaration automatically when serializing the document.

Special namespaces
The "xml" and "xmlns" prefixes are reserved and have special behavior. See [XML-NAMES].
Apex nodes
An apex node is an element node in a document subset having no element node ancestor in the document subset.
Default namespace
The default namespace is declared by xmlns="...". To make the algorithm simpler this will be treated as a namespace declaration whose prefix value is "" i.e. an empty string.
Visibility utilized
This concept is required for exclusive canonicalization. An element E in the document subset visibly utilizes a namespace declaration, i.e. a namespace prefix P and bound value V, if any of the following conditions are true:
  • The element E itself has a qualified name that uses the prefix P. (Note if an element does not have a prefix, that means it visibly utilizes the default namespace.)
  • OR The element E is among those enumerated for the QNameAware parameter, and the QName value of the element uses the prefix P (or, lacking a prefix, it visibly utilizes the default namespace)
  • OR The element E is among those enumerated for the QNameAware parameter, and it listed as an XPathElement. This value of the element is to be interpreted as an XPath 1.0 expression and any prefixes used in this XPath expression are considered to be visibility utilized.
  • OR An attribute A of that element has a qualified name that uses the prefix P, and that attribute is not in the exclusion list. (Note: unlike elements, if an attribute doesn't have a prefix, that means it is a locally scoped attribute. It does NOT mean that the attribute visibly utilizes the default namespace.)
  • OR An attribute A of that element is among those enumerated for the QNameAware parameter, and the QName value of the attribute uses the prefix P (or, lacking a prefix, it visibly utilizes the default namespace)

2.5.2 Namespace processing algorithm

Step 1: At first determine the namespaces to be output for an element E.

  1. Find a list of namespace declarations that are in scope for this element E by looking at both implicit and explicit namespace declarations in this element and its ancestors. Include the default namespace declaration if present.
  2. If in this list, any of the namespace declaration has already been output during the canonicalization of one of the element E's ancestors, say Ej, and has not been redeclared since then to a different value, i.e not been redeclared by an element between Ej and E, then remove it from this list.
  3. If this list contains the definition of the xml prefix, remove it.
    Note: Canonical XML 2.0 never emits the declaration for the xml or xmlns prefixes. As mentioned in [XML-NAMES] a valid XML document should never have the declaration for xmlns, so Canonical XML 2.0 should never encounter this declaration. Also a valid XML document can optionally declare the xml prefix , but if present it must be bound to http://www.w3.org/XML/1998/namespace. Canonical XML 2.0 should ignore this declatation.
  4. Return the list of namespace declarations left on the list.

Step 2: For each of the prefixes check for visible utilization as follows

  1. If E itself has a qualified name that uses the prefix P, then P is visibly utilized. Note if E does not have a prefix, that means it visibly utilizes the default namespace.
  2. If an attribute A of that element E has a qualified name that uses the prefix P, and that attribute is not in the exclusion list. Note: unlike elements, if an attribute doesn't have a prefix, that means it is a locally scoped attribute. It does NOT mean that the attribute visibly utilizes the default namespace.
  3. If there is a QNameAware parameter, check whether the E or its attributes is enumerated in it as follows:
    • If there is an Element subchild, whose Name and NS attributes match E's localname and namespace respectively, then E is expected to have a single text node child containing a QName. Extract the prefix from this QName, and consider this prefix as visibly utilized.
    • If there is a QualifiedAttr subchild, whose Name and NS attributes match one of E's qualified attribute's localname and namespace respectively, then that attribute is expected to contain a QName. Extract this prefix from the QName and consider this prefix as visibly utilized.
    • If there is a UnqualifiedAttr subchild, whose Name attribute match one of E's unqualified attribute's name, and its ParentName and ParentNS attributes match E's localname and namespace respectively, then that attribute is expected to contain a QName. Extract this prefix from the QName and consider this prefix as visibly utilized.
    • If there is a XPathElement subchild, whose Name and NS attributes match E's localname and namespace respectively, then E is expected to have a single text node child containing a XPath 1.0 expression. Extract the prefixes from this XPath by using the following algorithm. All of these extracted prefixes should be considered as visibly utilized.
      • Search for single colons : in the XPath expression, but do not consider single colons inside quoted strings. Double colons are used for axes, e.g. in self::node() , "self:" is not a prefix, but an axis name.
      • The prefix will be present just before the single colon. Go backwards from the colon, skip whitespace, and extract the prefix, by collecting charcaters till the first non NCName match. e.g. in /soap : Body, extract the "soap". The NCName production is defined in [XML-NAMES].
      This can be evaluated using perl style regular expressions as follows. Note the regular expressions here are provided as an example only, they are not normative.
      1. First remove all single quoted and double quoted strings from the XPath, because prefixes cannot be present there. i.e. do a substitute of s/"[^"]*"//g and s/'[^']*'//g. Removing the quoted string eliminates false positives in the next step.
      2. In the resultant string search for single colons and get the word just before colon, i.e search for match forn m/([\w-_.]+)?\s*:(?!:)/ Note prefixes follow the NCName production, i.e. consists of alphanumeric or hyphen or underscore or dot, but cannot start with digit, hyphen or dot. . In an NCName, the allowed alphanumeric characters are not just Ascii, but any Unicode alphanumeric characters. However the regular expression provided here is a very simplified form of NCName production.
    • If PrefixRewrite parameter is set to sequential each of the prefixes found in the above steps would need to be replaced by the a new prefix. For efficiency, consider combining this searching for prefixes step with the subsequent replacing prefixes step.
Step 3: If the PrefixRewrite parameter is set to other than "none", then compute new prefixes for all the namespaces declarations in this list, as follows:
  • For PrefixRewrite="sequential" sort this list of namespace declarations by URI. Then assign a new prefix value "nN" to each prefix, incrementing the value of N for every prefix. The counter should be set to 0 in the beginning of the canonicalization (e.g. if the value of this counter was 5 when the traversal reached this element, and this element had 3 prefixes to be output, then use the prefixes "n5", "n6", "n7" and set the counter to 8 after that).
Note: with prefix rewriting the default namespace is also rewritten into a "nN" style prefix.

Note: with exclusive canonicalization namespace declarations and output only when they are utilized, this may lead to one declaration being output multiple times, and it may be rewritten to a different value every time as shown in the example below.

Step 4: Sort this list of namespaces as follows:
In case of PrefixRewrite="none" sort the namespace declaration in lexicographic(ascending) order of prefixes (the default namespace declaration has no prefix, so it is lexicographically least).
In case of PrefixRewrite="sequential" sort them in ascending order of namespace URI.

Step 5: Output each of these namespace nodes, as specified in the Processing model.

2.5.3 Example of exclusive canonicalization with prefix rewriting

This following XML snippet will be used to determine the various options of prefixRewriting.
<wsse:Security  
xmlns:wsse="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd"
xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">
<wsse:UserName wsu:Id="i1">
...
</wsse:UserName>
<wsse:Timestamp wsu:Id="i2">
...
</wsse:Timestamp>
<wsse:Security>
2.5.3.1 With PrefixRewrite="none"
<wsse:Security 
xmlns:wsse="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd">
<wsse:UserName
xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd"
wsu:Id="i1">
...
</wsse:UserName>
<wsse:Timestamp
xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd"
wsu:Id="i2">
...
</wsse:Timestamp>
</wsse:Security>
Note how the "wsu" prefix declaration is present in wsse:Security, but is not utilized. So exclusive canonicalization will "push the declaration down" into <UserName> and <Timestamp> where it is really used, i.e. the wsu declaration will be output twice, once in <UserName> and another in <Timestamp>, as shown above.
2.5.3.2 With PrefixRewrite="sequential"
<n0:Security
xmlns:n0="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd">
<n0:UserName
xmlns:n1="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd"
n1:Id="i1">
...
</n0:UserName>
<n0:Timestamp
xmlns:n2="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd"
n2:Id="i2">
...
</n0:Timestamp>
</n0:Security>
Now observe what happens with sequential prefix rewriting, the wsu namespace is emitted twice, but each time with a different prefix. - "n1" and "n2", as shown above.

2.6 Attribute processing

Note: namespace declarations are not considered as attributes, they are processed separately as namespace nodes.

Processing the attributes of an element E consists of the following steps:

3. Use of Canonical XML 2.0 in XML Security

3.1 Use of Canonical XML 2.0 in XML Signature 2.0

Canonical XML 2.0 may be used as a canonicalization algorithm in XML Digital Signature [XMLDSIG-CORE2], via the <ds:CanonicalizationMethod>.

Identifier:
http://www.w3.org/2010/xml-c14n2

Canonical XML 2.0 supports a set of parameters, as enumerated in Canonicalization Parameters. All parameters are optional and have default values. When used in conjunction with the <ds:CanonicalizationMethod> element, each parameter is expressed with a dedicated child element. They can be present in any order. A schema definition for each parameter follows:

  Schema Definition:
        <schema xmlns:xs="http://www.w3.org/2001/XMLSchema"
        xmlns="http://www.w3.org/2010/xml-c14n2"
        targetNamespace="http://www.w3.org/2010/xml-c14n2"
        version="0.1" elementFormDefault="qualified">

        <xs:element name="IgnoreComments" type="xs:boolean"/>
        
        <xs:element name="TrimTextNodes" type="xs:boolean"/>
        
        <xs:element name="PrefixRewrite">
        <xs:simpleType>
        <xs:restriction base="xs:string">
        <xs:enumeration value="none"/>
        <xs:enumeration value="sequential"/>
        <xs:enumeration value="derived"/>
        </xs:restriction>
        </xs:simpleType>
        </xs:element>
        
        <xs:element name="QNameAware">
        <xs:complexType>
        <xs:choice maxOccurs="unbounded">
        <xs:element ref="Element"/>
        <xs:element ref="XPathElement"/>
        <xs:element ref="QualifiedAttr"/>
        <xs:element ref="UnqualifiedAttr"/>
        <xs:sequence>
        </xs:complexType>
        </xs:element>
        
        <xs:element name="Element">
        <xs:complexType>
        <xs:attribute name="Name" type="xs:NCName" use="required"/>
        <xs:attribute name="NS" type="xs:anyURI"/>
        </xs:complexType>
        </xs:element>
        
        <xs:element name="QualifiedAttr">
        <xs:complexType>
        <xs:attribute name="Name" type="xs:NCName" use="required"/>
        <xs:attribute name="NS" type="xs:anyURI"/>
        </xs:complexType>
        </xs:element>
        
        <xs:element name="UnqualifiedAttr">
        <xs:complexType>
        <xs:attribute name="Name" type="xs:NCName" use="required"/>
        <xs:attribute name="ParentName" type="xs:NCName" use="required"/>
        <xs:attribute name="ParentNS" type="xs:anyURI"/>
        </xs:complexType>
        </xs:element>

        <xs:element name="XPathElement">
        <xs:complexType>
        <xs:attribute name="Name" type="xs:NCName" use="required"/>
        <xs:attribute name="NS" type="xs:anyURI"/>
        </xs:complexType>
        </xs:element>
        

        </schema>

XML Signature 2.0 must implicitly pass in the dsig2:IncludedXPath and dsig2:ExcludedXpath as QNameAware, even if they are not explictly present in the Signature element.

3.2 Use of Canonical XML 2.0 in XML Encryption 1.1

Canonical XML 2.0 may also be used in XML Encryption 1.1, with changes as noted in the non-normative section "Serializing XML" of XML Encryption 1.1 [XMLENC-CORE1].

4. Pseudocode

This section presents the entire canonicalization algorithm in pseudo code. It is not normative.

4.1 canonicalize()

Top level canonicalize function.
          canonicalize(list of subtree, list of exclusion elements and attributes, properties)
          {
          put the exclusion elements and attributes in hash table for easier lookup
          
          sort the multiple subtrees by document order
          
          for each subtree
          canonicalizeSubtree(subtree) 
          }
        

4.2 canonicalizeSubtree()

Canonicalize an individual subtree.

For efficiency the routines below maintain two contexts

          canonicalizeSubtree(node)
          {
          initialize namespaceContext to contain the default prefix, mapped
          to an empty URI, and hasBeenOutput to true 
          
          if (node is the document node or a document root element) 
          {
          // (whole document is being processed, no ancestors to worry about)
          call processNode(node, namespaceContext)
          }
          else
          {
          starting from the element, walk up the tree to collect a list of
          ancestors 
          
          for each of this ancestor elements starting with the document
          root, but not including the element itself 
          addNamespaces(ancestorElem, namespaceContext)

          initialize xmlattribContext to empty

          for each of this ancestor elements starting with the document
          root, and also including the element itself 
          addXMLAttributes(ancestorElem, xmlattribContext)
          
          if there are any attributes in xmlattribContext 
          temporarily add/replace these XML attributes in node
          
          processNode(node, namspaceContext)
          
          restore the original XML attributes
          }   
          }
        

4.3 processNode()

Redirect to appropriate node processing function
          processNode(node, namespaceContext)
          {
          call the appropriate function - processDocument, processElement,
          processTextNode, ... depending on the node type.
          }
        

4.4 processDocument()

Process the Document Node.
          processDocument(document, namespaceContext)
          {
          Loop through all child nodes and call
          processNode(child, namespaceContext)
          }
        

4.5 processElement()

Process an Element Node.
          processElement(element, namespaceContext)
          {
          if this exists in the exclusion hash table
          return
          
          make of copy of xmlattribContext and namespaceContext
          //(by copying, any changes made can be undone when this function returns)
          
          nsToBeOutputList = processNamespaces(element, namespaceContext)
          
          output('<')
          if PrefixRewrite is sequential or digest, temporarily modify the
          QName to have the new prefix value as determined from the namespaceContext
          
          output(element QName)  

          for each of the namespaces in the nsToBeOutputList
          output this namespace declaration 
          
          sort each of the non namespaces attributes by URI first then attribute name.
          output each of these attributes with original QName or a modifiedQName if PrefixRewrite is true
          
          output('>')
          
          Loop through all child nodes and call
          processNode(child, namespaceContext)
          
          output('</')
          output(element QName)
          output('>')
          
          restore xmlattribContext and namespaceContext
          }
        

4.6 processText()

Process an Text Node.
          processText(textNode)
          {
          if this text node is outside document root
          return
          
          in the text replace 
          all ampersands by &, 
          all open angle brackets (<) by &lt;, 
          all closing angle brackets (>) by &gt;, 
          and all  #xD characters by &#xD;.
          
          If TrimTextNodes is true and there is no xml:space="preserve" declaration in scope
          trim leading and trailing space
          
          output(text)
          }                    
        

Note: The DOM parser might have split up a long text node into multiple adjacent text nodes, some of which may be empty. In that case be careful when trimming the leading and trailing space - the net result should be same as if it the adjacent text nodes were concatenated into one

4.7 processPI()

Process an Processing Instruction (PI) Node.
          processPI(piNode)
          {
          if after document node
          output('#xA')
          
          output('<?')
          output(the PI target name of the node)
          output(a leading space)
          output(the PI string value)
          output('?>') 

          if before document node
          output('#xA')
          }                     
        

4.8 processComment()

Process an Comment Node.
          processComment(commentNode)
          {
          if ignoreComments
          return
          
          if after document node
          output('#xA')
          
          output('<!--')
          output(string value of node)
          output('-->')

          if before document node
          output('#xA')
          }
        

4.9 addNamespaces()

Add namespaces from this element to the namespace context. This function is called for every ancestor element, and also at every element of the subtrees (minus the exclusion elements).
          addNamespaces(element, namespaceContext)
          {
          for each the explicit and implicit namespace declarations in the element
          {
          if there is already a declaration for this prefix, and this
          declaration is different from existing declaration 
          overwrite the URI , and set hasBeenOutput to false
          
          if there is no entry for this prefix
          add an entry for this URI, and hasBeenOutout to false
          
          } 
          }
        

4.10 processNamespaces()

Process the list of namespaces for this element.
          processNamespaces(element, namespaceContext)
          {
          addNamespaces(element, namespaceContext)
          
          initialize nsToBeOutputList to empty list
          
          for each prefix in the namespaceContext for which hasBeenOutput is false
          {
          if ExclusiveMode and this prefix is not in the inclusiveNamespacesList
          {
          if the prefix is visibly utilized by this element
          add the prefix to the nsToBeOutputList and set
          hasBeenOutput to true 
          }
          else
          add the prefix to the nsToBeOutputList and set hasBeenOutput to true    
          }
          
          if (PrefixRewrite is none)
          {
          sort the nsToBeOutputList by the prefix
          }
          else if (PrefixRewrite is sequential) 
          {
          sort the nsToBeOutputList by URI
          assign new prefix values "nN" to each prefix in this
          nsToBeOutputList where N represents an incremented counter value ,
          i.e. n0, n1, n2 .. 
          // the counter should be set to 0 in the beginning of the canonicalization
          // note: prefix numbers are assigned in the order that the
          prefixes are present in nsToBeOutputList 
          }
          else if (PrefixRewrite in digest)
          {
          sort the nsToBeOutputList by URI
          assign new prefix values "nD" to each prefix in this nsToBeOutputList where
          D represents the SHA1 digest of the URI represented as a hex string
          }
          
          return nsToBeOutputList    
          }
        

4.11 addXMLAttributes()

Combine/modify the 3 special xml attributes: xml:lang, xml:space and xml:base.
          addXMLAttributes(element, xmlattribContext)
          {
          for each of the xml: attributes of this element
          {

          case xml:lang attribute 
          if XmlAncestors is inherit then store this attribute value, else do nothing

          case xml:space attribute 
          if XmlAncestors is inherit then store this attribute value, else do nothing

          case xml:base attribute 
          if XmlAncestors is inherit, and there is a previous value of xml:base
          then do a "join-URI-References" to combine the new value and the old value 
          else do nothing
          } 
          }
        

5. Output rules

6. Processing model for Streaming XML parsers

Unlike DOM parsers which represent XML document as a tree of nodes, streaming parsers represent an XML document as stream of events like "start-element", "end-element", "text" etc. A document subset can also be represented as a stream of events. This stream of events in exactly in the same order as a tree walk, so the above canonicalization algorithm can be also used to canonicalize an event stream.

A. References

Dated references below are to the latest known or appropriate edition of the referenced work. The referenced works may be subject to revision, and conformant implementations may follow, and are encouraged to investigate the appropriateness of following, some or all more recent editions or replacements of the works cited. It is in each case implementation-defined which editions are supported.

A.1 Normative references

[RFC2119]
S. Bradner. Key words for use in RFCs to Indicate Requirement Levels. March 1997. Internet RFC 2119. URL: http://www.ietf.org/rfc/rfc2119.txt
[XML-NAMES]
Richard Tobin; et al. Namespaces in XML 1.0 (Third Edition). 8 December 2009. W3C Recommendation. URL: http://www.w3.org/TR/2009/REC-xml-names-20091208/
[XML10]
C. M. Sperberg-McQueen; et al. Extensible Markup Language (XML) 1.0 (Fifth Edition). 26 November 2008. W3C Recommendation. URL: http://www.w3.org/TR/2008/REC-xml-20081126/
[XMLDSIG-CORE2]
Mark Bartel; John Boyer; Barb Fox et al. XML Signature Syntax and Processing Version 2.0. 21 April 2011. W3C Last Call Working Draft. URL: http://www.w3.org/TR/2011/WD-xmldsig-core2-20110421/

A.2 Informative references

[DOM-LEVEL-2-CORE]
Arnaud Le Hors; et al. Document Object Model (DOM) Level 2 Core Specification. 13 November 2000. W3C Recommendation. URL: http://www.w3.org/TR/2000/REC-DOM-Level-2-Core-20001113/
[URI]
T. Berners-Lee; R. Fielding; L. Masinter. Uniform Resource Identifiers (URI): generic syntax. January 2005. Internet RFC 3986. URL: http://www.ietf.org/rfc/rfc3986.txt
[XML-C14N]
John Boyer. Canonical XML Version 1.0. 15 March 2001. W3C Recommendation. URL: http://www.w3.org/TR/2001/REC-xml-c14n-20010315
[XML-C14N11]
John Boyer, Glenn Marcy. Canonical XML Version 1.1. 2 May 2008. W3C Recommendation. URL: http://www.w3.org/TR/2008/REC-xml-c14n11-20080502/
[XML-EXC-C14N]
Donald E. Eastlake 3rd; Joseph Reagle; John Boyer. Exclusive XML Canonicalization Version 1.0. 18 July 2002. W3C Recommendation. URL: http://www.w3.org/TR/2002/REC-xml-exc-c14n-20020718/
[XML-PARSER-STAX]
Christopher Fry; JSR 173: Streaming API for XML for Java Specification 8th October 2003. v1.0 URL: http://jcp.org/en/jsr/detail?id=173
[XMLBASE]
Jonathan Marsh, Richard Tobin. XML Base (Second Edition). 28 January 2009. W3C Recommendation. URL: http://www.w3.org/TR/2009/REC-xmlbase-20090128/
[XMLDSIG-XPATH-FILTER2]
Merlin Hughes; John Boyer; Joseph Reagle. XML-Signature XPath Filter 2.0. 8 November 2002. W3C Recommendation. URL: http://www.w3.org/TR/2002/REC-xmldsig-filter2-20021108/
[XMLENC-CORE1]
J. Reagle; D. Eastlake; F. Hirsch; T. Roessler. XML Encryption Syntax and Processing Version 1.1. 3 March 2011. W3C Candidate Recommendation. (Work in progress.) URL: http://www.w3.org/TR/2011/CR-xmlenc-core1-20110303/