crypto_curve25519.c 11.2 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
#include "util.h"
29
#include "torlog.h"
30

31
32
#include "ed25519/donna/ed25519_donna_tor.h"

33
34
35
36
37
38
39
40
41
/* ==============================
   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
42
#ifdef HAVE_CRYPTO_SCALARMULT_CURVE25519_H
43
#include <crypto_scalarmult_curve25519.h>
44
45
46
#elif defined(HAVE_NACL_CRYPTO_SCALARMULT_CURVE25519_H)
#include <nacl/crypto_scalarmult_curve25519.h>
#endif
47
#endif /* defined(USE_CURVE25519_NACL) */
48

49
50
static void pick_curve25519_basepoint_impl(void);

51
52
53
/** 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. */
54
55
static int curve25519_use_ed = -1;

56
57
58
59
60
/**
 * 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.
 **/
61
STATIC int
62
curve25519_impl(uint8_t *output, const uint8_t *secret,
63
                const uint8_t *point)
64
{
65
66
  uint8_t bp[CURVE25519_PUBKEY_LEN];
  int r;
67
  memcpy(bp, point, CURVE25519_PUBKEY_LEN);
68
69
  /* Clear the high bit, in case our backend foolishly looks at it. */
  bp[31] &= 0x7f;
70
#ifdef USE_CURVE25519_DONNA
71
  r = curve25519_donna(output, secret, bp);
72
#elif defined(USE_CURVE25519_NACL)
73
  r = crypto_scalarmult_curve25519(output, secret, bp);
74
75
#else
#error "No implementation of curve25519 is available."
76
#endif /* defined(USE_CURVE25519_DONNA) || ... */
77
78
  memwipe(bp, 0, sizeof(bp));
  return r;
79
80
}

81
82
83
/**
 * 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
84
 * success, -1 on failure.
85
 */
86
87
88
89
STATIC int
curve25519_basepoint_impl(uint8_t *output, const uint8_t *secret)
{
  int r = 0;
90
91
  if (BUG(curve25519_use_ed == -1)) {
    /* LCOV_EXCL_START - Only reached if we forgot to call curve25519_init() */
92
    pick_curve25519_basepoint_impl();
93
    /* LCOV_EXCL_STOP */
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
  }

  /* 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;
}

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

120
121
122
123
124
125
126
127
128
129
130
/* ==============================
   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)
{
131
  return !safe_mem_is_zero(key->public_key, CURVE25519_PUBKEY_LEN);
132
133
}

134
135
136
137
138
139
140
141
142
/**
 * 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.
 */
143
int
144
curve25519_rand_seckey_bytes(uint8_t *out, int extra_strong)
145
{
146
147
148
149
150
  if (extra_strong)
    crypto_strongest_rand(out, CURVE25519_SECKEY_LEN);
  else
    crypto_rand((char*)out, CURVE25519_SECKEY_LEN);

151
152
153
154
155
156
157
158
159
160
161
162
163
  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;

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

  return 0;
169
170
}

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

182
183
184
185
/**
 * 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. */
186
int
187
188
189
curve25519_keypair_generate(curve25519_keypair_t *keypair_out,
                            int extra_strong)
{
190
191
  if (curve25519_secret_key_generate(&keypair_out->seckey, extra_strong) < 0)
    return -1;
192
  curve25519_public_key_generate(&keypair_out->pubkey, &keypair_out->seckey);
193
  return 0;
194
195
}

196
197
198
199
200
201
202
/** 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.*/
203
204
205
206
207
208
209
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;
210

211
212
213
214
215
216
217
218
219
220
221
222
223
224
  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;
}

225
226
227
228
/** 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. */
229
230
231
232
233
234
235
236
237
238
239
240
241
242
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;

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

  r = 0;

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

262
263
264
265
266
267
268
269
270
271
/** 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);
}

272
273
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
/** 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
299
   * may catch catastrophic failures on systems where Curve25519 is expensive,
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
   * 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;
322
323
 // LCOV_EXCL_START -- we can only hit this code if there is a bug in our
 // curve25519-basepoint implementation.
324
325
 fail:
  r = -1;
326
 // LCOV_EXCL_STOP
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
 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;

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

/** 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();
}