On Verifying Identity Using Cryptography

One of the most important uses of cryptography these days is verifying the identity of the other side of a digital conversation. That conversation could be between two people using OTR-encrypted IM, a web browser showing a bank website, a Debian Developer uploading a package to the Debian build server, an ssh client logging into an ssh server, and on and on. In all of these cases, cryptography is used to ensure that the software is indeed receiving replies from the expected entity. This happens by checking the current cryptographic key against one that is known to be correct. That is essential to the whole process. If you see the key for the first time, you have no way of knowing whether that is indeed the key you are expecting because there is no point of reference.

In order for this validation of identity to work, there needs to be a method of verifying any given key and making it a reference. There are many ideas about how to do this:

  • a trusted list of central certificate authorities like in HTTPS
  • key-signing parties where people validate and sign each other’s keys in person, like used with the OpenPGP Web of Trust
  • “trust on first use” (aka “Persistence of Pseudonym”), where you save the key the first time you see it, and then use that as a reference (this is the way most people use SSH)
  • fingerprint verification, where the two people wanting to communicate cryptographically use another channel to manually check each other’s key fingerprints, like a phone call (this is used a lot in OTR and OpenPGP)
  • the Socialist Millionaires’ Protocol (SMP), which is a combination of user-generated question/answer pairs with a cryptographic technique that lets each side confirm whether the other answered the question correctly without divulging any information (this was recently added to OTR and is implemented in Pidgin, Gibberbot, and maybe a couple other programs)
  • a manually confirmed shared secret like a short password (ZRTP uses this when starting secure phone calls)
  • whitelists of fingerprints of widely used keys (aka public key pinning) (this was recently added to Chrome in the wake of the HTTPS certificate authority failures)

Each of these techniques has its advantages and disadvantages, but generally the higher level of verification provided means the more work to do the process. Most people don’t need the high level of verification provided by OpenPGP key signing parties, but maybe if it was fun and much easier to do, then a lot more people would do it. “Trust on first use” is really easy to use and implement, and has been working pretty well for a lot of people who use SSH and OTR. But it has big shortcomings in environments where the state or other central authority that provides the internet infrastructure wants to spy on its users. HTTPS has proven to be quite easy to use, but it has also proven to be quite breakable.

Currently, each of these techniques described above is used as the sole means of verification, then the level of verification is represented as “verified” or “not verified”. This is definitely the way that HTTPS and SSH handle it. OTR is a bit different, it has 3 states of verification: “new key”, “unverified key” i.e. trusted on first use, or “verified”, and good OTR chat apps will represent these three states in the UI. Then OpenPGP is perhaps the opposite extreme: it provides both chains of verification signatures via the Web of Trust but also user-set “trust levels” from 0 to 255 for any given key.

Perhaps an answer is to cryptographically link up these different ways of verification and represent key verification as a continuum. Then when the possibility of linking in “trust on first use” and other techniques was there, people could gradually build up cryptographic trust as they needed it. Starting with “I have seen this key before”, then on to “I have gotten them to verify their OTR key with an SMP question/answer”, then to “I have an OpenPGP trust path to them”, to “I have met them in person and manually verified their key and identity”.

To go into technical detail as an example, GnuPG supports RSA, DSA, ECDSA, El Gamal, and other key types as subkeys for an OpenPGP key. Those core algorithms core basically all of the most common uses of cryptography, including HTTPS, SSH, OTR, and OpenPGP. The link between an OpenPGP key and its subkeys is perhaps the strongest link for verification that exists, so if a given person includes their OTR key, for example, into their OpenPGP key, that provides a strong cryptographic link between them, and one that is easily publicly sharable via the OpenPGP public keyservers. When two people verify their OTR keys using the SMP question/answer, this verification could then extend to their OpenPGP keys if their OTR keys were subkeys. (The Monkeysphere Project is one such implementation of this idea, using OpenPGP keys for SSH and HTTPS).

Then the last piece of this puzzle is how to represent all of this complexity to the users. The essential part is to stop representing trust as binary yes/no. A one-dimensional continuum provides a lot more info and is a very commonly understood concept in computers (think progress bars). The hard part of this question is ranking the various techniques in how much progress they provide towards the goal of solid identity verification.

For this round of the PSST Project, we have focused on first allowing people to easily move around their OTR identities, then worked on testing out the idea of linking in all identity keys into an OpenPGP key. From what we have seen so far, we believe this is not only feasible but will provide a solid platform for linking together all these verification techniques and identity keys. And on top of that, with diligent attention to user experience and testing, it should be possible to create user interfaces that make navigating all of this a common, daily task for most computer users.

2 comments for “On Verifying Identity Using Cryptography

  1. 2012/04/04 at 4:35 am

    OpenPGP keysigning is largely deprecated at this point, because it’s a) so difficult to use that almost no one who really needs the protection (activists and journalists) has the level of technical background required to understand how it works, let alone the many, many ways that it can fail, and much more importantly, b) because it reveals the entire social graph of everyone you might potentially be interested in exchanging encrypted email with. A global observer may be able to conveniently acquire much of this information anyway, but there’s no reason to collect it for them and anyone else who wants to look in a single, easily queryable place. While handling the verification of multiple identities is important, explicitly linking all of those identities in a public manner is not necessarily a good idea.

  2. hans
    2012/04/04 at 12:40 pm

    You bring up some important points. Encryption in general is far too difficult to use. And the OpenPGP Web of Trust does indeed have very strong privacy concerns since the keysigning is expected to be published to public servers. But the Web of Trust does provide a decentralized means for loosely affiliated community members to establish trusted communications between each other, something that no other commonly used technique can provide.

    I would not say that the Web of Trust is deprecated, but rather not applicable to many communities. If you look at Debian development, then you’ll see a case where the OpenPGP Web of Trust is thriving, and indeed required for that model of distributed development. Many people are not sensitive to the privacy concerns of publishing social graph information publicly. Facebook is a great example of that.

    We are planning to address both the difficulty and the privacy concerns in our GPG for Android app that is in the works. For the privacy concerns of the Web of Trust, we plan on using the “lsign” feature of GnuPG which allows for local, unpublishable signatures on keys. GPG will not publish these signatures to the public keyservers. In order to then restore the Web of Trust, we are currently thinking of making our GPG app able to swap key validation signatures from directly person to person. This would not provide ultimate privacy, since you would rely on the holders of your signatures to respect your privacy wishes. It would provide some level of Web of Trust without having the information published publicly.

    That is just one idea, we are interested in hearing more along these lines, and of course comments and criticisms on these ideas.

Leave a Reply

Your email address will not be published. Required fields are marked *