Subject: RE: SV: Briefing on CRL Path for IETF PKIX WG Meeting

From: "Alberti Antoine" <[email-masked]>
Date: Tue, 2 Nov 2004 11:21:21 +0100

From my point of view, identification has always been the main of PKI. Nothing guarantees that a DN is unique, as I have never seen the unique global LDAP directory, or the root of such a directory, managed like OIDs. And this is the reason why all these extensions and complicated fuzzy identifiers were born, making PKI so complicated that it takes centuries to be understood and spread out as a global solution.
Then, what should be done when a PKI server finds 2 entities with the same DN, coming from 2 different trusted sources ? Should we sew the one that comes last ? Or refuse anything that comes from any of the entities until they both agree on different DNs ? (And how is one supposed to warn these entities that they can not be used on a global scale when they have a local structure that works ?) Or make the products manage data models with no structure at all, in order to be compliant with any case that may be occur ? Or try to find a solution for uniquely identifying entities and certificates, making all these problems disappear in a few dozen years, which is almost nothing regarding PKI deployment ?
Regards.
AA.

> -----Message d'origine-----
> De : [email-masked]
> [mailto:[email-masked]]De la part de Julien Stern
> Envoyé : mardi 2 novembre 2004 10:30
> À : [email-masked]
> Objet : Re: SV: Briefing on CRL Path for IETF PKIX WG Meeting
> 
> 
> 
> Greetings,
> 
> the more posting about this issue and the more confused I am :)
> I understood that
> 
> 1) Ideally, a DN should uniquely identify a entity.
> 
> 2) If two Trust Anchors with the same DN are different entities, there
> is a major (configuration) problem.
> 
> 3) If two certificates have the same DN but represent 
> different entitities
> that is a mistake (or an attack). That must be detected.
> 
> 4) The way to detect it is to check for the ancestors according to the
> algorithm proposed by Santosh.
> 
> Is that correct ?
> Is there a consensus on this ?
> Shouldn't OCSP have a special treatment on that respect ?
> 
> Sincerely,
> 
> --
> Julien Stern
> 
> On Sat, Oct 30, 2004 at 03:59:23PM +0100, Stefan Santesson wrote:
> > 
> > Peter,
> > 
> > I assume that this encapsulates the issue:
> > <snip>
> > > Are you saying that in the presence of two CA certs with same name
> > having
> > > a different key, one general should
> > > first assume that they belong to different entities, and 
> only if one
> > finds
> > > a cross certificate pair of
> > > one signing the other key and vice versa, you may 
> conclude that you
> > have
> > > the same entity so you look for
> > > CRLs signed by *the same* CA but the other key.
> > 
> > Yes and no.
> > 
> > Validation software should start with the assumption that two
> > certificates (CA or CRLissuer type), carrying the same subject name,
> > represent different entities until it can determine that they are
> > offspring of the same ancestors according to the algorithm 
> proposed by
> > Santosh.
> > 
> > This approach is much more attack resilient and reduce complexity in
> > path validation. 
> > 
> > I don't see how building a local database is neither 
> generally feasible
> > nor a valid alternative.
> > 
> > Stefan Santesson
> > Microsoft Security Center of Excellence (SCOE)
> >  
> > > -----Original Message-----
> > > From: [email-masked]
> > [mailto:[email-masked]]
> > > On Behalf Of Peter Sylvester
> > > Sent: den 29 oktober 2004 18:06
> > > To: [email-masked]; Stefan Santesson
> > > Cc: [email-masked]
> > > Subject: Re: SV: Briefing on CRL Path for IETF PKIX WG Meeting
> > > 
> > > 
> > > >
> > > > Peter,
> > > >
> > > > I disagree. I think it is very important to cover for 
> the case where
> > 2
> > > CAs may have the same name.
> > > >
> > > 
> > > I am not against having someone to provide a specification how to
> > > construct
> > > a local database and a way to detect such a situation inside the
> > potato
> > > of cross certificates connected CA suppended by trust hooks.
> > > 
> > > > In troducing indirect CRLs means that we introduce 
> possible attack
> > > vectors and it is our responsibility to create rules that makes
> > > vulnerabilities as unlikely as possible, even in bad 
> implementations
> > (80%+
> > > of all vulnerabilities are miconfiguration problems).
> > > >
> > > > If you include trust in public roots, then It is virtually
> > impossible to
> > > guarantee and check that there are not any CAs with name 
> collisions
> > > anywhere.
> > > 
> > > If the PKI "database" is just a set of otherwise isolated 
> parts each
> > > of them hanging on one trusted root without cross certs amongs the
> > parts,
> > > then
> > > the situation is rather simple, i.e. you have different 
> PKIs, if not,
> > what
> > > do you propose?
> > > 
> > > The problem to me seems what you should assume when you 
> find two keys
> > > attributes to the same CA name?
> > > probably whene you have a crosscert pair each key certifying the
> > other?
> > > 
> > > > As writer of validation code, we must close every 
> possible weaknes
> > for
> > > an error, miconfiguration or attack.
> > > 
> > > When you write a piece of software, It may be hard to 
> predict in what
> > > context that software will be running. You can't say that 
> this code is
> > > only for use in aninfrastructure with CAs without name collisions,
> > unless
> > > the code have some means of detecting such environment 
> and refuse to
> > > operate in it. This is not the case however.
> > > >
> > > 
> > > Are you saying that in the presence of two CA certs with same name
> > having
> > > a different key, one general should
> > > first assume that they belong to different entities, and 
> only if one
> > finds
> > > a cross certificate pair of
> > > one signing the other key and vice versa, you may 
> conclude that you
> > have
> > > the same entity so you look for
> > > CRLs signed by *the same* CA but the other key.
> > > 
> > > > The other aspect is complexity. Use of indirect CRLs without any
> > > limitations may lead to infinitely complex path 
> validation where every
> > new
> > > path introduce more CRL paths and where each new CRL path 
> introduce
> > new
> > > CRL paths which introduce new CRL paths etc.......  
> Denial of service
> > > attacks through complex paths isn't faar away.
> > > 
> > > I don't understand why you say this here. What make this more
> > difficult, a
> > > requirement that CAs are unique or
> > > the contrary? Welcome in the real world. :-)
> > > 
> > 
> > 
> 
>

