Normalising and signing XML – the rationale for Xoxa

The text below describes the need for a normalised form for XML, describes a normalised form which is simple to generate and is reversible, and which can be signed by GPG in a natural way. The mechanism has been implemented in a Java library.

Contents

Normalising and signing XML

Both normalising and signing XML appear to be hard problems, given the size and complexity of the work of the W3C Signature working group, which has produced recommendations on creating signatures for XML, as well as on the necessary problem of canonicalising XML prior to signature.

The reason why canonicalisation is necessary is that for each XML document, there is a set of other documents with trivially different syntax, but which mean ‘the same thing’ – that is, they might use single-quotes rather than double-quotes for marking attributes, or have the attributes in a different order, or have ‘unimportant’ whitespace differences between elements, or appear in a different encoding, while still being usefully regarded as the same document. If you read an XML document into a system, either an application for processing, or into an XML database for storage, it might be hard to arrange that the XML document you write out or retrieve is represented by exactly the same sequence of bytes, which is necessary for any more-or-less naive signature to validate.

In a sturdily-reasoned essay, Peter Gutmann has discussed this, and suggested that the approach used by the W3C WG is fundamentally mistaken: Why XML Security is Broken. It's a reasonably persuasive argument for the general nproblem, but in the case of a large category of XML documents (and I'm interested in particular in VOEvent packets), the problem is not as hard as this analysis suggests, because we don't have to solve the general problem.

The two key points that Gutmann makes are:

One solution is not to normalise at all, but instead to regard the on-disk or on-the-wire XML document as the bag of bytes to be signed. This works, but throws away the mutability of XML, which means that if you want to actually do anything with the XML other than simply admire it, and if you want to round-trip the XML into and out of a system which doesn't know about your signature, you're presented with the dilemma of either abandoning the signature, or else worrying about how to reproduce exactly the same bag of bytes when the XML is serialised at some later stage.

It is part of the point of XML that XML documents are not just bags of bytes, and that there is a well-defined distinction between important content and meaninglessly mutable syntax. XML processors and editors freely take advantage of this: it is generally hard to guarantee what flavour of quotes will be written by an XSLT transformer, or that (insignificant) whitespace will be preserved by XML editors. Schemas can make this mutability more pronounced, since amongst other things they can license more extensive syntactic transformations. This syntactic mutability is reflected in the fact that applications typically do not operate on the bytes of a document or stream, but instead on the abstracted content of a document, as exposed via an API such as SAX, DOM, or an XSL node-set. An XML database is free to store an XML document in any way it likes, as long as it produces an equivalent document when required.

These notions have been formalised in the concept of the XML Information Set, which describes all of the information which a complete XML processor must preserve and make available to an application (the ‘canonicalization’ work of the XML Signatures WG is effectively concerned with defining a single serializaton of this set).

The XML InfoSet is quite elaborate, and includes many features of an XML document. The SAX model, however, implicitly defines a much simpler information model for XML, with just 11 API functions (in the org.xml.sax.ContentHandler interface). The SAX model is defined in terms of Java, but there are exactly analogous APIs in other languages, which can consequently support the same model. Viewed through a SAX lens, an XML document is a rather simple thing, which is consequently very simple to normalise, serialise and then sign.

A simple-enough normalisation procedure

What I'm proposing here is a very simple normalisation mechanism, which straightforwardly turns an XML document into a stream of bytes, in a well-defined, streamable and reversible way (that's reversible in the sense that the stream can be turned back into XML, in one or other equivalent forms). The resulting stream can be signed by GPG in a natural way, and the signature embedded into the XML equally naturally.

The simple normalisation turns the XML:

<doc>
<p class='foo'>Hello</p>
  <p> there
chum
</p>
</doc>

into the normalised form:

(doc
Aclass foo
(p
-Hello
)p
(p
- there chum 
)p
)doc

This normalised form can then be signed, and the signature reinserted into the original XML, or else included as the parsed XML is passed downstream.

The following document has the same normalised form as the earlier one, but includes a PGP signature block which can be used to verify it:

<doc><p class="foo">Hello</p><p> there
chum </p>
<?signature armor='-----BEGIN PGP SIGNATURE-----
....
-----END PGP SIGNATURE-----'?></doc>

The normalisation procedure

The normalisation is done in two steps. Firstly, we define a textual representation of the parsed XML; second, we define a transformation of this output which normalises it.

The textual representation is based on the sgmls ESIS output, which was originally defined, in the 90s, by the sgmls program. The original point of the format was that it should be easy for downstream tools to parse. The point here is that it turns an XML file into an unambiguous byte-stream and, further, that it permits a normalisation operation which is both well-defined and simple.

There isn't a complete overlap between the ESIS and the SAX models, so there are some differences in the output of this normalisation. All the differences here are extensions rather than changes.

The output consists of a sequence of records, separated by CR LF (ie bytes 0xd 0xa). Each line consists of a start character indicating which type of output record it represents, followed by one or more arguments. There are always the same number of arguments, all separated by a single space.

Mprefix uristart prefix mappingextn
mprefixend prefix mappingextn
Aattname CDATA valuedeclare attributeESIS
Bnamespace localname CDATA valuedeclare namespaced attributeextn
(namestart elementESIS
[namespace localnamestart namespaced elementextn
)nameend elementESIS
]namespace localnameend namespaced elementextn
-textcharacter contentESIS
=textignorable whitespaceextn
?pi dataprocessing instructionESIS
Xnameskipped entityextn

Each start element event is preceded by the set of attributes on that event.

Note:

An important function of this class is to normalise the ESIS output. We do this in the following ways:

  1. Attribute records (‘A’ and ‘B’) are alphabetised on output (this implies that all of the ‘A’ records appear before the ‘B’ records).
  2. Successive 'character content' events are merged, and leading and trailing whitespace is trimmed from the resulting merged event. If the resulting event is empty, it is discarded. Ignorable whitespace is... ignored.
  3. Start and end prefix mappings (‘M’ and ‘m’) are discarded.
  4. Any processing instruction which has a ‘target’ of signature is removed.
  5. All of the output is encoded to bytes as UTF-8.

The result of this is to turn the XML:

<doc><ns:p class='foo'
           xmlns:ns="urn:namespace"
           ns:att='bar'>Hello</ns:p>
  <p> there
chum
</p>
</doc>

into the (unnormalised) ESIS form:

(doc
Mns urn:namespace
Aclass CDATA foo
Burn:namespace att CDATA bar
[urn:namespace p
-Hello
]urn:namespace p
mns
-\n  
(p
- there\nchum\n
)p
-\n
)doc

This can also be given the normalised form:

(doc
Aclass CDATA foo
Burn:namespace att CDATA bar
[urn:namespace p
-Hello
]urn:namespace p
(p
-there\nchum
)p
)doc

In the normalised form, the prefix mappings have been removed (the prefixes are not semantically important), leading and trailing whitespace has been removed from the ‘-’ lines, and all-whitespace ‘-’ records have been removed.

Norman Gray