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 */
ecdsa_restart_ver_init(mbedtls_ecdsa_restart_ver_ctx * ctx)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 */
ecdsa_restart_ver_free(mbedtls_ecdsa_restart_ver_ctx * ctx)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 */
ecdsa_restart_sig_init(mbedtls_ecdsa_restart_sig_ctx * ctx)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 */
ecdsa_restart_sig_free(mbedtls_ecdsa_restart_sig_ctx * ctx)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 */
ecdsa_restart_det_init(mbedtls_ecdsa_restart_det_ctx * ctx)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 */
ecdsa_restart_det_free(mbedtls_ecdsa_restart_det_ctx * ctx)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 */
derive_mpi(const mbedtls_ecp_group * grp,mbedtls_mpi * x,const unsigned char * buf,size_t blen)204 static int derive_mpi(const mbedtls_ecp_group *grp, mbedtls_mpi *x,
205 const unsigned char *buf, size_t blen)
206 {
207 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
208 size_t n_size = (grp->nbits + 7) / 8;
209 size_t use_size = blen > n_size ? n_size : blen;
210
211 MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(x, buf, use_size));
212 if (use_size * 8 > grp->nbits) {
213 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(x, use_size * 8 - grp->nbits));
214 }
215
216 /* While at it, reduce modulo N */
217 if (mbedtls_mpi_cmp_mpi(x, &grp->N) >= 0) {
218 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(x, x, &grp->N));
219 }
220
221 cleanup:
222 return ret;
223 }
224 #endif /* ECDSA_DETERMINISTIC || !ECDSA_SIGN_ALT || !ECDSA_VERIFY_ALT */
225
mbedtls_ecdsa_can_do(mbedtls_ecp_group_id gid)226 int mbedtls_ecdsa_can_do(mbedtls_ecp_group_id gid)
227 {
228 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 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 */
mbedtls_ecdsa_sign_restartable(mbedtls_ecp_group * grp,mbedtls_mpi * r,mbedtls_mpi * s,const mbedtls_mpi * d,const unsigned char * buf,size_t blen,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng,int (* f_rng_blind)(void *,unsigned char *,size_t),void * p_rng_blind,mbedtls_ecdsa_restart_ctx * rs_ctx)244 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 int ret, key_tries, sign_tries;
253 int *p_sign_tries = &sign_tries, *p_key_tries = &key_tries;
254 mbedtls_ecp_point R;
255 mbedtls_mpi k, e;
256 mbedtls_mpi *pk = &k, *pr = r;
257
258 /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
259 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 if (mbedtls_mpi_cmp_int(d, 1) < 0 || mbedtls_mpi_cmp_mpi(d, &grp->N) >= 0) {
265 return MBEDTLS_ERR_ECP_INVALID_KEY;
266 }
267
268 mbedtls_ecp_point_init(&R);
269 mbedtls_mpi_init(&k); mbedtls_mpi_init(&e);
270
271 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 *p_sign_tries = 0;
292 do {
293 if ((*p_sign_tries)++ > 10) {
294 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
295 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 do {
304 if ((*p_key_tries)++ > 10) {
305 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
306 goto cleanup;
307 }
308
309 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 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 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(pr, &R.X, &grp->N));
323 } 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 ECDSA_BUDGET(MBEDTLS_ECP_OPS_INV + 4);
337
338 /*
339 * Step 5: derive MPI from hashed message
340 */
341 MBEDTLS_MPI_CHK(derive_mpi(grp, &e, buf, blen));
342
343 /*
344 * Step 6: compute s = (e + r * d) / k
345 */
346 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(s, pr, d));
347 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&e, &e, s));
348 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd_modinv_odd(NULL, s, pk, &grp->N));
349 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(s, s, &e));
350 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(s, s, &grp->N));
351 } 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 cleanup:
360 mbedtls_ecp_point_free(&R);
361 mbedtls_mpi_free(&k); mbedtls_mpi_free(&e);
362
363 ECDSA_RS_LEAVE(sig);
364
365 return ret;
366 }
367
368 /*
369 * Compute ECDSA signature of a hashed message
370 */
mbedtls_ecdsa_sign(mbedtls_ecp_group * grp,mbedtls_mpi * r,mbedtls_mpi * s,const mbedtls_mpi * d,const unsigned char * buf,size_t blen,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)371 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 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 */
mbedtls_ecdsa_sign_det_restartable(mbedtls_ecp_group * grp,mbedtls_mpi * r,mbedtls_mpi * s,const mbedtls_mpi * d,const unsigned char * buf,size_t blen,mbedtls_md_type_t md_alg,int (* f_rng_blind)(void *,unsigned char *,size_t),void * p_rng_blind,mbedtls_ecdsa_restart_ctx * rs_ctx)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 */
mbedtls_ecdsa_sign_det_ext(mbedtls_ecp_group * grp,mbedtls_mpi * r,mbedtls_mpi * s,const mbedtls_mpi * d,const unsigned char * buf,size_t blen,mbedtls_md_type_t md_alg,int (* f_rng_blind)(void *,unsigned char *,size_t),void * p_rng_blind)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 */
mbedtls_ecdsa_verify_restartable(mbedtls_ecp_group * grp,const unsigned char * buf,size_t blen,const mbedtls_ecp_point * Q,const mbedtls_mpi * r,const mbedtls_mpi * s,mbedtls_ecdsa_restart_ctx * rs_ctx)479 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 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
487 mbedtls_mpi e, s_inv, u1, u2;
488 mbedtls_ecp_point R;
489 mbedtls_mpi *pu1 = &u1, *pu2 = &u2;
490
491 mbedtls_ecp_point_init(&R);
492 mbedtls_mpi_init(&e); mbedtls_mpi_init(&s_inv);
493 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 if (!mbedtls_ecdsa_can_do(grp->id) || grp->N.p == NULL) {
497 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
498 }
499
500 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 if (mbedtls_mpi_cmp_int(r, 1) < 0 || mbedtls_mpi_cmp_mpi(r, &grp->N) >= 0 ||
519 mbedtls_mpi_cmp_int(s, 1) < 0 || mbedtls_mpi_cmp_mpi(s, &grp->N) >= 0) {
520 ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
521 goto cleanup;
522 }
523
524 /*
525 * Step 3: derive MPI from hashed message
526 */
527 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 ECDSA_BUDGET(MBEDTLS_ECP_OPS_CHK + MBEDTLS_ECP_OPS_INV + 2);
533
534 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd_modinv_odd(NULL, &s_inv, s, &grp->N));
535
536 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(pu1, &e, &s_inv));
537 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(pu1, pu1, &grp->N));
538
539 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(pu2, r, &s_inv));
540 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 MBEDTLS_MPI_CHK(mbedtls_ecp_muladd_restartable(grp,
553 &R, pu1, &grp->G, pu2, Q, ECDSA_RS_ECP));
554
555 if (mbedtls_ecp_is_zero(&R)) {
556 ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
557 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 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 if (mbedtls_mpi_cmp_mpi(&R.X, r) != 0) {
570 ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
571 goto cleanup;
572 }
573
574 cleanup:
575 mbedtls_ecp_point_free(&R);
576 mbedtls_mpi_free(&e); mbedtls_mpi_free(&s_inv);
577 mbedtls_mpi_free(&u1); mbedtls_mpi_free(&u2);
578
579 ECDSA_RS_LEAVE(ver);
580
581 return ret;
582 }
583
584 /*
585 * Verify ECDSA signature of hashed message
586 */
mbedtls_ecdsa_verify(mbedtls_ecp_group * grp,const unsigned char * buf,size_t blen,const mbedtls_ecp_point * Q,const mbedtls_mpi * r,const mbedtls_mpi * s)587 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 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 */
ecdsa_signature_to_asn1(const mbedtls_mpi * r,const mbedtls_mpi * s,unsigned char * sig,size_t sig_size,size_t * slen)600 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 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
605 unsigned char buf[MBEDTLS_ECDSA_MAX_LEN] = { 0 };
606 unsigned char *p = buf + sizeof(buf);
607 size_t len = 0;
608
609 MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_mpi(&p, buf, s));
610 MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_mpi(&p, buf, r));
611
612 MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_len(&p, buf, len));
613 MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_tag(&p, buf,
614 MBEDTLS_ASN1_CONSTRUCTED |
615 MBEDTLS_ASN1_SEQUENCE));
616
617 if (len > sig_size) {
618 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
619 }
620
621 memcpy(sig, p, len);
622 *slen = len;
623
624 return 0;
625 }
626
627 /*
628 * Compute and write signature
629 */
mbedtls_ecdsa_write_signature_restartable(mbedtls_ecdsa_context * ctx,mbedtls_md_type_t md_alg,const unsigned char * hash,size_t hlen,unsigned char * sig,size_t sig_size,size_t * slen,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng,mbedtls_ecdsa_restart_ctx * rs_ctx)630 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 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
639 mbedtls_mpi r, s;
640 if (f_rng == NULL) {
641 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
642 }
643
644 mbedtls_mpi_init(&r);
645 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 (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 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 MBEDTLS_MPI_CHK(ecdsa_signature_to_asn1(&r, &s, sig, sig_size, slen));
668
669 cleanup:
670 mbedtls_mpi_free(&r);
671 mbedtls_mpi_free(&s);
672
673 return ret;
674 }
675
676 /*
677 * Compute and write signature
678 */
mbedtls_ecdsa_write_signature(mbedtls_ecdsa_context * ctx,mbedtls_md_type_t md_alg,const unsigned char * hash,size_t hlen,unsigned char * sig,size_t sig_size,size_t * slen,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)679 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 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 */
mbedtls_ecdsa_read_signature(mbedtls_ecdsa_context * ctx,const unsigned char * hash,size_t hlen,const unsigned char * sig,size_t slen)694 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 return mbedtls_ecdsa_read_signature_restartable(
699 ctx, hash, hlen, sig, slen, NULL);
700 }
701
702 /*
703 * Restartable read and check signature
704 */
mbedtls_ecdsa_read_signature_restartable(mbedtls_ecdsa_context * ctx,const unsigned char * hash,size_t hlen,const unsigned char * sig,size_t slen,mbedtls_ecdsa_restart_ctx * rs_ctx)705 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 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
711 unsigned char *p = (unsigned char *) sig;
712 const unsigned char *end = sig + slen;
713 size_t len;
714 mbedtls_mpi r, s;
715 mbedtls_mpi_init(&r);
716 mbedtls_mpi_init(&s);
717
718 if ((ret = mbedtls_asn1_get_tag(&p, end, &len,
719 MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE)) != 0) {
720 ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
721 goto cleanup;
722 }
723
724 if (p + len != end) {
725 ret = MBEDTLS_ERROR_ADD(MBEDTLS_ERR_ECP_BAD_INPUT_DATA,
726 MBEDTLS_ERR_ASN1_LENGTH_MISMATCH);
727 goto cleanup;
728 }
729
730 if ((ret = mbedtls_asn1_get_mpi(&p, end, &r)) != 0 ||
731 (ret = mbedtls_asn1_get_mpi(&p, end, &s)) != 0) {
732 ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
733 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 if ((ret = mbedtls_ecdsa_verify_restartable(&ctx->grp, hash, hlen,
744 &ctx->Q, &r, &s, rs_ctx)) != 0) {
745 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 if (p != end) {
753 ret = MBEDTLS_ERR_ECP_SIG_LEN_MISMATCH;
754 }
755
756 cleanup:
757 mbedtls_mpi_free(&r);
758 mbedtls_mpi_free(&s);
759
760 return ret;
761 }
762
763 #if !defined(MBEDTLS_ECDSA_GENKEY_ALT)
764 /*
765 * Generate key pair
766 */
mbedtls_ecdsa_genkey(mbedtls_ecdsa_context * ctx,mbedtls_ecp_group_id gid,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)767 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 int ret = 0;
771 ret = mbedtls_ecp_group_load(&ctx->grp, gid);
772 if (ret != 0) {
773 return ret;
774 }
775
776 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 */
mbedtls_ecdsa_from_keypair(mbedtls_ecdsa_context * ctx,const mbedtls_ecp_keypair * key)784 int mbedtls_ecdsa_from_keypair(mbedtls_ecdsa_context *ctx, const mbedtls_ecp_keypair *key)
785 {
786 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
787 if ((ret = mbedtls_ecp_group_copy(&ctx->grp, &key->grp)) != 0 ||
788 (ret = mbedtls_mpi_copy(&ctx->d, &key->d)) != 0 ||
789 (ret = mbedtls_ecp_copy(&ctx->Q, &key->Q)) != 0) {
790 mbedtls_ecdsa_free(ctx);
791 }
792
793 return ret;
794 }
795
796 /*
797 * Initialize context
798 */
mbedtls_ecdsa_init(mbedtls_ecdsa_context * ctx)799 void mbedtls_ecdsa_init(mbedtls_ecdsa_context *ctx)
800 {
801 mbedtls_ecp_keypair_init(ctx);
802 }
803
804 /*
805 * Free context
806 */
mbedtls_ecdsa_free(mbedtls_ecdsa_context * ctx)807 void mbedtls_ecdsa_free(mbedtls_ecdsa_context *ctx)
808 {
809 if (ctx == NULL) {
810 return;
811 }
812
813 mbedtls_ecp_keypair_free(ctx);
814 }
815
816 #if defined(MBEDTLS_ECP_RESTARTABLE)
817 /*
818 * Initialize a restart context
819 */
mbedtls_ecdsa_restart_init(mbedtls_ecdsa_restart_ctx * ctx)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 */
mbedtls_ecdsa_restart_free(mbedtls_ecdsa_restart_ctx * ctx)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 */
859