L.P.A.A. - lentil, pea and ashes

L.P.A.A. - lentil, pea and ashes



Abstract

A messaging system designed to be resilient against content and communication network analysis, network failure or blockade.

Status of this Memo

2014-09-09 - 8th release-candidate

Terminology

The words MUST (REQUIRED, SHALL), SHOULD, MAY as well as their negatives (MUST NOT, SHOULD NOT) are to be interpreted as defined in RfC 2119.

Design Considerations

The protocol is designed with the following goals/targets:

Primary goals

  1. The messaging system shall enable the asynchronous exchange of messages and files between to or more participants.
  2. Communication MUST be possible over a variety of delivery paths, invariant to the transfer protocols, relaying providers or networks actually used. In case of complete network-outages (or -blocks) even delivery via file exchange over file storage like USB-drives ("Turnschuh-Tokenring") SHALL be supported.
  3. It SHALL be trivial for any user to set up new communication channels or distribution lists.
  4. It MUST be impossible for intermediates (server providers, messengers carrying drives) or interceptors to identify contents or intended recipient(s) of a message unless they are in possession of a current copy of the recipient's encryption keys.
  5. It SHOULD be very hard for intermediates (server providers, messengers carrying drives) or interceptors to identify the sender of a specific message (unless that knowledge can be derived from detailed upload timing analysis). The protocol SHOULD obstruct construction of communication matrixes.
  6. It MUST NOT be possible to change messages during transfer or to pose as communication partner without the tampering being recognized (unless the crypto keys have been compromised).
  7. Even if two communication partners share a common third one, it MUST NOT be possible to identify him/her/it from protocol or lpaa address book data alone to be the same partner, even if the communication equipment of the first two is compromized - unless both chose the same (nick)name for him/her/it, linked to the same accompanying data (phone numbers, addresses, etc.) or unless its identity is revealed from message contents ("Dear Mr. Anderson, ...").
  8. The messaging system MUST implement plausible deniability, i.e. from the protocol alone it is impossible to prove who sent the message.
  9. The messaging system SHOULD implement forward secrecy / key renegotiation, i.e. encryption keys change over time so even when the current encryption keys are revealed it is impossible to decrypt all past messages that might have been intercepted and stored.

Corollary Design Considerations

These design restrictions follow from the primary goals:

  1. All communication MUST be end-to-end encrypted.
  2. All key generation and handling MUST be done decentrally, directly and exclusively between the communication partners.
  3. Message delivery MUST be invariant to transmission channel - the same message CAN simultaneously be sent/delivered over multiple channels. To make it harder for observers to identify communication matrices a sender CAN use irregularily alternating delivery paths (servers) for sending messages.
  4. To increase difficulty for a (network-sided) observer delivery (and reception) of messages SHOULD use regularly encrypted and commonly used protocols (ssh, https) so broad blockades are costly and/or publically recognizable to implement.


Protocol


Protocol Overview

Communication partners agree upon one or more exchange channels (server names, USB stick drive exchanges) which basically are used as dead drops. Sender or recipients of messages cannot be identified by file name, thus recipients from this dead drop have to download all message from that drop box. This way no observer can identify who was the recipient of which message (or if of any at all). To identify whether a message is for the recipient, he/she/it has to decrypt the first encrypted block with each key (used with this dead drop) known to the recipient and check whether it is readable. If so, the sender (or group) is identified by the crypto key used.

The communication partners agree upon communication channels (e.g. servers) to use and a passphrase from which a cryptographic hash (scrypt) is computed that then is used as first cryptographic key. For private communication channels the passphrase should be a long and possibly unique (e.g. between Alice and Bob that might be "Alice promplty proposes paranoid pink pretzels pour Bob"). Automatic/advanced ratcheting enables frequent key change within the protocol and thus forward screcy.

To emulate decentral mailing lists or (twitter) hashtags a short common denominator can be used as (initial) passphrase. While technically it is possible to rekey a group (as this is after all only is another communication channel), a client SHOULD warn about this before issuing or confirming a rekey request.

For housekeeping purposes dead drop servers SHOULD remove messages on the dead drops which have timestamps older than 1 month.

As messages are sorted out at the final recipient, it is a valid approach to send them out via all known dead drops simultaneously or redistribute them again - which can enhance ensuring message delivery even on partially broken or filtered message paths, e.g. from local server, downsync'd to USB-stick, traveled via messenger, upsync'd to other local (or global) server.

Implications


Address Book

The lpaa address book SHOULD NOT be used as general address book and MUST NOT be incorporated into general address books (which can be also used by other programs) to inhibit data leakage. Instead it is recommended to place the NICKNAME@lpaa address into the general address book and reverse-map other contact data within the lpaa (mail) client from there.

