RFC 2803

RFC 2803: Digest Values for DOM (DOMHASH) 💖 (part 1 of 2)

okay bestie, this one is from April 2000, and it's all about making digest (hash) values for XML and DOM stuff 🦋

• Stream: Network Working Group
• Authors: H. Maruyama, K. Tamura, and N. Uramoto, all from IBM 👑
• Category: Informational
• Date: April 2000
• Obsoletes / Updates: this header doesn't list either one 🙈

---

Status of This Memo

okay so this memo is just giving info to the Internet community 📖 it is NOT an Internet standard of any kind, so don't go treating it like one 💅 and anyone can distribute it, no limits ✨

Copyright Notice

Copyright (C) The Internet Society (2000). All Rights Reserved. 🎀

Abstract

this doc gives a super clear, no-confusion definition of digest (hash) values for XML objects, even when the XML is written in different ways on the surface 🫶 that definition can be used for XML digital signatures, and also for efficient replication of XML objects. it's giving precision 🔥

Table of Contents

   1. Introduction............................................2
   2. Digest Calculation......................................3
   2.1. Overview..............................................3
   2.2. Namespace Considerations..............................4
   2.3. Definition with Code Fragments........................5
   2.3.1. Text Nodes..........................................5
   2.3.2. Processing Instruction Nodes........................6
   2.3.3. Attr Nodes..........................................6
   2.3.4. Element Nodes.......................................7
   2.3.5. Document Nodes......................................9
   3. Discussion..............................................9
   4. Security Considerations.................................9
   References................................................10
   Authors' Addresses........................................10
   Full Copyright Statement..................................11

---

1. Introduction ✨

so the whole point of this doc is to give a clear, unambiguous definition of digest (hash) values for XML objects [XML] 💖 two subtrees count as identical if their hash values match, and different if their hash values don't 🙌

there are at least two usage scenarios for DOMHASH 🧚 the first one is as the basis for XML digital signatures. digital signature algorithms normally hash the content that's getting signed before the signing happens, and DOMHASH gives a concrete definition of how that hash value gets calculated 🔐

the second one is for synchronizing two DOM structures [DOM] 🌈 picture this: a server program makes a DOM structure that clients are gonna render. if the server keeps making small changes to a big DOM tree, it's way better to only send over the parts that changed 😭 a client can start a request by sending the root hash value of the structure it has cached. if that matches the root hash value of the server's current structure, nothing needs to be sent at all 💅 if it doesn't match, the server checks its cache for older versions. if it finds one that matches the client's version, it figures out what's different from the current version by recursively comparing the hash values of each node. this way the client only gets the updated part of a big structure, without having to request the whole thing ✨

one way to define digest values is to use a surface string as the input for a digest algorithm. but ngl that approach has a bunch of problems 💀 the same internal DOM structure can be written as a bunch of different surface strings, even when every one of them is totally valid XML. stuff like how whitespace gets handled, which character encodings get picked, how entity references (aka ampersands) are written, and so on all change what the surface string looks like. if two implementations generate surface strings differently, the hash values come out different, which means digital signatures can't be validated and identical DOM structures won't be detected as identical 😭 so it's way better to define the DOM digest in DOM terms. basically, it's an unambiguous algorithm that operates on a DOM tree, and that's the approach this spec takes 👑

namespaces are another source of surface string variation 🎀 different namespace prefixes can be used to represent the same namespace URI [URI]. in the example below, the prefix "edi" is bound to the URI "http://ecommerce.org/schema", but that prefix can be picked arbitrarily without changing the logical contents, like in the second example 🦋

<?xml version="1.0"?>
<root xmlns:edi='http://ecommerce.org/schema'>
    <edi:order>
        :
    </edi:order>
</root>


<?xml version="1.0"?>
<root xmlns:ec='http://ecommerce.org/schema'>
    <ec:order>
        :
    </ec:order>
</root>

the DOMHASH defined here is designed so that the choice of namespace prefix doesn't affect the digest value 💖 in the example above, both "root" elements get the same digest value. no cap, that's the whole vibe 🫶

2. Digest Calculation 🌸

2.1. Overview 💅

