1// Copyright (c) 2012 The Chromium 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 <crypto/p224_spake.h>
9
10#include <algorithm>
11
12#include <base/logging.h>
13#include <crypto/p224.h>
14#include <crypto/random.h>
15#include <crypto/secure_util.h>
16
17namespace {
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
80const 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
88const 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}  // anonymous namespace
97
98namespace crypto {
99
100P224EncryptedKeyExchange::P224EncryptedKeyExchange(
101    PeerType peer_type, const base::StringPiece& password)
102    : state_(kStateInitial),
103      is_server_(peer_type == kPeerTypeServer) {
104  memset(&x_, 0, sizeof(x_));
105  memset(&expected_authenticator_, 0, sizeof(expected_authenticator_));
106
107  // x_ is a random scalar.
108  RandBytes(x_, sizeof(x_));
109
110  // Calculate |password| hash to get SPAKE password value.
111  SHA256HashString(std::string(password.data(), password.length()),
112                   pw_, sizeof(pw_));
113
114  Init();
115}
116
117void P224EncryptedKeyExchange::Init() {
118  // X = g**x_
119  p224::Point X;
120  p224::ScalarBaseMult(x_, &X);
121
122  // The client masks the Diffie-Hellman value, X, by adding M**pw and the
123  // server uses N**pw.
124  p224::Point MNpw;
125  p224::ScalarMult(is_server_ ? kN : kM, pw_, &MNpw);
126
127  // X* = X + (N|M)**pw
128  p224::Point Xstar;
129  p224::Add(X, MNpw, &Xstar);
130
131  next_message_ = Xstar.ToString();
132}
133
134const std::string& P224EncryptedKeyExchange::GetNextMessage() {
135  if (state_ == kStateInitial) {
136    state_ = kStateRecvDH;
137    return next_message_;
138  } else if (state_ == kStateSendHash) {
139    state_ = kStateRecvHash;
140    return next_message_;
141  }
142
143  LOG(FATAL) << "P224EncryptedKeyExchange::GetNextMessage called in"
144                " bad state " << state_;
145  next_message_ = "";
146  return next_message_;
147}
148
149P224EncryptedKeyExchange::Result P224EncryptedKeyExchange::ProcessMessage(
150    const base::StringPiece& message) {
151  if (state_ == kStateRecvHash) {
152    // This is the final state of the protocol: we are reading the peer's
153    // authentication hash and checking that it matches the one that we expect.
154    if (message.size() != sizeof(expected_authenticator_)) {
155      error_ = "peer's hash had an incorrect size";
156      return kResultFailed;
157    }
158    if (!SecureMemEqual(message.data(), expected_authenticator_,
159                        message.size())) {
160      error_ = "peer's hash had incorrect value";
161      return kResultFailed;
162    }
163    state_ = kStateDone;
164    return kResultSuccess;
165  }
166
167  if (state_ != kStateRecvDH) {
168    LOG(FATAL) << "P224EncryptedKeyExchange::ProcessMessage called in"
169                  " bad state " << state_;
170    error_ = "internal error";
171    return kResultFailed;
172  }
173
174  // Y* is the other party's masked, Diffie-Hellman value.
175  p224::Point Ystar;
176  if (!Ystar.SetFromString(message)) {
177    error_ = "failed to parse peer's masked Diffie-Hellman value";
178    return kResultFailed;
179  }
180
181  // We calculate the mask value: (N|M)**pw
182  p224::Point MNpw, minus_MNpw, Y, k;
183  p224::ScalarMult(is_server_ ? kM : kN, pw_, &MNpw);
184  p224::Negate(MNpw, &minus_MNpw);
185
186  // Y = Y* - (N|M)**pw
187  p224::Add(Ystar, minus_MNpw, &Y);
188
189  // K = Y**x_
190  p224::ScalarMult(Y, x_, &k);
191
192  // If everything worked out, then K is the same for both parties.
193  key_ = k.ToString();
194
195  std::string client_masked_dh, server_masked_dh;
196  if (is_server_) {
197    client_masked_dh = message.as_string();
198    server_masked_dh = next_message_;
199  } else {
200    client_masked_dh = next_message_;
201    server_masked_dh = message.as_string();
202  }
203
204  // Now we calculate the hashes that each side will use to prove to the other
205  // that they derived the correct value for K.
206  uint8_t client_hash[kSHA256Length], server_hash[kSHA256Length];
207  CalculateHash(kPeerTypeClient, client_masked_dh, server_masked_dh, key_,
208                client_hash);
209  CalculateHash(kPeerTypeServer, client_masked_dh, server_masked_dh, key_,
210                server_hash);
211
212  const uint8_t* my_hash = is_server_ ? server_hash : client_hash;
213  const uint8_t* their_hash = is_server_ ? client_hash : server_hash;
214
215  next_message_ =
216      std::string(reinterpret_cast<const char*>(my_hash), kSHA256Length);
217  memcpy(expected_authenticator_, their_hash, kSHA256Length);
218  state_ = kStateSendHash;
219  return kResultPending;
220}
221
222void P224EncryptedKeyExchange::CalculateHash(
223    PeerType peer_type,
224    const std::string& client_masked_dh,
225    const std::string& server_masked_dh,
226    const std::string& k,
227    uint8_t* out_digest) {
228  std::string hash_contents;
229
230  if (peer_type == kPeerTypeServer) {
231    hash_contents = "server";
232  } else {
233    hash_contents = "client";
234  }
235
236  hash_contents += client_masked_dh;
237  hash_contents += server_masked_dh;
238  hash_contents +=
239      std::string(reinterpret_cast<const char *>(pw_), sizeof(pw_));
240  hash_contents += k;
241
242  SHA256HashString(hash_contents, out_digest, kSHA256Length);
243}
244
245const std::string& P224EncryptedKeyExchange::error() const {
246  return error_;
247}
248
249const std::string& P224EncryptedKeyExchange::GetKey() const {
250  DCHECK_EQ(state_, kStateDone);
251  return GetUnverifiedKey();
252}
253
254const std::string& P224EncryptedKeyExchange::GetUnverifiedKey() const {
255  // Key is already final when state is kStateSendHash. Subsequent states are
256  // used only for verification of the key. Some users may combine verification
257  // with sending verifiable data instead of |expected_authenticator_|.
258  DCHECK_GE(state_, kStateSendHash);
259  return key_;
260}
261
262void P224EncryptedKeyExchange::SetXForTesting(const std::string& x) {
263  memset(&x_, 0, sizeof(x_));
264  memcpy(&x_, x.data(), std::min(x.size(), sizeof(x_)));
265  Init();
266}
267
268}  // namespace crypto
269