X.509 Public Key Infrastructure Mechanism Overview — a bottom-up approach

Public key infrastructures plays an important role in our everyday lives, from internet browsing to secure transmission of sensitive materials. Among common PKIs, X.509 is currently the most popular and the default choice. Today, we’ll talk about how it works.

Overview

Here’s a brief view of what we’re going to cover

• Asymmetric Schemes
• Digital Signatures
• X.509 Overview
• Certificate Structure
• Certificate Validation
• Certificate Chain

Asymmetric Themes

Generally speaking, an asymmetric theme fits the following criterias:

1. Has a keypair consisting of a public key and a private key
2. Includes a one-way method using one of the keys that is possible to reverse if and only if the other key in the set is provided

As you can see in the image, the asymmetric key pair (the one mentioned before) has ability to (left) encrypt data with the public key that is only decryptable by the private key in the same key pair, and/or (right) encrypt data with the private key that is only decryptable by the public key in the same key pair.

Here’s are some of the most common used themes:

• RSA: The most commonly used encryption theme currently used in relevant industries, this algorithm utilizes prime number pairs to fit the asymmetric criteria, you can read more about it here
• DSA: It works similar to RSA, but it is optimized to be faster at signing efficiency(in contrast to RSA verifying faster), wiki link
• ECC: A much newer, but gradually accepted set of algorithms. ECC relies on “curves” with specific mathematic properties. Some notable curves are: curve25519(popular, but only provides 128-bit security), NIST-Pxxx series (available key-sizes: 256, 384, and 512 bits, but with security concerns of several preselected “magic numbers”), Brainpool-Pxxx series (available key-sizes: 256, 384, 521 bits, NIST-P variant without “magic numbers”, but with much slower speed)

Note: the most secure popular curve is currently Brainpool-P521

Comparison chart of key sizes on RSA and ECC, and the security they provide:

Digital Signatures

So, here’s a common question that we often ask ourselves, how do we “sign” something online? To make it work, the “signing” action must fit two major criteria:

1. The signature is unforgeable
2. Anyone can verify what you signed

There is a main difference between traditional signatures on paper and their digital counterparts. When signing on a piece of paper, copying/moving the signature to another piece of paper is a rather tricky thing to do. However, digital signatures can be copied/moved easily, hence, each signature must uniquely correlate to the contents of the signed file/text.

In order to do this, asymmetric themes are applied to complete a process called digital signatures.

simple flowchart for digital signatures

As featured in the image, our scenario consists of two people, Alice and a random person, Bob. The goal is for Alice to sign a digital document such that any random Bob can verify that Alice signed the digital document and that Alice is the only person possible to have created that particular signature for the exact document.

Here’s how it works:

Prerequisite: Alice generates an asymmetric keypair and publishes the public key on a key server or a public place/website and saves the private key in a secure location.

1. Alice uses a one-way hash function(such as SHA, md5,…) to produce a digest of the document.
2. Alice then encrypts the digest with the private key generated before and appends the encrypted digest to the original document.
3. Alice publishes the encrypted-digest-appended document.

Now, some random Bob sees the signed document and tries to verify it.

1. Bob extracts the signature from the document and requests Alice’s public key from the key server.
2. Bob decrypts the encrypted digest with Alice’s public key.
3. Bob uses the same one-way hash function to produce the digest of the document(without the signature included).
4. Bob compares the digest from step 2 and step 3 to check if they are equal. The signature verifies if they are, and fails if they are different.

X.509 Overview

Now we have a reliable method of signing and verifying digitally, we’ll start talking about public key infrastructures.

X.509 workflow

Component definitions:

• certificate authority: a trusted third-party that manages certificates
• certificate revocation LDAP: a LDAP server that is used to publish revoked certificates
• server: a service provider that hopes to provide services to end users
• end user: a user of the service provided by the server

To make it more easy to comprehend, we’ll use a webserver and a browser as the server and end user respectively.

Here’s how it works

Assumptions:

1. The certificate authority’s certificate is included in the root certificate list of the browser(the actual list of certificate authorities), hence we skip the diagonal step 0.
2. The certificate authority routinely publishes revoked certificates on the certificate revocation LDAP

