src/lib/crypt_ops/crypto_curve25519.c

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