One document matched: draft-hiroshi-dom-hash-00.txt
Network Working Group Hiroshi Maruyama
INTERNET-DRAFT Kent Tamura
January 1999 Naohiko Uramoto
Expires: July 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-00.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. 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 January 1999
Abstract
This document is intended to contribute discussions how digest (hash)
values should be defined for general DOM structures. See Document
Object Model (DOM) Level 1 Specification Version 1.0 for the
specifications of DOM 1.0.
H. Maruyama, K. Tamura, & N. Uramoto [Page 2]
INTERNET-DRAFT DOMHASH January 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. Comment Nodes.......................................8
2.3.3. ProcessingInstruction Nodes.........................8
2.3.4. Attr Nodes..........................................9
2.3.5. Element Nodes.......................................9
3. Suggested API..........................................11
4. Discussion.............................................12
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 January 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 January 1999
<?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 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 five node types that are used for representing a DOM
document structure:
1. Element
2. Attr
3. ProcessingInstruction
4. Comment
5. Text (including the subtype CDATASection)
Note: It is not simple to define hash values for DTD. At this moment,
we do not define hash values for the Document, DocumentType, and so
on, to avoid this complication. Future release will cover this point.
Nodes with the node type EntityReference are assumed to be expanded
before digest calculation.
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
H. Maruyama, K. Tamura, & N. Uramoto [Page 5]
INTERNET-DRAFT DOMHASH January 1999
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
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>
:
</order>
</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()
H. Maruyama, K. Tamura, & N. Uramoto [Page 6]
INTERNET-DRAFT DOMHASH January 1999
method (which returns the expanded name as defined above) is defined
in both Element and Attr interfaces of DOM.
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 (4 bytes)
- 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
H. Maruyama, K. Tamura, & N. Uramoto [Page 7]
INTERNET-DRAFT DOMHASH January 1999
built-in packages of JDK 1.1.
2.3.2. Comment Nodes
Comment nodes are similar to Text nodes except for the header.
- Node.COMMENT_NODE (8) in 32 bit network-byte-ordered integer (4
bytes)
- Comment data in UTF-16 stream (variable length)
public byte[] getDigest(String digestAlgorithm) {
MessageDigest md = MessageDigest.getInstance(digestAlgorithm);
md.update((byte)((Node.COMMENT_NODE >> 24) & 0xff));
md.update((byte)((Node.COMMENT_NODE >> 16) & 0xff));
md.update((byte)((Node.COMMENT_NODE >> 8) & 0xff));
md.update((byte)(Node.COMMENT_NODE & 0xff));
md.update(getData().getBytes("UnicodeBigUnmarked"));
return md.digest();
}
2.3.3. ProcessingInstruction Nodes
A ProcessingIinstruction (PI) node has two components: the target and
the data. Accordingly, the hash is computed on the concatenation of
both. Note that the data contains the leading space character so
there is no ambiguity even if there is no separator between the
target and the data.
- Node.PROCESSING_INSTRUCTION_NODE (7) in 32 bit network-byte-ordered
integer (4 bytes)
- PI target and 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(getData().getBytes("UnicodeBigUnmarked"));
return md.digest();
}
H. Maruyama, K. Tamura, & N. Uramoto [Page 8]
INTERNET-DRAFT DOMHASH January 1999
2.3.4. 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 (4
bytes)
- Expanded attribute name in UTF-16 stream (variable length)
- 0x00 0x00 (2 bytes)
- Attribute value in UTF-16 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)((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.5. 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 (no "ties" are possible because of the
unique attribute name constraint).
H. Maruyama, K. Tamura, & N. Uramoto [Page 9]
INTERNET-DRAFT DOMHASH January 1999
- Node.ELEMENT_NODE (1) in 32 bit network-byte-ordered integer (4
bytes)
- Expanded element name in UTF-16 stream (variable length)
- 0x00 0x00 (2 bytes)
- A number of non-namespace-declaration attributes in 32 bit
network-byte-ordered unsigned integer (4 bytes)
- Sequence of digest values of non-namespace-declaration attributes,
sorted by String#compareTo() for attribute names (variable length)
- A number of child elements in 32bit network-byte-ordered unsigned
integer (4 bytes)
- Sequence of digest values of each child elements (variable length)
(A sequence of child texts is merged to one text. A zero-length text
is 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(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 and no 0-length Text.
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();
}
H. Maruyama, K. Tamura, & N. Uramoto [Page 10]
INTERNET-DRAFT DOMHASH January 1999
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.
typedef sequence<octet> bytearray;
interface Node {
// NodeType
const unsigned short ELEMENT_NODE = 1;
const unsigned short ATTRIBUTE_NODE = 2;
const unsigned short TEXT_NODE = 3;
const unsigned short CDATA_SECTION_NODE = 4;
const unsigned short ENTITY_REFERENCE_NODE = 5;
const unsigned short ENTITY_NODE = 6;
const unsigned short PROCESSING_INSTRUCTION_NODE = 7;
const unsigned short COMMENT_NODE = 8;
const unsigned short DOCUMENT_NODE = 9;
const unsigned short DOCUMENT_TYPE_NODE = 10;
const unsigned short DOCUMENT_FRAGMENT_NODE = 11;
const unsigned short NOTATION_NODE = 12;
readonly attribute DOMString nodeName;
attribute DOMString nodeValue;
// raises(DOMException) on setting
// raises(DOMException) on retrieval
readonly attribute unsigned short nodeType;
readonly attribute Node parentNode;
readonly attribute NodeList childNodes;
readonly attribute Node firstChild;
readonly attribute Node lastChild;
readonly attribute Node previousSibling;
readonly attribute Node nextSibling;
readonly attribute NamedNodeMap attributes;
readonly attribute Document ownerDocument;
Node insertBefore(in Node newChild,
in Node refChild)
raises(DOMException);
Node replaceChild(in Node newChild,
in Node oldChild)
raises(DOMException);
Node removeChild(in Node oldChild)
raises(DOMException);
Node appendChild(in Node newChild)
raises(DOMException);
boolean hasChildNodes();
H. Maruyama, K. Tamura, & N. Uramoto [Page 11]
INTERNET-DRAFT DOMHASH January 1999
Node cloneNode(in boolean deep);
bytearray getDigest(in DOMString digestAlgorithm);
};
4. Discussion
The definition described above can be efficiently implemented. XML
Parser for Java has a reference implementation with the source code.
5. Security Considerations
DOMHASH is expected to be used as the basis for digital signature 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 January 1999
References
[DOM] - "Document Object Model (DOM), Level 1 Specification", October
1998, http://www.w3.org/TR/REC-DOM-Level-1/
[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
[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 January 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 July 1999.
Its file name is draft-hiroshi-dom-hash-00.txt.
H. Maruyama, K. Tamura, & N. Uramoto [Page 14]
| PAFTECH AB 2003-2026 | 2026-04-24 07:35:01 |