---

From: Peter Sylvester <[email-masked]>
Date: Tue, 2 Nov 2004 15:41:13 +0100 (MET)

> offspring of the same ancestors according to the algorithm proposed by
> Santosh.

I am not sure what you say "(CA or CRLissuer type)": 
Does this include the case that two CA keys are certified by
the same third entity, i.e. the fact having two certs from
one CA for the "same entity"? 

I think that indeed assuming different entities is robust and does
not create more new problems.  

> I don't see how building a local database is neither generally feasible
> nor a valid alternative.

I don't meant a permanent storage, just the data structure that is used
to hold some "indexed" heap of certs,allowing a minimal number
of signature tests., i.e. issuer/serial may point to several certs in
this heap.

---

From: "Stefan Santesson" <[email-masked]>
Date: Wed, 3 Nov 2004 15:14:12 -0000

Peter,

The problem and the algorithm presented address the case where the CA
and the CRL issuer are represented by different certificates. This can
be the case both when the CA and the CRLissuer is the same entity with
the same name, but using different keys, or when the CA and the
CRLissuer is separate entities. This is what I meant by CA or CRLissuer
type.

Stefan Santesson

> From: Peter Sylvester [mailto:[email-masked]]
> Sent: den 2 november 2004 15:41
> Subject: RE: SV: Briefing on CRL Path for IETF PKIX WG Meeting
> 
> > Yes and no.
> >

---

From: "Stefan Santesson" <[email-masked]>
Date: Wed, 3 Nov 2004 17:51:41 -0000

Peter,

Your assumption is wrong.

A CA with 2 keys is still just 1 entity and one CA. That has been
determined through the discussions on this list.

I'm the first to admit though that this is not all too clearly and
explicitly spelled out in neither X.509 nor RFC 3280 in but it is
definitely defined in indirect terms.

Stefan Santesson
 
> Sent: den 3 november 2004 18:42
> I think we don't have a problem but I'd like to know whether
> the following is correct:
> 
> if we assume that PKI entity unicity is based on key+DN (or
practically
> just key), then we could have a situation that after rekeying a
> CA may have had issed a CRL with the old key which is still valid as
> well as a CRL with the new key. These CRL are assumed to come from
> two different entities, thus the availability of the new does not
> replace the older one. This is probably not worse than not being
> able to access to the new CRL.
> If one can detect a rekeying, this is not better than the effects
> of a good access to fresh CRLs?
> 
> A problem remaining is that if an RP does not detect a rekeying
> then trust configuations for the old CA cannot be carried over to
> the other.

---

