I've had an idea rattling around in my head for a while now about how this might be achieved.

* CAVEATS *

(Not directed at anyone in particular, but I always state these when I talk about security in detail).

"Security" and "trust" are fundamentally economic and social problems that sometimes (but not always) have feasible technical solutions. You can't reason about either without first considering the (human) adversaries you face, as well as the society in which your users and adversaries live. In my ideal world, for example, all systems are secure and trustworthy by default, since the people building them and interacting with them are all responsible and ethical (we sadly do not live in this world).

Paradoxically, the "easy" part of making a system secure and trustworthy is implementing the cryptographic primitives, since their correctness can be formally proven. The "hard" part is key management, since "correct" key management depends on your threat model. If you mess key management up, then it doesn't matter how well your crypto is implemented, since now your adversaries have your keys.

* THREAT MODEL *

Now that that's out of the way, let's consider threats to key distribution in the post-Snowden world. We're up against a large state-level adversary (i.e. the Mafia, the NSA, botnets) that has lots and lots of CPU cycles. The adversary can read anything on any network and store it indefinitely, and they can alter any data in-transit. They can coerce a large number of users to make all of their data readable, and they can coerce them to change their data arbitrarily. However, I'll assume that the rest of the users beyond the adversary have more computing power combined, and that the adversary cannot coerce the majority of users to reveal or alter their data. I think that both of these constraints on the adversary's power are reasonable, since external factors (like social push-back against the large-scale power abuse required to overcome these constraints) will limit the power of the adversary in practice.

Now, the problem is: given this adversary, how do two users Alice and Bob exchange and revoke public keys over the Internet? With PKI strategies, Alice and Bob both trust Charlie, who certifies Alice's and Bob's public keys. If Alice revokes her public key, she gets Charlie to vouch for a revocation notice to Bob, which Bob accepts since Charlie vouched for it.

The problem with PKI implementations today isn't Charlie per se. After all, Alice and Bob have to have some way of verifying that the each other's public keys are authentic, and since it's not feasible for them to meet in person to do this, they have to "meet in the middle" with either trust-on-first-use semantics or with one or more trusted intermediaries (CAs, web-of-trust). The problem with PKI implementations today is that our adversary can get Charlie (i.e. a TLS CA, a key server, the ISP's network, etc.) to vouch for or deliver the wrong keys and revocation notices. What's needed is a way to make it so the adversary can't coerce Charlie without receiving a HUGE public backlash each time.

To do so, we'll use a well-known blockchain as a notary for Alice and Bob's public keys. Under our threat model, it's reasonable to assume that even a state-level adversary does not have enough power (computing or coercive) to execute a 51% attack on the blockchain. To see why this is a reasonable assumption, consider what would happen if the NSA were to attack Bitcoin. If they did, everyone who invested in Bitcoin--a lot of people, some with powerful friends and lobbying groups--would be out for blood, and the NSA's power would likely be reduced by Congress or the President as part of the backlash (we might also see resignations from the NSA ranks). Moreover, the blockchain could be recovered and the offending hosts identified (the fork where the 51% attack started would be evident), making the pay-off to the NSA very small compared to its potential losses.

* KEY MANAGEMENT *

The blockchain gives me an idea for a protocol based on the Sovereign Key proposal from the EFF [1], but with two key differences (no pun intended). First, unlike traditional PKI systems, Alice generates key pairs and CSRs in advance, and publishes all of the public keys at once to one or more public locations. She uploads the URLs to the public key bundle, its cryptographic hash, and one or more user-specific identifiers to the blockchain (using a one-time-use blockchain key pair). Then, anyone can fetch her public key bundle and verify its integrity by using the blockchain as a notary, and we don't have to worry about the adversary covertly modifying the keys or identifying information after the fact.

The second key difference is that Alice manages her private keys in a way to force the adversary to use human intervention to compromise them (greatly driving up the economic and social costs of doing so). To bootstrap key distribution, Alice thinks for a while, and deduces that she is likely to encouter N private key compromises over her lifetime. She gets a trusted computer and generates N key pairs and a CSR for each one. She signs each CSR with every private key to prove their authenticity (since throughout her life, only she is expected to know them all). She puts these keys in the order she will use them over the course of her lifetime, and gives them each a sequence number (PK_1, PK_2, PK_3, etc.).

She takes the private keys and their matching CSRs and stores them in various places that are hard for the adversary to find without noticeable human involvement. Some she keeps on her devices, some she stores in an offline USB stick, some she prints out and puts in a bank vault, some she prints out and buries in a safe in her back yard, etc. She only needs to have the keypair she's currently using installed on her devices. This leverages the assumption that it's not feasible for the adversary to compromise all of her keys without forcing her to help (and thus bringing their snooping to her attention, which she'll complain about on the Internet and get the media involved). Even a state-level adversary won't be covertly digging up everyone's back yards in search of buried private keys anytime soon :)

Alice uses her keypairs in order, revoking them as they get compromised or expires (if she specifies an expiration date). When she revokes a public key, she goes and gets her offline CSR and publishes it to the blockchain.

Alice always uses the uncompromised private key with the smallest sequence number to communicate securely. Bob can easily figure out which one this by (1) fetching Alice's key list (i.e. from one of the URLs in the blockchain), (2) verifying its integrity with the blockchain's copy of its hash, and (3) scanning the blockchain for subsequent valid CSRs.

The remaining challenge is for Bob to discover which blockchain record belongs to Alice (so he can get the right key bundles). To do so, Alice includes as many user-specific identifiers in her blockchain record as possible, to bind her strongly to her key bundle.

The set of user-specific identifiers is arbitrary (I got the idea from onename.io [2]). Examples:

* a (hash, [URL list]) pair that identifies a picture of Alice holding a hand-written copy of her key bundle hash.

* Alice's TLS-secured and DNSSEC-secured domain name

* Alice's bitcoin wallet, which has a transaction including her key bundle hash

* Alice's twitter feed, which contains her key bundle hash

* A signature of the key bundle using a private key from a separate PKI (which Bob has the public key for)

* her email address, so you can ask her for her key bundle hash

* a link to a press conference that features a picture of her doing something she's well known for

* cryptographic signatures from other people or CAs

* usernames on other services, along with content that includes the hash

* an OpenID identity URL, which contains her key bundle hash

There is space here for TOFU, CA, and WOT semantics, allowing Alice and Bob multiple ways to authenticate (some automatic, some manual). Alice can include her TLS certificate to authenticate to Bob via the existing TLS CA infrastructure. If Alice and Bob prefer WOT, they can authenticate through a chain of individuals between them. If Alice and Bob want manually authenticate with TOFU (i.e. through their web browsers), the browser will load a dosier of the other principal using the blockchain record.

Once Bob has decided to accept Alice's key bundle hash based on the identifying information, then Bob can communicate with Alice securely. I intentionally avoid mandating an authentication mechanism, because this is an application-specific choice based on what the user will trust the application with and how secure the application needs to be.

[1] https://www.eff.org/deeplinks/2011/11/sovereign-keys-proposa...

[2] https://onename.io