BTP.md



Bramble Transport Protocol, version 4

1 Introduction
Bramble Transport Protocol (BTP) is a transport layer security protocol suitable for delay-tolerant networks. It provides a secure channel between two peers, ensuring the confidentiality, integrity, authenticity and forward secrecy of their communication across a wide range of underlying transports.
BTP's main components are a time-based key management protocol and a wire protocol for securely carrying streams of data.
BTP can operate over any transport that can deliver a stream of bytes from one device to another on a best-effort basis, meaning that streams may be delayed, lost, reordered or duplicated. The underlying transport is not required to provide any security properties.
The BTP wire protocol includes optional padding and does not use any timeouts, handshakes or plaintext headers. This makes BTP compatible with traffic analysis prevention techniques such as traffic morphing, with the goal of making it difficult to distinguish BTP from other protocols.
BTP does not attempt to conceal the identities of the communicating parties or the fact that they are communicating - in other words, it does not provide anonymity, unlinkability or unobservability. If such properties are required, BTP can use an anonymity system such as Tor as the underlying transport.
Forward secrecy is achieved by establishing an initial root key between two peers and using a one-way key derivation function to derive a series of temporary keys from the root key. Once both peers have deleted a given key, it cannot be re-derived if the peer devices are later compromised.

1.1 Motivation
The primary motivation for BTP's design is to provide a versatile building block for censorship-resistant communication systems. BTP is therefore designed to be used across a diverse mixture of transports, both online and offline, with varying properties. The transports are not given access to unencrypted or unauthenticated data; nor are they required to ensure the confidentiality, integrity, authenticity or forward secrecy of the data they carry. BTP is responsible for providing those properties.
BTP is unusual in that it provides forward secrecy even for transports where one of the peers can only send and the other can only receive. It can be used on transports with very high latency, such as disks sent through the mail.

1.2 Design Requirements


Flexibility
The protocol should be able to operate over a wide range of underlying transports with bandwidths varying from kilobits to gigabits per second, and with latencies varying from milliseconds to days.


Layering
The protocol should treat each underlying transport connection as a unidirectional or bidirectional sequence of bytes with a simple socket-like interface (open, read/write, close). Likewise, the protocol should provide a socket-like interface to higher protocol layers.


Concealability
The protocol should not reveal any plaintext fields that would make it easily distinguishable from other protocols. It should be compatible with techniques such as traffic morphing that are designed to resist traffic analysis and traffic classification.


Confidentiality
The adversary should not be able to learn what data is being carried by the protocol.


Integrity
The adversary should not be able to cause either peer to read data from the BTP layer that differs from the data written to the BTP layer by the other peer. If the adversary truncates the data, the receiving peer should be able to detect that this has happened.


Authenticity
The adversary should not be able to cause either peer to accept data from any third party as though it came from the other peer.


Forward Secrecy
The adversary should not be able to learn what data was carried by the protocol if, at some later time, the adversary compromises one or both of the peer devices.


The protocol is not required to conceal the identities of the communicating parties or the fact that they are communicating.

1.3 Adversary Model
BTP is intended to be used in systems that resist surveillance and censorship by powerful adversaries, such as governments. We must therefore assume:


The adversary can observe, block, delay, replay and modify traffic on all underlying transports.


The adversary can choose the data written to the BTP layer by higher protocol layers.


The adversary has a limited ability to compromise peer devices. If a device is compromised, the adversary can access any information held in the device's volatile memory or persistent storage.


The adversary cannot break standard cryptographic primitives such as ciphers and message authentication codes.


1.4 Underlying Transports
BTP can operate over any transport that can deliver a unidirectional or bidirectional sequence of bytes from one device to another on a best-effort basis. We refer to this sequence of bytes as a connection. If the connection is unidirectional then BTP uses it to carry an encrypted and authenticated sequence of bytes, which we refer to as a stream. If the connection is bidirectional then BTP uses it to carry two separate streams, one in each direction.
Transports must ensure that the bytes within a given connection arrive in the correct order. If the bytes within a connection are reordered then none of BTP's security properties are lost, but it will reject the stream or streams carried by the connection.
Transport connections themselves may be reordered. There is no requirement that all connections reach the intended recipient.
If one endpoint of a connection starts writing to the transport at time T0 and the other endpoint starts reading from the transport at time T1, we call T1 - T0 the latency of the connection. For a bidirectional connection we define the latency of the connection to be the maximum latency in either direction.
If a transport imposes a maximum connection length, such as the storage capacity of a disk, BTP passes this restriction on to higher protocol layers by limiting the stream length; it does not fragment a stream across multiple connections. BTP cannot use transport connections with less capacity than the minimum length of a stream. (Note: In the current version of the protocol, the minimum length of a stream is 134 bytes.)
Using BTP over a datagram-oriented transport such as UDP (which does not have a concept of connections) would require the use of an intermediate connection-oriented protocol such as UDT to provide an ordered sequence of bytes in each direction.

