insanity::pkix: A New Certificate Path Building & Validation Library

September 25th, 2013

[Note July 9th, 2015: I am sharing this for historical interest. It was originally written near the beginning of the now-sensitively-named mozilla::pkix project. It was an introduction of the project to people in the Mozilla community, especially people who were “concerned” about it. The original, private, version of this document went into much more detail about what is wrong with existing X.509 libraries, but most of that was removed before it was shared with people outside of Mozilla Corp. I did not make any changes to this public version of the document other than fixing formatting, spelling, and grammar mistakes. Some of it is quite out of date. For example, Firefox has been using mozilla::pkix for a whole year now, and mozilla::pkix no longer has any hard dependencies on NSS and can now be used with any crypto library.]

insanity::pkix is a new certificate verification library that fixes some longstanding problems with Firefox’s current certificate validation code. It provides a solid foundation for future work to improve Firefox’s PKI support. We will replace Firefox’s current certificate verification logic with usage of insanity::pkix as soon as code review and testing is completed.

Beyond Firefox, I hope that insanity::pkix will be able to serve as a reference implementation for new simpler and more secure PKI specifications, including replacements for RFC 5280, RFC 4158, RFC 5019, and RFC 6960. I would like also like to work with other open source projects—Apache Web Server, Chromium, nginx, NSS, and OpenSSL, in particular—to help them integrate insanity::pkix into their client-side and server-side software, with the goal of improving interoperability and security internet-wide. To facilitate such sharing, insanity::pkix is licensed under the Apache License 2.0, a BSD-like non-copyleft license that is compatible with the copyleft MPL 2.0 license that Gecko, NSPR, and NSS are licensed under.

Before we get to the point where insanity::pkix can serve as a reference implementation for any specification, and before we integrate it into other projects, we need to make sure it works. Although we have written a lot of tests and are still doing more testing, the biggest test of whether insanity::pkix works will be when we enable it in Firefox as the default way of verifying certificates.

We would like to help people inside and outside of the Mozilla community test insanity::pkix, to ensure that it is as correct as possible before it ships to hundreds of millions of Firefox users. Please send email to the Mozilla dev-tech-crypto mailing list or email me directly at brian@briansmith.org or if you would like to help.

Already-implemented Improvements over Firefox’s Current Certificate Processing

insanity::pkix implements the following improvements over the NSS-based certificate processing Firefox currently uses:

Improved path building for improved compatibility: Firefox currently (before insanity::pkix) does certificate path building in a very simplistic way that results in it failing to verify valid paths in some cases where there are multiple candidate certificates with the same name. insanity::pkix does a depth-first traversal over all the possible certificate chains similar to what RFC 4158 recommends, which resolves this issue.
Much easier to understand, maintain, and improve: The insanity::pkix codebase clocks in at less than 5,000 lines of code that has been written with readability as a key concern. The NSS certificate validation code clocks in at over 90,000 lines of code that is very difficult to understand and even more difficult to modify.
Flexible and pluggable certificate trust handling and crypto: The NSS code is hard-coded to use NSS’s certificate trust databases and NSS’s crypto primitives. insanity::pkix abstracts out both of these aspects into a pluggable interface called TrustDomain that allows the application to use whichever certificate trust database and/or whatever crypto library it chooses. (In its current state, insanity::pkix does still have some hard-coded dependencies on NSPR and NSS. I encourage people to submit patches to help complete this abstraction work.)
Improved key usage and extended key usage validation: insanity::pkix will allow Firefox to better enforce the key usage and extended key usage restrictions in server’s certificates, because insanity::pkix allows the application to validate certificates for the exact key usages and exact extended key usage needed. Further, insanity::pkix allows extended key usage restrictions to be applied by any certificate in the certificate chain, not just the end-entity.
Memory usage and speed improvements: insanity::pkix is designed to use very little memory and to be as efficient as possible, while still optimizing the code for readability. The optimization work on insanity::pkix is not done yet and there is still room for improvement in this area.

Potential Future Improvements

The new, easier-to-maintain code should make it much easier for us to implement long-overdue enhancements to current PKI standards, such as OCSP must-staple, Certificate public key pinning, revocations pushed to the browser, better enforcement of secure public key sizes, Certificate Transparency, intermediate CA whitelisting, ephemeral/short-lived certificates, externally-applied name constraints for CA certificates, server-side correction of broken certificate chains, and more.

