Debian Codegraph @

Protocol-v3.html

raw
1 <!DOCTYPE html
2 PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
3 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
4 <html><head>
5 <title>Off-the-Record Messaging Protocol version 3</title>
6 <style type="text/css">
7 body { background: white; color: black }
8 h1 { text-align: center }
9 dd ul.note { list-style: none }
10 dl.doublespace dd { margin-bottom: 2ex }
11 </style>
12 </head><body>
13 <h1>Off-the-Record Messaging Protocol version 3</h1>
14 <p>This document describes version 3 of the Off-the-Record Messaging
15 protocol. The main changes over version 2 include:</p>
16 <ul>
17 <li>Both fragmented and unfragmented messages contain sender and
18 recipient instance tags. This avoids an issue on IM networks that
19 always relay all messages to all sessions of a client who is logged
20 in multiple times. In this situation, OTR clients can attempt to
21 establish an OTR session indefinitely if there are interleaving
22 messages from each of the sessions.</li>
23 <li>An extra symmetric key is derived during AKE. This may be used for
24 secure communication over a different channel (e.g., file transfer,
25 voice chat).</li>
26 </ul>
27 <h2>Very high level overview</h2>
28 <p>OTR assumes a network model which provides in-order delivery of
29 messages, but that some messages may not get delivered at all
30 (for example, if the user disconnects). There may be
31 an active attacker, who is allowed to perform a Denial of
32 Service attack, but not to learn the contents of messages.</p>
33 <ol>
34 <li>Alice signals to Bob that she would like (using an OTR Query Message)
35 or is willing (using a whitespace-tagged plaintext message) to use OTR
36 to communicate. Either mechanism should convey the version(s) of OTR
37 that Alice is willing to use.</li>
38 <li>Bob initiates the authenticated key exchange (AKE) with Alice.
39 Versions 2 and 3 of OTR use a variant of the SIGMA protocol as its AKE.</li>
40 <li>Alice and Bob exchange Data Messages to send information to each
41 other.</li>
42 </ol>
43 <h2>High level overview</h2>
44 <h3>Requesting an OTR conversation</h3>
45 <p>There are two ways Alice can inform Bob that she is willing to use
46 the OTR protocol to speak with him: by sending him the OTR Query Message,
47 or by including a special "tag" consisting of whitespace characters in
48 one of her messages to him. Each method also includes a way for Alice
49 to communicate to Bob which versions of the OTR protocol she is willing
50 to speak with him.</p>
51 <p>The semantics of the OTR Query Message are that Alice is
52 <em>requesting</em> that Bob start an OTR conversation with her (if, of
53 course, he is willing and able to do so). On the other hand, the
54 semantics of the whitespace tag are that Alice is merely
55 <em>indicating</em> to Bob that she is willing and able to have an OTR
56 conversation with him. If Bob has a policy of "only use OTR when it's
57 explicitly requested", for example, then he <em>would</em> start an OTR
58 conversation upon receiving an OTR Query Message, but <em>would not</em>
59 upon receiving the whitespace tag.</p>
60 <h3>Authenticated Key Exchange (AKE)</h3>
61 <p>This section outlines the version of the SIGMA protocol used as the
62 AKE. All exponentiations are done modulo a particular 1536-bit prime,
63 and g is a generator of that group, as indicated in the detailed
64 description below. Alice and Bob's long-term authentication public keys
65 are pub<sub>A</sub> and pub<sub>B</sub>, respectively.</p>
66 <p>The general idea is that Alice and Bob do an <em>unauthenticated</em>
67 Diffie-Hellman (D-H) key exchange to set up an encrypted channel, and
68 then do mutual authentication <em>inside</em> that channel.</p>
69 <p>Bob will be initiating the AKE with Alice.</p>
70 <ul>
71 <li>Bob:
72 <ol>
73 <li>Picks a random value r (128 bits)</li>
74 <li>Picks a random value x (at least 320 bits)</li>
75 <li>Sends Alice AES<sub>r</sub>(g<sup>x</sup>), HASH(g<sup>x</sup>)</li>
76 </ol></li>
77 <li>Alice:
78 <ol>
79 <li>Picks a random value y (at least 320 bits)</li>
80 <li>Sends Bob g<sup>y</sup></li>
81 </ol></li>
82 <li>Bob:
83 <ol>
84 <li>Verifies that Alice's g<sup>y</sup> is a legal value (2 &lt;=
85 g<sup>y</sup> &lt;= modulus-2)</li>
86 <li>Computes s = (g<sup>y</sup>)<sup>x</sup></li>
87 <li>Computes two AES keys c, c' and four MAC keys m1, m1', m2, m2' by
88 hashing s in various ways</li>
89 <li>Picks keyid<sub>B</sub>, a serial number for his D-H key
90 g<sup>x</sup></li>
91 <li>Computes M<sub>B</sub> = MAC<sub>m1</sub>(g<sup>x</sup>, g<sup>y</sup>,
92 pub<sub>B</sub>, keyid<sub>B</sub>)</li>
93 <li>Computes X<sub>B</sub> = pub<sub>B</sub>, keyid<sub>B</sub>,
94 sig<sub>B</sub>(M<sub>B</sub>)</li>
95 <li>Sends Alice r, AES<sub>c</sub>(X<sub>B</sub>),
96 MAC<sub>m2</sub>(AES<sub>c</sub>(X<sub>B</sub>))</li>
97 </ol></li>
98 <li>Alice:
99 <ol>
100 <li>Uses r to decrypt the value of g<sup>x</sup> sent earlier</li>
101 <li>Verifies that HASH(g<sup>x</sup>) matches the value sent earlier</li>
102 <li>Verifies that Bob's g<sup>x</sup> is a legal value (2 &lt;=
103 g<sup>x</sup> &lt;= modulus-2)</li>
104 <li>Computes s = (g<sup>x</sup>)<sup>y</sup> (note that this will be the
105 same as the value of s Bob calculated)</li>
106 <li>Computes two AES keys c, c' and four MAC keys m1, m1', m2, m2' by
107 hashing s in various ways (the same as Bob)</li>
108 <li>Uses m2 to verify MAC<sub>m2</sub>(AES<sub>c</sub>(X<sub>B</sub>))</li>
109 <li>Uses c to decrypt AES<sub>c</sub>(X<sub>B</sub>) to obtain
110 X<sub>B</sub> = pub<sub>B</sub>, keyid<sub>B</sub>,
111 sig<sub>B</sub>(M<sub>B</sub>)</li>
112 <li>Computes M<sub>B</sub> = MAC<sub>m1</sub>(g<sup>x</sup>,
113 g<sup>y</sup>, pub<sub>B</sub>, keyid<sub>B</sub>)</li>
114 <li>Uses pub<sub>B</sub> to verify sig<sub>B</sub>(M<sub>B</sub>)</li>
115
116 <li>Picks keyid<sub>A</sub>, a serial number for her D-H key
117 g<sup>y</sup></li>
118 <li>Computes M<sub>A</sub> = MAC<sub>m1'</sub>(g<sup>y</sup>, g<sup>x</sup>,
119 pub<sub>A</sub>, keyid<sub>A</sub>)</li>
120 <li>Computes X<sub>A</sub> = pub<sub>A</sub>, keyid<sub>A</sub>,
121 sig<sub>A</sub>(M<sub>A</sub>)</li>
122 <li>Sends Bob AES<sub>c'</sub>(X<sub>A</sub>),
123 MAC<sub>m2'</sub>(AES<sub>c'</sub>(X<sub>A</sub>))</li>
124 </ol></li>
125 <li>Bob:
126 <ol>
127 <li>Uses m2' to verify MAC<sub>m2'</sub>(AES<sub>c'</sub>(X<sub>A</sub>))</li>
128 <li>Uses c' to decrypt AES<sub>c'</sub>(X<sub>A</sub>) to obtain
129 X<sub>A</sub> = pub<sub>A</sub>, keyid<sub>A</sub>,
130 sig<sub>A</sub>(M<sub>A</sub>)</li>
131 <li>Computes M<sub>A</sub> = MAC<sub>m1'</sub>(g<sup>y</sup>,
132 g<sup>x</sup>, pub<sub>A</sub>, keyid<sub>A</sub>)</li>
133 <li>Uses pub<sub>A</sub> to verify sig<sub>A</sub>(M<sub>A</sub>)</li>
134 </ol></li>
135 <li>If all of the verifications succeeded, Alice and Bob now know each
136 other's Diffie-Hellman public keys, and share the value s. Alice is
137 assured that s is known by someone with access to the private key
138 corresponding to pub<sub>B</sub>, and similarly for Bob.</li>
139 </ul>
140 <h3>Exchanging data</h3>
141 <p>This section outlines the method used to protect data being exchanged
142 between Alice and Bob. As above, all exponentiations are done modulo
143 a particular 1536-bit prime, and g is a generator of
144 that group, as indicated in the detailed description below.</p>
145 <p>Suppose Alice has a message (msg) to send to Bob.</p>
146 <ul>
147 <li>Alice:
148 <ol>
149 <li>Picks the most recent of her own D-H encryption keys that Bob has
150 acknowledged receiving (by using it in a Data Message, or failing that,
151 in the AKE). Let key<sub>A</sub> be that key, and let keyid<sub>A</sub>
152 be its serial number.</li>
153 <li>If the above key is Alice's most recent key, she generates a new D-H key
154 (next_dh), to get the serial number keyid<sub>A</sub>+1.</li>
155 <li>Picks the most recent of Bob's D-H encryption keys that she has
156 received from him (either in a Data Message or in the AKE). Let
157 key<sub>B</sub> by that key, and let keyid<sub>B</sub> be its serial
158 number.</li>
159 <li>Uses Diffie-Hellman to compute a shared secret from the two keys
160 key<sub>A</sub> and key<sub>B</sub>, and generates the
161 sending AES key, ek, and the sending MAC key, mk, as detailed
162 below.</li>
163 <li>Collects any old MAC keys that were used in previous messages, but
164 will never again be used (because their associated D-H keys are no
165 longer the most recent ones) into a list, oldmackeys.</li>
166 <li>Picks a value of the counter, ctr, so that the triple
167 (key<sub>A</sub>, key<sub>B</sub>, ctr) is never the same for more
168 than one Data Message Alice sends to Bob.</li>
169 <li>Computes T<sub>A</sub> = (keyid<sub>A</sub>, keyid<sub>B</sub>, next_dh,
170 ctr, AES-CTR<sub>ek,ctr</sub>(msg))</li>
171 <li>Sends Bob T<sub>A</sub>, MAC<sub>mk</sub>(T<sub>A</sub>),
172 oldmackeys</li>
173 </ol></li>
174 <li>Bob:
175 <ol>
176 <li>Uses Diffie-Hellman to compute a shared secret from the two keys
177 labelled by keyid<sub>A</sub> and keyid<sub>B</sub>, and generates the
178 receiving AES key, ek, and the receiving MAC key, mk, as detailed
179 below. (These will be the same as the keys Alice generated, above.)</li>
180 <li>Uses mk to verify MAC<sub>mk</sub>(T<sub>A</sub>).</li>
181 <li>Uses ek and ctr to decrypt
182 AES-CTR<sub>ek,ctr</sub>(msg).</li>
183 </ol>
184 </li>
185 </ul>
186 <h3>Socialist Millionaires' Protocol (SMP)</h3>
187 <p>While data messages are being exchanged, either Alice or Bob may
188 run SMP to detect impersonation or man-in-the-middle attacks.
189 As above, all exponentiations are done modulo a particular 1536-bit
190 prime, and g<sub>1</sub> is a generator of that group. All sent values
191 include zero-knowledge proofs that they were generated according to
192 this protocol, as indicated in the detailed description below.</p>
193 <p>Suppose Alice and Bob have secret information x and y respectively,
194 and they wish to know whether x = y. The Socialist Millionaires' Protocol
195 allows them to compare x and y without revealing any other information
196 than the value of (x == y). For OTR, the secrets contain
197 information about both parties' long-term authentication public keys,
198 as well as information entered by the users themselves. If x = y,
199 this means that Alice and Bob entered the same secret information, and
200 so must be the same entities who established that secret to begin with.</p>
201 <p>Assuming that Alice begins the exchange:</p>
202 <ul>
203 <li>Alice:
204 <ol>
205 <li>Picks random exponents a<sub>2</sub> and a<sub>3</sub></li>
206 <li>Sends Bob g<sub>2a</sub> = g<sub>1</sub><sup>a<sub>2</sub></sup> and
207 g<sub>3a</sub> = g<sub>1</sub><sup>a<sub>3</sub></sup></li>
208 </ol></li>
209 <li>Bob:
210 <ol>
211 <li>Picks random exponents b<sub>2</sub> and b<sub>3</sub></li>
212 <li>Computes g<sub>2b</sub> = g<sub>1</sub><sup>b<sub>2</sub></sup> and
213 g<sub>3b</sub> = g<sub>1</sub><sup>b<sub>3</sub></sup></li>
214 <li>Computes g<sub>2</sub> = g<sub>2a</sub><sup>b<sub>2</sub></sup> and
215 g<sub>3</sub> = g<sub>3a</sub><sup>b<sub>3</sub></sup></li>
216 <li>Picks random exponent r</li>
217 <li>Computes P<sub>b</sub> = g<sub>3</sub><sup>r</sup> and
218 Q<sub>b</sub> = g<sub>1</sub><sup>r</sup> g<sub>2</sub><sup>y</sup></li>
219 <li>Sends Alice g<sub>2b</sub>, g<sub>3b</sub>, P<sub>b</sub> and
220 Q<sub>b</sub></li>
221 </ol></li>
222 <li>Alice:
223 <ol>
224 <li>Computes g<sub>2</sub> = g<sub>2b</sub><sup>a<sub>2</sub></sup> and
225 g<sub>3</sub> = g<sub>3b</sub><sup>a<sub>3</sub></sup></li>
226 <li>Picks random exponent s</li>
227 <li>Computes P<sub>a</sub> = g<sub>3</sub><sup>s</sup> and
228 Q<sub>a</sub> = g<sub>1</sub><sup>s</sup> g<sub>2</sub><sup>x</sup></li>
229 <li>Computes R<sub>a</sub> = (Q<sub>a</sub> / Q<sub>b</sub>)
230 <sup>a<sub>3</sub></sup></li>
231 <li>Sends Bob P<sub>a</sub>, Q<sub>a</sub> and R<sub>a</sub></li>
232 </ol></li>
233 <li>Bob:
234 <ol>
235 <li>Computes R<sub>b</sub> = (Q<sub>a</sub> / Q<sub>b</sub>)
236 <sup>b<sub>3</sub></sup></li>
237 <li>Computes R<sub>ab</sub> = R<sub>a</sub><sup>b<sub>3</sub></sup></li>
238 <li>Checks whether R<sub>ab</sub> == (P<sub>a</sub> / P<sub>b</sub>)</li>
239 <li>Sends Alice R<sub>b</sub></li>
240 </ol></li>
241 <li>Alice:
242 <ol>
243 <li>Computes R<sub>ab</sub> = R<sub>b</sub><sup>a<sub>3</sub></sup></li>
244 <li>Checks whether R<sub>ab</sub> == (P<sub>a</sub> / P<sub>b</sub>)</li>
245 </ol></li>
246 <li>If everything is done correctly, then R<sub>ab</sub> should hold the
247 value of (P<sub>a</sub> / P<sub>b</sub>) times
248 (g<sub>2</sub><sup>a<sub>3</sub>b<sub>3</sub></sup>)<sup>(x - y)</sup>, which means that the test at the end of
249 the protocol will only succeed if x == y. Further, since
250 g<sub>2</sub><sup>a<sub>3</sub>b<sub>3</sub></sup> is a random number
251 not known to any party, if x is not equal to y, no other information is
252 revealed.</li>
253 </ul>
254 <h2>Details of the protocol</h2>
255 <h3>Unencoded messages</h3>
256 <p>This section describes the messages in the OTR protocol that are not
257 base-64 encoded binary.</p>
258 <h4>OTR Query Messages</h4>
259 <p>If Alice wishes to communicate to Bob that she would like to use OTR,
260 she sends a message containing the string "?OTR" followed by an
261 indication of what versions of OTR she is willing to use with Bob. The
262 version string is constructed as follows:</p>
263 <ul>
264 <li>If she is willing to use OTR version 1, the version string must
265 start with "?".</li>
266 <li>If she is willing to use OTR versions other than 1, a "v" followed
267 by the byte identifiers for the versions in question, followed by "?".
268 The byte identifier for OTR version 2 is "2", and similarly for 3. The
269 order of the identifiers between the "v" and the "?" does not matter,
270 but none should be listed more than once.</li>
271 </ul>
272 <p>For example:</p>
273 <dl>
274 <dt>"?OTR?"</dt>
275 <dd>Version 1 only</dd>
276 <dt>"?OTRv2?"</dt>
277 <dd>Version 2 only</dd>
278 <dt>"?OTRv23?"</dt>
279 <dd>Versions 2 and 3</dd>
280 <dt>"?OTR?v2?"</dt>
281 <dd>Versions 1 and 2</dd>
282 <dt>"?OTRv24x?"</dt>
283 <dd>Version 2, and hypothetical future versions identified by "4" and
284 "x"</dd>
285 <dt>"?OTR?v24x?"</dt>
286 <dd>Versions 1, 2, and hypothetical future versions identified by "4" and
287 "x"</dd>
288 <dt>"?OTR?v?"</dt>
289 <dd>Also version 1 only</dd>
290 <dt>"?OTRv?"</dt>
291 <dd>A bizarre claim that Alice would like to start an OTR conversation,
292 but is unwilling to speak any version of the protocol</dd>
293 </dl>
294 <p>These strings may be hidden from the user (for example, in
295 an attribute of an HTML tag), and/or may be accompanied by an
296 explanitory message ("Alice has requested an Off-the-Record private
297 conversation."). If Bob is willing to use OTR with Alice (with a
298 protocol version that Alice has offered), he should start the AKE.</p>
299 <h4>Tagged plaintext messages</h4>
300 <p>If Alice wishes to communicate to Bob that she is willing to use OTR,
301 she can attach a special whitespace tag to any plaintext message she
302 sends him. This tag may occur anywhere in the message, and may be
303 hidden from the user (as in the Query Messages, above).</p>
304 <p>The tag consists of the following 16 bytes, followed by one or more
305 sets of 8 bytes indicating the version of OTR Alice is willing to
306 use:</p>
307 <ul>
308 <li>Always send "\x20\x09\x20\x20\x09\x09\x09\x09"
309 "\x20\x09\x20\x09\x20\x09\x20\x20", followed by one or more of:</li>
310 <li>"\x20\x09\x20\x09\x20\x20\x09\x20" to indicate a willingness to use
311 OTR version 1 with Bob (note: this string must come before all other
312 whitespace version tags, if it is present, for backwards
313 compatibility)</li>
314 <li>"\x20\x20\x09\x09\x20\x20\x09\x20" to indicate a willingness to use
315 OTR version 2 with Bob</li>
316 <li>"\x20\x20\x09\x09\x20\x20\x09\x09" to indicate a willingness to use
317 OTR version 3 with Bob</li>
318 </ul>
319 <p>If Bob is willing to use OTR with Alice (with a protocol version that
320 Alice has offered), he should start the AKE. On the other hand, if
321 Alice receives a plaintext message from Bob (rather than an initiation
322 of the AKE), she should stop sending him the whitespace tag.</p>
323 <h4>OTR Error Messages</h4>
324 <p>Any message containing the string "?OTR Error:" is an OTR Error
325 Message. The following part of the message should contain
326 human-readable details of the error.</p>
327 <h3>Encoded messages</h3>
328 <p>This section describes the byte-level format of the base-64 encoded
329 binary OTR messages. The binary form of each of the messages is
330 described below. To transmit one of these messages, construct the ASCII
331 string consisting of the five bytes "?OTR:", followed by the base-64
332 encoding of the binary form of the message, followed by the byte
333 ".".</p>
334 <p>For the Diffie-Hellman group computations, the group is the one
335 defined in RFC 3526 with 1536-bit modulus (hex, big-endian):</p>
336 <blockquote><pre>
337 FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
338 29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
339 EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
340 E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
341 EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
342 C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
343 83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
344 670C354E 4ABC9804 F1746C08 CA237327 FFFFFFFF FFFFFFFF
345 </pre></blockquote>
346 <p>and a generator (g) of 2. Note that this means that whenever you see a
347 Diffie-Hellman exponentiation in this document, it always means that the
348 exponentiation is done modulo the above 1536-bit number.</p>
349 <h4>Data types</h4>
350 <dl>
351 <dt>Bytes (BYTE):</dt>
352 <dd> 1 byte unsigned value</dd>
353 <dt>Shorts (SHORT):</dt>
354 <dd> 2 byte unsigned value, big-endian</dd>
355 <dt>Ints (INT):</dt>
356 <dd> 4 byte unsigned value, big-endian</dd>
357 <dt>Multi-precision integers (MPI):</dt>
358 <dd> 4 byte unsigned len, big-endian
359 <br /> len byte unsigned value, big-endian
360 <br /> (MPIs must use the minimum-length encoding; i.e. no leading 0x00
361 bytes. This is important when calculating public key
362 fingerprints.)</dd>
363 <dt>Opaque variable-length data (DATA):</dt>
364 <dd> 4 byte unsigned len, big-endian
365 <br /> len byte data</dd>
366 <dt>Initial CTR-mode counter value (CTR):</dt>
367 <dd> 8 bytes data</dd>
368 <dt>Message Authentication Code (MAC):</dt>
369 <dd> 20 bytes MAC data</dd>
370 </dl>
371 <h4>Public keys, signatures, and fingerprints</h4>
372 <p>OTR users have long-lived public keys that they use for
373 authentication (but <em>not</em> encryption). The current version of
374 the OTR protocol only supports DSA public keys, but there is a key type
375 marker for future extensibility.</p>
376 <dl>
377 <dt>OTR public authentication DSA key (PUBKEY):</dt>
378 <dd>Pubkey type (SHORT)
379 <ul class="note"><li>DSA public keys have type 0x0000</li></ul>
380 p (MPI)
381 <br />q (MPI)
382 <br />g (MPI)
383 <br />y (MPI)
384 <ul class="note"><li>(p,q,g,y) are the DSA public key parameters</li></ul>
385 </dd>
386 </dl>
387 <p>OTR public keys are used to generate <b>signatures</b>; different
388 types of keys produce signatures in different formats. The format for a
389 signature made by a DSA public key is as follows:</p>
390 <dl>
391 <dt>DSA signature (SIG):</dt>
392 <dd> (len is the length of the DSA public parameter q, which in
393 current implementations must be 20 bytes, or 160 bits)
394 <br /> len byte unsigned r, big-endian
395 <br /> len byte unsigned s, big-endian</dd>
396 </dl>
397 <p>OTR public keys have <b>fingerprints</b>, which are hex strings that
398 serve as identifiers for the public key. The fingerprint is calculated
399 by taking the SHA-1 hash of the byte-level representation of the public
400 key. However, there is an exception for backwards compatibility: if the
401 pubkey type is 0x0000, those two leading 0x00 bytes are omitted from the
402 data to be hashed. The encoding assures that, assuming the hash
403 function itself has no useful collisions, and DSA keys have length less
404 than 524281 bits (500 times larger than most DSA keys), no two public
405 keys will have the same fingerprint.</p>
406 <h4>Instance Tags</h4>
407 <p>Clients include instance tags in all OTR version 3 messages. Instance
408 tags are 32-bit values that are intended to be persistent. If the same
409 client is logged into the same account from multiple locations, the
410 intention is that the client will have different instance tags at each
411 location. As shown below, OTR version 3 messages (fragmented and
412 unfragmented) include the source and destination instance tags. If a client
413 receives a message that lists a destination instance tag different from its
414 own, the client should discard the message.</p>
415 <p>The smallest valid instance tag is 0x00000100. It is appropriate to set the
416 destination instance tag to '0' when an actual destination instance tag is
417 not known at the time the message is prepared. If a client receives a
418 message with the sender instance tag set to less than 0x00000100, it should
419 discard the message. Similarly, if a client receives a message with the
420 recipient instance tag set to greater than 0 but less than 0x00000100, it
421 should discard the message.
422 </p>
423
424 <p>This avoids an issue on IM networks that always relay all messages to
425 all sessions of a client who is logged in multiple times. In this
426 situation, OTR clients can attempt to establish an OTR session indefinitely
427 if there are interleaving messages from each of the sessions.</p>
428 <h4>D-H Commit Message</h4>
429 <p>This is the first message of the AKE. Bob sends it to Alice to
430 commit to a choice of D-H encryption key (but the key itself is not yet
431 revealed). This allows the secure session id to be much shorter than in
432 OTR version 1, while still preventing a man-in-the-middle attack on
433 it.</p>
434 <dl>
435 <dt>Protocol version (SHORT)</dt>
436 <dd>The version number of this protocol is 0x0003.</dd>
437 <dt>Message type (BYTE)</dt>
438 <dd>The D-H Commit Message has type 0x02.</dd>
439 <dt>Sender Instance tag (INT)</dt>
440 <dd>The instance tag of the person sending this message.</dd>
441 <dt>Receiver Instance tag (INT)</dt>
442 <dd>The instance tag of the intended recipient.
443 For a commit message this will often be 0, since the other party
444 may not have identified their instance tag yet.</dd>
445 <dt>Encrypted g<sup>x</sup> (DATA)</dt>
446 <dd>Produce this field as follows:
447 <ul>
448 <li>Choose a random value r (128 bits)</li>
449 <li>Choose a random value x (at least 320 bits)</li>
450 <li>Serialize g<sup>x</sup> as an MPI, gxmpi. [gxmpi will probably be
451 196 bytes long, starting with "\x00\x00\x00\xc0".]</li>
452 <li>Encrypt gxmpi using AES128-CTR, with key r and initial counter value
453 0. The result will be the same length as gxmpi.</li>
454 <li>Encode this encrypted value as the DATA field.</li>
455 </ul></dd>
456 <dt>Hashed g<sup>x</sup> (DATA)</dt>
457 <dd>This is the SHA256 hash of gxmpi.</dd>
458 </dl>
459 <h4>D-H Key Message</h4>
460 <p>This is the second message of the AKE. Alice sends it to Bob, and it
461 simply consists of Alice's D-H encryption key.</p>
462 <dl>
463 <dt>Protocol version (SHORT)</dt>
464 <dd>The version number of this protocol is 0x0003.</dd>
465 <dt>Message type (BYTE)</dt>
466 <dd>The D-H Key Message has type 0x0a.</dd>
467 <dt>Sender Instance tag (INT)</dt>
468 <dd>The instance tag of the person sending this message.</dd>
469 <dt>Receiver Instance tag (INT)</dt>
470 <dd>The instance tag of the intended recipient.</dd>
471 <dt>g<sup>y</sup> (MPI)</dt>
472 <dd>Choose a random value y (at least 320 bits), and calculate
473 g<sup>y</sup>.</dd>
474 </dl>
475 <h4>Reveal Signature Message</h4>
476 <p>This is the third message of the AKE. Bob sends it to Alice,
477 revealing his D-H encryption key (and thus opening an encrypted
478 channel), and also authenticating himself (and the parameters of the
479 channel, preventing a man-in-the-middle attack on the channel itself) to
480 Alice.</p>
481 <dl>
482 <dt>Protocol version (SHORT)</dt>
483 <dd>The version number of this protocol is 0x0003.</dd>
484 <dt>Message type (BYTE)</dt>
485 <dd>The Reveal Signature Message has type 0x11.</dd>
486 <dt>Sender Instance tag (INT)</dt>
487 <dd>The instance tag of the person sending this message.</dd>
488 <dt>Receiver Instance tag (INT)</dt>
489 <dd>The instance tag of the intended recipient.</dd>
490 <dt>Revealed key (DATA)</dt>
491 <dd>This is the value r picked earlier.</dd>
492 <dt>Encrypted signature (DATA)</dt>
493 <dd>This field is calculated as follows:
494 <ul>
495 <li>Compute the Diffie-Hellman shared secret s.</li>
496 <li>Use s to compute an AES key c and two MAC keys m1 and m2, as specified below.</li>
497 <li>Select keyid<sub>B</sub>, a serial number for the D-H key computed
498 earlier. It is an INT, and must be greater than 0.</li>
499 <li>Compute the 32-byte value M<sub>B</sub> to be the SHA256-HMAC of the
500 following data, using the key m1:<dl>
501 <dt>g<sup>x</sup> (MPI)</dt>
502 <dt>g<sup>y</sup> (MPI)</dt>
503 <dt>pub<sub>B</sub> (PUBKEY)</dt>
504 <dt>keyid<sub>B</sub> (INT)</dt>
505 </dl></li>
506 <li>Let X<sub>B</sub> be the following structure:<dl>
507 <dt>pub<sub>B</sub> (PUBKEY)</dt>
508 <dt>keyid<sub>B</sub> (INT)</dt>
509 <dt>sig<sub>B</sub>(M<sub>B</sub>) (SIG)</dt>
510 <dd>This is the signature, using the private part of the key
511 pub<sub>B</sub>, of the 32-byte M<sub>B</sub> (taken modulo q instead of
512 being truncated (as described in FIPS-186), and not hashed again).</dd>
513 </dl></li>
514 <li>Encrypt X<sub>B</sub> using AES128-CTR with key c and initial
515 counter value 0.</li>
516 <li>Encode this encrypted value as the DATA field.</li>
517 </ul></dd>
518 <dt>MAC'd signature (MAC)</dt>
519 <dd>This is the SHA256-HMAC-160 (that is, the first 160 bits of the
520 SHA256-HMAC) of the encrypted signature field (including the four-byte
521 length), using the key m2.</dd>
522 </dl>
523 <h4>Signature Message</h4>
524 <p>This is the final message of the AKE. Alice sends it to Bob,
525 authenticating herself and the channel parameters to him.</p>
526 <dl>
527 <dt>Protocol version (SHORT)</dt>
528 <dd>The version number of this protocol is 0x0003.</dd>
529 <dt>Message type (BYTE)</dt>
530 <dd>The Signature Message has type 0x12.</dd>
531 <dt>Sender Instance tag (INT)</dt>
532 <dd>The instance tag of the person sending this message.</dd>
533 <dt>Receiver Instance tag (INT)</dt>
534 <dd>The instance tag of the intended recipient.</dd>
535 <dt>Encrypted signature (DATA)</dt>
536 <dd>This field is calculated as follows:
537 <ul>
538 <li>Compute the Diffie-Hellman shared secret s.</li>
539 <li>Use s to compute an AES key c' and two MAC keys m1' and m2', as specified below.</li>
540 <li>Select keyid<sub>A</sub>, a serial number for the D-H key computed
541 earlier. It is an INT, and must be greater than 0.</li>
542 <li>Compute the 32-byte value M<sub>A</sub> to be the SHA256-HMAC of the
543 following data, using the key m1':<dl>
544 <dt>g<sup>y</sup> (MPI)</dt>
545 <dt>g<sup>x</sup> (MPI)</dt>
546 <dt>pub<sub>A</sub> (PUBKEY)</dt>
547 <dt>keyid<sub>A</sub> (INT)</dt>
548 </dl></li>
549 <li>Let X<sub>A</sub> be the following structure:<dl>
550 <dt>pub<sub>A</sub> (PUBKEY)</dt>
551 <dt>keyid<sub>A</sub> (INT)</dt>
552 <dt>sig<sub>A</sub>(M<sub>A</sub>) (SIG)</dt>
553 <dd>This is the signature, using the private part of the key
554 pub<sub>A</sub>, of the 32-byte M<sub>A</sub> (which does not need to be
555 hashed again to produce the signature).</dd>
556 </dl></li>
557 <li>Encrypt X<sub>A</sub> using AES128-CTR with key c' and initial
558 counter value 0.</li>
559 <li>Encode this encrypted value as the DATA field.</li>
560 </ul></dd>
561 <dt>MAC'd signature (MAC)</dt>
562 <dd>This is the SHA256-HMAC-160 (that is, the first 160 bits of the
563 SHA256-HMAC) of the encrypted signature field (including the four-byte
564 length), using the key m2'.</dd>
565 </dl>
566 <h4>Data Message</h4>
567 <p>This message is used to transmit a private message to the
568 correspondent. It is also used to reveal old MAC keys.</p>
569 <p>The plaintext message (either before encryption, or after decryption)
570 consists of a human-readable message (encoded in UTF-8, optionally with
571 HTML markup), optionally followed by:</p>
572 <ul>
573 <li>a single NUL (a BYTE with value 0x00), <b>and</b></li>
574 <li>zero or more TLV (type/length/value) records (with no padding
575 between them)</li>
576 </ul>
577 <p>Each TLV record is of the form:</p>
578 <dl>
579 <dt>Type (SHORT)</dt>
580 <dd>The type of this record. Records with unrecognized types should be
581 ignored.</dd>
582 <dt>Length (SHORT)</dt>
583 <dd>The length of the following field</dd>
584 <dt>Value (len BYTEs) [where len is the value of the Length field]</dt>
585 <dd>Any pertinent data for the record type.</dd>
586 </dl>
587 <p>Some TLV examples:</p>
588 <dl>
589 <dt>\x00\x01\x00\x00</dt>
590 <dd>A TLV of type 1, containing no data</dd>
591 <dt>\x00\x00\x00\x05\x68\x65\x6c\x6c\x6f</dt>
592 <dd>A TLV of type 0, containing the value "hello"</dd>
593 </dl>
594 <p>The currently defined TLV record types are:</p>
595 <dl>
596 <dt>Type 0: Padding</dt>
597 <dd>The value may be an arbitrary amount of data, which should be
598 ignored. This type can be used to disguise the length of the plaintext
599 message.</dd>
600 <dt>Type 1: Disconnected</dt>
601 <dd>If the user requests to close the private connection, you may send a
602 message (possibly with empty human-readable part) containing a record
603 with this TLV type just before you discard the session keys, and
604 transition to MSGSTATE_PLAINTEXT (see below). If you receive a TLV
605 record of this type, you should transition to MSGSTATE_FINISHED (see
606 below), and inform the user that his correspondent has closed his end of
607 the private connection, and the user should do the same.</dd>
608 <dt>Type 2: SMP Message 1</dt>
609 <dd>The value represents an initiating message of the Socialist
610 Millionaires' Protocol, described below.</dd>
611 <dt>Type 3: SMP Message 2</dt>
612 <dd>The value represents the second message in an instance of SMP.</dd>
613 <dt>Type 4: SMP Message 3</dt>
614 <dd>The value represents the third message in an instance of SMP.</dd>
615 <dt>Type 5: SMP Message 4</dt>
616 <dd>The value represents the final message in an instance of SMP.</dd>
617 <dt>Type 6: SMP Abort Message</dt>
618 <dd>If the user cancels SMP prematurely or encounters an error in the
619 protocol and cannot continue, you may send a message (possibly with empty
620 human-readable part) with this TLV type to instruct the other party's
621 client to abort the protocol. The associated length should be zero and
622 the associated value should be empty. If you receive a TLV of this type,
623 you should change the SMP state to SMP_EXPECT1 (see below).</dd>
624 <dt>Type 7: SMP Message 1Q</dt>
625 <dd>Like a SMP Message 1, but whose value begins with a NUL-terminated
626 user-specified question.</dd>
627 <dt>Type 8: Extra symmetric key</dt>
628 <dd>If you wish to use the extra symmetric key, compute it yourself as
629 outlined in the section "Extra symmetric key", below. Then send this
630 type 8 TLV to your buddy to indicate that you'd like to use the extra
631 symmetric key for something. The value of the TLV begins with a 4-byte
632 indication of what this symmetric key will be used for (file transfer,
633 voice encryption, etc.). After that, the contents are use-specific
634 (which file, etc.). There are no currently defined uses. Note that the
635 value of the key itself is <em>not</em> placed into the TLV; your buddy
636 will compute it on his/her own.
637 </dd>
638 </dl>
639 <p>SMP Message TLVs (types 2-5) all carry data sharing the same general
640 format:</p>
641 <dl>
642 <dt>MPI count (INT)</dt>
643 <dd>The number of MPIs contained in the remainder of the TLV.</dd>
644 <dt>MPI 1 (MPI)</dt>
645 <dd>The first MPI of the TLV, serialized into a byte array.</dd>
646 <dt>MPI 2 (MPI)</dt>
647 <dd>The second MPI of the TLV, serialized into a byte array.</dd>
648 <dt>etc.</dt>
649 </dl>
650 <p>There should be as many MPIs as declared in the MPI count field. For
651 the exact MPIs passed for each SMP TLV, see the SMP state machine
652 below.</p>
653 <p>A message with an empty human-readable part (the plaintext is of zero
654 length, or starts with a NUL) is a "heartbeat" packet, and should not
655 be displayed to the user. (But it's still useful to effect key
656 rotations.)</p>
657 <p>Data Message format:</p>
658 <dl>
659 <dt>Protocol version (SHORT)</dt>
660 <dd>The version number of this protocol is 0x0003.</dd>
661 <dt>Message type (BYTE)</dt>
662 <dd>The Data Message has type 0x03.</dd>
663 <dt>Sender Instance tag (INT)</dt>
664 <dd>The instance tag of the person sending this message.</dd>
665 <dt>Receiver Instance tag (INT)</dt>
666 <dd>The instance tag of the intended recipient.</dd>
667 <dt>Flags (BYTE)</dt>
668 <dd>The bitwise-OR of the flags for this message. Usually you should
669 set this to 0x00. The only currently defined flag is:<dl>
670 <dt>IGNORE_UNREADABLE (0x01)</dt>
671 <dd>If you receive a Data Message with this flag set, and you are unable
672 to decrypt the message or verify the MAC (because, for example, you
673 don't have the right keys), just ignore the message instead of producing
674 some kind of error or notification to the user.</dd>
675 </dl></dd>
676 <dt>Sender keyid (INT)</dt>
677 <dd>Must be strictly greater than 0, and increment by 1 with each key
678 change</dd>
679 <dt>Recipient keyid (INT)</dt>
680 <dd>Must therefore be strictly greater than 0, as the receiver has no
681 key with id 0.
682 <br />The sender and recipient keyids are those used to encrypt and MAC
683 this message.</dd>
684 <dt>DH y (MPI)</dt>
685 <dd>The *next* [i.e. sender_keyid+1] public key for the sender</dd>
686 <dt>Top half of counter init (CTR)</dt>
687 <dd>This should monotonically increase (as a big-endian value) for
688 each message sent with the same (sender keyid, recipient keyid)
689 pair, and must not be all 0x00.</dd>
690 <dt>Encrypted message (DATA)</dt>
691 <dd>Using the appropriate encryption key (see below) derived from the
692 sender's and recipient's DH public keys (with the keyids given in
693 this message), perform AES128 counter-mode (CTR) encryption of the
694 message. The initial counter is a 16-byte value whose first 8
695 bytes are the above "top half of counter init" value, and whose
696 last 8 bytes are all 0x00. Note that counter mode does not change
697 the length of the message, so no message padding needs to be done.
698 If you *want* to do message padding (to disguise the length of
699 your message), use the above TLV of type 0.</dd>
700 <dt>Authenticator (MAC)</dt>
701 <dd>The SHA1-HMAC, using the appropriate MAC key (see below) of everything
702 from the Protocol version to the end of the encrypted message</dd>
703 <dt>Old MAC keys to be revealed (DATA)</dt>
704 <dd>See "Revealing MAC Keys", below.</dd>
705 </dl>
706 <h3>Socialist Millionaires' Protocol (SMP)</h3>
707 <p>The Socialist Millionaires' Protocol allows two parties with secret
708 information x and y respectively to check whether (x==y) without revealing
709 any additional information about the secrets. The protocol used by OTR is
710 based on the work of Boudot, Schoenmakers and Traore (2001). A full
711 justification for its use in OTR is made by Alexander and Goldberg,
712 in a paper published in 2007. The following is a technical account
713 of what is transmitted during the course of the protocol.</p>
714 <h4>Secret information</h4>
715 <p>The secret information x and y compared during this protocol contains
716 not only information entered by the users, but also information unique to
717 the conversation in which SMP takes place. Specifically, the format is:</p>
718 <dl>
719 <dt>Version (BYTE)</dt>
720 <dd>The version of SMP used. The version described here is 1.</dd>
721 <dt>Initiator fingerprint (20 BYTEs)</dt>
722 <dd>The fingerprint that the party initiating SMP is using in
723 the current conversation.</dd>
724 <dt>Responder fingerprint (20 BYTEs)</dt>
725 <dd>The fingerprint that the party that did not initiate SMP is
726 using in the current conversation.</dd>
727 <dt>Secure Session ID</dt>
728 <dd>The ssid described below.</dd>
729 <dt>User-specified secret</dt>
730 <dd>The input string given by the user at runtime.</dd>
731 </dl>
732 <p>Then the SHA256 hash of the above is taken, and the digest becomes the
733 actual secret (x or y) to be used in SMP. The additional fields insure
734 that not only do both parties know the same secret input string, but no
735 man-in-the-middle is capable of reading their communication either.</p>
736 <h3>The SMP state machine</h3>
737 <p>Whenever the OTR message state machine has MSGSTATE_ENCRYPTED set
738 (see below), the SMP state machine may progress. If at any point
739 MSGSTATE_ENCRYPTED becomes unset, SMP must abandon its state and return
740 to its initial setup. The SMP state consists of one main variable, as
741 well as information from the partial computations at each protocol step.</p>
742 <h4>Expected Message</h4>
743 <p>This main state variable for SMP controls what SMP-specific TLVs will
744 be accepted. This variable has no effect on type 0 or type 1 TLVs, which
745 are always allowed. smpstate can take one of four values:</p>
746 <dl>
747 <dt>SMPSTATE_EXPECT1</dt>
748 <dd>This state indicates that only type 2 (SMP message 1) and type 7
749 (SMP message 1Q) TLVs should be accepted. This is the default state when
750 SMP has not yet begun. This state is also reached whenever an error
751 occurs or SMP is aborted, and the protocol must be restarted from the
752 beginning.</dd>
753 <dt>SMPSTATE_EXPECT2</dt>
754 <dd>This state indicates that only type 3 TLVs (SMP message 2) should
755 be accepted.</dd>
756 <dt>SMPSTATE_EXPECT3</dt>
757 <dd>This state indicates that only type 4 TLVs (SMP message 3) should
758 be accepted.</dd>
759 <dt>SMPSTATE_EXPECT4</dt>
760 <dd>This state indicates that only type 5 TLVs (SMP message 4) should
761 be accepted.</dd>
762 </dl>
763 <h4>State Transitions</h4>
764 <p>There are 7 actions that an OTR client must handle:</p>
765 <ul>
766 <li>Received TLVs:
767 <ul>
768 <li>SMP Message 1</li>
769 <li>SMP Message 2</li>
770 <li>SMP Message 3</li>
771 <li>SMP Message 4</li>
772 <li>SMP Abort Message</li>
773 </ul></li>
774 <li>User actions:</li>
775 <ul>
776 <li>User requests to begin SMP</li>
777 <li>User requests to abort SMP</li>
778 </ul></li>
779 </ul>
780 <p>The following sections outline what is to be done in each case. They
781 all assume that MSGSTATE_ENCRYPTED is set. For simplicity, they also
782 assume that Alice has begun SMP, and Bob is responding to her.</p>
783 <h4>SMP Hash function</h4>
784 <p>In the following actions, there are many places where a SHA256 hash of
785 an integer followed by one or two MPIs is taken. The input to this hash
786 function is:</p>
787 <dl>
788 <dt>Version (BYTE)</dt>
789 <dd>This distinguishes calls to the hash function at different points in
790 the protocol, to prevent Alice from replaying Bob's zero knowledge proofs
791 or vice versa.</dd>
792 <dt>First MPI (MPI)</dt>
793 <dd>The first MPI given as input, serialized in the usual way.</dd>
794 <dt>Second MPI (MPI)</dt>
795 <dd>The second MPI given as input, if present, serialized in the usual way.
796 If only one MPI is given as input, this field is simply omitted.</dd>
797 </dl>
798 <h4>Receiving a type 2 TLV (SMP message 1)</h4>
799 <p>SMP message 1 is sent by Alice to begin a DH exchange to determine two
800 new generators, g<sub>2</sub> and g<sub>3</sub>. It contains the
801 following mpi values:</p>
802 <dl>
803 <dt>g<sub>2a</sub></dt>
804 <dd>Alice's half of the DH exchange to determine g<sub>2</sub>.</dd>
805 <dt>c2, D2</dt>
806 <dd>A zero-knowledge proof that Alice knows the exponent associated with
807 her transmitted value g<sub>2a</sub>.</dd>
808 <dt>g<sub>3a</sub></dt>
809 <dd>Alice's half of the DH exchange to determine g<sub>3</sub>.</dd>
810 <dt>c3, D3</dt>
811 <dd>A zero-knowledge proof that Alice knows the exponent associated with
812 her transmitted value g<sub>3a</sub>.</dd>
813 </dl>
814 <p>A type 7 (SMP Message 1Q) TLV is the same as the above, but is
815 preceded by a user-specified question, which is associated with the
816 user-specified portion of the secret.</p>
817 <p>When Bob receives this TLV he should do:</p>
818 <dl>
819 <dt>If smpstate is not SMPSTATE_EXPECT1:</dt>
820 <dd>Set smpstate to SMPSTATE_EXPECT1 and send a type 6 TLV (SMP abort)
821 to Alice.</dd>
822 <dt>If smpstate is SMPSTATE_EXPECT1:</dt>
823 <dd>Verify Alice's zero-knowledge proofs for g<sub>2a</sub> and
824 g<sub>3a</sub>:
825 <ol>
826 <li>Check that both g<sub>2a</sub> and g<sub>3a</sub> are &gt;= 2 and
827 &lt;= modulus-2.</li>
828 <li>Check that c2 = SHA256(1, g<sub>1</sub><sup>D2</sup>
829 g<sub>2a</sub><sup>c2</sup>).</li>
830 <li>Check that c3 = SHA256(2, g<sub>1</sub><sup>D3</sup>
831 g<sub>3a</sub><sup>c3</sup>).</li>
832 </ol>
833 Create a type 3 TLV (SMP message 2) and send it to Alice:
834 <ol>
835 <li>Determine Bob's secret input y, which is to be compared to Alice's
836 secret x.</li>
837 <li>Pick random exponents b<sub>2</sub> and b<sub>3</sub>.
838 These will used during the DH exchange to pick generators.</li>
839 <li>Pick random exponents r2, r3, r4, r5 and r6.
840 These will be used to add a blinding factor to the final results, and
841 to generate zero-knowledge proofs that this message was created honestly.</li>
842 <li>Compute g<sub>2b</sub> = g<sub>1</sub><sup>b<sub>2</sub></sup> and
843 g<sub>3b</sub> = g<sub>1</sub><sup>b<sub>3</sub></sup></li>
844 <li>Generate a zero-knowledge proof that the exponent b<sub>2</sub> is
845 known by setting c2 = SHA256(3, g<sub>1</sub><sup>r2</sup>) and
846 D2 = r2 - b<sub>2</sub> c2 mod q. In the zero-knowledge proofs the D values
847 are calculated modulo q = (p - 1) / 2, where p is the same 1536-bit prime
848 as elsewhere. The random exponents are 1536-bit numbers.</li>
849 <li>Generate a zero-knowledge proof that the exponent b<sub>3</sub> is
850 known by setting c3 = SHA256(4, g<sub>1</sub><sup>r3</sup>) and
851 D3 = r3 - b<sub>3</sub> c3 mod q.</li>
852 <li>Compute g<sub>2</sub> = g<sub>2a</sub><sup>b<sub>2</sub></sup> and
853 g<sub>3</sub> = g<sub>3a</sub><sup>b<sub>3</sub></sup></li>
854 <li>Compute P<sub>b</sub> = g<sub>3</sub><sup>r4</sup> and
855 Q<sub>b</sub> = g<sub>1</sub><sup>r4</sup> g<sub>2</sub><sup>y</sup></li>
856 <li>Generate a zero-knowledge proof that P<sub>b</sub> and Q<sub>b</sub>
857 were created according to the protocol by setting
858 cP = SHA256(5, g<sub>3</sub><sup>r5</sup>, g<sub>1</sub><sup>r5</sup>
859 g<sub>2</sub><sup>r6</sup>), D5 = r5 - r4 cP mod q and D6 = r6 - y cP mod q.</li>
860 <li>Store the values of g<sub>3a</sub>, g<sub>2</sub>, g<sub>3</sub>,
861 b<sub>3</sub>, P<sub>b</sub> and Q<sub>b</sub> for use later in the
862 protocol.</li>
863 <li>Send Alice a type 3 TLV (SMP message 2) containing g<sub>2b</sub>,
864 c2, D2, g<sub>3b</sub>, c3, D3, P<sub>b</sub>, Q<sub>b</sub>, cP, D5
865 and D6, in that order.</li>
866 </ol>
867 Set smpstate to SMPSTATE_EXPECT3.</dd>
868 </dl>
869 <h4>Receiving a type 3 TLV (SMP message 2)</h4>
870 <p>SMP message 2 is sent by Bob to complete the DH exchange to
871 determine the new generators, g<sub>2</sub> and g<sub>3</sub>.
872 It also begins the construction of the values used in the final
873 comparison of the protocol. It contains the following mpi values:</p>
874 <dl>
875 <dt>g<sub>2b</sub></dt>
876 <dd>Bob's half of the DH exchange to determine g<sub>2</sub>.</dd>
877 <dt>c2, D2</dt>
878 <dd>A zero-knowledge proof that Bob knows the exponent associated with
879 his transmitted value g<sub>2b</sub>.</dd>
880 <dt>g<sub>3b</sub></dt>
881 <dd>Bob's half of the DH exchange to determine g<sub>3</sub>.</dd>
882 <dt>c3, D3</dt>
883 <dd>A zero-knowledge proof that Bob knows the exponent associated with
884 his transmitted value g<sub>3b</sub>.</dd>
885 <dt>P<sub>b</sub>, Q<sub>b</sub></dt>
886 <dd>These values are used in the final comparison to determine if Alice
887 and Bob share the same secret.</dd>
888 <dt>cP, D5, D6</dt>
889 <dd>A zero-knowledge proof that P<sub>b</sub> and Q<sub>b</sub> were
890 created according to the protcol given above.</dd>
891 </dl>
892 <p>When Alice receives this TLV she should do:</p>
893 <dl>
894 <dt>If smpstate is not SMPSTATE_EXPECT2:</dt>
895 <dd>Set smpstate to SMPSTATE_EXPECT1 and send a type 6 TLV (SMP abort)
896 to Bob.</dd>
897 <dt>If smpstate is SMPSTATE_EXPECT2:</dt>
898 <dd>Verify Bob's zero-knowledge proofs for g<sub>2b</sub>,
899 g<sub>3b</sub>, P<sub>b</sub> and Q<sub>b</sub>:
900 <ol>
901 <li>Check that g<sub>2b</sub>,
902 g<sub>3b</sub>, P<sub>b</sub> and Q<sub>b</sub> are &gt;= 2 and
903 &lt;= modulus-2.</li>
904 <li>Check that c2 = SHA256(3, g<sub>1</sub><sup>D2</sup>
905 g<sub>2b</sub><sup>c2</sup>).</li>
906 <li>Check that c3 = SHA256(4, g<sub>1</sub><sup>D3</sup>
907 g<sub>3b</sub><sup>c3</sup>).</li>
908 <li>Check that cP = SHA256(5, g<sub>3</sub><sup>D5</sup>
909 P<sub>b</sub><sup>cP</sup>, g<sub>1</sub><sup>D5</sup>
910 g<sub>2</sub><sup>D6</sup> Q<sub>b</sub><sup>cP</sup>).</li>
911 </ol>
912 Create a type 4 TLV (SMP message 3) and send it to Bob:
913 <ol>
914 <li>Pick random exponents r4, r5, r6 and r7.
915 These will be used to add a blinding factor to the final results, and
916 to generate zero-knowledge proofs that this message was created honestly.</li>
917 <li>Compute g<sub>2</sub> = g<sub>2b</sub><sup>a<sub>2</sub></sup> and
918 g<sub>3</sub> = g<sub>3b</sub><sup>a<sub>3</sub></sup></li>
919 <li>Compute P<sub>a</sub> = g<sub>3</sub><sup>r4</sup> and
920 Q<sub>a</sub> = g<sub>1</sub><sup>r4</sup> g<sub>2</sub><sup>x</sup></li>
921 <li>Generate a zero-knowledge proof that P<sub>a</sub> and Q<sub>a</sub>
922 were created according to the protocol by setting
923 cP = SHA256(6, g<sub>3</sub><sup>r5</sup>, g<sub>1</sub><sup>r5</sup>
924 g<sub>2</sub><sup>r6</sup>), D5 = r5 - r4 cP mod q and D6 = r6 - x cP mod q.</li>
925 <li>Compute R<sub>a</sub> = (Q<sub>a</sub> / Q<sub>b</sub>)
926 <sup>a<sub>3</sub></sup></li>
927 <li>Generate a zero-knowledge proof that R<sub>a</sub> was created
928 according to the protocol by setting cR = SHA256(7, g<sub>1</sub><sup>r7</sup>,
929 (Q<sub>a</sub> / Q<sub>b</sub>)<sup>r7</sup>) and
930 D7 = r7 - a<sub>3</sub> cR mod q.</li>
931 <li>Store the values of g<sub>3b</sub>, (P<sub>a</sub> / P<sub>b</sub>),
932 (Q<sub>a</sub> / Q<sub>b</sub>) and a<sub>3</sub> for use later in the
933 protocol.</li>
934 <li>Send Bob a type 4 TLV (SMP message 3) containing P<sub>a</sub>,
935 Q<sub>a</sub>, cP, D5, D6, R<sub>a</sub>, cR and D7 in that order.</li>
936 </ol>
937 Set smpstate to SMPSTATE_EXPECT4.</dd>
938 </dl>
939 <h4>Receiving a type 4 TLV (SMP message 3)</h4>
940 <p>SMP message 3 is Alice's final message in the SMP exchange. It
941 has the last of the information required by Bob to determine if x = y.
942 It contains the following mpi values:</p>
943 <dl>
944 <dt>P<sub>a</sub>, Q<sub>a</sub></dt>
945 <dd>These values are used in the final comparison to determine if Alice
946 and Bob share the same secret.</dd>
947 <dt>cP, D5, D6</dt>
948 <dd>A zero-knowledge proof that P<sub>a</sub> and Q<sub>a</sub> were
949 created according to the protcol given above.</dd>
950 <dt>R<sub>a</sub></dt>
951 <dd>This value is used in the final comparison to determine if Alice
952 and Bob share the same secret.</dd>
953 <dt>cR, D7</dt>
954 <dd>A zero-knowledge proof that R<sub>a</sub> was
955 created according to the protcol given above.</dd>
956 <dt>
957 </dl>
958 <p>When Bob receives this TLV he should do:</p>
959 <dl>
960 <dt>If smpstate is not SMPSTATE_EXPECT3:</dt>
961 <dd>Set smpstate to SMPSTATE_EXPECT1 and send a type 6 TLV (SMP abort)
962 to Bob.</dd>
963 <dt>If smpstate is SMPSTATE_EXPECT3:</dt>
964 <dd>Verify Alice's zero-knowledge proofs for P<sub>a</sub>, Q<sub>a</sub>
965 and R<sub>a</sub>:
966 <ol>
967 <li>Check that P<sub>a</sub>, Q<sub>a</sub> and R<sub>a</sub> are &gt;= 2 and
968 &lt;= modulus-2.</li>
969 <li>Check that cP = SHA256(6, g<sub>3</sub><sup>D5</sup>
970 P<sub>a</sub><sup>cP</sup>, g<sub>1</sub><sup>D5</sup> g<sub>2</sub><sup>D6</sup>
971 Q<sub>a</sub><sup>cP</sup>).</li>
972 <li>Check that cR = SHA256(7, g<sub>1</sub><sup>D7</sup>
973 g<sub>3a</sub><sup>cR</sup>, (Q<sub>a</sub> / Q<sub>b</sub>)<sup>D7</sup>
974 R<sub>a</sub><sup>cR</sup>).</li>
975 </ol>
976 Create a type 5 TLV (SMP message 4) and send it to Alice:
977 <ol>
978 <li>Pick a random exponent r7.
979 This will be used to generate Bob's final zero-knowledge proof that
980 this message was created honestly.</li>
981 <li>Compute R<sub>b</sub> = (Q<sub>a</sub> / Q<sub>b</sub>)
982 <sup>b<sub>3</sub></sup></li>
983 <li>Generate a zero-knowledge proof that R<sub>b</sub> was created
984 according to the protocol by setting cR = SHA256(8, g<sub>1</sub><sup>r7</sup>,
985 (Q<sub>a</sub> / Q<sub>b</sub>)<sup>r7</sup>) and
986 D7 = r7 - b<sub>3</sub> cR mod q.</li>
987 <li>Send Alice a type 5 TLV (SMP message 4) containing R<sub>b</sub>,
988 cR and D7 in that order.</li>
989 </ol>
990 Check whether the protocol was successful:
991 <ol>
992 <li>Compute R<sub>ab</sub> = R<sub>a</sub><sup>b<sub>3</sub></sup>.</li>
993 <li>Determine if x = y by checking the equivalent condition that
994 (P<sub>a</sub> / P<sub>b</sub>) = R<sub>ab</sub>.</li>
995 </ol>
996 Set smpstate to SMPSTATE_EXPECT1, as no more messages are expected from
997 Alice.</dd>
998 </dl>
999 <h4>Receiving a type 5 TLV (SMP message 4)</h4>
1000 <p>SMP message 4 is Bob's final message in the SMP exchange. It
1001 has the last of the information required by Alice to determine if x = y.
1002 It contains the following mpi values:</p>
1003 <dl>
1004 <dt>R<sub>b</sub></dt>
1005 <dd>This value is used in the final comparison to determine if Alice
1006 and Bob share the same secret.</dd>
1007 <dt>cR, D7</dt>
1008 <dd>A zero-knowledge proof that R<sub>b</sub> was
1009 created according to the protcol given above.</dd>
1010 <dt>
1011 </dl>
1012 <p>When Alice receives this TLV she should do:</p>
1013 <dl>
1014 <dt>If smpstate is not SMPSTATE_EXPECT4:</dt>
1015 <dd>Set smpstate to SMPSTATE_EXPECT1 and send a type 6 TLV (SMP abort)
1016 to Bob.</dd>
1017 <dt>If smpstate is SMPSTATE_EXPECT4:</dt>
1018 <dd>Verify Bob's zero-knowledge proof for R<sub>b</sub>:
1019 <ol>
1020 <li>Check that R<sub>b</sub> is &gt;= 2 and
1021 &lt;= modulus-2.</li>
1022 <li>Check that cR = SHA256(8, g<sub>1</sub><sup>D7</sup>
1023 g<sub>3b</sub><sup>cR</sup>, (Q<sub>a</sub> / Q<sub>b</sub>)<sup>D7</sup>
1024 R<sub>b</sub><sup>cR</sup>).</li>
1025 </ol>
1026 Check whether the protocol was successful:
1027 <ol>
1028 <li>Compute R<sub>ab</sub> = R<sub>b</sub><sup>a<sub>3</sub></sup>.</li>
1029 <li>Determine if x = y by checking the equivalent condition that
1030 (P<sub>a</sub> / P<sub>b</sub>) = R<sub>ab</sub>.</li>
1031 </ol>
1032 Set smpstate to SMPSTATE_EXPECT1, as no more messages are expected from
1033 Bob.</dd>
1034 </dl>
1035 <h4>User requests to begin SMP</h4>
1036 <dl>
1037 <dt>If smpstate is not set to SMPSTATE_EXPECT1:</dt>
1038 <dd>SMP is already underway. If you wish to restart SMP, send a
1039 type 6 TLV (SMP abort) to the other party and then proceed as if
1040 smpstate was SMPSTATE_EXPECT1. Otherwise, you may simply continue the
1041 current SMP instance.</dd>
1042 <dt>If smpstate is set to SMPSTATE_EXPECT1:</dt>
1043 <dd>No current exchange is underway. In this case, Alice should
1044 create a valid type 2 TLV (SMP message 1) as follows:
1045 <ol>
1046 <li>Determine her secret input x, which is to be compared to Bob's
1047 secret y.</li>
1048 <li>Pick random values a<sub>2</sub> and a<sub>3</sub> (1536 bits).
1049 These will be Alice's exponents for the DH exchange to pick generators.</li>
1050 <li>Pick random values r2 and r3 (1536 bits).
1051 These will be used to generate zero-knowledge proofs that this message
1052 was created according to the protocol.</li>
1053 <li>Compute g<sub>2a</sub> = g<sub>1</sub><sup>a<sub>2</sub></sup> and
1054 g<sub>3a</sub> = g<sub>1</sub><sup>a<sub>3</sub></sup></li>
1055 <li>Generate a zero-knowledge proof that the exponent a<sub>2</sub> is
1056 known by setting c2 = SHA256(1, g<sub>1</sub><sup>r2</sup>) and
1057 D2 = r2 - a<sub>2</sub> c2 mod q.</li>
1058 <li>Generate a zero-knowledge proof that the exponent a<sub>3</sub> is
1059 known by setting c3 = SHA256(2, g<sub>1</sub><sup>r3</sup>) and
1060 D3 = r3 - a<sub>3</sub> c3 mod q.</li>
1061 <li>Store the values of x, a<sub>2</sub> and a<sub>3</sub>
1062 for use later in the protocol.</li>
1063 <li>Send Bob a type 2 TLV (SMP message 1) containing g<sub>2a</sub>,
1064 c2, D2, g<sub>3a</sub>, c3 and D3 in that order.</li>
1065 </ol>
1066 Set smpstate to SMPSTATE_EXPECT2.</dd>
1067 </dl>
1068 <h4>User requests to abort SMP</h4>
1069 <p>In all cases, send a type 6 TLV (SMP abort) to the correspondent and
1070 set smpstate to SMPSTATE_EXPECT1.</p>
1071 <h3>Key Management</h3>
1072 <p>For each correspondent, keep track of:</p>
1073 <dl>
1074 <dt>Your two most recent DH public/private key pairs</dt>
1075 <dd>our_dh[our_keyid] (most recent) and our_dh[our_keyid-1] (previous)</dd>
1076 <dt>His two most recent DH public keys</dt>
1077 <dd>their_y[their_keyid] (most recent) and their_y[their_keyid-1]
1078 (previous)</dd>
1079 </dl>
1080
1081 <p>When starting a private conversation with a correspondent, generate
1082 two DH key pairs for yourself, and set our_keyid = 2. Note that all DH
1083 key pairs should have a private part that is at least 320 bits long.</p>
1084
1085 <dl class="doublespace">
1086 <dt>When you send AKE messages:</dt>
1087 <dd>Send the public part of our_dh[our_keyid-1], with the keyid field,
1088 of course, set to (our_keyid-1).</dd>
1089
1090 <dt>Upon completing the AKE:</dt>
1091 <dd>If the specified keyid equals either their_keyid or their_keyid-1,
1092 and the DH pubkey contained in the AKE messages matches the
1093 one you've stored for that keyid, that's great. Otherwise, forget
1094 all values of their_y[], and of their_keyid, and set their_keyid to
1095 the keyid value given in the AKE messages, and
1096 their_y[their_keyid] to the DH pubkey value given in the AKE
1097 messages. their_y[their_keyid-1] should be set to NULL.</dd>
1098
1099 <dt>When you send a Data Message:</dt>
1100 <dd>Set the sender keyid to (our_keyid-1), and the recipient keyid to
1101 (their_keyid). Set the DH pubkey in the Data message to the public
1102 part of our_dh[our_keyid]. Use our_dh[our_keyid-1] and
1103 their_y[their_keyid] to calculate session keys, as outlined below.
1104 Use the "sending AES key" to encrypt the message, and the "sending
1105 MAC key" to calculate its MAC.</dd>
1106
1107 <dt>When you receive a Data Message:</dt>
1108 <dd>Use the keyids in the message to select which of your DH key pairs
1109 and which of his DH pubkeys to use to verify the MAC. If the keyids
1110 do not represent either the most recent key or the previous key (for
1111 either the sender or receiver), reject the message. Also reject the
1112 message if the sender keyid is their_keyid-1, but
1113 their_y[their_keyid-1] is NULL.
1114
1115 <p>Otherwise, calculate the session keys as outlined below. Use the
1116 "receiving MAC key" to verify the MAC on the message. If it does not
1117 verify, reject the message.</p>
1118
1119 <p>Check that the counter in the Data message is strictly larger than the
1120 last counter you saw using this pair of keys. If not, reject the
1121 message.</p>
1122
1123 <p>If the MAC verifies, decrypt the message using the "receiving AES
1124 key".</p>
1125
1126 <p>Finally, check if keys need rotation:</p>
1127 <ul>
1128 <li>If the "recipient keyid" in the Data message equals our_keyid, then
1129 he's seen the public part of our most recent DH key pair, so you
1130 must securely forget our_dh[our_keyid-1], increment our_keyid, and set
1131 our_dh[our_keyid] to a new DH key pair which you generate.</li>
1132 <li>If the "sender keyid" in the Data message equals their_keyid,
1133 increment their_keyid, and set their_y[their_keyid] to the new DH
1134 pubkey specified in the Data message.</li>
1135 </ul></dd>
1136 </dl>
1137
1138 <h4>Computing AES keys, MAC keys, and the secure session id</h4>
1139 <p>OTR uses Diffie-Hellman to calculate shared secrets in the usual way:
1140 if Bob knows x, and tells Alice g<sup>x</sup>, and Alice knows y, and
1141 tells Bob g<sup>y</sup>, then they each can calculate s =
1142 g<sup>xy</sup>: Alice calculates (g<sup>x</sup>)<sup>y</sup>, and Bob
1143 calculates (g<sup>y</sup>)<sup>x</sup>.</p>
1144 <p>During the AKE, Alice and Bob each calculate s in this way, and then
1145 they each compute seven values based on s:</p>
1146 <ul>
1147 <li>A 64-bit secure session id, ssid</li>
1148 <li>Two 128-bit AES encryption keys, c and c'</li>
1149 <li>Four 256-bit SHA256-HMAC keys, m1, m2, m1', and m2'</li>
1150 </ul>
1151 <p>This is done in the following way:</p>
1152 <ul>
1153 <li>Write the value of s as a minimum-length MPI, as specified above
1154 (4-byte big-endian len, len-byte big-endian value). Let this
1155 (4+len)-byte value be "secbytes".</li>
1156 <li>For a given byte b, define h2(b) to be the 256-bit output of the
1157 SHA256 hash of the (5+len) bytes consisting of the byte b followed by
1158 secbytes.</li>
1159 <li>Let ssid be the first 64 bits of h2(0x00).</li>
1160 <li>Let c be the first 128 bits of h2(0x01), and let c' be the second
1161 128 bits of h2(0x01).</li>
1162 <li>Let m1 be h2(0x02).</li>
1163 <li>Let m2 be h2(0x03).</li>
1164 <li>Let m1' be h2(0x04).</li>
1165 <li>Let m2' be h2(0x05).</li>
1166 </ul>
1167 <p>c, m1, and m2 are used to create and verify the Reveal Signature
1168 Message; c', m1', and m2' are used to create and verify the Signature
1169 message.</p>
1170 <p>If the user requests to see the secure session id, it should be
1171 displayed as two 32-bit bigendian unsigned values, in C "%08x" format.
1172 If the user transmitted the Reveal Signature message during the AKE that
1173 produced this ssid, then display the first 32 bits in bold, and the
1174 second 32 bits in non-bold. If the user transmitted the Signature
1175 message instead, display the first 32 bits in non-bold, and the
1176 second 32 bits in bold. This session id can be used by the parties to
1177 verify (say, over the telephone, assuming the parties recognize each
1178 others' voices) that there is no man-in-the-middle by having each side
1179 read his bold part to the other. [Note that this only needs to be done
1180 in the event that the users do not trust that their long-term signature
1181 keys have not been compromised.]</p>
1182 <p>During the exchange of Data Messages, Alice and Bob use the keyids
1183 listed in the Data Message to select Diffie-Hellman keys to use to
1184 compute s, and the (4+len)-byte value of secbytes, as above.</p>
1185 <p>From this, they calculate four values:</p>
1186 <ul>
1187 <li>Two 128-bit AES encryption keys, the "sending AES key", and the
1188 "receiving AES key"</li>
1189 <li>Two 160-bit SHA1-HMAC keys, the "sending MAC key", and the
1190 "receiving MAC key"</li>
1191 </ul>
1192 <p>These keys are calculated as follows:</p>
1193 <ul>
1194 <li>Alice (and similarly for Bob) determines if she is the "low" end
1195 or the "high" end of this Data Message. If Alice's public key is
1196 numerically greater than Bob's public key, then she
1197 is the "high" end. Otherwise, she is the "low" end. Note that who is the
1198 "low" end and who is the "high" end can change every time a new D-H
1199 public key is exchanged in a Data Message.</li>
1200 <li>She sets the values of "sendbyte" and "recvbyte" according to
1201 whether she is the the "low" or the "high" end of the Data Message:
1202 <ul>
1203 <li>If she is the "high" end, she sets "sendbyte" to 0x01 and "recvbyte"
1204 to 0x02.</li>
1205 <li>If she is the "low" end, she sets "sendbyte" to 0x02 and "recvbyte"
1206 to 0x01.</li>
1207 </ul></li>
1208 <li>For a given byte b, define h1(b) to be the 160-bit output of the
1209 SHA-1 hash of the (5+len) bytes consisting of the byte b, followed by
1210 secbytes.</li>
1211 <li>The "sending AES key" is the first 16 bytes of h1(sendbyte).</li>
1212 <li>The "sending MAC key" is the 20-byte SHA-1 hash of the 16-byte
1213 sending AES key.</li>
1214 <li>The "receiving AES key" is the first 16 bytes of h1(recvbyte).</li>
1215 <li>The "receiving MAC key" is the 20-byte SHA-1 hash of the 16-byte
1216 receiving AES key.</li>
1217 </ul>
1218 <h4>Extra symmetric key</h4>
1219 <p>OTR version 3 defines an additional symmetric key that can be derived
1220 by the communicating parties to use for application-specific purposes,
1221 such as file transfer, voice encryption, etc. When one party wishes to
1222 use the extra symmetric key, he or she creates a type 8 TLV attached to
1223 a Data Message (see above). The key itself is then derived using the
1224 same "secbytes" used to compute the encryption and MAC keys used to
1225 protect the Data Message.
1226 The extra symmetric key is derived by calculating
1227 h2(0xFF) and keeping the entire 256 bits, using the same definition
1228 of h2 as above.</p>
1229 <p>Upon receipt of the Data Message containing the type 8 TLV, the
1230 recipient will compute the extra symmetric key in the same way. Note
1231 that the value of the extra symmetric key is <em>not</em> contained in
1232 the TLV itself.</p>
1233 <h4>Revealing MAC keys</h4>
1234 <p>Whenever you are about to forget either one of your old D-H key pairs, or
1235 one of your correspondent's old D-H public keys, take all of the
1236 receiving MAC keys
1237 that were generated by that key (note that there are up to two: the
1238 receiving MAC keys produced by the pairings of that key with
1239 each of two of the other side's keys; but note that you only need to
1240 take MAC keys that were actually used to verify a MAC on a message), and
1241 put them (as a set of
1242 concatenated 20-byte values) into the "Old MAC keys to be revealed"
1243 section of the next Data Message you send. This in done to allow the
1244 forgeability of OTR transcripts: once the MAC keys are revealed, anyone
1245 can modify an OTR message and still have it appear valid. But since we
1246 don't reveal the MAC keys until their corresponding pubkeys are being
1247 discarded, there is no danger of accepting a message as valid which
1248 uses a MAC key which has already been revealed.</p>
1249 <h3>Fragmentation</h3>
1250 <p>Some networks may have a maximum message size that is too small to
1251 contain an encoded OTR message. In that event, the sender may choose
1252 to split the message into a number of <em>fragments</em>. This section
1253 describes the format of the fragments. All OTR version 2 and 3 clients
1254 must be able to assemble received fragments, but performing
1255 fragmentation on outgoing messages is optional.</p>
1256
1257 <dl class="doublespace">
1258 <dt>Transmitting Fragments</dt>
1259 <dd>If you have information about the maximum size of message you are
1260 able to send (the different IM networks have different limits), you
1261 can fragment an encoded OTR message as follows:
1262 <ul>
1263 <li>Start with the OTR message as you would normally transmit it. For
1264 example, a Data Message would start with "?OTR:AAED" and end
1265 with ".".</li>
1266 <li>Break it up into sufficiently small pieces. Let the number of
1267 pieces be (n), and the pieces be
1268 piece[1],piece[2],...,piece[n].</li>
1269 <li>Transmit (n) OTR version 3 fragmented messages with the following
1270 (printf-like) structure (as k runs from 1 to n inclusive):
1271
1272 <p>"?OTR|%x|%x,%hu,%hu,%s," , sender_instance, receiver_instance,
1273 k , n , piece[k]</p>
1274
1275 OTR version 2 messages get fragmented in a similar format, but
1276 without the instance tags fields:
1277
1278 <p>"?OTR,%hu,%hu,%s," ,
1279 k , n , piece[k]</p></li>
1280
1281 <li>Note that k and n are unsigned short ints (2 bytes), and each has
1282 a maximum value of 65535. Also, each piece[k] must be
1283 non-empty. The instance tags (if applicable) and the k and n
1284 values may have leading zeroes.</li>
1285 </ul>
1286 <p>Note that fragments are not themselves messages that can be
1287 fragmented: you can't fragment a fragment.</p></dd>
1288
1289 <dt>Receiving Fragments:</dt>
1290
1291 <dd>If you receive a message containing "?OTR|" (note that you'll need
1292 to check for this _before_ checking for any of the other "?OTR:"
1293 markers):
1294
1295 <ul>
1296 <li>Parse it as the printf statement above into k, n, and
1297 piece.</li>
1298 <li>If the recipient's own instance tag does not match the listed
1299 receiver instance tag, and the listed receiver instance tag is not
1300 zero, the recipient should discard the message and optionally pass
1301 along a warning for the user.</li>
1302 <li>Let (K,N) be your currently stored fragment number, and F be your
1303 currently stored fragment. [If you have no currently stored
1304 fragment, then K = N = 0 and F = "".]</li>
1305
1306 <li>If k == 0 or n == 0 or k &gt; n, discard this (illegal)
1307 fragment.</li>
1308
1309 <li>If k == 1:
1310 <ul>
1311 <li>Forget any stored fragment you may have</li>
1312 <li>Store (piece) as F.</li>
1313 <li>Store (k,n) as (K,N).</li>
1314 </ul></li>
1315
1316 <li>If n == N and k == K+1:
1317 <ul>
1318 <li>Append (piece) to F.</li>
1319 <li>Store (k,n) as (K,N).</li>
1320 </ul></li>
1321
1322 <li>Otherwise:
1323 <ul>
1324 <li>Forget any stored fragment you may have</li>
1325 <li>Store "" as F.</li>
1326 <li>Store (0,0) as (K,N).</li>
1327 </ul></li>
1328 </ul>
1329
1330 <p>After this, if N &gt; 0 and K == N, treat F as the received
1331 message.</p>
1332
1333 <p>If you receive a non-OTR message, or an unfragmented message,
1334 forget any stored fragment you may have, store "" as F and store
1335 (0,0) as (K,N).</p>
1336
1337 <p>OTR version 2 fragmented messages follow the same behaviour as
1338 described above, but do not list the sender and receiver instance
1339 tags.</dd>
1340 </dl>
1341
1342 <p>For example, here is a Data Message we would like to transmit over a
1343 network with an unreasonably small maximum message size:</p>
1344
1345 <blockquote><pre>
1346 ?OTR:AAMDJ+MVmSfjFZcAAAAAAQAAAAIAAADA1g5IjD1ZGLDVQEyCgCyn9hb
1347 rL3KAbGDdzE2ZkMyTKl7XfkSxh8YJnudstiB74i4BzT0W2haClg6dMary/jo
1348 9sMudwmUdlnKpIGEKXWdvJKT+hQ26h9nzMgEditLB8vjPEWAJ6gBXvZrY6ZQ
1349 rx3gb4v0UaSMOMiR5sB7Eaulb2Yc6RmRnnlxgUUC2alosg4WIeFN951PLjSc
1350 ajVba6dqlDi+q1H5tPvI5SWMN7PCBWIJ41+WvF+5IAZzQZYgNaVLbAAAAAAA
1351 AAAEAAAAHwNiIi5Ms+4PsY/L2ipkTtquknfx6HodLvk3RAAAAAA==.
1352 </pre></blockquote>
1353
1354 <p>We could fragment this message into (for example) three
1355 pieces:</p>
1356
1357 <blockquote><pre>
1358 ?OTR|5a73a599|27e31597,00001,00003,?OTR:AAMDJ+MVmSfjFZcAAAAA
1359 AQAAAAIAAADA1g5IjD1ZGLDVQEyCgCyn9hbrL3KAbGDdzE2ZkMyTKl7XfkSx
1360 h8YJnudstiB74i4BzT0W2haClg6dMary/jo9sMudwmUdlnKpIGEKXWdvJKT+
1361 hQ26h9nzMgEditLB8v,
1362 </pre></blockquote>
1363
1364 <blockquote><pre>
1365 ?OTR|5a73a599|27e31597,00002,00003,jPEWAJ6gBXvZrY6ZQrx3gb4v0
1366 UaSMOMiR5sB7Eaulb2Yc6RmRnnlxgUUC2alosg4WIeFN951PLjScajVba6dq
1367 lDi+q1H5tPvI5SWMN7PCBWIJ41+WvF+5IAZzQZYgNaVLbAAAAAAAAAAEAAAA
1368 HwNiIi5Ms+4PsY/L2i,
1369 </pre></blockquote>
1370
1371 <blockquote><pre>
1372 ?OTR|5a73a599|27e31597,00003,00003,pkTtquknfx6HodLvk3RAAAAAA
1373 ==.,
1374 </pre></blockquote>
1375 <h3>The protocol state machine</h3>
1376 <p>An OTR client maintains separate state for every correspondent. For
1377 example, Alice may have an active OTR conversation with Bob, while
1378 having an unprotected conversation with Charlie. This state consists of
1379 two main state variables, as well as some other information (such as
1380 encryption keys). The two main state variables are:</p>
1381 <h4>Message state</h4>
1382 <p>The message state variable, msgstate, controls what happens to
1383 outgoing messages typed by the user. It can take one of three
1384 values:</p>
1385 <dl>
1386 <dt>MSGSTATE_PLAINTEXT</dt>
1387 <dd>This state indicates that outgoing messages are sent without
1388 encryption. This is the state that is used before an OTR conversation
1389 is initiated. This is the initial state, and the only way to
1390 subsequently enter this state is for the user to explicitly request to
1391 do so via some UI operation.</dd>
1392 <dt>MSGSTATE_ENCRYPTED</dt>
1393 <dd>This state indicates that outgoing messages are sent encrypted.
1394 This is the state that is used during an OTR conversation. The only way
1395 to enter this state is for the authentication state machine (below) to
1396 successfully complete.</dd>
1397 <dt>MSGSTATE_FINISHED</dt>
1398 <dd>This state indicates that outgoing messages are not delivered at
1399 all. This state is entered only when the other party indicates he has
1400 terminated his side of the OTR conversation. For example, if Alice and
1401 Bob are having an OTR conversation, and Bob instructs his OTR client to
1402 end its private session with Alice (for example, by logging out), Alice
1403 will be notified of this, and <em>her</em> client will switch to
1404 MSGSTATE_FINISHED mode. This prevents Alice from accidentally sending a
1405 message to Bob in plaintext. (Consider what happens if Alice was in the
1406 middle of typing a private message to Bob when he suddenly logs out,
1407 just as Alice hits Enter.)</dd>
1408 </dl>
1409 <h4>Authentication state</h4>
1410 <p>The authentication state variable, authstate, can take one of four
1411 values (plus one extra for OTR version 1 compatibility):</p>
1412 <dl>
1413 <dt>AUTHSTATE_NONE</dt>
1414 <dd>This state indicates that the authentication protocol is not
1415 currently in progress. This is the initial state.</dd>
1416 <dt>AUTHSTATE_AWAITING_DHKEY</dt>
1417 <dd>After Bob initiates the authentication protocol by sending Alice
1418 the D-H Commit Message, he enters this state to await Alice's reply.</dd>
1419 <dt>AUTHSTATE_AWAITING_REVEALSIG</dt>
1420 <dd>After Alice receives Bob's D-H Commit Message, and replies with her
1421 own D-H Key Message, she enters this state to await Bob's reply.</dd>
1422 <dt>AUTHSTATE_AWAITING_SIG</dt>
1423 <dd>After Bob receives Alice's D-H Key Message, and replies with his own
1424 Reveal Signature Message, he enters this state to await Alice's reply.</dd>
1425 <dt>AUTHSTATE_V1_SETUP</dt>
1426 <dd>For OTR version 1 compatibility, if Bob sends a version 1 Key
1427 Exchange Message to Alice, he enters this state to await Alice's
1428 reply.</dd>
1429 </dl>
1430 <p>After:</p>
1431 <ul>
1432 <li>Alice (in AUTHSTATE_AWAITING_REVEALSIG) receives Bob's Reveal
1433 Signature Message (and replies with her own Signature Message), <b>or</b>
1434 </li>
1435 <li>Bob (in AUTHSTATE_AWAITING_SIG) receives Alice's Signature Message,
1436 /li>
1437 </ul>
1438 <p>then,
1439 assuming the signature verifications succeed, the msgstate
1440 variable is transitioned to MSGSTATE_ENCRYPTED. Regardless of whether
1441 the signature verifications succeed, the authstate variable is
1442 transitioned to AUTHSTATE_NONE.</p>
1443 <h4>Policies</h4>
1444 <p>OTR clients can set different <b>policies</b> for different
1445 correspondents. For example, Alice could set up her client so that it
1446 speaks only OTR version 3, except with Charlie, who she knows has only
1447 an old client; so that it will opportunistically start an OTR conversation
1448 whenever it detects the correspondent supports it; or so that it refuses
1449 to send non-encrypted messages to Bob, ever.</p>
1450 <p>The policies that can be set (on a global or per-correspondent basis)
1451 are any combination of the following boolean flags:</p>
1452 <dl>
1453 <dt>ALLOW_V1</dt>
1454 <dd>Allow version 1 of the OTR protocol to be used (in general this
1455 document will not address OTR protocol version 1; see previous
1456 protocol documents for these details).</dd>
1457 <dt>ALLOW_V2</dt>
1458 <dd>Allow version 2 of the OTR protocol to be used.</dd>
1459 <dt>ALLOW_V3</dt>
1460 <dd>Allow version 3 of the OTR protocol to be used.</dd>
1461 <dt>REQUIRE_ENCRYPTION</dt>
1462 <dd>Refuse to send unencrypted messages.</dd>
1463 <dt>SEND_WHITESPACE_TAG</dt>
1464 <dd>Advertise your support of OTR using the whitespace tag.</dd>
1465 <dt>WHITESPACE_START_AKE</dt>
1466 <dd>Start the OTR AKE when you receive a whitespace tag.</dd>
1467 <dt>ERROR_START_AKE</dt>
1468 <dd>Start the OTR AKE when you receive an OTR Error Message.</dd>
1469 </dl>
1470 <p>Note that it is possible for UIs simply to offer the old
1471 "combinations" of options, and not ask about each one separately.</p>
1472 <h4>State transitions</h4>
1473 <p>There are twelve actions an OTR client must handle:</p>
1474 <ul>
1475 <li>Received messages:
1476 <ul>
1477 <li>Plaintext without the whitespace tag</li>
1478 <li>Plaintext with the whitespace tag</li>
1479 <li>Query Message</li>
1480 <li>Error Message</li>
1481 <li>D-H Commit Message</li>
1482 <li>D-H Key Message</li>
1483 <li>Reveal Signature Message</li>
1484 <li>Signature Message</li>
1485 <li>Data Message</li>
1486 </ul></li>
1487 <li>User actions:
1488 <ul>
1489 <li>User requests to start an OTR conversation</li>
1490 <li>User requests to end an OTR conversation</li>
1491 <li>User types a message to be sent</li>
1492 </ul></li>
1493 </ul>
1494 <p>The following sections will outline what actions to take in each
1495 case. They all assume that at least one of ALLOW_V1, ALLOW_V2 or
1496 ALLOW_V3 is set; if not, then OTR is completely disabled, and no
1497 special handling of messages should be done at all. For version 1
1498 messages, please refer to previous OTR protocol documents. For version
1499 3 messages, someone receiving a message with a recipient instance tag
1500 specified that does not equal their own should discard the message
1501 and optionally warn the user. The exception here is the D-H Commit
1502 Message where the recipient instance tag may be 0, indicating that no
1503 particular instance is specified.</p>
1504 <h4>Receiving plaintext without the whitespace tag</h4>
1505 <dl>
1506 <dt>If msgstate is MSGSTATE_PLAINTEXT:</dt>
1507 <dd>Simply display the message to the user. If REQUIRE_ENCRYPTION is
1508 set, warn him that the message was received unencrypted.</dd>
1509 <dt>If msgstate is MSGSTATE_ENCRYPTED or MSGSTATE_FINISHED:</dt>
1510 <dd>Display the message to the user, but warn him that the message was
1511 received unencrypted.</dd>
1512 </dl>
1513 <h4>Receiving plaintext with the whitespace tag</h4>
1514 <dl>
1515 <dt>If msgstate is MSGSTATE_PLAINTEXT:</dt>
1516 <dd>Remove the whitespace tag and display the message to the user. If
1517 REQUIRE_ENCRYPTION is set, warn him that the message was received
1518 unencrypted.</dd>
1519 <dt>If msgstate is MSGSTATE_ENCRYPTED or MSGSTATE_FINISHED:</dt>
1520 <dd>Remove the whitespace tag and display the message to the user, but
1521 warn him that the message was received unencrypted.</dd>
1522 </dl>
1523 <p>In any event, if WHITESPACE_START_AKE is set:</p>
1524 <dl>
1525 <dt>If the tag offers OTR version 3 and ALLOW_V3 is set:</dt>
1526 <dd>Send a version 3 D-H Commit Message, and transition authstate to
1527 AUTHSTATE_AWAITING_DHKEY.</dd>
1528 <dt>Otherwise, if the tag offers OTR version 2 and ALLOW_V2 is set:</dt>
1529 <dd>Send a version 2 D-H Commit Message, and transition authstate to
1530 AUTHSTATE_AWAITING_DHKEY.</dd>
1531 </dl>
1532 <h4>Receiving a Query Message</h4>
1533 <dl>
1534 <dt>If the query message offers OTR version 3 and ALLOW_V3 is set:</dt>
1535 <dd>Send a version 3 D-H Commit Message, and transition authstate to
1536 AUTHSTATE_AWAITING_DHKEY.</dd>
1537 <dt>Otherwise, if the message offers OTR version 2 and ALLOW_V2 is set:</dt>
1538 <dd>Send a version 2 D-H Commit Message, and transition authstate to
1539 AUTHSTATE_AWAITING_DHKEY.</dd>
1540 </dl>
1541 <h4>Receiving an Error Message</h4>
1542 <p>Display the message to the user. If ERROR_START_AKE is set, reply
1543 with a Query Message.</p>
1544 <h4>User requests to start an OTR conversation</h4>
1545 <p>Send an OTR Query Message to the correspondent.</p>
1546 <h4>Receiving a D-H Commit Message</h4>
1547 <p>If the message is version 2 and ALLOW_V2 is not set, ignore this message.
1548 Similarly if the message is version 3 and ALLOW_V3 is not set, ignore the
1549 message. Otherwise:</p>
1550 <dl>
1551 <dt>If authstate is AUTHSTATE_NONE:</dt>
1552 <dd>Reply with a D-H Key Message, and transition authstate to
1553 AUTHSTATE_AWAITING_REVEALSIG.</dd>
1554 <dt>If authstate is AUTHSTATE_AWAITING_DHKEY:</dt>
1555 <dd>This is the trickiest transition in the whole protocol. It
1556 indicates that you have already sent a D-H Commit message to your
1557 correspondent, but that he either didn't receive it, or just didn't
1558 receive it <em>yet</em>, and has sent you one as well. The symmetry
1559 will be broken by comparing the hashed g<sup>x</sup> you sent in your
1560 D-H Commit Message with the one you received, considered as 32-byte
1561 unsigned big-endian values.
1562 <dl>
1563 <dt>If yours is the higher hash value:</dt>
1564 <dd>Ignore the incoming D-H Commit message, but resend your D-H
1565 Commit message.</dd>
1566 <dt>Otherwise:</dt>
1567 <dd>Forget your old g<sup>x</sup> value that you sent (encrypted)
1568 earlier, and pretend you're in AUTHSTATE_NONE; i.e. reply with a D-H Key
1569 Message, and transition authstate to AUTHSTATE_AWAITING_REVEALSIG.</dd>
1570 </dl></dd>
1571 <dt>If authstate is AUTHSTATE_AWAITING_REVEALSIG:</dt>
1572 <dd>Retransmit your D-H Key Message (the same
1573 one as you sent when you entered AUTHSTATE_AWAITING_REVEALSIG). Forget
1574 the old D-H Commit message, and use this new one instead. There
1575 are a number of reasons this might happen, including:
1576 <ul>
1577 <li>Your correspondent simply started a new AKE.</li>
1578 <li>Your correspondent resent his D-H Commit message, as specified
1579 above.</li>
1580 <li>On some networks, like AIM, if your correspondent is logged in
1581 multiple times, each of his clients will send a D-H Commit Message in
1582 response to a Query Message; resending the same D-H Key Message in
1583 response to each of those messages will prevent compounded confusion,
1584 since each of his clients will see each of the D-H Key Messages you
1585 send. [And the problem gets even worse if you are <em>each</em> logged
1586 in multiple times.]</li>
1587 </ul></dd>
1588 <dt>If authstate is AUTHSTATE_AWAITING_SIG or AUTHSTATE_V1_SETUP:</dt>
1589 <dd>Reply with a new D-H Key message, and transition authstate to
1590 AUTHSTATE_AWAITING_REVEALSIG.</dd>
1591 </dl>
1592 <h4>Receiving a D-H Key Message</h4>
1593 <p>If the message is version 2 and ALLOW_V2 is not set, ignore this
1594 message. Similarly if the message is version 3 and ALLOW_V3 is not
1595 set, ignore this message. Otherwise:</p>
1596 <dl>
1597 <dt>If authstate is AUTHSTATE_AWAITING_DHKEY:</dt>
1598 <dd>Reply with a Reveal Signature Message and transition authstate to
1599 AUTHSTATE_AWAITING_SIG.</dd>
1600 <dt>If authstate is AUTHSTATE_AWAITING_SIG:</dt>
1601 <dd>
1602 <dl>
1603 <dt>If this D-H Key message is the same the one you received earlier
1604 (when you entered AUTHSTATE_AWAITING_SIG):</dt>
1605 <dd>Retransmit your Reveal Signature Message.</dd>
1606 <dt>Otherwise:</dt>
1607 <dd>Ignore the message.</dd>
1608 </dl></dd>
1609 <dt>If authstate is AUTHSTATE_NONE, AUTHSTATE_AWAITING_REVEALSIG, or
1610 AUTHSTATE_V1_SETUP:</dt>
1611 <dd>Ignore the message.</dd>
1612 </dl>
1613 <h4>Receiving a Reveal Signature Message</h4>
1614 <p>If the message is version 2 and ALLOW_V2 is not set, ignore this message.
1615 Similarly if the message is version 3 and ALLOW_V3 is not set, ignore the
1616 message. Otherwise:</p>
1617 <dl>
1618 <dt>If authstate is AUTHSTATE_AWAITING_REVEALSIG:</dt>
1619 <dd>Use the received value of r to decrypt the value of g<sup>x</sup>
1620 received in the D-H Commit Message, and verify the hash therein.
1621 Decrypt the encrypted signature, and verify the signature and the MACs.
1622 If everything checks out:
1623 <ul>
1624 <li>Reply with a Signature Message.</li>
1625 <li>Transition authstate to AUTHSTATE_NONE.</li>
1626 <li>Transition msgstate to MSGSTATE_ENCRYPTED.</li>
1627 <li>If there is a recent stored message, encrypt it and send it as a
1628 Data Message.</li>
1629 </ul>
1630 Otherwise, ignore the message.</dd>
1631 <dt>If authstate is AUTHSTATE_NONE, AUTHSTATE_AWAITING_DHKEY,
1632 AUTHSTATE_AWAITING_SIG, or AUTHSTATE_V1_SETUP:</dt>
1633 <dd>Ignore the message.</dd>
1634 </dl>
1635 <h4>Receiving a Signature Message</h4>
1636 <p>If the message is version 2 and ALLOW_V2 is not set, ignore this message.
1637 Similarly if the message is version 3 and ALLOW_V3 is not set, ignore the
1638 message. Otherwise:</p>
1639 <dl>
1640 <dt>If authstate is AUTHSTATE_AWAITING_SIG:</dt>
1641 <dd>Decrypt the encrypted signature, and verify the signature and the MACs.
1642 If everything checks out:
1643 <ul>
1644 <li>Transition authstate to AUTHSTATE_NONE.</li>
1645 <li>Transition msgstate to MSGSTATE_ENCRYPTED.</li>
1646 <li>If there is a recent stored message, encrypt it and send it as a
1647 Data Message.</li>
1648 </ul>
1649 Otherwise, ignore the message.</dd>
1650 <dt>If authstate is AUTHSTATE_NONE, AUTHSTATE_AWAITING_DHKEY,
1651 or AUTHSTATE_AWAITING_REVEALSIG:</dt>
1652 <dd>Ignore the message.</dd>
1653 </dl>
1654 <h4>User types a message to be sent</h4>
1655 <dl>
1656 <dt>If msgstate is MSGSTATE_PLAINTEXT:</dt>
1657 <dd><dl><dt>If REQUIRE_ENCRYPTION is set:</dt>
1658 <dd>Store the plaintext message for possible retransmission, and send a
1659 Query Message.</dd>
1660 <dt>Otherwise:</dt>
1661 <dd>If SEND_WHITESPACE_TAG is set, and you have not received a plaintext
1662 message from this correspondent since last entering MSGSTATE_PLAINTEXT,
1663 attach the whitespace tag to the message. Send the (possibly modified)
1664 message as plaintext.</dd></dl></dd>
1665 <dt>If msgstate is MSGSTATE_ENCRYPTED:</dt>
1666 <dd>Encrypt the message, and send it as a Data Message. Store the
1667 plaintext message for possible retransmission.</dd>
1668 <dt>If msgstate is MSGSTATE_FINISHED:</dt>
1669 <dd>Inform the user that the message cannot be sent at this time. Store
1670 the plaintext message for possible retransmission.</dd>
1671 </dl>
1672 <h4>Receiving a Data Message</h4>
1673 <dl>
1674 <dt>If msgstate is MSGSTATE_ENCRYPTED:</dt>
1675 <dd>Verify the information (MAC, keyids, ctr value, etc.) in the
1676 message.
1677 <dl>
1678 <dt>If the verification succeeds:</dt>
1679 <dd>
1680 <ul>
1681 <li>Decrypt the message and display the human-readable part (if
1682 non-empty) to the user.</li>
1683 <li>Update the D-H encryption keys, if necessary.</li>
1684 <li>If you have not sent a message to this correspondent in some
1685 (configurable) time, send a "heartbeat" message, consisting of a Data
1686 Message encoding an empty plaintext. The heartbeat message should have
1687 the IGNORE_UNREADABLE flag set.</li>
1688 <li>If the received message contains a TLV type 1, forget all encryption
1689 keys for this correspondent, and transition msgstate to
1690 MSGSTATE_FINISHED.</li>
1691 </ul>
1692 </dd>
1693 <dt>Otherwise, inform the user that an unreadable encrypted message was
1694 received, and reply with an Error Message.</dt>
1695 </dl></dd>
1696 <dt>If msgstate is MSGSTATE_PLAINTEXT or MSGSTATE_FINISHED:</dt>
1697 <dd>Inform the user that an unreadable encrypted message was received,
1698 and reply with an Error Message.</dd>
1699 </dl>
1700 <h4>User requests to end an OTR conversation</h4>
1701 <dl>
1702 <dt>If msgstate is MSGSTATE_PLAINTEXT:</dt>
1703 <dd>Do nothing.</dd>
1704 <dt>If msgstate is MSGSTATE_ENCRYPTED:</dt>
1705 <dd>Send a Data Message, encoding a message with an empty human-readable
1706 part, and TLV type 1. Transition msgstate to MSGSTATE_PLAINTEXT.</dd>
1707 <dt>If msgstate is MSGSTATE_FINISHED:</dt>
1708 <dd>Transition msgstate to MSGSTATE_PLAINTEXT.</dd>
1709 </dl>
1710 </body></html>