1 /* Copyright (c) 2016, Google Inc.
2 *
3 * Permission to use, copy, modify, and/or distribute this software for any
4 * purpose with or without fee is hereby granted, provided that the above
5 * copyright notice and this permission notice appear in all copies.
6 *
7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
10 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
14
15 #include <openssl/curve25519.h>
16
17 #include <assert.h>
18 #include <string.h>
19
20 #include <openssl/bytestring.h>
21 #include <openssl/mem.h>
22 #include <openssl/rand.h>
23 #include <openssl/sha.h>
24
25 #include "../internal.h"
26 #include "../../third_party/fiat/internal.h"
27
28
29 // The following precomputation tables are for the following
30 // points used in the SPAKE2 protocol.
31 //
32 // N:
33 // x: 49918732221787544735331783592030787422991506689877079631459872391322455579424
34 // y: 54629554431565467720832445949441049581317094546788069926228343916274969994000
35 // encoded: 10e3df0ae37d8e7a99b5fe74b44672103dbddcbd06af680d71329a11693bc778
36 //
37 // M:
38 // x: 31406539342727633121250288103050113562375374900226415211311216773867585644232
39 // y: 21177308356423958466833845032658859666296341766942662650232962324899758529114
40 // encoded: 5ada7e4bf6ddd9adb6626d32131c6b5c51a1e347a3478f53cfcf441b88eed12e
41 //
42 // These points and their precomputation tables are generated with the
43 // following Python code. For a description of the precomputation table,
44 // see curve25519.c in this directory.
45 //
46 // Exact copies of the source code are kept in bug 27296743.
47
48 /*
49 import hashlib
50 import ed25519 as E # http://ed25519.cr.yp.to/python/ed25519.py
51
52 SEED_N = 'edwards25519 point generation seed (N)'
53 SEED_M = 'edwards25519 point generation seed (M)'
54
55 def genpoint(seed):
56 v = hashlib.sha256(seed).digest()
57 it = 1
58 while True:
59 try:
60 x,y = E.decodepoint(v)
61 except Exception, e:
62 print e
63 it += 1
64 v = hashlib.sha256(v).digest()
65 continue
66 print "Found in %d iterations:" % it
67 print " x = %d" % x
68 print " y = %d" % y
69 print " Encoded (hex)"
70 print E.encodepoint((x,y)).encode('hex')
71 return (x,y)
72
73 def gentable(P):
74 t = []
75 for i in range(1,16):
76 k = ((i >> 3 & 1) * (1 << 192) +
77 (i >> 2 & 1) * (1 << 128) +
78 (i >> 1 & 1) * (1 << 64) +
79 (i & 1))
80 t.append(E.scalarmult(P, k))
81 return ''.join(E.encodeint(x) + E.encodeint(y) for (x,y) in t)
82
83 def printtable(table, name):
84 print "static const uint8_t %s[15 * 2 * 32] = {" % name,
85 for i in range(15 * 2 * 32):
86 if i % 12 == 0:
87 print "\n ",
88 print " 0x%02x," % ord(table[i]),
89 print "\n};"
90
91 if __name__ == "__main__":
92 print "Searching for N"
93 N = genpoint(SEED_N)
94 print "Generating precomputation table for N"
95 Ntable = gentable(N)
96 printtable(Ntable, "kSpakeNSmallPrecomp")
97
98 print "Searching for M"
99 M = genpoint(SEED_M)
100 print "Generating precomputation table for M"
101 Mtable = gentable(M)
102 printtable(Mtable, "kSpakeMSmallPrecomp")
103 */
104
105 static const uint8_t kSpakeNSmallPrecomp[15 * 2 * 32] = {
106 0x20, 0x1b, 0xc5, 0xb3, 0x43, 0x17, 0x71, 0x10, 0x44, 0x1e, 0x73, 0xb3,
107 0xae, 0x3f, 0xbf, 0x9f, 0xf5, 0x44, 0xc8, 0x13, 0x8f, 0xd1, 0x01, 0xc2,
108 0x8a, 0x1a, 0x6d, 0xea, 0x4d, 0x00, 0x5d, 0x6e, 0x10, 0xe3, 0xdf, 0x0a,
109 0xe3, 0x7d, 0x8e, 0x7a, 0x99, 0xb5, 0xfe, 0x74, 0xb4, 0x46, 0x72, 0x10,
110 0x3d, 0xbd, 0xdc, 0xbd, 0x06, 0xaf, 0x68, 0x0d, 0x71, 0x32, 0x9a, 0x11,
111 0x69, 0x3b, 0xc7, 0x78, 0x93, 0xf1, 0x57, 0x97, 0x6e, 0xf0, 0x6e, 0x45,
112 0x37, 0x4a, 0xf4, 0x0b, 0x18, 0x51, 0xf5, 0x4f, 0x67, 0x3c, 0xdc, 0xec,
113 0x84, 0xed, 0xd0, 0xeb, 0xca, 0xfb, 0xdb, 0xff, 0x7f, 0xeb, 0xa8, 0x23,
114 0x68, 0x87, 0x13, 0x64, 0x6a, 0x10, 0xf7, 0x45, 0xe0, 0x0f, 0x32, 0x21,
115 0x59, 0x7c, 0x0e, 0x50, 0xad, 0x56, 0xd7, 0x12, 0x69, 0x7b, 0x58, 0xf8,
116 0xb9, 0x3b, 0xa5, 0xbb, 0x4d, 0x1b, 0x87, 0x1c, 0x46, 0xa7, 0x17, 0x9d,
117 0x6d, 0x84, 0x45, 0xbe, 0x7f, 0x95, 0xd2, 0x34, 0xcd, 0x89, 0x95, 0xc0,
118 0xf0, 0xd3, 0xdf, 0x6e, 0x10, 0x4a, 0xe3, 0x7b, 0xce, 0x7f, 0x40, 0x27,
119 0xc7, 0x2b, 0xab, 0x66, 0x03, 0x59, 0xb4, 0x7b, 0xc7, 0xc7, 0xf0, 0x39,
120 0x9a, 0x33, 0x35, 0xbf, 0xcc, 0x2f, 0xf3, 0x2e, 0x68, 0x9d, 0x53, 0x5c,
121 0x88, 0x52, 0xe3, 0x77, 0x90, 0xa1, 0x27, 0x85, 0xc5, 0x74, 0x7f, 0x23,
122 0x0e, 0x93, 0x01, 0x3e, 0xe7, 0x2e, 0x2e, 0x95, 0xf3, 0x0d, 0xc2, 0x25,
123 0x25, 0x39, 0x39, 0x3d, 0x6e, 0x8e, 0x89, 0xbd, 0xe8, 0xbb, 0x67, 0x5e,
124 0x8c, 0x66, 0x8b, 0x63, 0x28, 0x1e, 0x4e, 0x74, 0x85, 0xa8, 0xaf, 0x0f,
125 0x12, 0x5d, 0xb6, 0x8a, 0x83, 0x1a, 0x77, 0x76, 0x5e, 0x62, 0x8a, 0xa7,
126 0x3c, 0xb8, 0x05, 0x57, 0x2b, 0xaf, 0x36, 0x2e, 0x10, 0x90, 0xb2, 0x39,
127 0xb4, 0x3e, 0x75, 0x6d, 0x3a, 0xa8, 0x31, 0x35, 0xc2, 0x1e, 0x8f, 0xc2,
128 0x79, 0x89, 0x35, 0x16, 0x26, 0xd1, 0xc7, 0x0b, 0x04, 0x1f, 0x1d, 0xf9,
129 0x9c, 0x05, 0xa6, 0x6b, 0xb5, 0x19, 0x5a, 0x24, 0x6d, 0x91, 0xc5, 0x31,
130 0xfd, 0xc5, 0xfa, 0xe7, 0xa6, 0xcb, 0x0e, 0x4b, 0x18, 0x0d, 0x94, 0xc7,
131 0xee, 0x1d, 0x46, 0x1f, 0x92, 0xb1, 0xb2, 0x4a, 0x2b, 0x43, 0x37, 0xfe,
132 0xc2, 0x15, 0x11, 0x89, 0xef, 0x59, 0x73, 0x3c, 0x06, 0x76, 0x78, 0xcb,
133 0xa6, 0x0d, 0x79, 0x5f, 0x28, 0x0b, 0x5b, 0x8c, 0x9e, 0xe4, 0xaa, 0x51,
134 0x9a, 0x42, 0x6f, 0x11, 0x50, 0x3d, 0x01, 0xd6, 0x21, 0xc0, 0x99, 0x5e,
135 0x1a, 0xe8, 0x81, 0x25, 0x80, 0xeb, 0xed, 0x5d, 0x37, 0x47, 0x30, 0x70,
136 0xa0, 0x4e, 0x0b, 0x43, 0x17, 0xbe, 0xb6, 0x47, 0xe7, 0x2a, 0x62, 0x9d,
137 0x5d, 0xa6, 0xc5, 0x33, 0x62, 0x9d, 0x56, 0x24, 0x9d, 0x1d, 0xb2, 0x13,
138 0xbc, 0x17, 0x66, 0x43, 0xd1, 0x68, 0xd5, 0x3b, 0x17, 0x69, 0x17, 0xa6,
139 0x06, 0x9e, 0x12, 0xb8, 0x7c, 0xd5, 0xaf, 0x3e, 0x21, 0x1b, 0x31, 0xeb,
140 0x0b, 0xa4, 0x98, 0x1c, 0xf2, 0x6a, 0x5e, 0x7c, 0x9b, 0x45, 0x8f, 0xb2,
141 0x12, 0x06, 0xd5, 0x8c, 0x1d, 0xb2, 0xa7, 0x57, 0x5f, 0x2f, 0x4f, 0xdb,
142 0x52, 0x99, 0x7c, 0x58, 0x01, 0x5f, 0xf2, 0xa5, 0xf6, 0x51, 0x86, 0x21,
143 0x2f, 0x5b, 0x8d, 0x6a, 0xae, 0x83, 0x34, 0x6d, 0x58, 0x4b, 0xef, 0xfe,
144 0xbf, 0x73, 0x5d, 0xdb, 0xc4, 0x97, 0x2a, 0x85, 0xf3, 0x6c, 0x46, 0x42,
145 0xb3, 0x90, 0xc1, 0x57, 0x97, 0x50, 0x35, 0xb1, 0x9d, 0xb7, 0xc7, 0x3c,
146 0x85, 0x6d, 0x6c, 0xfd, 0xce, 0xb0, 0xc9, 0xa2, 0x77, 0xee, 0xc3, 0x6b,
147 0x0c, 0x37, 0xfa, 0x30, 0x91, 0xd1, 0x2c, 0xb8, 0x5e, 0x7f, 0x81, 0x5f,
148 0x87, 0xfd, 0x18, 0x02, 0x5a, 0x30, 0x4e, 0x62, 0xbc, 0x65, 0xc6, 0xce,
149 0x1a, 0xcf, 0x2b, 0xaa, 0x56, 0x3e, 0x4d, 0xcf, 0xba, 0x62, 0x5f, 0x9a,
150 0xd0, 0x72, 0xff, 0xef, 0x28, 0xbd, 0xbe, 0xd8, 0x57, 0x3d, 0xf5, 0x57,
151 0x7d, 0xe9, 0x71, 0x31, 0xec, 0x98, 0x90, 0x94, 0xd9, 0x54, 0xbf, 0x84,
152 0x0b, 0xe3, 0x06, 0x47, 0x19, 0x9a, 0x13, 0x1d, 0xef, 0x9d, 0x13, 0xf3,
153 0xdb, 0xc3, 0x5c, 0x72, 0x9e, 0xed, 0x24, 0xaa, 0x64, 0xed, 0xe7, 0x0d,
154 0xa0, 0x7c, 0x73, 0xba, 0x9b, 0x86, 0xa7, 0x3b, 0x55, 0xab, 0x58, 0x30,
155 0xf1, 0x15, 0x81, 0x83, 0x2f, 0xf9, 0x62, 0x84, 0x98, 0x66, 0xf6, 0x55,
156 0x21, 0xd8, 0xf2, 0x25, 0x64, 0x71, 0x4b, 0x12, 0x76, 0x59, 0xc5, 0xaa,
157 0x93, 0x67, 0xc3, 0x86, 0x25, 0xab, 0x4e, 0x4b, 0xf6, 0xd8, 0x3f, 0x44,
158 0x2e, 0x11, 0xe0, 0xbd, 0x6a, 0xf2, 0x5d, 0xf5, 0xf9, 0x53, 0xea, 0xa4,
159 0xc8, 0xd9, 0x50, 0x33, 0x81, 0xd9, 0xa8, 0x2d, 0x91, 0x7d, 0x13, 0x2a,
160 0x11, 0xcf, 0xde, 0x3f, 0x0a, 0xd2, 0xbc, 0x33, 0xb2, 0x62, 0x53, 0xea,
161 0x77, 0x88, 0x43, 0x66, 0x27, 0x43, 0x85, 0xe9, 0x5f, 0x55, 0xf5, 0x2a,
162 0x8a, 0xac, 0xdf, 0xff, 0x9b, 0x4c, 0x96, 0x9c, 0xa5, 0x7a, 0xce, 0xd5,
163 0x79, 0x18, 0xf1, 0x0b, 0x58, 0x95, 0x7a, 0xe7, 0xd3, 0x74, 0x65, 0x0b,
164 0xa4, 0x64, 0x30, 0xe8, 0x5c, 0xfc, 0x55, 0x56, 0xee, 0x14, 0x14, 0xd3,
165 0x45, 0x3b, 0xf8, 0xde, 0x05, 0x3e, 0xb9, 0x3c, 0xd7, 0x6a, 0x52, 0x72,
166 0x5b, 0x39, 0x09, 0xbe, 0x82, 0x23, 0x10, 0x4a, 0xb7, 0xc3, 0xdc, 0x4c,
167 0x5d, 0xc9, 0xf1, 0x14, 0x83, 0xf9, 0x0b, 0x9b, 0xe9, 0x23, 0x84, 0x6a,
168 0xc4, 0x08, 0x3d, 0xda, 0x3d, 0x12, 0x95, 0x87, 0x18, 0xa4, 0x7d, 0x3f,
169 0x23, 0xde, 0xd4, 0x1e, 0xa8, 0x47, 0xc3, 0x71, 0xdb, 0xf5, 0x03, 0x6c,
170 0x57, 0xe7, 0xa4, 0x43, 0x82, 0x33, 0x7b, 0x62, 0x46, 0x7d, 0xf7, 0x10,
171 0x69, 0x18, 0x38, 0x27, 0x9a, 0x6f, 0x38, 0xac, 0xfa, 0x92, 0xc5, 0xae,
172 0x66, 0xa6, 0x73, 0x95, 0x15, 0x0e, 0x4c, 0x04, 0xb6, 0xfc, 0xf5, 0xc7,
173 0x21, 0x3a, 0x99, 0xdb, 0x0e, 0x36, 0xf0, 0x56, 0xbc, 0x75, 0xf9, 0x87,
174 0x9b, 0x11, 0x18, 0x92, 0x64, 0x1a, 0xe7, 0xc7, 0xab, 0x5a, 0xc7, 0x26,
175 0x7f, 0x13, 0x98, 0x42, 0x52, 0x43, 0xdb, 0xc8, 0x6d, 0x0b, 0xb7, 0x31,
176 0x93, 0x24, 0xd6, 0xe8, 0x24, 0x1f, 0x6f, 0x21, 0xa7, 0x8c, 0xeb, 0xdb,
177 0x83, 0xb8, 0x89, 0xe3, 0xc1, 0xd7, 0x69, 0x3b, 0x02, 0x6b, 0x54, 0x0f,
178 0x84, 0x2f, 0xb5, 0x5c, 0x17, 0x77, 0xbe, 0xe5, 0x61, 0x0d, 0xc5, 0xdf,
179 0x3b, 0xcf, 0x3e, 0x93, 0x4f, 0xf5, 0x89, 0xb9, 0x5a, 0xc5, 0x29, 0x31,
180 0xc0, 0xc2, 0xff, 0xe5, 0x3f, 0xa6, 0xac, 0x03, 0xca, 0xf5, 0xff, 0xe0,
181 0x36, 0xce, 0xf3, 0xe2, 0xb7, 0x9c, 0x02, 0xe9, 0x9e, 0xd2, 0xbc, 0x87,
182 0x2f, 0x3d, 0x9a, 0x1d, 0x8f, 0xc5, 0x72, 0xb8, 0xa2, 0x01, 0xd4, 0x68,
183 0xb1, 0x84, 0x16, 0x10, 0xf6, 0xf3, 0x52, 0x25, 0xd9, 0xdc, 0x4c, 0xdd,
184 0x0f, 0xd6, 0x4a, 0xcf, 0x60, 0x96, 0x7e, 0xcc, 0x42, 0x0f, 0x64, 0x9d,
185 0x72, 0x46, 0x04, 0x07, 0xf2, 0x5b, 0xf4, 0x07, 0xd1, 0xf4, 0x59, 0x71,
186 };
187
188 static const uint8_t kSpakeMSmallPrecomp[15 * 2 * 32] = {
189 0xc8, 0xa6, 0x63, 0xc5, 0x97, 0xf1, 0xee, 0x40, 0xab, 0x62, 0x42, 0xee,
190 0x25, 0x6f, 0x32, 0x6c, 0x75, 0x2c, 0xa7, 0xd3, 0xbd, 0x32, 0x3b, 0x1e,
191 0x11, 0x9c, 0xbd, 0x04, 0xa9, 0x78, 0x6f, 0x45, 0x5a, 0xda, 0x7e, 0x4b,
192 0xf6, 0xdd, 0xd9, 0xad, 0xb6, 0x62, 0x6d, 0x32, 0x13, 0x1c, 0x6b, 0x5c,
193 0x51, 0xa1, 0xe3, 0x47, 0xa3, 0x47, 0x8f, 0x53, 0xcf, 0xcf, 0x44, 0x1b,
194 0x88, 0xee, 0xd1, 0x2e, 0x03, 0x89, 0xaf, 0xc0, 0x61, 0x2d, 0x9e, 0x35,
195 0xeb, 0x0e, 0x03, 0xe0, 0xb7, 0xfb, 0xa5, 0xbc, 0x44, 0xbe, 0x0c, 0x89,
196 0x0a, 0x0f, 0xd6, 0x59, 0x47, 0x9e, 0xe6, 0x3d, 0x36, 0x9d, 0xff, 0x44,
197 0x5e, 0xac, 0xab, 0xe5, 0x3a, 0xd5, 0xb0, 0x35, 0x9f, 0x6d, 0x7f, 0xba,
198 0xc0, 0x85, 0x0e, 0xf4, 0x70, 0x3f, 0x13, 0x90, 0x4c, 0x50, 0x1a, 0xee,
199 0xc5, 0xeb, 0x69, 0xfe, 0x98, 0x42, 0x87, 0x1d, 0xce, 0x6c, 0x29, 0xaa,
200 0x2b, 0x31, 0xc2, 0x38, 0x7b, 0x6b, 0xee, 0x88, 0x0b, 0xba, 0xce, 0xa8,
201 0xca, 0x19, 0x60, 0x1b, 0x16, 0xf1, 0x25, 0x1e, 0xcf, 0x63, 0x66, 0x1e,
202 0xbb, 0x63, 0xeb, 0x7d, 0xca, 0xd2, 0xb4, 0x23, 0x5a, 0x01, 0x6f, 0x05,
203 0xd1, 0xdc, 0x41, 0x73, 0x75, 0xc0, 0xfd, 0x30, 0x91, 0x52, 0x68, 0x96,
204 0x45, 0xb3, 0x66, 0x01, 0x3b, 0x53, 0x89, 0x3c, 0x69, 0xbc, 0x6c, 0x69,
205 0xe3, 0x51, 0x8f, 0xe3, 0xd2, 0x84, 0xd5, 0x28, 0x66, 0xb5, 0xe6, 0x06,
206 0x09, 0xfe, 0x6d, 0xb0, 0x72, 0x16, 0xe0, 0x8a, 0xce, 0x61, 0x65, 0xa9,
207 0x21, 0x32, 0x48, 0xdc, 0x7a, 0x1d, 0xe1, 0x38, 0x7f, 0x8c, 0x75, 0x88,
208 0x3d, 0x08, 0xa9, 0x4a, 0x6f, 0x3d, 0x9f, 0x7f, 0x3f, 0xbd, 0x57, 0x6b,
209 0x19, 0xce, 0x3f, 0x4a, 0xc9, 0xd3, 0xf9, 0x6e, 0x72, 0x7b, 0x5b, 0x74,
210 0xea, 0xbe, 0x9c, 0x7a, 0x6d, 0x9c, 0x40, 0x49, 0xe6, 0xfb, 0x2a, 0x1a,
211 0x75, 0x70, 0xe5, 0x4e, 0xed, 0x74, 0xe0, 0x75, 0xac, 0xc0, 0xb1, 0x11,
212 0x3e, 0xf2, 0xaf, 0x88, 0x4d, 0x66, 0xb6, 0xf6, 0x15, 0x4f, 0x3c, 0x6c,
213 0x77, 0xae, 0x47, 0x51, 0x63, 0x9a, 0xfe, 0xe1, 0xb4, 0x1a, 0x12, 0xdf,
214 0xe9, 0x54, 0x8d, 0x3b, 0x30, 0x2a, 0x75, 0xe3, 0xe5, 0x29, 0xb1, 0x4c,
215 0xb0, 0x7c, 0x6d, 0xb5, 0xae, 0x85, 0xdb, 0x1e, 0x38, 0x55, 0x96, 0xa5,
216 0x5b, 0x9f, 0x15, 0x23, 0x28, 0x36, 0xb8, 0xa2, 0x41, 0xb4, 0xd7, 0x19,
217 0x91, 0x8d, 0x26, 0x3e, 0xca, 0x9c, 0x05, 0x7a, 0x2b, 0x60, 0x45, 0x86,
218 0x8b, 0xee, 0x64, 0x6f, 0x5c, 0x09, 0x4d, 0x4b, 0x5a, 0x7f, 0xb0, 0xc3,
219 0x26, 0x9d, 0x8b, 0xb8, 0x83, 0x69, 0xcf, 0x16, 0x72, 0x62, 0x3e, 0x5e,
220 0x53, 0x4f, 0x9c, 0x73, 0x76, 0xfc, 0x19, 0xef, 0xa0, 0x74, 0x3a, 0x11,
221 0x1e, 0xd0, 0x4d, 0xb7, 0x87, 0xa1, 0xd6, 0x87, 0x6c, 0x0e, 0x6c, 0x8c,
222 0xe9, 0xa0, 0x44, 0xc4, 0x72, 0x3e, 0x73, 0x17, 0x13, 0xd1, 0x4e, 0x3d,
223 0x8e, 0x1d, 0x5a, 0x8b, 0x75, 0xcb, 0x59, 0x2c, 0x47, 0x87, 0x15, 0x41,
224 0xfe, 0x08, 0xe9, 0xa6, 0x97, 0x17, 0x08, 0x26, 0x6a, 0xb5, 0xbb, 0x73,
225 0xaa, 0xb8, 0x5b, 0x65, 0x65, 0x5b, 0x30, 0x9e, 0x62, 0x59, 0x02, 0xf8,
226 0xb8, 0x0f, 0x32, 0x10, 0xc1, 0x36, 0x08, 0x52, 0x98, 0x4a, 0x1e, 0xf0,
227 0xab, 0x21, 0x5e, 0xde, 0x16, 0x0c, 0xda, 0x09, 0x99, 0x6b, 0x9e, 0xc0,
228 0x90, 0xa5, 0x5a, 0xcc, 0xb0, 0xb7, 0xbb, 0xd2, 0x8b, 0x5f, 0xd3, 0x3b,
229 0x3e, 0x8c, 0xa5, 0x71, 0x66, 0x06, 0xe3, 0x28, 0xd4, 0xf8, 0x3f, 0xe5,
230 0x27, 0xdf, 0xfe, 0x0f, 0x09, 0xb2, 0x8a, 0x09, 0x5a, 0x23, 0x61, 0x0d,
231 0x2d, 0xf5, 0x44, 0xf1, 0x5c, 0xf8, 0x82, 0x4e, 0xdc, 0x78, 0x7a, 0xab,
232 0xc3, 0x57, 0x91, 0xaf, 0x65, 0x6e, 0x71, 0xf1, 0x44, 0xbf, 0xed, 0x43,
233 0x50, 0xb4, 0x67, 0x48, 0xef, 0x5a, 0x10, 0x46, 0x81, 0xb4, 0x0c, 0xc8,
234 0x48, 0xed, 0x99, 0x7a, 0x45, 0xa5, 0x92, 0xc3, 0x69, 0xd6, 0xd7, 0x8a,
235 0x20, 0x1b, 0xeb, 0x8f, 0xb2, 0xff, 0xec, 0x6d, 0x76, 0x04, 0xf8, 0xc2,
236 0x58, 0x9b, 0xf2, 0x20, 0x53, 0xc4, 0x74, 0x91, 0x19, 0xdd, 0x2d, 0x12,
237 0x53, 0xc7, 0x6e, 0xd0, 0x02, 0x51, 0x3c, 0xa6, 0x7d, 0x80, 0x75, 0x6b,
238 0x1d, 0xdf, 0xf8, 0x6a, 0x52, 0xbb, 0x81, 0xf8, 0x30, 0x45, 0xef, 0x51,
239 0x85, 0x36, 0xbe, 0x8e, 0xcf, 0x0b, 0x9a, 0x46, 0xe8, 0x3f, 0x99, 0xfd,
240 0xf7, 0xd9, 0x3e, 0x84, 0xe5, 0xe3, 0x37, 0xcf, 0x98, 0x7f, 0xeb, 0x5e,
241 0x5a, 0x53, 0x77, 0x1c, 0x20, 0xdc, 0xf1, 0x20, 0x99, 0xec, 0x60, 0x40,
242 0x93, 0xef, 0x5c, 0x1c, 0x81, 0xe2, 0xa5, 0xad, 0x2a, 0xc2, 0xdb, 0x6b,
243 0xc1, 0x7e, 0x8f, 0xa9, 0x23, 0x5b, 0xd9, 0x0d, 0xfe, 0xa0, 0xac, 0x11,
244 0x28, 0xba, 0x8e, 0x92, 0x07, 0x2d, 0x07, 0x40, 0x83, 0x14, 0x4c, 0x35,
245 0x8d, 0xd0, 0x11, 0xff, 0x98, 0xdb, 0x00, 0x30, 0x6f, 0x65, 0xb6, 0xa0,
246 0x7f, 0x9c, 0x08, 0xb8, 0xce, 0xb3, 0xa8, 0x42, 0xd3, 0x84, 0x45, 0xe1,
247 0xe3, 0x8f, 0xa6, 0x89, 0x21, 0xd7, 0x74, 0x02, 0x4d, 0x64, 0xdf, 0x54,
248 0x15, 0x9e, 0xba, 0x12, 0x49, 0x09, 0x41, 0xf6, 0x10, 0x24, 0xa1, 0x84,
249 0x15, 0xfd, 0x68, 0x6a, 0x57, 0x66, 0xb3, 0x6d, 0x4c, 0xea, 0xbf, 0xbc,
250 0x60, 0x3f, 0x52, 0x1c, 0x44, 0x1b, 0xc0, 0x4a, 0x25, 0xe3, 0xd9, 0x4c,
251 0x9a, 0x74, 0xad, 0xfc, 0x9e, 0x8d, 0x0b, 0x18, 0x66, 0x24, 0xd1, 0x06,
252 0xac, 0x68, 0xc1, 0xae, 0x14, 0xce, 0xb1, 0xf3, 0x86, 0x9f, 0x87, 0x11,
253 0xd7, 0x9f, 0x30, 0x92, 0xdb, 0xec, 0x0b, 0x4a, 0xe8, 0xf6, 0x53, 0x36,
254 0x68, 0x12, 0x11, 0x5e, 0xe0, 0x34, 0xa4, 0xff, 0x00, 0x0a, 0x26, 0xb8,
255 0x62, 0x79, 0x9c, 0x0c, 0xd5, 0xe5, 0xf5, 0x1c, 0x1a, 0x16, 0x84, 0x4d,
256 0x8e, 0x5d, 0x31, 0x7e, 0xf7, 0xe2, 0xd3, 0xa1, 0x41, 0x90, 0x61, 0x5d,
257 0x04, 0xb2, 0x9a, 0x18, 0x9e, 0x54, 0xfb, 0xd1, 0x61, 0x95, 0x1b, 0x08,
258 0xca, 0x7c, 0x49, 0x44, 0x74, 0x1d, 0x2f, 0xca, 0xc4, 0x7a, 0xe1, 0x8b,
259 0x2f, 0xbb, 0x96, 0xee, 0x19, 0x8a, 0x5d, 0xfb, 0x3e, 0x82, 0xe7, 0x15,
260 0xdb, 0x29, 0x14, 0xee, 0xc9, 0x4d, 0x9a, 0xfb, 0x9f, 0x8a, 0xbb, 0x17,
261 0x37, 0x1b, 0x6e, 0x28, 0x6c, 0xf9, 0xff, 0xb5, 0xb5, 0x8b, 0x9d, 0x88,
262 0x20, 0x08, 0x10, 0xd7, 0xca, 0x58, 0xf6, 0xe1, 0x32, 0x91, 0x6f, 0x36,
263 0xc0, 0xad, 0xc1, 0x57, 0x5d, 0x76, 0x31, 0x43, 0xf3, 0xdd, 0xec, 0xf1,
264 0xa9, 0x79, 0xe9, 0xe9, 0x85, 0xd7, 0x91, 0xc7, 0x31, 0x62, 0x3c, 0xd2,
265 0x90, 0x2c, 0x9c, 0xa4, 0x56, 0x37, 0x7b, 0xbe, 0x40, 0x58, 0xc0, 0x81,
266 0x83, 0x22, 0xe8, 0x13, 0x79, 0x18, 0xdb, 0x3a, 0x1b, 0x31, 0x0d, 0x00,
267 0x6c, 0x22, 0x62, 0x75, 0x70, 0xd8, 0x96, 0x59, 0x99, 0x44, 0x79, 0x71,
268 0xa6, 0x76, 0x81, 0x28, 0xb2, 0x65, 0xe8, 0x47, 0x14, 0xc6, 0x39, 0x06,
269 };
270
SPAKE2_CTX_new(enum spake2_role_t my_role,const uint8_t * my_name,size_t my_name_len,const uint8_t * their_name,size_t their_name_len)271 SPAKE2_CTX *SPAKE2_CTX_new(enum spake2_role_t my_role,
272 const uint8_t *my_name, size_t my_name_len,
273 const uint8_t *their_name, size_t their_name_len) {
274 SPAKE2_CTX *ctx = OPENSSL_malloc(sizeof(SPAKE2_CTX));
275 if (ctx == NULL) {
276 return NULL;
277 }
278
279 OPENSSL_memset(ctx, 0, sizeof(SPAKE2_CTX));
280 ctx->my_role = my_role;
281
282 CBS my_name_cbs, their_name_cbs;
283 CBS_init(&my_name_cbs, my_name, my_name_len);
284 CBS_init(&their_name_cbs, their_name, their_name_len);
285 if (!CBS_stow(&my_name_cbs, &ctx->my_name, &ctx->my_name_len) ||
286 !CBS_stow(&their_name_cbs, &ctx->their_name, &ctx->their_name_len)) {
287 SPAKE2_CTX_free(ctx);
288 return NULL;
289 }
290
291 return ctx;
292 }
293
SPAKE2_CTX_free(SPAKE2_CTX * ctx)294 void SPAKE2_CTX_free(SPAKE2_CTX *ctx) {
295 if (ctx == NULL) {
296 return;
297 }
298
299 OPENSSL_free(ctx->my_name);
300 OPENSSL_free(ctx->their_name);
301 OPENSSL_free(ctx);
302 }
303
304 // left_shift_3 sets |n| to |n|*8, where |n| is represented in little-endian
305 // order.
left_shift_3(uint8_t n[32])306 static void left_shift_3(uint8_t n[32]) {
307 uint8_t carry = 0;
308 unsigned i;
309
310 for (i = 0; i < 32; i++) {
311 const uint8_t next_carry = n[i] >> 5;
312 n[i] = (n[i] << 3) | carry;
313 carry = next_carry;
314 }
315 }
316
317 typedef union {
318 uint8_t bytes[32];
319 uint32_t words[8];
320 } scalar;
321
322 // kOrder is the order of the prime-order subgroup of curve25519 in
323 // little-endian order.
324 static const scalar kOrder = {{0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
325 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
326 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
327 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10}};
328
329 // scalar_cmov copies |src| to |dest| if |mask| is all ones.
scalar_cmov(scalar * dest,const scalar * src,crypto_word_t mask)330 static void scalar_cmov(scalar *dest, const scalar *src, crypto_word_t mask) {
331 for (size_t i = 0; i < 8; i++) {
332 dest->words[i] =
333 constant_time_select_w(mask, src->words[i], dest->words[i]);
334 }
335 }
336
337 // scalar_double sets |s| to |2×s|.
scalar_double(scalar * s)338 static void scalar_double(scalar *s) {
339 uint32_t carry = 0;
340
341 for (size_t i = 0; i < 8; i++) {
342 const uint32_t carry_out = s->words[i] >> 31;
343 s->words[i] = (s->words[i] << 1) | carry;
344 carry = carry_out;
345 }
346 }
347
348 // scalar_add sets |dest| to |dest| plus |src|.
scalar_add(scalar * dest,const scalar * src)349 static void scalar_add(scalar *dest, const scalar *src) {
350 uint32_t carry = 0;
351
352 for (size_t i = 0; i < 8; i++) {
353 uint64_t tmp = ((uint64_t)dest->words[i] + src->words[i]) + carry;
354 dest->words[i] = (uint32_t)tmp;
355 carry = (uint32_t)(tmp >> 32);
356 }
357 }
358
SPAKE2_generate_msg(SPAKE2_CTX * ctx,uint8_t * out,size_t * out_len,size_t max_out_len,const uint8_t * password,size_t password_len)359 int SPAKE2_generate_msg(SPAKE2_CTX *ctx, uint8_t *out, size_t *out_len,
360 size_t max_out_len, const uint8_t *password,
361 size_t password_len) {
362 if (ctx->state != spake2_state_init) {
363 return 0;
364 }
365
366 if (max_out_len < sizeof(ctx->my_msg)) {
367 return 0;
368 }
369
370 uint8_t private_tmp[64];
371 RAND_bytes(private_tmp, sizeof(private_tmp));
372 x25519_sc_reduce(private_tmp);
373 // Multiply by the cofactor (eight) so that we'll clear it when operating on
374 // the peer's point later in the protocol.
375 left_shift_3(private_tmp);
376 OPENSSL_memcpy(ctx->private_key, private_tmp, sizeof(ctx->private_key));
377
378 ge_p3 P;
379 x25519_ge_scalarmult_base(&P, ctx->private_key);
380
381 // mask = h(password) * <N or M>.
382 uint8_t password_tmp[SHA512_DIGEST_LENGTH];
383 SHA512(password, password_len, password_tmp);
384 OPENSSL_memcpy(ctx->password_hash, password_tmp, sizeof(ctx->password_hash));
385 x25519_sc_reduce(password_tmp);
386
387 // Due to a copy-paste error, the call to |left_shift_3| was omitted after
388 // the |x25519_sc_reduce|, just above. This meant that |ctx->password_scalar|
389 // was not a multiple of eight to clear the cofactor and thus three bits of
390 // the password hash would leak. In order to fix this in a unilateral way,
391 // points of small order are added to the mask point such that it is in the
392 // prime-order subgroup. Since the ephemeral scalar is a multiple of eight,
393 // these points will cancel out when calculating the shared secret.
394 //
395 // Adding points of small order is the same as adding multiples of the prime
396 // order to the password scalar. Since that's faster, that is what is done
397 // below. The prime order (kOrder) is a large prime, thus odd, thus the LSB
398 // is one. So adding it will flip the LSB. Adding twice it will flip the next
399 // bit and so one for all the bottom three bits.
400
401 scalar password_scalar;
402 OPENSSL_memcpy(&password_scalar, password_tmp, sizeof(password_scalar));
403
404 // |password_scalar| is the result of |x25519_sc_reduce| and thus is, at
405 // most, $l-1$ (where $l$ is |kOrder|, the order of the prime-order subgroup
406 // of Ed25519). In the following, we may add $l + 2×l + 4×l$ for a max value
407 // of $8×l-1$. That is < 2**256, as required.
408
409 if (!ctx->disable_password_scalar_hack) {
410 scalar order = kOrder;
411 scalar tmp;
412
413 OPENSSL_memset(&tmp, 0, sizeof(tmp));
414 scalar_cmov(&tmp, &order,
415 constant_time_eq_w(password_scalar.bytes[0] & 1, 1));
416 scalar_add(&password_scalar, &tmp);
417
418 scalar_double(&order);
419 OPENSSL_memset(&tmp, 0, sizeof(tmp));
420 scalar_cmov(&tmp, &order,
421 constant_time_eq_w(password_scalar.bytes[0] & 2, 2));
422 scalar_add(&password_scalar, &tmp);
423
424 scalar_double(&order);
425 OPENSSL_memset(&tmp, 0, sizeof(tmp));
426 scalar_cmov(&tmp, &order,
427 constant_time_eq_w(password_scalar.bytes[0] & 4, 4));
428 scalar_add(&password_scalar, &tmp);
429
430 assert((password_scalar.bytes[0] & 7) == 0);
431 }
432
433 OPENSSL_memcpy(ctx->password_scalar, password_scalar.bytes,
434 sizeof(ctx->password_scalar));
435
436 ge_p3 mask;
437 x25519_ge_scalarmult_small_precomp(&mask, ctx->password_scalar,
438 ctx->my_role == spake2_role_alice
439 ? kSpakeMSmallPrecomp
440 : kSpakeNSmallPrecomp);
441
442 // P* = P + mask.
443 ge_cached mask_cached;
444 x25519_ge_p3_to_cached(&mask_cached, &mask);
445 ge_p1p1 Pstar;
446 x25519_ge_add(&Pstar, &P, &mask_cached);
447
448 // Encode P*
449 ge_p2 Pstar_proj;
450 x25519_ge_p1p1_to_p2(&Pstar_proj, &Pstar);
451 x25519_ge_tobytes(ctx->my_msg, &Pstar_proj);
452
453 OPENSSL_memcpy(out, ctx->my_msg, sizeof(ctx->my_msg));
454 *out_len = sizeof(ctx->my_msg);
455 ctx->state = spake2_state_msg_generated;
456
457 return 1;
458 }
459
update_with_length_prefix(SHA512_CTX * sha,const uint8_t * data,const size_t len)460 static void update_with_length_prefix(SHA512_CTX *sha, const uint8_t *data,
461 const size_t len) {
462 uint8_t len_le[8];
463 size_t l = len;
464 unsigned i;
465
466 for (i = 0; i < 8; i++) {
467 len_le[i] = l & 0xff;
468 l >>= 8;
469 }
470
471 SHA512_Update(sha, len_le, sizeof(len_le));
472 SHA512_Update(sha, data, len);
473 }
474
SPAKE2_process_msg(SPAKE2_CTX * ctx,uint8_t * out_key,size_t * out_key_len,size_t max_out_key_len,const uint8_t * their_msg,size_t their_msg_len)475 int SPAKE2_process_msg(SPAKE2_CTX *ctx, uint8_t *out_key, size_t *out_key_len,
476 size_t max_out_key_len, const uint8_t *their_msg,
477 size_t their_msg_len) {
478 if (ctx->state != spake2_state_msg_generated ||
479 their_msg_len != 32) {
480 return 0;
481 }
482
483 ge_p3 Qstar;
484 if (!x25519_ge_frombytes_vartime(&Qstar, their_msg)) {
485 // Point received from peer was not on the curve.
486 return 0;
487 }
488
489 // Unmask peer's value.
490 ge_p3 peers_mask;
491 x25519_ge_scalarmult_small_precomp(&peers_mask, ctx->password_scalar,
492 ctx->my_role == spake2_role_alice
493 ? kSpakeNSmallPrecomp
494 : kSpakeMSmallPrecomp);
495
496 ge_cached peers_mask_cached;
497 x25519_ge_p3_to_cached(&peers_mask_cached, &peers_mask);
498
499 ge_p1p1 Q_compl;
500 ge_p3 Q_ext;
501 x25519_ge_sub(&Q_compl, &Qstar, &peers_mask_cached);
502 x25519_ge_p1p1_to_p3(&Q_ext, &Q_compl);
503
504 ge_p2 dh_shared;
505 x25519_ge_scalarmult(&dh_shared, ctx->private_key, &Q_ext);
506
507 uint8_t dh_shared_encoded[32];
508 x25519_ge_tobytes(dh_shared_encoded, &dh_shared);
509
510 SHA512_CTX sha;
511 SHA512_Init(&sha);
512 if (ctx->my_role == spake2_role_alice) {
513 update_with_length_prefix(&sha, ctx->my_name, ctx->my_name_len);
514 update_with_length_prefix(&sha, ctx->their_name, ctx->their_name_len);
515 update_with_length_prefix(&sha, ctx->my_msg, sizeof(ctx->my_msg));
516 update_with_length_prefix(&sha, their_msg, 32);
517 } else {
518 update_with_length_prefix(&sha, ctx->their_name, ctx->their_name_len);
519 update_with_length_prefix(&sha, ctx->my_name, ctx->my_name_len);
520 update_with_length_prefix(&sha, their_msg, 32);
521 update_with_length_prefix(&sha, ctx->my_msg, sizeof(ctx->my_msg));
522 }
523 update_with_length_prefix(&sha, dh_shared_encoded, sizeof(dh_shared_encoded));
524 update_with_length_prefix(&sha, ctx->password_hash,
525 sizeof(ctx->password_hash));
526
527 uint8_t key[SHA512_DIGEST_LENGTH];
528 SHA512_Final(key, &sha);
529
530 size_t to_copy = max_out_key_len;
531 if (to_copy > sizeof(key)) {
532 to_copy = sizeof(key);
533 }
534 OPENSSL_memcpy(out_key, key, to_copy);
535 *out_key_len = to_copy;
536 ctx->state = spake2_state_key_generated;
537
538 return 1;
539 }
540