Subject: Re: I-D ACTION:draft-ietf-pkix-certstore-http-01.txt

From: [email-masked] (Peter Gutmann)
Date: Fri, 11 Jan 2002 16:38:02 +1300 (NZDT)

Tomas Gustavsson <[email-masked]> writes:

>How much space is saved by only using 128 bits from the SHA1 hash?

The short answer is: It's quite significant (even 128 bits is far larger than
is optimal, but I figured that was the lower bound of what I could get away
with.  64 bits would be better).  The space saving on disk is irrelevant,
what's significant is the space in indices.  The less keys you can fit per
page, the more pages the index consumes, and the worse performance gets.
That's still not the full answer, for that I'd recommend any book on database
design, or the paper I reference in the draft which looks at this in some
detail.

>Is the added chance of collision insignificant when truncating the hash?

Yes.  I doubt there are more than about 2^20 certs in the whole world, let
alone 2^64.

Peter.

---

From: Michael Ströder <[email-masked]>
Date: Fri, 11 Jan 2002 09:51:30 +0100

> design, or the paper I reference in the draft which looks at this in some

Hmm, I think the cert store implementation itself should deal with
these kind of index optimization issues. I vote for just submitting
search values as is and let the certificate store backend do the bit
reducing at the server-side if necessary at all. That makes client
implementations simpler and leaves up decisions about how to deal
with possible collisions to the server-side cert store
implementation.

Peter, as I understand your draft it's only an interface definition.
There shouldn't be e.g. database-specific limits in this draft
because they are dependent on the DB backend used by an
implementation. Only limitations imposed by the protocols used for
the interface (HTTP in this case) should be considered.

BTW: I'm not an DB expert but IMHO index generation with hashes of
appropriate size and collision handling is made internally by DB
servers anyway.

> Yes.  I doubt there are more than about 2^20 certs in the whole world, let

You know this famous sentence about "640kByte on DOS systems is
enough"... ;-)

Ciao, Michael.

---

From: Tomas Gustavsson <[email-masked]>
Date: Sat, 11 Jan 2002 13:30:36 +0100

> with possible collisions to the server-side cert store

I would agree with this. It simplifies things to use 'real' values and let the backend/middleware do the optimization.

---

From: Michael Ströder <[email-masked]>
Date: Sun, 13 Jan 2002 14:36:47 +0100

Tomas Gustavsson wrote:
> I would agree with this. It simplifies things to use 'real'
> values and let the backend/middleware do the optimization.

While we're at it: It could also be useful to simply use a string
hex-encoding of e.g. SHA-1 fingerprint as search value instead
base64-encoding the binary SHA-1 value. I'd also like to suggest
that a cert store implementation simply strips colons or spaces used
as hex-byte separator to determine the search value. This would
enable the cert store to search for values which the user can
cut&paste from another software's output. (Off course the search
value is assumed to be URL-encoded as already stated in the draft.)

Example of typically used representations of SHA-1 fingerprint used
as search value treated as equal:

C1:50:FF:EF:93:5A:FA:8C:15:49:AE:74:C1:A0:8E:FA:CC:10:99:1F

C150 FFEF 935A FA8C 1549 AE74 C1A0 8EFA CC10 991F

C150FFEF935AFA8C1549AE74C1A08EFACC10991F

c150ffef935afa8c1549ae74c1a08efacc10991f

This can all be implemented very easily with typical programming
languages used for web apps today.

Ciao, Michael.