1.5 Prerequisites
Before two peers can communicate using BTP they must agree on the following properties:


Roles of the peers
The peers must agree which of them will play the role of Alice and which the role of Bob. The roles are identical except for some key derivation constants. It does not matter which peer plays which role, as long as one is Alice and the other Bob.


Maximum clock difference
The peers must agree on the maximum expected difference between their clocks, D. This value may be hard-coded. The current version of BTP assumes D = 86,400 seconds (24 hours). This is to accommodate mobile devices, which often have inaccurate clocks.


Maximum latency
The peers must agree on the maximum expected latency, L, of each transport they wish to use. This value may be hard-coded. For any given transport we can choose some maximum latency that is unlikely to be exceeded under normal conditions. For example, we might choose one minute as the maximum latency for TCP, or two weeks as the maximum latency for disks sent through the mail. If a connection exceeds the maximum latency, none of BTP's security properties are lost but it may reject the stream or streams carried by the connection.


1.6 Notation


|| denotes concatenation


Double quotes denote an ASCII string


len(x) denotes the length of x in bytes


int_n(x) denotes x represented as an unsigned, big-endian, n-bit integer


1.7 Cryptographic Primitives
BTP uses three cryptographic primitives:


A pseudo-random function, PRF(k, m)
The output of PRF(k, m) is PRF_LEN bytes. (Note: The current version of BTP uses keyed BLAKE2b with a 32-byte output length as the pseudo-random function, giving PRF_LEN = 32.)


An authenticated cipher, ENC(k, n, m) and DEC(k, n, m), where n is a nonce
The output of ENC(k, n, m) is AUTH_LEN bytes longer than m. All keys are KEY_LEN bytes and all nonces are NONCE_LEN bytes. For simplicity we require that PRF_LEN = KEY_LEN. (Note: The current version of BTP uses XSalsa20/Poly1305 for the authenticated cipher, giving KEY_LEN = 32, NONCE_LEN = 24, and AUTH_LEN = 16.)


A random number generator, R(n), with an output length of n bytes
R(n) must be either an unbiased true random number generator or a cryptographically secure pseudo-random number generator.


2 Key Management Protocol
BTP uses a time-based key management protocol to derive a series of temporary keys from an initial root key. The root key must be KEY_LEN bytes long and contain KEY_LEN * 8 bits of entropy.

2.1 Key Management Modes
BTP has two key management modes, which are suitable for different purposes.
Rotation mode provides forward secrecy for the data being carried, but requires the peers to delete the root key, and any information that could be used to re-derive it, before the temporary keys are used. As well as the root key, rotation mode requires the peers to agree on a timestamp, T, which must be in the past according to both peers' clocks.
Handshake mode does not provide forward secrecy for the data being carried, but allows the peers to retain the root key or information that could be used to re-derive it. Handshake mode does not require a timestamp.
These modes are intended to be complementary. Handshake mode can be used to bootstrap rotation mode by carrying the messages of a key agreement protocol that establishes a root key and timestamp for rotation mode.
The establishment of root keys and timestamps is not handled by BTP itself. BTP is designed to be used with a separate key agreement protocol that securely establishes the initial state. A key agreement protocol for rotation mode must use ephemeral keys, or a combination of static and ephemeral keys, such that the root key cannot be re-derived from information retained by the peers. A key agreement protocol for handshake mode may use static keys, as it is not necessary to prevent the root key from being re-derived.

2.2 Key Derivation Function
BTP uses a key derivation function to derive temporary keys from the root key. The key derivation function is based on PRF(k, m):

KDF(k, x_1, ..., x_n) = PRF(k, int_32(len(x_1)) || x_1 || ... || int_32(len(x_n)) || x_n)


