Briar: Protocol Spec

This document describes the protocols used for communication between Briar nodes: the Briar Transport Protocol (BTP) and the Briar Messaging Protocol (BMP).

BTP provides a secure channel between two nodes, which can be used to carry any kind of data. BMP uses BTP to carry private messages, group messages and subscription updates between pairs of contacts.

1. BTP - the Briar Transport Protocol

BTP has the following design goals:

To be usable over a wide range of underlying transports
To ensure the confidentiality, integrity, authenticity and forward secrecy of delivered data
To be difficult for an observer to identify through techniques such as deep packet inspection

1.1 Transport plugins

To operate over diverse underlying transports, BTP uses transport plugins. Each plugin is responsible for sending and receiving data over a particular underlying transport. Transport plugins do not have access to unencrypted or unauthenticated data, nor are they required to ensure the confidentiality, integrity or authenticity of the data they carry. They are only required to deliver opaque streams of bytes known as connections.

A connection may be simplex or duplex, depending on the nature of the underlying transport. Simplex connections are unidirectional, while duplex connections are bidirectional. Transports with very high latency are only used for simplex connections, even if they are able to carry data in both directions.

Sending DVDs through the mail is an example of a simplex transport. TCP is an example of a duplex transport.

Transport plugins must ensure that the bytes carried in each direction across a given connection are delivered in order, but the connections themselves may be reordered. For example, a simplex transport plugin for DVDs sent through the mail must ensure that bytes are read from a given DVD in the same order as they were written, but the plugin does not need to ensure that any two DVDs arrive in the same order as they were sent.

1.2 Key derivation

BTP attempts to ensure the forward secrecy of connections, meaning that if an adversary gains control of a node, the adversary should not be able to decrypt any of the node's previous connections.

To ensure forward secrecy, contacts do not keep any long-term shared secrets. Instead, each pair of contacts uses several sequences of ephemeral shared secrets. One sequence is allocated to each transport over which the contacts communicate. Each secret in the sequence is used to derive the keys for a single connection. The secret is destroyed after deriving the keys, and the keys are destroyed when the connection is closed.

To initialise their sequences of shared secrets, the contacts establish an incoming secret, i, and an outgoing secret, o, during the initial face-to-face invitation process, such that each contact's incoming secret is equal to the other's outgoing secret.

Each contact uses a key derivation function f(a,b,c) to derive the secrets i_0,0 ... i_T,0 and o_0,0 ... o_T,0 from i and o, where i_n,0 = f(i,n,0) and o_n,0 = f(o,n,0). The incoming and outgoing secrets, i and o, are then destroyed.

The parameter T is the number of sequences of secrets the contacts share. Since one sequence will be allocated to each transport over which the contacts communicate, they will not be able to use more than T transports.

The same key derivation function is used to derive a sequence of ephemeral secrets from each secret i_0,0 ... i_T,0 and o_0,0 ... o_T,0, where i_n,m+1 = f(i_n,m,n,m+1) and o_n,m+1 = f(o_n,m,n,m+1).

Six keys are derived from each ephemeral secret: an authentication key for use in each direction, an encryption key for use in each direction, and a tag key for use in each direction.

1.3 Tags

Every connection begins with a 16-byte pseudo-random tag that is generated with the sender's tag key. The intended recipient of the connection generates the same tag in advance and uses it to recognise the connection. To anyone but the intended recipient, the tag is indistinguishable from random data.

The purpose of the tag is to allow the recipient to recognise the connection while making it difficult for observers to identify BTP through techniques such as deep packet inspection.

Each connection's tag consists of an all-zero plaintext encrypted with the sender's tag key using AES-256 in ECB mode. Since every connection uses a unique tag key, every connection also has a unique tag.

1.4 Frame format

The tag is followed by a series of encrypted frames. The frames sent in each direction across each connection are numbered sequentially from zero. No more than 2³² frames may be sent in either direction. Each frame consists of a nine-byte header, zero or more bytes of payload, zero or more bytes of padding and a 48-byte message authentication code. The header has the following format:

Bits 0-31: Frame number as a big-endian unsigned 32-bit integer.
Bits 32-47: Length of the optional payload in bytes as a big-endian unsigned 16-bit integer.
Bits 48-63: Length of the optional padding in bytes as a big-endian unsigned 16-bit integer.
Bits 64-71: Flags. Bit 64 is set to one if this is the last frame in this direction. All other bits are set to zero.

The MAC is calculated over the header, payload and padding with the sender's authentication key using HMAC-SHA-384. The entire frame, including the MAC, is then encrypted with the sender's encryption key using AES-256 in CTR mode. The counter has the following format:

