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

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.

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.

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).

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?

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
Microsoft Security Center of Excellence (SCOE)

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 9 Nov 2004 15:43:52 -0500

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.

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].

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.

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

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?

[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: "Julien Stern" <[email-masked]>
Date: Wed, 10 Nov 2004 02:03:52 +0100

Stefan,

see my comments in-line with [JS].

> server holding the real CRL and replace the real CRL with the rough CRL.

[JS thanks for this nice summary of the situation (well, for my
threat at least, I'll let Denis comment on his).

At you said in the beginning of your email, I think we need to define
at least a minimal security and adversarial model.

I though that the strict separation of two different hierachies that
are not cross-certified could be a security goal.

I also though that the compromise of a CA is a plausible scenario,
and that it should not affect any other CA above it or in unrelated
hierarchy.

However, it is true that in practice, the attack is fairly difficult
to mount, even assuming a CA compromise.]

> require Santosh algorithm which remains if at least problem 1 above is

[JS: Santosh algorithm clearly renders the attack more difficult, and
may prevent mistake.

But what is does is ensuring that two certificates belong to
the same entities, assuming that the CAs in their respectives trust
path are uncompromised and never gave the same DN to two different
entities.

This algorithm can certainly be useful, for CRL, and maybe other things.
However, as I have shown, it only renders the attack harder, not
impossible. What we need is a algorithm that shows the certificates
belong to the same entity AND that this entity actually delivered
the certificate.

It my threat model is considered unrealistic, I'm also in favor
of Santosh algorithm. Otherwise, I think it is only a patch on a
security hole, and that we should find a way to actually plug this hole.

Maybe could we simply add an extension in the EE certificate specifying
the public key of the CRL Issuer ? The CA could simply and securely
delegate to his other key or to an other entity this way.]

--
Julien

---

From: "Julien Stern" <[email-masked]>
Date: Wed, 10 Nov 2004 02:17:29 +0100

Santosh,

comments in line with [JS]

On Tue, Nov 09, 2004 at 03:43:52PM -0500, Santosh Chokhani wrote:
> take on Julien's scenario.

> First, Julien's scenario will not come about for
> the relying parties who do not trust the rogue CA.

[JS: this is true, but the rogue CA could be anywhere in the hierarchy
of any trusted anchor. Also, if you assume no CA rogue CA is trusted, your
algorithm mostly only simplifies path construction.]

> Second, the algorithm
> perspective can only revoke the certificate.

[JS: the whole point being that it is simple to conterfeit the certicate
issuer from the relying party perspective. Trust in X509 in going down,
not up. This is how the attck works.]

> Third, even if the same key

[JS: it might be possible to perform an attack even when the same key is
used, but my current scenario does not. The attack would be much more
complex. It do not see to what scenario you refer to.]

> real CRL and replace the real CRL with the rough CRL.

[JS: it seems to me that you assume that you can force the use of a
CRL over an other for the attack you described work.

So the difference between our threat models, security wise, is that
you assume all CA are honests and never compromised but can make mistakes,
while I assume a CA can act in a dishonest way. It that correct ?]

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 9 Nov 2004 22:11:39 -0500

Julien,

The basic point is that there are many ways to compromise the security of
X.509 once a relying party trusts a rogue CA.  Path matching algorithm will
not fix that.  Whether you use the algorithm or not, these problems remain.
If you do not use the algorithm, there are attacks that will not be
mitigated.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On
Behalf Of Julien Stern
Sent: Tuesday, November 09, 2004 8:17 PM
To: [email-masked]
Subject: Re: Briefing on CRL Path for IETF PKIX WG Meeting

Santosh,

On Tue, Nov 09, 2004 at 03:43:52PM -0500, Santosh Chokhani wrote:
> 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.
> 
> [SC: This is only an issue in the context of indirect CRL.  For the 
> direct CRL issuer, the algorithm will disambiguate the issues].
> 
> [SC: I have not seen a scenario from Denis.  I have a different and 
> simple take on Julien's scenario.

> the relying parties who do not trust the rogue CA.

[JS: this is true, but the rogue CA could be anywhere in the hierarchy of
any trusted anchor. Also, if you assume no CA rogue CA is trusted, your
algorithm mostly only simplifies path construction.]

> Second, the algorithm
> makes sure that who ever is the certificate issuer from the relying 
> party perspective can only revoke the certificate.

[JS: the whole point being that it is simple to conterfeit the certicate
issuer from the relying party perspective. Trust in X509 in going down, not
up. This is how the attck works.]

> 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.]

> rouge CA in the original certificate path, because if the original 
> cert path has a rouge CA, then all bets are off anyway.
> 
requires
> [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.]

[JS: it seems to me that you assume that you can force the use of a CRL over
an other for the attack you described work.

So the difference between our threat models, security wise, is that you
assume all CA are honests and never compromised but can make mistakes, while
I assume a CA can act in a dishonest way. It that correct ?]

---

From: Denis Pinkas <[email-masked]>
Date: Wed, 10 Nov 2004 10:50:07 +0100

Stefan,

My comments with [DP: ]

( ... text relative to Julien deleted)

[DP: Thank you for the acknowledgment]

[Santosh: since you intercept every mail, I guess you will notice that 
Stefan mentions that your algorithm has indeed a problem].

[DP: No. In my scenario there is no intentional malicious
behaviour of the CRL issuer. Anybody can make an interception attack an 
substitute one CRL by another].

[DP: No. There is no notion of a "rough CRL". Both CRLs are real CRLs but 
issued by two CAs which happened to have the same DN (but these DNs have 
been given by two different CAs)]

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

[DP: Your suggestion would not work. It is not possible to exclude the fact 
that two CAs in a certification path may issue the same DN to two different 
CRL Issuers: when a CA is naming a CRL Issuer, it does not need to check if 
that name has been given or not by another CA from the chain.]

( ... remaining of text relative to Julien deleted)

Denis

---

From: "Julien Stern" <[email-masked]>
Date: Wed, 10 Nov 2004 02:17:29 +0100

Santosh,

---

From: "Julien Stern" <[email-masked]>
Date: Wed, 10 Nov 2004 02:03:52 +0100

Stefan,

--
Julien

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 9 Nov 2004 15:43:52 -0500

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

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 9 Nov 2004 22:11:39 -0500

Julien,

-----Original Message-----

Santosh,

requires

---

From: Denis Pinkas <[email-masked]>
Date: Wed, 10 Nov 2004 10:50:07 +0100

Stefan,

My comments with [DP: ]

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

Denis