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

Re: C14N-Hash implementations???

From: Carl Ellison <cme@jf.intel.com>
Date: Fri, 26 Jul 2002 08:06:11 -0700
Message-Id: <3.0.5.32.20020726080611.01f58868@mailbox.jf.intel.com>
To: "XML Signature (W3C/IETF)" <w3c-ietf-xmldsig@w3.org>

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



>
>Christian

-----BEGIN PGP SIGNATURE-----
Version: PGP 7.1

iQA/AwUBPUFlY8xqBGb+WvJAEQKH+wCgg1LnTsih10io2MsglgTfFMQ+n6UAnA+l
9Jif2VM/EsjnHohFoF8cOv0j
=U1eG
-----END PGP SIGNATURE-----


+--------------------------------------------------------+
|Carl Ellison      Intel Labs        E: cme@jf.intel.com |
|2111 NE 25th Ave                    T: +1-503-264-2900  |
|Hillsboro OR 97124                  F: +1-503-264-6225  |
|PGP Key ID: 0xFE5AF240              C: +1-503-819-6618  |
|  1FDB 2770 08D7 8540 E157  AAB4 CC6A 0466 FE5A F240    |
+--------------------------------------------------------+
Received on Friday, 26 July 2002 11:06:59 UTC

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