p224_spake.cc 12 KB

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