2.3 Time Periods
For each transport, BTP divides time into numbered periods, where period zero starts at the Unix epoch. A different set of temporary keys is used for each period.
The length of each period is D + L seconds, where D is the maximum expected difference between the peers' clocks and L is the maximum expected latency of the transport.
This ensures that if the sender starts sending a stream in period P0 according to the sender's clock, and if D and L are not exceeded, then the recipient will start receiving the stream in period P1 according to the recipient's clock, where abs(P1 - P0) <= 1. In other words, the recipient only needs to retain the temporary keys for the previous, current and next periods.

2.4 Key Derivation for Rotation Mode
In rotation mode, BTP achieves forward secrecy by periodically rotating and deleting the temporary keys. The key derivation function is deterministic, so peers that start from the same root key and timestamp will derive the same temporary keys for each time period. Forward secrecy relies on the one-way nature of the key derivation function: the keys of an earlier period cannot be re-derived from those of a later period.

Initial Keys
The peers derive temporary keys for each transport over which they want to communicate. Each transport is uniquely identified by an ASCII string known to both peers (for example, "org.briarproject.bramble.bluetooth" for Bluetooth).
For each transport, each peer derives four initial keys from the root key. Alice derives her initial keys as follows:


outgoing_tag_key := KDF(root_key, "org.briarproject.bramble.transport/ALICE_TAG_KEY", transport_id)


outgoing_header_key := KDF(root_key, "org.briarproject.bramble.transport/ALICE_HEADER_KEY", transport_id)


incoming_tag_key := KDF(root_key, "org.briarproject.bramble.transport/BOB_TAG_KEY", transport_id)


incoming_header_key := KDF(root_key, "org.briarproject.bramble.transport/BOB_HEADER_KEY", transport_id)


Bob derives his initial keys as follows:


outgoing_tag_key := KDF(root_key, "org.briarproject.bramble.transport/BOB_TAG_KEY", transport_id)


outgoing_header_key := KDF(root_key, "org.briarproject.bramble.transport/BOB_HEADER_KEY", transport_id)


incoming_tag_key := KDF(root_key, "org.briarproject.bramble.transport/ALICE_TAG_KEY", transport_id)


incoming_header_key := KDF(root_key, "org.briarproject.bramble.transport/ALICE_HEADER_KEY", transport_id)


Thus Alice's outgoing keys for each transport are the same as Bob's incoming keys, and vice versa.
After deriving the initial keys, both peers must delete the root key.
The initial keys are used as the temporary keys for period P - 1, where period P contains the timestamp T.
The purpose of the timestamp is to save the cost of rotating keys from period zero to the current period. If it is not possible or convenient to agree a timestamp T along with the root key then T can be hard-coded to some value that is certain to be in the past according to both peers' clocks, at the cost of some extra key rotations.

Key Rotation
The temporary keys for each time period P are derived from the previous period's keys as follows:


outgoing_tag_key := KDF(outgoing_tag_key, "org.briarproject.bramble.transport/ROTATE", int_64(P))


outgoing_header_key := KDF(outgoing_header_key, "org.briarproject.bramble.transport/ROTATE", int_64(P))


incoming_tag_key := KDF(incoming_tag_key, "org.briarproject.bramble.transport/ROTATE", int_64(P))


incoming_header_key := KDF(incoming_header_key, "org.briarproject.bramble.transport/ROTATE", int_64(P))


To ensure forward secrecy, keys must be deleted when they are no longer needed. The outgoing keys for period P must be deleted at the end of period P, while the incoming keys for period P must be deleted at the end of period P + 1.

2.5 Key Derivation for Handshake Mode
In handshake mode, BTP does not provide forward secrecy. The temporary keys for any period can be derived from the root key, which is retained by the peers.
Alice derives her temporary keys for each time period P as follows:


outgoing_tag_key := KDF(root_key, "org.briarproject.bramble.transport/ALICE_HANDSHAKE_TAG_KEY", transport_id, int_64(P))


outgoing_header_key := KDF(root_key, "org.briarproject.bramble.transport/ALICE_HANDSHAKE_HEADER_KEY", transport_id, int_64(P))


incoming_tag_key := KDF(root_key, "org.briarproject.bramble.transport/BOB_HANDSHAKE_TAG_KEY", transport_id, int_64(P))


incoming_header_key := KDF(root_key, "org.briarproject.bramble.transport/BOB_HANDSHAKE_HEADER_KEY", transport_id, int_64(P))


Bob derives his temporary keys as follows:


