BQP.md 12 KB
Newer Older
akwizgran's avatar
akwizgran committed
1
# Bramble QR Code Protocol, version 4
akwizgran's avatar
akwizgran committed
2 3 4

## 1 Introduction

akwizgran's avatar
akwizgran committed
5
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.
akwizgran's avatar
akwizgran committed
6 7 8

### 1.1 Outline

akwizgran's avatar
akwizgran committed
9
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.
akwizgran's avatar
akwizgran committed
10

11
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.
akwizgran's avatar
akwizgran committed
12 13 14

### 1.2 Adversary Model 

15
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.
akwizgran's avatar
akwizgran committed
16 17 18

### 1.3 Man-in-the-Middle Attacks

akwizgran's avatar
akwizgran committed
19
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.
akwizgran's avatar
akwizgran committed
20 21 22

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.

akwizgran's avatar
akwizgran committed
23
### 1.4 Notation
akwizgran's avatar
akwizgran committed
24

akwizgran's avatar
akwizgran committed
25 26 27 28 29 30
- || denotes concatenation

- Double quotes denote an ASCII string

- len(x) denotes the length of x in bytes

akwizgran's avatar
akwizgran committed
31
- int\_n(x) denotes x represented as an unsigned, big-endian, n-bit integer
akwizgran's avatar
akwizgran committed
32 33

### 1.5 Cryptographic Primitives
akwizgran's avatar
akwizgran committed
34

35
BQP uses three cryptographic primitives:
akwizgran's avatar
akwizgran committed
36

37
1. **A cryptographic hash function**, H(m)
akwizgran's avatar
akwizgran committed
38

39
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
akwizgran's avatar
akwizgran committed
40

41
3. **A message authentication code**, MAC(k, m), which must be a pseudo-random function
akwizgran's avatar
akwizgran committed
42 43 44

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

akwizgran's avatar
akwizgran committed
45
- HASH(x\_1, ..., x\_n) = H(int\_32(len(x\_1)) || x\_1 || ... || int\_32(len(x\_n)) || x\_n)
akwizgran's avatar
akwizgran committed
46 47 48

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

akwizgran's avatar
akwizgran committed
49
- KDF(k, x\_1, ..., x\_n) = MAC(k, int\_32(len(x\_1)) || x\_1 || ... || int\_32(len(x\_n)) || x\_n)
akwizgran's avatar
akwizgran committed
50 51 52

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.

akwizgran's avatar
akwizgran committed
53
(*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.)
akwizgran's avatar
akwizgran committed
54

akwizgran's avatar
akwizgran committed
55
### 1.6 Protocol Phases
akwizgran's avatar
akwizgran committed
56 57 58 59 60 61 62

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

akwizgran's avatar
akwizgran committed
63
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).
akwizgran's avatar
akwizgran committed
64 65 66 67 68 69 70

(*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.

akwizgran's avatar
akwizgran committed
71
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.
akwizgran's avatar
akwizgran committed
72

akwizgran's avatar
akwizgran committed
73
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**.
akwizgran's avatar
akwizgran committed
74

akwizgran's avatar
akwizgran committed
75
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.
akwizgran's avatar
akwizgran committed
76

akwizgran's avatar
akwizgran committed
77
The peer encodes its scan payload as a QR code, which it displays.
akwizgran's avatar
akwizgran committed
78 79 80

## 3 Connection Establishment Phase

akwizgran's avatar
akwizgran committed
81
Each peer scans the other peer's QR code and extracts the scan payload.
akwizgran's avatar
akwizgran committed
82

akwizgran's avatar
akwizgran committed
83
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.
akwizgran's avatar
akwizgran committed
84

akwizgran's avatar
akwizgran committed
85
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.)
akwizgran's avatar
akwizgran committed
86

akwizgran's avatar
akwizgran committed
87
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.
akwizgran's avatar
akwizgran committed
88 89 90 91 92 93 94

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

akwizgran's avatar
akwizgran committed
95
The peers exchange a series of **records** over the connection chosen by Alice. Each record has the following format:
akwizgran's avatar
akwizgran committed
96

akwizgran's avatar
akwizgran committed
97
- record\_header = int\_8(protocol\_version) || int\_8(record\_type) || int\_16(len(payload))
akwizgran's avatar
akwizgran committed
98

akwizgran's avatar
akwizgran committed
99
- record = record\_header || payload
akwizgran's avatar
akwizgran committed
100

akwizgran's avatar
akwizgran committed
101 102
The maximum length of the payload is 48 KiB.

akwizgran's avatar
akwizgran committed
103
The current version of the protocol is 4, which has three record types:
akwizgran's avatar
akwizgran committed
104 105 106 107 108 109 110

**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.

akwizgran's avatar
akwizgran committed
111 112 113
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.
akwizgran's avatar
akwizgran committed
114

akwizgran's avatar
akwizgran committed
115
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.
akwizgran's avatar
akwizgran committed
116 117 118

