crypto_curve25519.c 11 KB
Newer Older
Nick Mathewson's avatar
Nick Mathewson committed
1
/* Copyright (c) 2012-2016, 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 "util.h"
28
#include "torlog.h"
29

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

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

48
49
static void pick_curve25519_basepoint_impl(void);

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

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

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

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

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

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

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

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

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

  return 0;
168
169
}

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

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

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

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

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

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

  r = 0;

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

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

271
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
/** 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
298
   * may catch catastrophic failures on systems where Curve25519 is expensive,
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
   * 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;
 fail:
  r = -1;
 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;

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

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