Skip to content
Snippets Groups Projects
Select Git revision
  • master default protected
1 result
Blame Permalink
BQP.md 11.99 KiB

Bramble QR Code Protocol, version 4

1 Introduction

Bramble QR Code Protocol (BQP) is a key agreement protocol that establishes a shared secret key between two peers. The peers must be near each other and equipped with screens and cameras. They must also have a short-range bidirectional transport over which they can communicate, such as a wireless LAN. The transport is not required to provide any security properties.

1.1 Outline

Each peer displays a QR code containing a commitment to an ephemeral public key and information about how to connect to the peer over various short-range transports. The peers scan each other's QR codes and use the transport information to establish an insecure connection. The peers then exchange public keys matching their commitments over the insecure connection.

Each peer derives a shared secret from its own private key and the received public key, then derives an ephemeral master key from the shared secret. The peers exchange confirmation codes to verify that they have received each other's public keys. The master key is returned to the calling application, which may use it to derive other keys for communicating securely over the transport connection, or for other purposes.

1.2 Adversary Model

We assume the adversary can read, modify, delete and insert traffic on all transports at will. Anything displayed on a screen (specifically QR codes) is assumed to be seen by the adversary.

1.3 Man-in-the-Middle Attacks

The initial exchange of QR codes is assumed to be secure against man-in-the-middle attacks because the users can see which screens they are scanning. This allows each user to be sure that the QR code they scanned was provided by the person with whom they intend to exchange keys.

Man-in-the-middle attacks against the subsequent exchange of public keys over the insecure connection can be detected by comparing the keys to the commitments contained in the QR codes.

1.4 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.5 Cryptographic Primitives

BQP uses three cryptographic primitives:

  1. A cryptographic hash function, H(m)

  2. A key agreement function, DH(pri, pub), where pri is one party's private key and pub is the other party's public key

  3. A message authentication code, MAC(k, m), which must be a pseudo-random function

We use H(m) to define a multi-argument hash function:

  • HASH(x_1, ..., x_n) = H(int_32(len(x_1)) || x_1 || ... || int_32(len(x_n)) || x_n)

We use MAC(k, m) to define a key derivation function:

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

All hashes are HASH_LEN bytes, all symmetric keys are KEY_LEN bytes, and the output of MAC(k, m) is MAC_LEN bytes. For simplicity we require that HASH_LEN = KEY_LEN = MAC_LEN.

(Note: The current version of the protocol uses BLAKE2b as the hash function and keyed BLAKE2b as the message authentication code, both with an output length of 32 bytes. This gives HASH_LEN = KEY_LEN = MAC_LEN = 32. The key agreement function is X25519.)

1.6 Protocol Phases

Each run of the protocol has four phases: preparation, connection establishment, key agreement, and master key derivation. The phases are described in the following sections.

2 Preparation Phase

2.1 Key Generation

Each peer starts by generating a fresh ephemeral key pair (pri, pub). The peer's public key commitment is the first COMMIT_LEN bytes of HASH("org.briarproject.bramble.keyagreement/COMMIT", pub).

(Note: In the current version of the protocol, COMMIT_LEN = 16. This is sufficient for 128-bit security because the adversary cannot make use of the birthday paradox: a successful man-in-the-middle attack requires a public key with a commitment that matches the victim's commitment, rather than two public keys with commitments that match each other.)

2.2 Scan Payloads

BQP uses Bramble Data Format (BDF) to represent structured data. BDF has six primitive types (null, boolean, integer, float, string, raw) and two container types (list, dictionary). BDF is specified in a separate document.

Each peer creates a scan payload, which starts with a byte containing the protocol version as an unsigned 8-bit integer. The current protocol version is 4. If a peer scans a QR code with a version lower than 4, or with version 89, it must abort the protocol. Peers may accept QR codes with higher versions if they know how to handle them, but version 89 is reserved.

The remainder of the scan payload is a BDF list with one or more elements. The first element is the public key commitment, represented as a BDF raw. The remaining elements are transport descriptors.

Each transport descriptor describes how to connect to the peer over a short-range transport. The descriptor is a BDF list with one or more elements. The first element is a transport identifier, represented as a BDF integer. The remaining elements are transport-dependent. Descriptors for the currently supported transports are defined below. Peers should ignore descriptors with unrecognised transport identifiers without aborting the protocol.

The peer encodes its scan payload as a QR code, which it displays.

3 Connection Establishment Phase

Each peer scans the other peer's QR code and extracts the scan payload.

A peer may immediately connect to the other peer over any transports supported by both peers, simultaneously or in any order. This may result in one or more transport connections being established by either or both peers.

If no incoming or outgoing connection is established within CONNECTION_TIMEOUT seconds of scanning the QR code, the peer aborts the protocol. (Note: The current version of BQP uses CONNECTION_TIMEOUT = 60 seconds, which provides a reasonable tradeoff between reliability and responsiveness.)

In the remainder of the protocol, the peers are assigned roles according to the lexicographic order of their scan payloads, compared as byte strings. The peer with the earlier payload plays the role of Alice, while the peer with the later payload plays the role of Bob. Each peer can determine its role after scanning the other peer's QR code. 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.

If multiple transport connections are established, Alice decides which connection to use and closes any other connections. Bob waits for Alice to start communicating over one of the connections and then closes any other connections.

4 Key Agreement Phase

4.1 Records

The peers exchange a series of records over the connection chosen by Alice. Each record has the following format:

  • record_header = int_8(protocol_version) || int_8(record_type) || int_16(len(payload))

  • record = record_header || payload

The maximum length of the payload is 48 KiB.

The current version of the protocol is 4, which has three record types:

0: KEY - The payload consists of the sender's ephemeral public key.

1: CONFIRM - The payload consists of a confirmation code.

2: ABORT - The payload is empty.

If a peer aborts the protocol it must send an ABORT record unless it has already sent one. If a peer receives an ABORT record it must abort the protocol.

If a peer receives a record with a protocol version lower than 4, or with version 89, it must abort the protocol. Peers may accept records with higher versions if they know how to handle them, but version 89 is reserved.

Peers should ignore any records with unrecognised record types without aborting the protocol. If a peer receives a record with a recognised protocol version and record type at an unexpected stage in the protocol, it must abort the protocol.

4.2 Key Exchange

Alice begins by sending a KEY record containing her ephemeral public key, pub_a. Bob compares the first COMMIT_LEN bytes of HASH("org.briarproject.bramble.keyagreement/COMMIT", pub_a) to the commitment in Alice's scan payload. If the key does not match the commitment, Bob aborts the protocol.

Bob sends a KEY record containing his ephemeral public key, pub_b. Alice compares the first COMMIT_LEN bytes of HASH("org.briarproject.bramble.keyagreement/COMMIT", pub_b) to the commitment in Bob's scan payload code. If the key does not match the commitment, Alice aborts the protocol.

Alice and Bob calculate the "raw" shared secret as follows:

  • Alice calculates raw_secret = DH(pri_a, pub_b)

  • Bob calculates raw_secret = DH(pri_b, pub_a)

(Note: If a peer calculates an X25519 raw shared secret that is all zeroes, the peer must abort the protocol.)

If the adversary has not modified the KEY records, both peers will calculate the same shared secret. The peers then derive a "cooked" shared secret that incorporates the protocol version and both peers' public keys:

  • cooked_secret = HASH("org.briarproject.bramble.keyagreement/SHARED_SECRET", raw_secret, int_8(protocol_version), pub_a, pub_b)