crypto_curve25519.c (11731B)
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 }