Subject: Re: msg-id

From: John Stanley <[email-masked]>
Date: Tue, 7 Dec 2004 17:36:56 -0800 (PST)

Seth Breidbart <sethb@xxxxxxxxx>:

>>> To whom are you attributing that error?
>> To everyone who says that "once per thousand years" is good enough.

>Then you're wrong.   I think one collision, total, on average every
>thousand years is good enough. 

The "error" is not whether you think that is "good enough", but on the
meaning of "once per thousand years". It does not mean it cannot happen 
tomorrow or the day after. It does not mean it will only happen in
one thousand years.

> I also understand probability theory quite well.

Then you would know that "once per thousand years" is 1) a pretty 
meaningless statistic and 2) not in any way an implementation of "MUST 
NOT".

>> A breakdown in a piece of hardware is different than a programmed, known
>> flaw.

>They both cause the same violation of the same MUST.

No, they don't, and even were that true, they are still very different 
things. The existance of one does not mean the other is unimportant.

>> Really? What is special about "finishing editing the proto-article" that
>> protects the computer from failure until hitting "send"?

>Nothing.

Oh. Then the chances of it breaking are just as good then as at any other 
time. In fact, hitting "send" is likely to activate the disk, which is a 
time when failures would be more likely. And since computers fail more 
often than "once per thousand years", on average ...

>So you'll have to make the effort of asking them, instead of
>expecting the information to be thrust upon you.

And THEY will know the answer because? The magic information fairy tells 
them?

>>> You don't have to consider that a problem.
>> There are lots of things I don't HAVE to consider a problem that are still
>> problems.

>You are welcome to worry about them as much as you want to.  I choose
>not to bother.

You are choosing to bother by participating in this discussion. Make up 
your mind.

---

From: Seth Breidbart <[email-masked]>
Date: Tue, 7 Dec 2004 20:49:17 -0500 (EST)

> meaning of "once per thousand years".

I fully understand the meaning of "once per thousand years".  I also
think it's good enough.  Hence, you are attributing the error to me,
and I'm not making it.  Therefore you're wrong.

> It does not mean it cannot happen tomorrow or the day after. It does
> not mean it will only happen in one thousand years.

I understand that.  It means it will happen, on average, one thousand
time in one million years.

> meaningless statistic

It has a clear meaning (providing the details are spelled out: how
many users posting how often, etc.)

> and 2) not in any way an implementation of "MUST NOT".

It's a flawed implementation.  So is any other, since whatever method
you use might generate a Message-ID that was previously used by a
previous owner of the domain (or might sometime in the future be used
by a subsequent owner).

> No, they don't,

They both cause a non-unique Message-ID.  That's the same violation of
the same MUST.

> and even were that true, they are still very different things.

I didn't say they were the same thing, I said they had the same
effect.

> often than "once per thousand years", on average ...

Yes, and spend what fraction of their time between my finishing the
proto-article and my hitting send?

> And THEY will know the answer because? The magic information fairy tells 

You don't think ISPs will know what software they're running?  Maybe
you should avoid such ISPs.  I do.

> You are choosing to bother by participating in this discussion. Make up 

I am not at all bothered by the expected once in the next thousand
years Message-ID collision.

Seth

---

From: Thorfinn <[email-masked]>
Date: Wed, 8 Dec 2004 13:21:37 +1100

On Tue 07 Dec 2004 at 05:36:56PM -0800, in <[email-masked]>,
> tomorrow or the day after. It does not mean it will only happen in

You seem to not get it.

> Then you would know that "once per thousand years" is 1) a pretty 

Err, no, it's not meaningless.  It means that it's an extremely low
probability event.  Sufficiently low in probability, that the likelihood
of other untoward things happening (like the computer crashing between
pressing send and the server getting it, or the likelihood that relying
on the FQDN part being unique will generate a collision) is *much*
higher in importance.

> and 2) not in any way an implementation of "MUST 

"The computer crashes" isn't an implementation of MUST NOT, either.

> things. The existance of one does not mean the other is unimportant.

It's a question of scale.  Do you want to worry about the fact that it
is possible that your component atoms could suddenly decide to separate
and fly in all different directions?  That could happen you know.  It's
extremely low probability... for some reason, most of us choose to
ignore it.

Or, how about the probability that a meteor will land on your head?  Or
a plane?  A car crashing into you as you walk down the street?

A "MUST" isn't some magical stick to be implemented in airy fairy theory
land.  It butts up against the reality that is practice.  And in
practice, hardly anyone is going to give a shit about once in every
thousand years events (hell - I should know - I got an MD5 collision on
two randomly generated numbers once on an automated MD5 module install
test, shrugged and tried again), when there are far more critical issues
affecting the problem.

