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