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

From: "Santosh Chokhani" <[email-masked]>
Date: Sat, 6 Nov 2004 12:12:36 -0500

Julien,

One more thing.

Even in your example, only the certificates related to hierarchy underneath
the rouge CA will be screwed it.  Even if you relied on the rouge CA, the
name matching algorithm will be robust with respect to the other PKI
hierarchies.

The proposal does prevent the attack since DN1 and DN 3 are not the same.
Hence CRL certification path will not match that of the certificate
certification path.  Please look at the check under the first bullet in
slide 12.

-----Original Message-----
From: Santosh Chokhani [mailto:[email-masked]] 
Sent: Saturday, November 06, 2004 11:56 AM
To: 'Julien Stern'; [email-masked]'
Subject: RE: Briefing on CRL Path for IETF PKIX WG Meeting

Julien,

A CA is not permitted to issue certificates to two distinct entities with
the same name.  Your example violates this constraint.

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

Santosh,

See response in-line.

On Fri, Nov 05, 2004 at 04:07:08PM -0500, Santosh Chokhani wrote:
> 
> Julien,
> 
> The algorithm proposed specifically eliminates the risk.
> 
> The certificate certification path and the CRL certification path will
> not match because CRL certification path has the node VeriSign CA in 
> it and the certificate certification path has the node real_VersiSign 
> CA in it.
> 
> May be you mean that the two CAs have really the same DN.  Well, in
> that case, the algorithm makes sure that all the DNs of the CAs in the 
> two paths match (one for one) starting with the DN of the trust 
> anchor.  So, in order for the attack to work, a CA in the system must 
> have certified two distinct CAs for the same subject DN.  If a CA does 
> that, all bets are off.
> 
> Please look at the algorithm closely.  It is match two different
> paths.

Well, I might be wrong, be I believe my scenario is NOT eliminated by your
proposal.

You say that your assumption is that a CA in the system must not certify two
distincts CAs for the same subject DN. Which would be:

     CA1
     DN1
    /   \
  CA2   CA3
  DN2   DN2

In the scenario I envisionned, the "graph" would be:

    CA1        ROGUECA
    DN1          DN3
     |          /   \
    CA2       CA3   CA3  <- CA3 is a single CA with Cert and CRL keys
    DN2       DN2   DN2
    KEY1      KEY1  KEY2

Now, I have a legitime certificate EE issued by CA2, with DN2 and KEY2. The
path building algorithm has TWO choices to reconstruct the path (well unless
specific helper extensions are used, but we should not rely on them for
security), namely:

    CA1        ROGUECA
    DN1          DN3
     |          /   \
    CA2       CA3   CA3  <- CA3 is a single CA with Cert and CRL keys
    DN2       DN2   DN2
    KEY1      KEY1  KEY2
       \      /      |
         \  /        |
          EE      Fake CRL

If it goes on the "left" side, you proposal prevents the attack. If it goes
on the "right" side, you proposal does not, because the CRL has a match for
all the ancestors. Consequently, we are in a situation where the same
certificate will be seen as revoked or not depending on the first path
chosen by the path building algorithm, which is believe is bad.

> Also, look at the extension that cryptographically binds the CA's keys
> to the CRL.
> 
> BTW, Step 2 should not happen in a PKI.  A CA must not bind a public
> key to a wrong subject (specially, when the subject is a CA).  This is 
> one of the reasons we require proof of possession of a private key.  
> But, even with Step 2 that no CA would do, the algorithm will not let 
> another claim to be you.

I agree step 2 should not happen. I guess that if I could possibly convince
a CA to give a a CA cert with Verisign DN, I could also convince it to
"forget" to verify the POP :)

But serioulsy, I believe that such a RogueCA can indeed publish fake CRLs
that would be validated even by your improved algorithm.

Please let me know if you believe I overlooked something

Sincerely,