Bits 0-79: Zero.
Bits 80-111: Frame number as a big-endian unsigned 32-bit integer.
Bits 112-127: Block counter, initialised to zero and incremented after each block is encrypted.

The maximum length of a frame including header and MAC is 2¹⁶ bytes (64 KiB), so the sum of the payload length and the padding length must be less than or equal to 2¹⁶ - 57. If padding is used, all padding bytes must be set to zero.

CTR mode is a stream mode, so the frame length does not need to be a multiple of the cipher's block size.

After receiving, decrypting and authenticating an entire frame, the recipient discards any padding and processes the payload, if any. If a frame is badly formatted or fails the authentication check, the connection must be closed immediately without processing the frame's payload.

1.5 Transport indices and connection numbers

Every connection is associated with a transport index and a connection number. The transport index is a 16-bit unsigned integer that uniquely identifies a transport plugin within the scope of a given sender. Each node assigns its own indices to plugins and informs its contacts of the index assigned to each plugin (Briar uses BMP for this purpose, but BTP does not depend on the way in which transport indices are communicated).

The connection number is a 32-bit unsigned integer that uniquely identifies a connection within the scope of a given sender, recipient and transport. To prevent replay attacks, connection numbers must never be reused. Each node must persistently store a monotonically increasing counter for allocating connection numbers to each transport, and the counter must never wrap.

For a simplex connection with transport index n and connection number m, the sender derives the authentication, encryption and tag keys from the ephemeral secret o_n,m. The recipient derives the same keys from i_n,m (recall that each contact's i is equal to the other's o). Both endpoints use the sender's transport index for the plugin in question.

For a duplex connection with transport index n and connection number m, the initiator derives the keys for the initiator's side of the connection from o_n,m and the keys for the responder's side of the connection from i_n,m. The responder derives the same keys from i_n,m and o_n,m, respectively. Both endpoints use the initiator's transport index for the plugin in question.

1.6 Replay protection

After initialising their sequences of ephemeral secrets, new contacts prepare each transport for use by setting its connection number in both directions to zero and initialising its connection reordering window. The connection reordering window is a mechanism that prevents replay attacks while allowing for the fact that some transports may reorder connections to a limited extent. It is broadly similar to the replay protection mechanism in IPSec.

For each transport, a potential recipient keeps a sliding window of W connection numbers with respect to each potential sender. This window is centred on a number one greater than the highest connection number so far received from the sender. The W / 2 connection numbers below the centre and the W / 2 - 1 numbers above it are contained in the window, with the exception that the window never contains a connection number less than zero or greater than the maximum possible connection number, 2³² - 1. When the window is first initialised it is centred on zero.

The recipient persistently stores the highest connection number so far received from each sender, together with a record of whether each connection number in the window has so far been received. The persistent storage of these values is vital for preventing replay attacks.

For each connection number in the window that has not yet been received, the recipient derives the sender's tag key for the connection, calculates the tag that the sender will use, and stores the resulting expected tag for comparison with the initial bytes of incoming connections.

By examining the first 16 bytes of an incoming connection, the recipient can tell which contact is the sender, over which transport the connection should have arrived, and which keys should be used to decrypt and authenticate the connection's frames.

Receipt of an expected tag does not prove the authenticity or integrity of the subsequent frames; it only allows the recipient to look up the appropriate keys for checking the authenticity and integrity of the frames.

The maximum number of expected tags a recipient may have to store at any time is W - 1 per transport per sender. Unlike the connection reordering window, the expected tags do not need to be stored persistently, since they can be recalculated at any time using the connection reordering window and the appropriate tag keys.

Depending on the transport over which a connection arrives, the recipient may need to check the connection's tag against the expected tags for all senders or only one sender. The check does not involve a substantial cost in any case, since it can be done with a simple hashtable lookup.

If a connection with an unexpected tag is received, the connection must be closed immediately. Note that this may allow an adversary to test whether a given transport endpoint (such as a TCP port) is accepting BTP connections: the adversary opens a connection, sends 15 bytes of data, waits, then sends another byte. If the connection is never closed after 15 bytes of data but is always closed after 16 bytes, the endpoint may be accepting BTP connections. Preventing this kind of testing is a matter for future work.

If a connection with an expected tag is received, the recipient must update the set of expected tags and persistently store the updated connection reordering window before processing any frames. This prevents an adversary from replaying legitimate connections.

