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 🙂

Advertisements

Yet another authentication scheme

Recently, I was asked to design a new authentication protocol for a web service. I know that I shouldn’t do reinvent the wheel, so I immediatly proposed OAUTH. It turns out that it can’t be used in this situation. Here are the constraints:

-calls to the webservice must be authenticated: I can keep the tokens and signature from OAUTH here. The problem is: how do I get that token?

-calls are made from devices or applications without access to a webbrowser (embedded devices, phones, etc.). The redirection dance of OAUTH is not acceptable here

-communications are done over an untrusted network, without SSL.

-I can’t use application keys and secrets to encrypt and sign the authentication process: clients include open source software and smartphone applications. You can’t hide a secret key in these.

-the protocol has to be simple to implement, on a lot of languages

-the server must not store the password in cleartext (I shouldn’t have to precise this…), the client must not store the password

Summing it up: no preshared keys, no browser, no SSL, untrusted networks, no passwords stored, and an OAUTH-like environment once the client is authenticated (tokens, authorizations, revoking, etc)

Apparently, I should just give up. But I like to play, so I’ll try!

First, I must say that I am not an expert in security nor cryptography. But I’m really enthusiastic about these subjects, and my day job is at a company providing strong authentication solutions (no, this protocol is not related to my day job). So, I know a bit about the subject, and I know that I should ask for reviews, hence this post.

Rough ideas

We need a safe communication over an untrusted network. TLS immediatly comes to mind, but the targeted applications might not have access to a TLS implementation. I’d like to use SRP, but I don’t think I’m able to implement it correctly (and it has to be SIMPLE). Using Diffie-Hellman to establish a shared key is another idea, but it is not safe against MITM.

Here’s my idea: we don’t need to generate a shared secret, we already have it. It’s the password!

But how can I use the password if the server doesn’t store it in cleartext?

The trick: key derivation functions

Decveoplers are finally understanding that they should not use MD5 nor SHA1 to store their passwords, even with a salt, because computing power is so cheap these days that anyone could crack easily a lot of passwords.

It is now recommended to use other functrions tro store passwords. The key derivation functions are a class of functions that create a key from a password. Basically, they do it by interating a lot of times. That makes them very slow, which is an interesting property if you want to stpre passwords: it is too expensive to “crack” the password. PBKDF2, bcrypt and scrypt are well known key derivation functions. They’re simple to use and available in a lot of languages.

With these functions, I can safely store the passwords, and generate a key shared with the client.

In short: if I store kdf(password, N) with N the number of iterations, I can send any M > N to the client and ask him to compute the key, without compromising what I store.

Designing the protocol

Now that we have a way to use a shared key, we can look at what will go over the wire to establish it. If I use directly kdf(pass, M), anybody getting access to the client storage will be able to obtain the key for any L > M. So, the key establishment has to use a nonce. That way, the client will only use the password once and forget it, and store the derivated key.

I would rather use a truly random key that has no relation with the password. It could be given to the client, encrypted with the derivated key. The derivated key could then be thrown away. But I still do not know if it is really necesary.

The server still needs to authenticate the client. The client will make a second call to the web service, signing it with HMAC and the key.

That’s it! It is really simple, so if there are flaws I did not see, you will surely catch them.

TL; DR

The protocol is based on key derivation functions, like PBKDF or bcrypt.

  • The server stores login and H = kdf(pass, N), with N integer
  • The client wants to authenticate and makes a call to the server with the login as argument
  • The server replies with M > N and i nonce
  • The client calculates k1 = kdf(kdf(pass, M)+i, 1)
  • The server calculates k2 = kdf(kdf(H, M-N)+i, 1)
  • The client calls the server with args “user=login&sign=”.HMAC(“user=login”, k2)
  • If k1=k2. The signature matches and the client is authenticated.