hash values are defined on the DOM type Node 🧚 we look at these five node types, which are the ones used to represent a DOM document structure:

   - Text
   - ProcessingInstruction
   - Attr
   - Element
   - Document

comment nodes and Document Type Definitions (DTDs) don't take part in the digest value calculation 🙈 that's because DOM doesn't require a conformant processor to create data structures for them. DOMHASH is designed so it can be computed with any XML processor that's conformant to the DOM or SAX [SAX] specification ✨

nodes with the node type EntityReference must be expanded before digest calculation 🔥

the digest values are defined recursively on each level of the DOM tree, so when a small part of the tree changes, only the relevant part needs to be recalculated 🌈

the precise definitions for these types come next. the format of the data that gets fed to a hash algorithm is described with a figure and a simple description, followed by a Java code fragment that only uses the DOM API and the JDK 1.1 Platform Core API 💜 that way the semantics stay unambiguous 🎀

rule of thumb: all strings are in UTF-16BE [UTF16] 🦋 if there's a run of text nodes with no element nodes in between, those text nodes get merged into one by concatenating them. a zero-length text node is always ignored 💖

heads up, validating and non-validating XML processors can generate different DOM trees from the same XML document, because of attribute normalization and default attributes 👀 if DOMHASH is being used to test logical equivalence between two XML documents (as opposed to DOM trees), it may be necessary to normalize attributes and supply default attributes before doing the DOMHASH calculation 🫶

some legacy character encodings (like ISO-2022-JP) are a little ambiguous when translating into Unicode 😭 that also depends on the XML processor. handling those processor dependencies is out of scope for this document 🙅‍♀️

2.2. Namespace Considerations 🌸

to avoid depending on the namespace prefix, we use "expanded names" for the digest calculation ✨ if an element name or an attribute name is qualified by either an explicit namespace prefix or a default namespace, then before digest calculation the name's LocalPart gets the URI of the namespace (the namespace name as defined in the Namespace specification [NAM]) prepended to it, with a colon in between 💅 in the example below, the default qualified name "order" expands into "http://ecommerce.org/schema:order", while the explicit qualified name "book:title" expands into "urn:loc.gov:books:title" before digest calculation 🧚

<?xml version="1.0"?>

<root xmlns='http://ecommerce.org/schema'
         xmlns:book='urn:loc.gov:books'>
    <order>
       <book:title> ... </book:title>
        :
    </order>
</root>

here's how we define an expanded name (for an element or an attribute) 🎀

   If a name is not qualified, the expanded name is the name itself.

   If a name is qualified with the prefix "xmlns", the expanded name
   is undefined.

   If a name is qualified either by default or by an explicit
   namespace prefix, the expanded name is URI bound to the namespace
   + ":" + LocalPart

in the example code below, we assume the getExpandedName() method (which returns the expanded name as defined above) is defined in both the Element and Attr interfaces of DOM 💖

note that digest values are NOT defined on namespace declarations 🙈 in other words, the digest value is not defined for an attribute when:

   - the attribute name is "xmlns", or
   - the namespace prefix is "xmlns".

so in the example above, the two attributes that are namespace declarations don't have digest values, which means they won't take part in calculating the digest value of the "root" element 🌈

2.3. Definition with Code Fragments 🦋

the code fragments in the definitions below assume they live in implementation classes of Node 🧠 so a method call without an explicit object reference is for the Node itself. for example, getData() returns the text data of the current node if it's a Text node 💅 the parameter digestAlgorithm gets replaced with an identifier for the digest algorithm, like "MD5" [MD5] and "SHA-1" [SHA] ✨

the computation starts with a four byte integer that represents the type of the node, like TEXT_NODE or ELEMENT_NODE 🔥

2.3.1. Text Nodes 💖

the hash value of a Text node is computed over the four byte header, followed by the UTF-16BE encoded text string 🫶

   - TEXT_NODE (3) in 32 bit network-byte-ordered integer
   - Text data in UTF-16BE stream (variable length)

public byte[] getDigest(String digestAlgorithm) {
    MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
    md.update((byte)0);
    md.update((byte)0);
    md.update((byte)0);
    md.update((byte)3);
    md.update(getData().getBytes("UnicodeBigUnmarked"));
    return md.digest();
}

