crypto_curve25519.c 11.3 KB
Newer Older
1
/* Copyright (c) 2012-2017, The Tor Project, Inc. */
2
3
/* See LICENSE for licensing information */

4
5
6
7
/**
 * \file crypto_curve25519.c
 *
 * \brief Wrapper code for a curve25519 implementation.
8
9
10
11
12
13
14
15
 *
 * Curve25519 is an Elliptic-Curve Diffie Hellman handshake, designed by
 * Dan Bernstein.  For more information, see https://cr.yp.to/ecdh.html
 *
 * Tor uses Curve25519 as the basis of its "ntor" circuit extension
 * handshake, and in related code.  The functions in this module are
 * used to find the most suitable available Curve25519 implementation,
 * to provide wrappers around it, and so on.
16
 */
17
18
19

#define CRYPTO_CURVE25519_PRIVATE
#include "orconfig.h"
20
21
22
#ifdef HAVE_SYS_STAT_H
#include <sys/stat.h>
#endif
23
#include "container.h"
24
25
#include "crypto.h"
#include "crypto_curve25519.h"
26
#include "crypto_format.h"
27
#include "crypto_digest.h"
28
29
#include "crypto_rand.h"
#include "crypto_util.h"
30
#include "util.h"
31
#include "torlog.h"
32

33
34
#include "ed25519/donna/ed25519_donna_tor.h"

35
36
37
38
39
40
41
42
43
/* ==============================
   Part 1: wrap a suitable curve25519 implementation as curve25519_impl
   ============================== */

#ifdef USE_CURVE25519_DONNA
int curve25519_donna(uint8_t *mypublic,
                     const uint8_t *secret, const uint8_t *basepoint);
#endif
#ifdef USE_CURVE25519_NACL
44
#ifdef HAVE_CRYPTO_SCALARMULT_CURVE25519_H
45
#include <crypto_scalarmult_curve25519.h>
46
47
48
#elif defined(HAVE_NACL_CRYPTO_SCALARMULT_CURVE25519_H)
#include <nacl/crypto_scalarmult_curve25519.h>
#endif
49
#endif /* defined(USE_CURVE25519_NACL) */
50

51
52
static void pick_curve25519_basepoint_impl(void);

53
54
55
/** This is set to 1 if we have an optimized Ed25519-based
 * implementation for multiplying a value by the basepoint; to 0 if we
 * don't, and to -1 if we haven't checked. */
56
57
static int curve25519_use_ed = -1;

58
59
60
61
62
/**
 * Helper function: call the most appropriate backend to compute the
 * scalar "secret" times the point "point".  Store the result in
 * "output".  Return 0 on success, negative on failure.
 **/
63
STATIC int
64
curve25519_impl(uint8_t *output, const uint8_t *secret,
65
                const uint8_t *point)
66
{
67
68
  uint8_t bp[CURVE25519_PUBKEY_LEN];
  int r;
69
  memcpy(bp, point, CURVE25519_PUBKEY_LEN);
70
71
  /* Clear the high bit, in case our backend foolishly looks at it. */
  bp[31] &= 0x7f;
72
#ifdef USE_CURVE25519_DONNA
73
  r = curve25519_donna(output, secret, bp);
74
#elif defined(USE_CURVE25519_NACL)
75
  r = crypto_scalarmult_curve25519(output, secret, bp);
76
77
#else
#error "No implementation of curve25519 is available."
78
#endif /* defined(USE_CURVE25519_DONNA) || ... */
79
80
  memwipe(bp, 0, sizeof(bp));
  return r;
81
82
}

83
84
85
/**
 * Helper function: Multiply the scalar "secret" by the Curve25519
 * basepoint (X=9), and store the result in "output".  Return 0 on
Nick Mathewson's avatar
Nick Mathewson committed
86
 * success, -1 on failure.
87
 */
88
89
90
91
STATIC int
curve25519_basepoint_impl(uint8_t *output, const uint8_t *secret)
{
  int r = 0;
92
93
  if (BUG(curve25519_use_ed == -1)) {
    /* LCOV_EXCL_START - Only reached if we forgot to call curve25519_init() */
94
    pick_curve25519_basepoint_impl();
95
    /* LCOV_EXCL_STOP */
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
  }

  /* TODO: Someone should benchmark curved25519_scalarmult_basepoint versus
   * an optimized NaCl build to see which should be used when compiled with
   * NaCl available.  I suspected that the ed25519 optimization always wins.
   */
  if (PREDICT_LIKELY(curve25519_use_ed == 1)) {
    curved25519_scalarmult_basepoint_donna(output, secret);
    r = 0;
  } else {
    static const uint8_t basepoint[32] = {9};
    r = curve25519_impl(output, secret, basepoint);
  }
  return r;
}

112
113
114
115
/**
 * Override the decision of whether to use the Ed25519-based basepoint
 * multiply function.  Used for testing.
 */
116
117
118
119
120
121
void
curve25519_set_impl_params(int use_ed)
{
  curve25519_use_ed = use_ed;
}