When a duplex connection is first established, the responder may start sending data as soon as the tag has been received, since the tag identifies (though does not authenticate) the initiator of the connection. This creates another opportunity for an adversary to test whether a given transport endpoint is accepting BTP connections: the adversary allows the first 15 bytes of a legitimate incoming connection to reach the endpoint, but delays the next byte. If the endpoint never responds after 15 bytes but always responds after 16 bytes, the endpoint may be accepting BTP connections. Again, preventing this kind of testing is a matter for future work.

1.7 Payloads

Each frame of a connection contains between zero and 2¹⁶ - 57 bytes of payload. BTP requires frames to be delivered in order, without gaps or duplicates, so the payloads sent in each direction across each connection can be treated as a continuous stream of bytes. BTP could be used to carry any application-layer protocol, although of course many protocols can only operate over duplex connections.

2. BMP - the Briar Messaging Protocol

Briar uses BTP connections between pairs of contacts to carry BMP, an application-layer protocol for synchronising the contacts' private messages, group messages and subscriptions, as well as the information they need for connecting to each other across various transports.

BMP has two variants. Simplex BMP can operate over simplex or duplex connections, while the more bandwidth-efficient duplex BMP can only operate over duplex connections.

Each direction of a BMP connection consists of a series of packets. The following sections describe the function of each packet. The packet formats are described in a separate document.

2.1 Packets in simplex BMP

The simplex variant of BMP uses the following packets, which may be sent in any sequence.

2.1.1 Batch

A batch packet contains one or more messages, which may be any mixture of private messages and group messages. A private message is sent from a user to one of her contacts, and is not intended for forwarding. A group message is addressed to a group, and may be forwarded to any of the group's subscribers.

Any group messages included in a batch should be addressed to groups to which the sender of the batch knows the recipient subscribes, and to which the recipient of the batch knows the sender subscribes. However, since subscriptions and subscription visibilities may change while packets are in transit, a batch may contain messages addressed to a group for which the recipient does not have a subscription that is visible to the sender at the time of receipt. The recipient must discard any such messages. This prevents the sender from testing whether the recipient subscribes to a group that is not visible to the sender by sending a message addressed to that group and seeing whether it is propagated.

Each batch is uniquely identified by a cryptographic hash of its contents. The sender persistently stores this identifier, together with the unique identifiers of the messages contained in the batch, in an outstanding batch record. Messages for which an outstanding batch record exists are not eligible for retransmission to the same contact until the outstanding batch record is removed.

The recipient of a batch marks the messages in the batch as having been seen by the sender. This makes the messages permanently ineligible for transmission to the sender of the batch.

2.1.2 Ack

An ack packet contains one or more unique identifiers of batches from the contact to whom the ack is sent. An ack only indicates that the corresponding batches were received; it does not indicate anything about how the messages contained in the batches were processed. Batches should always be acknowledged, even if all the messages they contain are discarded.

The recipient of an ack removes any corresponding outstanding batch records and marks the messages they contain as having been seen by the sender of the ack. This makes the messages permanently ineligible for retransmission to the sender of the ack.

Each outstanding batch record contains a timestamp that records the time at which the batch was transmitted, and a counter called the passover count. When an outstanding batch is acknowledged, the passover counts of any older outstanding batch records pertaining to the same contact are incremented. If a record's passover count reaches R, meaning that R batches sent more recently to the same contact have been acknowledged, the batch is considered to have been lost; the outstanding batch record is removed and the messages it contains become eligible for retransmission. This is similar to the fast retransmission mechanism in TCP.

Note that retransmission can be triggered by batches or acknowledgements being delivered out of order. Setting R to a low value will detect losses more quickly, at the cost of making the protocol more likely to retransmit messages unnecessarily, than setting it to a high value. The current value of R is 5; the choice of an appropriate value for real-world conditions is a matter for further study.

An ack may be sent across a different transport from the batch or batches it acknowledges. If no suitable transport is available then the recipient of a batch may not be able to acknowledge receipt. If the batch's sender does not receive an acknowledgement then the sender's outstanding batch record will not be removed. To limit the amount of state that senders of unacknowledged batches must maintain, messages are removed from outstanding batch records when they expire from the sender's database, and outstanding batch records that no longer contain any messages are removed. Simplex BMP can therefore operate over transports where data only ever travels in one direction, though it cannot detect losses over such transports.

2.1.3 Subscription update

A subscription update packet lists zero or more groups to which the sender subscribes, and which the sender has chosen to make visible to the recipient. Each group is associated with a timestamp that is set to the later of two times: the time when the sender's subscription to the group began, and the expiry time of the sender's database.

The expiry time of the database is equal to the timestamp of the oldest message in the database, rounded down to a multiple of one hour. Rounding prevents the expiry time from revealing the presence or absence of any particular message, which might reveal to a contact the existence of a subscription that would not otherwise be visible to that contact.

