W3C home > Mailing lists > Public > w3c-ietf-xmldsig@w3.org > July to September 2002

Re: C14N-Hash implementations???

From: Christian Geuer-Pollmann <geuer-pollmann@nue.et-inf.uni-siegen.de>
Date: Fri, 26 Jul 2002 17:13:59 +0200
To: Carl Ellison <cme@jf.intel.com>, "XML Signature (W3C/IETF)" <w3c-ietf-xmldsig@w3.org>
Message-ID: <33379777.1027703639@crypto>



--On Freitag, 26. Juli 2002 08:06 -0700 Carl Ellison <cme@jf.intel.com> wrote:

>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> At 05:01 PM 7/26/2002 +0200, Christian Geuer-Pollmann wrote:
>>> I am very curious whether anyone has done what I call C14N-Hash.
>>> That is, all C14N implementations I have heard of run exorbitantly
>>> long times.  I suspect that that runtime is due mostly to string
>>> concatenation operations.  If instead of building a single
>>> canonical XML string you walk a DOM and only send substrings to a
>>> hash
>>> accumulator, in the C14N order, you should be able to produce the
>>> C14N hash of a DOM structure in almost the time it takes to walk
>>> that structure for printing without canonicalization.
>>>
>>> So, has anyone done that experiment?  If so, how did it perform?
>>
>> About c14n runtime, there are two basic different forms of c14n: (1)
>> c14nize a full subtree which is moderately fast and (2)
>> canonicalizing a node set (document subset) which takes much longer.
>> The thing that really wastes time is to keep track of the [inscope
>> namespace]s, whether you have to output one or not.
>>
>> My estimation is that the most of the time spent is in the DOM tree
>> traversal (including namespace administration), not in some string
>> concatenations (which involves copy ops etc).
>>
>
> Do you base that estimation on an actual performance analysis?  The
> only C14N implementation that we actually did a performance analysis
> on was spending almost all of its time in free storage routines,
> suggesting that string concatenation was the culprit.  That
> implementation, BTW, was one of two different ones (the only ones we
> have heard of) that each took more time to canonicalize the test
> document than to do public key operations, making C14N completely
> unacceptable for our constrained machine uses.
>
> However, if C14N-Hash is as efficient as I suspect it would be, maybe
> we were scared off inappropriately.
>
> That's why I would like to know if that experiment has been done.

No, I did not do any profiling on my implementation. The estimation was on the complexity of the code which involved the namespace stuff.

Christian
Received on Friday, 26 July 2002 11:11:23 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 20:10:10 UTC