crypto_curve25519.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360
  1. /* Copyright (c) 2012-2018, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. /**
  4. * \file crypto_curve25519.c
  5. *
  6. * \brief Wrapper code for a curve25519 implementation.
  7. *
  8. * Curve25519 is an Elliptic-Curve Diffie Hellman handshake, designed by
  9. * Dan Bernstein. For more information, see https://cr.yp.to/ecdh.html
  10. *
  11. * Tor uses Curve25519 as the basis of its "ntor" circuit extension
  12. * handshake, and in related code. The functions in this module are
  13. * used to find the most suitable available Curve25519 implementation,
  14. * to provide wrappers around it, and so on.
  15. */
  16. #define CRYPTO_CURVE25519_PRIVATE
  17. #include "orconfig.h"
  18. #ifdef HAVE_SYS_STAT_H
  19. #include <sys/stat.h>
  20. #endif
  21. #include "lib/ctime/di_ops.h"
  22. #include "lib/crypt_ops/crypto_curve25519.h"
  23. #include "lib/crypt_ops/crypto_digest.h"
  24. #include "lib/crypt_ops/crypto_format.h"
  25. #include "lib/crypt_ops/crypto_rand.h"
  26. #include "lib/crypt_ops/crypto_util.h"
  27. #include "lib/log/log.h"
  28. #include "lib/log/util_bug.h"
  29. #include "ed25519/donna/ed25519_donna_tor.h"
  30. #include <string.h>
  31. /* ==============================
  32. Part 1: wrap a suitable curve25519 implementation as curve25519_impl
  33. ============================== */
  34. #ifdef USE_CURVE25519_DONNA
  35. int curve25519_donna(uint8_t *mypublic,
  36. const uint8_t *secret, const uint8_t *basepoint);
  37. #endif
  38. #ifdef USE_CURVE25519_NACL
  39. #ifdef HAVE_CRYPTO_SCALARMULT_CURVE25519_H
  40. #include <crypto_scalarmult_curve25519.h>
  41. #elif defined(HAVE_NACL_CRYPTO_SCALARMULT_CURVE25519_H)
  42. #include <nacl/crypto_scalarmult_curve25519.h>
  43. #endif
  44. #endif /* defined(USE_CURVE25519_NACL) */
  45. static void pick_curve25519_basepoint_impl(void);
  46. /** This is set to 1 if we have an optimized Ed25519-based
  47. * implementation for multiplying a value by the basepoint; to 0 if we
  48. * don't, and to -1 if we haven't checked. */
  49. static int curve25519_use_ed = -1;
  50. /**
  51. * Helper function: call the most appropriate backend to compute the
  52. * scalar "secret" times the point "point". Store the result in
  53. * "output". Return 0 on success, negative on failure.
  54. **/
  55. STATIC int
  56. curve25519_impl(uint8_t *output, const uint8_t *secret,
  57. const uint8_t *point)
  58. {
  59. uint8_t bp[CURVE25519_PUBKEY_LEN];
  60. int r;
  61. memcpy(bp, point, CURVE25519_PUBKEY_LEN);
  62. /* Clear the high bit, in case our backend foolishly looks at it. */
  63. bp[31] &= 0x7f;
  64. #ifdef USE_CURVE25519_DONNA
  65. r = curve25519_donna(output, secret, bp);
  66. #elif defined(USE_CURVE25519_NACL)
  67. r = crypto_scalarmult_curve25519(output, secret, bp);
  68. #else
  69. #error "No implementation of curve25519 is available."
  70. #endif /* defined(USE_CURVE25519_DONNA) || ... */
  71. memwipe(bp, 0, sizeof(bp));
  72. return r;
  73. }
  74. /**
  75. * Helper function: Multiply the scalar "secret" by the Curve25519
  76. * basepoint (X=9), and store the result in "output". Return 0 on
  77. * success, -1 on failure.
  78. */
  79. STATIC int
  80. curve25519_basepoint_impl(uint8_t *output, const uint8_t *secret)
  81. {
  82. int r = 0;
  83. if (BUG(curve25519_use_ed == -1)) {
  84. /* LCOV_EXCL_START - Only reached if we forgot to call curve25519_init() */
  85. pick_curve25519_basepoint_impl();
  86. /* LCOV_EXCL_STOP */
  87. }
  88. /* TODO: Someone should benchmark curved25519_scalarmult_basepoint versus
  89. * an optimized NaCl build to see which should be used when compiled with
  90. * NaCl available. I suspected that the ed25519 optimization always wins.
  91. */
  92. if (PREDICT_LIKELY(curve25519_use_ed == 1)) {
  93. curved25519_scalarmult_basepoint_donna(output, secret);
  94. r = 0;
  95. } else {
  96. static const uint8_t basepoint[32] = {9};
  97. r = curve25519_impl(output, secret, basepoint);
  98. }
  99. return r;
  100. }
  101. /**
  102. * Override the decision of whether to use the Ed25519-based basepoint
  103. * multiply function. Used for testing.
  104. */
  105. void
  106. curve25519_set_impl_params(int use_ed)
  107. {
  108. curve25519_use_ed = use_ed;
  109. }
  110. /* ==============================
  111. Part 2: Wrap curve25519_impl with some convenience types and functions.
  112. ============================== */
  113. /**
  114. * Return true iff a curve25519_public_key_t seems valid. (It's not necessary
  115. * to see if the point is on the curve, since the twist is also secure, but we
  116. * do need to make sure that it isn't the point at infinity.) */
  117. int
  118. curve25519_public_key_is_ok(const curve25519_public_key_t *key)
  119. {
  120. return !safe_mem_is_zero(key->public_key, CURVE25519_PUBKEY_LEN);
  121. }
  122. /**
  123. * Generate CURVE25519_SECKEY_LEN random bytes in <b>out</b>. If
  124. * <b>extra_strong</b> is true, this key is possibly going to get used more
  125. * than once, so use a better-than-usual RNG. Return 0 on success, -1 on
  126. * failure.
  127. *
  128. * This function does not adjust the output of the RNG at all; the will caller
  129. * will need to clear or set the appropriate bits to make curve25519 work.
  130. */
  131. int
  132. curve25519_rand_seckey_bytes(uint8_t *out, int extra_strong)
  133. {
  134. if (extra_strong)
  135. crypto_strongest_rand(out, CURVE25519_SECKEY_LEN);
  136. else
  137. crypto_rand((char*)out, CURVE25519_SECKEY_LEN);
  138. return 0;
  139. }
  140. /** Generate a new keypair and return the secret key. If <b>extra_strong</b>
  141. * is true, this key is possibly going to get used more than once, so
  142. * use a better-than-usual RNG. Return 0 on success, -1 on failure. */
  143. int
  144. curve25519_secret_key_generate(curve25519_secret_key_t *key_out,
  145. int extra_strong)
  146. {
  147. if (curve25519_rand_seckey_bytes(key_out->secret_key, extra_strong) < 0)
  148. return -1;
  149. key_out->secret_key[0] &= 248;
  150. key_out->secret_key[31] &= 127;
  151. key_out->secret_key[31] |= 64;
  152. return 0;
  153. }
  154. /**
  155. * Given a secret key in <b>seckey</b>, create the corresponding public
  156. * key in <b>key_out</b>.
  157. */
  158. void
  159. curve25519_public_key_generate(curve25519_public_key_t *key_out,
  160. const curve25519_secret_key_t *seckey)
  161. {
  162. curve25519_basepoint_impl(key_out->public_key, seckey->secret_key);
  163. }
  164. /**
  165. * Construct a new keypair in *<b>keypair_out</b>. If <b>extra_strong</b>
  166. * is true, this key is possibly going to get used more than once, so
  167. * use a better-than-usual RNG. Return 0 on success, -1 on failure. */
  168. int
  169. curve25519_keypair_generate(curve25519_keypair_t *keypair_out,
  170. int extra_strong)
  171. {
  172. if (curve25519_secret_key_generate(&keypair_out->seckey, extra_strong) < 0)
  173. return -1;
  174. curve25519_public_key_generate(&keypair_out->pubkey, &keypair_out->seckey);
  175. return 0;
  176. }
  177. /** Store the keypair <b>keypair</b>, including its secret and public
  178. * parts, to the file <b>fname</b>. Use the string tag <b>tag</b> to
  179. * distinguish this from other Curve25519 keypairs. Return 0 on success,
  180. * -1 on failure.
  181. *
  182. * See crypto_write_tagged_contents_to_file() for more information on
  183. * the metaformat used for these keys.*/
  184. int
  185. curve25519_keypair_write_to_file(const curve25519_keypair_t *keypair,
  186. const char *fname,
  187. const char *tag)
  188. {
  189. uint8_t contents[CURVE25519_SECKEY_LEN + CURVE25519_PUBKEY_LEN];
  190. int r;
  191. memcpy(contents, keypair->seckey.secret_key, CURVE25519_SECKEY_LEN);
  192. memcpy(contents+CURVE25519_SECKEY_LEN,
  193. keypair->pubkey.public_key, CURVE25519_PUBKEY_LEN);
  194. r = crypto_write_tagged_contents_to_file(fname,
  195. "c25519v1",
  196. tag,
  197. contents,
  198. sizeof(contents));
  199. memwipe(contents, 0, sizeof(contents));
  200. return r;
  201. }
  202. /** Read a curve25519 keypair from a file named <b>fname</b> created by
  203. * curve25519_keypair_write_to_file(). Store the keypair in
  204. * <b>keypair_out</b>, and the associated tag string in <b>tag_out</b>.
  205. * Return 0 on success, and -1 on failure. */
  206. int
  207. curve25519_keypair_read_from_file(curve25519_keypair_t *keypair_out,
  208. char **tag_out,
  209. const char *fname)
  210. {
  211. uint8_t content[CURVE25519_SECKEY_LEN + CURVE25519_PUBKEY_LEN];
  212. ssize_t len;
  213. int r = -1;
  214. len = crypto_read_tagged_contents_from_file(fname, "c25519v1", tag_out,
  215. content, sizeof(content));
  216. if (len != sizeof(content))
  217. goto end;
  218. /* Make sure that the public key matches the secret key */
  219. memcpy(keypair_out->seckey.secret_key, content, CURVE25519_SECKEY_LEN);
  220. curve25519_public_key_generate(&keypair_out->pubkey, &keypair_out->seckey);
  221. if (tor_memneq(keypair_out->pubkey.public_key,
  222. content + CURVE25519_SECKEY_LEN,
  223. CURVE25519_PUBKEY_LEN))
  224. goto end;
  225. r = 0;
  226. end:
  227. memwipe(content, 0, sizeof(content));
  228. if (r != 0) {
  229. memset(keypair_out, 0, sizeof(*keypair_out));
  230. tor_free(*tag_out);
  231. }
  232. return r;
  233. }
  234. /** Perform the curve25519 ECDH handshake with <b>skey</b> and <b>pkey</b>,
  235. * writing CURVE25519_OUTPUT_LEN bytes of output into <b>output</b>. */
  236. void
  237. curve25519_handshake(uint8_t *output,
  238. const curve25519_secret_key_t *skey,
  239. const curve25519_public_key_t *pkey)
  240. {
  241. curve25519_impl(output, skey->secret_key, pkey->public_key);
  242. }
  243. /** Check whether the ed25519-based curve25519 basepoint optimization seems to
  244. * be working. If so, return 0; otherwise return -1. */
  245. static int
  246. curve25519_basepoint_spot_check(void)
  247. {
  248. static const uint8_t alicesk[32] = {
  249. 0x77,0x07,0x6d,0x0a,0x73,0x18,0xa5,0x7d,
  250. 0x3c,0x16,0xc1,0x72,0x51,0xb2,0x66,0x45,
  251. 0xdf,0x4c,0x2f,0x87,0xeb,0xc0,0x99,0x2a,
  252. 0xb1,0x77,0xfb,0xa5,0x1d,0xb9,0x2c,0x2a
  253. };
  254. static const uint8_t alicepk[32] = {
  255. 0x85,0x20,0xf0,0x09,0x89,0x30,0xa7,0x54,
  256. 0x74,0x8b,0x7d,0xdc,0xb4,0x3e,0xf7,0x5a,
  257. 0x0d,0xbf,0x3a,0x0d,0x26,0x38,0x1a,0xf4,
  258. 0xeb,0xa4,0xa9,0x8e,0xaa,0x9b,0x4e,0x6a
  259. };
  260. const int loop_max=200;
  261. int save_use_ed = curve25519_use_ed;
  262. unsigned char e1[32] = { 5 };
  263. unsigned char e2[32] = { 5 };
  264. unsigned char x[32],y[32];
  265. int i;
  266. int r=0;
  267. /* Check the most basic possible sanity via the test secret/public key pair
  268. * used in "Cryptography in NaCl - 2. Secret keys and public keys". This
  269. * may catch catastrophic failures on systems where Curve25519 is expensive,
  270. * without requiring a ton of key generation.
  271. */
  272. curve25519_use_ed = 1;
  273. r |= curve25519_basepoint_impl(x, alicesk);
  274. if (fast_memneq(x, alicepk, 32))
  275. goto fail;
  276. /* Ok, the optimization appears to produce passable results, try a few more
  277. * values, maybe there's something subtle wrong.
  278. */
  279. for (i = 0; i < loop_max; ++i) {
  280. curve25519_use_ed = 0;
  281. r |= curve25519_basepoint_impl(x, e1);
  282. curve25519_use_ed = 1;
  283. r |= curve25519_basepoint_impl(y, e2);
  284. if (fast_memneq(x,y,32))
  285. goto fail;
  286. memcpy(e1, x, 32);
  287. memcpy(e2, x, 32);
  288. }
  289. goto end;
  290. // LCOV_EXCL_START -- we can only hit this code if there is a bug in our
  291. // curve25519-basepoint implementation.
  292. fail:
  293. r = -1;
  294. // LCOV_EXCL_STOP
  295. end:
  296. curve25519_use_ed = save_use_ed;
  297. return r;
  298. }
  299. /** Choose whether to use the ed25519-based curve25519-basepoint
  300. * implementation. */
  301. static void
  302. pick_curve25519_basepoint_impl(void)
  303. {
  304. curve25519_use_ed = 1;
  305. if (curve25519_basepoint_spot_check() == 0)
  306. return;
  307. /* LCOV_EXCL_START
  308. * only reachable if our basepoint implementation broken */
  309. log_warn(LD_BUG|LD_CRYPTO, "The ed25519-based curve25519 basepoint "
  310. "multiplication seems broken; using the curve25519 "
  311. "implementation.");
  312. curve25519_use_ed = 0;
  313. /* LCOV_EXCL_STOP */
  314. }
  315. /** Initialize the curve25519 implementations. This is necessary if you're
  316. * going to use them in a multithreaded setting, and not otherwise. */
  317. void
  318. curve25519_init(void)
  319. {
  320. pick_curve25519_basepoint_impl();
  321. }