One of the most problematic aspects with public key cryptography is the necessity for key verification. If Alice has a key that she thinks is from Bob, how does she know that it really is from Bob and not from Mallory who is trying to do a man-in-the-middle attack? With PGP, te traditional solution to this problem has been either to do manual fingerprint verification using an out-of-bound channel or to use the web-of-trust. Out-of-band verification is pretty safe, but is quite cumbersome. Generally you have to compare 80 hexadecimal digits with each other (one for Alice's key and one for Bob's) before being able to trust the communication. This means a phone call or in person in general. This is just too cumbersome for many people and it's very easy to make mistakes. It doesn't help that the user interfaces for the tools don't make the task easy for non-technical people.

The web-of-trust is meant to make this a bit easier. The core idea is that after I have verified the fingerprint of someone else, I can attach my signature to that key, attesting that it really is the right key. So if Carol wants to talk securely with Alice, and Carol already has a verified key for Bob, then if Bob has exported a signature about the purported key for Alice, Carol should be able to trust that as much as she trusts Bob. In practice you probably shouldn't trust it as much, but only almost as much. Now if Alice signs a key for Dave and exports that, Carol could send a message to Dave with some certainty as well.

In theory this is a beautiful system. PGP implements it a more complicated, allowing transitive trust to become stronger if there are several signatures from people you trust on another key, etc. But for looking at the weaknesses, we don't need to care about that.

So what are the problems? First, by signing a key and exporting it you are telling the world about your contact net. That breaks several privacy and anonymity requirements in many settings. Second, where do you export these keys? In PGP we use something called keyservers. But these keyservers have a lot of power. Indeed, in the basic setup the keyserver will be able to figure out who you are talking to based on what keys you are downloading and uploading. A keyserver also has the power to delete information. This makes it more likely that users will make mistakes.

The PGP model has served us well for many yearas, but in the current climate we urgently need something better. And luckily there are a lot of groups working on other models. The one I wanted to talk about in this post is the group working on what I call "Low Threat Key Verification Protocols". There are several of these proposals: Nicknym, Nyms and Keybase are the ones I'm the most familiar with. You could also argue that TOFU is the most basic version of this style of key verification.

The idea with these protocols is that instead of trying to verify something about the key's connection to an identity, they verify some other property that is not as strong but is easier to verify automatically. This means that the user experience gets much improved, while the argument is that the lesser security of these proposals isn't a problem in practice. The most extreme of these proposals is TOFU, which is short for Trust On First Use. The idea is that every time you send an email you attach your public key to it. The receivers user agent will remember which key was used initially and then if a message is ever signed using another key from the same person a warning about attack will be given to the user. Of course this approach only works if an attacker doesn't have the foresight to prepare for this case. There are also many other things that can go wrong with this approach.

Nicknym, Nyms and Keybase are trying to do something more ambitious. Their idea is to associate a key with specific pieces of identifiable pieces of proof available online. One is an assocation between an email address and a key. This is done by regularly sending a cryptographic challenge to that email address and expecting the correct result back. Another way is to expect the answer to a cryptographic challenge to show up in a Tweet from the user, or on an https-protected website for the user, or in a gist from a Github account by the user. Each one of these approaches can be automatically checker (and rechecked regularly). And if you do all of them, you can tie a key to a specific email address, specific web site, a specific github account and a specific twitter account. This should give a pretty good way of establishing identities that are well known. However, it doesn't help if you want to create anonymous or pseudonymous identities. It also doesn't give a good easy way for users to understand how much they should trust a specific key.

At the end of the day, these protocols are more prone to automation which means they will be easier for the end-user to use correctly. That shouldn't be underestimated. Any of these protocols will lead to a larger number of end-to-end encrypted emails (and other communication) out there. But fundamentally they also mean less strength of security compared to the ideal of fingerprint verification and the web-of-trust. That is not really a problem in itself - the problem comes in when we start talking about high-risk targets. People that will be actively attacked by Mallory, Eve and the others. The problem is that risk is not transitive. Alice can be a low-risk person while Bob is a high-risk person. But if Alice is using TOFU or any of the other protocols, that means that Bob's communication to and from Alice might be used to attack Bob in various ways. Thus, we can't just think that Alice can use one protocol and Bob can use another protocol. Alice's very act in using a low-threat key verification protocol actually puts Bob at larger risk.

I do think it's good that research and work is being done in this area, and I don't want the groups to stop - in fact, we should implement these protocols in free and interoperable software for all major clients and operating systems. However, we should do it consciously and thinking clearly about the fact that our work is not done, and that we need to find a better solution soon!