--
Julien

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]] On Behalf Of Julien Stern
> Sent: Friday, November 05, 2004 1:38 PM
> To: [email-masked]
> Subject: Re: Briefing on CRL Path for IETF PKIX WG Meeting
> 
> 
> 
> All,
> 
> I believe X509 and PKIX are even much more flawed with respect to CRL
> validation that underligned by Santosh. The flaw appear as soon as it 
> valid to sign a certificate and a CRL with different keys.
> 
> I think the flaw CANNOT be solved without modifying the existing
> certificates or simply disallowing these different keys. Let me 
> explain:
> 
> We all agree that a CA is defined by name. However, if two CAs have
> the same name, one of them may be able to revoke the other CA 
> certificates. I believe we agree on this flaw of X509 and RFC3280, but 
> I think the algorithm proposed by Santosh does not change the 
> situation.
> 
> The flaw is more severe and is due to the fact that, when
> a CA is using two different certificates for signing certificate and
> signing CRLs, they are unrelated. In order to solve the flaw, we need 
> to link these two certificates by an other mean that the ancestors. 
> Actually, we probably need to sign the CRL signing certificate with 
> the certificate signing certificate.
> 
> More precisely, if a CA, _any_ CA, whose certificate validates with
> respect to one of your Trust Anchor, agrees to deliver me a 
> certificate whose DN is the same DN as Verisign, I will easily be able 
> to revoke all Verisign certificates.
> 
> The simple attack goes as follow:
> 
> 1) Find any moderately honest CA who agrees to sign me a certificate
> signing certificate and a CRL signing certificate whose DNs match 
> Verisign DN.
> 
> 2) For the certificate signing certificate, send a CSR whose public
> key matches the _real_ Verisign CA certificate.
> 
> 3) For the CRL signing certificate, send a CSR whose public key
> correspond to a private key I know.
> 
> 4) Finally, simply revoke any legitimate Verisign user by producing
> CRLs signed with this private key.
> 
> A path building algorithm will have two choices to go up when
> validating a Verisign certificate, (that is, two certificate with 
> matching DN and key). It it chooses mine, then, the path building 
> chain will go up to the same TA as the chain coming from my CRL and 
> all the DNs will match.
> 
> Conclusions:
> 
> - The current CRL checking algorithm is flawed
> - Santosh proposal solves some problems but unfortunately, not all
> - A possible way to solve the problem would be:
> 
> 1) Simply disallow different keys for certificate and CRL signing
> 2) If different keys are allowed, then the CRL signing key MUST be 
> signed with the certificate signing key with an appropriate delegation 
> extension (aka ~ indirect CRLs)
> 
>

---

From: "Julien Stern" <[email-masked]>
Date: Sun, 7 Nov 2004 00:08:32 +0100

Santosh,

I understand the name matching algorithm. However, you assume that the
path builder will pick the path
EE -> CA2 (DN2/KEY1) -> CA1 (DN1)

whereas it could AS WELL pick the path
EE -> CA3 (DN2/KEY1) -> ROGUECA (DN3)

which is as valid as the first one.
In that case, the name matching algorithm will perfectly work, 
because the CRL path is
FakeCRL -> CA3 (DN2/KEY2) -> ROGUECA (DN3)

The whole idea of the attack is that a rogue CA can produce a
certificate which matches the DN and KEY of an existing cert.
Of course, this certificate will be useless, because the private
key will not be known, but it may allow to fool the path building
algorithm into following an other path as the intended one.
If it does, it can leverage the fact that there is no cryptographic
binding between the cert and CRL key to produce a fake CRL.
If the path algorithm indeed follows my (valid!) but rogue path,
then the CRL will match.

--
Julien

---

From: "Santosh Chokhani" <[email-masked]>
Date: Sat, 6 Nov 2004 20:31:25 -0500

Julien,

The rogue PKI hierarchy can get around the certificate and CRL being signed
using the same key by simply re-issuing the legitimate end entities
certificates and then revoking or not revoking certificates.

EE legitimate key certified by CA3 (DN2/KEY2) -> CA3 (DN2/KEY2) -> ROGUECA
(DN3)

Now using DN2, KEY2 to sign CRL will provide crypto binding and still fool
you.

The basic point is if a relying party trusts a rogue trust anchor, PKI
security will go to hell.

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

