- From: Sean Mullan <Sean.Mullan@Sun.COM>
- Date: Tue, 21 Apr 2009 09:39:02 -0400
- To: Pratik Datta <pratik.datta@oracle.com>
- Cc: Thomas Roessler <tlr@w3.org>, XMLSec WG Public List <public-xmlsec@w3.org>
Pratik Datta wrote: > Yes this is better than a vanilla exclusive C14N, but it is possible to > do even better, if we limit to complete subtrees, or subtrees with > exclusions of complete subtrees. > > In the original algorithm you start with a nodeset, and sort the nodeset > by document order. This sorting is a very expensive operation, the > nodeset can have thousands of nodes, especially if you expand out all > namespace nodes as well, and the "document order compare function" is > not cheap. > > But in this algorithm, you start with the DOM tree, which is already in > a sorted order. Now for each element of the tree you need to check if it > exists in the XPath nodeset. > > However this algorithm has two problems > a) It asks to you iterate over the entire tree. If you are signing only > a small part of the DOM tree, why iterate over the entire tree and > reject most of the nodes? Instead just limit to only those subtrees > that are being signed. > b) It asks you compare each node with an XPath subset. Note this XPath > nodeset has all nodes expanded out so it is a large data structure that > you need to create. > > For simple ID based references (which by definition select a single > complete subtree), you can bypass both these issues, and just iterate > over that particular subtree, and not check against any XPath nodeset, > because you know that all of the subtree is being signed. > > This simple algorithm can be extended to the case where there are > multiple subtrees being signed - just sign the trees one by one.And > also to the case of subtree exclusions - just prune your traversal > whenever you come to an exclusion subtree. The Enveloped Signature > Transform, which is very commonly used can be assumed to be such kind of > exclusion. > > With this simple algorithm, the speed of canonicalization is almost the > same as XML serialization. And I suspect many XML DSig C14N implementations have already been enhanced to do the subtree optimizations above. At least Apache's implementation is. --Sean
Received on Tuesday, 21 April 2009 13:39:40 UTC