1. Paolo Brandoli
  2. protocol

Overview

HTTPS SSH

FlowingMail Protocol Specifications

Authors: Paolo Brandoli
Mike Vorobiev

Warning

This document is not finished and it is being modified on a regular basis.

Introduction

Warning

For simplicity this section intentionally omits some details (e.g. key revocation). In order to have the full protocol specifications please read the Protocol specifications.

FlowingMail is a non-real-time, decentralized and encrypted messaging systems.

The main scope of the FlowingMail protocol is to hide the information being transmitted and the parties involved in the communication.

This section tries to give an high-level overview on the protocol.

Overview

DHT

FlowingMail is based on a Distributed Hash Table (DHT): The DHT is a kind of distributed storage where every stored information (block) is represented by an unique ID. Each participant in the DHT (node) has also an unique ID and is responsible for storing the blocks that have an ID similar to the participant's ID.

For redundancy purposes a single block is stored in several nodes with similar IDs. Each node contains a routing table that is used to find other nodes in the DHT network.

Each stored block is accessible by every node that knows the block's ID.

There are several kind of DHTs: the DHT used by FlowingMail is the Kademlia DHT with the following parameters:

  • K = 20 (size of a bucket in the routing table and number of nodes that store the same block)
  • I = 256 (size of the blocks and nodes' IDs, in bits)
  • A = 3 (number of parallel operations)
  • MAX_FAILURES = 3 (number of maximum failures in a node: the node is removed from the routing table when it fails more than MAX_FAILURES)

Information stored in the DHT

The DHT is seen as a global storage pool that stores blocks of information identified by an unique 256 bit ID: each block is stored in the few DHT nodes that have an ID similar to the block ID.

The DHT is used to store:

  • blocks containing the certificate of each partecipating node
  • blocks containing slices of encrypted emails
  • blocks containing an encrypted list of IDs of blocks that together form a complete encrypted email

Apart for the certificate blocks, other blocks are wiped from the DHT after a pre-determined amount of time.

IDs of the nodes and the block of informations

The nodes and the blocks they store have a 256 bit wide unique ID.

The ID of each block can be found by hashing twice the block content using the SHA-512/256 algorithm:

block_id = SHA-512/256 (SHA-512/256 (block_content) )

Where block_content is the array of bytes that contain the stored information.

The ID of a node corresponds to the ID of the block containing its certificate:

certificate_block_id[i] = SHA-512/256 (SHA-512/256 (certificate_content[i]) ) node_id[i] = certificate_block_id[i]

Since the block containing the certificate has the same ID as the node it represents, it is usually stored in the node itself and its neighbours (nodes that have a similar ID).

Warning

the block containing the certificate also contains an hash of the certificate. For simplicity this has not been described in this introductory chapter.

Sequence of operations

When a node wants to send an email then it performs the following operations:

  1. fetch the certificate of the recipient's node by querying the DHT for the block with ID equal to the recipient's ID or just connecting to the recipient (the TLS handshake will cause the transmission of the certificates which can be verified by hashing them and recalculating the node's ID). The recipient's ID may also be already available from previous communications
  2. encrypt the mail using the recipient's public key (available in the recipient's certificate)
  3. split the encrypted mail in several blocks and store them in the DHT: each block will be stored in few nodes that have an ID similar to the block ID.
  4. prepare a list of IDs of the blocks that contain the encrypted email
  5. build an encryted block that contains the list of blocks IDs that form the email
  6. add to the block containing the list of IDs a sequence of bytes that cause the ID of the block to be similar to the ID of the recipient, then store the block in the DHT. This operation is computationally intensive and is used as "proof of work" to prevent spam

The block containing the encrypted list of IDs will be stored also in the recipient node because the block's ID will be similar to the recipient's ID. If the recipient is offline then it will receive it when it goes back online because neighbour nodes republish their content at predefined intervals.

Each node tries to decrypt all the blocks that it receives and stores, but it will manage to decrypt only the blocks encrypted using its own public key. When a node receives a block containing the list of IDs and manages to decrypt it then it performs the following operations:

  1. fetch from the DHT all the blocks with the ID specified in the decrypted list
  2. join all the blocks
  3. decrypt the received email

Protocol specifications

Transport

Communications between the nodes happens through a TCP stream secured by TLS (Transport Layer Security).

There is no standard TCP port number assigned to FlowingMail: each FlowingMail node can choose to which port it listen for connections.

The stream format used to encode messages and blocks' content is GoingThere stream format, a format explicitly developed for FlowingMail.

GoingThere stream format

GoingThere defines a stream protocol.

The GoingThere stream embeds tags containing specific information, and the tags can be inserted into a continuous stream of data (e.g. a tag can be inserted at any point into a video stream and can be found without having information about its position).

The reasons for the development of GoingThere were:

  • a framework that verifies the stream against a known scheme was needed
  • a format with strict parsing was needed. Both ProtocolBuffer and Thrift allow the insertion of optional tags that are not defined in the schema and this is not allowed by FlowingMail
  • XML was considered but it requires huge libraries and it needs to be compressed. Additionally it needs to be normalized in order to produce FlowingMail blocks IDs in a deterministic way
  • a search for a light and usable binary XML framework didn't end successfully
Introduction

GoingThere takes inspiration from the Jpeg stream format: each tag is identified by the byte 0xff followed by the tag's id.

Few feature of GoingThere: - provides a streaming format that allows to embed tags into a continuous stream of data - strict or relaxed parsing of tag data - uses schemas to parse complex structures - a tag id ranges from 0 to 2^63 - 1 - tags can be specified as string names (the tag id is calculated by hashing the name)

Stream specification

GoingThere allows to embed tags with data into a continuous stream of data.

In the stream of data, each byte with the value 0xff indicates the presence of a tag, unless it is followed by a byte with value 0x0 in which case the couple of bytes 0xff, 0x00 represents a single byte of the stream with value 0xff.

Tag identifier

Tags IDs are integer numbers ranging from 0 to 2^63-1 A tag is marked by the byte 0xff followed by the tag's ID encoded as described in Integers encoding: when the tag's ID is equal to 0 then a -1 is written as tag's ID to avoid the sequence of bytes 0xff, 0x00.

If the tag's identifier is a string, then the string is hashed using the SHA1 algorithm and the first 8 bytes of the hash are copied into the 64 bit ID (the first byte of the hash is the most significant byte of the ID), then the most significant bit of the ID is set to 0.

The tag's ID is followed by the tag's type, a single byte that specify the type of information encapsulated in the tag. The tag's type can be:

The tag's information is encoded accordingly to its type.

Structures encoding

A structure tag (tag's type = 1) includes a collection of other tags. The structure tag itself does not encapsulate any private information and after it there should be immediately another tag which is embedded in the structure.

A tag with ID 0 and no type signals the end of the structure.

Before being serialized, the tags are ordered according to their numeric ID.

Booleans encoding

A boolean tag (tag's type = 3) is encoded as a single byte with value 0x01 to encode "true" or value 0x00 to encode "false".

Integers encoding

An integer tag (tag's type = 4) can encode a 64 bit signed integer.

The number of bytes used to encode the integer varies according to its magnitude.

To avoid writing a large number of bytes when the integer is negative the sign bit:

  • if the integer value is positive then the integer's value is simply shifted to the left by one bit.
  • if the integer is negative then ABS(integer_value + 1) is shifted to the left by one bit and the least significant bit is set to 1.

After the the integer has been prepared for writing:

  • the 7 lower significant bits are extrapolated into a byte
  • the value prepared for writing is shifted to the right by 7 bits
  • the most significant bit of the extrapolated byte is set to 0 if the prepared value reached 0, or is set to 1 otherwise
  • the single byte is written into the stream. If the byte value is 0xff then a byte 0x00 is written immediately after
  • if the prepared value has not reached 0 then restart from the first step

An integer with value 0 is always encoded as a sequence of two bytes 0x80, 0x00 to avoid having a sequence 0xff, 0x00 when the integer encodes a tag's ID

Floating point encoding

A double tag (tag's type = 5) is encoded using the IEC559 format.

The bynary representation of the double in IEC559 format is written to the stream after replacing all the 0xff bytes with the sequence 0xff, 0x00.

Strings encoding

A string tag (tag's type = 6) is encoded using an integer that specify the lenght of the string in bytes (the integer is encoded as specified in Integers encoding), followed by the bytes embedded in the string after all the bytes with value 0xff have been replaced by the sequence 0xff, 0x00.

Examples

A structure including one integer with value 1045 and one boolean with value "false"

tag ID tag's type content Byte stream
1 Structure   0xff, 0x02, 0x01
2 Integer 1045 0xff, 0x04, 0x03, 0xaa, 0x10
3 Boolean false 0xff, 0x06, 0x02, 0x00
0 End of struct   0xff, 0x80, 0x00

Kademlia Distributed Hash Table

This section illustrates the operations of the DHT and the byte format of the commands (without TLS applied).

It also illustrates the defensive measures that the DHT module must perform to avoid a range of attacks.

The DHT chosen for FlowingMail is the Kademlia DHT.

All the transmissions of FlowingMail messages happens through write operations into the DHT storage.

DHT parameters

The parameters for the Kademlia DHT used by FlowingMail are the following:

  • Node Address & IDs (B): 256 bit wide
  • Values: blocks of bytes with a maximum length of 8192 bytes
  • Calculation of the values IDs: SHA-512/256(SHA-512/256(value))
  • Number of nodes for each bucket (k): 20
  • Number of parallel DHT operations (alpha): 3
  • Maximum failure rate (number of failures after which a node is removed from the bucket): 3

DHT commands

Each node must recognize the four DHT commands 'Lookup', 'Find', 'Store' and 'Ping'.

All the commands are transmitted using the GoingThere stream format.

All the commands and responses are encapsulated in a structure tag with string ID "FlowingMail" (numerical ID 0x6d471bc1b7b83a83). The first tag in the structure is a string tag with numerical ID 0x1 which contains an unique string that changes at every command: responses to the command should carry the same requestId as the one in their related command.

FlowingMail GoingThere Schema

This paragraph describes the GoingThere schema used to build and parse the commands and response for the DHT, and to build the information blocks.:

/**
 * Contains the value of a single Node's parameter
 */
struct Parameter = 0x12
{
    string parameterName = 0x01;  // Name of the parameter
    string parameterValue = 0x02; // Value of the parameter
}

/**
 * Contains information related to a single node
 */
struct Node = 0x10
{
    string id = 0x02;            // Node ID (256 bit)
    string addresses[] = 0x03;   // List of addresses that can be used to contact the node
    string capabilities[] = 0x4; // List of supported capabilities
    Parameter parameters[];      // List of parameters and related values
}

/**
 * Union used to send and receive DHT commands and responses
 */
struct FlowingMail = "FlowingMail"
{
    // Request's ID. An unique ID that changes for every request. Responses should use the
    // same ID received in the command
    //------------------------------------------------------------------------------------
    string requestId = 0x01;

    // Union containing the command or the response
    //---------------------------------------------
    union command = 63
    {
        // Lookup command
        //---------------
        struct Lookup = 0x20
        {
            string id = 0x01; // ID of the node to lookup
        };

        // Lookup response
        //----------------
        struct LookupResponse = 0x30
        {
            Node nodes[]; // List of found nodes and their addresses
        }

        // Find command
        //-------------
        struct Find = 0x21
        {
            string id =0x01;
        }

        // Find response
        //--------------
        struct FindResponse = 0x31
        {
            string* value = 0x04; // Found block
            Node nodes[];         // List of nodes that may store the value
        }

        // Store command
        //------------
        struct Store = 0x22
        {
            string value = 0x04; // Value to store
        }

        // Ping command
        //-------------
        struct Ping = 0x23
        {
        };

        // Ping response (Pong)
        //---------------------
        struct PingResponse = 0x32
        {
            Node node; // Informations about the node
        };
    }

}

/**
 * Block containing a node's certificate
 */
struct Certificate = "Certificate"
{
    string certificate = 1; // contains the binary DER encoded certificate
    string slowHash = 2;    // contains the slow hash
}

/**
 * Initiation block
 */
struct InitiationBlock = "InitiationBlock"
{
    union blockType = 63
    {
        struct Initiation = 64
        {
            string messageId = 0x1;         // An unique ID for the message
            string conversationId = 0x2;    // The unique ID of the conversation
            string* subject = 0x3;          // The subject (optional)
            int epoch = 0x4;                // Date when the message was sent.
            string* senderCertificate = 0x5;// Certificate block of the sender (optional)
            string recipients[] = 0x6;      // List of recipients
            string replyTo[] = 0x7          // List of addresses to which the reply can be sent
            string* message = 0x1e;         // Message
            string blocks[] = 0x1f;         // List of blocks that form the email. Encrypted with the same key used for the initiation block
        }

        struct Forward = 65
        {
            string forwardToId = 0x20;      // Address to which the block must be forwarded
            string block = 0x21;            // Block to forward
        }
    }

}
Lookup

When a node receives the 'Lookup' commands then it has to return the list of nodes it knows that are closer to the requested id.

The parameter k determines the number of returned nodes.

The command is embedded into a Lookup structure tag ID 0x20, which contains a string tag ValueId with ID 0x02, which in turn contains the ID of the node to lookup.

Example of lookup command:

Description Numeric ID tag's type content Byte stream
FlowingMail 0x6d471bc1b7b83a83 Structure   0xff, 0x86, 0xea, 0xc1, 0xfb, 0xb6, 0xf0, 0x8d, 0xc7, 0xda, 0x01, 0x01
requestId 0x01 String "1" 0xff, 0x02, 0x05, 0x02, 0x31
Lookup structure 0x20 Structure   0xff, 0x40
valueId field 0x02 String 32 bytes with node ID to lookup 0xff, 0x04, 0x05, 0x40, follow 32 bytes or more with node ID (each 0xff byte is replaced by 2 bytes 0xff, 0x00)
End of Lookup 0x0 end of structure   0xff, 0x80, 0x00
End of FlowingMail 0x0 end of structure   0xff, 0x80, 0x00

When a node receives a lookup command then it should respond with a list of nodes (IDs and IP addresses) that have an ID close to the requested one.

The response is embedded into a structure tag with string ID "FlowingMail" (numerical ID 0x6d471bc1b7b83a83).

The first tag in the "FlowingMail" structure is the requestId string tag (numerical ID 0x01), which contains the same request ID that was present in the lookup command.

The second tag is a LookupResponse structure with ID 0x30 which contains zero or more Node structures "Node" (numerical ID 0x260f7a8cd4f6938b). The Node structure contains 2 string tags "id" and "address" (numerical IDs 0x07ea5dfc8b8e384d and c662180230cad147) that contain the node ID and the node address.

Find

When a node receives the 'Find' command then it has to return the value associated to the requested ID (if it knows it) or the list of nodes closer to the requested ID.

Store

The 'Store' command is used to store a block of information into a node.

The node must react in two different ways according to the type of block it receives:

  • blocks containing a certificate have a long term storage: each time a certificate is received and cleared for storage then its expiration date is set for 30 days after the last reception date
  • blocks that don't contain a certificate have a short term storage: the ID of each block is stored the first time that the block is received, and its expiration date is set to 15 days after the date of first reception. When a block is expired then it will be removed from the DHT and subsequent storage request for the same block will be ignored.
The ID of each received block must be calculated with the following formula:
block_ID = SHA-512/256 (SHA-512/256 (block_content))

If the block_ID is not in the range of IDs associated with the node then the storage of the block should be denied, unless the node is willing to try to decrypt the block content and accept it if the decryption succeedes.

If the decryption of the received block succeedes then the node can parse the received message and eventually it can start fetching the blocks that form the complete email.

Ping

When a node receives the "Ping" command then it just have to return a "Pong" response.

DHT operations

Re-publish

The DHT must periodically republish the values it stores. This allow to redistribute the values to nodes that may be closer to the target ID.

If a node detects that after the republish operation the value is stored in enough nodes close to the target ID (excluding itself), then it can discard the value from its own storage.

Mitigation of attacks

The DHT module must implement the specifications in this section to reject several kinds of attacks.

DHT values

The DHT's purpose is to store values associated with an ID: the ID of each value is found by hashing the value twice with SHA512/256.

There are three kinds of DHT values:

  • certificate blocks (stored unencrypted)
  • initiation blocks (encrypted with the recipient's public key)
  • message blocks (encrypted with the recipient's public key)

Blocks' IDs

Certificate block

A certificate block is a block containing a node's certificate and its slow hash, encoded using the Certificate structure defined in the FlowingMail GoingThere Schema.

The node's X509 certificate must contain the following fields:

  • Version
  • Algorithm ID
  • Subject Public Key Info - Public Key Algorithm - Subject Public Key
  • AlternativeName (only if the certificate can be revoked)
  • Certificate Signature Algorithm
  • Certificate Signature
  • SlowHashParameters(NID 2.25.184163686009197051666987705173424850203)

The SlowHashParameters field is specific to FlowingMail certificates and contains the parameters used to calculate the slow hash of the certificate (encoded in binary DER format). The slow hash parameters contains one number followed by numbers or strings, each separated by a semicolon: the first number specifies the slow hash algorithm to use, the subsequent numbers or strings are specific to the slow hash algorithm.

At the moment, only the PBKDF2 algorithm is used, represented by the number 0. The PBKDF2 hash requires two parameters:

  • iterations, an integer number (normally 32768)
  • salt, a collection of bytes encoded in HEX format (e.g. FE67A6)

The AlternativeName field may contain a different Node human readable address. See Key revocation for more informations about this field.

X509 certificate information block and node ID

This image shows how the X509 certificate is related to the certificate block and the node id.

The X509 certificate encoded in binary DER format is inserted in the certificate field of the Certificate GoingThere structure, while the calculated slow hash is inserted in the slowHash field of the same structure.

The certificate block is obtained by encoding the Certificate structure using the GoingThere protocol.

Certificate blocks are not encrypted in any way and are stored in the DHT. The DHT will assign to it the same ID as the owner node ID, because the ID of the DHT values is also calculated by hashing the value twice.

Other nodes can retrieve a particular node's certificate by finding in the DHT the value with ID equal to the node's ID and can verify the authenticity of
a certificate by comparing the SHA2(SHA2(certificate information block)) hash with the node's ID and by verifying the correctness of the slow hash part.

Node ID

The node's ID is generated by hashing twice (with SHA-512/256) the block containing the X509 certificate (see Certificate block).

Node human readable address

The FlowingMail nodes always use the Node ID to communicate with each other and to store information. However the Node ID cannot be read by humans because it contains non alphabetic chars.

In order to obtain an human readable string, the Node ID must be encoded using a Base58 algorithm.

Key revocation

The ID of a node depends on the node's certificate, as illustrated by the following formula:

node_id = SHA-512/256 (SHA-512/256 (block_containing_the_certificate) )

When a node obtains a certificate then it looks in the Subject Alternative Name field of the certificate for an ID of a certificate that when published in the DHT invalidates the current one.

During the first setup of a node a sequence of keys and certificates is generated: each subsequent certificate contains the ID of the previous one in its Subject Alternative Name field.

When all the certificates have been generated then only the last one is published in the DHT and can be retrieved by other nodes, while all the other certificates are kept hidden and should be stored with their private keys in a safe place.

When a key get compromised then the certificate with the same ID as the one stored in the current certificate Subject Alternative Name field is published in the DHT: from this moment forward the node will have a new ID and the previous certificate and key will be void.

Generation of the revocation certificate

Several chained certificates. The first one revocates the second one.

Sending and receiving of messages

A message is composed by the sender and received by the recipient.

The sender and the recipient don't have to be on-line at the same time for the message to be delivered, but the recipient must come on-line within a predefined amount of time after the message has been sent by the sender. The sender can go off-line after it has sent the message and before the message is delivered.

Creation and delivery of a message

The sender of the message must know the recipient's public key by obtaining its X509 certificate.

The sender may obtain the key in the following ways:

  • preferred method: it may have cached the recipient's public key from a previous operation
  • suggested method: it may have obtained the X509 certificate (and therefore the public key) while communicating with the recipient during others DHT operations (which are authenticated and encrypted by TLS/DTLS)
  • discouraged method: it may explicitly retrieve from the DHT the value with the ID of the recipient, which correspond to the recipient's X509 certificate. This way of retrieving the DHT is discouraged because a third party may understand the recipient a sender is going to interact with.

Once the X509 certificate has been obtained then the sender calculate its slow hash and double hash the result with SHA-512/256 to check that the hash result correspond to the recipient's id. Additional verifications on the certificate itself must be performed.

If the recipient has an alternative Node human readable address in the X509 certificate, then the sender must check if the alternative certificate has been published. If the alternative certificate exists then the sender must delete any reference to the current X509 certificate and use the alternative certificate instead.

When the X509 certificate has been verified then the sender performs the following operations:

  • generate a random integer 'm' with the same length as the encryption key
  • derive a symmetric key from the random integer 'm'
  • build the array of bytes that will be encrypted and sent, using the message byte stream format
  • encrypt the array of bytes that embed the message using the symmetric key
  • split the message in separate blocks and calculates the double hash SHA-512/256 of each block
  • create a new block (initiation block) containing the list of hashes of each encrypted block, formatted as specified in the initiation block byte format
  • encrypt the initiation block using the random symmetric derived key previously generated
  • the sender adds to the initiation block a random number of random bytes that causes the double hash of the block to be close to the recipient's ID
  • the sender stores all the blocks (including the initiation one) in the DHT: the ID of each block is represented by its double hash. The blocks must be stored in random order and possibly with a slight delay. Because the initiation block has an ID similar to the recipient's ID then it will be stored directly into the recipient and/or its neighbors.

Reception and decryption of the message

When the sender stores the initiation block into the DHT then the recipient of the block will receive it, because the ID of the initiation block is similar to the recipient's ID.

If when the initiation block is stored into the DHT the recipient is off-line, then it will receive the block when it goes back on-line because the participants of the DHT periodically re-publish the values they store.

The recipient must try to decrypt all the blocks its receive: when an initiation block is received and the decryption succeeded then the recipient has a list of the IDs of the blocks that compose the mail and will try to retrieve all the blocks from the DHT.

When all the blocks have been received then the recipient decrypts the mail.

Message encryption

Once the raw message has been built then it is encrypted using the symmetric AES key in CBC mode.

The 256 bit AES key is derived through the PBKDF2 algorithm from the random integer 'm' created at the beginning of the message creation.

The PBKDF2 parameters for the key derivation are the following:

  • TODO:

Several random bytes should be appended to the tail of the resulting encrypted message.