1 // Copyright 2012 The Chromium OS Authors. All rights reserved.
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 "third_party/chromium/crypto/p224_spake.h"
9
10 #include <algorithm>
11
12 #include <base/logging.h>
13 #include <base/rand_util.h>
14
15 #include "third_party/chromium/crypto/p224.h"
16
17 namespace {
18
19 // The following two points (M and N in the protocol) are verifiable random
20 // points on the curve and can be generated with the following code:
21
22 // #include <stdint.h>
23 // #include <stdio.h>
24 // #include <string.h>
25 //
26 // #include <openssl/ec.h>
27 // #include <openssl/obj_mac.h>
28 // #include <openssl/sha.h>
29 //
30 // static const char kSeed1[] = "P224 point generation seed (M)";
31 // static const char kSeed2[] = "P224 point generation seed (N)";
32 //
33 // void find_seed(const char* seed) {
34 // SHA256_CTX sha256;
35 // uint8_t digest[SHA256_DIGEST_LENGTH];
36 //
37 // SHA256_Init(&sha256);
38 // SHA256_Update(&sha256, seed, strlen(seed));
39 // SHA256_Final(digest, &sha256);
40 //
41 // BIGNUM x, y;
42 // EC_GROUP* p224 = EC_GROUP_new_by_curve_name(NID_secp224r1);
43 // EC_POINT* p = EC_POINT_new(p224);
44 //
45 // for (unsigned i = 0;; i++) {
46 // BN_init(&x);
47 // BN_bin2bn(digest, 28, &x);
48 //
49 // if (EC_POINT_set_compressed_coordinates_GFp(
50 // p224, p, &x, digest[28] & 1, NULL)) {
51 // BN_init(&y);
52 // EC_POINT_get_affine_coordinates_GFp(p224, p, &x, &y, NULL);
53 // char* x_str = BN_bn2hex(&x);
54 // char* y_str = BN_bn2hex(&y);
55 // printf("Found after %u iterations:\n%s\n%s\n", i, x_str, y_str);
56 // OPENSSL_free(x_str);
57 // OPENSSL_free(y_str);
58 // BN_free(&x);
59 // BN_free(&y);
60 // break;
61 // }
62 //
63 // SHA256_Init(&sha256);
64 // SHA256_Update(&sha256, digest, sizeof(digest));
65 // SHA256_Final(digest, &sha256);
66 //
67 // BN_free(&x);
68 // }
69 //
70 // EC_POINT_free(p);
71 // EC_GROUP_free(p224);
72 // }
73 //
74 // int main() {
75 // find_seed(kSeed1);
76 // find_seed(kSeed2);
77 // return 0;
78 // }
79
80 const crypto::p224::Point kM = {
81 {174237515, 77186811, 235213682, 33849492,
82 33188520, 48266885, 177021753, 81038478},
83 {104523827, 245682244, 266509668, 236196369,
84 28372046, 145351378, 198520366, 113345994},
85 {1, 0, 0, 0, 0, 0, 0, 0},
86 };
87
88 const crypto::p224::Point kN = {
89 {136176322, 263523628, 251628795, 229292285,
90 5034302, 185981975, 171998428, 11653062},
91 {197567436, 51226044, 60372156, 175772188,
92 42075930, 8083165, 160827401, 65097570},
93 {1, 0, 0, 0, 0, 0, 0, 0},
94 };
95
96 // Performs a constant-time comparison of two strings, returning true if the
97 // strings are equal.
98 //
99 // For cryptographic operations, comparison functions such as memcmp() may
100 // expose side-channel information about input, allowing an attacker to
101 // perform timing analysis to determine what the expected bits should be. In
102 // order to avoid such attacks, the comparison must execute in constant time,
103 // so as to not to reveal to the attacker where the difference(s) are.
104 // For an example attack, see
105 // http://groups.google.com/group/keyczar-discuss/browse_thread/thread/5571eca0948b2a13
SecureMemEqual(const uint8_t * s1_ptr,const uint8_t * s2_ptr,size_t n)106 bool SecureMemEqual(const uint8_t* s1_ptr, const uint8_t* s2_ptr, size_t n) {
107 uint8_t tmp = 0;
108 for (size_t i = 0; i < n; ++i, ++s1_ptr, ++s2_ptr)
109 tmp |= *s1_ptr ^ *s2_ptr;
110 return (tmp == 0);
111 }
112
113 } // anonymous namespace
114
115 namespace crypto {
116
P224EncryptedKeyExchange(PeerType peer_type,const base::StringPiece & password)117 P224EncryptedKeyExchange::P224EncryptedKeyExchange(
118 PeerType peer_type, const base::StringPiece& password)
119 : state_(kStateInitial),
120 is_server_(peer_type == kPeerTypeServer) {
121 memset(&x_, 0, sizeof(x_));
122 memset(&expected_authenticator_, 0, sizeof(expected_authenticator_));
123
124 // x_ is a random scalar.
125 base::RandBytes(x_, sizeof(x_));
126
127 // Calculate |password| hash to get SPAKE password value.
128 SHA256HashString(std::string(password.data(), password.length()),
129 pw_, sizeof(pw_));
130
131 Init();
132 }
133
Init()134 void P224EncryptedKeyExchange::Init() {
135 // X = g**x_
136 p224::Point X;
137 p224::ScalarBaseMult(x_, &X);
138
139 // The client masks the Diffie-Hellman value, X, by adding M**pw and the
140 // server uses N**pw.
141 p224::Point MNpw;
142 p224::ScalarMult(is_server_ ? kN : kM, pw_, &MNpw);
143
144 // X* = X + (N|M)**pw
145 p224::Point Xstar;
146 p224::Add(X, MNpw, &Xstar);
147
148 next_message_ = Xstar.ToString();
149 }
150
GetNextMessage()151 const std::string& P224EncryptedKeyExchange::GetNextMessage() {
152 if (state_ == kStateInitial) {
153 state_ = kStateRecvDH;
154 return next_message_;
155 } else if (state_ == kStateSendHash) {
156 state_ = kStateRecvHash;
157 return next_message_;
158 }
159
160 LOG(FATAL) << "P224EncryptedKeyExchange::GetNextMessage called in"
161 " bad state " << state_;
162 next_message_ = "";
163 return next_message_;
164 }
165
ProcessMessage(const base::StringPiece & message)166 P224EncryptedKeyExchange::Result P224EncryptedKeyExchange::ProcessMessage(
167 const base::StringPiece& message) {
168 if (state_ == kStateRecvHash) {
169 // This is the final state of the protocol: we are reading the peer's
170 // authentication hash and checking that it matches the one that we expect.
171 if (message.size() != sizeof(expected_authenticator_)) {
172 error_ = "peer's hash had an incorrect size";
173 return kResultFailed;
174 }
175 if (!SecureMemEqual(reinterpret_cast<const uint8_t*>(message.data()),
176 expected_authenticator_, message.size())) {
177 error_ = "peer's hash had incorrect value";
178 return kResultFailed;
179 }
180 state_ = kStateDone;
181 return kResultSuccess;
182 }
183
184 if (state_ != kStateRecvDH) {
185 LOG(FATAL) << "P224EncryptedKeyExchange::ProcessMessage called in"
186 " bad state " << state_;
187 error_ = "internal error";
188 return kResultFailed;
189 }
190
191 // Y* is the other party's masked, Diffie-Hellman value.
192 p224::Point Ystar;
193 if (!Ystar.SetFromString(message)) {
194 error_ = "failed to parse peer's masked Diffie-Hellman value";
195 return kResultFailed;
196 }
197
198 // We calculate the mask value: (N|M)**pw
199 p224::Point MNpw, minus_MNpw, Y, k;
200 p224::ScalarMult(is_server_ ? kM : kN, pw_, &MNpw);
201 p224::Negate(MNpw, &minus_MNpw);
202
203 // Y = Y* - (N|M)**pw
204 p224::Add(Ystar, minus_MNpw, &Y);
205
206 // K = Y**x_
207 p224::ScalarMult(Y, x_, &k);
208
209 // If everything worked out, then K is the same for both parties.
210 key_ = k.ToString();
211
212 std::string client_masked_dh, server_masked_dh;
213 if (is_server_) {
214 client_masked_dh = message.as_string();
215 server_masked_dh = next_message_;
216 } else {
217 client_masked_dh = next_message_;
218 server_masked_dh = message.as_string();
219 }
220
221 // Now we calculate the hashes that each side will use to prove to the other
222 // that they derived the correct value for K.
223 uint8_t client_hash[kSHA256Length], server_hash[kSHA256Length];
224 CalculateHash(kPeerTypeClient, client_masked_dh, server_masked_dh, key_,
225 client_hash);
226 CalculateHash(kPeerTypeServer, client_masked_dh, server_masked_dh, key_,
227 server_hash);
228
229 const uint8_t* my_hash = is_server_ ? server_hash : client_hash;
230 const uint8_t* their_hash = is_server_ ? client_hash : server_hash;
231
232 next_message_ =
233 std::string(reinterpret_cast<const char*>(my_hash), kSHA256Length);
234 memcpy(expected_authenticator_, their_hash, kSHA256Length);
235 state_ = kStateSendHash;
236 return kResultPending;
237 }
238
CalculateHash(PeerType peer_type,const std::string & client_masked_dh,const std::string & server_masked_dh,const std::string & k,uint8_t * out_digest)239 void P224EncryptedKeyExchange::CalculateHash(
240 PeerType peer_type,
241 const std::string& client_masked_dh,
242 const std::string& server_masked_dh,
243 const std::string& k,
244 uint8_t* out_digest) {
245 std::string hash_contents;
246
247 if (peer_type == kPeerTypeServer) {
248 hash_contents = "server";
249 } else {
250 hash_contents = "client";
251 }
252
253 hash_contents += client_masked_dh;
254 hash_contents += server_masked_dh;
255 hash_contents +=
256 std::string(reinterpret_cast<const char *>(pw_), sizeof(pw_));
257 hash_contents += k;
258
259 SHA256HashString(hash_contents, out_digest, kSHA256Length);
260 }
261
error() const262 const std::string& P224EncryptedKeyExchange::error() const {
263 return error_;
264 }
265
GetKey() const266 const std::string& P224EncryptedKeyExchange::GetKey() const {
267 DCHECK_EQ(state_, kStateDone);
268 return GetUnverifiedKey();
269 }
270
GetUnverifiedKey() const271 const std::string& P224EncryptedKeyExchange::GetUnverifiedKey() const {
272 // Key is already final when state is kStateSendHash. Subsequent states are
273 // used only for verification of the key. Some users may combine verification
274 // with sending verifiable data instead of |expected_authenticator_|.
275 DCHECK_GE(state_, kStateSendHash);
276 return key_;
277 }
278
SetXForTesting(const std::string & x)279 void P224EncryptedKeyExchange::SetXForTesting(const std::string& x) {
280 memset(&x_, 0, sizeof(x_));
281 memcpy(&x_, x.data(), std::min(x.size(), sizeof(x_)));
282 Init();
283 }
284
285 } // namespace crypto
286