122
123
124
125
126
127
128
129
130
131
132
/* ==============================
   Part 2: Wrap curve25519_impl with some convenience types and functions.
   ============================== */

/**
 * Return true iff a curve25519_public_key_t seems valid. (It's not necessary
 * to see if the point is on the curve, since the twist is also secure, but we
 * do need to make sure that it isn't the point at infinity.) */
int
curve25519_public_key_is_ok(const curve25519_public_key_t *key)
{
133
  return !safe_mem_is_zero(key->public_key, CURVE25519_PUBKEY_LEN);
134
135
}

136
137
138
139
140
141
142
143
144
/**
 * Generate CURVE25519_SECKEY_LEN random bytes in <b>out</b>. If
 * <b>extra_strong</b> is true, this key is possibly going to get used more
 * than once, so use a better-than-usual RNG. Return 0 on success, -1 on
 * failure.
 *
 * This function does not adjust the output of the RNG at all; the will caller
 * will need to clear or set the appropriate bits to make curve25519 work.
 */
145
int
146
curve25519_rand_seckey_bytes(uint8_t *out, int extra_strong)
147
{
148
149
150
151
152
  if (extra_strong)
    crypto_strongest_rand(out, CURVE25519_SECKEY_LEN);
  else
    crypto_rand((char*)out, CURVE25519_SECKEY_LEN);

153
154
155
156
157
158
159
160
161
162
163
164
165
  return 0;
}

/** Generate a new keypair and return the secret key.  If <b>extra_strong</b>
 * is true, this key is possibly going to get used more than once, so
 * use a better-than-usual RNG. Return 0 on success, -1 on failure. */
int
curve25519_secret_key_generate(curve25519_secret_key_t *key_out,
                               int extra_strong)
{
  if (curve25519_rand_seckey_bytes(key_out->secret_key, extra_strong) < 0)
    return -1;

166
167
168
  key_out->secret_key[0] &= 248;
  key_out->secret_key[31] &= 127;
  key_out->secret_key[31] |= 64;
169
170

  return 0;
171
172
}

173
174
175
176
/**
 * Given a secret key in <b>seckey</b>, create the corresponding public
 * key in <b>key_out</b>.
 */
177
178
179
180
void
curve25519_public_key_generate(curve25519_public_key_t *key_out,
                               const curve25519_secret_key_t *seckey)
{
181
  curve25519_basepoint_impl(key_out->public_key, seckey->secret_key);
182
183
}

184
185
186
187
/**
 * Construct a new keypair in *<b>keypair_out</b>. If <b>extra_strong</b>
 * is true, this key is possibly going to get used more than once, so
 * use a better-than-usual RNG. Return 0 on success, -1 on failure. */
188
int
189
190
191
curve25519_keypair_generate(curve25519_keypair_t *keypair_out,
                            int extra_strong)
{
192
193
  if (curve25519_secret_key_generate(&keypair_out->seckey, extra_strong) < 0)
    return -1;
194
  curve25519_public_key_generate(&keypair_out->pubkey, &keypair_out->seckey);
195
  return 0;
196
197
}

198
199
200
201
202
203
204
/** Store the keypair <b>keypair</b>, including its secret and public
 * parts, to the file <b>fname</b>.  Use the string tag <b>tag</b> to
 * distinguish this from other Curve25519 keypairs. Return 0 on success,
 * -1 on failure.
 *
 * See crypto_write_tagged_contents_to_file() for more information on
 * the metaformat used for these keys.*/
205
206
207
208
209
210
211
int
curve25519_keypair_write_to_file(const curve25519_keypair_t *keypair,
                                 const char *fname,
                                 const char *tag)
{
  uint8_t contents[CURVE25519_SECKEY_LEN + CURVE25519_PUBKEY_LEN];
  int r;
212

213
214
215
216
217
218
219
220
221
222
223
224
225
226
  memcpy(contents, keypair->seckey.secret_key, CURVE25519_SECKEY_LEN);
  memcpy(contents+CURVE25519_SECKEY_LEN,
         keypair->pubkey.public_key, CURVE25519_PUBKEY_LEN);

  r = crypto_write_tagged_contents_to_file(fname,
                                           "c25519v1",
                                           tag,
                                           contents,
                                           sizeof(contents));

  memwipe(contents, 0, sizeof(contents));
  return r;
}

227
228
229
230
/** Read a curve25519 keypair from a file named <b>fname</b> created by
 * curve25519_keypair_write_to_file(). Store the keypair in
 * <b>keypair_out</b>, and the associated tag string in <b>tag_out</b>.
 * Return 0 on success, and -1 on failure. */
