Internet DRAFT - draft-hiroshi-dom-hash

draft-hiroshi-dom-hash




Network Working Group                                    Hirosi Maruyama
INTERNET-DRAFT                                               Kent Tamura
February 1999                                            Naohiko Uramoto
Expires: August 1999                                                 IBM



                    Digest Values for DOM (DOMHASH)
                    ------ ------ --- --- ---------

                            Hiroshi Maruyama
                              Kent Tamura
                            Naohiko Uramoto



Status of This Document

   This draft, file name draft-hiroshi-dom-hash-01.txt, is intended to
   be become a Proposed Standard RFC.  Distribution of this document is
   unlimited. Comments should be sent to the xml-dsig mailing list
   <xml-dsig@socratic.org> or to the authors.

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.  Internet drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas
   and its working groups. Note that other groups may also distribute
   working information as Internet drafts.

   Internet Drafts are draft documents valid for a maximum of six months
   and can be updated, replaced or obsoleted by other documents at any
   time. It is inappropriate to use Internet drafts as reference
   material or to cite them as other than as "work in progress".

   To learn the current status of any Internet draft please check the
   "lid-abstracts.txt" listing contained in the Internet drafts shadow
   directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ftp.ietf.org (US East coast) or
   ftp.isi.edu (US West coast). Further information about the IETF can
   be found at URL: http://www.ietf.org/















H. Maruyama, K. Tamura, & N. Uramoto                            [Page 1]


INTERNET-DRAFT                  DOMHASH                    February 1999


Abstract

   This internet draft defines a clear and unambiguous definition of
   digest (hash) values of the XML objects regardless of the surface
   string variation of XML. This definition can be used for XML digital
   signature as well efficient replication of XML objects.














































H. Maruyama, K. Tamura, & N. Uramoto                            [Page 2]


INTERNET-DRAFT                  DOMHASH                    February 1999


Table of Contents

      Status of This Document....................................1

      Abstract...................................................2

      Table of Contents..........................................3

      1. Introduction............................................4
      2. Digest Calculation......................................5
      2.1. Overview..............................................5
      2.2. Namespace Considerations..............................6
      2.3. Definition with Code Fragments........................7
      2.3.1. Text Nodes..........................................7
      2.3.2. ProcessingInstruction Nodes.........................8
      2.3.3. Attr Nodes..........................................8
      2.3.4. Element Nodes.......................................9
      3. Suggested API..........................................10
      4. Discussion.............................................11
      5. Security Considerations................................12

      References................................................13

      Author's Address..........................................14
      Expiration and File Name..................................14



























H. Maruyama, K. Tamura, & N. Uramoto                            [Page 3]


INTERNET-DRAFT                  DOMHASH                    February 1999


1. Introduction

   The purpose of this document is to give a clear and unambiguous
   definition of digest (hash) values of the XML objects [XML]. In
   addition, we propose to add a new API getDigest() to the interface
   Node that returns a digest value, a fixed length value (normally 128
   bits or 160 bits) representing an entire subtree. Two subtrees are
   considered identical if their hash values are the same, and different
   if their hash values are different.

   There are at least two usage scenarios of DOMHASH. One is as a basis
   for digital signatures for XML. Digital signature algorithms normally
   require hashing a signed content before signing.  DOMHASH provides a
   concrete definition of the hash value calculation.

   The other is to use DOMHASH when synchronizing two DOM structures
   [DOM]. Suppose that a server program generates a DOM structure which
   is to be rendered by clients. If the server makes frequent small
   changes on a large DOM tree, it is desirable that only the modified
   parts are sent over to the client. A client can initiate a request by
   sending the root hash value of the structure in the cache memory. If
   it matches with the root hash value of the current server structure,
   nothing needs be sent. If not, then the server compares the client
   hash with the older versions in the server's cache. If it finds one
   that matches the client's version of the structure, then it locates
   differences with the current version by recursively comparing the
   hash values of each node. This way, the client can receive only an
   updated portion of a large structure without requesting the whole
   thing.

   One way of defining digest values is to take a surface string as the
   input for a digest algorithm. However, this approach has several
   drawbacks. The same internal DOM structure may be represented in may
   different ways as surface strings even if they strictly conform to
   the XML specification.  Treatment of white spaces, selection of
   character encodings, entity references (i.e., use of ampersands), and
   so on have impact on the generation of a surface string. If the
   implementations of surface string generation are different, the hash
   values would be different, resulting in unvalidatable digital
   signatures and unsuccessful detection of identical DOM structures.
   Therefore, it is desirable that digest of DOM is defined in the DOM
   terms -- that is, as an unambiguous algorithm operating on a DOM
   tree.  This is the approach we take in this specification.

   Introduction of namespace is another source of variation of surface
   string because different namespace prefixes can be used for
   representing the same namespace URI [URI]. In the following example,
   the namespace prefix "edi" is bound to the URI
   "http://ecommerce.org/schema" but this prefix can be arbitrary chosen
   without changing the logical contents as shown in the second example.