On Sat, Nov 06, 2004 at 12:12:36PM -0500, Santosh Chokhani wrote:
> 
> Julien,
> 
> One more thing.
> 
> Even in your example, only the certificates related to hierarchy 
> underneath the rouge CA will be screwed it.  Even if you relied on the 
> rouge CA, the name matching algorithm will be robust with respect to 
> the other PKI hierarchies.
> 
> The proposal does prevent the attack since DN1 and DN 3 are not the 
> same. Hence CRL certification path will not match that of the 
> certificate certification path.  Please look at the check under the 
> first bullet in slide 12.

Santosh,

I understand the name matching algorithm. However, you assume that the path
builder will pick the path EE -> CA2 (DN2/KEY1) -> CA1 (DN1)

The whole idea of the attack is that a rogue CA can produce a certificate
which matches the DN and KEY of an existing cert. Of course, this
certificate will be useless, because the private key will not be known, but
it may allow to fool the path building algorithm into following an other
path as the intended one. If it does, it can leverage the fact that there is
no cryptographic binding between the cert and CRL key to produce a fake CRL.
If the path algorithm indeed follows my (valid!) but rogue path, then the
CRL will match.

--
Julien

> A CA is not permitted to issue certificates to two distinct entities 
> with the same name.  Your example violates this constraint.
> 
> > The certificate certification path and the CRL certification path 
> > will not match because CRL certification path has the node VeriSign 
> > CA in it and the certificate certification path has the node 
> > real_VersiSign CA in it.
> > 
> > that case, the algorithm makes sure that all the DNs of the CAs in 
> > the two paths match (one for one) starting with the DN of the trust 
> > anchor.  So, in order for the attack to work, a CA in the system 
> > must have certified two distinct CAs for the same subject DN.  If a 
> > CA does that, all bets are off.
> > 
> Well, I might be wrong, be I believe my scenario is NOT eliminated by 
> your proposal.
> 
> You say that your assumption is that a CA in the system must not 
> certify two distincts CAs for the same subject DN. Which would be:
> 
>      CA1
>      DN1
>     /   \
>   CA2   CA3
>   DN2   DN2
> 
> Now, I have a legitime certificate EE issued by CA2, with DN2 and 
> KEY2. The path building algorithm has TWO choices to reconstruct the 
> path (well unless specific helper extensions are used, but we should 
> not rely on them for security), namely:
> 
>     CA1        ROGUECA
>     DN1          DN3
>      |          /   \
> If it goes on the "left" side, you proposal prevents the attack. If it 
> goes on the "right" side, you proposal does not, because the CRL has a 
> match for all the ancestors. Consequently, we are in a situation where 
> the same certificate will be seen as revoked or not depending on the 
> first path chosen by the path building algorithm, which is believe is 
> bad.
> 
> > Also, look at the extension that cryptographically binds the CA's 
> > keys to the CRL.
> > 
> > key to a wrong subject (specially, when the subject is a CA).  This 
> > is one of the reasons we require proof of possession of a private key.
> I agree step 2 should not happen. I guess that if I could possibly 
> convince a CA to give a a CA cert with Verisign DN, I could also 
> convince it to "forget" to verify the POP :)
> 
> But serioulsy, I believe that such a RogueCA can indeed publish fake 
> CRLs that would be validated even by your improved algorithm.
> 
> > I believe X509 and PKIX are even much more flawed with respect to 
> > CRL validation that underligned by Santosh. The flaw appear as soon 
> > as it valid to sign a certificate and a CRL with different keys.
> > 
> > certificates. I believe we agree on this flaw of X509 and RFC3280, 
> > but I think the algorithm proposed by Santosh does not change the 
> > situation.
> > 
> > signing CRLs, they are unrelated. In order to solve the flaw, we 
> > need to link these two certificates by an other mean that the 
> > ancestors. Actually, we probably need to sign the CRL signing 
> > certificate with the certificate signing certificate.
> > 
> > certificate whose DN is the same DN as Verisign, I will easily be 
> > able to revoke all Verisign certificates.
> >