From: Peter Sylvester <[email-masked]>
Date: Wed, 3 Nov 2004 18:41:38 +0100 (MET)

if we assume that PKI entity unicity is based on key+DN (or practically

---

From: Peter Sylvester <[email-masked]>
Date: Wed, 3 Nov 2004 19:09:14 +0100 (MET)

> determined through the discussions on this list.

Well, then to me the question remains: 

How do you determine *safely* that two keys associated to the same DN
belongs to one CA, and how can you be sure not assuming that you
have a case with two CAs. 

Is having two certs from the same superior CA the determining condition?

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 9 Nov 2004 16:07:06 -0500

Stefan,

One more thing.  Aside from the threat the algorithm mitigates described at
the end of the e-mail, the algorithm mitigates threats for Julien's rogue CA
scenario.  If the relying party had the legitimate path from the left side
of his diagram, using the path matching will ensure that they do not accept
the CRL from the rogue side.  Without the algorithm, they would.

-----Original Message-----
From: Santosh Chokhani [mailto:[email-masked]] 
Sent: Tuesday, November 09, 2004 3:44 PM
To: [email-masked]'
Subject: RE: Briefing on CRL Path for IETF PKIX WG Meeting

Stefan,

See responses in line in [SC:}

-----Original Message-----
From: Stefan Santesson [mailto:[email-masked]] 
Sent: Tuesday, November 09, 2004 2:06 PM
To: Denis Pinkas; Santosh Chokhani; Julien Stern
Cc: [email-masked]
Subject: RE: Briefing on CRL Path for IETF PKIX WG Meeting

It seams that we have a problem with agreeing on the security assumptions
more than on the technical matters.

I recognize that Julien's scenario is a valid remark, at least in theory.
The point Julien is that there is a problem if an attacker that has obtained
a rouge CA under a valid root actually could fool an RP software to accept
the rouge path to the target certificate. IF the RP accept the path over the
rouge CA then that rouge CA could also defeat the proposed algorithm.

The question is just if this is a valid threat or not.

Denis is making a valid remark that different CA's in the certificate path
may certify different CRL Issuers with the same name by accident and the
algorithm doesn't account for that.

[SC: This is only an issue in the context of indirect CRL.  For the direct
CRL issuer, the algorithm will disambiguate the issues].

The question is if this is a valid threat or not.

Both Denis and Julien's scenarios require intentional malicious behaviour of
the CRL issuer or the CDP and the IDP wouldn't match (the storage location
pointer would differ).

[SC: I have not seen a scenario from Denis.  I have a different and simple
take on Julien's scenario.  First, Julien's scenario will not come about for
the relying parties who do not trust the rogue CA.  Second, the algorithm
makes sure that who ever is the certificate issuer from the relying party
perspective can only revoke the certificate.  Third, even if the same key
was used, in Julien's scenario relying party can always be fooled into using
bad revocation information along with bogus certificate minted by the rogue
CA.]

Both scenarios also require the attacker to convince the RP to NOT obtain
the correct CRL through the CDP pointer and instead accept the rough CRL
from other source OR it requires the attacker to hack the server holding the
real CRL and replace the real CRL with the rough CRL.

----------------

In Denis scenario I would suggest that we can exclude presence of a rouge CA
in the original certificate path, because if the original cert path has a
rouge CA, then all bets are off anyway.

This leaves us with Julien's scenario.

-----------------

So the main question is which of these threats that is in scope or out of
scope 

1) Presence of a trusted Rouge CA that is NOT part of the original
certificate path.

2) The ability of the attacker to fool the RP to pick a rouge path and rouge
CRL where the IDP and CDP match.

Questions/remarks:
- If both these threats are in scope then Julien's scenario is also valid.
- If there threats are out of scope, then what threat remains that requires
Santosh algorithm in the first place?

[SC: The threat that the algorithm mitigates is one of accidental error and
one of malfeasance.  Let me illustrate.  Let us say that both Microsoft and
VeriSign roots are in a relying party trust anchor  set.  Let us say that
that we have Microsoft --> Orion CA --> Chokhani.  Chokhani is an end entity
with serial number 10.  Let us also say that VeriSign has certified another
Orion.  So, we have VeriSign -->  Orion CA --> CRL X.  Now, some one can
compromise Chokhani key and play the CRL X  that does not contain 10 and
make the relying party access Chokhani certificate which actually has been
compromised.  In this case, all four CAs and Chokhani are playing nice, but
some one else just ate our lunch.]