Traditional PKIX Features Purposely Excluded

insanity::pkix intentionally avoids implementing several features found in some other certificate path validation libraries:

No CRL support (CRLDP and otherwise): RFC 5280 does not require implementations to support CRLs as a revocation mechanism. Firefox, in its default configuration, has never supported CRL fetching based on the CRLDP certificate extension, except for when it validates EV certificates. The CABForum Extended Validation guidelines now require OCSP support, so Firefox no longer needs to process CRLs for EV certificates. Further, there are numerous practical problems with CRL fetching as a revocation checking mechanism in a web browser, which I will detail in another document. Finally, CRL processing is one of the most complex parts of PKIX, and the implementation of insanity::pkix is greatly simplified by omitting support for them entirely.
No certificate fetching via the AIA id-ad-caIssuers field: Firefox, in its default configuration, has never supported fetching missing intermediate certificates over HTTP based on the contents of a certificates id-ad-caIssuers AIA field. This has caused some significant interoperability issues for Firefox, and some of the workarounds Firefox has implemented are admittedly problematic. However, AIA id-ad-caIssuers is a security, privacy, and performance footgun. This feature also requires CMS parsing and BER decoding, which would otherwise not be needed by a certificate verification library. We should put more effort into alternative solutions to improving these interoperability issues before resorting to implementing id-ad-caIssuers AIA support.
No DSA and ECDSA parameter inheritance: DSA parameter inheritance is a mechanism where, given a certificate A that chains to a CA certificate B, certificate A can omit some components of its public key with the intention that the verifier of the certificate will substitute the corresponding parameters from certificate B. This mechanism is problematic for public key pinning and seems to be rarely, if ever used on today’s web.
No certificate policy support beyond the minimum required to validate extended validation (EV) certificates.: Firefox in its default configuration, has never supported certificate policies beyond what is necessary for it to validatate EV certificates. This has not caused any practical problems for Firefox. Certificate policy processing is one of the most complex parts of PKIX and it is also one of the least helpful parts of PKIX for protecting users online. The subset of certificate policy supported needed to validate extended validation certificates is much simpler and more efficient to implement than full certificate policy support. Also note that RFC 5280 says that certificate policy mapping is an optional feature, so it was not implemented at all in insanity::pkix.
Limited error reporting: insanity::pkix is designed to tell the application whether a given certificate is valid, what certificate chain was used to make that determination, and nothing else. It does return distinct error codes for each different reason that it rejects a certificate, but it does not attempt to enumerate all the possible reasons for a certificate being rejected when a certificate has multiple problems. Also, it does not try very hard to rank certificate chains according to how bad they are. insanity::pkix’s error reporting should be just sufficient to classify errors into the categories that Firefox uses: name mismatch, expired, untrusted issuer, or un-overridable error. Avoiding more detailed error reporting helps make insanity::pkix efficient and easy to understand.
No UI support: insanity::pkix does not support parsing certificates into something readable by people. This saves a lot of complexity. Firefox already has support for parsing certificates into natural language form through NSS and it will continue to use NSS for this purpose.

Temporary Known Limitations

OCSP response signing certificates do not have their subject names constrained by name constraints. This is not a big deal because these names are not used for any security-critical purpose, but it should be fixed.
OCSP response signing certificates are not required to validate with respect to any certificate policy. NSS seems to have a similar issue. It is unclear whether it is a good idea to change this.
Name matching is too strict. Sometimes we may not find an issuer certificate that we should find because we require a certificate’s issuer name to match the subject name of the issuer certificate exactly. This is a limitation inherited from NSS and this is something we should fix soon.
insanity::pkix does not have a stable API, stable semantics, a C ABI, or support for being built as a shared library. All of these things are anti-features for Firefox. Once insanity::pkix has stabilized, we can figure out what, if any, stable interface we can provide for other (non-C++) projects to use.

About the Name

The “insanity” in insanity::pkix’s name is intended to draw attention to the fact that there are several aspects of PKIX that are unnecessarily complex and/or completely nonsensical. The name invites people working with it to ask “Why are we doing things this way? Shouldn’t we do something to improve this?”

The “::” in the name is to make it clear that insanity::pkix is purposefully based on C++. By using C++ features and idioms (e.g. RAII) and avoiding problematic C++ features (e.g. RTTI and exceptions), we have made the insanity::pkix code much easier to understand and correctly maintain.