Sean, The "Path Building" logic/requirements/concerned you described is best described within RFC 4158, which has been mentioned previously.
As Brian mentioned in the past, this was 'lumped in' with the description of RFC 5280, but it's really its own thing. libpkix reflects the union of RFC 4158's practices and RFC 5280's requirements. As you note in your spreadsheet, libpkix already implements the majority of 5280 (at least, the "important to browsers" / "commonly used in PKIs including Internet PKIs"). While libpkix tries for some of 4158, it isn't exactly the most robust, nor is 4158 the end-all and be-all of path building strategies. I believe that over time, it would be useful (ergo likely) to implement some of the scoring logic described in 4158 and hand-waved at by Microsoft's CryptoAPI documentation, rather than its current logic of just applying its checkers to see if the path MIGHT be valid in a DFS search, so that libpkix returns not just a good path, but a close-to-optimal path, and can also provide diagnostics for the paths not taken. Ryan > 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 > -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
