Subject: RE: Take 2: References/In-Reply-To replacement text

From: "Larry Osterman (Exchange)" <[email-masked]>
Date: Wed, 26 May 1999 10:21:11 -0700

Comments in-line below....

Larry Osterman
Sent from larryo-laptop.dns.microsoft.com running NT5 and Outlook 2000
and Exchange Server 5.5.  Please notify the sender of any difficulties

> -----Original Message-----
> From: Robert Elz [mailto:[email-masked]]
> Sent: Wednesday, May 26, 1999 6:08 AM
> To: Larry Osterman (Exchange)
> Cc: DRUMS
> Subject: Re: Take 2: References/In-Reply-To replacement text 
> 
> 
>   | The reason this is just recommended is that there are 
> message-id generation
>   | algorithms that guarantee universal uniqueness regardless 
> of the rhs.
> 
> Surely this could only work if everyone is using a compatible 
> algorithm.
> That's just fine within one domain, but surely you aren't attempting
> to tell me that I couldn't generate the same message-id LHS using some
> completely different method?

Of course someone could generate the same message-id LHS using some
different method, but that can happen with ANY message-id generation
algorithm.  There is no more probability that they can come up with the
unique 176 bit (44 character) string that comprises the exchange message ID
than they can come up with someone elses message-id. 
> 
>   | For
>   | example, Exchange generates the LHS of the message-id 
> based on the 128 bit
>   | UUID of the message store concatenated with the 48bit ID 
> of the message -
>   | this combination is guaranteed to be unique, even if the 
> RHS isn't.
> 
> I don't believe that for a second.   How is it guaranteed to 
> be unique?
> What's to stop me having a message-store with the same uuid 
> and a message
> with the same 48bit id (not using exchange, and hence not 
> using whatever
> algorithm it uses to get the what seem to be unique numbers) and then
> encoding it the same way (and adding "@TOTO" to the end - 
> which I assume
> here is done just to meet the syntax requirements).

For a discussion of how UUIDs are guaranteed to be unique, please look at:
	
http://search.ietf.org/internet-drafts/draft-leach-uuids-guids-01.txt
which describes the algorithms for generating UUIDs in detail.  Of course
someone else could purposely forge a UUID to match one generated by another
computer, but the only way to guarantee absolute uniqueness is to mandate
one and only one ID generation algorithm.  And none of the existing
algorithms can be guaranteed to be accurate across all machines across the
entire world.  The best you can do is to put enough complexity in your
algorithm to hope that things are unique "enough". 

> 
>   | For
>   | compatibility reasons, Exchange uses the DNS name of the 
> server as retrieved
>   | from gethostbyname() as the rhs,
> 
> That's not just a compatability reason, even if you think it 
> is - doing that
> means you can guarantee uniqueness, because within that host 
> your message
> generation algorithm is fixed (or can be arranged to be so), 
> and you can
> arrange it any way that you like which generates locally 
> unique numbers.
> if you desire, you could even be having them globally unique 
> amongst the
> universe of all exchange users in the world - but to claim 
> this is globally
> unique amongst all the other (unspecified) algorithms that 
> could exist is
> a bit hard for me to swallow.

Sure, but the reality is that this statement is true of ALL ID generation
algorithms, not just the exchange.  For example, the current ID generation
algorithm requires that every machine that generate IDs be part of the
global DNS, which simply isn't the case - the DNS inside Microsoft is
totally isolated from the rest of the world, and there is simply no reason
to believe that the computer names within Microsoft are unique across the
internet, they are just guaranteed to be unique within  our corporate
network.  Even if we used the recommended algorithm, there is nothing that
prevents two isolated networks from having a servers named
"server.corporate.net" and generating message-id's that conflict.

I realize that I'm starting to sound like Dan, but.....  You have to
understand that RFC822-style messages are used in more places than just on
the internet - they are also used on internal corporate networks that don't
guarantee global uniqueness of names.  Thus there is NO algorithm for
message-id generation that can be specified that GUARANTEES 100% uniqueness
(in the absense of some form of global naming system), the best you can do
is a good faith attempt to generate uniqueness.

> 
> I understood that.   I still fail to see how any algorithm 
> can guarantee 
> uniqueness in the face of other undefined algorithms using 
> the same space
> of identifiers, but with totally different generation 
> methods.   Make it
> long enough and the chances of a collision are small, but non-zero.

This is my point exactly - there is NO algorithm that can guarantee
uniqueness.  Even if the algorithm is mandated to be the SAME on all
machines, it STILL does not guarantee uniqueness.

> I could be
> generating "@TOTO" too (I used to watch the lone ranger as a 
> kid...) and