I'm still pro Santosh algorithm since it limits complexity in path
processing but it would be good to know if there are any threats that
require Santosh algorithm which remains if at least problem 1 above is out
of scope.

Stefan Santesson

---

From: Peter Sylvester <[email-masked]>
Date: Wed, 10 Nov 2004 15:19:27 +0100 (MET)

3280 5.1.1.3:  

   CRL checking in turn requires a separate
   certification path to be constructed and validated for the CA's CRL
   signature validation certificate. Applications that perform CRL
   checking MUST support certification path validation when certificates
                         XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
   and CRLs are digitally signed with the same CA private key.  These
   applications SHOULD support certification path validation when
                               XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
   certificates and CRLs are digitally signed with different CA private
   keys.

what 'certification path validation' is meant here? 
I guess the validation of the initial certificate?

---

From: "Stefan Santesson" <[email-masked]>
Date: Wed, 10 Nov 2004 14:58:22 -0000

Denis,
 
<snip>
>Denis is making a valid remark that different CA's in the certificate
>path may certify different CRL Issuers with the same name by accident
>
>[DP: Thank you for the acknowledgment]
>
>and the algorithm doesn't account for that.
>
>[Santosh: since you intercept every mail, I guess you will notice that
>Stefan mentions that your algorithm has indeed a problem].

I didn't say that. My conclusion was that this is only applicable to indirect CRLs where IDP/CDP match is required, which mitigates this issue (unless you have a rouge CA).
 
I guess this also address the rest of your remarks.

Stefan Santesson

---

From: Peter Sylvester <[email-masked]>
Date: Wed, 10 Nov 2004 15:26:00 +0100 (MET)

IMO you can ignore my previous message concerning chapter 5.1.1.3

---

From: "Dave Engberg" <[email-masked]>
Date: Thu, 11 Nov 2004 08:55:42 -0500

I think that there is a confusion between the logical identity of a CA and
the provable denotation of its certificates. 
 
For a PKI administrator, it may be philosophically correct to say that the
CA is defined by its name alone.  Of course, it is not useful (or even
correct?) to say that every X.509 certificate with the same subject Name
denotes the same CA.  For relying parties, Name equality is a necessary but
not sufficient requirement for determining whether two certs refer to the
same entity.
 
For relying party processing, I think that it is more useful to consider a
CA to be a an entity with a single Name and one or more Public Keys.  For a
relying party:
 
* Two certs with the same subject Name and Public Key always denote the same
entity.
 
* Two certs with different subject Names always denote different entities.
 
* Two certs with the same subject Name and different Public Keys denote the
same entity if and only if a trusted path can be found to both according to
Santosh's algorithm.

Of course, all this talk about theoretical CA identity for CRL processing
has obscured Santosh's original recommendation that if you care at all about
interoperability, your CA should always sign a CRL with the same key used to
sign any certs holding that CRL's distributionPoint URI.  The confusion on
this list makes it seem like this recommendation should be repeated.
 
(In fact, if the goal of the spec was interoperability, I'd make Santosh's
recommendation mandatory instead of hoping that all COTS PKI apps will
implement all these baroque discovery and validation edge cases.  The value
of this alternate-key CRL signing is pretty low compared to the complexity
it introduces for relying parties ...)

  _____  

From: [email-masked] [mailto:[email-masked]] On
Behalf Of David A. Cooper
Sent: Wednesday, November 10, 2004 9:34 PM
To: Denis Pinkas
Cc: [email-masked]
Subject: Re: Briefing on CRL Path for IETF PKIX WG Meeting

Denis,

X.509 states:

NOTE 1 - Although the CAs are unambiguously defined by a distinguished name
in the DIT, this does not imply that there is any relationship between the
organization of the CAs and the DIT.

Where in X.509 does it say or even imply that a CA in not defined by name
alone, but that a name is always relative to the CA which has issued it?  I
can't find anything in X.509 to support this.  On the other hand, there is
plenty to support the notion a CA is defined by name alone.  In addition to
the above quote, note that the cRLDistributionPoints extension identifies an
indirect CRL issuer by name alone as does the certificateIssuer CRL entry
extension.  This makes sense if a CA can be identified by name alone but
does not make sense if a CA name is only relative to the CA which has issued
it.  Similarly, in many protocols, a certificate is identified by issuer
name and serial number.  These two pieces of information would not be
sufficient to identify a certificate if your interpretation were correct.

 ...
 
Dave

Denis Pinkas wrote: 