Steps:

1. The certificate authority issues a certificate to the webserver(this is kind of step 0 as well, since certificates are not single-use and certificate requests only happen once in a few years)
2. The user connects to the webserver with his/her browser. The browser starts a three-way handshake with the webserver, first validating the signature of the server’s certificate along the way.
3. The browser checks with the certificate authority’s revocation LDAP to see if the certificate was revoked.
4. Browser encrypts “premaster secret” with the public key included in the server’s certificate and sends it over

Note: In order to make it easier to understand, I skipped several steps of the TLS three-way handshake and only focus on the parts concerning certificates

Certificate Structure

So basically, X.509 certificates consist of a public key and information on the keyholder, certificate authority, and the certificate itself. Normally, the structure is as follows:

Certificate
  Version Number
  Serial Number
  Signature Algorithm ID
  Issuer Name
  Validity period
    Not Before
    Not After
  Subject name
  Subject Public Key Info
    Public Key Algorithm
    Subject Public Key
  Issuer Unique Identifier (optional)
  Subject Unique Identifier (optional)
  Extensions (optional)
    ...
Certificate Signature Algorithm
Certificate Signature

X.509 certificates can generally be categorized into three types of certificates

• end-entity certificate: certificate issued to a service provider(such as the webserver mentioned in the example)
• intermediate certificate: a certificate that is able to issue a child certificate, while being issued by a upstream certificate
• root certificate: the root issuer with no upstream certificate

Samples of all three certificate types can be found here on Wikipedia. Please pay extra notice to the “extensions” section, we’ll cover more about this in the certificate chain section.

Certificate Validation

Other than the signature, a standard validation of a certificate also contains:

• issuer name: check if matches the name of the upstream authority
• name constraints: check if the name of the current entity is allowed by upstream authority
• policy OID constraints: validate OID of policies
• pathlength: pathlength defines the maximum nested layers of child entities allowed(for instance, a certificate with pathlength 0 cannot issue a child certificate, a certificate authority must have a pathlength larger than 0), the pathlength of the upstream authority is checked to see if the current certificate is allowed to be issued
• validity period: checks if the certificate is within date
• revocation status: checks with the upstream authority’s LDAP to see if the certificate has been revoked

Certificate Chain

X509 extensions:
  X509v3 Subject Key Identifier:
    xx:xx…
  X509 CRL Distribution Points:
    Full Name:
    URI:http://xxx/xxx.crl
  Authority Information Access:
    OCSP - URI:http://xxx/xxx
  X509 Authority Key Identifier:
    keyid:xx:xx:xx …

First, let’s take a look at the extensions section in a certificate:

• subject key identifier: key id of the public key in the current certificate
• CRL distribution points: url of the certificate revocation list LDAP for this certificate
• authority information access: url to get upstream certificate
• authority key identifier: key id of the public key in the upstream certificate

Let’s go through how a end user constructs and verifies a certificate chain

1. The end user validates fields in the certificate that do not require the upstream certificate.
2. The end user checks local cache for a cached certificate with the same key id as the one specified in authority key identifier. If no such certificate exists, the end users requests the certificate with the authority information access specified in the certificate.
3. The end user then finishes validation of the certificate (CRL is checked with the information on CRL distribution point specified in the certificate)
4. After validating the base certificate, the end user then repeats steps 1–3 on the upstream certificate forming a “chain” of certificates until the end of the chain is reached.
5. The end of the chain is a certificate that does not specify any authority fields in the extensions section. That particular certificate will be checked with trusted root certificates stored on the end user’s machine. If the certificate matches one of the trusted root certificate, the whole certificate chain validates.

Final Word

We’ve successfully covered the basics of X.509 and related mechanisms. It’s a simple overview, but I hope it provides a brief overview of the topic. Please feel free to provide suggestions. Claps and follows are appreciated!!

💌 Get In Touch

For questions, or just to say hi, feel free to reach out to me on Twitter @ruisiang_tw or drop me an email at hi@rs.me.