crypto_curve25519.c 11 KB

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