1 // Copyright 2012 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // This code implements SPAKE2, a variant of EKE:
6 // http://www.di.ens.fr/~pointche/pub.php?reference=AbPo04
7
8 #include "crypto/p224_spake.h"
9
10 #include <string.h>
11
12 #include <algorithm>
13 #include <string_view>
14
15 #include "base/check_op.h"
16 #include "base/logging.h"
17 #include "crypto/random.h"
18 #include "crypto/secure_util.h"
19 #include "third_party/boringssl/src/include/openssl/bn.h"
20 #include "third_party/boringssl/src/include/openssl/ec.h"
21
22 namespace {
23
24 // The following two points (M and N in the protocol) are verifiable random
25 // points on the curve and can be generated with the following code:
26
27 // #include <stdint.h>
28 // #include <stdio.h>
29 // #include <string.h>
30 //
31 // #include <openssl/ec.h>
32 // #include <openssl/obj_mac.h>
33 // #include <openssl/sha.h>
34 //
35 // // Silence a presubmit.
36 // #define PRINTF printf
37 //
38 // static const char kSeed1[] = "P224 point generation seed (M)";
39 // static const char kSeed2[] = "P224 point generation seed (N)";
40 //
41 // void find_seed(const char* seed) {
42 // SHA256_CTX sha256;
43 // uint8_t digest[SHA256_DIGEST_LENGTH];
44 //
45 // SHA256_Init(&sha256);
46 // SHA256_Update(&sha256, seed, strlen(seed));
47 // SHA256_Final(digest, &sha256);
48 //
49 // BIGNUM x, y;
50 // EC_GROUP* p224 = EC_GROUP_new_by_curve_name(NID_secp224r1);
51 // EC_POINT* p = EC_POINT_new(p224);
52 //
53 // for (unsigned i = 0;; i++) {
54 // BN_init(&x);
55 // BN_bin2bn(digest, 28, &x);
56 //
57 // if (EC_POINT_set_compressed_coordinates_GFp(
58 // p224, p, &x, digest[28] & 1, NULL)) {
59 // BN_init(&y);
60 // EC_POINT_get_affine_coordinates_GFp(p224, p, &x, &y, NULL);
61 // char* x_str = BN_bn2hex(&x);
62 // char* y_str = BN_bn2hex(&y);
63 // PRINTF("Found after %u iterations:\n%s\n%s\n", i, x_str, y_str);
64 // OPENSSL_free(x_str);
65 // OPENSSL_free(y_str);
66 // BN_free(&x);
67 // BN_free(&y);
68 // break;
69 // }
70 //
71 // SHA256_Init(&sha256);
72 // SHA256_Update(&sha256, digest, sizeof(digest));
73 // SHA256_Final(digest, &sha256);
74 //
75 // BN_free(&x);
76 // }
77 //
78 // EC_POINT_free(p);
79 // EC_GROUP_free(p224);
80 // }
81 //
82 // int main() {
83 // find_seed(kSeed1);
84 // find_seed(kSeed2);
85 // return 0;
86 // }
87
88 const uint8_t kM_X962[1 + 28 + 28] = {
89 0x04, 0x4d, 0x48, 0xc8, 0xea, 0x8d, 0x23, 0x39, 0x2e, 0x07, 0xe8, 0x51,
90 0xfa, 0x6a, 0xa8, 0x20, 0x48, 0x09, 0x4e, 0x05, 0x13, 0x72, 0x49, 0x9c,
91 0x6f, 0xba, 0x62, 0xa7, 0x4b, 0x6c, 0x18, 0x5c, 0xab, 0xd5, 0x2e, 0x2e,
92 0x8a, 0x9e, 0x2d, 0x21, 0xb0, 0xec, 0x4e, 0xe1, 0x41, 0x21, 0x1f, 0xe2,
93 0x9d, 0x64, 0xea, 0x4d, 0x04, 0x46, 0x3a, 0xe8, 0x33,
94 };
95
96 const uint8_t kN_X962[1 + 28 + 28] = {
97 0x04, 0x0b, 0x1c, 0xfc, 0x6a, 0x40, 0x7c, 0xdc, 0xb1, 0x5d, 0xc1, 0x70,
98 0x4c, 0xd1, 0x3e, 0xda, 0xab, 0x8f, 0xde, 0xff, 0x8c, 0xfb, 0xfb, 0x50,
99 0xd2, 0xc8, 0x1d, 0xe2, 0xc2, 0x3e, 0x14, 0xf6, 0x29, 0x96, 0x08, 0x09,
100 0x07, 0xb5, 0x6d, 0xd2, 0x82, 0x07, 0x1a, 0xa7, 0xa1, 0x21, 0xc3, 0x99,
101 0x34, 0xbc, 0x30, 0xda, 0x5b, 0xcb, 0xc6, 0xa3, 0xcc,
102 };
103
104 // ToBignum returns |big_endian_bytes| interpreted as a big-endian number.
ToBignum(base::span<const uint8_t> big_endian_bytes)105 bssl::UniquePtr<BIGNUM> ToBignum(base::span<const uint8_t> big_endian_bytes) {
106 bssl::UniquePtr<BIGNUM> bn(BN_new());
107 CHECK(BN_bin2bn(big_endian_bytes.data(), big_endian_bytes.size(), bn.get()));
108 return bn;
109 }
110
111 // GetPoint decodes and returns the given X.962-encoded point. It will crash if
112 // |x962| is not a valid P-224 point.
GetPoint(const EC_GROUP * p224,base::span<const uint8_t,1+28+28> x962)113 bssl::UniquePtr<EC_POINT> GetPoint(
114 const EC_GROUP* p224,
115 base::span<const uint8_t, 1 + 28 + 28> x962) {
116 bssl::UniquePtr<EC_POINT> point(EC_POINT_new(p224));
117 CHECK(EC_POINT_oct2point(p224, point.get(), x962.data(), x962.size(),
118 /*ctx=*/nullptr));
119 return point;
120 }
121
122 // GetMask returns (M|N)**pw, where the choice of M or N is controlled by
123 // |use_m|.
GetMask(const EC_GROUP * p224,bool use_m,base::span<const uint8_t> pw)124 bssl::UniquePtr<EC_POINT> GetMask(const EC_GROUP* p224,
125 bool use_m,
126 base::span<const uint8_t> pw) {
127 bssl::UniquePtr<EC_POINT> MN(GetPoint(p224, use_m ? kM_X962 : kN_X962));
128 bssl::UniquePtr<EC_POINT> MNpw(EC_POINT_new(p224));
129 bssl::UniquePtr<BIGNUM> pw_bn(ToBignum(pw));
130 CHECK(EC_POINT_mul(p224, MNpw.get(), nullptr, MN.get(), pw_bn.get(),
131 /*ctx=*/nullptr));
132 return MNpw;
133 }
134
135 // ToMessage serialises |in| as a 56-byte string that contains the big-endian
136 // representations of x and y, or is all zeros if |in| is infinity.
ToMessage(const EC_GROUP * p224,const EC_POINT * in)137 std::string ToMessage(const EC_GROUP* p224, const EC_POINT* in) {
138 if (EC_POINT_is_at_infinity(p224, in)) {
139 return std::string(28 + 28, 0);
140 }
141
142 uint8_t x962[1 + 28 + 28];
143 CHECK(EC_POINT_point2oct(p224, in, POINT_CONVERSION_UNCOMPRESSED, x962,
144 sizeof(x962), /*ctx=*/nullptr) == sizeof(x962));
145 return std::string(reinterpret_cast<const char*>(&x962[1]), sizeof(x962) - 1);
146 }
147
148 // FromMessage converts a message, as generated by |ToMessage|, into a point. It
149 // returns |nullptr| if the input is invalid or not on the curve.
FromMessage(const EC_GROUP * p224,std::string_view in)150 bssl::UniquePtr<EC_POINT> FromMessage(const EC_GROUP* p224,
151 std::string_view in) {
152 if (in.size() != 56) {
153 return nullptr;
154 }
155
156 uint8_t x962[1 + 56];
157 x962[0] = 4;
158 memcpy(&x962[1], in.data(), sizeof(x962) - 1);
159
160 bssl::UniquePtr<EC_POINT> ret(EC_POINT_new(p224));
161 if (!EC_POINT_oct2point(p224, ret.get(), x962, sizeof(x962),
162 /*ctx=*/nullptr)) {
163 return nullptr;
164 }
165
166 return ret;
167 }
168
169 } // anonymous namespace
170
171 namespace crypto {
172
P224EncryptedKeyExchange(PeerType peer_type,std::string_view password)173 P224EncryptedKeyExchange::P224EncryptedKeyExchange(PeerType peer_type,
174 std::string_view password)
175 : state_(kStateInitial), is_server_(peer_type == kPeerTypeServer) {
176 memset(&x_, 0, sizeof(x_));
177 memset(&expected_authenticator_, 0, sizeof(expected_authenticator_));
178
179 // x_ is a random scalar.
180 RandBytes(x_, sizeof(x_));
181
182 // Calculate |password| hash to get SPAKE password value.
183 SHA256HashString(std::string(password.data(), password.length()),
184 pw_, sizeof(pw_));
185
186 Init();
187 }
188
Init()189 void P224EncryptedKeyExchange::Init() {
190 // X = g**x_
191 const EC_GROUP* p224 = EC_group_p224();
192 bssl::UniquePtr<EC_POINT> X(EC_POINT_new(p224));
193 bssl::UniquePtr<BIGNUM> x_bn(ToBignum(x_));
194 // x_bn may be >= the order, but |EC_POINT_mul| handles that. It doesn't do so
195 // in constant-time, but the these values are locally generated and so this
196 // occurs with negligible probability. (Same with |pw_|, just below.)
197 CHECK(EC_POINT_mul(p224, X.get(), x_bn.get(), nullptr, nullptr,
198 /*ctx=*/nullptr));
199
200 // The client masks the Diffie-Hellman value, X, by adding M**pw and the
201 // server uses N**pw.
202 bssl::UniquePtr<EC_POINT> MNpw(GetMask(p224, !is_server_, pw_));
203
204 // X* = X + (N|M)**pw
205 bssl::UniquePtr<EC_POINT> Xstar(EC_POINT_new(p224));
206 CHECK(EC_POINT_add(p224, Xstar.get(), X.get(), MNpw.get(),
207 /*ctx=*/nullptr));
208
209 next_message_ = ToMessage(p224, Xstar.get());
210 }
211
GetNextMessage()212 const std::string& P224EncryptedKeyExchange::GetNextMessage() {
213 if (state_ == kStateInitial) {
214 state_ = kStateRecvDH;
215 return next_message_;
216 } else if (state_ == kStateSendHash) {
217 state_ = kStateRecvHash;
218 return next_message_;
219 }
220
221 LOG(FATAL) << "P224EncryptedKeyExchange::GetNextMessage called in"
222 " bad state " << state_;
223 }
224
ProcessMessage(std::string_view message)225 P224EncryptedKeyExchange::Result P224EncryptedKeyExchange::ProcessMessage(
226 std::string_view message) {
227 if (state_ == kStateRecvHash) {
228 // This is the final state of the protocol: we are reading the peer's
229 // authentication hash and checking that it matches the one that we expect.
230 if (message.size() != sizeof(expected_authenticator_)) {
231 error_ = "peer's hash had an incorrect size";
232 return kResultFailed;
233 }
234 if (!SecureMemEqual(message.data(), expected_authenticator_,
235 message.size())) {
236 error_ = "peer's hash had incorrect value";
237 return kResultFailed;
238 }
239 state_ = kStateDone;
240 return kResultSuccess;
241 }
242
243 if (state_ != kStateRecvDH) {
244 LOG(FATAL) << "P224EncryptedKeyExchange::ProcessMessage called in"
245 " bad state " << state_;
246 }
247
248 const EC_GROUP* p224 = EC_group_p224();
249
250 // Y* is the other party's masked, Diffie-Hellman value.
251 bssl::UniquePtr<EC_POINT> Ystar(FromMessage(p224, message));
252 if (!Ystar) {
253 error_ = "failed to parse peer's masked Diffie-Hellman value";
254 return kResultFailed;
255 }
256
257 // We calculate the mask value: (N|M)**pw
258 bssl::UniquePtr<EC_POINT> MNpw(GetMask(p224, is_server_, pw_));
259 // Y = Y* - (N|M)**pw
260 CHECK(EC_POINT_invert(p224, MNpw.get(), /*ctx=*/nullptr));
261 bssl::UniquePtr<EC_POINT> Y(EC_POINT_new(p224));
262 CHECK(EC_POINT_add(p224, Y.get(), Ystar.get(), MNpw.get(),
263 /*ctx=*/nullptr));
264
265 // K = Y**x_
266 bssl::UniquePtr<EC_POINT> K(EC_POINT_new(p224));
267 bssl::UniquePtr<BIGNUM> x_bn(ToBignum(x_));
268 CHECK(EC_POINT_mul(p224, K.get(), nullptr, Y.get(), x_bn.get(),
269 /*ctx=*/nullptr));
270
271 // If everything worked out, then K is the same for both parties.
272 key_ = ToMessage(p224, K.get());
273
274 std::string client_masked_dh, server_masked_dh;
275 if (is_server_) {
276 client_masked_dh = std::string(message);
277 server_masked_dh = next_message_;
278 } else {
279 client_masked_dh = next_message_;
280 server_masked_dh = std::string(message);
281 }
282
283 // Now we calculate the hashes that each side will use to prove to the other
284 // that they derived the correct value for K.
285 uint8_t client_hash[kSHA256Length], server_hash[kSHA256Length];
286 CalculateHash(kPeerTypeClient, client_masked_dh, server_masked_dh, key_,
287 client_hash);
288 CalculateHash(kPeerTypeServer, client_masked_dh, server_masked_dh, key_,
289 server_hash);
290
291 const uint8_t* my_hash = is_server_ ? server_hash : client_hash;
292 const uint8_t* their_hash = is_server_ ? client_hash : server_hash;
293
294 next_message_ =
295 std::string(reinterpret_cast<const char*>(my_hash), kSHA256Length);
296 memcpy(expected_authenticator_, their_hash, kSHA256Length);
297 state_ = kStateSendHash;
298 return kResultPending;
299 }
300
CalculateHash(PeerType peer_type,const std::string & client_masked_dh,const std::string & server_masked_dh,const std::string & k,uint8_t * out_digest)301 void P224EncryptedKeyExchange::CalculateHash(
302 PeerType peer_type,
303 const std::string& client_masked_dh,
304 const std::string& server_masked_dh,
305 const std::string& k,
306 uint8_t* out_digest) {
307 std::string hash_contents;
308
309 if (peer_type == kPeerTypeServer) {
310 hash_contents = "server";
311 } else {
312 hash_contents = "client";
313 }
314
315 hash_contents += client_masked_dh;
316 hash_contents += server_masked_dh;
317 hash_contents +=
318 std::string(reinterpret_cast<const char *>(pw_), sizeof(pw_));
319 hash_contents += k;
320
321 SHA256HashString(hash_contents, out_digest, kSHA256Length);
322 }
323
error() const324 const std::string& P224EncryptedKeyExchange::error() const {
325 return error_;
326 }
327
GetKey() const328 const std::string& P224EncryptedKeyExchange::GetKey() const {
329 DCHECK_EQ(state_, kStateDone);
330 return GetUnverifiedKey();
331 }
332
GetUnverifiedKey() const333 const std::string& P224EncryptedKeyExchange::GetUnverifiedKey() const {
334 // Key is already final when state is kStateSendHash. Subsequent states are
335 // used only for verification of the key. Some users may combine verification
336 // with sending verifiable data instead of |expected_authenticator_|.
337 DCHECK_GE(state_, kStateSendHash);
338 return key_;
339 }
340
SetXForTesting(const std::string & x)341 void P224EncryptedKeyExchange::SetXForTesting(const std::string& x) {
342 memset(&x_, 0, sizeof(x_));
343 memcpy(&x_, x.data(), std::min(x.size(), sizeof(x_)));
344 Init();
345 }
346
347 } // namespace crypto
348