Umm... That was "Tonto".  Toto was Dorothy Gale's dog (In general, all the
servers in our dogfood lab are named after dogs - we have rin-tin-tin, dino,
sierradog (the dog of one of our PM's), lassie, etc).

---

From: Robert Elz <[email-masked]>
Date: Thu, 27 May 1999 19:55:28 +1000

Date:        Wed, 26 May 1999 10:21:11 -0700
    From:        "Larry Osterman (Exchange)" <[email-masked]>
    Message-ID:  <01D6C7224936D211BA450000F805D5380542164A@TOTO>

  | Of course someone could generate the same message-id LHS using some
  | different method, but that can happen with ANY message-id generation
  | algorithm.

Exactly.   This is why the domain part of the message-id is important.
In any one (specific) domain (ie: not including sub-domains) the idea is
that the generation algroithm to be used is defined, and arranged in such
a way that the local part can be guaranteed to be unique.

In different domains the generation methods can be totally different, and
hence it is totally irrelevant if the local parts generated there just happen
to clash because of different generation algorithms.

  | For a discussion of how UUIDs are guaranteed to be unique,

This is irrelevant, you're totally missing the point.   I have no doubt but
that algorithms can be defined such that unique identifiers can be created
(with sufficient probability of uniqueness).    If 822 (822bis) message-id's
were to define such a generation algorithm, then perhaps the need for the
RHS would be unnecessary, as you claimed in yoru first message.   But there's
no way that is going to happen any time soon (despite the drafts that Simon
pointed out which show ways that can be used to generate Message-Ids).

Without such a common algorithm, there needs to be an "algorithm identifier"
which allows the particular unique local part algorithm to be specified.
Rather than inventing a new namespace for that, what was done (and I think
very sensibly) was to instead allow specification of the name of the entity
which generated the message-id (and which then guarantees the uniqueness).

  | And none of the existing
  | algorithms can be guaranteed to be accurate across all machines across the
  | entire world.  The best you can do is to put enough complexity in your
  | algorithm to hope that things are unique "enough".

No, you can do better than that, you can include an extra reference which
specifies the scope in which the particular generation algorithm being used
expects to guarantee uniqueness.

Note here that I am not at all concerned with people deliberately faking
message-id's such that they duplicate others.   Unless we were to go to
some kind of authenticated mechanism, there's nothing we can possibly do
to prevent that.   But that's not the issue here.   The point is how
systems that are attempting to co-operate with each other should operate
such as to achieve the common aim.

If we specified the uuid + message number algorithm, and everyone used
that, that would certainly be one way.   But there's simply no way that
is going to happen.   I'm not sure this is worth discussing any more, as
there is no serious proposal to delete the domain name part (or to make it
optional), but I would like to attempt to convince you that it is important,
so that you can make sure that your (widespread) product interoperates
with the rest of the world as best it can, rather than just by chance.

  | I realize that I'm starting to sound like Dan, but.....  You have to
  | understand that RFC822-style messages are used in more places than just on
  | the internet - they are also used on internal corporate networks that don't
  | guarantee global uniqueness of names.

Sure, nothing in the message-id syntax requires that the hostname of the
machine generating the I-D be the one that is used.   What is needed is
a domain name that guarantees the uniqueness of the message-id.  In your
particular case, if you were to add "@exchange.microsoft.com" (or something
similar like that) as the RHS of all your uuid message-ID's, that would be
just fine.   Microsoft Exchange is generating message-ids which will be
unique among all users of that software, everywhere (as I read what you
said in the previous message).  That domain name (perhaps better if it is
a domain used for nothing else, though that isn't required) is the one
guaranteeing the uniqueness of your particular identifiers.  The domain
name in the mesage-ID doesn't have to be in any way related to the system
upon which the message-id is generated (my @munnari.oz.au message-id's aren't
actually being generated on munnari.oz.au ...)

On the same system, if I am using exchange, netscape, and eudora (and
perhaps several others) to generate messages, I could be getting message-ids
with several quite different RHS parts - each identifying different
generation algorithms.  Some of those might be, as yours, using an algorithm
which makes unique LHS values across all users of the product, others might
only be expected to be unique on the particular system generating the I-D,
and as such require some more specific RHS to get global uniqueness.

  | This is my point exactly - there is NO algorithm that can guarantee
  | uniqueness.  Even if the algorithm is mandated to be the SAME on all
  | machines, it STILL does not guarantee uniqueness.

Algorithms exist, even trivial ones, they're just not practical.
One could easily imagine a server somewhere which simply handed out
sequential numbers, from 1 upwards, of unlimited size.   That server
could be contacted for a unique number for each message you want to
send - lose the response, no big deal, just ask for another, and the
lost one gets skipped (numbers are cheap).   If you're going to be
off line for a while (or are supplying a product to someone who may
never be connected), just ask for a few million numbers from the
server, and install them as available for use (when they're used
up, a new installation with a new number range would be needed).

Aside from intentional duplication, that algorithm would work - but
there's no way at all it would be practical, and actually function.

  | Umm... That was "Tonto".

Oops - you're right of course.   My only excuse is that it has been a LONG
time...

kre