[security-area] Fwd: How ambiguous are names in actuality?

[Von Welch]

An interesting note from Tim Polk on ambiguous names in
PKIs. Unfortunately it doesn't apply to the types of PKIs we use in
Grids since it assume a single trust anchor that cross certifies all
peers.

Von

------- start of forwarded message -------
From: Tim Polk <tim.polk at nist.gov>
To: ietf-pkix at imc.org
Subject: How ambiguous are names in actuality?
Date: Thu, 14 Jul 2005 14:24:00 -0400



Ambiguity has recently become a hot topic on this list.  This is a really 
complicated issue, and I have personally had a great deal of trouble 
sorting out the real level of risk.  Some of the proposed changes would 
greatly impact current software, and these changes should only be 
contemplated if the risk is merits such change.

So, I have spent a lot of time, off and on, thinking about ambiguity.  I 
can't claim to have sorted it all out, but I have convinced myself that one 
minor change is absolutely required, and that the current suite of 
mechanisms can virtually eliminate ambiguity in real PKIs.

My thinking is appended to this message;  I apologize for its length, but 
to paraphrase Mark Twain, I simply don't have time to make this short and 
concise.  I have attempted to define ambiguity, characterize the ways 
ambiguity can enter into a PKI, and describe the set of mechanisms that 
mitigate this risk.

Thanks,

Tim Polk

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

              How ambiguous are names in actuality, and how important is it?

I believe that X.509 expected assignment of unambiguous names based on a 
hierarchical system of naming authorities.  Whether you agree with that 
premise, it is safe to say that the global X.500 directory and its 
corresponding system of naming authorities do not exist. So, it may not be 
safe to assume that there are no name collisions whatsoever in all the DNs 
that appear in certificates and CRLs!  I am sure such collisions exist 
somewhere (although I haven’t encountered any examples).  The real question 
here is “What security risk does this situation present, and are the 
current mechanisms adequate to address this risk?”

Let’s recognize that the goal for PKIX is not to have globally unambiguous 
names, but to be able to obtain a trustworthy public key to establish a 
security service. Ambiguity in names is a problem when it causes the 
relying party to trust the wrong public key.

There are two ways ambiguous names could cause problems.  First, I could 
accept public keys from two certificates as representing the same person 
based on the same subject name.  If these two certificates are bound to 
different individuals I may provide a service to the wrong party (or 
disclose confidential data, etc., etc.)  Second, I could accept a CRL to 
validate a particular certificate, based on the same issuer name in the 
certificate and CRL.  If the certificate and CRL were not actually issued 
by the same CA, then the relying party may obtain incorrect certificate status.

Note that both of these problems are in the context of path validation.  If 
a name collision exists, but only one of the objects (e.g., certificate or 
CRL) validates for a given relying party, then there is no actual ambiguity 
from that relying party’s point of view.

That is, assume two certificates exist with the same subject name but are 
bound to different people.  If Alice can only validate one of those 
certificates, there is no ambiguity in Alice’s world.   Similarly, if Bob 
can only validate one of those certificates, there is no ambiguity in Bob’s 
world.   (It does not matter if Bob and Alice are validating the same 
certificate, or different ones!)   Similarly, if two CAs have the same 
issuer name, but Alice can only validate one, she can’t accept the wrong 
CRL.  Ditto for Bob.

So, ambiguity is a concern only in the context of path validation for a 
given relying party. This means that the mechanisms that are employed in 
path validation are relevant to when names are, and are not, ambiguous. I’d 
also like to point out that path validation is always performed in the 
context of a particular trust anchor.  (A relying party may accept paths 
that begin with multiple trust anchors, but each specific path has a single 
trust anchor.)  Seems irrelevant at the moment, but I will get back to it!

Definition 1:  a Name N is unambiguous for a trust anchor T if and only if 
all certificates that validate for T and have the subject N refer to the 
same entity.

Now, let’s think about where name collisions can occur in the first place. 
There seems to be consensus that a single CA will not issue two 
certificates to two different entities with the same subject name.  So, if 
a single CA issues two certificates to “O=Microsoft, cn=John Wilson” they 
better relate to the same guy.  Similarly if a particular CA issues two 
certificates to “c=US, O=U.S. Government, OU=NIST, CN=CA1” then the subject 
of both certificates must be the same CA.

