Canonical XML Version 2.0

1.4.1 Performance

A major factor in performance issues noted in XML Signature is often C14N11 canonicalization. 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 C14N 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 solved by the simple tree walk algorithm are mostly edge use cases. This specification restricts the input of 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 spec does not use a nodeset, visits each node exactly once, and it 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 it all in memory, i.e. it should be able to process the document one chunk at a time.

1.4.3 Robustness

Whitespace handling was a common cause of signature breakages. 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. Remove leading and trailing whitespace from text nodes,

2. Allow for QNames in content especially in the xsi:type attribute,

3. Rewrite prefixes

1.4.4 Simplicity

C14N 1.x algorithms are complex and depend a full XPath library. This makes it very hard 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 - also it introduces a minimal canonicalization mode.

2.3.1 XML Attribute Processing

Special processing is required for xml:id, xml:lang, xml:space and xml:base attributes. To process this keep a hash table of attribute name to attribute value.

xmlattribContext is a hash table of  name -> value

While processing the ancestors of each subtree, these special XML attributes need to inherited, combined or ignored depending on the parameters.

addXMLAttribute(element, xmlattribContext)
{
   for each of the xml: attributes of this element
   {
      case xml:id attribute: 
        if xmlIdAncestors is inherit then store this attribute value, else do nothing

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

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

      case xml:base attribute 
        if xmlBaseAncestors is inherit then store this attribute value,
        else if xmlBaseAncestors is combine, 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
   } 
}

2.3.2 Node Processing

The following pseudo code use a recursive function processNode(node) to traverse the tree.

• Generic node: Redirect to appropriate node processing function

  processNode(node, namespaceContext)
  {
    call the appropriate function - processElement, processTextNode, ... 
  }
  

• Document node: Loop through all the children

  processDocument(document, namespaceContext)
  {
    Loop through all child nodes and call
      processNode(child, namespaceContext)
  }
  

• Element nodes First check if this matches an exclusion node, in which case completely ignore this element and all its descendants. Otherwise process the namespaces as described in the next section. This will return a list of namespaces to be output and also compute the rewritten prefix value. Now output the element start tag, then the list of namespaces and then the list of attributes. After that loop through all the children, and then output the element end tag.

  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('<')
    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
  
    output('>')
    
    Loop through all child nodes and call
      processNode(child, namespaceContext)
    
    output('</')
    output(element QName)
    output('>')
    
    restore xmlattribContext and namespaceContext
  }
  

  Note: Take special care when rewritePrefix parameter is set. In that case use the new prefix value for all QNames, element names, attribute names, and also QNames in xsi:type attributes.

• Text nodes: Ignore text nodes outside document root. For text nodes inside the document root replace special characters. Also if the trimTextNode is set to true, and there is no xml:space="preserve" declaration trim leading and trailing space.

  processTextNode(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 trimTextNode 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

• Processing Instruction (PI) Nodes: If the string value is empty, do not add the leading space is not added. Also, output a trailing #xA is rendered after the closing PI symbol for PI children of the root node which are before the document element, and output a leading #xA before the opening PI symbol of PI children of the root node which are after the document element.

  processPINode(piNode)
  {
    if before document node
      output('#xA')
      
    output('<?')
    output(the PI target name of the node)
    output(a leading space)
    output(the PI string value)
    output('?>') 
  
    if after document node
      output('#xA')
  }                                        
  

• Comment Nodes: Output nothing uf generating canonical XML without comments. For canonical XML with comments, generate the opening comment symbol (<!--), the string value of the node, and the closing comment symbol (-->). Also, output a trailing #xA after the closing comment symbol for comment children of the root node which are before the document element, and output a leading #xA before the opening comment symbol of comment children of the root node which are after the document element. (Comment children of the root node represent comments outside of the top-level document element and outside of the document type declaration).

  processCommentNode(commentNode)
  {
    if ignoreComments
      return
      
    if before document node
      output('#xA')
      
    output('<!--')
    output(string value of node)
    output('-->')
  
    if after document node
      output('#xA')
  }
  

2.3.3 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, whose prefix is "xmlns" and whose locaName is the prefix begin 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, but there is no declaration for that prefix, the declaration is automatically added when serializing the document.

• Default namespace The default namespace is declared by xmlns="...". If such a declaration does not exist, it means that default namespace is null.

• Visibility utilized This concept is required for exclusive canonicalization. A namespace prefix is visibly utilitized by an element when

  • The element itself uses the prefix. (Note if an element does not have a prefix, that means it visibily utilizes the default namespace.)

  • An attribute of that element uses that prefix, and that attribute is not in the exclusion list. (Note: unlike elements, if an attribute doesn't have a prefix, its means it is a locally scoped attribute. It does NOT mean that the attribute visibily utilizes the default namespace.)

  • xsiTypeAware is true, and the element has an xsi:type attribute, and this attribute's value uses this prefix.

• Namespace context

  namespaceContext is a hash table of  prefix -> (uri, hasBeenOutput, newPrefix)
  

  While traversing the subtrees, maintain a "namespace context" which is mapping of prefixes to URIs. Each prefix should also have

  • a boolean flag hasBeenOutput - whether tha namespace declaration has been output

  • a new prefix value - used for prefix rewriting.

  At the beginning of the canoncalization initialize this to contain only entry - the default namespace mapped to an empty URI, and hasBeenOutput = true. A prefix value of null can be used to denote the default namespace.

• This function is called for every ancestor element, and also at every element of the subtrees (minus the exclusion elements). It adds the namespaces declaration to this namespaceContext.

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

• At every element of the subtree (minus the exclusion subtrees), compute a list of namespaces that need be output. In inclusive mode output the namespace declaration right away, but in exclusive delay outputting till the namespace prefix is visibily utilized. After computing the list of namespaces to be output do prefix rewriting.

  • If prefixRewrite is none, just sort the namespaces to be output by prefix name, default prefix is an empty string so if present it goes first

  • If prefixRewrite is sequential, sort the nameapces to be output by URI. Then sequentially assign them prefixes n0, n1, n2 .... For this keep a counter variable that is initialized to 0 at the beginning of the canonicalization and then incremented to get the prefixes.

  • If prefixRewrite is digest, sort the namespaces to be output by URI. Then assign them a prefixes based on a SHA1 digest of the URI, which is then base64 ed, and base64 chars '/' and '+' replaced by '_' and '-' to achieve XML name rules.

  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 visibily 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 Base64
        string 
      // refer to presentation by Ed Simon  
    }
    
    return nsToBeOutputList    
  }
  

2.3.4 Output rules

• The document is encoded in UTF-8

• Line breaks normalized to #xA on input (automatically done by a DOM parser)

• Attribute values are normalized, if ignoreDTD is false

• Character and parsed entity references are replaced

• CDATA sections are replaced with their character content

• The XML declaration and document type declaration are removed

• Empty elements are converted to start-end tag pairs

• Whitespace outside of the document element and within start and end tags is normalized

• Attribute value delimiters are set to quotation marks (double quotes)

• Special characters in attribute values and character content are replaced by character references

• Default attributes are added to each element, if ignoreDTD is false

2.3.5 Other ideas considered

• Qnames in content: Have another parameter listing other element / attribute names that can have QNames, besides xsi:type. Or simply search all text content for QName.

• Significant white space: Have a parameters listing elements in which whitespace is significant. Instead of listing individual element names, and entire target namespace URI can be specified, e.g. in many elements in xhtml namespace whitespace is significant