Line data Source code
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 104226 : curve25519_impl(uint8_t *output, const uint8_t *secret,
66 : const uint8_t *point)
67 : {
68 104226 : uint8_t bp[CURVE25519_PUBKEY_LEN];
69 104226 : int r;
70 104226 : memcpy(bp, point, CURVE25519_PUBKEY_LEN);
71 : /* Clear the high bit, in case our backend foolishly looks at it. */
72 104226 : bp[31] &= 0x7f;
73 : #ifdef USE_CURVE25519_DONNA
74 104226 : 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 103999 : memwipe(bp, 0, sizeof(bp));
81 103884 : 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 127883 : curve25519_basepoint_impl(uint8_t *output, const uint8_t *secret)
91 : {
92 127883 : int r = 0;
93 127883 : 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 127883 : if (PREDICT_LIKELY(curve25519_use_ed == 1)) {
104 81347 : curved25519_scalarmult_basepoint_donna(output, secret);
105 81347 : r = 0;
106 : } else {
107 46536 : static const uint8_t basepoint[32] = {9};
108 46536 : r = curve25519_impl(output, secret, basepoint);
109 : }
110 127883 : 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 4096 : curve25519_set_impl_params(int use_ed)
119 : {
120 4096 : curve25519_use_ed = use_ed;
121 4096 : }
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 46 : curve25519_public_key_is_ok(const curve25519_public_key_t *key)
133 : {
134 46 : 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 29279 : curve25519_rand_seckey_bytes(uint8_t *out, int extra_strong)
148 : {
149 29279 : if (extra_strong)
150 1067 : crypto_strongest_rand(out, CURVE25519_SECKEY_LEN);
151 : else
152 28212 : crypto_rand((char*)out, CURVE25519_SECKEY_LEN);
153 :
154 29279 : 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 29279 : curve25519_secret_key_generate(curve25519_secret_key_t *key_out,
162 : int extra_strong)
163 : {
164 29279 : if (curve25519_rand_seckey_bytes(key_out->secret_key, extra_strong) < 0)
165 : return -1;
166 :
167 29279 : key_out->secret_key[0] &= 248;
168 29279 : key_out->secret_key[31] &= 127;
169 29279 : key_out->secret_key[31] |= 64;
170 :
171 29279 : 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 29248 : curve25519_public_key_generate(curve25519_public_key_t *key_out,
180 : const curve25519_secret_key_t *seckey)
181 : {
182 29248 : curve25519_basepoint_impl(key_out->public_key, seckey->secret_key);
183 29248 : }
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 2302 : curve25519_keypair_generate(curve25519_keypair_t *keypair_out,
191 : int extra_strong)
192 : {
193 2302 : if (curve25519_secret_key_generate(&keypair_out->seckey, extra_strong) < 0)
194 : return -1;
195 2302 : curve25519_public_key_generate(&keypair_out->pubkey, &keypair_out->seckey);
196 2302 : 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 13 : curve25519_keypair_write_to_file(const curve25519_keypair_t *keypair,
208 : const char *fname,
209 : const char *tag)
210 : {
211 13 : uint8_t contents[CURVE25519_SECKEY_LEN + CURVE25519_PUBKEY_LEN];
212 13 : int r;
213 :
214 13 : memcpy(contents, keypair->seckey.secret_key, CURVE25519_SECKEY_LEN);
215 13 : memcpy(contents+CURVE25519_SECKEY_LEN,
216 13 : keypair->pubkey.public_key, CURVE25519_PUBKEY_LEN);
217 :
218 13 : r = crypto_write_tagged_contents_to_file(fname,
219 : "c25519v1",
220 : tag,
221 : contents,
222 : sizeof(contents));
223 :
224 13 : memwipe(contents, 0, sizeof(contents));
225 13 : 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 10 : curve25519_keypair_read_from_file(curve25519_keypair_t *keypair_out,
234 : char **tag_out,
235 : const char *fname)
236 : {
237 10 : uint8_t content[CURVE25519_SECKEY_LEN + CURVE25519_PUBKEY_LEN];
238 10 : ssize_t len;
239 10 : int r = -1;
240 :
241 10 : len = crypto_read_tagged_contents_from_file(fname, "c25519v1", tag_out,
242 : content, sizeof(content));
243 10 : if (len != sizeof(content))
244 1 : goto end;
245 :
246 : /* Make sure that the public key matches the secret key */
247 9 : memcpy(keypair_out->seckey.secret_key, content, CURVE25519_SECKEY_LEN);
248 9 : curve25519_public_key_generate(&keypair_out->pubkey, &keypair_out->seckey);
249 9 : if (tor_memneq(keypair_out->pubkey.public_key,
250 : content + CURVE25519_SECKEY_LEN,
251 : CURVE25519_PUBKEY_LEN))
252 1 : goto end;
253 :
254 : r = 0;
255 :
256 10 : end:
257 10 : memwipe(content, 0, sizeof(content));
258 10 : if (r != 0) {
259 2 : memset(keypair_out, 0, sizeof(*keypair_out));
260 2 : tor_free(*tag_out);
261 : }
262 10 : 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 56088 : curve25519_handshake(uint8_t *output,
269 : const curve25519_secret_key_t *skey,
270 : const curve25519_public_key_t *pkey)
271 : {
272 56088 : curve25519_impl(output, skey->secret_key, pkey->public_key);
273 55510 : }
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 5561 : curve25519_basepoint_spot_check(void)
279 : {
280 5561 : 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 5561 : 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 5561 : const int loop_max=8;
293 5561 : int save_use_ed = curve25519_use_ed;
294 5561 : unsigned char e1[32], e2[32];
295 5561 : unsigned char x[32],y[32];
296 5561 : int i;
297 5561 : int r=0;
298 :
299 5561 : memset(x, 0, sizeof(x));
300 5561 : memset(y, 0, sizeof(y));
301 5561 : memset(e1, 0, sizeof(e1));
302 5561 : memset(e2, 0, sizeof(e2));
303 5561 : e1[0]=5;
304 5561 : 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 5561 : curve25519_use_ed = 1;
312 5561 : r |= curve25519_basepoint_impl(x, alicesk);
313 5561 : if (fast_memneq(x, alicepk, 32))
314 0 : 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 50049 : for (i = 0; i < loop_max; ++i) {
320 44488 : curve25519_use_ed = 0;
321 44488 : r |= curve25519_basepoint_impl(x, e1);
322 44488 : curve25519_use_ed = 1;
323 44488 : r |= curve25519_basepoint_impl(y, e2);
324 44488 : if (fast_memneq(x,y,32))
325 0 : goto fail;
326 44488 : memcpy(e1, x, 32);
327 44488 : memcpy(e2, x, 32);
328 : }
329 :
330 5561 : 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 5561 : end:
337 5561 : curve25519_use_ed = save_use_ed;
338 5561 : return r;
339 : }
340 :
341 : /** Choose whether to use the ed25519-based curve25519-basepoint
342 : * implementation. */
343 : static void
344 5561 : pick_curve25519_basepoint_impl(void)
345 : {
346 5561 : curve25519_use_ed = 1;
347 :
348 5561 : 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 5561 : curve25519_init(void)
364 : {
365 5561 : pick_curve25519_basepoint_impl();
366 5561 : }
|
