PKI (Public-key Infrastructure)

\( \def\ZZ{\mathbb{Z}} \def\GG{\mathbb{G}} \def\HH{\mathbb{H}} \)

Problem of distribution of public keys

In our discussion of public-key crypto, we have assumed users know each others' public keys. But how can public keys be reliably distributed?

Download the public keys from a web page? This will be insecure against man-in-the-middle attack.
Store the public keys in CD-ROM and give them in person? This solution may work but it's impractical in general.

One solution is to bootstrap new public keys from public keys you already know. That is, certificates vouch for binding of public keys to names.

Certificates

Using a certificate, party \( A \) can vouch for the public key of another party \( B \). In particular, we have \[{\sf Cert}(A \rightarrow B) = ({\sf info}_B, ~~ {\sf Sign}_{sk_A} ({\sf info}_B)),\] where \({\sf info}_B\) = ("B", \(pk_B\), ...).

Here, info can contain other administrative information such as expiration time, restrictions, etc. This can be viewed as as a directed edge in a graph:

If you know A's public key and trust its certification, you can learn B's public key.

Fig 1. Abstract view of a certificate issued by A for B

Warning: Be careful about distinguishing between the jobs of \(A\) and those of \(B\). What is \(A\) doing? What is \(B\) doing? Whose key is used in the signature?

Certificate chains

One can learn public key via multiple hops.

If you trust \(pk_A\) is \(A\)'s public key, and if you also trust its certification, then you trust that \(pk_B\) is \(B\)'s public key.
If you trust \(pk_B\) is \(B\)'s public key, and if you also trust its certification, then you trust that \(pk_C\) is \(C\)'s public key.

Obtaining certificates and certificate authorities (CAs)

A (trust-worthy) party that issues certificates are called a certificate authority. One can obtain ask a CA to create a certificate for its key as follows:

DoD and PKI

