A Novel Regular Format for X.509 Digital Certificates

Digital certificates are one of the key components to ensure secure network communications. The complexity of the certificate standard, ITU-R-X.509, has led to a number of breaches in the TLS protocol security due to certificate misinterpretation by TLS libraries. We argue that the root cause of such an issue is the complexity of the certificate structure, which can be gauged with the framework of formal language theory: the language describing digital certificates is context sensitive. Such a complexity led to handcrafted X.509 parsers, resulting in implementations which are not guaranteed to perform correct language recognition. We highlight the issues in X.509, and propose a new format for digital certificates, designed to be parsed effectively and efficiently, while retaining the same semantic expressiveness. The certificate format can be deployed gradually, is fully specified as a regular language, and is specified as a formal grammar from which a provably correct parser can be automatically derived. We validate the effectiveness of our proposal, and the linear running time provided by the approach, generating an instance of the parser with a production grade lexer/parser generation framework.