p224_spake.cc 12 KB

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