Public Authentication

Published 2014-07-30

The public authentication problem is one we have all learned to solve with intuition: How do I decide to trust a new person? We ask for introductions from mutual acquaintances, or find their LinkedIn profile, or even do a few searches on Google. For those of us who lean to being introverts, it’s a little stressful, but we all manage.

For computer systems, it’s a harder problem: the information from an impostor can be made to exactly mimic a legitimate system. Since computers can’t make intuitive leaps or weigh risks, the answers to the authentication problem must be mathematical.

Cryptography to the Rescue

Asymmetric cryptography, pioneered in public life by Ron Rivest, Adi Shamir and Leonard Adleman in 1977, provides a way to mathematically prove the identity of another entity.

There are numerous explanations of the mechanics of digital signature algorithms like the one published by Rivest, Shamir and Aldeman, so I won’t go into the details of its function. Generally though, it allows this logical leap:

1. If I have a certificate that identifies Computer A, and
2. If I ask Computer A to prove that it is legitimate, then
3. If Computer A has the key that corresponds to the certificate, then
4. I can use the certificate to prove Computer A has the corresponding key.

Using this concept, cryptographers have designed two techniques to prove that a new computer system is legitimate: Public Key Infrastructures, and Webs of Trust.

Public Key Infrastructures

A Public Key Infrastructure (a PKI) is built around the concept of a Trusted Third Party which issues the certificates above. The Trusted Third Party is called a Certificate Authority, and it can be thought of as a kind of notary: it is trusted to only issue certificates to legitimate computers.

Individuals in the PKI start their digital lives trusting a small set of Certificate Authorities, typically the list is maintained by their computer vendor. As long as the Certificate Authorities are trustworthy and charge a reasonable fee for issuing certificates, the system works.

Functionally, when an individual (computer) encounters a new computer system, it verifies that its certificate was issued by one of the trusted Certificate Authorities; this can be done without interrupting the user to make a decision. This is how the Web works today.

Unfortunately, several CAs have been compromised.

Webs of Trust

Another approach is to let every individual (computer) decide how trustworthy a new computer system is at the first encounter, and to share with each other a list of all other encountered systems, trusted or not.

When you encounter a computer system for the first time, you first analyze all the lists you’ve collected from other systems, and the lists they have collected, and play something akin to six degrees of separation. Depending on how deep you have to dig to find a relationship, and how much you trust the intermediate relationships, determines if the new computer system is trustworthy.

Webs of Trust, like that used by PGP/GPG, are free and mimic human behavior, but they make it hard to fix problems when they show up; the graph theory can become quite complex.