Slide 5. The statement " A CA is defined by name alone" is 
wrong. A CA is not simply defined by a name alone. A name, 
for X.509, is always relative to the CA which has issued it. 
So the "clarification' to say that a CA is unambiguously 
defined by name is wrong. Then since the other slides are 
based on that wrong assumption, they are wrong as well. 

 ...

---

From: Peter Sylvester <[email-masked]>
Date: Mon, 15 Nov 2004 16:54:53 +0100 (MET)

> 
> Slide 7:  There is no "need to account for multiple CAs with the same 
> name". This formulation is pretty bad. A CA must provide different 
> names to two different entities. Since a CA name is relative to 
> another CA name space, there cannot be two CAs with the same name.
> 
> [SC: There is XX requirement or mechanism that ensures that a relying 
> party

It seems to me that there is a missing *no* where I added the XX.

> with multiple trust anchors will not encounter two CAs with the same 
> name. If a relying party has two trust anchors A and B and there are 
> two distinct companies with the same name C, it is possible that one C 
> is certified via A and another via B.]
> 
> [DP1: The assumption : "there is requirement or mechanism that ensures 
> that a relying party with multiple trust anchors will not encounter 
> two CAs with the same name" is fully wrong ! The same name may be 
> found.]

---

From: Peter Sylvester <[email-masked]>
Date: Mon, 15 Nov 2004 16:54:53 +0100 (MET)

---

From: Peter Sylvester <[email-masked]>
Date: Wed, 10 Nov 2004 15:19:27 +0100 (MET)

3280 5.1.1.3:

---

From: "Stefan Santesson" <[email-masked]>
Date: Wed, 10 Nov 2004 14:58:22 -0000

Denis,
 
<snip>

Stefan Santesson

---

From: "Dave Engberg" <[email-masked]>
Date: Thu, 11 Nov 2004 08:55:42 -0500

_____  

Denis,

X.509 states:

 ...
 
Dave

Denis Pinkas wrote: 

 ...

---

From: "Stefan Santesson" <[email-masked]>
Date: Tue, 9 Nov 2004 19:05:32 -0000

It seams that we have a problem with agreeing on the security
assumptions more than on the technical matters.

I recognize that Julien's scenario is a valid remark, at least in
theory. The point Julien is that there is a problem if an attacker that
has obtained a rouge CA under a valid root actually could fool an RP
software to accept the rouge path to the target certificate. IF the RP
accept the path over the rouge CA then that rouge CA could also defeat
the proposed algorithm.

Both Denis and Julien's scenarios require intentional malicious
behaviour of the CRL issuer or the CDP and the IDP wouldn't match (the
storage location pointer would differ).

Both scenarios also require the attacker to convince the RP to NOT
obtain the correct CRL through the CDP pointer and instead accept the
rough CRL from other source OR it requires the attacker to hack the
server holding the real CRL and replace the real CRL with the rough CRL.

----------------

In Denis scenario I would suggest that we can exclude presence of a
rouge CA in the original certificate path, because if the original cert
path has a rouge CA, then all bets are off anyway.

-----------------

So the main question is which of these threats that is in scope or out
of scope 

2) The ability of the attacker to fool the RP to pick a rouge path and
rouge CRL where the IDP and CDP match.

Questions/remarks:
- If both these threats are in scope then Julien's scenario is also
valid.
- If there threats are out of scope, then what threat remains that
requires Santosh algorithm in the first place?

I'm still pro Santosh algorithm since it limits complexity in path
processing but it would be good to know if there are any threats that
require Santosh algorithm which remains if at least problem 1 above is
out of scope.

Stefan Santesson

---

From: Peter Sylvester <[email-masked]>
Date: Wed, 10 Nov 2004 15:26:00 +0100 (MET)

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 9 Nov 2004 16:07:06 -0500

Stefan,

-----Original Message-----
From: Santosh Chokhani [mailto:[email-masked]] 
Sent: Tuesday, November 09, 2004 3:44 PM
To: [email-masked]'
Subject: RE: Briefing on CRL Path for IETF PKIX WG Meeting

Stefan,

-----Original Message-----
From: Stefan Santesson [mailto:[email-masked]] 
Sent: Tuesday, November 09, 2004 2:06 PM
To: Denis Pinkas; Santosh Chokhani; Julien Stern
Cc: [email-masked]
Subject: RE: Briefing on CRL Path for IETF PKIX WG Meeting

----------------

-----------------

Questions/remarks:

Stefan Santesson