# 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:

- If I have a
`certificate`

that identifies`Computer A`

, and - If I ask
`Computer A`

to prove that it is legitimate, then - If
`Computer A`

has the`key`

that corresponds to the`certificate`

, then - 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.