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