Worst Case Messaging Protocol

We already have lots of tools to communicate safely, and in some cases, anonymously. These tools work well for their purpose, but spying and law enforcement tools have also improved.

People are forced to decrypt their hard drives in airports. Rootkits are developed by police forces. DPI systems are installed on a country level. Using the graph of who communicates with whom, it is possible to map the whole hierarchy of an organisation, even if all communications are encrypted. How can we defend against that?

I believe that the analysis of organisations is one of the biggest threats right now. The ability to recognize an organization is the ability to destroy it by seizing a few members. That may be useful against terrorists, but these tools are too powerful, and they may be used by the wrong hands. Terrorists already know how to defend against such systems, but what of common people? Any company, association or union could be broken anytime.

I think we need tools to mount resilient organizations. A compromised node shouldn’t bring down the whole system. Intercepted messages shouldn’t give too much information on the different parties. People can still find ways to send their messages safely (PGP, dead drops, giving USB keys hand to hand), but we need a framework to build decentralized human systems.

Here is the solution I propose: a messaging protocol designed to protect identities and route around interception. This protocol is designed to work in the worst case (hence its name), when any communication could be intercepted, and even when we can only use offline communication.

Every message is encrypted, signed and nearly anonymized (if you already know the emitter or receiver, you can recognize their presence, but this can be mitigated). To introduce redundant routes in the network, a simple broadcast is used (the protocol is not designed for IP networks, but for human networks, with limited P2P communication). Any node can be used to transmit all the messages. The fundamental idea is that if you’re compromised, the whole organization can still work safely without you.

Prerequisites

Assumptions

  • Every communication can be intercepted
  • if a node is compromised, every message it can read or write is compromised
  • People can still create a P2P (IRL) network to communicate (aka giving an USB key to someone else)

Goals

  • Confidentiality
  • Anonymity
  • Authentication
  • Deniability? (I am just a messenger)
  • Untraceability
  • Can work offline (worst case)

For this protocol, we need a RNG, a HMAC function, a symmetric cipher and an asymmetric cipher. I have not yet decided what algorithms must be used. They could be specified in the message format, to permit future changes in algorithms.

Message format

  • nonce1
  • HMAC( sender’s public key, nonce1 )
  • expiration date
  • symcrypt( symmetric key, message )
  • nonce2
  • For each receiver:
    • asymcrypt( receiver1′s public key, symmetric key )
    • HMAC( receiver1′s public key, nonce2 )
    • asymcrypt( receiver2′s public key, symmetric key )
    • HMAC( receiver2′s public key, nonce2 )
  • asymsign( sender’s private key, whole message )

Here is how it works:
An identity is represented by one or more public keys (you can have a different public key for each of your contacts, it makes messages difficult to link to one person). They are not publicly linked to a name or email address, but the software layer could handle the complexity with a good enough UI. I do not cover key exchange: users must design their own way to meet or establish communications.

Every user is a hub: all messages are broadcasted by all users. To prevent data explosion, expiration dates are used. Users recognize the message they receive and the identity of the emitter, using the HMAC of the public keys. All communication are encrypted, but I use the convergent encryption ideas to have multirecipient messages.

Handling the messages

Parsing

  • verify if one of my public keys is in the receivers by calculating the HMAC with nonce2
  • validate the signature (if I already know the emitter’s public key)
  • decrypt the symmetric key that was encrypted with my public key
  • decrypt the message

Creating messages

  • write the message
  • choose the emitter’s identity and public key
  • choose the receivers and the public keys used
  • choose an expiration date
  • generate two random nonces
  • generate a symmetric key
  • insert nonce 1 and the HMAC of nonce 1 and my key
  • insert the expiration date
  • encrypt the message with the symmetric key and insert it
  • insert nonce 2
  • for each receiver:
    • encrypt the symmetric key with the receiver’s public key and insert the result
    • insert the HMAC of nonce 2 and the receiver’s public key
  • sign the whole message with my private key and append the signature

Sending messages

  • Take all the messages you received
  • filter them according to some rules:
    • remove expired messages
    • remove messages too large?
    • etc
  • add your messages to the list
  • give the message list to the next node in the network

This protocol is voluntarily simple and extensible. New techniques can be devised based on this protocol, like dummy receivers in a message or dummy messages to complicate analysis. It is independent of the type of data transmitted, so any type of client could use this protocol (it is at the same level as IP). Most of the logic will be in the client and the contact manager, to present an interface easy to use.

I truly hope we will never need this to communicate, but recent events have convinced me that I need to release it, just in case.

I am open to any critique or suggestion about this protocol. I will soon open a repository to host some code implementing it, and it will of course be open to contributions :)

About these ads