Subject: Re: AKI and SKI problem with RFC 3280?

From: Peter Sylvester <[email-masked]>
Date: Tue, 21 Oct 2003 18:27:48 +0200 (MEST)

A little bit of nit-picking the text in 3820:

>4.2.1.2
>     One common method for generating unique values is a monotonically
>     increasing sequence of integers.
  1, 1, 2, 2, 3, 3 is a monotonically increasing sequence of integers
according to some common definitions for sequences or functions.

As far as I remember my math classes from 30 years ago,
non-ambiguous terms are 'strictly increasing" or
"monotone and strictly increasing" or "monotonically
strictly increasing" ...

Peter

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 21 Oct 2003 17:17:17 -0400

Based on a review of Sections 4.2.1.2 and 4.2.1.1 of 3280, I draw the
following conclusion: A 3280 compliant CA MUST ensure that AKI and SKI chain
properly.  This is sufficient for path construction.  Thus, I do not see a
particular need to change 3280 in this area.

The various methods for calculating these values and their probability of
collision need not be described in 3280.  As others have pointed out, AKI
and SKI need not be unique or different globally.  For efficient path
development, it is sufficient that AKI and SKI be different, with high
degree of probability, for different keys of the same entity.  The algorithm
chosen can be left up to the CA.  The proper chaining of AKI and SKI (not
for path validation, but for path construction) is important.  By proper
chaining, I mean that the SKI in certificate(s) issued to a CA for a
specific public key should (I read 3280 to say MUST, and I like that over
SHOULD) match the AKI in those certificates that the CA issues which are
verified using the said specific public key.

Santosh Chokhani
Orion Security Solutions, Inc.
1489 Chain Bridge Road, Suite 300
McLean, Virginia 22101
(703) 917-0060  Ext. 35(voice)
(703) 917-0260 (Fax)
[email-masked]
Visit our Web site
http://www.orionsec.com

---

From: "Peter Hesse" <[email-masked]>
Date: Wed, 22 Oct 2003 09:38:44 -0400

Santosh,

> Based on a review of Sections 4.2.1.2 and 4.2.1.1 of 
> 3280, I draw the following conclusion: A 3280 compliant
> CA MUST ensure that AKI and SKI chain properly.  This 
> is sufficient for path construction.  Thus, I do not 
> see a particular need to change 3280 in this area.

I read this differently.  I agree that for a given CA, that CA must make
sure that for certificates it issues, the AKID and SKID must match.
However, when you add the "IssuerDN/Serial" tuple version of AKID, that
can no longer be true.  When you start interoperating across domains,
there are times at which AKID and SKID will not match, but yet it should
lead to a valid path.  Consider the following example:

+------------------+                +--------------------+
|  Allied Pilots   |                |     Boeing Root    |
| Association Root |                |                    |
|                  |                | SKID: Q            |
| SKID: A          |                |                    |
+------------------+                +--------------------+
         \                                   /
          \                                 /
           V                               V
    =================================================
    | +-------------------+   +-------------------+ |
    | | American Airlines |   | American Airlines | |
    | |                   |   |                   | |
    | | SN: 12345         |   | SN: 87654         | |
    | | SKID: Z           |   | SKID: Z           | |
    | | AKID: A           |   | AKID: Q           | |
    | +-------------------+   +-------------------+ |
    =================================================
                            |
                            |
                            V
                  +-------------------+
                  |     Joe Pilot     |
                  |                   |
                  | SKID: W           |
                  | AKID: "American   |
                  |        Airlines,  |
                  |        12345"     |
                  +-------------------+