To prevent unauthorized access to communication data and encryption keys the address book itself MUST be properly encrypted. The cleartext data MUST NOT be stored on any non-volatile memory.

The address book is stored in normalized database format to reduce ammount of identical text to make cryptoanalysis harder.
It consists of the following tables:

Contacts

Servers

Keys
The address book consists of records with the following fields

For exporting the address book it SHOULD be converted (MUST be done in-memory only to prevent even typorary storage of cleartext on disk) into three tab-separated files (contacts.tsv servers.tsv keys.tsv) where all fields are exported into their human-readable equivalents (UTF-8, bitfields as base64-strings), and then combined into a ZIP file with AES encryption.


Server/Key Expiry

Address records with OldKey status MUST be deleted automatically after a short transition time (few days / some messages) to ensure forward secrecy while still having a window open for asynchronous messages to arrive late.

Stale servers or old keys SHOULD no longer used for sending messages. The currentmost stale/old entries SHOULD be kept for a short time (depending on usual message exchange frequency, probably a few days) to be able to receive possibly delayed messages or (in case of servers) to keep a communication channel open in case the new/usual server does not work as advertized.

The client MUST allow the user to manually set single nick/server combinations or a specific server (for all contacts) to chosen status (usually either StaleServer, FallbackServer or ManualPriority).


Moving to other servers

The client's address book functions SHOULD support adding a new server to one or more contacts in one action, e.g.

The client then sends according AddServer messages (see below) to all contacts indicated.

Similarly moving existing contacts from one server to another SHOULD be supported for all three use modes. Then the client additionally sends DeprecateServer messages to the respective contacts.

Emergency-adding of a new server

To make communication possible in times of major network or server outages (by accident or malice) the clients SHOULD support adding a new server to one, multiple or all contacts as explained above. For this it sends out AddServer messages "all known channels" (see below: Selecting a Message Channel) - including the new, not yet used server to make discovery possible.

For receiving partners the client SHOULD support a function to discover knwon contacts on a new server. For this the client tries all known IDpw (regardless server associated with the record) for each message on the new to-be-discovered server. Where it discovers a valid message, it adds a new entry for the identified nickname and the new server to the address book.


Selecting a Message Channel

When sending a message to one contact from the address book, the communication channel is chosen as follows:

Message Format


The message itself does NOT have any fileype identifier / magic-cookie to make identification/filtering and especially file carving more difficult.

Messages (including all encryption, session keys etc.) MUST be padded to at least 4kiByte (4096 byte) length and to the next full exponent of 2 (4ki, 8ki, 16ki, 32ki, ...) to spoil message identification and tracking based on file length.

Messages are transferred in the following format:

In case the message format might be have to be changed in the future, new and old messages can run in parallel when new message formats are designed to fail Nonce/crypt(None)-Check. Care should be taken that content length always is a multiple of 512bit to have proper CBC block ciphers. In the current design it has a block alignment of at least 2048bit.

The use of a separate MAC was deliberately chosen to enable easier algorithm switching in case of need.
The MAC of the ciphertext is chosen as ward against attacks against cipher malleabilities or chosen plaintext / padding oracle attacks, its separate encryption to additionally decouple the MAC from the encryption.

Receiving Messages

The client visits all dead drop servers known to it and downloads all (current) messages. As it cannot know which messages are valid each client will download all messages for all customers of this download-URI. This inhibits identification of which message(file) was intended for which recipient, but also heavily increases data transfer on the servers and all clients.

For each server:

  1. The messages (or at least the message list including the nonce and encrypted nonce of each message) are downsync'd into an individual local directory or database.
  2. From the local addressbook all communication channels are selected that use this server.
  3. For each (new) downloaded message and each (subselected) addressbook contact the encrypted Nonce is decrypted with available ValidKey and SuggestedKeys and checked whether it is identical to the cleartext Nonce. If so, the message probably is valid for the contact.
    1. If decryption results in size errors (i.e. given lengths of header + frontpadding + content exceed the actual message length) the message is corrupt and is dropped.
    2. If sizes add up but the HMAC fails comparison with (ciphertext) HMAC, there might be tampering and an error message / warning MUST be displayed before discarding the invalid message.
  4. Successfully decrypted messages contents are stored in a separate (encrypted) store.
  5. If the nick is not a hashtag, the used IPpw is compared to the nick's keys in the address book.
    1. If the KeySuggestion is identical to an IDpw in SuggestedKey status, its status is changed to ValidKey. All other ValidKeys for this nickname+server MUST be set to OldKey status and any InitialKey MUST be deleted.
    2. If the KeySuggestion does not match a key in the address book for this nick+server, a new address record is created for the nick and server, its IDpw-key is set to the KeySuggestion and its status MUST be set to ValidKey. Maximum CipherID and HMAC-type are set to the values given (if supported) or to the known values whichever are higher. All other ValidKeys and SuggestedKeys for this nickname+server MUST be set to OldKey status.
  6. If the message is a AddServer message, the user SHOULD be prompted for confirmation to make changes (and maybe manipulations of taken-over clients) at least recognizable.
  7. If the message received via a deprecated server, a new DeprecateServer message SHOULD be sent to the partner (while care SHOULD be taken that this can not lead to a denial-of-service situation). The programs SHOULD suggest to (re)send AddServer messages to the sender for all locally assumed channels with a ValidKey via the old, deprecated channel. The user SHOULD be asked to select which connections to re-send.