### 4.2 Key Exchange

akwizgran's avatar
akwizgran committed
119
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.
akwizgran's avatar
akwizgran committed
120

akwizgran's avatar
akwizgran committed
121
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.
akwizgran's avatar
akwizgran committed
122

akwizgran's avatar
akwizgran committed
123
Alice and Bob calculate the "raw" shared secret as follows:
akwizgran's avatar
akwizgran committed
124

akwizgran's avatar
akwizgran committed
125
- Alice calculates raw\_secret = DH(pri\_a, pub\_b)
akwizgran's avatar
akwizgran committed
126

akwizgran's avatar
akwizgran committed
127
- Bob calculates raw\_secret = DH(pri\_b, pub\_a)
akwizgran's avatar
akwizgran committed
128

akwizgran's avatar
akwizgran committed
129 130 131 132 133
(*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)
akwizgran's avatar
akwizgran committed
134 135 136

### 4.3 Confirmation

akwizgran's avatar
akwizgran committed
137
Each peer knows it has received the correct public key because it has compared the received public key to the commitment in the other peer's scan payload. However, each peer also needs to know that the other peer has received the correct public key. To confirm this, both peers derive a **confirmation key** from the cooked shared secret and use it to calculate two message authentication codes over the scan payloads, q\_a and q\_b, and the public keys, pub\_a and pub\_b:
akwizgran's avatar
akwizgran committed
138

akwizgran's avatar
akwizgran committed
139
- confirmation\_key = KDF(cooked\_secret, "org.briarproject.bramble.keyagreement/CONFIRMATION\_KEY")
akwizgran's avatar
akwizgran committed
140

141
- confirm\_a = KDF(confirmation\_key, "org.briarproject.bramble.keyagreement/CONFIRMATION\_MAC", q\_a, pub\_a, q\_b, pub\_b)
akwizgran's avatar
akwizgran committed
142

143
- confirm\_b = KDF(confirmation\_key, "org.briarproject.bramble.keyagreement/CONFIRMATION\_MAC", q\_b, pub\_b, q\_a, pub\_a)
akwizgran's avatar
akwizgran committed
144

akwizgran's avatar
akwizgran committed
145
Alice sends a CONFIRM record containing confirm\_a. Bob compares the received confirm\_a to the confirm\_a he calculated. If the values do not match, Bob aborts the protocol.
akwizgran's avatar
akwizgran committed
146

akwizgran's avatar
akwizgran committed
147
Bob sends a CONFIRM record containing confirm\_b. Alice compares the received confirm\_b to the confirm\_b she calculated. If the values do not match, Alice aborts the protocol.
akwizgran's avatar
akwizgran committed
148 149 150

## 5 Master Key Derivation Phase

151
Finally, each peer derives the ephemeral master key from the cooked shared secret:
akwizgran's avatar
akwizgran committed
152

153
- ephemeral\_master\_key = KDF(cooked\_secret, "org.briarproject.bramble.keyagreement/MASTER\_SECRET")
akwizgran's avatar
akwizgran committed
154

akwizgran's avatar
akwizgran committed
155
The peers must then delete the raw and cooked shared secrets, allowing the calling application to use the master key for forward secret communication if required.
akwizgran's avatar
akwizgran committed
156

akwizgran's avatar
akwizgran committed
157
The master key is retured to the calling application, together with the open transport connection and a flag indicating whether the peer played the role of Alice or Bob. The application may use the master key and flag to derive keys for communicating securely over the transport connection, or for any other purpose.
akwizgran's avatar
akwizgran committed
158 159 160 161 162 163 164

## 6 Transport Descriptors

The current version of the protocol supports the following transports:

### 6.1 Bluetooth

akwizgran's avatar
akwizgran committed
165
The peer registers a Bluetooth service to accept RFCOMM connections. The service's name is "RFCOMM". The UUID is generated by converting the first 16 bytes of the peer's public key commitment into a UUID, as specified in section 4.4 of RFC 4122. The peer unregisters the service when the protocol terminates.
akwizgran's avatar
akwizgran committed
166

akwizgran's avatar
akwizgran committed
167
The transport identifier is 0. After the identifier the descriptor may contain the peer's Bluetooth address, represented as a BDF raw. If the peer supports Bluetooth but does not know its own address, it should omit the address from the descriptor and make itself discoverable so the other peer can discover its address.
akwizgran's avatar
akwizgran committed
168 169 170

### 6.2 Local Area Network

akwizgran's avatar
akwizgran committed
171
The peer connects to a local area network and opens a port to accept TCP connections. The peer closes the port when the protocol terminates.
akwizgran's avatar
akwizgran committed
172

akwizgran's avatar
akwizgran committed
173
The transport identifier is 1. After the identifier the descriptor contains the peer's IP address, represented as a BDF raw, and the port number as a BDF integer. The address must have link-local or site-local scope.