- From: Donald E. Eastlake 3rd <dee3@torque.pothole.com>
- Date: Wed, 27 Oct 1999 11:47:54 -0400
- To: "IETF/W3C XML-DSig WG" <w3c-ietf-xmldsig@w3.org>

From: "Phillip M Hallam-Baker" <pbaker@verisign.com> To: "Donald E. Eastlake 3rd" <dee3@torque.pothole.com>, "IETF/W3C XML-DSig WG" <w3c-ietf-xmldsig@w3.org> Date: Wed, 25 Aug 1999 13:04:18 -0400 Message-ID: <000801beef1b$de1ab400$6e07a8c0@pbaker-pc.verisign.com> In-Reply-To: <199908251556.LAA01878@torque.pothole.com> >> >The definition of canonicalization is a function f(x) such that >> >f(x) = f(f(x)). >> >> No. That's the fix point property, which is a desireable property of >> canonicalization but by no means its definition. > >Actually it is a required property for it to be a canonical form. Your proof only works with the unstated assumption that the output of the canonicalization function is of exactly the same syntactic and semantic type as the input. However, that is not how I used the word and not how you have always used it since you said that DOM produces a canonicalization of XML. XML is a octet stream. The output of DOM is an abstract structure with a specified API. The DOM canonicalization function converts the octet stream to the structure. DOM(DOM(x)) is meaningless and therefor not equal to DOM(x) which is meaningful (assuming x is XML). >The point of canonicalization is to be able to test for equivalence >between different syntactical representations of the same data. > >> My definition of >> canonicalization is a function f(x) which is useful for application A >> if f(x1) = f(x2) implies that application A considers x1 and x2 >> semantically identical. > >And f(x1) <> f(x2) implies they are distinct. Therefore a c14n >function must have the fixed point property. > >Lema >Exists f(x) <> f(f(x)) for some x > >=> f(x) <> f(x2) where x2 = f(f(x)) ^^^^^^^ you just want f(x) here >but x, x2 are semantically equivalent, therefore > >f(x) = f(x2), thus disproving the lema. Above is your bug. f(x) is identically x2 but x isn't even necessarily the same type. No XML object is identical to the abstract structure DOM converts XML objects to. You are using "semantic equivalence" in some sort of sense which is not the same as mathematical equality. Perhaps this will be seen more clearing if you consider something I'll make up called DOMstring. DOMstring produces an octet stream but it is the result of traversing the DOM tree in a specified way and replacing all the name space labels with full URIs. This is probably a more reasonable example since the kinds of canonicalization (and trasnformation) functions we are talking about produce octet streams to sign. DOMstring output is not syntactically correct XML. Even though the input and output of DOMstring are octet strings, you can't apply DOMstring to the output of DOMstring, only to XML. Thus f(f(x)) and f(x2) which appear in varous of your statements are all meaningless and no matter how "semantically equivalent" x and DOMstring(x) are, it does not follow that DOMstring(x) = DOMstring(DOMstring(x)) since the left had side is an octet string and the right hand side is a type error. But if you look at the definition of canonicalizaton I used above, you will find that, by that definition, DOMstring is a fine canonicalization algorithm for DOM oriented applications. >Therefore all canonicalization functions are fixed point functions >QED. There is nothing particularly wrong with the unstated assumption/definition you are using above for canonical, which makes your proof true. But "canonical" has not always been used with that assumption in this working group. Donald =================================================================== Donald E. Eastlake 3rd +1 914-276-2668 dee3@torque.pothole.com 65 Shindegan Hill Rd, RR#1 +1 914-784-7913(w) dee3@us.ibm.com Carmel, NY 10512 USA

Received on Wednesday, 27 October 1999 11:47:58 UTC