If the database is empty then its expiry time is zero (midnight UTC on 1 January 1970). Since no Briar subscriptions existed at that time, the timestamp associated with every group will be the time when the sender's subscription to the group began.

Subscription timestamps serve the dual purpose of preventing the transmission of messages that will immediately expire from the recipient's database, and preventing new subscribers from being overwhelmed by floods of old messages.

A subscription update packet also has a timestamp indicating when the update itself was created. The recipient of a subscription update should ignore it if a more recently created subscription update has been received from the same contact. Otherwise the recipient should replace any existing record of the sender's subscriptions with the subscriptions listed in the update, and thereafter should only send the sender messages addressed to the listed groups. For each group, the recipient of the update should only send the sender messages with timestamps that are greater than or equal to the timestamp associated with the group.

Note that if subscription updates are lost, reordered or delayed, contacts may have out-of-date information about each other's subscriptions, and this situation may persist indefinitely.

The number of subscriptions that may be revealed to a given contact is currently limited by the maximum length of a subscription update packet. The design of an incremental update mechanism is a matter for future work.

2.1.4 Transport update

A transport update packet contains zero or more named collections of key-value pairs, which are called transport properties. These describe ways in which connections may be made to the sender of the transport update. For example, the transport properties of a TCP transport plugin might specify an IP address and port number.

A transport update packet also has a timestamp indicating when the update itself was created. The recipient of a transport update should ignore it if a more recently created transport update has been received from the same contact. Otherwise the recipient should replace any existing record of the sender's transport properties with the properties listed in the update, and thereafter should only use those properties to contact the sender, with the exception that any currently active connections need not be closed.

The loss, reordering or delay of transport updates may cause contacts to have out-of-date information about each other's transport properties, and this situation may persist indefinitely. If contacts find themselves unable to establish a connection over any transport due to changes in their transport properties, they may have to repeat the initial face-to-face exchange of invitations in order to resynchronise their properties.

The total length of the properties that may be sent to a given contact is currently limited by the maximum length of a transport update packet. The design of an incremental update mechanism is a matter for future work.

2.2 Packets in duplex BMP

In addition to the packets used in the simplex variant of BMP, the duplex variant uses two packets that take advantage of bidirectional communication to avoid transmitting redundant copies of messages.

2.2.1 Offer

An offer packet contains the unique identifiers of one or more messages, which may be any mixture of private messages and group messages. Any group messages included in an offer should be addressed to groups to which the sender of the offer knows the recipient subscribes, and to which the recipient of the offer knows the sender subscribes. A group message should not be offered to a contact if it is older than the timestamp associated with the group in the most recently created subscription update received from the contact.

The sender of an offer keeps a copy of the list of offered messages until the recipient responds. An offer is only valid within the scope of a given connection, so the list of messages does not require persistent storage and can be discarded if the connection is closed without receiving a response.

2.2.2 Request

A request packet is sent in response to an offer. The request contains a bitmap indicating which of the messages listed in the offer the sender of the request would like to receive. There is a one-to-one correspondence between offer packets and request packets.

To prevent the sender of an offer from testing whether the recipient subscribes to a group that is not visible to the sender by offering a message addressed to that group, the recipient of an offer must request each message listed in the offer if either (a) the recipient does not have a copy of the message, or (b) the recipient has a copy, but the message is addressed to a group that is not visible to the sender.

The recipient of a request uses the bitmap contained in the request and the locally stored list of offered messages to generate zero or more batch packets in response to the request. Not all of the requested messages will necessarily be sent - messages may have expired from the database, or changes to subscriptions or subscription visibilities may have occurred since the offer was sent.

After sending the batches, the recipient of the request may send another offer. Acks, subscription updates and transport updates may be sent at any time.

2.3 Protocol states

Duplex BMP places the following constraints on the sequence in which packets may be transmitted:

Each end of a duplex BMP connection has a state, which is either SEND_OFFER, AWAIT_REQUEST or SEND_BATCHES.
When the connection is first opened, both ends are in the state SEND_OFFER.
Offers must only be sent when the sender's state is SEND_OFFER. Sending an offer changes the sender's state from SEND_OFFER to AWAIT_REQUEST.
Offers may be received in any state. The recipient of an offer responds with a single request. Receiving and responding to an offer does not cause a change of state.
If a request is received when the recipient's state is not AWAIT_REQUEST, an error has occurred and the connection must be closed immediately. Receiving a request changes the recipient's state from AWAIT_REQUEST to SEND_BATCHES. The recipient of the request responds with zero or more batch packets. When there are no more batches to send, the state of the recipient of the request changes to SEND_OFFER.
Batches may be received in any state. Receiving a batch does not cause a change of state.
Acks, subscription updates and transport updates may be sent and received in any state. Sending or receiving them does not cause a change of state.

