Tor  0.4.5.0-alpha-dev
crypto_curve25519.c
Go to the documentation of this file.
1 /* Copyright (c) 2012-2020, 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"
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() */
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
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
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)
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
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
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
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
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 
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
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,
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
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
345 {
346  curve25519_use_ed = 1;
347 
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
364 {
366 }
safe_mem_is_zero
int safe_mem_is_zero(const void *mem, size_t sz)
Definition: di_ops.c:224
tor_free
#define tor_free(p)
Definition: malloc.h:52
CURVE25519_PUBKEY_LEN
#define CURVE25519_PUBKEY_LEN
Definition: x25519_sizes.h:20
memwipe
void memwipe(void *mem, uint8_t byte, size_t sz)
Definition: crypto_util.c:55
LD_BUG
#define LD_BUG
Definition: log.h:86
curve25519_impl
STATIC int curve25519_impl(uint8_t *output, const uint8_t *secret, const uint8_t *point)
Definition: crypto_curve25519.c:65
curve25519_basepoint_impl
STATIC int curve25519_basepoint_impl(uint8_t *output, const uint8_t *secret)
Definition: crypto_curve25519.c:90
crypto_read_tagged_contents_from_file
ssize_t crypto_read_tagged_contents_from_file(const char *fname, const char *typestring, char **tag_out, uint8_t *data_out, ssize_t data_out_len)
Definition: crypto_format.c:77
curve25519_init
void curve25519_init(void)
Definition: crypto_curve25519.c:363
util_bug.h
Macros to manage assertions, fatal and non-fatal.
curve25519_use_ed
static int curve25519_use_ed
Definition: crypto_curve25519.c:57
crypto_util.h
Common functions for cryptographic routines.
curve25519_public_key_generate
void curve25519_public_key_generate(curve25519_public_key_t *key_out, const curve25519_secret_key_t *seckey)
Definition: crypto_curve25519.c:179
curve25519_keypair_read_from_file
int curve25519_keypair_read_from_file(curve25519_keypair_t *keypair_out, char **tag_out, const char *fname)
Definition: crypto_curve25519.c:233
crypto_format.h
Header for crypto_format.c.
curve25519_rand_seckey_bytes
int curve25519_rand_seckey_bytes(uint8_t *out, int extra_strong)
Definition: crypto_curve25519.c:147
tor_memneq
#define tor_memneq(a, b, sz)
Definition: di_ops.h:21
crypto_strongest_rand
void crypto_strongest_rand(uint8_t *out, size_t out_len)
Definition: crypto_rand.c:340
pick_curve25519_basepoint_impl
static void pick_curve25519_basepoint_impl(void)
Definition: crypto_curve25519.c:344
curve25519_keypair_generate
int curve25519_keypair_generate(curve25519_keypair_t *keypair_out, int extra_strong)
Definition: crypto_curve25519.c:190
crypto_curve25519.h
Header for crypto_curve25519.c.
curve25519_secret_key_generate
int curve25519_secret_key_generate(curve25519_secret_key_t *key_out, int extra_strong)
Definition: crypto_curve25519.c:161
fast_memneq
#define fast_memneq(a, b, c)
Definition: di_ops.h:42
di_ops.h
Headers for di_ops.c.
crypto_rand.h
Common functions for using (pseudo-)random number generators.
curve25519_basepoint_spot_check
static int curve25519_basepoint_spot_check(void)
Definition: crypto_curve25519.c:278
curve25519_public_key_is_ok
int curve25519_public_key_is_ok(const curve25519_public_key_t *key)
Definition: crypto_curve25519.c:132
curve25519_public_key_t
Definition: crypto_curve25519.h:24
LD_CRYPTO
#define LD_CRYPTO
Definition: log.h:64
log.h
Headers for log.c.
curve25519_secret_key_t
Definition: crypto_curve25519.h:33
crypto_write_tagged_contents_to_file
int crypto_write_tagged_contents_to_file(const char *fname, const char *typestring, const char *tag, const uint8_t *data, size_t datalen)
Definition: crypto_format.c:42
crypto_rand
void crypto_rand(char *to, size_t n)
Definition: crypto_rand.c:477
crypto_digest.h
Headers for crypto_digest.c.
STATIC
#define STATIC
Definition: testsupport.h:32
curve25519_handshake
void curve25519_handshake(uint8_t *output, const curve25519_secret_key_t *skey, const curve25519_public_key_t *pkey)
Definition: crypto_curve25519.c:268
CURVE25519_SECKEY_LEN
#define CURVE25519_SECKEY_LEN
Definition: x25519_sizes.h:22
curve25519_keypair_write_to_file
int curve25519_keypair_write_to_file(const curve25519_keypair_t *keypair, const char *fname, const char *tag)
Definition: crypto_curve25519.c:207
curve25519_set_impl_params
void curve25519_set_impl_params(int use_ed)
Definition: crypto_curve25519.c:118
curve25519_keypair_t
Definition: crypto_curve25519.h:38