Subject: Message-ID draft, comments please

From: Matt Curtin <[email-masked]>
Date: Mon, 7 Jun 1999 18:11:45 -0400 (EDT)

There are a number of issues here that aren't quite resolved and I
haven't been reading the list for a few days.  I'll try to get caught
up with everything this week.

I'd like to make sure that the draft reflects comments from folks here 
(specifically, the Message-ID thread) before submitting this to IETF.
Note that this was originally submitted through USEFOR, but this is
very low on the priority list over there, so I expect we'll have to
make it a DRUMS product if it's going to see the light of day this
year.

(I think that the weakest part is in the specification of the FQDN
necessity; it would be fair to note that some organizations don't want 
internal DNS to bleed outside and that a vendor's creation of a zone
inside of their namespace for Message-IDs would be allowed, provided
that they have some way to prevent collision, as is the case with
Microsoft's scheme.  Would a stats person please check Appendix A?  I
believe I'm using the correct distribution and whatnot, but I'm not
sure.) 

-- 
Matt Curtin [email-masked] http://www.interhack.net/people/cmcurtin/

Internet Draft                                              Matt Curtin
will be draft-ietf-usefor-message-id-02.txt   The Ohio State University
Category-to-be: Best Current Practice                    Jamie Zawinski
                                          Netscape Communications (Ret)

                                                              June 1999
                                    Expires: Six Months from above date

	      Recommendations for generating Message IDs

			 Status of this Memo

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
documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months
and may 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 other than as ``work in progress.''

To view the entire list of current Internet-Drafts, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe),
ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim),
ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast).

			       Abstract

This document provides recommendations on how to generate globally
unique Message IDs in client software.

Table of Contents

1. Introduction
2. Message-ID formatting
3. Message-ID generation
3.1 "Domain part"
3.2 "Local part"
3.2.1 Sequence number
3.2.2 Using a pseudorandom number generator
3.2.3 Using a hash
3.3 Bringing it all together
4. Acknowledgments
5. References
6. Authors' addresses
Appendix A: Probability of Message-ID Collision

1. Introduction

Message-ID headers are used to identify Internet messages uniquely.
Having a unique identifier for each message has many benefits,
including ease in the following of threads and intelligent scoring of
messages based on threads to which they belong.

It has been suggested that it is impossible for client software to be
able to generate globally-unique Message-IDs.  We believe this to be
incorrect, and herein to offer suggestions for generating unique
Message-IDs.

2. Message-ID formatting

As defined in [NEWS], a message ID consists of two parts, a local part
and a domain, separated by an at-sign and enclosed in angle brackets:

    message-id = "<" local-part "@" domain ">"

Practically, news message IDs are a restricted subset of mail message
IDs.  In particular, no existing news software copes properly with mail
quoting conventions within the local part, so software generating a
Message-ID would be well-advised to avoid this pitfall.

It is also noted that some buggy software considers message IDs
completely case-insensitive, in violation of the standards.  It is
therefore advised that one not generate IDs such that two IDs so
generated can differ only in character case.

Domain MUST be a reasonable, resolvable fully-qualified domain name
(FQDN).  It is noteworthy that it is not always possible for a host to
determine its FQDN and sometimes site policy dictates that internal
hostnames not be exposed to the public Internet.  In these cases,
Message-ID generators MUST NOT use an unqualified hostname.

3. Message-ID generation

As shown above, the Message-ID is made up of two sections.  We'll
consider each seperately.

3.1. "Domain part"

On many client systems, it is not always possible to get the FQDN of
the local host.  In that situation, a reasonable fallback course of
action would be to use the domain-part of the user's return address.
(Use of an unqualified hostname for the domain part of the Message-ID
header would be foolish, and should never be done.)

Using the domain-part of the user's return address makes the
generation of the "local part" be more important; in particular, it
means that a process ID is probably not sufficient.

3.2. "Local part"

The most popular method of generating local parts is to use the date and
time, plus some way of distinguishing between simultaneous postings on
the same host (e.g. a process number), and encode them in a suitably-
restricted alphabet.

A number of approaches here are possible.  Each has its advantages and
drawbacks.  The importance of the local part's uniqueness increases
with the frequency of messages being generated in a given domain.
Using several of these methods together will produce a Message-ID that
is longer, but significantly less likely to collide.

3.2.1. Sequence number

An older but now less-popular alternative is to use a sequence number,
incremented each time the host generates a new message ID; this is
workable for servers, but requires careful design to cope properly
with simultaneous posting attempts, and is not as robust in the
presence of crashes and other malfunctions.  For client Message-ID
generation, particularly on hosts where the exact FQDN cannot be
obtained, or is subject to change, this might not even be workable.

3.2.2. Using a psuedorandom number generator

One could take 64 bits from a good, well-seeded pseudorandom number
generator [PRNG] in order to increase significantly the uniqueness of
the Message-ID.  The advantage of this method is that it is fast and
effective.  The disadvantage is that not all pseudorandom number
generators are created equal: just because you've generated a 64-bit
random number does not mean that you have actually gotten 64 bits of
randomness.  The quality of your random number generator is important.