3. Traffic analysis

Although BTP does not explicitly reveal the locations of BMP packet boundaries or even BTP frame boundaries to an observer, the length and timing of the blocks of encrypted data transported between contacts may reveal a great deal.

For example, the offer-request-batch rhythm of duplex BMP may be easy for an observer to recognise (especially since the relationship between the length of an offer and the length of the corresponding request is known), and occasional deviations from that rhythm may be assumed to be subscription and transport updates. The length of a subscription update may reveal information about the sender's subscriptions, while the length of a batch may reveal information about which messages the batch contains.

Any transport that is at risk of observation must therefore take measures to hinder traffic analysis. As with encryption and authentication, it is better to have a single well-tested implementation of such measures than to rely on each transport plugin to provide its own implementation. Briar therefore provides an optional Traffic Analysis Prevention (TAP) mechanism for connections that are at risk of observation.

When TAP is disabled, each BMP packet is sent as a sequence of unpadded BTP frames; the length of the sequence of frames reveals the length of the packet.

When TAP is enabled for a simplex connection, BTP frames are only sent when they are full, with the last frame being padded to the maximum length if necessary. The encrypted data is therefore written to the underlying transport in blocks of 64 KiB, except for the first block, which is the 16-byte tag.

When TAP is enabled for a duplex connection, BTP frames are sent at regular intervals, with each frame being padded to the maximum length if necessary. The encrypted data is therefore written to the underlying transport in blocks of 64 KiB, except for the first block sent by the initiator, which is the 16-byte tag.

The rate at which frames are sent across a TAP-enabled duplex connection depends on the amount of data waiting to be sent. The rate is adjusted incrementally each time a frame is sent: if there is too much data for a full frame then the rate is increased, and if there is not enough data for a full frame then the rate is decreased. Analysing how much information this reveals to an observer about the data sent across the connection is a matter for future work.

Even when TAP is enabled, an observer may be able to guess that encrypted data belongs to a BTP connection by its total length, or by the lengths of the blocks written to the underlying transport. Preventing such identification is a matter for future work.

4. Attacks on BTP

As well as passively observing connections, an adversary may be able to modify the data sent across the underlying transport. For example, the adversary may control a router on the path between two TCP endpoints, or may be able to intercept DVDs sent through the mail and replace them with modified DVDs.

4.1 Reordering frames

An adversary who can locate the boundaries between frames may be able to delete, delay, replay or reorder frames, either within a connection or across connections. If a recipient were to accept such frames then the adversary would be able to manipulate the stream of authenticated bytes processed by the recipient, so BTP must prevent such frames from being accepted.

This is achieved by using a unique authentication key for each connection, and by calculating each frame's MAC over a header that includes the frame number.

If a frame arrives by the wrong connection, the recipient will check the MAC with a different key from the one used by the sender and the authentication check will fail. If a frame arrives by the right connection but in the wrong order, the recipient will notice that the frame number in the header is out of sequence. In either case, the connection will be closed without processing the frame's payload.

4.2 Modifying frames

Each frame's MAC covers the entire frame, including the header, so any modification to the header, payload, padding or MAC will cause the frame to fail the authentication check. An adversary might exploit this fact to locate the boundary between two frames by modifying a connection's encrypted data and observing the point at which the recipient closes the connection. For a connection with TAP disabled, the boundary between two frames might reveal the boundary between two BMP packets. As discussed in section 3, this might in turn reveal sensitive information about the sender's subscriptions, or about which messages are being sent.

To prevent such attacks, any transport that may be at risk of tampering should use TAP. Connections with TAP enabled always send full frames, so the BTP frame boundaries are unrelated to the BMP packet boundaries.

4.3 Attacks on the connection reordering window

As described in section 1.5, each recipient keeps a connection reordering window for each transport and each potential sender, and each sender keeps a connection counter for each transport and each potential recipient. The sender's connection counter is updated whenever a tag is sent, and the recipient's connection window is updated whenever an expected tag is received.

If an adversary is able to prevent tags sent across a given transport from being received, the sender will continue to update the connection counter whenever a tag is sent, until eventually the counter exceeds the recipient's connection window. From that moment on, the sender and recipient will be unable to establish a connection across the transport in question, even if the adversary stops intercepting tags.

Preventing such attacks is an important task for future work.