From: Jamie Zawinski (jwz@netscape.com)
Date: Wed Jul 01 1998 - 23:38:54 CDT
C Matthew Curtin wrote:
>
> o There is some room for improvement in jwz's proposal for uniqueness
> in the "local-part". Specifically, the use of random numbers in
> the local-part is somewhat concerning. This is because, as someone
> (Greg?) pointed out, a *really* good RNG will have just as much
> probability in generating the same random value twice in a row as
> it will in generating any two values.
Yes, of course -- the probabilities will be equal, and the probabilities
will be *very small*.
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.
You can argue about how much entropy a particular PRNG includes, and
how many pseudo-random bits you have to suck out of it to drop the
probability of a duplicate down into the cosmic-ray range, but you
really just can't argue that using random numbers is not effective
*because they are random*. At the level of probability we're talking
about here, *all* computed results are random, because we live in an
analog world.
> o I am of the opinion that in general, it's sensible to use
> combinations of values (i.e., PIDs, timestamps, and other stuff)
> for the local-part. It doesn't seem difficult to push the
> probability of collision out of the range of concern, practically
> speaking.
Yes, that's fine. If you've got some other way of generating a
non-collibable local-part for a given domain-part, you might as well
use that. The words I used in the draft were:
An alternative for generating the distinguishing number, on
systems where the process ID isn't available, or in the case
where the local host's FQDN isn't known, is to generate a large
random number from a high-quality, well-seeded pseudorandom
number generator.
> What I would like to do is this:
> o Generalize the next rev of the Message-ID draft to a formula that
> argues essentially the same point: it's possible to generate
> Message-IDs on the client side that are unique enough for practical
> use.
If you think you can find better words than the ones I used, I encourage
you to do so; but I don't see how that's a generalization, because
that's exactly what I was trying to say.
> At some point, we have to accept some level of risk of collision.
> We accept risks in other areas, and eventually we've got to figure
> out whether it's really important for Message-ID collision to
> happen less frequently than Jimmy Hoffa sightings.
There is no *practical* risk of collision if you use your RNG properly.
We accept the risk that our computers will not mis-compute, by running
computers that are not triply-redundant and tempest-hardened. (Not that
even that would be a guarentee.)
> o Including brief discusions of a number of things that can be used
> for the local-part, such as hashes, PRNGs, etc.
>
> I realize that Greg thinks the use of hashes are even worse than
> PRNGs, but I can argue that a good hash function is darn unlikely
> to generate exactly the same thing on two different messages within
> a domain, especially at precisely the same time, in the same
> process, etc., such that the only way to tell one message from the
> other is to rely completely on the hash in the local-part.
>
> Does this sound generally reasonable?
Yes, that sounds fine to me.
Perhaps it would passify Greg if someone were to actually come up with
some examples that worked through the math and came up with actual
probibilities of collision per some unit time. (I know that I've seen
entropy numbers for some popular PRNGs at some point; I guess the
Cypherpunks archive would be a good place to start looking, if you
thought that was a worthwhile effort.)
-- Jamie Zawinski http://people.netscape.com/jwz/ about:jwz