|
|
BTP is a transport layer security protocol for delay-tolerant networks. It provides confidentiality, authenticity, integrity, forward secrecy and protocol obfuscation for simplex byte streams. It can operate over any transport that can deliver a simplex stream of bytes from a sender to a recipient on a best-effort basis, meaning that streams may be delayed, lost, reordered or duplicated by the transport. A memory card tied to a carrier pigeon is one example of such a transport.
|
|
|
|
|
|
When operating over a duplex transport, BTP treats each duplex connection as two independent simplex streams.
|
|
|
|
|
|
The underlying transport is not required to provide any security properties. We assume the adversary can read, modify, delete and insert traffic on the underlying transport at will.
|
|
|
|
|
|
### Notation
|
|
|
|
|
|
We use || to denote concatenation, double quotes to denote an ASCII string, int(x) to denote x represented as a 64-bit integer, and len(x) to denote the length of x in bytes, represented as a 32-bit integer. All integers in BTP are big-endian.
|
|
|
|
|
|
### Crypto primitives
|
|
|
|
|
|
BTP uses the following cryptographic primitives:
|
|
|
|
|
|
* A message authentication code, MAC(k, m)
|
|
|
* An authenticated cipher, ENC(k, n, m) and DEC(k, n, m), where n is a nonce
|
|
|
|
|
|
We use MAC(k, m) to define a key derivation function:
|
|
|
|
|
|
* `KDF(k, x_1, ..., x_n) == MAC(k, len(x_1) || x_1 || ... || len(x_n) || x_n)`
|
|
|
|
|
|
All keys are KEY_LEN bytes and all nonces are NONCE_LEN bytes. The output of MAC(k, m) is MAC_LEN bytes, and the output of ENC(k, n, m) is AUTH_LEN bytes longer than m. For simplicity we require that MAC_LEN == KEY_LEN.
|
|
|
|
|
|
> Implementation note: We propose to use keyed BLAKE2s as the message authentication code and XSalsa20/Poly1305 as the authenticated cipher. This gives KEY_LEN = MAC_LEN = 32, NONCE_LEN = 24, and AUTH_LEN = 16.
|
|
|
|
|
|
### Initial state
|
|
|
|
|
|
Before two devices can communicate using BTP they must establish the following state:
|
|
|
|
|
|
* A shared secret key_len bytes long, S
|
|
|
* A timestamp in seconds since the Unix epoch, T
|
|
|
* The maximum expected difference between the devices' clocks in seconds, D
|
|
|
* The maximum expected latency of the transport in seconds, L
|
|
|
|
|
|
How this state is established is outside the scope of BTP. The devices must establish a separate S for each transport over which they wish to communicate. T must be in the past according to both devices' clocks.
|
|
|
|
|
|
The devices must also agree which of them will play the role of Alice and which will play the role of Bob. The roles are identical except for some key derivation constants.
|
|
|
|
|
|
> Implementation note: Shared secrets for multiple transports may be derived from an initial shared secret established by a separate key agreement protocol. T may be hard-coded or negotiated by the key agreement protocol. D and L may be hard-coded. We propose to use D = 86400 (24 hours).
|
|
|
|
|
|
### Key derivation
|
|
|
|
|
|
Each device derives four initial keys from S. Alice derives her keys as follows:
|
|
|
|
|
|
* `outgoing_tag_key = KDF(S, "ALICE_TAG_KEY")`
|
|
|
* `outgoing_header_key = KDF(S, "ALICE_HEADER_KEY")`
|
|
|
* `incoming_tag_key = KDF(S, "BOB_TAG_KEY")`
|
|
|
* `incoming_header_key = KDF(S, "BOB_HEADER_KEY")`
|
|
|
|
|
|
Bob derives his keys as follows:
|
|
|
|
|
|
* `outgoing_tag_key = KDF(S, "BOB_TAG_KEY")`
|
|
|
* `outgoing_header_key = KDF(S, "BOB_HEADER_KEY")`
|
|
|
* `incoming_tag_key = KDF(S, "ALICE_TAG_KEY")`
|
|
|
* `incoming_header_key = KDF(S, "ALICE_HEADER_KEY")`
|
|
|
|
|
|
Thus Alice's outgoing keys are Bob's incoming keys and vice versa. Both devices then erase S.
|
|
|
|
|
|
### Key rotation
|
|
|
|
|
|
BTP achieves forward secrecy by rotating keys periodically. The key rotation function is deterministic, so devices that start from the same S will have matching keys in each rotation period.
|
|
|
|
|
|
The length of each rotation period is R = D + L seconds. Rotation periods are aligned with the Unix epoch.
|
|
|
|
|
|
The initial keys derived from S are the keys for rotation period 0. The timestamp T falls in rotation period 1. The keys for the i^th rotation period are derived from the previous period's keys as follows:
|
|
|
|
|
|
* `outgoing_tag_key = KDF(outgoing_tag_key, "ROTATE", int(i))`
|
|
|
* `outgoing_header_key = KDF(outgoing_header_key, "ROTATE", int(i))`
|
|
|
* `incoming_tag_key = KDF(incoming_tag_key, "ROTATE", int(i))`
|
|
|
* `incoming_header_key = KDF(incoming_header_key, "ROTATE", int(i))`
|
|
|
|
|
|
If the sender starts sending a stream at time t according to the sender's clock, the recipient may start receiving the stream at any time between t - D and t + D + L according to the recipient's clock. Therefore each device must retain the incoming keys for the previous, current and next rotation periods, along with the outgoing keys for the current rotation period. Keys are erased when they are no longer needed.
|
|
|
|
|
|
### Tags
|
|
|
|
|
|
Each stream starts with a pseudo-random tag, which is TAG_LEN bytes long. The recipient calculates the 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 rotation period is the first TAG_LEN bytes of MAC(k, int(i)), where k is the sender's outgoing tag key. For simplicity we require that TAG_LEN <= MAC_LEN. Streams are counted from zero in each rotation period.
|
|
|
|
|
|
> Implementation note: We propose to use TAG_LEN = 16.
|
|
|
|
|
|
### Reordering windows
|
|
|
|
|
|
BTP uses reordering windows to allow the recipient to recognise streams that are received out of order due to reordering or loss by the underlying transport. The recipient maintains reordering windows for the previous, current and next rotation periods. Each window contains *W* tags, each of which is marked as seen or unseen. When a previously unseen tag is marked as seen, the window slides according to the following rules:
|
|
|
|
|
|
1. Slide the window until all tags in the top half of the window are unseen.
|
|
|
2. Slide the window until the lowest tag in the window is unseen.
|
|
|
|
|
|
If the window slides past a tag that has not been seen, the recipient can no longer recognise the corresponding stream. Larger values of *W* make it possible to tolerate more reordering and loss by the underlying transport, but require the recipient to maintain larger windows.
|
|
|
|
|
|
To avoid reusing tags, which would allow the adversary to distinguish BTP traffic from random, the sender must persistently store the number of streams sent to the recipient in the current rotation period. To avoid accepting replayed streams, the recipient must persistently store the reordering windows for the previous, current and next rotation periods.
|
|
|
|
|
|
> Implementation note: We propose to use W = 32. Different values of W may be suitable for different transports.
|
|
|
|
|
|
### Stream header
|
|
|
|
|
|
The pseudo-random tag is followed by the stream header, which consists of a random initialisation vector followed by an ephemeral key encrypted and authenticated with the sender's outgoing header key, using the random IV as the nonce. The stream header is NONCE_LEN + KEY_LEN + AUTH_LEN bytes long. The ephemeral key is used for encrypting and authenticating the rest of the stream.
|
|
|
|
|
|
### Frames
|
|
|
|
|
|
The remainder of the stream consists of one or more frames. Each frame has a fixed-length header and a variable-length body that may contain data, padding, neither or both. The frames are numbered from zero. A stream may not contain more than 2^63 frames.
|
|
|
|
|
|
The plaintext frame header is 4 bytes long, with the following format:
|
|
|
|
|
|
* Bit 0: Final frame flag, set to one if this is the last frame in the stream
|
|
|
* Bits 1-15: Length of the data in bytes as a 15-bit integer
|
|
|
* Bit 16: Zero
|
|
|
* Bits 17-31: Length of the padding in bytes as a 15-bit integer
|
|
|
|
|
|
The plaintext frame body contains the data and padding. The total length of the data and padding must be less than 2^15 bytes. If any padding is present it must all be zeroes.
|
|
|
|
|
|
The header and body are encrypted and authenticated separately using the ephemeral key and deterministic nonces, which are not sent.
|
|
|
|
|
|
The nonce for the frame header is NONCE_LEN bytes long, with the following format:
|
|
|
|
|
|
* Bit 0: Header flag, set to one
|
|
|
* Bits 1-63: Frame number as a 63-bit integer
|
|
|
* Remaining bits: Zero
|
|
|
|
|
|
The nonce for the frame body is NONCE_LEN bytes long, with the following format:
|
|
|
|
|
|
* Bit 0: Header flag, set to zero
|
|
|
* Bits 1-63: Frame number as a 63-bit integer
|
|
|
* Remaining bits: Zero
|
|
|
|
|
|
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. |