So, we are only worried about the case where two different CAs are trusted 
with respect to a trust anchor T and issue certificates to different 
subjects but use the same name.  So, when can name collisions occur between 
CAs?  Or, better yet, under what conditions can we be sure name collisions 
won’t occur?  Let’s start with user certificates.

In general, each CA that issues user certificates does so for a particular 
name space.  That is, all names assigned to users will be in a particular 
Directory Information Tree (DIT).   The CA will either work with a naming 
authority that it considers authoritative or may assume that function 
itself.   For example, the NIST CA only issues user certificates in the 
“C=US, O=U.S. Government, OU=NIST” DIT.   The NIST CA has been designated 
as our naming authority as well, so it keeps track of the names it 
assigns.  Similarly, the CA that supports NASA only issues certificates for 
the name space “C=US,  O=U.S. Government, OU=NASA” DIT.

These name spaces are disjoint, so name collisions cannot occur involving 
user certificates generated by the NASA and NIST CAs.  In fact, consider a 
PKI with trust anchor T and CAs C(1), C(2), …, C(n) issuing for name spaces 
P(1), P(2), …, P(n).  If spaces P(1), P(2), …, P(n) are pairwise disjoint, 
name collisions cannot occur involving user certificates generated by C(1), 
C(2), …, C(n).

Case 1:  Consider a PKI with trust anchor T, and CAs C1, C2, and C3.  C1, 
C2, and C3 issue end user certificates in the DITs N1, N2, and N3 
respectively.  If N1, N2, and N3 are pairwise disjoint, then the user names 
are unambiguous with respect to T.

In more complex PKIs, we may encounter situations where CAs issue user 
certificates for name spaces that overlap.  For example, in the U.S DoD’s 
hierarchical PKI, CAs all issue certificates in the DIT “C=US, O=U.S. 
Government, OU=DOD”.  Users routinely receive three certificates from two 
different CAs, so all the DoD CAs rely on a common naming authority to 
ensure that certificates with the same DNs are issued to the same person.

Case 2: Consider a PKI with trust anchor T, and CAs C1, C2, and C3.  C1, 
C2, and C3 issue end user certificates in the DITs N1, N2, and N3 
respectively.  N1 and N2 overlap, but N3 is disjoint from N1 and N2.   If 
CA1 and CA2 recognize the same naming authority, then the user names in the 
PKI are unambiguous with respect to T.

That is, if all the CAs either: (1) issue certificates in disjoint name 
spaces, or (2) issue certificates in shared name spaces based on a common 
naming authority, names will be unambiguous!

Of course, CAs may issue CA certificates as well.  In this case, the CA 
does not assign the names, but rather uses the established name.  This is 
trickier, since the name spaces for CA certificates overlaps but no naming 
authority exists.  It is still the responsibility of each CA to ensure that 
there are no name collisions in CA certificates it issues!  This is not 
generally a problem, since we require names to be meaningful.  A CA should 
never issue a certificate to a CA with the DN “C=US, O=Coca Cola” unless 
the subject CA is associated with that company.  Similarly, if a CA issues 
certificates in the DIT “C=US, O=Coca Cola” then it must be associated with 
the company!

Of course, a rogue CA may masquerade under the wrong name, or issue 
certificates in a DIT it clearly has no right to use, but no decent CA will 
cross certify with it.  Since we are interested in ambiguity with respect 
to a trust anchor, the behavior of a rogue CA is irrelevant.  Without cross 
certification, no paths involving the rogue CA can be constructed.  (Note 
that users installing the rogue as a trust anchor is out of scope here!)

However, authority for a name space is not always crystal clear.  Without a 
central naming authority, there is no clear title for a particular DIT.  We 
rely on heuristics that work nicely for large entities like Coca-Cola but 
may fail for smaller organizations.  For example, there may be a number of 
companies with variants on a particular name.  If the name space assumed by 
an organization asserts “Orion” rather than “Orion Security” or “Orion 
Space Sciences”, the name may be ambiguous without being blatantly 
false.  Each entity could reasonably assign user names in the “C=US, 
O=Orion” DIT.   If each organization established their CA with the name 
“C=US, O=Orion, CN=CA1” things could get really ugly.