Sending Messages

  1. When a message is sent to a contact (nickname), a valid server and the ValidKey IDpw are selected as described in "Selecting a Message Channel".
  2. A SessionKey, Nonce, HMAC-cryptkey and Content-cryptkey are randomly generated. The SessionKey is the most critical part in the encryption and thus MUST use the best random number source available, followed by the two cryptkeys. Nonce and front-padding length SHOULD use good randomness sources, too, while the padding contents are in comparison not as much as important (and e.g. could use /dev/urandom).
  3. If the nick is not a hashtag, a new address record is created for the addressed nickname+server with the encrypted HMAC as new IDpw-key with its status set to SuggestedKey.
  4. The message content (including front+back-padding) is encrypted with the Content-cryptkey.
  5. The message's HMAC is calculated and encrypted with the HMAC-Cryptkey.
  6. The Metadata (including Nonce, Content- and HMAC-key, maximum CipherID and HMAC-type set from program version) are encrypted with the SessionKey
  7. SessionKey and random Nonce are encrypted with the IDpw.
  8. The message is constructed from Nonce, crypted Nonce, metadata and content
  9. and the message uploaded to that server. Uploads SHOULD be batched in regularly or timed intervals (e.g. exactly to the hour). To make identification of message flows by passive network sniffing more difficult, valid looking messages consisting of random garbage CAN be uploaded randomly.
  10. As messages are sorted out at the final recipient, it is a valid approach to send them out via multiple or even all known dead drops simultaneously or redistribute them again - which can enhance ensuring message delivery even on partially broken or filtered message paths. This can result in multiple message deliveries, though.

Data Exchange / Dead Drop Servers


Servers CAN be used completely anonymously as they only act as dead drops, not forwarding messages or otherwise active (unless you count housekeeping and deletion of old messages as activity). For local use simply a network share directory can be used as dead drop within LAN/WAN networks.

Server providers CAN require access limitiations and login (at least for uploading):.

To inhibit identification of message senders by passive network sniffing at least message uploading SHOULD be done with an encrypted standard protocol (e.g. scp, ftps, https, ...).

To make identification of message uploaders more difficult uploaded messages SHOULD NOT be immediately available for receiving (e.g. move them from incoming to the visible downsync message drop). Instead messages SHOULD be moved in batches, e.g. hourly (or: quarter of an hour).

Additionally the server MAY insert valid looking messages in size similar to the ones uploaded that in fact are random garbage. This way it becomes more difficult for external observers to identify valid messages and who sent which message.

Dead Drop Types

Usually dead drop implementations store and share messages where each message is stored and transferred as individual file.

File names SHOULD be restricted to the use of [A-Za-z0-9_-] characters plus the dot [.] as extension separator to be portable across various file systems.

Shared Dead Drops

...do not distinguish between sending and receiving structures. Here usually the client does all message handling by itself.
Classic examples are USB-sticks and file shares.
Unless these Shared Dead Drops are limited in access (e.g. USB sticks or password-protected servers) they are prone to possible abuse as file servers and thus might cause liability issues.

Directional Dead Drops

...distinguish between "internal" (authenticated) and "external" (anonymous) users to prevent anonymous abuse of ressources.

Standard Dead-Drop-Server Implementations


The use of standard protocols for transferring message files discourages blocking these protocols (or makes it at least very recognizable or unfeasible). As additional bonus such protocols usually are well debugged and implemented so they are less prone to attacks.

To enhance anonymity logging file access SHOULD be disabled on the server.

To prevent misuse as anonymous file sharing service the server SHOULD remove files with noncompliant length(i.e. non-multiple of 4kiByte length) from the message directory when exchange of obfuscated messages is not allowed - unless messages obfuscated as regular files are allowed.

A server MAY use a limit for simultaneous connections from one IP to limit load from one customer (network).

For all systems the forwarding mechanism SHOULD unify all filesystem metadata ( creator, owner, ...) are set to the same values across all files to prevent gathering intelligence from these data. Timestamps SHOULD be randomized on a day between "today" and 7 days ago and a random time.