231
232
233
234
235
236
237
238
239
240
241
242
243
244
int
curve25519_keypair_read_from_file(curve25519_keypair_t *keypair_out,
                                  char **tag_out,
                                  const char *fname)
{
  uint8_t content[CURVE25519_SECKEY_LEN + CURVE25519_PUBKEY_LEN];
  ssize_t len;
  int r = -1;

  len = crypto_read_tagged_contents_from_file(fname, "c25519v1", tag_out,
                                              content, sizeof(content));
  if (len != sizeof(content))
    goto end;

245
  /* Make sure that the public key matches the secret key */
246
  memcpy(keypair_out->seckey.secret_key, content, CURVE25519_SECKEY_LEN);
247
248
  curve25519_public_key_generate(&keypair_out->pubkey, &keypair_out->seckey);
  if (tor_memneq(keypair_out->pubkey.public_key,
249
                 content + CURVE25519_SECKEY_LEN,
250
251
252
253
254
255
                 CURVE25519_PUBKEY_LEN))
    goto end;

  r = 0;

 end:
256
  memwipe(content, 0, sizeof(content));
257
258
259
260
261
262
263
  if (r != 0) {
    memset(keypair_out, 0, sizeof(*keypair_out));
    tor_free(*tag_out);
  }
  return r;
}

264
265
266
267
268
269
270
271
272
273
/** Perform the curve25519 ECDH handshake with <b>skey</b> and <b>pkey</b>,
 * writing CURVE25519_OUTPUT_LEN bytes of output into <b>output</b>. */
void
curve25519_handshake(uint8_t *output,
                     const curve25519_secret_key_t *skey,
                     const curve25519_public_key_t *pkey)
{
  curve25519_impl(output, skey->secret_key, pkey->public_key);
}

274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
/** Check whether the ed25519-based curve25519 basepoint optimization seems to
 * be working. If so, return 0; otherwise return -1. */
static int
curve25519_basepoint_spot_check(void)
{
  static const uint8_t alicesk[32] = {
    0x77,0x07,0x6d,0x0a,0x73,0x18,0xa5,0x7d,
    0x3c,0x16,0xc1,0x72,0x51,0xb2,0x66,0x45,
    0xdf,0x4c,0x2f,0x87,0xeb,0xc0,0x99,0x2a,
    0xb1,0x77,0xfb,0xa5,0x1d,0xb9,0x2c,0x2a
  };
  static const uint8_t alicepk[32] = {
    0x85,0x20,0xf0,0x09,0x89,0x30,0xa7,0x54,
    0x74,0x8b,0x7d,0xdc,0xb4,0x3e,0xf7,0x5a,
    0x0d,0xbf,0x3a,0x0d,0x26,0x38,0x1a,0xf4,
    0xeb,0xa4,0xa9,0x8e,0xaa,0x9b,0x4e,0x6a
  };
  const int loop_max=200;
  int save_use_ed = curve25519_use_ed;
  unsigned char e1[32] = { 5 };
  unsigned char e2[32] = { 5 };
  unsigned char x[32],y[32];
  int i;
  int r=0;

  /* Check the most basic possible sanity via the test secret/public key pair
   * used in "Cryptography in NaCl - 2. Secret keys and public keys".  This
Nick Mathewson's avatar
Nick Mathewson committed
301
   * may catch catastrophic failures on systems where Curve25519 is expensive,
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
   * without requiring a ton of key generation.
   */
  curve25519_use_ed = 1;
  r |= curve25519_basepoint_impl(x, alicesk);
  if (fast_memneq(x, alicepk, 32))
    goto fail;

  /* Ok, the optimization appears to produce passable results, try a few more
   * values, maybe there's something subtle wrong.
   */
  for (i = 0; i < loop_max; ++i) {
    curve25519_use_ed = 0;
    r |= curve25519_basepoint_impl(x, e1);
    curve25519_use_ed = 1;
    r |= curve25519_basepoint_impl(y, e2);
    if (fast_memneq(x,y,32))
      goto fail;
    memcpy(e1, x, 32);
    memcpy(e2, x, 32);
  }

  goto end;
324
325
 // LCOV_EXCL_START -- we can only hit this code if there is a bug in our
 // curve25519-basepoint implementation.
326
327
 fail:
  r = -1;
328
 // LCOV_EXCL_STOP
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
 end:
  curve25519_use_ed = save_use_ed;
  return r;
}

/** Choose whether to use the ed25519-based curve25519-basepoint
 * implementation. */
static void
pick_curve25519_basepoint_impl(void)
{
  curve25519_use_ed = 1;

  if (curve25519_basepoint_spot_check() == 0)
    return;

344
345
346
  /* LCOV_EXCL_START
   * only reachable if our basepoint implementation broken */
  log_warn(LD_BUG|LD_CRYPTO, "The ed25519-based curve25519 basepoint "
347
348
349
           "multiplication seems broken; using the curve25519 "
           "implementation.");
  curve25519_use_ed = 0;
350
  /* LCOV_EXCL_STOP */
351
352
353
354
355
356
357
358
359
360
}

/** Initialize the curve25519 implementations. This is necessary if you're
 * going to use them in a multithreaded setting, and not otherwise. */
void
curve25519_init(void)
{
  pick_curve25519_basepoint_impl();
}