MessageDigest lives in the java.security.* package, which is one of the built-in packages of JDK 1.1 🌸

2.3.2. ProcessingInstruction Nodes 🧚

a ProcessingInstruction (PI) node has two components: the target and the data 🎀 so the hash is computed over the concatenation of both, separated by 'x0000' 💜 the PI data runs from the first non white space character after the target up to the character right before the "?>" 🙌

   - PROCESSING_INSTRUCTION_NODE (7) in 32 bit network-byte-ordered
     integer
   - PI target in UTF-16BE stream (variable length)
   - 0x00  0x00
   - PI data in UTF-16BE stream (variable length)

public byte[] getDigest(String digestAlgorithm) {
    MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
    md.update((byte)0);
    md.update((byte)0);
    md.update((byte)0);
    md.update((byte)7);
    md.update(getName().getBytes("UnicodeBigUnmarked"));
    md.update((byte)0);
    md.update((byte)0);
    md.update(getData().getBytes("UnicodeBigUnmarked"));
    return md.digest();
}

2.3.3. Attr Nodes ✨

Okay so Attr nodes are basically PI nodes' cousins 💅 Their digest works the same way, with one extra piece: we need a separator between the expanded attribute name and the attribute value. Here's the lowkey genius part: 0x0000 in UTF-16BE is allowed nowhere in an XML document, so it's a perfect unambiguous separator 🫶 The expanded name has to be the attribute name because it might be qualified 🎀

One spicy edge case 🌶️: if the attribute is a namespace declaration (the attribute name is "xmlns" or its prefix is "xmlns"), the digest value is undefined and getDigest() should return null 🙈

- ATTRIBUTE_NODE (2) in 32 bit network-byte-ordered integer
- Expanded attribute name in UTF-16BE stream (variable length)
- 0x00  0x00
- Attribute value in UTF-16BE stream (variable length)

public byte[] getDigest(String digestAlgorithm) {
    if (getNodeName().equals("xmlns")
            || getNodeName().startsWith("xmlns:"))
        return null;
    MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
    md.update((byte)0);
    md.update((byte)0);
    md.update((byte)0);
    md.update((byte)2);
    md.update(getExpandedName().getBytes("UnicodeBigUnmarked"));
    md.update((byte)0);
    md.update((byte)0);
    md.update(getValue().getBytes("UnicodeBigUnmarked"));
    return md.digest();
}

2.3.4. Element Nodes 🌸

Element nodes are the most complex 😭 because they're made of other nodes, recursively. The hash values of those component nodes get reused to calculate the node's digest, so when the structure only changes a little, we can save computation. Very efficient, very iconic 👑

First up, we collect all the attributes except namespace declarations. That list gets sorted lexicographically by the expanded attribute names, based on Unicode character code points. When no surrogate characters are involved, this matches sorting in ascending order of the UTF-16BE encoded expanded attribute names, using the string comparison operator String.compareTo() in Java 🧚

- ELEMENT_NODE (1) in 32 bit network-byte-ordered integer
- Expanded element name in UTF-16BE stream (variable length)
- 0x00  0x00
- A number of non-namespace-declaration attributes in 32 bit
  network-byte-ordered unsigned integer
- Sequence of digest values of non-namespace-declaration attributes,
  sorted lexicographically by expanded attribute names
- A number of child nodes (except for Comment nodes) in 32bit

  network-byte-ordered unsigned integer
- Sequence of digest values of each child node except for Comment
  nodes (variable length) (A sequence of child texts is merged to one
  text. A zero-length text and Comment nodes are not counted as
  child)

