Subject: RE: keyIdentifiers

From: Kevin Kingdon <[email-masked]>
Date: Tue, 3 Nov 1998 12:45:27 -0800

One issue that does affect applications is the scope of a key identifier. Is
it unique for a given subject, a given CA, or globally unique? In other
words, can I build a certificate chain using just key identifiers, or do I
have to use some combination of subject + identifier or issuer + (subject)
identifier to build the chain? X.509 says the first case (unique only with
respect to a given subject). Does PKIX expand the scope of the identifier to
one of the other two levels I mentioned?

-----Original Message-----
From: Marc Branchaud [mailto:[email-masked]]
Sent: Tuesday, November 03, 1998 11:59 AM
To: [email-masked]
Subject: Re: keyIdentifiers 

-----BEGIN PGP SIGNED MESSAGE-----

Content-Type: text/plain; charset=us-ascii

Robert Moskowitz <[email-masked]> scrawled:
> 
> Not according to a presentation Chicani gave to the federal PKI TWG back
in
> the spring.  He was quite clear that it was an APP issue to use
> keyIdentifiers to build a cert chain.
> 

Sure, but the app doesn't have to construct any key identifiers, just use 
the ones that are already in the certs.

> Then last week Mike Myers was pointing out how an app can use keyIdentifer
> for simpler processing for renewals.  Mike could better discuss this then
> me remember it.
> 

That's a different, and new, usage for key identifiers which I haven't 
heard of before.

My point is that s'far as chain construction goes, apps don't need to know
how to create key identifiers.  If key IDs are to be used for other
purposes, then some standard method of construction is probably a good
idea.  PKIX part1 (perhaps not very clearly) expects CAs to build key
identifiers, not apps.

		Marc

+------------------------------------------------------------------------+
 Marc Branchaud                                  \/
 Chief PKI Architect                             /\CERT INTERNATIONAL INC.
 [email-masked]        PKI References page:              www.xcert.com
 604-640-6227          www.xcert.com/~marcnarc/PKI/
+------------------------------------------------------------------------+
  PGP key fingerprint:  60 11 4B 9D 4E E5 2F 47  BD C5 C2 BF 26 DF 5A E1

---

From: Robert Moskowitz <[email-masked]>
Date: Tue, 03 Nov 1998 16:29:42 -0500

>one of the other two levels I mentioned?
I have been in discussions where there is an ASSUMPTION that the scope is
fairly broad, provided that the users use a different key pair for all of
their certs.  In fact, if I remember right about one aspect of the X.9
attribute cert doc, it puts a lot of reliance on uniqueness of
keyIdentifer.  Now I could be remembering wrong; I can't pull the doc right
now, and it was not necessarily the final markup version.

Robert Moskowitz
ICSA
Security Interest EMail: [email-masked]

---

From: "Simonetti David" <[email-masked]>
Date: Tue, 03 Nov 1998 18:21:27 -0500

Kevin,

I believe the key identifier is intended to be universally unique.  The
profile does not state this.  However, I recall a presentation where
someone was proving mathematically that taking 60 bits out of a SHA-1
hash of the public key would provide sufficient uniqueness.  What is
sufficient?  It was a very, very, very small fraction for a very, very
large number of certificates.  Sorry for the generalities, but I'm not a
mathematician.

Dave S.

Kevin Kingdon wrote:
> -----BEGIN PGP SIGNATURE-----
> Version: 2.6.2
> 
> iQB1AwUBNj9gblrdFXNdDxPlAQFCSwL+KeJshlbX05hbLWXcE2CXB1YZt2rg4t6w
> YBwyyKI9XI2VyXxabhO34iFtYBccLHkBB9w8Dhed81T23GojWEv8kloDoPW6RszK
> F9EY7+6W2tp9cMoKzSmkVtOKuclc9p+g
> =Itvv
> -----END PGP SIGNATURE-----

-- 
David Simonetti, Booz·Allen & Hamilton Inc.

---

From: Robert Moskowitz <[email-masked]>
Date: Tue, 03 Nov 1998 19:18:10 -0500

>large number of certificates.  Sorry for the generalities, but I'm not a
Dave,

I heard that was for a smaller, Elliptic Curve, key pair.  Not an RSA 1024
(let alone an RSA 2048) key pair.  In fact Tim mentioned the development of
SHA2 for a larger hash...

So the choice of hashing scheme, by the CA, is related to the key
algorithm, selected for global uniqueness.  Full 160 bits for RSA 1024 and
60 bits for little EC.

I guess.

Therefor I am, I guess.

Robert Moskowitz
ICSA

---

From: "Phillip M Hallam-Baker" <[email-masked]>
Date: Wed, 4 Nov 1998 10:47:47 -0500

> large number of certificates.  Sorry for the generalities, but I'm not a

They would be expecting to issue far fewer than 2^30 (1 billion)
certificates.

I'm not sure that is a very good assumption. In fact its a lousy one on
a planet with 5 billion people.

We are not so short of bits that we need to skimp on them to create unique
key IDs.

		Phill

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 04 Nov 1998 11:23:11 -0500

>a planet with 5 billion people.

But you are counting carbon based life forms.  There will be many factors
more of silicon based life forms that will need certificates.  Mike O'dell,
in his comments on bandwidth consumption has already named all of these
various systems (PCSs, pagers, heart monitors, toasters, refigs) as silicon
cockroaches.

>We are not so short of bits that we need to skimp on them to create unique
Some people are bandwidth conservative.  Some devices are indeed bandwidth
limited.