H. Maruyama, K. Tamura, & N. Uramoto                            [Page 4]


INTERNET-DRAFT                  DOMHASH                    February 1999


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


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

   The DOMHash defined in this document is designed so that the choice
   of the namespace prefix does not affect the digest value. In the
   above example, both the "root" elements will get the same digest
   value.



2. Digest Calculation



2.1. Overview

   Hash values are defined on the DOM type Node. We consider the
   following four node types that are used for representing a DOM
   document structure:

     1. Element
     2. Attr
     3. ProcessingInstruction
     4. Text

   Comment nodes and Document Type Definitions (DTDs) do not participate
   in the digest value calculation.  This is because DOM does not
   require a conformant processor to create data structures for these.
   DOMHash is designed so that it can be computed with any XML processor
   conformant to the DOM or SAX [SAX] specification.

   The digest values are defined recursively on each level of the DOM
   tree so that only a relavant part needs to be recalculated when a
   small portion of the tree is changed.

   Below, we give the precise definitions of digest for these types. We
   describe the format of the data to be supplied to a hash algorithm
   using a figure and a simple description, followed by a Java code


H. Maruyama, K. Tamura, & N. Uramoto                            [Page 5]


INTERNET-DRAFT                  DOMHASH                    February 1999


   fragment using the DOM API and the JDK 1.1 Platform Core API only.
   Therefore, the semantics should be unambiguous.

   As the rule of thumb, all strings are to be in UTF-16 in the network
   byte order (Big Endian) with no byte order mark. If there is a
   sequence of text nodes without any element nodes inbetween, these
   text nodes are merged into one by concatenating them. A zero-length
   text node is always ignored.



2.2. Namespace Considerations

   To avoid the dependence on the namespace prefix, we use "expanded
   names" to do digest calculation. If an element name or an attribute
   name is qualified either by a explicit namespace prefix or by a
   default namespace, the name's LocalPart is prepended by the URI of
   the namespace (the namespace name as defined in the NameSpace
   specification [NAM]) and a colon before digest calculation. In the
   following example, the default qualified name "order" is expanded
   into "http://ecommerce.org/schema:order" while the explicit qualified
   name "book:title" is exapanded 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>
            :
        </name>
    </root>

   We define an expanded name (either for element or attirbute) as
   follows:

        If a name is not qualified, the exapanded 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 following example code, we assume that the getExpandedName()
   method (which returns the expanded name as defined above) is defined
   in both Element and Attr interfaces of DOM.


H. Maruyama, K. Tamura, & N. Uramoto                            [Page 6]


INTERNET-DRAFT                  DOMHASH                    February 1999


   Note that the 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".

   In the above example, the two attributes which are namespace
   declarations do not have digest values and therefore will not
   participate in the calculation of the digest value of the "root"
   element.



