Crypto

Overview

This article describes the cryptography involved in the Dead Drop protocol in more detail. The design rests on three completely independent systems:

1. “Traditional” end-to-end encryption.
2. Private Information Retrieval
3. “Uniformization”

Let’s look at each of those in a bit more detail.

End-to-end Encryption

Dead Drop uses the excellent Noise Protocol Framework to build the end-to-end encryption part of the protocol. The concrete parameters chosen are:

1. AES (256 bits) symmetric cipher with GCM mode
2. SHA-256 as hash algorithm
3. Curve25519 is used for DH key agreement

The static keys are generated on the user’s device and the public part is published through a side-channel (a phone-book of sorts) to every other user. Note: static keys still need to be authenticated to really belong to the right person, but is out-of-scope for this discussion.

The handshake happens automatically with every user independently of further user actions. This means the handshake is not initiated when the sender wants to speak to a recipient. Doing that would trivially leak this association.

Ephemeral keys used to exchange a message are renewed after each message to enable Perfect Forward Secrecy¹.

Private Information Retrieval

Perhaps the most novel part of Dead Drop’s approach lies in its implementation of Private Information Retrieval².

Using an end-to-end encrypted message might enable confidentiality of message contents, but if the recipient must ask the server explicitly for a message, or if the server itself must deliver a message to a given recipient, then the association between sender and receiver is revealed.

Instead of doing the above, a Dead Drop client sends a PIR query to the server. This query is cryptographically constructed to be completely opaque to the server and acts as a black box into which messages can be dropped.

Now obviously the server doesn’t know what message this query needs, so its only option is to drop all messages into the query black box. The query will output an equally opaque result which the server will return to the client. The client then decrypts the result with an ephemeral key specifically created for this query only, which will reveal the one message the client actually wanted.

The cryptography used to achieve this is based on Ring Learning With Errors³, with parameters that are currently estimated to produce above ~256 bits of security. This level of security is acceptable even beyond 2030 according to NIST⁴.

An interesting fact for this kind of cryptography is that keys, public or otherwise, are not shared at all. Since both the source and target of this operation is the client, neither the key nor any derivates thereof leave the client, only ciphertext does. The server works directly with the ciphertext without knowing what it means or if it means anything at all.

Nevertheless, the client generates a new RingLWE key for each query in-line with Perfect Forward Secrecy¹ practices.

“Uniformization”

The only missing part of being completely meta-data secure after the above is just getting rid of all other sources of statistical data. This is achieved by decoupling certain parameters from user action, so no information about user action can leak.

This entails the following:

1. Every message is the same size, currently 10KB.
2. Encrypted messages are indistinguishable from random noise.
3. Everyone sends 1 message / hour, regardless of user action. If there is no message to send, random noise is sent.
4. Everyone queries the server for 1 message / hour, regardless of user action. If there is no message for the user to query, it will send a random query.

Summary

Dead Drop is the only protocol / messaging service which leaks absolutely no meta-data and no statistical data at all.

It does this through three building blocks: end-to-end encryption, private information retrieval and uniformization. The end result is a trade-off of some usability for a perfectly meta-data secure messaging experience.