Robert Moskowitz
ICSA

---

From: Ambarish Malpani <[email-masked]>
Date: Wed, 04 Nov 1998 09:50:16 -0800

I don't think the key identifier was meant to be universally unique
(although I would like it to be so).

The use of key idenfiers, AFAIK, is as follows:

A CA includes a subject key identifier in its cert. It includes that
subject key identifier as authority key identifier in all certs that
it issues. This allows an application to find the CA cert - useful
where an application may have more than one CA cert with the same
name - for example, when the CA is going through key rollover.

Hope this helps (and is correct),

Ambarish

-- 
---------------------------------------------------------------------
Ambarish Malpani
Architect					         650.567.5457
ValiCert, Inc.				        [email-masked]
1215 Terra Bella Ave.		              http://www.valicert.com
Mountain View, CA 94043-1833

---

From: Paul Koning <[email-masked]>
Date: Wed, 4 Nov 1998 13:02:47 -0500

>>>>> "Robert" == Robert Moskowitz <[email-masked]> writes:

 >> We are not so short of bits that we need to skimp on them to
 >> create unique key IDs.
 >> 
 Robert> Some people are bandwidth conservative.  Some devices are
 Robert> indeed bandwidth limited.

I think lots of mistakes in protocol design have been made in the name
of a misguided goal of saving a few bytes.  I was just looking at one
yesterday -- a certain well known protocol throwing off all alignment
for the sake of saving ONE lousy byte.

Anyway, if you're dealing with certs, you already have big blobs of
bytes.  And if a few bytes is really that big a deal, isn't the right
answer to make key IDs optional?  But if supplied they should be good, 
and I agree with Phillip that there is no sensible reason to truncate
them to such tiny lengths.  If they need truncation, at least have the 
length be 96 or so (by the arguments applied to HMAC).

	paul

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 04 Nov 1998 13:17:21 -0500

>for the sake of saving ONE lousy byte.

I agree with your assessment.  I fought a derived IV for IPsec like PPTP
uses (and I think L2TP) to save 4 bytes per packet for 'slow links' and
potentially have IVs with low haming distance or require prior packet
delivery.  Some byte squeezing costs more than is gained.

>length be 96 or so (by the arguments applied to HMAC).

This is an interesting point.  Of course, I THINK the HMAC work post-dates
the selection of 60 bits by the ECC crowd.  They will have to speak up to
see if this is a good approach.

Robert Moskowitz
ICSA

---

From: "Simonetti David" <[email-masked]>
Date: Wed, 04 Nov 1998 14:42:38 -0500

I don't disagree.  The original proposal for a unique key identifier was
for 60 bits of the hash.  PKIX has since added a proposal for use of the
full 160 bits of the SHA-1 hash.

My point is...the key identifier is intended to be unique, using
whatever method you desire to generate it.

Dave S.

---

From: "Phillip M Hallam-Baker" <[email-masked]>
Date: Wed, 4 Nov 1998 14:47:58 -0500

> If they need truncation, at least have the

The HMAC work is not relevant here. With HMAC the collision problem
is much less severe because there is no requirement for HMACs to be
unique. The requirement is simply to make the discovery of the HMAC
key by brute force to be computationally infeasible.

This means that the HMAC strength is not reduced through the
birthday attack. So the effective cipher strength of 96 bits of
HMAC output is 2^96 - which is in the same ballpark as requiring
generation of 2^80 messages before collision is likely.

2^48 is getting there but in a world with a population of 5,000
billion robots (only 1000 each) the ability to only colonize 50
more solar systems might be constraining.

As Tom Knight once said.. "32 bits is not enough, thats not even
large enough for a phone number" - guess what the venue was??

	Phill

PS, Please, don't feel obliged to remind me there are silicon
lifeforms as well as 9 list members have done this morning. I
did not want to distract from the political point that we should
look beyond the parochial needs of the 1 billion citizens of
the rich countries when designing technology.

---

From: "Simonetti David" <[email-masked]>
Date: Wed, 04 Nov 1998 15:21:18 -0500

X.509 states, for Subject Key Identifier, "A key identifier shall be
unique with respect to all key identifiers for the subject with which it
is used."  

For Authority Key Identifier, it states, "A key identifier shall be
unique with respect to all key identifiers for the issuing authority for
the certificate or CRL containing the extension."

This sounds to me like the key identifier need only be unique to the
subject or issuer, respectively.  Seems like 60 bits would be
sufficiently effective.

Dave S.

---

From: Stephen Kent <[email-masked]>
Date: Wed, 4 Nov 1998 20:40:48 -0500

Folks,

Sorry I didn't jump in earlier, but I've been out of town and out of touch
for a while.

Key identifiers were motivated as a hueristic to solve the problem of which
of several certs (presumably with different keys) belonging to a CA should
be used to validate a cert that was signed by that CA.  This means that the
IDs need only be unique relative to the CA in question, since the scope of
the "search" was just the set of certs associated with that CA. Note that
CA name and serial number also are an acceptable alternative for this
purpose.

Some have suggested using these IDs are a "key" for database searches for
cert chain construction, etc., but this is not within the scope of the
extension, and thus I would advise against design decisions based on
presumed global uniqueness, even though the odds are in your favor for many
values of "global" ;-).  S/MIME does rely on the likely global uniqueness
of this value, if I recall correctly, using it as a tag for per-recipient
tokens.  This is a carryover from the MSP design, where we had a key
material ID that was guaranteed to be unique and which could be used for
this purpose.

Steve