As long as the probability of the same number being generated twice is
smaller than the probability that the machine will mis-execute an
instruction, your job is done.

3.2.3. Using a hash

Another approach would be to generate a hash of the message and use
that after the timestamp.  If this is done well, this can also
significantly reduce the opportunity for collision, and will generate
a value that is relatively unique.  Note that, in practice, this is
more difficult than it sounds.  It is recommended that a
cryptographically secure hash function [SHA1, MD5] be used, as
others, such as CRC, are likely to have higher instances of collision.

3.3. Bringing it all together

In summary, our recommended recipe for generating a Message-ID is as
follows:

  1. Start with "<".

  2. Get the current time in the highest resolution to which you have
     access (at least seconds, though most systems will give you
     milliseconds.)  This time value should be one that does not roll
     over: use a value that is measured in some units from some Epoch.

  3. Generate additional data to prevent Message-ID collision on two
     messages processed by the same host at the same clock-tick.
     Suggestions for sources of these additional data are described
     in section 3.2.  We recommend a good 64-bit random number.

  4. For each of the numbers generated in steps 2 and 3, convert the
     numbers to base 36 (using the characters 0-9 and A-Z), and write
     the numbers, with a "." between them.

     (Base36 is recommended in order to reduce the overall length of
     the message ID; economy in message ID length is a good thing,
     given how prevalent they are.)

  5. Append an "@", to end the local-part.
 
  6. Append the FQDN of the local host.  If you don't know the FQDN of
     the local host, append the host name in the return email address
     configured by the user.

  7. Append ">".

4. Acknowledgments

This document is partially derived from an earlier, unrelated draft by
Henry Spencer.  Russ Allbery provided the basis for Appendix A.

5. References

Ref.          Author, title                         IETF status (June 1998)
                                                    ----------------------
---           -------------

[NEWS]        M.R. Horton, R. Adams: "Standard      Non-standard (but still
              for interchange of USENET             widely used as a de-facto
              messages", RFC 1036, December         standard).
              1987.

[SHA1]        National Institute of Standards
	      and Technology (NIST), "Announcement
	      of Weakness in the Secure Hash 
	      Standard", May 1994.  (Update of
	      FIPS 180:  "Secure Hash Standard".)

[MD5]	      R. Rivest: "The MD5 Message-Digest    Informational (but 
	      Algorithm", RFC 1321, April 1992.     (widely used as a
						    de-facto standard).

[PRNG]        D. Eastlake, 3rd, S. Crocker,	    Informational.
	      J. Schiller: "Randomness 
	      Recommendations for Security",
	      RFC 1750, December 1994.

6. Authors' Addresses

Matt Curtin
The Ohio State University
791 Dreese Laboratories
2015 Neil Ave
Columbus OH 43210
+1 614 292 7352
[email-masked]

Jamie Zawinski
Netscape Communications Corporation
501 East Middlefield Road
Mountain View, CA 94043
(650) 937-2620
[email-masked]

Appendix A: Probability of Message-ID Collision

Let's suppose that a given Internet Service Provider has one million
customers who will all have the same hostname on their messages.  Now,
let's suppose that each one of those customers generates one thousand
messages per day.  Assume a timestamp as part of the message ID that
includes the time to the nearest second.  There are 86,400 seconds in
a day, making the probability that a given customer will be sending a
message at a given second about 0.012. There will be, on average,
12,000 customers generating a message ID at the same time to the limit
of accuracy of the clock.

A truly random 64 bit number added to the Message-ID means that the
probability of a collision is incredibly miniscule.  Specifically, the
probability of collosion per per day is:

      (10^9)!        (10^9)!
    -----------  x  ---------
    (24x60x60)!     (2^{64})!
 
As soon as we find a way to calculate that, we'll spell it out.  In
the mean time, it's safe to say it's "very, very tiny", and certainly, 
good enough.

---

From: Brad Knowles <[email-masked]>
Date: Tue, 8 Jun 1999 14:45:01 +0200

> 3.3. Bringing it all together

	[ ... deletia ... ]

>      given how prevalent they are.)

	Given that base64 is a reasonably well-known algorithm (at least, 
in the context of recent MTAs and MUAs that might need to do MIME 
parsing), and that it is a more compact representation than base-36, 
might I suggest that we recommend it instead?

-- 
   These are my opinions -- not to be taken as official Skynet policy
  ____________________________________________________________________
|o| Brad Knowles, <[email-masked]>            Belgacom Skynet NV/SA |o|
|o| Systems Architect, News & FTP Admin      Rue Col. Bourg, 124   |o|
|o| Phone/Fax: +32-2-706.11.11/12.49         B-1140 Brussels       |o|
|o| http://www.skynet.be                     Belgium               |o|
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
  Unix is like a wigwam -- no Gates, no Windows, and an Apache inside.
   Unix is very user-friendly.  It's just picky who its friends are.