public byte[] getDigest(String digestAlgorithm) {
    MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    DataOutputStream dos = new DataOutputStream(baos);
    dos.writeInt(ELEMENT_NODE);//This is stored in network byte order
    dos.write(getExpandedName().getBytes("UnicodeBigUnmarked"));
    dos.write((byte)0);
    dos.write((byte)0);
    // Collect all attributes except for namespace declarations
    NamedNodeMap nnm = this.getAttributes();
    int len = nnm.getLength()
            // Find "xmlns" or "xmlns:foo" in nnm and omit it.
    ...
    dos.writeInt(len);    // This is sorted in the network byte order
    // Sort attributes lexicographically by expanded attribute
    // names.
    ...
    // Assume that `Attr[] aattr' has sorted Attribute instances.
    for (int i = 0;  i < len;  i ++)
        dos.write(aattr[i].getDigest(digestAlgorithm));
    Node n = this.getFirstChild();
    // Assume that adjoining Texts are merged,
    // there is  no 0-length Text, and
    // comment nodes are removed.
    len = this.getChildNodes().getLength();
    dos.writeInt(len);    // This is stored in the network byte order
    while (n != null) {
        dos.write(n.getDigest(digestAlgorithm));
        n = n.getNextSibling();
    }
    dos.close();
    md.update(baos.toByteArray());
    return md.digest();
}

2.3.5. Document Nodes 🦋

A Document node can have PI nodes before and after the root Element node. Its digest value is computed from the sequence of digest values of the pre-root PI nodes, the root Element node, and the post-root PI nodes, in that order. Comment nodes and DocumentType nodes, if any, get ignored 🙈

- DOCUMENT_NODE (9) in 32 bit network-byte-ordered integer
- A number of child nodes (except for Comment and DocumentType nodes)
  in 32bit network-byte-ordered unsigned integer
- Sequence of digest values of each child node except for Comment and
  DocumentType nodes (variable length)

public byte[] getDigest(String digestAlgorithm) {
    MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    DataOutputStream dos = new DataOutputStream(baos);
    dos.writeInt(DOCUMENT_NODE);//This is stored in network byte order

    // Assume that Comment and DocumentType nodes are removed and this
    // node has only an Element node and PI nodes.
    len = this.getChildNodes().getLength();
    dos.writeInt(len);    // This is stored in the network byte order
    Node n = this.getFirstChild();
    while (n != null) {
        dos.write(n.getDigest(digestAlgorithm));
        n = n.getNextSibling();
    }
    dos.close();
    md.update(baos.toByteArray());
    return md.digest();
}

3. Discussion 💜

This definition can be implemented efficiently with any XML processor that conforms to either the DOM or the SAX specification. Reference implementations are available on request ✨

4. Security Considerations 🚨

Okay, serious moment, bestie 🥺 DOMHASH is expected to be the basis for digital signatures and other security and integrity uses. Whether it's actually appropriate for that depends on two things: how secure the hash algorithm is, and whether the parts of the DOM model that DOMHASH folds into the digest actually include the fundamental characteristics you want to check 💀 So double-check both before you trust it with anything important!

References 📚

[DOM] "Document Object Model (DOM), Level 1 Specification", October 1998, http://www.w3.org/TR/REC-DOM-Level-1/

[MD5] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 1992.

[NAM] Tim Bray, Dave Hollander, Andrew Layman, "Namespaces in XML", http://www.w3.org/TR/1999/REC-xml-names-19990114.

[SAX] David Megginson, "SAX 1.0: The Simple API for XML", http://www.megginson.com/SAX/, May 1998.

[SHA] (US) National Institute of Standards and Technology, "Federal Information Processing Standards Publication 180-1: Secure Hash Standard", 17 April 1995.

[URI] Berners-Lee, T., Fielding, R. and L. Masinter, "Uniform Resource Identifiers (URI): Generic Syntax", RFC 2396, August 1998.

[UTF16] Hoffman, P., Yergeau, F., "UTF-16, an encoding of ISO 10646", RFC 2781, February 2000.

[XML] Tim Bray, Jean Paoli, C. M. Sperber-McQueen, "Extensible Markup Language (XML) 1.0", http://www.w3.org/TR/1998/REC-xml- 19980210

Authors' Addresses 🎀

Hiroshi Maruyama, IBM Research, Tokyo Research Laboratory

EMail: maruyama@jp.ibm.com

Kent Tamura, IBM Research, Tokyo Research Laboratory

EMail: kent@trl.ibm.co.jp

Naohiko Uramoto, IBM Research, Tokyo Research Laboratory

EMail: uramoto@jp.ibm.com

Full Copyright Statement ⭐

Copyright (C) The Internet Society (2000). All Rights Reserved.

This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.

The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.

This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Acknowledgment 🫶

Funding for the RFC Editor function is currently provided by the Internet Society. 🌈