outgoing_tag_key := KDF(root_key, "org.briarproject.bramble.transport/BOB_HANDSHAKE_TAG_KEY", transport_id, int_64(P))


outgoing_header_key := KDF(root_key, "org.briarproject.bramble.transport/BOB_HANDSHAKE_HEADER_KEY", transport_id, int_64(P))


incoming_tag_key := KDF(root_key, "org.briarproject.bramble.transport/ALICE_HANDSHAKE_TAG_KEY", transport_id, int_64(P))


incoming_header_key := KDF(root_key, "org.briarproject.bramble.transport/ALICE_HANDSHAKE_HEADER_KEY", transport_id, int_64(P))


Thus Alice's outgoing keys for each transport are the same as Bob's incoming keys, and vice versa.
The outgoing keys for period P can be deleted at the end of period P, and the incoming keys for period P can be deleted at the end of period P + 1, but this is not required for security.

3 Wire Protocol
A stream consists of three parts: a pseudo-random tag, a stream header, and one or more frames.

3.1 Tags
Each stream starts with a pseudo-random tag TAG_LEN bytes long. (Note: In the current version of the protocol, TAG_LEN = 16.) The recipient calculates the same tag in advance and uses it to recognise which sender the stream comes from and which incoming header key should be used for the stream.
The tag for the i^th stream from a given sender to a given recipient in a given time period is the first TAG_LEN bytes of PRF(k, int_16(protocol_version) || int_64(i)), where k is the sender's outgoing tag key (which is also the recipient's incoming tag key) and protocol_version is 4 for the current version of BTP. Streams are counted from zero in each time period.

3.2 Stream Headers
The pseudo-random tag is followed by the stream header, which has the following format:


nonce = R(NONCE_LEN)


stream_header_plaintext = int_16(protocol_version) || int_64(stream_number) || ephemeral_cipher_key


stream_header = nonce || ENC(outgoing_header_key, nonce, stream_header_plaintext)


The stream header is NONCE_LEN + 2 + 8 + KEY_LEN + AUTH_LEN = 82 bytes long. The header contains an ephemeral cipher key that is used for encrypting and authenticating the rest of the stream.
The random nonce ensures that even if a stream number is accidentally reused, the combination of header key and nonce will be unique, which is a security requirement of many ciphers.

3.3 Frames
The remainder of the stream consists of one or more frames. Each frame has a fixed-length frame header and a variable-length frame body that may contain data and/or padding. The total length of the data and padding must be no more than 988 bytes, giving a maximum length of 1,024 bytes for an encrypted frame, including the header.
The frames in each stream are numbered from zero. A stream must not contain more than 2⁶³ frames.

Frame Header
The plaintext frame header is four bytes long, with the following format (where bit zero is the most significant):


Bit 0: Final frame flag, set to one if this is the last frame in the stream


Bits 0 - 15: int_16(len(data))


Bits 16 - 31: int_16(len(padding))


The final frame flag overlaps with the most significant bit of the data length, which is unused because the data must be no more than 988 bytes long.
The final frame flag allows the recipient to detect the end of the stream without reading to EOF, which is not possible for all transports on all platforms.

Encryption and Authentication
The header and body of each frame are encrypted and authenticated separately using the ephemeral cipher key and deterministic nonces. The nonces are not sent over the wire.
Each nonce is NONCE_LEN bytes long, with the following format (where bit zero is the most significant):


Bit 0: Header flag, set to one for the frame header or zero for the frame body


Bits 0 - 63: int_64(frame_number)


Remaining bits: Zero


The header flag overlaps with the most significant bit of the frame number, which is unused because a stream must not contain more than 2⁶³ frames.
The encrypted and authenticated frame header is 4 + AUTH_LEN bytes long, while the encrypted and authenticated frame body is AUTH_LEN bytes longer than the data and padding.

4 Reordering Windows
BTP uses reordering windows to allow peers to recognise streams that are received out of order due to reordering or loss of connections by the underlying transport. Each peer maintains reordering windows for the previous, current and next time periods. The windows are used to recognise incoming streams by their tags.
Each window contains W tags, each of which is marked as seen or unseen. W is an implementation parameter. Maintaining larger windows makes it possible to tolerate more reordering or loss by the transport, at the cost of storing more tags. (Note: In the current implementation of the protocol, W = 32.)
When a previously unseen tag is marked as seen, the window slides according to the following rules:


Slide the window until all tags in the top half of the window are unseen.


Slide the window until the lowest tag in the window is unseen.