---

From: "Julien Stern" <[email-masked]>
Date: Sun, 7 Nov 2004 17:00:46 +0100

Santosh,

The ROGUE CA will indeed be able to issue a certificate to a user and
revoke this very certificate that it has issued, which is perfectly
normal, because it actually issued it.
This behavior is not even "rogue": a EE certificate can have two
different CAs certifying him.

The unintended behavior I was underligning was that, in the context I
described, the rogue CA can revoke existing EE certificates issued by
an other CA.

> security will go to hell.

I was not talking about a rogue TA, I was talking about a rogue CA
possibly low in the hierarchy that could impersonate (CRL wise) an other
CA in a totally unrelated hierarchy.

As soon as there is a Rogue CA, PKI security goes to hell. But this
should be limited to the tree under this Rogue CA, and not affect all
the unrelated hierarchies as it is the case now.

--
Julien

---

From: "Santosh Chokhani" <[email-masked]>
Date: Sun, 7 Nov 2004 13:36:25 -0500

Julien,

X.509 and 3280 does not make any claim to security once you start trusting
rogue CAs.

The rogue CA behavior is limited to its tree.  Once, it creates a
certificate for another CA, the rest of the tree becomes part of its tree,

If you used the rule that the certificate and CRL must be signed by the same
key, that will not protect you since the rogue CA will move down the
hierarchy one step and issue the certificates to the relying parties
directly and revoke them, in effect achieving the same effect.

That is why I am saying that there is no secure way to provide security once
there is a rogue CA in the relying party trust chain.

The basic point is that in light of rogue CA, even the requirement that the
certificate and CRL be verified using the same public key does not protect
the relying party.  I assume you agree with that scenario.

Thus, all solutions are equally unsecure when the relying party ends up
trusting a rogue CA, which is what you expect.  That is why CAs need to be
trusted.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On
Behalf Of Julien Stern
Sent: Sunday, November 07, 2004 11:01 AM
To: [email-masked]
Subject: Re: Briefing on CRL Path for IETF PKIX WG Meeting

On Sat, Nov 06, 2004 at 08:31:25PM -0500, Santosh Chokhani wrote:
> 
> Julien,
> 
> The rogue PKI hierarchy can get around the certificate and CRL being 
> signed using the same key by simply re-issuing the legitimate end 
> entities certificates and then revoking or not revoking certificates.
> 
> Now using DN2, KEY2 to sign CRL will provide crypto binding and still 
> fool you.

Santosh,

The ROGUE CA will indeed be able to issue a certificate to a user and revoke
this very certificate that it has issued, which is perfectly normal, because
it actually issued it. This behavior is not even "rogue": a EE certificate
can have two different CAs certifying him.

The unintended behavior I was underligning was that, in the context I
described, the rogue CA can revoke existing EE certificates issued by an
other CA.

> security will go to hell.

I was not talking about a rogue TA, I was talking about a rogue CA possibly
low in the hierarchy that could impersonate (CRL wise) an other CA in a
totally unrelated hierarchy.

As soon as there is a Rogue CA, PKI security goes to hell. But this should
be limited to the tree under this Rogue CA, and not affect all the unrelated
hierarchies as it is the case now.

--
Julien

> path builder will pick the path EE -> CA2 (DN2/KEY1) -> CA1 (DN1)
> 
> certificate which matches the DN and KEY of an existing cert. Of 
> course, this certificate will be useless, because the private key will 
> not be known, but it may allow to fool the path building algorithm 
> into following an other path as the intended one. If it does, it can 
> leverage the fact that there is no cryptographic binding between the 
> cert and CRL key to produce a fake CRL. If the path algorithm indeed 
> follows my (valid!) but rogue path, then the CRL will match.
> 
> --
> Julien
> 
> > 
> > > The flaw is more severe and is due to the fact that, when a CA is 
> > > using two different certificates for signing certificate and 
> > > signed with the certificate signing key with an appropriate 
> > > delegation extension (aka ~ indirect CRLs)
> > > 
> > > 
> > 
> > 
> 
>