> often than "once per thousand years", on average ...

Then there are rather more important issues than worrying about once per
thousand years events.

> And THEY will know the answer because? The magic information fairy tells 

Well, presumably, if they're running the software that generates the
Message-ID, they can find out, either by asking the vendor or inspecting
the source code.

Later,

  Thorf

-- 
<a href="http://tertius.net.au/~thorfinn/">[email-masked]</a>
"Rabbit or gerbil, rabbit or gerbil?"
    -- Benno!jeamland.net

---

From: "Charles Lindsey" <[email-masked]>
Date: Thu, 9 Dec 2004 12:17:41 GMT

>test, shrugged and tried again), when there are far more critical issues

Now that is rather interesting, because I have never seen a report of a
genuine MD5 collisionw.

AIUI, there are suspicions that the MD5 hashing scheme is not as secure as
it was once thought to be. And apparently the nature of the problem is
that, given a truly random set of strings to be hashed, they do not map
uniformly on to the 128-bit space of hash values. I.e. there exist hash
values that are more likely to be mapped into than others.

Which probably explains how you came to observe an event that, on pure
probability grounds, was otherwise expected to occur about once before the
heat-death of the universe.

-- 
Charles H. Lindsey ---------At Home, doing my own thing------------------------
Tel: +44 161 436 6131 Fax: +44 161 436 6133   Web: http://www.cs.man.ac.uk/~chl
Email: [email-masked]      Snail: 5 Clerewood Ave, CHEADLE, SK8 3JU, U.K.
PGP: 2C15F1A9      Fingerprint: 73 6D C2 51 93 A0 01 E7 65 E8 64 7E 14 A4 AB A5

---

From: "Charles Lindsey" <[email-masked]>
Date: Thu, 9 Dec 2004 15:30:16 GMT

>things. The existance of one does not mean the other is unimportant.

Technically speaking, using a sufficiently large random number as a means
of constructing message-ids is in violation of that MUST, and that MUST is
still there (in RFC 2822 actually).

But in practice is is perfectly good enough that we do not really need to
care about it. And in fact our draft is currently totally silent on this
issue, relying on the wording in RCC 2822 (except that USEFOR now adds
that uniqueness now applies over both Email and Netnews).

I see no point in writing anything different in our drafts, but if I were
writing an informational document explaining ways of generating
message-ids, I would probably say that random generation was a good enough
approximation to unique for all practical purposes.

---

From: Thorfinn <[email-masked]>
Date: Fri, 10 Dec 2004 09:11:21 +1100

On Thu 09 Dec 2004 at 12:17:41PM +0000, in <[email-masked]>,
> Now that is rather interesting, because I have never seen a report of a

Hrm.  Should I be reporting it somewhere in particular?  I definitely
saw it, but obviously, it was unrepeatable when I tried again.

The module in question was the Perl Digest::MD5 module, and it was in
its automated test that grabs a random chunk out of /dev/random twice
and compares them that I got a collision...  Now, it's *possible* that

> values that are more likely to be mapped into than others.

*nodnod* Quite possible.

> heat-death of the universe.

Yeps.  There are also plenty other factors that could explain it such as
bugs in a number of possible different places.  And that's the point
with Message-ID generation... we're a whole lot more likely to get
duplicate Message-ID generation due to ordinary software bugs than
anything else.

Meep,

 Thorf

-- 
<a href="http://tertius.net.au/~thorfinn/">[email-masked]</a>
"Sorry I'm late, I was held up by that fuckwit Harradine."
    -- unnamed Liberal MP, to morgan(vurt.net

---

From: Richard Clayton <[email-masked]>
Date: Fri, 10 Dec 2004 00:28:17 +0000

In message <[email-masked]>, Charles Lindsey
<[email-masked]> writes

>Now that is rather interesting, because I have never seen a report of a

One was reported this August in the rump session of Crypto 2004

        http://www.tcs.hut.fi/~mjos/md5/

>it was once thought to be.

AIUI, there's still no known way of creating a clash with a previously
provided hash value, but it seems that the Chinese researchers can
provide collisions (ie they provide both of the pair) pretty much at
will. AFAIK, their methods are still not published, but study of what
they hash shows the sort of properties (minor changes to a few high
order bits) that they are exploiting.

SHA-0 also has collisions known, but despite rumours nothing firm is
known against SHA-1.  No-one from the trade has been recommending MD5
since the results found in the mid 1990s (and its output length is a
little bit too short anyway), but if you are using it there's still no
real reason to panic -- you should just be making plans to move away, at
present I would suggest to SHA-1, when it is convenient to do so.

- -- 
richard @ highwayman . com                       "Nothing seems the same
                          Still you never see the change from day to day
                                And no-one notices the customs slip away"