2.3. Definition with Code Fragments

   The code fragments in the definitions below assume that they are in
   implementation classes of Node. Therefore, a methods call without an
   explicit object reference is for the Node itself. For example,
   getData() returns the text data of the current node if it is a Text
   node. The parameter digestAlgorithm is to be replaced by an
   identifier of the digest algorithm, such as "MD5" [MD5] and "SHA-1".

   The computation should begin with a four byte integer that represents
   the type of the node, such as Node.TEXT_NODE or Node.ELEMENT_NODE.



2.3.1. Text Nodes

   The hash value of a Text node is computed on the four byte header
   followed by the UTF-16 encoded text string.

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

     public byte[] getDigest(String digestAlgorithm) {
         MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
         md.update((byte)((Node.TEXT_NODE >> 24) & 0xff));
         md.update((byte)((Node.TEXT_NODE >> 16) & 0xff));
         md.update((byte)((Node.TEXT_NODE >> 8) & 0xff));
         md.update((byte)(Node.TEXT_NODE & 0xff));
         md.update(getData().getBytes("UnicodeBigUnmarked"));
         return md.digest();
     }

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




H. Maruyama, K. Tamura, & N. Uramoto                            [Page 7]


INTERNET-DRAFT                  DOMHASH                    February 1999


2.3.2. ProcessingInstruction Nodes

   A ProcessingIinstruction (PI) node has two components: the target and
   the data. Accordingly, the hash is computed on the concatenation of
   both, separated by 'x0000'. PI data is from the first non white space
   character after the target to the character immediately preceding the
   "?>".

   - Node.PROCESSING_INSTRUCTION_NODE (7) in 32 bit network-byte-ordered
   integer

   - PI target in UTF-16 stream (variable length)
   - 0x00  0x00
   - PI data in UTF-16 stream (variable length)

   public byte[] getDigest(String digestAlgorithm) {
       MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
       md.update((byte)((Node.PROCESSING_INSTRUCTION_NODE >> 24) & 0xff));
       md.update((byte)((Node.PROCESSING_INSTRUCTION_NODE >> 16) & 0xff));
       md.update((byte)((Node.PROCESSING_INSTRUCTION_NODE >> 8) & 0xff));
       md.update((byte)(Node.PROCESSING_INSTRUCTION_NODE & 0xff));
       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

   The digest value of Attr nodes are defined similarly to PI nodes,
   except that we need a separator between the expanded attribute name
   and the attribute value. The '0x0000' value in UTF-16 is allowed
   nowhere in an XML document, so it can serve as an unambiguous
   separator. The expanded name must be used as the attribute name
   because it may be qualified. Note that if the attribute is a
   namespace declaration (either the attribute name is "xmlns" or its
   prefix is "xmlns"), the digest value is undefined and the getDigest()
   method should return null.

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






H. Maruyama, K. Tamura, & N. Uramoto                            [Page 8]


INTERNET-DRAFT                  DOMHASH                    February 1999


     public byte[] getDigest(String digestAlgorithm) {
         if (getNodeName().equals("xmlns")
                 || getNodeName().startsWith("xmlns:"))
             return null;
         MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
         md.update((byte)((Node.ATTRIBUTE_NODE >> 24) & 0xff));
         md.update((byte)((Node.ATTRIBUTE_NODE >> 16) & 0xff));
         md.update((byte)((Node.ATTRIBUTE_NODE >> 8) & 0xff));
         md.update((byte)(Node.ATTRIBUTE_NODE & 0xff));
         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 consist of other
   nodes recursively. Hash values of these component nodes are used to
   calculate the node's digest so that we can save computation when the
   structure is partially changed.

   First, all the attributes except for namespace declarations must be
   collected. This list is sorted by the expanded attribute names. The
   sorting is done in ascending order in terms of the UTF-16 encoded
   expanded attribute names, using the string comparison operator
   defined as String#compareTo() in Java. The semantics of this sorting
   operation should be clear.

   - Node.ELEMENT_NODE (1) in 32 bit network-byte-ordered integer
   - Expanded element name in UTF-16 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 by String#compareTo() for 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)








H. Maruyama, K. Tamura, & N. Uramoto                            [Page 9]


INTERNET-DRAFT                  DOMHASH                    February 1999


     public byte[] getDigest(String digestAlgorithm) {
         MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
         ByteArrayOutputStream baos = new ByteArrayOutputStream();
         DataOutputStream dos = new DataOutputStream(baos);
         dos.writeInt(Node.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 by String#compareTo() on 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();
     }



3. Suggested API

   We propose to add a new method to the Node interface as shown below.
   The getDigest() method takes one string as its parameter that
   specifies the digest algorithm. We assume that at least two
   algorithms, "MD5" and "SHA-1", must be implemented for any DOM
   processor to be compliant with DOMHASH.









H. Maruyama, K. Tamura, & N. Uramoto                           [Page 10]


INTERNET-DRAFT                  DOMHASH                    February 1999


      public interface Node {
          // NodeType
          public static final short     ELEMENT_NODE         = 1;
          public static final short     ATTRIBUTE_NODE       = 2;
          public static final short     TEXT_NODE            = 3;
          public static final short     CDATA_SECTION_NODE   = 4;
          public static final short     ENTITY_REFERENCE_NODE = 5;
          public static final short     ENTITY_NODE          = 6;
          public static final short     PROCESSING_INSTRUCTION_NODE = 7;
          public static final short     COMMENT_NODE         = 8;
          public static final short     DOCUMENT_NODE        = 9;
          public static final short     DOCUMENT_TYPE_NODE   = 10;
          public static final short     DOCUMENT_FRAGMENT_NODE = 11;
          public static final short     NOTATION_NODE        = 12;
          public String             getNodeName();
          public String             getNodeValue();
          public void               setNodeValue(String arg);
          public short              getNodeType();
          public Node               getParentNode();
          public NodeList           getChildNodes();
          public Node               getFirstChild();
          public Node               getLastChild();
          public Node               getPreviousSibling();
          public Node               getNextSibling();
          public NamedNodeMap       getAttributes();
          public Document           getOwnerDocument();
          public Node               insertBefore(Node newChild,
                                                 Node refChild)
                                                 throws DOMException;
          public Node               replaceChild(Node newChild,
                                                 Node oldChild)
                                                 throws DOMException;
          public Node               removeChild(Node oldChild)
                                                throws DOMException;
          public Node               appendChild(Node newChild)
                                                throws DOMException;
          public boolean            hasChildNodes();
          public Node               cloneNode(boolean deep);
          public byte[]             getDigest(String digestAlgorithm);
       };



4. Discussion

   The definition described above can be efficiently implemented with
   any XML processor that is conformant to either DOM and SAX
   specification.  Reference implementations are available on request.




H. Maruyama, K. Tamura, & N. Uramoto                           [Page 11]


INTERNET-DRAFT                  DOMHASH                    February 1999


5. Security Considerations

   DOMHASH is expected to be used as the basis for digital signature
   [DSG] and other security and integrity uses.  It's appropriateness
   for such uses depends on the security of the hash algorithm used and
   inclusion of the fundamental characteristics it is desired to check
   in parts of the DOM model incorporated in the digest by DOMHASH.













































H. Maruyama, K. Tamura, & N. Uramoto                           [Page 12]


INTERNET-DRAFT                  DOMHASH                    February 1999


References

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

   [DSG] - Richard D Brown, "Digital Signatures for XML",
   http://www.ietf.org/internet-drafts/draft-brown-xml-dsig-00.txt.

   [MD5] - RFC 1321 - R. Rivest, "The MD5 Message-Digest Algorithm",
   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.

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

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





























H. Maruyama, K. Tamura, & N. Uramoto                           [Page 13]


INTERNET-DRAFT                  DOMHASH                    February 1999


Author's Address

   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



Expiration and File Name

   This draft expires August 1999.

   Its file name is draft-hiroshi-dom-hash-01.txt.































H. Maruyama, K. Tamura, & N. Uramoto                           [Page 14]