A trust anchor T may cross certify with two different CAs – say the ones 
from NIST and NASA.  Each of those CAs may have a relationship with an 
“Orion”.  If each of them cross certifies with the Orion they know and 
love, we have an immediate name collision for a CA named “C=US, O=Orion, 
CN=CA1”, and potentially name collisions for “C=US, O=Orion, CN=John 
Wilson”, etc., etc.  Each CA has played by the rules, but names have just 
become ambiguous with respect to T.  This might be avoided if T is involved 
in the policy decisions leading up to cross certification – but that is 
often NOT the case.

Fortunately, we need not depend on policy alone.   Beyond the 
procedural/policy issues, there are some important mechanisms that help us 
with name space control.  Most significant are path length constraints and 
name constraints.  When trust anchor T issued those CA certificates, it 
probably wasn’t expecting to accept transitive trust from those CAs, and it 
certainly didn’t expect to accept the NIST or NASA CA as authoritative for 
the “C=US, O=Orion” DIT.

I listed path length constraints first because this mechanism provides the 
simplest and most widely available of our technical controls. Both NASA and 
NIST use a single CA, rather than a mesh or hierarchy.  If the trust anchor 
does not wish to leverage other cross certifications performed by NASA or 
NIST, it simply asserts a path length constraint of zero!  If T asserted 
this constraint for at least one of the NIST or NASA CAs, then the name 
“C=US, O=Orion, CN=John Wilson” is unambiguous. While this control was not 
designed exclusively for name space control, it does have the effect of 
prevenmting subsequent CAs from introducing unexpected name spaces.

Unfortunately, this does not solve our problem for “C=US, O=Orion, 
CN=CA1”.   This name remains ambiguous.  Even with a path length 
constraints of zero, a relying party can validate a CRL from either Orion CA.

Name constraints is a more appealing technical mechanism, if less 
consistently available.  T can explicitly designate the name spaces it 
wishes to recognize in the cross certificate issued to NIST (or NASA).  By 
asserting a permitted subtree of “C=US, O=U.S. Government, OU=NIST” with a 
SkipCerts of zero, certificates in the Orion name space are immediately 
eliminated.  This includes the offending CA certificate, so the “wrong” CRL 
no longer validates.

Case 3: Consider a PKI with trust anchor T, and CAs C1, C2, and C3.  C1, 
C2, and C3 issue end user certificates in the DITs N1, N2, and N3 respectively.

N1 and N2 are disjoint, but  N3 overlaps with N1 or N2.  C3 does not 
recognize the same naming authority as C1 or C2.   If name constraints 
permitted subtrees P3 is imposed in all cross certificates issued to C3, 
where N1, N2, and P3 are pairwise disjoint, then names are unambiguous with 
respect to T.  (Names that could have collided are excluded from C3’s DIT.)

Conclusion/Proposal

Ambiguity in names is a relatively minor risk with respect to a given trust 
anchor.  Ambiguity does not occur because of the actions of a single CA; 
rather it requires a combination of actions by different CAs within the 
infrastructure.  If all CA certificates accurately reflect the trust 
relationships between the CAs by incorporating appropriate path length and 
name constraints, these risks are greatly reduced if not eliminated.

The risk of ambiguous names can be mitigated with a relatively simple 
modification in 3280bis, and the addition of some security 
considerations.  Most importantly, 32890bis should be modified to ensure 
that certificate and CRL validation are always performed with respect to 
the same trust anchor.  Security considerations should be added to 
highlight the risk of issuing CA certificates without appropriate 
constraints, and to caution application developers that trust anchor 
information should be considered when accepting certificates.

The changes that I believe should be implemented are as follows:

  (1) Modify section 6.3.3 to state that CRL validation MUST use the same 
trust anchor T specified in the corresponding certification path.

(2) Add security considerations that indicate applications that accept 
multiple trust anchors should consider the trust anchor in access control 
decisions to ensure that names are unambiguous.

(3) Add security considerations that explain the importance of consistent 
use of path length and name constraints in preventing name ambiguity.

------- end of forwarded message -------