When using one file per message the message name SHOULD represent Nonce and Crypted nonce, i.e. base64url(nonce, crypted(nonce)) for easier handling.

file:// = USB-Stick, Fileserver

For receiving messages simply all message files are copied from the appropriate directory of the USB-stick into the incoming directory of the client computer.

To send messages the according files simply are copied onto the agreed directory. The client SHOULD anonymize all filesystem metadata.

For data protection the messages directory on a server SHOULD be write/delete-protected from clients, the incoming directory (for sending messages) SHOULD be protected against listing. In regular intervals the server SHOULD unify the metadata on the messages from incoming and move them to the message queue.

scp, ftps, sftp

For receiving messages simply all message files are copied from the appropriate message into the incoming directory of the client computer.

To help systems with reduced bandwidth to download only the interesting (plus random chaffing) messages the server MAY create a "lpaa.csv" file that lists (only tab-separated) base64url(nonce, crypted(nonce)) and filename of all message files in the directory whenever files are moved from incoming.

For sending messages the client uploads the message file to the server's incoming directory which SHOULD NOT be readable to a client.

For data protection the messages directory on a server MUST be write/delete-protected from clients, the incoming directory (for sending messages) MUST be protected against listing. In regular intervals the server SHALL randomize the metadata (to a random point in time between tomorrow and 7 days ago) on the messages from infoming and move them to the message queue.

The client SHOULD implement opportunistic certificate pinning to enable detection of man-in-the-middle-attacks(MitM).


https

For receiving messages a regular server SHOULD use a "messages/" directory relative to the lpaa URI as default setting.

To help systems with reduced bandwidth to download only the interesting (plus random chaffing) messages a regular server SHOULD create a "messages/" (e.g. messages/index.html) file that lists the file names (one per line) generated from base64url(nonce, crypted(nonce)) for all files available in the message store directory. The server SHOULD NOT list any additional file data in the directory listing to prevent accidental metadata leakage. The client periodically reads this index file and downloads all messages new to him from the server. Systems with reduced bandwidth MAY download only the interesting plus random chaffing messages from the server.

For uploading a regular server MUST offer file upload via a "upload/" form with POST method relative to the lpaa URI. The files MUST be transferred in the "files" variable field.

For data protection the incoming messages MUST NOT be directly accessible to a user. Instead the server SHALL unify the metadata on the messages from infoming before periodically moving them to the message queue (and update the index file while doing so).

The client SHOULD implement opportunistic certificate pinning to enable detection of man-in-the-middle-attacks(MitM).


Acknowledgements

Some ideas were inspired by by Ronald L. Rivest's "Winnowing & Chaffing" http://people.csail.mit.edu/rivest/Chaffing.txt

Jan Schejbal also came up with a similar idea on the TechTalk mailing list of German Pirate Party on 2013-07-16

Thanks to Dominik Oepen for proofreading the idea and his suggestions!

While frequent rekeying already was part of LPAA, the Advanced Ratcheting used for Pond inspired to automate this and increase key change frequency
https://www.whispersystems.org/blog/advanced-ratcheting/

Contributors

Please send comments to volker.tanger_lpaa@wyae.de

other ideas & protocols

References

The name stems from the Cinderella tale where she had to sort lentils and peas from the ashes. Likewise here the valid messages have to be sorted from all the stuff coming along with it (including messages for others).

History

2013-12-02 - first public suggestion
2013-12-07 - changed file name convention from UUE to base64url, clarified front padding
2013-12-17 - Typos, changed front padding from bytes to bits, clarified key expiry, clarified metadata
2013-12-28 - changed file definitions, added front-padding, HMAC
2014-01-08 - future-proofing key length to 512bit, changed front padding to byte-aligned, more robust message title, ephermal keys for address book
2014-01-17 - changed MAC-then-Encrypt-then-Encrypt to Encrypt-then-MAC-then-Encrypt, fixed Typos, removed 512byte front padding, specified text subject, reduced key size (to 256bit), added advanced ratcheting
2014-01-26 - changed key suggestion, chipher and HMAC
2014-01-30 - changed key suggestion (encrypted HMAC instead of HMAC-key), clarified: hashtags, distributed groups, rekeying ratchet behaviour
2014-01-31 - fixed typos, changed header bit order, clarified CBC block alignment
2014-02-18 - corrected text structure, clarified/defined first IDpw key hashes, clarified AddServer, added emergency server changes
2014-03-14 - added open / camouflaged message listings, re-added front-padding
2014-05-07 - changed key derivation to scrypt, otherwise added clarifications and removed typos
2014-05-27 - removed prototype implementation notes, normalized address book format
2014-09-09 - removed specified fake file wrapping method as standard, added AES256, Twofish and SHA512, added obligatory deletion of initial passphrase