Branch data Line data Source code
1 : : /*
2 : : * Elliptic curve DSA
3 : : *
4 : : * Copyright The Mbed TLS Contributors
5 : : * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
6 : : */
7 : :
8 : : /*
9 : : * References:
10 : : *
11 : : * SEC1 https://www.secg.org/sec1-v2.pdf
12 : : */
13 : :
14 : : #include "common.h"
15 : :
16 : : #if defined(MBEDTLS_ECDSA_C)
17 : :
18 : : #include "mbedtls/ecdsa.h"
19 : : #include "mbedtls/asn1write.h"
20 : : #include "bignum_internal.h"
21 : :
22 : : #include <string.h>
23 : :
24 : : #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
25 : : #include "mbedtls/hmac_drbg.h"
26 : : #endif
27 : :
28 : : #include "mbedtls/platform.h"
29 : :
30 : : #include "mbedtls/platform_util.h"
31 : : #include "mbedtls/error.h"
32 : :
33 : : #if defined(MBEDTLS_ECP_RESTARTABLE)
34 : :
35 : : /*
36 : : * Sub-context for ecdsa_verify()
37 : : */
38 : : struct mbedtls_ecdsa_restart_ver {
39 : : mbedtls_mpi u1, u2; /* intermediate values */
40 : : enum { /* what to do next? */
41 : : ecdsa_ver_init = 0, /* getting started */
42 : : ecdsa_ver_muladd, /* muladd step */
43 : : } state;
44 : : };
45 : :
46 : : /*
47 : : * Init verify restart sub-context
48 : : */
49 : : static void ecdsa_restart_ver_init(mbedtls_ecdsa_restart_ver_ctx *ctx)
50 : : {
51 : : mbedtls_mpi_init(&ctx->u1);
52 : : mbedtls_mpi_init(&ctx->u2);
53 : : ctx->state = ecdsa_ver_init;
54 : : }
55 : :
56 : : /*
57 : : * Free the components of a verify restart sub-context
58 : : */
59 : : static void ecdsa_restart_ver_free(mbedtls_ecdsa_restart_ver_ctx *ctx)
60 : : {
61 : : if (ctx == NULL) {
62 : : return;
63 : : }
64 : :
65 : : mbedtls_mpi_free(&ctx->u1);
66 : : mbedtls_mpi_free(&ctx->u2);
67 : :
68 : : ecdsa_restart_ver_init(ctx);
69 : : }
70 : :
71 : : /*
72 : : * Sub-context for ecdsa_sign()
73 : : */
74 : : struct mbedtls_ecdsa_restart_sig {
75 : : int sign_tries;
76 : : int key_tries;
77 : : mbedtls_mpi k; /* per-signature random */
78 : : mbedtls_mpi r; /* r value */
79 : : enum { /* what to do next? */
80 : : ecdsa_sig_init = 0, /* getting started */
81 : : ecdsa_sig_mul, /* doing ecp_mul() */
82 : : ecdsa_sig_modn, /* mod N computations */
83 : : } state;
84 : : };
85 : :
86 : : /*
87 : : * Init verify sign sub-context
88 : : */
89 : : static void ecdsa_restart_sig_init(mbedtls_ecdsa_restart_sig_ctx *ctx)
90 : : {
91 : : ctx->sign_tries = 0;
92 : : ctx->key_tries = 0;
93 : : mbedtls_mpi_init(&ctx->k);
94 : : mbedtls_mpi_init(&ctx->r);
95 : : ctx->state = ecdsa_sig_init;
96 : : }
97 : :
98 : : /*
99 : : * Free the components of a sign restart sub-context
100 : : */
101 : : static void ecdsa_restart_sig_free(mbedtls_ecdsa_restart_sig_ctx *ctx)
102 : : {
103 : : if (ctx == NULL) {
104 : : return;
105 : : }
106 : :
107 : : mbedtls_mpi_free(&ctx->k);
108 : : mbedtls_mpi_free(&ctx->r);
109 : : }
110 : :
111 : : #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
112 : : /*
113 : : * Sub-context for ecdsa_sign_det()
114 : : */
115 : : struct mbedtls_ecdsa_restart_det {
116 : : mbedtls_hmac_drbg_context rng_ctx; /* DRBG state */
117 : : enum { /* what to do next? */
118 : : ecdsa_det_init = 0, /* getting started */
119 : : ecdsa_det_sign, /* make signature */
120 : : } state;
121 : : };
122 : :
123 : : /*
124 : : * Init verify sign_det sub-context
125 : : */
126 : : static void ecdsa_restart_det_init(mbedtls_ecdsa_restart_det_ctx *ctx)
127 : : {
128 : : mbedtls_hmac_drbg_init(&ctx->rng_ctx);
129 : : ctx->state = ecdsa_det_init;
130 : : }
131 : :
132 : : /*
133 : : * Free the components of a sign_det restart sub-context
134 : : */
135 : : static void ecdsa_restart_det_free(mbedtls_ecdsa_restart_det_ctx *ctx)
136 : : {
137 : : if (ctx == NULL) {
138 : : return;
139 : : }
140 : :
141 : : mbedtls_hmac_drbg_free(&ctx->rng_ctx);
142 : :
143 : : ecdsa_restart_det_init(ctx);
144 : : }
145 : : #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
146 : :
147 : : #define ECDSA_RS_ECP (rs_ctx == NULL ? NULL : &rs_ctx->ecp)
148 : :
149 : : /* Utility macro for checking and updating ops budget */
150 : : #define ECDSA_BUDGET(ops) \
151 : : MBEDTLS_MPI_CHK(mbedtls_ecp_check_budget(grp, ECDSA_RS_ECP, ops));
152 : :
153 : : /* Call this when entering a function that needs its own sub-context */
154 : : #define ECDSA_RS_ENTER(SUB) do { \
155 : : /* reset ops count for this call if top-level */ \
156 : : if (rs_ctx != NULL && rs_ctx->ecp.depth++ == 0) \
157 : : rs_ctx->ecp.ops_done = 0; \
158 : : \
159 : : /* set up our own sub-context if needed */ \
160 : : if (mbedtls_ecp_restart_is_enabled() && \
161 : : rs_ctx != NULL && rs_ctx->SUB == NULL) \
162 : : { \
163 : : rs_ctx->SUB = mbedtls_calloc(1, sizeof(*rs_ctx->SUB)); \
164 : : if (rs_ctx->SUB == NULL) \
165 : : return MBEDTLS_ERR_ECP_ALLOC_FAILED; \
166 : : \
167 : : ecdsa_restart_## SUB ##_init(rs_ctx->SUB); \
168 : : } \
169 : : } while (0)
170 : :
171 : : /* Call this when leaving a function that needs its own sub-context */
172 : : #define ECDSA_RS_LEAVE(SUB) do { \
173 : : /* clear our sub-context when not in progress (done or error) */ \
174 : : if (rs_ctx != NULL && rs_ctx->SUB != NULL && \
175 : : ret != MBEDTLS_ERR_ECP_IN_PROGRESS) \
176 : : { \
177 : : ecdsa_restart_## SUB ##_free(rs_ctx->SUB); \
178 : : mbedtls_free(rs_ctx->SUB); \
179 : : rs_ctx->SUB = NULL; \
180 : : } \
181 : : \
182 : : if (rs_ctx != NULL) \
183 : : rs_ctx->ecp.depth--; \
184 : : } while (0)
185 : :
186 : : #else /* MBEDTLS_ECP_RESTARTABLE */
187 : :
188 : : #define ECDSA_RS_ECP NULL
189 : :
190 : : #define ECDSA_BUDGET(ops) /* no-op; for compatibility */
191 : :
192 : : #define ECDSA_RS_ENTER(SUB) (void) rs_ctx
193 : : #define ECDSA_RS_LEAVE(SUB) (void) rs_ctx
194 : :
195 : : #endif /* MBEDTLS_ECP_RESTARTABLE */
196 : :
197 : : #if defined(MBEDTLS_ECDSA_DETERMINISTIC) || \
198 : : !defined(MBEDTLS_ECDSA_SIGN_ALT) || \
199 : : !defined(MBEDTLS_ECDSA_VERIFY_ALT)
200 : : /*
201 : : * Derive a suitable integer for group grp from a buffer of length len
202 : : * SEC1 4.1.3 step 5 aka SEC1 4.1.4 step 3
203 : : */
204 : 10 : static int derive_mpi(const mbedtls_ecp_group *grp, mbedtls_mpi *x,
205 : : const unsigned char *buf, size_t blen)
206 : : {
207 : 10 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
208 : 10 : size_t n_size = (grp->nbits + 7) / 8;
209 : 10 : size_t use_size = blen > n_size ? n_size : blen;
210 : :
211 [ - + ]: 10 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(x, buf, use_size));
212 [ - + ]: 10 : if (use_size * 8 > grp->nbits) {
213 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(x, use_size * 8 - grp->nbits));
214 : : }
215 : :
216 : : /* While at it, reduce modulo N */
217 [ + - ]: 10 : if (mbedtls_mpi_cmp_mpi(x, &grp->N) >= 0) {
218 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(x, x, &grp->N));
219 : : }
220 : :
221 : 10 : cleanup:
222 : 10 : return ret;
223 : : }
224 : : #endif /* ECDSA_DETERMINISTIC || !ECDSA_SIGN_ALT || !ECDSA_VERIFY_ALT */
225 : :
226 : 10 : int mbedtls_ecdsa_can_do(mbedtls_ecp_group_id gid)
227 : : {
228 : 10 : switch (gid) {
229 : : #ifdef MBEDTLS_ECP_DP_CURVE25519_ENABLED
230 : : case MBEDTLS_ECP_DP_CURVE25519: return 0;
231 : : #endif
232 : : #ifdef MBEDTLS_ECP_DP_CURVE448_ENABLED
233 : : case MBEDTLS_ECP_DP_CURVE448: return 0;
234 : : #endif
235 : 10 : default: return 1;
236 : : }
237 : : }
238 : :
239 : : #if !defined(MBEDTLS_ECDSA_SIGN_ALT)
240 : : /*
241 : : * Compute ECDSA signature of a hashed message (SEC1 4.1.3)
242 : : * Obviously, compared to SEC1 4.1.3, we skip step 4 (hash message)
243 : : */
244 : 4 : int mbedtls_ecdsa_sign_restartable(mbedtls_ecp_group *grp,
245 : : mbedtls_mpi *r, mbedtls_mpi *s,
246 : : const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
247 : : int (*f_rng)(void *, unsigned char *, size_t), void *p_rng,
248 : : int (*f_rng_blind)(void *, unsigned char *, size_t),
249 : : void *p_rng_blind,
250 : : mbedtls_ecdsa_restart_ctx *rs_ctx)
251 : : {
252 : 4 : int ret, key_tries, sign_tries;
253 : 4 : int *p_sign_tries = &sign_tries, *p_key_tries = &key_tries;
254 : 4 : mbedtls_ecp_point R;
255 : 4 : mbedtls_mpi k, e;
256 : 4 : mbedtls_mpi *pk = &k, *pr = r;
257 : :
258 : : /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
259 [ + - + - ]: 4 : if (!mbedtls_ecdsa_can_do(grp->id) || grp->N.p == NULL) {
260 : : return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
261 : : }
262 : :
263 : : /* Make sure d is in range 1..n-1 */
264 [ + - - + ]: 4 : if (mbedtls_mpi_cmp_int(d, 1) < 0 || mbedtls_mpi_cmp_mpi(d, &grp->N) >= 0) {
265 : 0 : return MBEDTLS_ERR_ECP_INVALID_KEY;
266 : : }
267 : :
268 : 4 : mbedtls_ecp_point_init(&R);
269 : 4 : mbedtls_mpi_init(&k); mbedtls_mpi_init(&e);
270 : :
271 : 4 : ECDSA_RS_ENTER(sig);
272 : :
273 : : #if defined(MBEDTLS_ECP_RESTARTABLE)
274 : : if (rs_ctx != NULL && rs_ctx->sig != NULL) {
275 : : /* redirect to our context */
276 : : p_sign_tries = &rs_ctx->sig->sign_tries;
277 : : p_key_tries = &rs_ctx->sig->key_tries;
278 : : pk = &rs_ctx->sig->k;
279 : : pr = &rs_ctx->sig->r;
280 : :
281 : : /* jump to current step */
282 : : if (rs_ctx->sig->state == ecdsa_sig_mul) {
283 : : goto mul;
284 : : }
285 : : if (rs_ctx->sig->state == ecdsa_sig_modn) {
286 : : goto modn;
287 : : }
288 : : }
289 : : #endif /* MBEDTLS_ECP_RESTARTABLE */
290 : :
291 : 4 : *p_sign_tries = 0;
292 : 4 : do {
293 [ - + ]: 4 : if ((*p_sign_tries)++ > 10) {
294 : 0 : ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
295 : 0 : goto cleanup;
296 : : }
297 : :
298 : : /*
299 : : * Steps 1-3: generate a suitable ephemeral keypair
300 : : * and set r = xR mod n
301 : : */
302 : : *p_key_tries = 0;
303 : 4 : do {
304 [ - + ]: 4 : if ((*p_key_tries)++ > 10) {
305 : 0 : ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
306 : 0 : goto cleanup;
307 : : }
308 : :
309 [ - + ]: 4 : MBEDTLS_MPI_CHK(mbedtls_ecp_gen_privkey(grp, pk, f_rng, p_rng));
310 : :
311 : : #if defined(MBEDTLS_ECP_RESTARTABLE)
312 : : if (rs_ctx != NULL && rs_ctx->sig != NULL) {
313 : : rs_ctx->sig->state = ecdsa_sig_mul;
314 : : }
315 : :
316 : : mul:
317 : : #endif
318 [ - + ]: 4 : MBEDTLS_MPI_CHK(mbedtls_ecp_mul_restartable(grp, &R, pk, &grp->G,
319 : : f_rng_blind,
320 : : p_rng_blind,
321 : : ECDSA_RS_ECP));
322 [ - + ]: 4 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(pr, &R.X, &grp->N));
323 [ - + ]: 4 : } while (mbedtls_mpi_cmp_int(pr, 0) == 0);
324 : :
325 : : #if defined(MBEDTLS_ECP_RESTARTABLE)
326 : : if (rs_ctx != NULL && rs_ctx->sig != NULL) {
327 : : rs_ctx->sig->state = ecdsa_sig_modn;
328 : : }
329 : :
330 : : modn:
331 : : #endif
332 : : /*
333 : : * Accounting for everything up to the end of the loop
334 : : * (step 6, but checking now avoids saving e and t)
335 : : */
336 : 4 : ECDSA_BUDGET(MBEDTLS_ECP_OPS_INV + 4);
337 : :
338 : : /*
339 : : * Step 5: derive MPI from hashed message
340 : : */
341 [ - + ]: 4 : MBEDTLS_MPI_CHK(derive_mpi(grp, &e, buf, blen));
342 : :
343 : : /*
344 : : * Step 6: compute s = (e + r * d) / k
345 : : */
346 [ - + ]: 4 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(s, pr, d));
347 [ - + ]: 4 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&e, &e, s));
348 [ - + ]: 4 : MBEDTLS_MPI_CHK(mbedtls_mpi_gcd_modinv_odd(NULL, s, pk, &grp->N));
349 [ - + ]: 4 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(s, s, &e));
350 [ - + ]: 4 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(s, s, &grp->N));
351 [ - + ]: 4 : } while (mbedtls_mpi_cmp_int(s, 0) == 0);
352 : :
353 : : #if defined(MBEDTLS_ECP_RESTARTABLE)
354 : : if (rs_ctx != NULL && rs_ctx->sig != NULL) {
355 : : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(r, pr));
356 : : }
357 : : #endif
358 : :
359 : 4 : cleanup:
360 : 4 : mbedtls_ecp_point_free(&R);
361 : 4 : mbedtls_mpi_free(&k); mbedtls_mpi_free(&e);
362 : :
363 : 4 : ECDSA_RS_LEAVE(sig);
364 : :
365 : 4 : return ret;
366 : : }
367 : :
368 : : /*
369 : : * Compute ECDSA signature of a hashed message
370 : : */
371 : 4 : int mbedtls_ecdsa_sign(mbedtls_ecp_group *grp, mbedtls_mpi *r, mbedtls_mpi *s,
372 : : const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
373 : : int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
374 : : {
375 : : /* Use the same RNG for both blinding and ephemeral key generation */
376 : 4 : return mbedtls_ecdsa_sign_restartable(grp, r, s, d, buf, blen,
377 : : f_rng, p_rng, f_rng, p_rng, NULL);
378 : : }
379 : : #endif /* !MBEDTLS_ECDSA_SIGN_ALT */
380 : :
381 : : #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
382 : : /*
383 : : * Deterministic signature wrapper
384 : : *
385 : : * note: The f_rng_blind parameter must not be NULL.
386 : : *
387 : : */
388 : : int mbedtls_ecdsa_sign_det_restartable(mbedtls_ecp_group *grp,
389 : : mbedtls_mpi *r, mbedtls_mpi *s,
390 : : const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
391 : : mbedtls_md_type_t md_alg,
392 : : int (*f_rng_blind)(void *, unsigned char *, size_t),
393 : : void *p_rng_blind,
394 : : mbedtls_ecdsa_restart_ctx *rs_ctx)
395 : : {
396 : : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
397 : : mbedtls_hmac_drbg_context rng_ctx;
398 : : mbedtls_hmac_drbg_context *p_rng = &rng_ctx;
399 : : unsigned char data[2 * MBEDTLS_ECP_MAX_BYTES];
400 : : size_t grp_len = (grp->nbits + 7) / 8;
401 : : const mbedtls_md_info_t *md_info;
402 : : mbedtls_mpi h;
403 : :
404 : : if ((md_info = mbedtls_md_info_from_type(md_alg)) == NULL) {
405 : : return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
406 : : }
407 : :
408 : : mbedtls_mpi_init(&h);
409 : : mbedtls_hmac_drbg_init(&rng_ctx);
410 : :
411 : : ECDSA_RS_ENTER(det);
412 : :
413 : : #if defined(MBEDTLS_ECP_RESTARTABLE)
414 : : if (rs_ctx != NULL && rs_ctx->det != NULL) {
415 : : /* redirect to our context */
416 : : p_rng = &rs_ctx->det->rng_ctx;
417 : :
418 : : /* jump to current step */
419 : : if (rs_ctx->det->state == ecdsa_det_sign) {
420 : : goto sign;
421 : : }
422 : : }
423 : : #endif /* MBEDTLS_ECP_RESTARTABLE */
424 : :
425 : : /* Use private key and message hash (reduced) to initialize HMAC_DRBG */
426 : : MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(d, data, grp_len));
427 : : MBEDTLS_MPI_CHK(derive_mpi(grp, &h, buf, blen));
428 : : MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&h, data + grp_len, grp_len));
429 : : MBEDTLS_MPI_CHK(mbedtls_hmac_drbg_seed_buf(p_rng, md_info, data, 2 * grp_len));
430 : :
431 : : #if defined(MBEDTLS_ECP_RESTARTABLE)
432 : : if (rs_ctx != NULL && rs_ctx->det != NULL) {
433 : : rs_ctx->det->state = ecdsa_det_sign;
434 : : }
435 : :
436 : : sign:
437 : : #endif
438 : : #if defined(MBEDTLS_ECDSA_SIGN_ALT)
439 : : (void) f_rng_blind;
440 : : (void) p_rng_blind;
441 : : ret = mbedtls_ecdsa_sign(grp, r, s, d, buf, blen,
442 : : mbedtls_hmac_drbg_random, p_rng);
443 : : #else
444 : : ret = mbedtls_ecdsa_sign_restartable(grp, r, s, d, buf, blen,
445 : : mbedtls_hmac_drbg_random, p_rng,
446 : : f_rng_blind, p_rng_blind, rs_ctx);
447 : : #endif /* MBEDTLS_ECDSA_SIGN_ALT */
448 : :
449 : : cleanup:
450 : : mbedtls_hmac_drbg_free(&rng_ctx);
451 : : mbedtls_mpi_free(&h);
452 : :
453 : : ECDSA_RS_LEAVE(det);
454 : :
455 : : return ret;
456 : : }
457 : :
458 : : /*
459 : : * Deterministic signature wrapper
460 : : */
461 : : int mbedtls_ecdsa_sign_det_ext(mbedtls_ecp_group *grp, mbedtls_mpi *r,
462 : : mbedtls_mpi *s, const mbedtls_mpi *d,
463 : : const unsigned char *buf, size_t blen,
464 : : mbedtls_md_type_t md_alg,
465 : : int (*f_rng_blind)(void *, unsigned char *,
466 : : size_t),
467 : : void *p_rng_blind)
468 : : {
469 : : return mbedtls_ecdsa_sign_det_restartable(grp, r, s, d, buf, blen, md_alg,
470 : : f_rng_blind, p_rng_blind, NULL);
471 : : }
472 : : #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
473 : :
474 : : #if !defined(MBEDTLS_ECDSA_VERIFY_ALT)
475 : : /*
476 : : * Verify ECDSA signature of hashed message (SEC1 4.1.4)
477 : : * Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message)
478 : : */
479 : 6 : int mbedtls_ecdsa_verify_restartable(mbedtls_ecp_group *grp,
480 : : const unsigned char *buf, size_t blen,
481 : : const mbedtls_ecp_point *Q,
482 : : const mbedtls_mpi *r,
483 : : const mbedtls_mpi *s,
484 : : mbedtls_ecdsa_restart_ctx *rs_ctx)
485 : : {
486 : 6 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
487 : 6 : mbedtls_mpi e, s_inv, u1, u2;
488 : 6 : mbedtls_ecp_point R;
489 : 6 : mbedtls_mpi *pu1 = &u1, *pu2 = &u2;
490 : :
491 : 6 : mbedtls_ecp_point_init(&R);
492 : 6 : mbedtls_mpi_init(&e); mbedtls_mpi_init(&s_inv);
493 : 6 : mbedtls_mpi_init(&u1); mbedtls_mpi_init(&u2);
494 : :
495 : : /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
496 [ + - + - ]: 6 : if (!mbedtls_ecdsa_can_do(grp->id) || grp->N.p == NULL) {
497 : : return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
498 : : }
499 : :
500 : 6 : ECDSA_RS_ENTER(ver);
501 : :
502 : : #if defined(MBEDTLS_ECP_RESTARTABLE)
503 : : if (rs_ctx != NULL && rs_ctx->ver != NULL) {
504 : : /* redirect to our context */
505 : : pu1 = &rs_ctx->ver->u1;
506 : : pu2 = &rs_ctx->ver->u2;
507 : :
508 : : /* jump to current step */
509 : : if (rs_ctx->ver->state == ecdsa_ver_muladd) {
510 : : goto muladd;
511 : : }
512 : : }
513 : : #endif /* MBEDTLS_ECP_RESTARTABLE */
514 : :
515 : : /*
516 : : * Step 1: make sure r and s are in range 1..n-1
517 : : */
518 [ + - + - : 12 : if (mbedtls_mpi_cmp_int(r, 1) < 0 || mbedtls_mpi_cmp_mpi(r, &grp->N) >= 0 ||
+ - ]
519 [ - + ]: 12 : mbedtls_mpi_cmp_int(s, 1) < 0 || mbedtls_mpi_cmp_mpi(s, &grp->N) >= 0) {
520 : 0 : ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
521 : 0 : goto cleanup;
522 : : }
523 : :
524 : : /*
525 : : * Step 3: derive MPI from hashed message
526 : : */
527 [ - + ]: 6 : MBEDTLS_MPI_CHK(derive_mpi(grp, &e, buf, blen));
528 : :
529 : : /*
530 : : * Step 4: u1 = e / s mod n, u2 = r / s mod n
531 : : */
532 : 6 : ECDSA_BUDGET(MBEDTLS_ECP_OPS_CHK + MBEDTLS_ECP_OPS_INV + 2);
533 : :
534 [ - + ]: 6 : MBEDTLS_MPI_CHK(mbedtls_mpi_gcd_modinv_odd(NULL, &s_inv, s, &grp->N));
535 : :
536 [ - + ]: 6 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(pu1, &e, &s_inv));
537 [ - + ]: 6 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(pu1, pu1, &grp->N));
538 : :
539 [ - + ]: 6 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(pu2, r, &s_inv));
540 [ - + ]: 6 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(pu2, pu2, &grp->N));
541 : :
542 : : #if defined(MBEDTLS_ECP_RESTARTABLE)
543 : : if (rs_ctx != NULL && rs_ctx->ver != NULL) {
544 : : rs_ctx->ver->state = ecdsa_ver_muladd;
545 : : }
546 : :
547 : : muladd:
548 : : #endif
549 : : /*
550 : : * Step 5: R = u1 G + u2 Q
551 : : */
552 [ - + ]: 6 : MBEDTLS_MPI_CHK(mbedtls_ecp_muladd_restartable(grp,
553 : : &R, pu1, &grp->G, pu2, Q, ECDSA_RS_ECP));
554 : :
555 [ - + ]: 6 : if (mbedtls_ecp_is_zero(&R)) {
556 : 0 : ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
557 : 0 : goto cleanup;
558 : : }
559 : :
560 : : /*
561 : : * Step 6: convert xR to an integer (no-op)
562 : : * Step 7: reduce xR mod n (gives v)
563 : : */
564 [ - + ]: 6 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&R.X, &R.X, &grp->N));
565 : :
566 : : /*
567 : : * Step 8: check if v (that is, R.X) is equal to r
568 : : */
569 [ - + ]: 6 : if (mbedtls_mpi_cmp_mpi(&R.X, r) != 0) {
570 : 0 : ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
571 : 0 : goto cleanup;
572 : : }
573 : :
574 : 6 : cleanup:
575 : 6 : mbedtls_ecp_point_free(&R);
576 : 6 : mbedtls_mpi_free(&e); mbedtls_mpi_free(&s_inv);
577 : 6 : mbedtls_mpi_free(&u1); mbedtls_mpi_free(&u2);
578 : :
579 : 6 : ECDSA_RS_LEAVE(ver);
580 : :
581 : 6 : return ret;
582 : : }
583 : :
584 : : /*
585 : : * Verify ECDSA signature of hashed message
586 : : */
587 : 6 : int mbedtls_ecdsa_verify(mbedtls_ecp_group *grp,
588 : : const unsigned char *buf, size_t blen,
589 : : const mbedtls_ecp_point *Q,
590 : : const mbedtls_mpi *r,
591 : : const mbedtls_mpi *s)
592 : : {
593 : 6 : return mbedtls_ecdsa_verify_restartable(grp, buf, blen, Q, r, s, NULL);
594 : : }
595 : : #endif /* !MBEDTLS_ECDSA_VERIFY_ALT */
596 : :
597 : : /*
598 : : * Convert a signature (given by context) to ASN.1
599 : : */
600 : 0 : static int ecdsa_signature_to_asn1(const mbedtls_mpi *r, const mbedtls_mpi *s,
601 : : unsigned char *sig, size_t sig_size,
602 : : size_t *slen)
603 : : {
604 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
605 : 0 : unsigned char buf[MBEDTLS_ECDSA_MAX_LEN] = { 0 };
606 : 0 : unsigned char *p = buf + sizeof(buf);
607 : 0 : size_t len = 0;
608 : :
609 [ # # ]: 0 : MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_mpi(&p, buf, s));
610 [ # # ]: 0 : MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_mpi(&p, buf, r));
611 : :
612 [ # # ]: 0 : MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_len(&p, buf, len));
613 [ # # ]: 0 : MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_tag(&p, buf,
614 : : MBEDTLS_ASN1_CONSTRUCTED |
615 : : MBEDTLS_ASN1_SEQUENCE));
616 : :
617 [ # # ]: 0 : if (len > sig_size) {
618 : : return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
619 : : }
620 : :
621 : 0 : memcpy(sig, p, len);
622 : 0 : *slen = len;
623 : :
624 : 0 : return 0;
625 : : }
626 : :
627 : : /*
628 : : * Compute and write signature
629 : : */
630 : 0 : int mbedtls_ecdsa_write_signature_restartable(mbedtls_ecdsa_context *ctx,
631 : : mbedtls_md_type_t md_alg,
632 : : const unsigned char *hash, size_t hlen,
633 : : unsigned char *sig, size_t sig_size, size_t *slen,
634 : : int (*f_rng)(void *, unsigned char *, size_t),
635 : : void *p_rng,
636 : : mbedtls_ecdsa_restart_ctx *rs_ctx)
637 : : {
638 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
639 : 0 : mbedtls_mpi r, s;
640 [ # # ]: 0 : if (f_rng == NULL) {
641 : : return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
642 : : }
643 : :
644 : 0 : mbedtls_mpi_init(&r);
645 : 0 : mbedtls_mpi_init(&s);
646 : :
647 : : #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
648 : : MBEDTLS_MPI_CHK(mbedtls_ecdsa_sign_det_restartable(&ctx->grp, &r, &s, &ctx->d,
649 : : hash, hlen, md_alg, f_rng,
650 : : p_rng, rs_ctx));
651 : : #else
652 : 0 : (void) md_alg;
653 : :
654 : : #if defined(MBEDTLS_ECDSA_SIGN_ALT)
655 : : (void) rs_ctx;
656 : :
657 : : MBEDTLS_MPI_CHK(mbedtls_ecdsa_sign(&ctx->grp, &r, &s, &ctx->d,
658 : : hash, hlen, f_rng, p_rng));
659 : : #else
660 : : /* Use the same RNG for both blinding and ephemeral key generation */
661 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_ecdsa_sign_restartable(&ctx->grp, &r, &s, &ctx->d,
662 : : hash, hlen, f_rng, p_rng, f_rng,
663 : : p_rng, rs_ctx));
664 : : #endif /* MBEDTLS_ECDSA_SIGN_ALT */
665 : : #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
666 : :
667 : 0 : MBEDTLS_MPI_CHK(ecdsa_signature_to_asn1(&r, &s, sig, sig_size, slen));
668 : :
669 : 0 : cleanup:
670 : 0 : mbedtls_mpi_free(&r);
671 : 0 : mbedtls_mpi_free(&s);
672 : :
673 : 0 : return ret;
674 : : }
675 : :
676 : : /*
677 : : * Compute and write signature
678 : : */
679 : 0 : int mbedtls_ecdsa_write_signature(mbedtls_ecdsa_context *ctx,
680 : : mbedtls_md_type_t md_alg,
681 : : const unsigned char *hash, size_t hlen,
682 : : unsigned char *sig, size_t sig_size, size_t *slen,
683 : : int (*f_rng)(void *, unsigned char *, size_t),
684 : : void *p_rng)
685 : : {
686 : 0 : return mbedtls_ecdsa_write_signature_restartable(
687 : : ctx, md_alg, hash, hlen, sig, sig_size, slen,
688 : : f_rng, p_rng, NULL);
689 : : }
690 : :
691 : : /*
692 : : * Read and check signature
693 : : */
694 : 0 : int mbedtls_ecdsa_read_signature(mbedtls_ecdsa_context *ctx,
695 : : const unsigned char *hash, size_t hlen,
696 : : const unsigned char *sig, size_t slen)
697 : : {
698 : 0 : return mbedtls_ecdsa_read_signature_restartable(
699 : : ctx, hash, hlen, sig, slen, NULL);
700 : : }
701 : :
702 : : /*
703 : : * Restartable read and check signature
704 : : */
705 : 0 : int mbedtls_ecdsa_read_signature_restartable(mbedtls_ecdsa_context *ctx,
706 : : const unsigned char *hash, size_t hlen,
707 : : const unsigned char *sig, size_t slen,
708 : : mbedtls_ecdsa_restart_ctx *rs_ctx)
709 : : {
710 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
711 : 0 : unsigned char *p = (unsigned char *) sig;
712 : 0 : const unsigned char *end = sig + slen;
713 : 0 : size_t len;
714 : 0 : mbedtls_mpi r, s;
715 : 0 : mbedtls_mpi_init(&r);
716 : 0 : mbedtls_mpi_init(&s);
717 : :
718 [ # # ]: 0 : if ((ret = mbedtls_asn1_get_tag(&p, end, &len,
719 : : MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE)) != 0) {
720 : 0 : ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
721 : 0 : goto cleanup;
722 : : }
723 : :
724 [ # # ]: 0 : if (p + len != end) {
725 : 0 : ret = MBEDTLS_ERROR_ADD(MBEDTLS_ERR_ECP_BAD_INPUT_DATA,
726 : : MBEDTLS_ERR_ASN1_LENGTH_MISMATCH);
727 : 0 : goto cleanup;
728 : : }
729 : :
730 [ # # ]: 0 : if ((ret = mbedtls_asn1_get_mpi(&p, end, &r)) != 0 ||
731 [ # # ]: 0 : (ret = mbedtls_asn1_get_mpi(&p, end, &s)) != 0) {
732 : 0 : ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
733 : 0 : goto cleanup;
734 : : }
735 : : #if defined(MBEDTLS_ECDSA_VERIFY_ALT)
736 : : (void) rs_ctx;
737 : :
738 : : if ((ret = mbedtls_ecdsa_verify(&ctx->grp, hash, hlen,
739 : : &ctx->Q, &r, &s)) != 0) {
740 : : goto cleanup;
741 : : }
742 : : #else
743 [ # # ]: 0 : if ((ret = mbedtls_ecdsa_verify_restartable(&ctx->grp, hash, hlen,
744 : 0 : &ctx->Q, &r, &s, rs_ctx)) != 0) {
745 : 0 : goto cleanup;
746 : : }
747 : : #endif /* MBEDTLS_ECDSA_VERIFY_ALT */
748 : :
749 : : /* At this point we know that the buffer starts with a valid signature.
750 : : * Return 0 if the buffer just contains the signature, and a specific
751 : : * error code if the valid signature is followed by more data. */
752 [ # # ]: 0 : if (p != end) {
753 : 0 : ret = MBEDTLS_ERR_ECP_SIG_LEN_MISMATCH;
754 : : }
755 : :
756 : 0 : cleanup:
757 : 0 : mbedtls_mpi_free(&r);
758 : 0 : mbedtls_mpi_free(&s);
759 : :
760 : 0 : return ret;
761 : : }
762 : :
763 : : #if !defined(MBEDTLS_ECDSA_GENKEY_ALT)
764 : : /*
765 : : * Generate key pair
766 : : */
767 : 0 : int mbedtls_ecdsa_genkey(mbedtls_ecdsa_context *ctx, mbedtls_ecp_group_id gid,
768 : : int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
769 : : {
770 : 0 : int ret = 0;
771 : 0 : ret = mbedtls_ecp_group_load(&ctx->grp, gid);
772 [ # # ]: 0 : if (ret != 0) {
773 : : return ret;
774 : : }
775 : :
776 : 0 : return mbedtls_ecp_gen_keypair(&ctx->grp, &ctx->d,
777 : : &ctx->Q, f_rng, p_rng);
778 : : }
779 : : #endif /* !MBEDTLS_ECDSA_GENKEY_ALT */
780 : :
781 : : /*
782 : : * Set context from an mbedtls_ecp_keypair
783 : : */
784 : 0 : int mbedtls_ecdsa_from_keypair(mbedtls_ecdsa_context *ctx, const mbedtls_ecp_keypair *key)
785 : : {
786 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
787 [ # # ]: 0 : if ((ret = mbedtls_ecp_group_copy(&ctx->grp, &key->grp)) != 0 ||
788 [ # # ]: 0 : (ret = mbedtls_mpi_copy(&ctx->d, &key->d)) != 0 ||
789 [ # # ]: 0 : (ret = mbedtls_ecp_copy(&ctx->Q, &key->Q)) != 0) {
790 : 0 : mbedtls_ecdsa_free(ctx);
791 : : }
792 : :
793 : 0 : return ret;
794 : : }
795 : :
796 : : /*
797 : : * Initialize context
798 : : */
799 : 0 : void mbedtls_ecdsa_init(mbedtls_ecdsa_context *ctx)
800 : : {
801 : 0 : mbedtls_ecp_keypair_init(ctx);
802 : 0 : }
803 : :
804 : : /*
805 : : * Free context
806 : : */
807 : 0 : void mbedtls_ecdsa_free(mbedtls_ecdsa_context *ctx)
808 : : {
809 [ # # ]: 0 : if (ctx == NULL) {
810 : : return;
811 : : }
812 : :
813 : 0 : mbedtls_ecp_keypair_free(ctx);
814 : : }
815 : :
816 : : #if defined(MBEDTLS_ECP_RESTARTABLE)
817 : : /*
818 : : * Initialize a restart context
819 : : */
820 : : void mbedtls_ecdsa_restart_init(mbedtls_ecdsa_restart_ctx *ctx)
821 : : {
822 : : mbedtls_ecp_restart_init(&ctx->ecp);
823 : :
824 : : ctx->ver = NULL;
825 : : ctx->sig = NULL;
826 : : #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
827 : : ctx->det = NULL;
828 : : #endif
829 : : }
830 : :
831 : : /*
832 : : * Free the components of a restart context
833 : : */
834 : : void mbedtls_ecdsa_restart_free(mbedtls_ecdsa_restart_ctx *ctx)
835 : : {
836 : : if (ctx == NULL) {
837 : : return;
838 : : }
839 : :
840 : : mbedtls_ecp_restart_free(&ctx->ecp);
841 : :
842 : : ecdsa_restart_ver_free(ctx->ver);
843 : : mbedtls_free(ctx->ver);
844 : : ctx->ver = NULL;
845 : :
846 : : ecdsa_restart_sig_free(ctx->sig);
847 : : mbedtls_free(ctx->sig);
848 : : ctx->sig = NULL;
849 : :
850 : : #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
851 : : ecdsa_restart_det_free(ctx->det);
852 : : mbedtls_free(ctx->det);
853 : : ctx->det = NULL;
854 : : #endif
855 : : }
856 : : #endif /* MBEDTLS_ECP_RESTARTABLE */
857 : :
858 : : #endif /* MBEDTLS_ECDSA_C */
|
