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