Re: Identifying revoked certificates

[Jon Callas <[e-mail]>]

At 3:46 PM -0400 9/6/01, David Shaw wrote:

>Is it worth adding the timestamp from the original signature to help
>find it without having to look at the (larger) hashes?  On a uid with
>many signatures, this could speed things up.  Once found, of course,
>the hash could then be checked for confirmation.
>

My comments:

* The amount of time need to compare bytes is negligible compared to the
time needed to compare signatures. Byte compares are in the nanosecond to
microsecond range, and doing a signature check is in milliseconds. In
microsecond-land, a millisecond is a coffee break. In nanosecond-land, a
millisecond is an American (but not European) vacation.

* It's actually more likely to slow things down. Remember that hashes are
completely uncorrelated. So the first time I compare a byte, there's a
1/256 chance that they match, yet this is not the hash I'm looking for. For
ones that match the first byte, there's a 1/256 chance of a collision on
the second byte, and so on. In an optimal implementation that compares
bus-width quantities, (like 32, 64, or 128 bits), I'll almost never have a
collision beyond the first compare. Adding in the timestamp just gives me
more things to compare, things it is easier to have collisions on, and
therefore slows the process down.

* Having said all that, there's no good reason *not* to put the timestamp
in. The whole reason for having this is as a disambiguator, and why have a
disambiguator that isn't pretty darned specific, eh?


Now then, a question for implementors: If this gets put in, would you
implement it? "Yes, but not right away" is a fine answer, as are "Yes" and
"No."

	Jon