Check out the following figure (from https://public.cyber.mil/pki-pke/interoperability/).

X.509 Certificates

Here is an old certificate of Prof Choi that was in his CAC card. The format of this certificate follows the X.509 standard.

$ cat choi.cer
-----BEGIN CERTIFICATE-----
MIIEfjCCA2agAwIBAgIDQGAgMA0GCSqGSIb3DQEBBQUAMFcxCzAJBgNVBAYTAlVT
... (omitted) ...
UweOPpb8IbJu+MDGwuV3yxwtQjV9OMHQTJfP8anWwRlqillkGrYx0EBOiC/lnONu
xy6Q/KwF0nUStwvKVugFR/ODJ6U29UY8xqW1h+pfy+91tKkvwA4ATeXDNrWPvEno
J0FSlVvverZMIDPdxxiZEgvm7VfSBORmD+mW0nJuGHskq75WYiLNQUrAFeBBU7Cf
Cbs=
-----END CERTIFICATE-----

As you see above, it's a base64 encoded binary data. In Windows, you can click the file to check the details. You can also use openssl commands to see the details.

$ openssl x509 -in choi.cer -text -noout
Certificate:
  Data:
    Version: 3 (0x2)
    Serial Number: 4218912 (0x406020)
    Signature Algorithm: sha1WithRSAEncryption
    Issuer: C=US, O=U.S. Government, OU=DoD, OU=PKI, 
            CN=DOD CA-30
    Validity
      Not Before: Aug  8 00:00:00 2013 GMT
      Not After : Aug  7 23:59:59 2016 GMT
    Subject: C=US, O=U.S. Government, OU=DoD, OU=PKI, 
              OU=USN, CN=CHOI.SEUNG GEOL....
    Subject Public Key Info:
      Public Key Algorithm: rsaEncryption
        Public-Key: (2048 bit)
        Modulus:
          00:b8:9e:98:ae:bc:0b:f0:0c:f4:d1:22:17:bc:71:
          28:a7:e7:ab:3b:89:37:d9:94:30:8b:ae:78:50:e7:
          f9:30:09:ed:91:68:88:f5:e3:37:3a:69:af:d4:89:
          ...(omitted)...
          7c:b3:79:8e:58:da:f9:64:58:c3:ad:90:5f:95:7a:
          3c:79:82:31:54:6d:d7:87:68:61:8a:97:41:e2:58:
          3c:77:37:0c:ac:e0:ce:41:f9:40:c5:01:c5:b6:26:
          d4:4c:79:43:4f:eb:c2:e1:05:5c:65:ed:45:54:b0:
          a5:96:a9:28:d2:36:87:a7:f0:b0:e2:02:96:b6:76:
          0b:65:b0:60:15:ce:ad:a2:2f:99:aa:ea:cb:b5:3d:
          0d:21:e4:fa:1c:df:45:75:a8:f4:0d:b3:ac:7a:82:
          f2:63
        Exponent: 65537 (0x10001)
    X509v3 extensions:
      X509v3 Authority Key Identifier: 
        keyid:08:4E:D5:A4:...(omitted)...06:7C:0D:A3

      X509v3 CRL Distribution Points: 

        Full Name:
          URI:http://crl.disa.mil/crl/DODCA_30.crl

      X509v3 Key Usage: critical
        Digital Signature, Non Repudiation
      X509v3 Certificate Policies: 
        Policy: 2.16.840.1.101.2.1.11.9
        Policy: 2.16.840.1.101.2.1.11.19

      X509v3 Subject Key Identifier: 
        05:50:7E:FE:FF:4A:4D:...(omitted)...70:86:B9:FD:8A
      Authority Information Access: 
        CA Issuers - URI:http://crl.disa.mil/sign/DODCA_30.cer
        OCSP - URI:http://ocsp.disa.mil

      X509v3 Subject Directory Attributes: 
        0.0...+.......1...US
  Signature Algorithm: sha1WithRSAEncryption
     8f:91:a9:03:5c:29:75:83:c6:2c:c1:2a:0e:25:61:32:3a:5d:
     e8:f7:cd:6f:94:4f:7b:25:02:d9:98:71:db:70:12:3d:7b:f1:
     86:7d:71:c4:06:14:c2:a0:41:01:4c:9d:3a:86:0e:43:87:79:
     ...(omitted)...
     72:6e:18:7b:24:ab:be:56:62:22:cd:41:4a:c0:15:e0:41:53:
     b0:9f:09:bb

1. Data

Here, version is the version of X.509 standard, and the serial number is the number that the CA assigns this certificate among many certificates it signed.

Signature algorithm

Dr. Choi's signature algorithm is Hashed RSA that we learned, where hash is SHA-1. It's an old certificate using SHA-1 which is not secure any more.

Issuer

Issuer contains the information of the certificate authority who issued this certificate. Here, C stands for country, O stands for organization, and OU stands for organizational unit, and CN stands for common name. Usually, what's most important is CN.

Validity

The certificate has expired.

Subject

Subject contains the information of the party that owns the certified public key. In this case, it's Dr. Choi.

Subject Public Key Info

This shows the subject's public key, that is, Dr Choi's public key. The algorithm is based on RSA, and the public key consists of two numbers \( (N, e) \), where Modulus corresponds to \( N \), and Exponent corresponds to \( e \).

X509v3 extension

X509 version 3 allows extended pieces of information to be contained in the certificates.

The authority key identifier extension provides a means of identifying the public key corresponding to the private key used to sign a certificate. This extension is used where an issuer has multiple signing keys.
X509v3 CRL Distribution Points is used for revocation. CRL means certification revocation list. He will discuss this more later.
The key usage extension defines the purpose (e.g., encipherment, signature, certificate signing) of the key contained in the certificate. When this extension appears, it should be marked critical.

The subject key identifier extension provides a means of identifying certificates that contain a particular public key. For end entity certificates, this provides a means for identifying certificates containing the particular public key used in an application.
The authority information access extension indicates how to access CA information and services for the issuer of the certificate in which the extension appears. You can get the certificate of CA from CA Issuers by going to http://crl.disa.mil/sign/DODCA_30.cer (invalid now). The result can be seen here

2. Signature Algorithm

This is the actual digital signature created by CA on the message, which is the Data section above.

Revocation

Certificates do not last forever. After some time interval specified in the certificate (i.e., set by the CA), certificates expire. Alternatively, they can be revoked for any number of reasons, including if the private key is believed to have been compromised. Expiration and revocation seem straightforward, but they're not.

Certificates can become invalid in one of two ways.

They can expire; all certificates include an expiration date, after which they may not be used. There are three reasons for expiration.
1. First, there is the sense (often a vague sense) that after a certain period of time, the likelihood of an undetected compromise of the private key has become unacceptably high.
2. The second reason for certificate expiration is that cryptographic algorithms age. Recall that MD5 and SHA-1 are broken now.
3. Finally, certificates expire to ease bookkeeping with respect to revocations.
They can be revoked, that is to say, explicitly declared to be invalid. This may be done because of private key compromise, suspected or actual misbehavior by the holder of the private key, etc.

Certificate Revocation List (CRL)

A party accepting a certificate can check for revocation in two different ways. The older mechanism uses a Certificate Revocation List (CRL), a file of revoked certificates signed by the issuing CA; the URL of this list is included in certificates. Those of a certain age may recall store clerks looking up credit cards in a book-format blacklist; conceptually, this is the same thing, save that CRLs include the time of the next update, to provide warning of stale revocation lists.

In X.509 certificates, we saw the following:

  X509v3 CRL Distribution Points: 

    Full Name:
      URI:http://crl.disa.mil/crl/DODCA_30.crl

Visiting the above URL gives us the CRL list. The file can be parsed as follows:

> openssl crl -in DODCA_30.crl -inform DER -text -noout

The result can be seen here.

Issues of CRL

Inefficiency: Every CA maintains CRL, and there are several hundred CAs. This means that each client should download lots of lists. Sometimes, it's large. Moreover, whenever the client visits a webpage, it should check if the CRL is newly updated, and then if the site it is visiting is in the list. This is quite the pain.
Denial-of-service attack : There has been denial of service attacks to prevent folks from learning of newly-revoked certificates. (What will happen if a host cannot download the CRL?)
Equally clearly, rejecting all presented certificates under those circumstances is very unlikely to be correct. Today, systems that use revocation lists typically ignore these denial-of-service risks and hope for the best.

Other approaches

In another approach, OCSP (Online Certificate Status Protocol) is used to verify the continuing validity of a certificate, rather than whether or not it was every valid. The obvious analogy is a modern credit card terminal. OCSP can return "not revoked", "revoked", or "unknown" status codes.

Finding a better approach to deal with revocations is still an on-going battle. See here.

Issues With PKI: Too much trust on two many CAs

Do you know how many CAs we trust? In my laptop, I have about 400 CAs to trust! Do you know those CAs? If not, how do you trust them?

Hacked: DigiNotar (2011) and Comodo (2011) In 2011, CA, DigiNotar, was hacked and its private signing key stolen, allegedly by parties linked to the government of Iran (or maybe the NSA). More than 100 different company names are represented (because of assorted mergers and acquisitions, it's difficult to tell just how many companies are actually involved), from 49 different countries. More than 30 of the certificates are explicitly listed as belonging to agencies of national governments.
Comodo reported that a user account with an affiliate registration authority had been compromised which was used to create a new user account that issued nine certificate signing requests. Nine certificates for seven domains were issued.
- login.live.com
- mail.google.com
- www.google.com
- login.yahoo.com (3 certificates)
- login.skype.com
- addons.mozilla.org
- "Global Trustee"
The attack was traced to IP address 212.95.136.18, which originates in Tehran, Iran.
Signature forgery: Microsoft (2012) In 2012, according to Microsoft, the authors of the Flame malware used an MD5 collision to forge a Windows code-signing certificate.
Accident: HP (2014) HP signed a malware by accident.
Bad Intermediate CAs: CNNIC (2015) Google discovered that CNNIC (China Internet Network Information Center) had issued an intermediate CA certificate to an Egypt-based firm that used CNNIC's keys to impersonate Google domains. Google responded by removing CNNIC's root certificate from the certificate store in Google Chrome and all of Google's products.

Common CA Database (CCADB)

To tackle the issues of rogue CA's, Mozilla manages the public CCADBi. Chrome has a similar program, and it seems to refer to CCADB.

See below the most recent blog article Here's the first a couple of paragraphs:

In keeping with our commitment to the security and privacy of individuals on the internet, Mozilla is increasing our oversight and adding automation to our compliance-checking of publicly trusted intermediate CA certificates (“intermediate certificates”). This improvement in automation is important because intermediate certificates play a critical part in the web PKI (Public-Key Infrastructure).

Intermediate CA keys directly sign server certificates, and we currently recognize nearly 3,000 intermediate certificates, which chain up to approximately 150 root CA certificates embedded as trust anchors in NSS (Network Security Services) and Firefox.

More specifically, we are updating the Mozilla Root Store Policy (MRSP) and associated guidance, improving the public review of third-party intermediate certificates on the Mozilla dev-security-policy list, and enhancing automation in the Common CA Database (CCADB).