Subject: RE: Reverse paths

From: [email-masked] (Peter Gutmann)
Date: Fri, 21 Jul 2000 04:52:35 (NZST)

Sharon Boeyen <[email-masked]> writes:

>However, once you start connecting hierarchies together, e.g. through bridge
>CAs and once you moved out of hierarchies into distributed trust models, that
>condition no longer holds true. As bridges become more common and the
>certificates issued to and by bridges increases, the number of potential paths
>becomes quite large.

I had a long talk with some people a few weeks back about how to write code to
display cert chains in the presence of bridge CA's, and it turns out to be an
almost unsolveable problem because the bridges turn a hierarchy of trust into a
spaghetti of trust (I won't use the PGP term "web of trust" because PGP was
designed for this model and handles it reasonably well, whereas X.509 wasn't
and doesn't - I'm not trying to start a PGP flame war here, just pointing out
that X.509 was never intended to work this way).

The result is that instead of cert decisions being "yes" or "no", they become
"probably" (there may be another path which says otherwise) and "maybe" (again,
there may be another path which says otherwise).  Since you can never know
where all the paths lead or if you've examined all of them, you can never
really know whether you're making a valid decision based on the information
you've got (this is a generalisation of the original problem, which was "how
the *#^&$ can we display this mess in a meaningful manner?").

For example, if I start by collecting my set of initial policy identifiers and
find a cert for which I don't have a path leading to a member of the policy
set, this doesn't mean that the cert isn't acceptable, merely that I haven't
found one of the fifteen other paths to another CA which could end in an
acceptable policy.  Revocation is even messier ("It's revoked!  Not it isn't!
Yes it is!").

Has anyone ever done an analysis of the potential mess bridge CA's are leading
into, or was it just tacked onto the side of the original hierarchical model as
a quick fix?  (I've seen a paper which tries to formally model PKIX path
processing and finds that it's somewhat problematic once you try to create a
precise, formal spec rather than the informal description in the RFC, there are
some things which actually require the informal spec because they can't be
specified in a precise, formal manner).

As a subset of this question, how *do* you display the spaghetti of trust in a
meaningful manner?

Peter.

---

From: Paul Koning <[email-masked]>
Date: Thu, 20 Jul 2000 13:12:35 -0400 (EDT)

>>>>> "Peter" == Peter Gutmann <[email-masked]> writes:

 Peter> ...  (I've seen a
 Peter> paper which tries to formally model PKIX path processing and
 Peter> finds that it's somewhat problematic once you try to create a
 Peter> precise, formal spec rather than the informal description in
 Peter> the RFC, there are some things which actually require the
 Peter> informal spec because they can't be specified in a precise,
 Peter> formal manner).

A program (algorithm) is a precise formal specification, so does what
you say mean that the RFC cannot be translated into an algorithm?
That would be a problem, indeed...

     paul

---

From: Steve Hanna <[email-masked]>
Date: Thu, 20 Jul 2000 14:34:42 -0400

> the *#^&$ can we display this mess in a meaningful manner?").

Even in a hierarchical trust model, it is often difficult to say definitively "there is no valid
certification path from point A to point B". Especially if there exist certificates that you don't
have. All you can say is "I didn't find a valid path" or "I did find a valid path". However, this
should be sufficient for most purposes (IPsec, SSL, S/MIME, etc). If you're able to find a valid path,
you can proceed. If not, you must fail safe.

This is similar to the behavior if you're trying to determine revocation  status for a certificate
using CRLs and you can't find a current CRL that covers that cert. All you can say is "I don't know if
this certificate has been revoked." Of course, you should fail safe and reject the certificate in this
circumstance.

As to how you can display the network of trust in a mesh topology, X.500 DNs provide a nice hierarchy.
Certificates are directional arcs between nodes in the tree. Trust anchors can be displayed as arcs
from the RP to the trusted party (in a different color, if you like).

Of course, this doesn't represent the namespace of subject alternative names. Nor does it handle the
case where two distinct CAs (or EEs) have the same name or a single CA (or EE) has multiple keys that
have been separately certified. Like most visualizations, it's a simplification.

-Steve

---

From: Stephen Kent <[email-masked]>
Date: Thu, 20 Jul 2000 18:05:58 -0400

Steve,

<snip>

>from the RP to the trusted party (in a different color, if you like).

Experience with user behavior says that displaying cert paths is 
almost worthless.  Almost nobody will view them, and few would be 
able to understand the implications of such paths if they did view 
them.

<snip>

---

From: Tony Bartoletti <[email-masked]>
Date: Thu, 20 Jul 2000 18:18:28 -0700

At 06:05 PM 7/20/00 -0400, Stephen Kent wrote:
>Experience with user behavior says that displaying cert paths is almost 
>worthless.  Almost nobody will view them, and few would be able to 
>understand the implications of such paths if they did view them.
>
><snip>

Actually displaying the mesh to users, I hope, would not be the issue.

Rather, given the mesh can be uniquely represented in "memory", can
one write software that can reply accurately to queries of the form
"Is there a path from A to B that satisfies my set of constraints?"

And would the behavior of such a tool become intractably slow (as it
certainly must on a general graph with many nodes, and most painfully
if each "satisfies constraints" requires a net-fetch from a directory.)

___tony___

Tony Bartoletti 925-422-3881 <[email-masked]>
Information Operations, Warfare and Assurance Center
Lawrence Livermore National Laboratory
Livermore, CA 94551-9900

---

From: Stephen Kent <[email-masked]>
Date: Fri, 21 Jul 2000 09:46:05 -0400

Tony,

>if each "satisfies constraints" requires a net-fetch from a directory.)

Even if the user doesn't have to visually examine a complex cert 
path, I think all evidence to date suggests that users will not be 
amenable to formulating queries to pose to underlying software of 
this sort.

Steve