In our example, we have the "American Airlines" entity which has two
certificates, one issued by the Allied Pilots Association (AA's union)
and the other by Boeing (one of their manufacturers).  These two
certificates have the same public key and subject public key identifier,
but different serial numbers.  "American Airlines" issues a certificate
to "Joe Pilot".  Although Joe Pilot's AKID points to the AA Root
certificate issued by the Allied Pilots Association, there is no reason
why a path to the Boeing Root should not be found equally acceptable.

The other thing at play was what Steve Hanna mentioned in an earlier
message.  Currently, there is no commonly accepted way to for a
cross-certifying CA to accept the desired SKID in a request for
cross-certification.  Therefore, many CAs  calculate their own SKID.  In
fact, look at this part of section 4.2.1.2 of RFC3280:

   For CA certificates, subject key identifiers SHOULD be 
   derived from the public key or a method that generates 
   unique values.

Here, 3280 is saying you should derive the SKID from the public key, it
says nothing about making use of any existing  key identifier that the
CA is putting as the AKID in certificates it issues.  But wait!  If you
read down a little further, you get: 

   Where a key identifier has not been previously 
   established, this specification RECOMMENDS use of one 
   of these methods for generating keyIdentifiers.  Where
   a key identifier has been previously established, the 
   CA SHOULD use the previously established identifier.

I see shoulds and recommends here, and not MUSTs.  Prior experience has
shown me that two CAs configured in different ways (or running different
software) may both derive the SKID from the public key in two different
fashions, and you can end up with the following:

+------------------+                +--------------------+
|  Allied Pilots   |                |     Boeing Root    |
| Association Root |                |                    |
|                  |                | SKID: Q            |
| SKID: A          |                |                    |
+------------------+                +--------------------+
         \                                   /
          \                                 /
           V                               V
    =================================================
    | +-------------------+   +-------------------+ |
    | | American Airlines |   | American Airlines | |
    | |                   |   |                   | |
    | | SN: 12345         |   | SN: 87654         | |
    | | SKID: Z           |   | SKID: F           | |
    | | AKID: A           |   | AKID: Q           | |
    | +-------------------+   +-------------------+ |
    =================================================
                            |
                            |
                            V
                  +-------------------+
                  |     Joe Pilot     |
                  |                   |
                  | SKID: W           |
                  | AKID: Z           |
                  +-------------------+

Although the public key has remained the same, American Airlines now has
two certificates with two different SKIDs but the same public key.
Again, there is no reason why a path from Joe Pilot to the Boeing Root
should not be valid.

--Peter

+---------------------------------------------------------------+
| Peter Hesse                    [email-masked]     |
| Phone: (703)934-2031         Gemini Security Solutions, Inc.  |
| ICQ: 1942828                     www.geminisecurity.com       |
+---------------------------------------------------------------+
"Pay no attention to what the critics say; there has never been 
a statue set up in honor of a critic." --Jean Sibelius

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 22 Oct 2003 11:02:04 -0400

Peter:

My e-mail needs to be read in the context of the producers.  The CAs as
producers need to ensure that the AKI and SKI chain.  If the CAs do not do
that, they are not compliant with 3280.  That means in order to comply with
3280 issuing CA needs to honor the SKID requested by the subject CAs.

The consumers, i.e., the relying parties should not enforce the AKI and SKI
chaining.  They can use the match as the prioritization during path
construction.

Forcing CAs to enforce the AKI and SKI match and not requiring the relying
parties to enforce it (but simply use as a prioritization) offers us the
best of both worlds in terms of enhancing interoperability.

As for algorithm for constructing the values, 3280 should and does provides
these as recommendations as opposed to SHALL or MUST.

-----Original Message-----
From: Peter Hesse [mailto:[email-masked]] 
Sent: Wednesday, October 22, 2003 9:39 AM
To: 'Santosh Chokhani'; [email-masked]
Subject: RE: AKI and SKI problem with RFC 3280?

Santosh,

I read this differently.  I agree that for a given CA, that CA must make
sure that for certificates it issues, the AKID and SKID must match. However,
when you add the "IssuerDN/Serial" tuple version of AKID, that can no longer
be true.  When you start interoperating across domains, there are times at
which AKID and SKID will not match, but yet it should lead to a valid path.
Consider the following example:

In our example, we have the "American Airlines" entity which has two
certificates, one issued by the Allied Pilots Association (AA's union) and
the other by Boeing (one of their manufacturers).  These two certificates
have the same public key and subject public key identifier, but different
serial numbers.  "American Airlines" issues a certificate to "Joe Pilot".
Although Joe Pilot's AKID points to the AA Root certificate issued by the
Allied Pilots Association, there is no reason why a path to the Boeing Root
should not be found equally acceptable.

Here, 3280 is saying you should derive the SKID from the public key, it says
nothing about making use of any existing  key identifier that the CA is
putting as the AKID in certificates it issues.  But wait!  If you read down
a little further, you get: 

Although the public key has remained the same, American Airlines now has two
certificates with two different SKIDs but the same public key. Again, there
is no reason why a path from Joe Pilot to the Boeing Root should not be
valid.

---

From: Jean-Marc Desperrier <[email-masked]>
Date: Wed, 22 Oct 2003 19:11:34 +0200

This AKID is wrong. It should be "Allied Pilots Association Root, 12345".
This type of AKID is a issuer name/serial pair, this means pointing 
amongst the certificate emitted by ca IssuerName to the one that has the 
serial SN.
American Airlines certificate is the certificate SN:12345 amongst those 
issued by "Allied Pilots Association Root"

You certainly know about this, but this particular misinterpretation of 
AKID tends to be a recurrent problem, so I feel better not to leave it 
uncorrected.

---

From: "Peter Hesse" <[email-masked]>
Date: Wed, 22 Oct 2003 12:59:24 -0400

Santosh Chokhani wrote:
> My e-mail needs to be read in the context of the producers.  
> The CAs as producers need to ensure that the AKI and SKI chain.
> If the CAs do not do that, they are not compliant with 3280.  
> That means in order to comply with 3280 issuing CA needs to 
> honor the SKID requested by the subject CAs.

I think we're in violent agreement.  My main point was that although the
producer needs to ensure that AKID and SKID chain, cross-PKI
interoperability will cause cases in which the producer must choose
between two (or more) equally valid AKIDs to place in a subject
certificate.  Either of them will chain successfully and the producer
will be compliant; but as a result there will be valid paths where the
AKID and SKID will not chain, through no fault of the producer.

--Peter

---

From: Jean-Marc Desperrier <[email-masked]>
Date: Wed, 22 Oct 2003 19:09:33 +0200

Peter Hesse wrote:

>Currently, there is no commonly accepted way to for a
>cross-certification.
Why ?
Do cross-certifying CA discards all extensions inside the request so 
that it's not possible to specify the SKID by including it as an 
extension inside the request ?
But even when they do, then you need to specify all extensions to 
include by hand, so you could insert the correct SKID transported out of 
band, with the other info needed for that CA, wouldn't you ?

It would be interesting if I'm proven wrong, but it's seems to me 
cross-certifying doesn't happen everyday, and always involves some 
manual operations, so is there really a good reason why you can not do 
this customisation of the parameters ?

I just found a document from the pkiforum that endorses this method : 
http://www.pkiforum.org/pdfs/AKID_SKID1-af3.pdf
It also reports that both U.S. Federal Bridge CA and CESG 
interoperability initiatives reported mismatches preventing proper 
certification path construction.

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 22 Oct 2003 14:01:29 -0400

Peter:

Section 4.2.1.2 (Subject Key Identifier) of 3280 states and I quote: "The
value of the subject key identifier MUST be the value placed in the key
identifier field of the Authority Key Identifier extension (section 4.2.1.1)
of certificates issued by the subject of this certificate."  Read in
context, the above is stated for CA certificates.

Thus, in cross certified environment, 3280 compliant issuing CAs need to
ensure that the SKI in 3280 compliant subject CA certificate is the value
that the subject CA intends to use as AKI for certificates it issues.

If the AKI and SKI (even for cross certified environments) do not chain, one
or more of the CAs is not compliant with 3280.

-----Original Message-----
From: Peter Hesse [mailto:[email-masked]] 
Sent: Wednesday, October 22, 2003 12:59 PM
To: 'Santosh Chokhani'; [email-masked]
Subject: RE: AKI and SKI problem with RFC 3280?

I think we're in violent agreement.  My main point was that although the
producer needs to ensure that AKID and SKID chain, cross-PKI
interoperability will cause cases in which the producer must choose between
two (or more) equally valid AKIDs to place in a subject certificate.  Either
of them will chain successfully and the producer will be compliant; but as a
result there will be valid paths where the AKID and SKID will not chain,
through no fault of the producer.

--Peter

---

From: "Peter Hesse" <[email-masked]>
Date: Wed, 22 Oct 2003 16:12:40 -0400

Santosh,

Point taken.  3280 therefore requires that the keyIdentifier method (as
opposed to the issuer DN/serial tuple) MUST be used.  In 4.2.1.1 (AKID)
it only RECOMMENDS this; but the words you quote from 4.2.1.2 (SKID)
make it a requirement, intentionally or not.  As you said, in the below
case, at least one CA is not compliant with 3280.  Unfortunately, I've
seen this happen in practice.  As you said earlier, it would be best if
path building implementations could be flexible about this, but
certificate producers should be compliant.

Two other things: Sharon is dead on, and the only thing I would say is
that support for accepting SKIDs in certification requests seems to work
well with a particular implementation, but require manual input or is
not possible between different implementations.

And Jean-Marc was also quite correct, my example was wrong.  It's the
Issuer's Issuer DN and serial, I just put the Issuer's DN in my example.
Shame on me.

--Peter

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
On Behalf Of Santosh Chokhani
Sent: Wednesday, October 22, 2003 2:01 PM
To: [email-masked]
Subject: RE: AKI and SKI problem with RFC 3280?

Peter:

Section 4.2.1.2 (Subject Key Identifier) of 3280 states and I quote:
"The value of the subject key identifier MUST be the value placed in the
key identifier field of the Authority Key Identifier extension (section
4.2.1.1) of certificates issued by the subject of this certificate."
Read in context, the above is stated for CA certificates.

Thus, in cross certified environment, 3280 compliant issuing CAs need to
ensure that the SKI in 3280 compliant subject CA certificate is the
value that the subject CA intends to use as AKI for certificates it
issues.

If the AKI and SKI (even for cross certified environments) do not chain,
one or more of the CAs is not compliant with 3280.

-----Original Message-----
From: Peter Hesse [mailto:[email-masked]] 
Sent: Wednesday, October 22, 2003 12:59 PM
To: 'Santosh Chokhani'; [email-masked]
Subject: RE: AKI and SKI problem with RFC 3280?

> producers need to ensure that the AKI and SKI chain. If the CAs do not

> do that, they are not compliant with 3280.

--Peter

---

From: Steve Hanna <[email-masked]>
Date: Wed, 22 Oct 2003 16:58:57 -0400

Maybe we are close to ending this discussion. Everyone
agrees that CAs MUST use an SKI in CA certificates that
matches the AKI used in certificates issued by the
subject of the certificate. Relying parties can use
this as a hint during path construction, but they should
not require AKI/SKI matching during path construction or
path validation.

But RFC 3280 does not say clearly and explicitly that
relying parties should not require AKI/SKI matching.
Several implementors have misunderstood this. I suggest
that the successor to RFC 3280 should be changed to
make an explicit recommendation that relying parties
SHOULD NOT require AKI/SKI matching.

Thanks,

Steve

---

From: "L Williams" <[email-masked]>
Date: Wed, 22 Oct 2003 19:08:15 -0700

Man, I was loving this thread up until this point.

I think what this thread established was that sane CAs should be able to
respect existing key identifiers when they do cross-certification/bridging.
This means that AKI/SKI chaining should work the majority of the time, not
fail the majority of the time. Seems to me that the change would be to make
this a "SHOULD" not a "SHOULD NOT".

Yes, there are backwards compatibility issues, but this can be dealt with.

-Laudon
(Microsoft)

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On
Behalf Of Steve Hanna
Sent: Wednesday, October 22, 2003 1:59 PM
To: Peter Hesse
Cc: [email-masked]
Subject: Re: AKI and SKI problem with RFC 3280?

Thanks,

Steve

---

From: Steve Hanna <[email-masked]>
Date: Fri, 24 Oct 2003 10:19:39 -0400

I'll try Peter Gutmann's technique of responding to
several messages at once to reduce the number of messages.

Stefan Santesson wrote:
> And may I also suggest limiting recommendations to
> key identifiers derived from the key hash, unless
> there is a strong need for other solutions not yet
> presented in this debate.

Yes, I think there is universal agreement that
"a monotonically increasing sequence of integers"
SHOULD NOT be used for AKI/SKI. I'd be glad to
see such a recommendation added to the successor
to RFC 3280.

L Williams wrote:
> I think what this thread established was that sane CAs
> should be able to respect existing key identifiers when
> they do cross-certification/bridging. This means that
> AKI/SKI chaining should work the majority of the time,
> not fail the majority of the time. Seems to me that the
> change would be to make this a "SHOULD" not a "SHOULD NOT".

Which SHOULD are you talking about? I suspect you mean
my comment "relying parties SHOULD NOT require AKI/SKI
matching." If so, why do you think that relying parties
SHOULD require AKI/SKI matching? There's no security
benefit to doing so and some significant downsides, as
noted below.

Sharon Boeyen wrote:
> Shouldn't a CA determine what its own key identifier is
> (and 3280 recommends ways to calulate it). Once they have
> their own key id, this value should go into the AKI extension
> of all certificates issued by that CA and should go into
> the SKI extension of all certificates issued to that CA.

I agree that's best. However, it doesn't always work
out that way. Some CA software (or maybe just CAs as
operated) apparently doesn't allow the certificate
subject to specify what SKI it wants. Also, consider
the case where a CA decides to change its AKI (as when
moving away from monotonically increasing integers).
It would be nice to gradually transition from the old
AKI to the new one (without requiring all certificates
to and from the CA to be reissued simultaneously).

I agree with Santosh's earlier comment. We should stick with
the current RFC 3280 statements that CAs MUST use an
SKI in each CA certificate they issue that matches the
AKI used by the subject of the certificate. And we
should add a statement (explicitly stating what was already
implicit) saying that relying parties SHOULD NOT require
this match. It's only a hint for path building.

While I'm at it, I'll respond to one more comment:

Michael Ströder wrote:
> Is there any good reason to set AKI/SKI at all?

Some path building software uses it as a hint to
choose between several certs that look suitable.
Personally, I don't see a big win. As Peter points
out, subject and issuer names are a more reliable
mechanism. They *must* match or the path isn't valid.

Unfortunately, I have heard that some path building
software uses AKI/SKI as a database key and only
finds a path if they match. I've also heard that
some path validation software requires a match.
Both of those are mistakes. What a bummer for the
users! And all the more reason why the successor to
RFC 3280 should be explicit in saying that relying
parties SHOULD NOT require an AKI/SKI match.

So I think AKI/SKI have *some* utility

Thanks,

Steve

---

From: Jean-Marc Desperrier <[email-masked]>
Date: Fri, 24 Oct 2003 19:17:36 +0200

Steve Hanna wrote:

>Some CA software (or maybe just CAs as
>subject to specify what SKI it wants. 
>
Really I'd be surprised  if this was indeed a software limitation.
So who here distribute a CA products that can not be configured to 
attribute the correct SKI to a sub-CA certificate ?
Of course we're talking here about sub-CA and not end-entity certificates.
I don't expect to see certificates for CA delivered from an automatic 
process that can not be tuned, but I could be wrong for some cases of 
cross-certificates.

It would be really good to know if the problem met in interoperability 
tests were due to :
- insufficient attention given to this subject by the CA operator.
- actual limitation of some rarer CA software
- actual limitation of a significant number of popular CA software

I have met at least one product that did not offer a way to copy it 
automatically.
But the key ceremony required to create such a certificate already 
included a one page long description of every single tidbit that would 
go inside the certificate, so adding the exact value of the SKI in case 
it could not be created with one the standard algorithms would have been 
no great deal.