I ended up writing a lot of text in response to this post, so, I am
breaking up the response into three mini-responses.
Part I
On 1/18/2012 4:23 PM, Brian Smith wrote:
> Sean Leonard wrote:
>> The most glaring problem however is that when validation fails, such
>> as in the case of a revoked certificate, the API returns no
>> certificate chains
>
> My understanding is that when you are doing certificate path
building, and you have to account for multiple possibilities any any
point in the path, there is no partial chain that is better to return
than any other one, so libpkix is better off not even trying to return a
partial chain. The old code could return a partial chain somewhat
sensibly because it only ever considered one possible cert (the "best"
one, ha ha) at each point in the chain.
>
For our application--and I would venture to generalize that for all
sophisticated certificate-using applications (i.e., applications that
can act upon more than just "valid/not valid")--more information is a
lot better than less.
I have been writing notes on Sean's Comprehensive Guide to Certification
Path Validation. Here's a few paragraphs of Draft 0:
Say you have a cert. You want to know if it's "valid". How do you
determine if it's "valid"?
A certificate is "valid" if it satisfies the RFC 5280 Certification Path
Validation Algorithm. Given:
* a certification path of length n (the leaf cert and all certs up to
the trust anchor--in RFC 5280, it is said that cert #1 is the one
closest to the trust anchor, and cert n is the leaf cert you're validating),
* the time,
* "policy-stuff", <-- hand-wavy because few people in the SSL/TLS world
worry about this but it's actually given a lot of space in the RFC
* permitted name subtrees,
* excluded name subtrees,
* trust anchor information (issuer name, public key info)
you run the algorithm, and out pops:
* success/failure,
* the working public key (of the cert you're validating),
* "policy-stuff", <-- again, hand-wavy
and anything else that you could have gleaned on the way.
But, this doesn't answer the obvious initial question: how do you
construct "a certification path of length n" if you only have the
initial cert? RFC 5280 doesn't prescribe any particular algorithm, but
it does have some requirements (i.e., if you say you support X, you MUST
support it by doing it Y way).
"Certification Path Construction" is where we get into a little bit more
black art and try to make some tradeoffs based on speed, privacy,
comprehensiveness, and so forth.
Imagine that you know all the certificates ever issued in the known
universe. Given a set of trust anchors (ca name + public key), you
should be able to draw lines from your cert through some subset of
certificates to your trust anchors. What you'll find is that you've got
a big tree (visually, but not necessarily in the computer science sense;
it's actually a directed acyclic graph), where your cert is at the root
and the TAs are at the leaves. The nodes are linked by virtue of the
fact that the issuer DN in the prior cert is equal to the subject DN in
the next cert, or to the ca name in the trust anchor.
Practically, you search the local database(s) for all certificates that
match the issuer DN in the subject. If no certificates (or in your
opinion, an insufficient number of certificates) are returned, then, you
will want to resort to other methods, such as using the caIssuers AIA
extension (HTTP or LDAP), looking in other remote stores, or otherwise.
The ideal way (Way #1) to represent the output is by a tree, where each
node has zero or more children, and the root node is your target cert.
In lieu of a tree, you can represent it as an array of cert paths
(chains) (way #2). Way #2 is the way that Microsoft
CertGetCertificateChain validation function returns its results,
more-or-less.
Once you have all of these possibilities, you'll want to start pruning,
which involves non-cryptography (e.g., checking for basic constraints),
actual cryptography (digital signature verification), and more
non-cryptography (e.g., time bounds and name constraints). The general
received wisdom is to start verifying signatures from the trust anchor
public key(s) down to the leaf, rather than the other way around,
because otherwise an attacker can DoS your algorithm by putting in a
99999999 bit RSA key or some such. Incidentally, this is also one
argument why "unknown/untrusted issuer" is much worse than some folks
want to assume, but I understand that is a sensitive point among some
technical people so the main point is that you have to provide as much
of this information as possible to the validation-using application
(Firefox, Thunderbird, Penango, IPsec kernel, whatever) so that the
application can figure out these tradeoffs. If you keep it in the tree
form, you can eliminate whole branches of the tree. Eliminate could mean
a) don't report the path at all, or b) report the path anyway but stop
reporting the litany of all possible errors associated with each point
along the path.
Each node in the tree (i.e., each cert along each path) can suffer from
a multiplicity of problems. For example, it can be expired AND revoked
AND have bad formatting AND have an improper key usage AND violate the
name constraints. (Note that things like expired and violate name
constraints are path-dependent, so although you have one tree, you
actually have all this different state information based on each unique
path through the mountain of certs to the trust anchors.) Some of these
are obviously "really bad" but there are judgment calls that each
application needs to make on its own merits.
To save time, you can eliminate certificates in the "universe" or in the
first non-cryptography step, rather than in the post-cryptography step.
For example, if a "certificate" is not actually proper ASN.1 or has some
pathological problem like an extension that is not DER-encoded, you
could just say "well, that's not a real certificate" and exclude it from
the universe. Likewise, all certificates are potentially end-entity
certificates but not all certificates are CAs. If the cert is a v3 cert
and lacks basicConstraints or has basicConstraints CA=FALSE, you could
simply eliminate that from your universe of certs you will even consider
using for path construction. That is one of several examples where a
single bit is trivialized by a lot of implementations, which leads to
long-running exploits (e.g., the Apple iOS basicConstraints exploit,
although many other crypto stacks made the same mistake). When the CA
bit(s) are off, *it's not even a CA certificate*, so don't even bother
to give it a second look or attempt to put it in the path. What is an
application (or worse, a user) supposed to do--ignore that error?? [Cf
SEC_ERROR_CA_CERT_INVALID]
To conclude this section, if you have a path (e.g., from TLS) and you
care about speed, Certificate Path Construction isn't of much worry to
you: you just run the validation algorithm and call it a day. But if you
care about being comprehensive, you are not doomed to slowness: you can
optimize cleverly. CERT_PKIXVerifyCert permits either alternative
(cert_pi_certList) although I note that Firefox does not seem to use it,
probably because for compatibility and other reasons it does not assume
that the TLS server provided all the certificates in the right order.
libpkix/CERT_PKIXVerifyCert shows evidence that much of the above has
been taken into consideration. Other areas of NSS, like DB performance
as DB size increases (for the v8 DB--or, you could just switch to the v9
DB) are probably more important to optimize.
-Sean
--
dev-tech-crypto mailing list
dev-tech-crypto@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-tech-crypto
