-
Notifications
You must be signed in to change notification settings - Fork 14
/
Copy pathProtocol-v3.html
1703 lines (1670 loc) · 75.8 KB
/
Protocol-v3.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html
PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html><head>
<title>Off-the-Record Messaging Protocol version 3 - DRAFT</title>
<style type="text/css">
body { background: white; color: black }
h1 { text-align: center }
dd ul.note { list-style: none }
dl.doublespace dd { margin-bottom: 2ex }
</style>
</head><body>
<h1>Off-the-Record Messaging Protocol version 3</h1>
<p>This document describes version 3 of the Off-the-Record Messaging
protocol. The main changes over version 2 include:</p>
<ul>
<li>Both fragmented and unfragmented messages contain sender and
recipient instance tags. This avoids an issue on IM networks that
always relay all messages to all sessions of a client who is logged
in multiple times. In this situation, OTR clients can attempt to
establish an OTR session indefinitely if there are interleaving
messages from each of the sessions.</li>
<li>An extra symmetric key is derived during AKE. This may be used for
secure communication over a different channel (e.g., file transfer,
voice chat).</li>
</ul>
<h2>Very high level overview</h2>
<p>OTR assumes a network model which provides in-order delivery of
messages, but that some messages may not get delivered at all
(for example, if the user disconnects). There may be
an active attacker, who is allowed to perform a Denial of
Service attack, but not to learn the contents of messages.</p>
<ol>
<li>Alice signals to Bob that she would like (using an OTR Query Message)
or is willing (using a whitespace-tagged plaintext message) to use OTR
to communicate. Either mechanism should convey the version(s) of OTR
that Alice is willing to use.</li>
<li>Bob initiates the authenticated key exchange (AKE) with Alice.
Versions 2 and 3 of OTR use a variant of the SIGMA protocol as its AKE.</li>
<li>Alice and Bob exchange Data Messages to send information to each
other.</li>
</ol>
<h2>High level overview</h2>
<h3>Requesting an OTR conversation</h3>
<p>There are two ways Alice can inform Bob that she is willing to use
the OTR protocol to speak with him: by sending him the OTR Query Message,
or by including a special "tag" consisting of whitespace characters in
one of her messages to him. Each method also includes a way for Alice
to communicate to Bob which versions of the OTR protocol she is willing
to speak with him.</p>
<p>The semantics of the OTR Query Message are that Alice is
<em>requesting</em> that Bob start an OTR conversation with her (if, of
course, he is willing and able to do so). On the other hand, the
semantics of the whitespace tag are that Alice is merely
<em>indicating</em> to Bob that she is willing and able to have an OTR
conversation with him. If Bob has a policy of "only use OTR when it's
explicitly requested", for example, then he <em>would</em> start an OTR
conversation upon receiving an OTR Query Message, but <em>would not</em>
upon receiving the whitespace tag.</p>
<h3>Authenticated Key Exchange (AKE)</h3>
<p>This section outlines the version of the SIGMA protocol used as the
AKE. All exponentiations are done modulo a particular 1536-bit prime,
and g is a generator of that group, as indicated in the detailed
description below. Alice and Bob's long-term authentication public keys
are pub<sub>A</sub> and pub<sub>B</sub>, respectively.</p>
<p>The general idea is that Alice and Bob do an <em>unauthenticated</em>
Diffie-Hellman (D-H) key exchange to set up an encrypted channel, and
then do mutual authentication <em>inside</em> that channel.</p>
<p>Bob will be initiating the AKE with Alice.</p>
<ul>
<li>Bob:
<ol>
<li>Picks a random value r (128 bits)</li>
<li>Picks a random value x (at least 320 bits)</li>
<li>Sends Alice AES<sub>r</sub>(g<sup>x</sup>), HASH(g<sup>x</sup>)</li>
</ol></li>
<li>Alice:
<ol>
<li>Picks a random value y (at least 320 bits)</li>
<li>Sends Bob g<sup>y</sup></li>
</ol></li>
<li>Bob:
<ol>
<li>Verifies that Alice's g<sup>y</sup> is a legal value (2 <=
g<sup>y</sup> <= modulus-2)</li>
<li>Computes s = (g<sup>y</sup>)<sup>x</sup></li>
<li>Computes two AES keys c, c' and four MAC keys m1, m1', m2, m2' by
hashing s in various ways</li>
<li>Picks keyid<sub>B</sub>, a serial number for his D-H key
g<sup>x</sup></li>
<li>Computes M<sub>B</sub> = MAC<sub>m1</sub>(g<sup>x</sup>, g<sup>y</sup>,
pub<sub>B</sub>, keyid<sub>B</sub>)</li>
<li>Computes X<sub>B</sub> = pub<sub>B</sub>, keyid<sub>B</sub>,
sig<sub>B</sub>(M<sub>B</sub>)</li>
<li>Sends Alice r, AES<sub>c</sub>(X<sub>B</sub>),
MAC<sub>m2</sub>(AES<sub>c</sub>(X<sub>B</sub>))</li>
</ol></li>
<li>Alice:
<ol>
<li>Uses r to decrypt the value of g<sup>x</sup> sent earlier</li>
<li>Verifies that HASH(g<sup>x</sup>) matches the value sent earlier</li>
<li>Verifies that Bob's g<sup>x</sup> is a legal value (2 <=
g<sup>x</sup> <= modulus-2)</li>
<li>Computes s = (g<sup>x</sup>)<sup>y</sup> (note that this will be the
same as the value of s Bob calculated)</li>
<li>Computes two AES keys c, c' and four MAC keys m1, m1', m2, m2' by
hashing s in various ways (the same as Bob)</li>
<li>Uses m2 to verify MAC<sub>m2</sub>(AES<sub>c</sub>(X<sub>B</sub>))</li>
<li>Uses c to decrypt AES<sub>c</sub>(X<sub>B</sub>) to obtain
X<sub>B</sub> = pub<sub>B</sub>, keyid<sub>B</sub>,
sig<sub>B</sub>(M<sub>B</sub>)</li>
<li>Computes M<sub>B</sub> = MAC<sub>m1</sub>(g<sup>x</sup>,
g<sup>y</sup>, pub<sub>B</sub>, keyid<sub>B</sub>)</li>
<li>Uses pub<sub>B</sub> to verify sig<sub>B</sub>(M<sub>B</sub>)</li>
<li>Picks keyid<sub>A</sub>, a serial number for her D-H key
g<sup>y</sup></li>
<li>Computes M<sub>A</sub> = MAC<sub>m1'</sub>(g<sup>y</sup>, g<sup>x</sup>,
pub<sub>A</sub>, keyid<sub>A</sub>)</li>
<li>Computes X<sub>A</sub> = pub<sub>A</sub>, keyid<sub>A</sub>,
sig<sub>A</sub>(M<sub>A</sub>)</li>
<li>Sends Bob AES<sub>c'</sub>(X<sub>A</sub>),
MAC<sub>m2'</sub>(AES<sub>c'</sub>(X<sub>A</sub>))</li>
</ol></li>
<li>Bob:
<ol>
<li>Uses m2' to verify MAC<sub>m2'</sub>(AES<sub>c'</sub>(X<sub>A</sub>))</li>
<li>Uses c' to decrypt AES<sub>c'</sub>(X<sub>A</sub>) to obtain
X<sub>A</sub> = pub<sub>A</sub>, keyid<sub>A</sub>,
sig<sub>A</sub>(M<sub>A</sub>)</li>
<li>Computes M<sub>A</sub> = MAC<sub>m1'</sub>(g<sup>y</sup>,
g<sup>x</sup>, pub<sub>A</sub>, keyid<sub>A</sub>)</li>
<li>Uses pub<sub>A</sub> to verify sig<sub>A</sub>(M<sub>A</sub>)</li>
</ol></li>
<li>If all of the verifications succeeded, Alice and Bob now know each
other's Diffie-Hellman public keys, and share the value s. Alice is
assured that s is known by someone with access to the private key
corresponding to pub<sub>B</sub>, and similarly for Bob.</li>
</ul>
<h3>Exchanging data</h3>
<p>This section outlines the method used to protect data being exchanged
between Alice and Bob. As above, all exponentiations are done modulo
a particular 1536-bit prime, and g is a generator of
that group, as indicated in the detailed description below.</p>
<p>Suppose Alice has a message (msg) to send to Bob.</p>
<ul>
<li>Alice:
<ol>
<li>Picks the most recent of her own D-H encryption keys that Bob has
acknowledged receiving (by using it in a Data Message, or failing that,
in the AKE). Let key<sub>A</sub> by that key, and let keyid<sub>A</sub>
be its serial number.</li>
<li>If the above key is Alice's most recent key, she generates a new D-H key
(next_dh), to get the serial number keyid<sub>A</sub>+1.</li>
<li>Picks the most recent of Bob's D-H encryption keys that she has
received from him (either in a Data Message or in the AKE). Let
key<sub>B</sub> by that key, and let keyid<sub>B</sub> be its serial
number.</li>
<li>Uses Diffie-Hellman to compute a shared secret from the two keys
key<sub>A</sub> and key<sub>B</sub>, and generates the
sending AES key, ek, and the sending MAC key, mk, as detailed
below.</li>
<li>Collects any old MAC keys that were used in previous messages, but
will never again be used (because their associated D-H keys are no
longer the most recent ones) into a list, oldmackeys.</li>
<li>Picks a value of the counter, ctr, so that the triple
(key<sub>A</sub>, key<sub>B</sub>, ctr) is never the same for more
than one Data Message Alice sends to Bob.</li>
<li>Computes T<sub>A</sub> = (keyid<sub>A</sub>, keyid<sub>B</sub>, next_dh,
ctr, AES-CTR<sub>ek,ctr</sub>(msg))</li>
<li>Sends Bob T<sub>A</sub>, MAC<sub>mk</sub>(T<sub>A</sub>),
oldmackeys</li>
</ol></li>
<li>Bob:
<ol>
<li>Uses Diffie-Hellman to compute a shared secret from the two keys
labelled by keyid<sub>A</sub> and keyid<sub>B</sub>, and generates the
receiving AES key, ek, and the receiving MAC key, mk, as detailed
below. (These will be the same as the keys Alice generated, above.)</li>
<li>Uses mk to verify MAC<sub>mk</sub>(T<sub>A</sub>).</li>
<li>Uses ek and ctr to decrypt
AES-CTR<sub>ek,ctr</sub>(msg).</li>
</ol>
</li>
</ul>
<h3>Socialist Millionaires' Protocol (SMP)</h3>
<p>While data messages are being exchanged, either Alice or Bob may
run SMP to detect impersonation or man-in-the-middle attacks.
As above, all exponentiations are done modulo a particular 1536-bit
prime, and g<sub>1</sub> is a generator of that group. All sent values
include zero-knowledge proofs that they were generated according to
this protocol, as indicated in the detailed description below.</p>
<p>Suppose Alice and Bob have secret information x and y respectively,
and they wish to know whether x = y. The Socialist Millionaires' Protocol
allows them to compare x and y without revealing any other information
than the value of (x == y). For OTR, the secrets contain
information about both parties' long-term authentication public keys,
as well as information entered by the users themselves. If x = y,
this means that Alice and Bob entered the same secret information, and
so must be the same entities who established that secret to begin with.</p>
<p>Assuming that Alice begins the exchange:</p>
<ul>
<li>Alice:
<ol>
<li>Picks random exponents a<sub>2</sub> and a<sub>3</sub></li>
<li>Sends Bob g<sub>2a</sub> = g<sub>1</sub><sup>a<sub>2</sub></sup> and
g<sub>3a</sub> = g<sub>1</sub><sup>a<sub>3</sub></sup></li>
</ol></li>
<li>Bob:
<ol>
<li>Picks random exponents b<sub>2</sub> and b<sub>3</sub></li>
<li>Computes g<sub>2b</sub> = g<sub>1</sub><sup>b<sub>2</sub></sup> and
g<sub>3b</sub> = g<sub>1</sub><sup>b<sub>3</sub></sup></li>
<li>Computes g<sub>2</sub> = g<sub>2a</sub><sup>b<sub>2</sub></sup> and
g<sub>3</sub> = g<sub>3a</sub><sup>b<sub>3</sub></sup></li>
<li>Picks random exponent r</li>
<li>Computes P<sub>b</sub> = g<sub>3</sub><sup>r</sup> and
Q<sub>b</sub> = g<sub>1</sub><sup>r</sup> g<sub>2</sub><sup>y</sup></li>
<li>Sends Alice g<sub>2b</sub>, g<sub>3b</sub>, P<sub>b</sub> and
Q<sub>b</sub></li>
</ol></li>
<li>Alice:
<ol>
<li>Computes g<sub>2</sub> = g<sub>2b</sub><sup>a<sub>2</sub></sup> and
g<sub>3</sub> = g<sub>3b</sub><sup>a<sub>3</sub></sup></li>
<li>Picks random exponent s</li>
<li>Computes P<sub>a</sub> = g<sub>3</sub><sup>s</sup> and
Q<sub>a</sub> = g<sub>1</sub><sup>s</sup> g<sub>2</sub><sup>x</sup></li>
<li>Computes R<sub>a</sub> = (Q<sub>a</sub> / Q<sub>b</sub>)
<sup>a<sub>3</sub></sup></li>
<li>Sends Bob P<sub>a</sub>, Q<sub>a</sub> and R<sub>a</sub></li>
</ol></li>
<li>Bob:
<ol>
<li>Computes R<sub>b</sub> = (Q<sub>a</sub> / Q<sub>b</sub>)
<sup>b<sub>3</sub></sup></li>
<li>Computes R<sub>ab</sub> = R<sub>a</sub><sup>b<sub>3</sub></sup></li>
<li>Checks whether R<sub>ab</sub> == (P<sub>a</sub> / P<sub>b</sub>)</li>
<li>Sends Alice R<sub>b</sub></li>
</ol></li>
<li>Alice:
<ol>
<li>Computes R<sub>ab</sub> = R<sub>b</sub><sup>a<sub>3</sub></sup></li>
<li>Checks whether R<sub>ab</sub> == (P<sub>a</sub> / P<sub>b</sub>)</li>
</ol></li>
<li>If everything is done correctly, then R<sub>ab</sub> should hold the
value of (P<sub>a</sub> / P<sub>b</sub>) times
(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
the protocol will only succeed if x == y. Further, since
g<sub>2</sub><sup>a<sub>3</sub>b<sub>3</sub></sup> is a random number
not known to any party, if x is not equal to y, no other information is
revealed.</li>
</ul>
<h2>Details of the protocol</h2>
<h3>Unencoded messages</h3>
<p>This section describes the messages in the OTR protocol that are not
base-64 encoded binary.</p>
<h4>OTR Query Messages</h4>
<p>If Alice wishes to communicate to Bob that she would like to use OTR,
she sends a message containing the string "?OTR" followed by an
indication of what versions of OTR she is willing to use with Bob. The
version string is constructed as follows:</p>
<ul>
<li>If she is willing to use OTR version 1, the version string must
start with "?".</li>
<li>If she is willing to use OTR versions other than 1, a "v" followed
by the byte identifiers for the versions in question, followed by "?".
The byte identifier for OTR version 2 is "2", and similarly for 3. The
order of the identifiers between the "v" and the "?" does not matter,
but none should be listed more than once.</li>
</ul>
<p>For example:</p>
<dl>
<dt>"?OTR?"</dt>
<dd>Version 1 only</dd>
<dt>"?OTRv2?"</dt>
<dd>Version 2 only</dd>
<dt>"?OTRv23?"</dt>
<dd>Versions 2 and 3</dd>
<dt>"?OTR?v2?"</dt>
<dd>Versions 1 and 2</dd>
<dt>"?OTRv24x?"</dt>
<dd>Version 2, and hypothetical future versions identified by "4" and
"x"</dd>
<dt>"?OTR?v24x?"</dt>
<dd>Versions 1, 2, and hypothetical future versions identified by "4" and
"x"</dd>
<dt>"?OTR?v?"</dt>
<dd>Also version 1 only</dd>
<dt>"?OTRv?"</dt>
<dd>A bizarre claim that Alice would like to start an OTR conversation,
but is unwilling to speak any version of the protocol</dd>
</dl>
<p>These strings may be hidden from the user (for example, in
an attribute of an HTML tag), and/or may be accompanied by an
explanitory message ("Alice has requested an Off-the-Record private
conversation."). If Bob is willing to use OTR with Alice (with a
protocol version that Alice has offered), he should start the AKE.</p>
<h4>Tagged plaintext messages</h4>
<p>If Alice wishes to communicate to Bob that she is willing to use OTR,
she can attach a special whitespace tag to any plaintext message she
sends him. This tag may occur anywhere in the message, and may be
hidden from the user (as in the Query Messages, above).</p>
<p>The tag consists of the following 16 bytes, followed by one or more
sets of 8 bytes indicating the version of OTR Alice is willing to
use:</p>
<ul>
<li>Always send "\x20\x09\x20\x20\x09\x09\x09\x09"
"\x20\x09\x20\x09\x20\x09\x20\x20", followed by one or more of:</li>
<li>"\x20\x09\x20\x09\x20\x20\x09\x20" to indicate a willingness to use
OTR version 1 with Bob (note: this string must come before all other
whitespace version tags, if it is present, for backwards
compatibility)</li>
<li>"\x20\x20\x09\x09\x20\x20\x09\x20" to indicate a willingness to use
OTR version 2 with Bob</li>
<li>"\x20\x20\x09\x09\x20\x20\x09\x09" to indicate a willingness to use
OTR version 3 with Bob</li>
</ul>
<p>If Bob is willing to use OTR with Alice (with a protocol version that
Alice has offered), he should start the AKE. On the other hand, if
Alice receives a plaintext message from Bob (rather than an initiation
of the AKE), she should stop sending him the whitespace tag.</p>
<h4>OTR Error Messages</h4>
<p>Any message containing the string "?OTR Error:" is an OTR Error
Message. The following part of the message should contain
human-readable details of the error.</p>
<h3>Encoded messages</h3>
<p>This section describes the byte-level format of the base-64 encoded
binary OTR messages. The binary form of each of the messages is
described below. To transmit one of these messages, construct the ASCII
string consisting of the five bytes "?OTR:", followed by the base-64
encoding of the binary form of the message, followed by the byte
".".</p>
<p>For the Diffie-Hellman group computations, the group is the one
defined in RFC 3526 with 1536-bit modulus (hex, big-endian):</p>
<blockquote><pre>
FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
670C354E 4ABC9804 F1746C08 CA237327 FFFFFFFF FFFFFFFF
</pre></blockquote>
<p>and a generator (g) of 2. Note that this means that whenever you see a
Diffie-Hellman exponentiation in this document, it always means that the
exponentiation is done modulo the above 1536-bit number.</p>
<h4>Data types</h4>
<dl>
<dt>Bytes (BYTE):</dt>
<dd> 1 byte unsigned value</dd>
<dt>Shorts (SHORT):</dt>
<dd> 2 byte unsigned value, big-endian</dd>
<dt>Ints (INT):</dt>
<dd> 4 byte unsigned value, big-endian</dd>
<dt>Multi-precision integers (MPI):</dt>
<dd> 4 byte unsigned len, big-endian
<br /> len byte unsigned value, big-endian
<br /> (MPIs must use the minimum-length encoding; i.e. no leading 0x00
bytes. This is important when calculating public key
fingerprints.)</dd>
<dt>Opaque variable-length data (DATA):</dt>
<dd> 4 byte unsigned len, big-endian
<br /> len byte data</dd>
<dt>Initial CTR-mode counter value (CTR):</dt>
<dd> 8 bytes data</dd>
<dt>Message Authentication Code (MAC):</dt>
<dd> 20 bytes MAC data</dd>
</dl>
<h4>Public keys, signatures, and fingerprints</h4>
<p>OTR users have long-lived public keys that they use for
authentication (but <em>not</em> encryption). The current version of
the OTR protocol only supports DSA public keys, but there is a key type
marker for future extensibility.</p>
<dl>
<dt>OTR public authentication DSA key (PUBKEY):</dt>
<dd>Pubkey type (SHORT)
<ul class="note"><li>DSA public keys have type 0x0000</li></ul>
p (MPI)
<br />q (MPI)
<br />g (MPI)
<br />y (MPI)
<ul class="note"><li>(p,q,g,y) are the DSA public key parameters</li></ul>
</dd>
</dl>
<p>OTR public keys are used to generate <b>signatures</b>; different
types of keys produce signatures in different formats. The format for a
signature made by a DSA public key is as follows:</p>
<dl>
<dt>DSA signature (SIG):</dt>
<dd> (len is the length of the DSA public parameter q, which in
current implementations must be 20 bytes, or 160 bits)
<br /> len byte unsigned r, big-endian
<br /> len byte unsigned s, big-endian</dd>
</dl>
<p>OTR public keys have <b>fingerprints</b>, which are hex strings that
serve as identifiers for the public key. The fingerprint is calculated
by taking the SHA-1 hash of the byte-level representation of the public
key. However, there is an exception for backwards compatibility: if the
pubkey type is 0x0000, those two leading 0x00 bytes are omitted from the
data to be hashed. The encoding assures that, assuming the hash
function itself has no useful collisions, and DSA keys have length less
than 524281 bits (500 times larger than most DSA keys), no two public
keys will have the same fingerprint.</p>
<h4>Instance Tags</h4>
<p>Clients include instance tags in all OTR version 3 messages. Instance
tags are 32-bit values that are intended to be persistent. If the same
client is logged into the same account from multiple locations, the
intention is that the client will have different instance tags at each
location. As shown below, OTR version 3 messages (fragmented and
unfragmented) include the source and destination instance tags. If a client
receives a message that lists a destination instance tag different from its
own, the client should discard the message.</p>
<p>The smallest valid instance tag is 0x00000100. It is appropriate to set the
destination instance tag to '0' when an actual destination instance tag is
not known at the time the message is prepared. If a client receives a
message with the sender instance tag set to less than 0x00000100, it should
discard the message. Similarly, if a client receives a message with the
recipient instance tag set to greater than 0 but less than 0x00000100, it
should discard the message.
</p>
<p>This avoids an issue on IM networks that always relay all messages to
all sessions of a client who is logged in multiple times. In this
situation, OTR clients can attempt to establish an OTR session indefinitely
if there are interleaving messages from each of the sessions.</p>
<h4>D-H Commit Message</h4>
<p>This is the first message of the AKE. Bob sends it to Alice to
commit to a choice of D-H encryption key (but the key itself is not yet
revealed). This allows the secure session id to be much shorter than in
OTR version 1, while still preventing a man-in-the-middle attack on
it.</p>
<dl>
<dt>Protocol version (SHORT)</dt>
<dd>The version number of this protocol is 0x0003.</dd>
<dt>Message type (BYTE)</dt>
<dd>The D-H Commit Message has type 0x02.</dd>
<dt>Sender Instance tag (INT)</dt>
<dd>The instance tag of the person sending this message.</dd>
<dt>Receiver Instance tag (INT)</dt>
<dd>The instance tag of the intended recipient.
For a commit message this will often be 0, since the other party
may not have identified their instance tag yet.</dd>
<dt>Encrypted g<sup>x</sup> (DATA)</dt>
<dd>Produce this field as follows:
<ul>
<li>Choose a random value r (128 bits)</li>
<li>Choose a random value x (at least 320 bits)</li>
<li>Serialize g<sup>x</sup> as an MPI, gxmpi. [gxmpi will probably be
196 bytes long, starting with "\x00\x00\x00\xc0".]</li>
<li>Encrypt gxmpi using AES128-CTR, with key r and initial counter value
0. The result will be the same length as gxmpi.</li>
<li>Encode this encrypted value as the DATA field.</li>
</ul></dd>
<dt>Hashed g<sup>x</sup> (DATA)</dt>
<dd>This is the SHA256 hash of gxmpi.</dd>
</dl>
<h4>D-H Key Message</h4>
<p>This is the second message of the AKE. Alice sends it to Bob, and it
simply consists of Alice's D-H encryption key.</p>
<dl>
<dt>Protocol version (SHORT)</dt>
<dd>The version number of this protocol is 0x0003.</dd>
<dt>Message type (BYTE)</dt>
<dd>The D-H Key Message has type 0x0a.</dd>
<dt>Sender Instance tag (INT)</dt>
<dd>The instance tag of the person sending this message.</dd>
<dt>Receiver Instance tag (INT)</dt>
<dd>The instance tag of the intended recipient.</dd>
<dt>g<sup>y</sup> (MPI)</dt>
<dd>Choose a random value y (at least 320 bits), and calculate
g<sup>y</sup>.</dd>
</dl>
<h4>Reveal Signature Message</h4>
<p>This is the third message of the AKE. Bob sends it to Alice,
revealing his D-H encryption key (and thus opening an encrypted
channel), and also authenticating himself (and the parameters of the
channel, preventing a man-in-the-middle attack on the channel itself) to
Alice.</p>
<dl>
<dt>Protocol version (SHORT)</dt>
<dd>The version number of this protocol is 0x0003.</dd>
<dt>Message type (BYTE)</dt>
<dd>The Reveal Signature Message has type 0x11.</dd>
<dt>Sender Instance tag (INT)</dt>
<dd>The instance tag of the person sending this message.</dd>
<dt>Receiver Instance tag (INT)</dt>
<dd>The instance tag of the intended recipient.</dd>
<dt>Revealed key (DATA)</dt>
<dd>This is the value r picked earlier.</dd>
<dt>Encrypted signature (DATA)</dt>
<dd>This field is calculated as follows:
<ul>
<li>Compute the Diffie-Hellman shared secret s.</li>
<li>Use s to compute an AES key c and two MAC keys m1 and m2, as specified below.</li>
<li>Select keyid<sub>B</sub>, a serial number for the D-H key computed
earlier. It is an INT, and must be greater than 0.</li>
<li>Compute the 32-byte value M<sub>B</sub> to be the SHA256-HMAC of the
following data, using the key m1:<dl>
<dt>g<sup>x</sup> (MPI)</dt>
<dt>g<sup>y</sup> (MPI)</dt>
<dt>pub<sub>B</sub> (PUBKEY)</dt>
<dt>keyid<sub>B</sub> (INT)</dt>
</dl></li>
<li>Let X<sub>B</sub> be the following structure:<dl>
<dt>pub<sub>B</sub> (PUBKEY)</dt>
<dt>keyid<sub>B</sub> (INT)</dt>
<dt>sig<sub>B</sub>(M<sub>B</sub>) (SIG)</dt>
<dd>This is the signature, using the private part of the key
pub<sub>B</sub>, of the 32-byte M<sub>B</sub> (which does not need to be
hashed again to produce the signature).</dd>
</dl></li>
<li>Encrypt X<sub>B</sub> using AES128-CTR with key c and initial
counter value 0.</li>
<li>Encode this encrypted value as the DATA field.</li>
</ul></dd>
<dt>MAC'd signature (MAC)</dt>
<dd>This is the SHA256-HMAC-160 (that is, the first 160 bits of the
SHA256-HMAC) of the encrypted signature field (including the four-byte
length), using the key m2.</dd>
</dl>
<h4>Signature Message</h4>
<p>This is the final message of the AKE. Alice sends it to Bob,
authenticating herself and the channel parameters to him.</p>
<dl>
<dt>Protocol version (SHORT)</dt>
<dd>The version number of this protocol is 0x0003.</dd>
<dt>Message type (BYTE)</dt>
<dd>The Signature Message has type 0x12.</dd>
<dt>Sender Instance tag (INT)</dt>
<dd>The instance tag of the person sending this message.</dd>
<dt>Receiver Instance tag (INT)</dt>
<dd>The instance tag of the intended recipient.</dd>
<dt>Encrypted signature (DATA)</dt>
<dd>This field is calculated as follows:
<ul>
<li>Compute the Diffie-Hellman shared secret s.</li>
<li>Use s to compute an AES key c' and two MAC keys m1' and m2', as specified below.</li>
<li>Select keyid<sub>A</sub>, a serial number for the D-H key computed
earlier. It is an INT, and must be greater than 0.</li>
<li>Compute the 32-byte value M<sub>A</sub> to be the SHA256-HMAC of the
following data, using the key m1':<dl>
<dt>g<sup>y</sup> (MPI)</dt>
<dt>g<sup>x</sup> (MPI)</dt>
<dt>pub<sub>A</sub> (PUBKEY)</dt>
<dt>keyid<sub>A</sub> (INT)</dt>
</dl></li>
<li>Let X<sub>A</sub> be the following structure:<dl>
<dt>pub<sub>A</sub> (PUBKEY)</dt>
<dt>keyid<sub>A</sub> (INT)</dt>
<dt>sig<sub>A</sub>(M<sub>A</sub>) (SIG)</dt>
<dd>This is the signature, using the private part of the key
pub<sub>A</sub>, of the 32-byte M<sub>A</sub> (which does not need to be
hashed again to produce the signature).</dd>
</dl></li>
<li>Encrypt X<sub>A</sub> using AES128-CTR with key c' and initial
counter value 0.</li>
<li>Encode this encrypted value as the DATA field.</li>
</ul></dd>
<dt>MAC'd signature (MAC)</dt>
<dd>This is the SHA256-HMAC-160 (that is, the first 160 bits of the
SHA256-HMAC) of the encrypted signature field (including the four-byte
length), using the key m2'.</dd>
</dl>
<h4>Data Message</h4>
<p>This message is used to transmit a private message to the
correspondent. It is also used to reveal old MAC keys.</p>
<p>The plaintext message (either before encryption, or after decryption)
consists of a human-readable message (encoded in UTF-8, optionally with
HTML markup), optionally followed by:</p>
<ul>
<li>a single NUL (a BYTE with value 0x00), <b>and</b></li>
<li>zero or more TLV (type/length/value) records (with no padding
between them)</li>
</ul>
<p>Each TLV record is of the form:</p>
<dl>
<dt>Type (SHORT)</dt>
<dd>The type of this record. Records with unrecognized types should be
ignored.</dd>
<dt>Length (SHORT)</dt>
<dd>The length of the following field</dd>
<dt>Value (len BYTEs) [where len is the value of the Length field]</dt>
<dd>Any pertinent data for the record type.</dd>
</dl>
<p>Some TLV examples:</p>
<dl>
<dt>\x00\x01\x00\x00</dt>
<dd>A TLV of type 1, containing no data</dd>
<dt>\x00\x00\x00\x05\x68\x65\x6c\x6c\x6f</dt>
<dd>A TLV of type 0, containing the value "hello"</dd>
</dl>
<p>The currently defined TLV record types are:</p>
<dl>
<dt>Type 0: Padding</dt>
<dd>The value may be an arbitrary amount of data, which should be
ignored. This type can be used to disguise the length of the plaintext
message.</dd>
<dt>Type 1: Disconnected</dt>
<dd>If the user requests to close the private connection, you may send a
message (possibly with empty human-readable part) containing a record
with this TLV type just before you discard the session keys, and
transition to MSGSTATE_PLAINTEXT (see below). If you receive a TLV
record of this type, you should transition to MSGSTATE_FINISHED (see
below), and inform the user that his correspondent has closed his end of
the private connection, and the user should do the same.</dd>
<dt>Type 2: SMP Message 1</dt>
<dd>The value represents an initiating message of the Socialist
Millionaires' Protocol, described below.</dd>
<dt>Type 3: SMP Message 2</dt>
<dd>The value represents the second message in an instance of SMP.</dd>
<dt>Type 4: SMP Message 3</dt>
<dd>The value represents the third message in an instance of SMP.</dd>
<dt>Type 5: SMP Message 4</dt>
<dd>The value represents the final message in an instance of SMP.</dd>
<dt>Type 6: SMP Abort Message</dt>
<dd>If the user cancels SMP prematurely or encounters an error in the
protocol and cannot continue, you may send a message (possibly with empty
human-readable part) with this TLV type to instruct the other party's
client to abort the protocol. The associated length should be zero and
the associated value should be empty. If you receive a TLV of this type,
you should change the SMP state to SMP_EXPECT1 (see below).</dd>
<dt>Type 7: SMP Message 1Q</dt>
<dd>Like a SMP Message 1, but whose value begins with a NUL-terminated
user-specified question.</dd>
<dt>Type 8: Extra symmetric key</dt>
<dd>If you wish to use the extra symmetric key, compute it yourself as
outlined in the section "Extra symmetric key", below. Then send this
type 8 TLV to your buddy to indicate that you'd like to use the extra
symmetric key for something. The value of the TLV begins with a 4-byte
indication of what this symmetric key will be used for (file transfer,
voice encryption, etc.). After that, the contents are use-specific
(which file, etc.). There are no currently defined uses. Note that the
value of the key itself is <em>not</em> placed into the TLV; your buddy
will compute it on his/her own.
</dd>
</dl>
<p>SMP Message TLVs (types 2-5) all carry data sharing the same general
format:</p>
<dl>
<dt>MPI count (INT)</dt>
<dd>The number of MPIs contained in the remainder of the TLV.</dd>
<dt>MPI 1 (MPI)</dt>
<dd>The first MPI of the TLV, serialized into a byte array.</dd>
<dt>MPI 2 (MPI)</dt>
<dd>The second MPI of the TLV, serialized into a byte array.</dd>
<dt>etc.</dt>
</dl>
<p>There should be as many MPIs as declared in the MPI count field. For
the exact MPIs passed for each SMP TLV, see the SMP state machine
below.</p>
<p>A message with an empty human-readable part (the plaintext is of zero
length, or starts with a NUL) is a "heartbeat" packet, and should not
be displayed to the user. (But it's still useful to effect key
rotations.)</p>
<p>Data Message format:</p>
<dl>
<dt>Protocol version (SHORT)</dt>
<dd>The version number of this protocol is 0x0003.</dd>
<dt>Message type (BYTE)</dt>
<dd>The Data Message has type 0x03.</dd>
<dt>Sender Instance tag (INT)</dt>
<dd>The instance tag of the person sending this message.</dd>
<dt>Receiver Instance tag (INT)</dt>
<dd>The instance tag of the intended recipient.</dd>
<dt>Flags (BYTE)</dt>
<dd>The bitwise-OR of the flags for this message. Usually you should
set this to 0x00. The only currently defined flag is:<dl>
<dt>IGNORE_UNREADABLE (0x01)</dt>
<dd>If you receive a Data Message with this flag set, and you are unable
to decrypt the message or verify the MAC (because, for example, you
don't have the right keys), just ignore the message instead of producing
some kind of error or notification to the user.</dd>
</dl></dd>
<dt>Sender keyid (INT)</dt>
<dd>Must be strictly greater than 0, and increment by 1 with each key
change</dd>
<dt>Recipient keyid (INT)</dt>
<dd>Must therefore be strictly greater than 0, as the receiver has no
key with id 0.
<br />The sender and recipient keyids are those used to encrypt and MAC
this message.</dd>
<dt>DH y (MPI)</dt>
<dd>The *next* [i.e. sender_keyid+1] public key for the sender</dd>
<dt>Top half of counter init (CTR)</dt>
<dd>This should monotonically increase (as a big-endian value) for
each message sent with the same (sender keyid, recipient keyid)
pair, and must not be all 0x00.</dd>
<dt>Encrypted message (DATA)</dt>
<dd>Using the appropriate encryption key (see below) derived from the
sender's and recipient's DH public keys (with the keyids given in
this message), perform AES128 counter-mode (CTR) encryption of the
message. The initial counter is a 16-byte value whose first 8
bytes are the above "top half of counter init" value, and whose
last 8 bytes are all 0x00. Note that counter mode does not change
the length of the message, so no message padding needs to be done.
If you *want* to do message padding (to disguise the length of
your message), use the above TLV of type 0.</dd>
<dt>Authenticator (MAC)</dt>
<dd>The SHA1-HMAC, using the appropriate MAC key (see below) of everything
from the Protocol version to the end of the encrypted message</dd>
<dt>Old MAC keys to be revealed (DATA)</dt>
<dd>See "Revealing MAC Keys", below.</dd>
</dl>
<h3>Socialist Millionaires' Protocol (SMP)</h3>
<p>The Socialist Millionaires' Protocol allows two parties with secret
information x and y respectively to check whether (x==y) without revealing
any additional information about the secrets. The protocol used by OTR is
based on the work of Boudot, Schoenmakers and Traore (2001). A full
justification for its use in OTR is made by Alexander and Goldberg,
in a paper published in 2007. The following is a technical account
of what is transmitted during the course of the protocol.</p>
<h4>Secret information</h4>
<p>The secret information x and y compared during this protocol contains
not only information entered by the users, but also information unique to
the conversation in which SMP takes place. Specifically, the format is:</p>
<dl>
<dt>Version (BYTE)</dt>
<dd>The version of SMP used. The version described here is 1.</dd>
<dt>Initiator fingerprint (20 BYTEs)</dt>
<dd>The fingerprint that the party initiating SMP is using in
the current conversation.</dd>
<dt>Responder fingerprint (20 BYTEs)</dt>
<dd>The fingerprint that the party that did not initiate SMP is
using in the current conversation.</dd>
<dt>Secure Session ID</dt>
<dd>The ssid described below.</dd>
<dt>User-specified secret</dt>
<dd>The input string given by the user at runtime.</dd>
</dl>
<p>Then the SHA256 hash of the above is taken, and the digest becomes the
actual secret (x or y) to be used in SMP. The additional fields insure
that not only do both parties know the same secret input string, but no
man-in-the-middle is capable of reading their communication either.</p>
<h3>The SMP state machine</h3>
<p>Whenever the OTR message state machine has MSGSTATE_ENCRYPTED set
(see below), the SMP state machine may progress. If at any point
MSGSTATE_ENCRYPTED becomes unset, SMP must abandon its state and return
to its initial setup. The SMP state consists of one main variable, as
well as information from the partial computations at each protocol step.</p>
<h4>Expected Message</h4>
<p>This main state variable for SMP controls what SMP-specific TLVs will
be accepted. This variable has no effect on type 0 or type 1 TLVs, which
are always allowed. smpstate can take one of four values:</p>
<dl>
<dt>SMPSTATE_EXPECT1</dt>
<dd>This state indicates that only type 2 (SMP message 1) and type 7
(SMP message 1Q) TLVs should be accepted. This is the default state when
SMP has not yet begun. This state is also reached whenever an error
occurs or SMP is aborted, and the protocol must be restarted from the
beginning.</dd>
<dt>SMPSTATE_EXPECT2</dt>
<dd>This state indicates that only type 3 TLVs (SMP message 2) should
be accepted.</dd>
<dt>SMPSTATE_EXPECT3</dt>
<dd>This state indicates that only type 4 TLVs (SMP message 3) should
be accepted.</dd>
<dt>SMPSTATE_EXPECT4</dt>
<dd>This state indicates that only type 5 TLVs (SMP message 4) should
be accepted.</dd>
</dl>
<h4>State Transitions</h4>
<p>There are 7 actions that an OTR client must handle:</p>
<ul>
<li>Received TLVs:
<ul>
<li>SMP Message 1</li>
<li>SMP Message 2</li>
<li>SMP Message 3</li>
<li>SMP Message 4</li>
<li>SMP Abort Message</li>
</ul></li>
<li>User actions:</li>
<ul>
<li>User requests to begin SMP</li>
<li>User requests to abort SMP</li>
</ul></li>
</ul>
<p>The following sections outline what is to be done in each case. They
all assume that MSGSTATE_ENCRYPTED is set. For simplicity, they also
assume that Alice has begun SMP, and Bob is responding to her.</p>
<h4>SMP Hash function</h4>
<p>In the following actions, there are many places where a SHA256 hash of
an integer followed by one or two MPIs is taken. The input to this hash
function is:</p>
<dl>
<dt>Version (BYTE)</dt>
<dd>This distinguishes calls to the hash function at different points in
the protocol, to prevent Alice from replaying Bob's zero knowledge proofs
or vice versa.</dd>
<dt>First MPI (MPI)</dt>
<dd>The first MPI given as input, serialized in the usual way.</dd>
<dt>Second MPI (MPI)</dt>
<dd>The second MPI given as input, if present, serialized in the usual way.
If only one MPI is given as input, this field is simply omitted.</dd>
</dl>
<h4>Receiving a type 2 TLV (SMP message 1)</h4>
<p>SMP message 1 is sent by Alice to begin a DH exchange to determine two
new generators, g<sub>2</sub> and g<sub>3</sub>. It contains the
following mpi values:</p>
<dl>
<dt>g<sub>2a</sub></dt>
<dd>Alice's half of the DH exchange to determine g<sub>2</sub>.</dd>
<dt>c2, D2</dt>
<dd>A zero-knowledge proof that Alice knows the exponent associated with
her transmitted value g<sub>2a</sub>.</dd>
<dt>g<sub>3a</sub></dt>
<dd>Alice's half of the DH exchange to determine g<sub>3</sub>.</dd>
<dt>c3, D3</dt>
<dd>A zero-knowledge proof that Alice knows the exponent associated with
her transmitted value g<sub>3a</sub>.</dd>
</dl>
<p>A type 7 (SMP Message 1Q) TLV is the same as the above, but is
preceded by a user-specified question, which is associated with the
user-specified portion of the secret.</p>
<p>When Bob receives this TLV he should do:</p>
<dl>
<dt>If smpstate is not SMPSTATE_EXPECT1:</dt>
<dd>Set smpstate to SMPSTATE_EXPECT1 and send a type 6 TLV (SMP abort)
to Alice.</dd>
<dt>If smpstate is SMPSTATE_EXPECT1:</dt>
<dd>Verify Alice's zero-knowledge proofs for g<sub>2a</sub> and
g<sub>3a</sub>:
<ol>
<li>Check that both g<sub>2a</sub> and g<sub>3a</sub> are >= 2 and
<= modulus-2.</li>
<li>Check that c2 = SHA256(1, g<sub>1</sub><sup>D2</sup>
g<sub>2a</sub><sup>c2</sup>).</li>
<li>Check that c3 = SHA256(2, g<sub>1</sub><sup>D3</sup>
g<sub>3a</sub><sup>c3</sup>).</li>
</ol>
Create a type 3 TLV (SMP message 2) and send it to Alice:
<ol>
<li>Determine Bob's secret input y, which is to be compared to Alice's
secret x.</li>
<li>Pick random exponents b<sub>2</sub> and b<sub>3</sub>.
These will used during the DH exchange to pick generators.</li>
<li>Pick random exponents r2, r3, r4, r5 and r6.
These will be used to add a blinding factor to the final results, and
to generate zero-knowledge proofs that this message was created honestly.</li>
<li>Compute g<sub>2b</sub> = g<sub>1</sub><sup>b<sub>2</sub></sup> and
g<sub>3b</sub> = g<sub>1</sub><sup>b<sub>3</sub></sup></li>
<li>Generate a zero-knowledge proof that the exponent b<sub>2</sub> is
known by setting c2 = SHA256(3, g<sub>1</sub><sup>r2</sup>) and
D2 = r2 - b<sub>2</sub> c2 mod q. In the zero-knowledge proofs the D values
are calculated modulo q = (p - 1) / 2, where p is the same 1536-bit prime
as elsewhere. The random exponents are 1536-bit numbers.</li>
<li>Generate a zero-knowledge proof that the exponent b<sub>3</sub> is
known by setting c3 = SHA256(4, g<sub>1</sub><sup>r3</sup>) and
D3 = r3 - b<sub>3</sub> c3 mod q.</li>
<li>Compute g<sub>2</sub> = g<sub>2a</sub><sup>b<sub>2</sub></sup> and
g<sub>3</sub> = g<sub>3a</sub><sup>b<sub>3</sub></sup></li>
<li>Compute P<sub>b</sub> = g<sub>3</sub><sup>r4</sup> and
Q<sub>b</sub> = g<sub>1</sub><sup>r4</sup> g<sub>2</sub><sup>y</sup></li>
<li>Generate a zero-knowledge proof that P<sub>b</sub> and Q<sub>b</sub>
were created according to the protocol by setting
cP = SHA256(5, g<sub>3</sub><sup>r5</sup>, g<sub>1</sub><sup>r5</sup>
g<sub>2</sub><sup>r6</sup>), D5 = r5 - r4 cP mod q and D6 = r6 - y cP mod q.</li>
<li>Store the values of g<sub>3a</sub>, g<sub>2</sub>, g<sub>3</sub>,
b<sub>3</sub>, P<sub>b</sub> and Q<sub>b</sub> for use later in the
protocol.</li>
<li>Send Alice a type 3 TLV (SMP message 2) containing g<sub>2b</sub>,
c2, D2, g<sub>3b</sub>, c3, D3, P<sub>b</sub>, Q<sub>b</sub>, cP, D5
and D6, in that order.</li>
</ol>
Set smpstate to SMPSTATE_EXPECT3.</dd>
</dl>
<h4>Receiving a type 3 TLV (SMP message 2)</h4>
<p>SMP message 2 is sent by Bob to complete the DH exchange to
determine the new generators, g<sub>2</sub> and g<sub>3</sub>.
It also begins the construction of the values used in the final
comparison of the protocol. It contains the following mpi values:</p>
<dl>
<dt>g<sub>2b</sub></dt>
<dd>Bob's half of the DH exchange to determine g<sub>2</sub>.</dd>
<dt>c2, D2</dt>
<dd>A zero-knowledge proof that Bob knows the exponent associated with
his transmitted value g<sub>2b</sub>.</dd>
<dt>g<sub>3b</sub></dt>
<dd>Bob's half of the DH exchange to determine g<sub>3</sub>.</dd>
<dt>c3, D3</dt>
<dd>A zero-knowledge proof that Bob knows the exponent associated with
his transmitted value g<sub>3b</sub>.</dd>
<dt>P<sub>b</sub>, Q<sub>b</sub></dt>
<dd>These values are used in the final comparison to determine if Alice
and Bob share the same secret.</dd>
<dt>cP, D5, D6</dt>
<dd>A zero-knowledge proof that P<sub>b</sub> and Q<sub>b</sub> were
created according to the protcol given above.</dd>
</dl>
<p>When Alice receives this TLV she should do:</p>
<dl>
<dt>If smpstate is not SMPSTATE_EXPECT2:</dt>
<dd>Set smpstate to SMPSTATE_EXPECT1 and send a type 6 TLV (SMP abort)
to Bob.</dd>
<dt>If smpstate is SMPSTATE_EXPECT2:</dt>
<dd>Verify Bob's zero-knowledge proofs for g<sub>2b</sub>,
g<sub>3b</sub>, P<sub>b</sub> and Q<sub>b</sub>:
<ol>
<li>Check that g<sub>2b</sub>,
g<sub>3b</sub>, P<sub>b</sub> and Q<sub>b</sub> are >= 2 and
<= modulus-2.</li>
<li>Check that c2 = SHA256(3, g<sub>1</sub><sup>D2</sup>
g<sub>2b</sub><sup>c2</sup>).</li>
<li>Check that c3 = SHA256(4, g<sub>1</sub><sup>D3</sup>
g<sub>3b</sub><sup>c3</sup>).</li>
<li>Check that cP = SHA256(5, g<sub>3</sub><sup>D5</sup>
P<sub>b</sub><sup>cP</sup>, g<sub>1</sub><sup>D5</sup>
g<sub>2</sub><sup>D6</sup> Q<sub>b</sub><sup>cP</sup>).</li>
</ol>
Create a type 4 TLV (SMP message 3) and send it to Bob:
<ol>
<li>Pick random exponents r4, r5, r6 and r7.
These will be used to add a blinding factor to the final results, and
to generate zero-knowledge proofs that this message was created honestly.</li>
<li>Compute g<sub>2</sub> = g<sub>2b</sub><sup>a<sub>2</sub></sup> and
g<sub>3</sub> = g<sub>3b</sub><sup>a<sub>3</sub></sup></li>
<li>Compute P<sub>a</sub> = g<sub>3</sub><sup>r4</sup> and
Q<sub>a</sub> = g<sub>1</sub><sup>r4</sup> g<sub>2</sub><sup>x</sup></li>
<li>Generate a zero-knowledge proof that P<sub>a</sub> and Q<sub>a</sub>
were created according to the protocol by setting
cP = SHA256(6, g<sub>3</sub><sup>r5</sup>, g<sub>1</sub><sup>r5</sup>
g<sub>2</sub><sup>r6</sup>), D5 = r5 - r4 cP mod q and D6 = r6 - x cP mod q.</li>
<li>Compute R<sub>a</sub> = (Q<sub>a</sub> / Q<sub>b</sub>)
<sup>a<sub>3</sub></sup></li>
<li>Generate a zero-knowledge proof that R<sub>a</sub> was created
according to the protocol by setting cR = SHA256(7, g<sub>1</sub><sup>r7</sup>,
(Q<sub>a</sub> / Q<sub>b</sub>)<sup>r7</sup>) and
D7 = r7 - a<sub>3</sub> cR mod q.</li>
<li>Store the values of g<sub>3b</sub>, (P<sub>a</sub> / P<sub>b</sub>),
(Q<sub>a</sub> / Q<sub>b</sub>) and R<sub>a</sub> for use later in the
protocol.</li>
<li>Send Bob a type 4 TLV (SMP message 3) containing P<sub>a</sub>,
Q<sub>a</sub>, cP, D5, D6, R<sub>a</sub>, cR and D7 in that order.</li>
</ol>
Set smpstate to SMPSTATE_EXPECT4.</dd>
</dl>
<h4>Receiving a type 4 TLV (SMP message 3)</h4>
<p>SMP message 3 is Alice's final message in the SMP exchange. It
has the last of the information required by Bob to determine if x = y.
It contains the following mpi values:</p>
<dl>
<dt>P<sub>a</sub>, Q<sub>a</sub></dt>
<dd>These values are used in the final comparison to determine if Alice
and Bob share the same secret.</dd>
<dt>cP, D5, D6</dt>
<dd>A zero-knowledge proof that P<sub>a</sub> and Q<sub>a</sub> were
created according to the protcol given above.</dd>
<dt>R<sub>a</sub></dt>
<dd>This value is used in the final comparison to determine if Alice
and Bob share the same secret.</dd>
<dt>cR, D7</dt>
<dd>A zero-knowledge proof that R<sub>a</sub> was
created according to the protcol given above.</dd>
<dt>
</dl>
<p>When Bob receives this TLV he should do:</p>
<dl>
<dt>If smpstate is not SMPSTATE_EXPECT3:</dt>
<dd>Set smpstate to SMPSTATE_EXPECT1 and send a type 6 TLV (SMP abort)
to Bob.</dd>
<dt>If smpstate is SMPSTATE_EXPECT3:</dt>
<dd>Verify Alice's zero-knowledge proofs for P<sub>a</sub>, Q<sub>a</sub>
and R<sub>a</sub>:
<ol>
<li>Check that P<sub>a</sub>, Q<sub>a</sub> and R<sub>a</sub> are >= 2 and
<= modulus-2.</li>
<li>Check that cP = SHA256(6, g<sub>3</sub><sup>D5</sup>
P<sub>a</sub><sup>cP</sup>, g<sub>1</sub><sup>D5</sup> g<sub>2</sub><sup>D6</sup>
Q<sub>a</sub><sup>cP</sup>).</li>
<li>Check that cR = SHA256(7, g<sub>1</sub><sup>D7</sup>
g<sub>3a</sub><sup>cR</sup>, (Q<sub>a</sub> / Q<sub>b</sub>)<sup>D7</sup>
R<sub>a</sub><sup>cR</sup>).</li>
</ol>
Create a type 5 TLV (SMP message 4) and send it to Alice:
<ol>
<li>Pick a random exponent r7.
This will be used to generate Bob's final zero-knowledge proof that
this message was created honestly.</li>
<li>Compute R<sub>b</sub> = (Q<sub>a</sub> / Q<sub>b</sub>)
<sup>b<sub>3</sub></sup></li>
<li>Generate a zero-knowledge proof that R<sub>b</sub> was created
according to the protocol by setting cR = SHA256(8, g<sub>1</sub><sup>r7</sup>,
(Q<sub>a</sub> / Q<sub>b</sub>)<sup>r7</sup>) and
D7 = r7 - b<sub>3</sub> cR mod q.</li>
<li>Send Alice a type 5 TLV (SMP message 4) containing R<sub>b</sub>,
cR and D7 in that order.</li>
</ol>
Check whether the protocol was successful:
<ol>
<li>Compute R<sub>ab</sub> = R<sub>a</sub><sup>b<sub>3</sub></sup>.</li>
<li>Determine if x = y by checking the equivalent condition that
(P<sub>a</sub> / P<sub>b</sub>) = R<sub>ab</sub>.</li>
</ol>
Set smpstate to SMPSTATE_EXPECT1, as no more messages are expected from
Alice.</dd>
</dl>
<h4>Receiving a type 5 TLV (SMP message 4)</h4>
<p>SMP message 4 is Bob's final message in the SMP exchange. It