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