I've been reading about BitMessage, an anonymous, encrypted peer-to-peer email protocol. Unfortunately, there are some major problems:

  • BitMessage addresses are 36-character hashes, which isn't very user friendly.
  • Since the address is the hash of your public key, there's no way to change your keys without creating a new address.
  • All users receive all messages. The whitepaper claims this can be made scalable, but I'm not convinced.
  • There's no backwards compatibility with traditional email.

I'd really like to see something like this take off, so I've been thinking about what we would need to completely replace traditional email, and how we would do it without making things harder for normal people.

Distributed Secure Email Protocol (DSEP)

This protocol is designed to securely and anonymously transmit email between users, without being any more difficult for users than traditional email. However, if a user is willing to put in the same amount of effort as they would with PGP, the protocol should provide at least the same level of security.

The protocol will use a distributed hash table network to exchange email/public key certificates (see below), key revokations, key changes, and to find recipients based on public keys.

For this post, I'll just be giving a high-level view. At some point, I'd like to implement it and write a formal spec.

Email Addresses

First off, we'll steal the idea of using the public key as an address from BitMessage. As long as the keys are exchanged securely, for example, by meeting in-person to trade keys, this makes it impossible for someone to intercept a message without access to the recipient's private key (or the ability to break public key encryption).

However, normal people don't want to meet in person to exchange keys, or memorize 36-character strings (as in BitMessage). To meet normal people's needs, and also to provide backwards compatibility with the existing email network, users can associate a public key with an email address.

To associate an email address with a public key, the owner of the domain needs to associate their public key with the domain using a DNS record (to be determined), and then signs a certificate for the user stating that their public key is associated with their email address.

Once an email address and public key are associated, the association will not change unless:

  • The client sees the special key-change messages (see: Changing Keys).
  • The owner of the domain changes the key and the user authorizes it (after being presented with an warning that the domain may have been hijacked).

When used in this mode, the security is weakened, because an attacker with access to the DNS records can sign a bad key, then intercept the messages, however, this is still much better than standard email because:

  • Emails can't be intercepted passively. An attacker needs to change DNS records.
  • Emails can't be intercepted secretly. DNS records are public, and the sender and receiver will both be notified that something is wrong if the DNS records are ever fixed.
  • Emails can't be intercepted after the first exchange.
  • A sufficiently paranoid user can choose to verify keys out-of-band.

Sending and Receiving Messages

For the moment, we'll assume the internal message format is a traditional email. It may be possible to improve on that, but it's not important to the protocol.

To send a message, the sender first signs the message with their private key, then encrypts the result with their own public key. We sign-then-encrypt to prevent eavesdroppers from knowing who the sender or receiver is. We will likely want to prepend some information like the version number and possibly hashcash (to prevent spam).

The sender then checks the DHT network to find any IP addresses claiming to be the recipient. The sender connects to each potential recipient using TLS with a client authenticated handshake. The sender then checks the potential recipient's certificate chain to ensure that the root is the intended recipient. We allow certificate chains so users can delegate authority to accept messages for them without giving out their private key. Once a recipient is authenticated, the sender sends the encrypted message. A sender should follow this same process for each potential recipient, unless it would be impractical to do so.

The reason we authenticate the receivers is to limit the damage if a private key is ever made public.

Onion Routing

To provide anonymization, the network should support onion routing: Instead of sending a message directly to a recipient, a client may choose to send the message through other nodes. To do this:

  1. The client signs and encrypts the message for the final recipient as usual.
  2. For each random node chosen to route through, the client prepends the public key of the next node in the chain, or the final recipient if this is the last node, then encrypts the message with the random node's public key. We may also want to require hashcash here, to prevent wasting the network's resources.
  3. Once the message is sufficiently layered, the message is sent to the first node in the chain.

If any client receives a message that consists of a public key, hashcash, and an encrypted message, it's required to forward that message to the recipient associated with that public key.

From the outside, a message sent in this way will look identical to a message send directly to the first node in the chain, and then it will look like that node sent a message to the second node in the chain and so on. Only the first node will know where the message came from, and only the last node will know the recipient. Because the final message is encrypted, only the sender and recipient will know the contents.

To prevent leaking the trail to a dedicated attacker who can observe the entire network, it's also a good idea to include a random wait time before re-transmitting (since it's fairly obvious if a client gets a message and then immediately transmits a new, slightly smaller, message), and also to make at least one step of the chain a known "email laundering" service, which receives enough traffic to hide the association between messages in and messages out.

Changing Keys

To protect keys, it's valuable for users to be able to periodically change their keys (this is called "key rotation"). The advantage is that if a key is exposed, then only the messages encrypted with that key can be decrypted. Also, old keys can be deleted, making it impossible to expose them.

The method for changing keys in this system is:

  1. The client generates a new public and private key.
  2. The client signs the new public key with the old private key.
  3. If the user has an email address associated with the old key, they have the owner of their domain sign the new private key.
  4. The client revokes the old keys.
  5. The new keys and the signatures are advertised using DHT.

Other clients will:

  • Update their address books and email associations as needed, replacing the old keys with the new keys.
  • Possibly display a notification if the user is paranoid.
  • Reject any messages sent with the old keys (or display a prominent warning).

Backwards Compatibility

There are two methods for backwards compatibility:

  • A client can also have support for other email protocols like IMAP and SMTP. They could then handle traditional email exactly as before.

  • There could be "gateway" servers. The owner of a domain could set up an SMTP server, and whenever a message is received, sign and encrypt it with its own keys (signed by the keys in the DNS records), and then re-transmit the message. Clients would verify that the email address is not associated with a DSEP client, and that the message is signed by the domain's email gateway. Clients could also send messages to the gateway server, to be translated into SMTP emails.

    Using a gateway reduces the complexity of clients, and makes it unnecessary for the server to have any passwords for its users.

Obviously, any email that travels over the existing email network is insecure. If a user is paranoid, they should use a client which also supports SMTP and PGP, although there's no way to make this anonymous.

Servers

Since most people want to be able to receive email when they're not online, it should be possible to use servers. To do this, a client would sign a certificate for the server, allowing it to receive messages on behalf of the user. The messages would still be encrypted, so the contents of the message would be inaccessible to the server unless it somehow gains access to the user's private key.

For convenience, users may want to have the server handle their keys for them. To make this reasonably secure, I recommend this protocol.

To setup the account with the server, the client:

  1. Generates a random salt, IV and public and private key (if they don't already exist).
  2. Picks the number of iterations.
  3. Asks the user for their password.
  4. Uses PBKDF2(salt, password, iterations) to generate three keys: k1, k2, and k3.
  5. Encrypts the private key with k3.
  6. Generates HMAC(k2, encrypted blob).
  7. Sends the salt, IV, k1, iterations, public key, HMAC, and encrypted blob to the server (over TLS).

To access the keys:

  1. The client connects to the server (over TLS) and requests the keys from a particular user.
  2. The server sends a salt, number of iterations and public key.
  3. The client uses PBKDF2(salt, password, iterations) to generate three keys, k1, k2, k3.
  4. The client sends k1 to the server (this is basically the password).
  5. The server sends an encrypted blob, IV and HMAC.
  6. The client verifies that HMAC(k2, encrypted blob) matches the HMAC from the server. If this verification fails, the client stops processing and presents an error message.
  7. The client decrypts the encrypted blob with k3. The result is the user's private key.

k3 is basically a password, meant to protect the encrypted blob. The reason for this is that it protects against offline brute-force attacks, and also adds some protection to the keys, even if the user's password is compromised.

There are some details that could be changed (maybe using scrypt). The important part is that the server never has access to the password or unencrypted private key. This is obviously less secure than never giving the private key to anyone in any form, but it's much more user friendly, and secure as long as the password is reasonably strong.

Problems

There are a couple problems that would need to be resolved:

  • If the system requires hashcash, it would be very expensive to run a mailing list. If the system doesn't require hashcash, then attackers can disrupt the network by sending large onion-routed messages. I suspect this could be handling by having a per-user whitelist of addresses which are allowed to send messages without hashcash, or by using subcription services like RSS instead.

  • Large emails could be difficult to send. To handle this, I'd recommend sending attachments through BitTorrent (encrypted and signed, of course).

  • I don't know that much about DHT, so it may not be suitable for this, but BitMessage uses it and it seems to work.

Conclusion

Let me know if there are any other serious problems. The exact details aren't included intentionally, but most likely it will be something like ECDSA for public key cryptography, AES for symmetric encryption, and HMAC-SHA512 for verification. Of course, PGP is designed to encrypt part of messages, but it's possible that it can be repurposed to encrypt the entire message. If that's the case, then using an existing algorithm is preferable.

There's also something called signcryption that I need to look into. It sounds like it could make this faster, but it's not clear to me if it would provide the same anonymity.