1 /*
2 * Copyright (C) 2017 - This file is part of libecc project
3 *
4 * Authors:
5 * Ryad BENADJILA <ryadbenadjila@gmail.com>
6 * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
7 * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr>
8 *
9 * Contributors:
10 * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr>
11 * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr>
12 *
13 * This software is licensed under a dual BSD and GPL v2 license.
14 * See LICENSE file at the root folder of the project.
15 */
16 #include <libecc/lib_ecc_config.h>
17 #if defined(WITH_SIG_ECDSA) || defined(WITH_SIG_DECDSA)
18
19 #include <libecc/nn/nn_rand.h>
20 #include <libecc/nn/nn_mul_public.h>
21 #include <libecc/nn/nn_logical.h>
22
23 #include <libecc/sig/sig_algs_internal.h>
24 #include <libecc/sig/ec_key.h>
25 #include <libecc/utils/utils.h>
26 #ifdef VERBOSE_INNER_VALUES
27 #define EC_SIG_ALG "ECDSA"
28 #endif
29 #include <libecc/utils/dbg_sig.h>
30
31
32 #if defined(WITH_SIG_DECDSA)
33 #include <libecc/hash/hmac.h>
34
35 /*
36 * Deterministic nonce generation function for deterministic ECDSA, as
37 * described in RFC6979.
38 * NOTE: Deterministic nonce generation for ECDSA is useful against attackers
39 * in contexts where only poor RNG/entropy are available, or when nonce bits
40 * leaking can be possible through side-channel attacks.
41 * However, in contexts where fault attacks are easy to mount, deterministic
42 * ECDSA can bring more security risks than regular ECDSA.
43 *
44 * Depending on the context where you use the library, choose carefully if
45 * you want to use the deterministic version or not.
46 *
47 */
__ecdsa_rfc6979_nonce(nn_t k,nn_src_t q,bitcnt_t q_bit_len,nn_src_t x,const u8 * hash,u8 hsize,hash_alg_type hash_type)48 ATTRIBUTE_WARN_UNUSED_RET static int __ecdsa_rfc6979_nonce(nn_t k, nn_src_t q, bitcnt_t q_bit_len,
49 nn_src_t x, const u8 *hash, u8 hsize,
50 hash_alg_type hash_type)
51 {
52 int ret, cmp;
53 u8 V[MAX_DIGEST_SIZE];
54 u8 K[MAX_DIGEST_SIZE];
55 u8 T[BYTECEIL(CURVES_MAX_Q_BIT_LEN) + MAX_DIGEST_SIZE];
56 u8 priv_key_buff[EC_PRIV_KEY_MAX_SIZE];
57 hmac_context hmac_ctx;
58 bitcnt_t t_bit_len;
59 u8 q_len;
60 u8 hmac_size;
61 u8 tmp;
62
63 /* Sanity checks */
64 MUST_HAVE((k != NULL), ret, err);
65 MUST_HAVE((hash != NULL), ret, err);
66 ret = nn_check_initialized(q); EG(ret, err);
67 ret = nn_check_initialized(x); EG(ret, err);
68
69 q_len = (u8)BYTECEIL(q_bit_len);
70
71 MUST_HAVE((q_len <= EC_PRIV_KEY_MAX_SIZE) && (hsize <= MAX_BLOCK_SIZE), ret, err);
72
73 /* Steps b. and c.: set V = 0x01 ... 0x01 and K = 0x00 ... 0x00 */
74 ret = local_memset(V, 0x01, hsize); EG(ret, err);
75 ret = local_memset(K, 0x00, hsize); EG(ret, err);
76 /* Export our private key in a buffer */
77 ret = nn_export_to_buf(priv_key_buff, q_len, x); EG(ret, err);
78 /* Step d.: set K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))
79 * where x is the private key and h1 the message hash.
80 */
81 ret = hmac_init(&hmac_ctx, K, hsize, hash_type); EG(ret, err);
82 ret = hmac_update(&hmac_ctx, V, hsize); EG(ret, err);
83
84 tmp = 0x00;
85 ret = hmac_update(&hmac_ctx, &tmp, 1); EG(ret, err);
86 ret = hmac_update(&hmac_ctx, priv_key_buff, q_len); EG(ret, err);
87
88 /* We compute bits2octets(hash) here */
89 ret = nn_init_from_buf(k, hash, hsize); EG(ret, err);
90 if((8 * hsize) > q_bit_len){
91 ret = nn_rshift(k, k, (bitcnt_t)((8 * hsize) - q_bit_len)); EG(ret, err);
92 }
93 ret = nn_mod(k, k, q); EG(ret, err);
94 ret = nn_export_to_buf(T, q_len, k); EG(ret, err);
95 ret = hmac_update(&hmac_ctx, T, q_len); EG(ret, err);
96 hmac_size = sizeof(K);
97 ret = hmac_finalize(&hmac_ctx, K, &hmac_size); EG(ret, err);
98
99 /* Step e.: set V = HMAC_K(V) */
100 hmac_size = sizeof(V);
101 ret = hmac(K, hsize, hash_type, V, hsize, V, &hmac_size); EG(ret, err);
102 /* Step f.: K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1)) */
103 ret = hmac_init(&hmac_ctx, K, hsize, hash_type); EG(ret, err);
104 ret = hmac_update(&hmac_ctx, V, hsize); EG(ret, err);
105
106 tmp = 0x01;
107 ret = hmac_update(&hmac_ctx, &tmp, 1); EG(ret, err);
108 ret = hmac_update(&hmac_ctx, priv_key_buff, q_len); EG(ret, err);
109
110 /* We compute bits2octets(hash) here */
111 ret = hmac_update(&hmac_ctx, T, q_len); EG(ret, err);
112 hmac_size = sizeof(K);
113 ret = hmac_finalize(&hmac_ctx, K, &hmac_size); EG(ret, err);
114 /* Step g.: set V = HMAC_K(V)*/
115 hmac_size = sizeof(V);
116 ret = hmac(K, hsize, hash_type, V, hsize, V, &hmac_size); EG(ret, err);
117
118 /* Step h. now apply the generation algorithm until we get
119 * a proper nonce value:
120 * 1. Set T to the empty sequence. The length of T (in bits) is
121 * denoted tlen; thus, at that point, tlen = 0.
122 * 2. While tlen < qlen, do the following:
123 * V = HMAC_K(V)
124 * T = T || V
125 * 3. Compute:
126 * k = bits2int(T)
127 * If that value of k is within the [1,q-1] range, and is
128 * suitable for DSA or ECDSA (i.e., it results in an r value
129 * that is not 0; see Section 3.4), then the generation of k is
130 * finished. The obtained value of k is used in DSA or ECDSA.
131 * Otherwise, compute:
132 * K = HMAC_K(V || 0x00)
133 * V = HMAC_K(V)
134 * and loop (try to generate a new T, and so on).
135 */
136 restart:
137 t_bit_len = 0;
138 while(t_bit_len < q_bit_len){
139 /* V = HMAC_K(V) */
140 hmac_size = sizeof(V);
141 ret = hmac(K, hsize, hash_type, V, hsize, V, &hmac_size); EG(ret, err);
142 ret = local_memcpy(&T[BYTECEIL(t_bit_len)], V, hmac_size); EG(ret, err);
143 t_bit_len = (bitcnt_t)(t_bit_len + (8 * hmac_size));
144 }
145 ret = nn_init_from_buf(k, T, q_len); EG(ret, err);
146 if((8 * q_len) > q_bit_len){
147 ret = nn_rshift(k, k, (bitcnt_t)((8 * q_len) - q_bit_len)); EG(ret, err);
148 }
149 ret = nn_cmp(k, q, &cmp); EG(ret, err);
150 if(cmp >= 0){
151 /* K = HMAC_K(V || 0x00) */
152 ret = hmac_init(&hmac_ctx, K, hsize, hash_type); EG(ret, err);
153 ret = hmac_update(&hmac_ctx, V, hsize); EG(ret, err);
154
155 tmp = 0x00;
156 ret = hmac_update(&hmac_ctx, &tmp, 1); EG(ret, err);
157
158 hmac_size = sizeof(K);
159 ret = hmac_finalize(&hmac_ctx, K, &hmac_size); EG(ret, err);
160 /* V = HMAC_K(V) */
161 hmac_size = sizeof(V);
162 ret = hmac(K, hsize, hash_type, V, hsize, V, &hmac_size); EG(ret, err);
163
164 goto restart;
165 }
166
167 err:
168 return ret;
169 }
170 #endif
171
__ecdsa_init_pub_key(ec_pub_key * out_pub,const ec_priv_key * in_priv,ec_alg_type key_type)172 int __ecdsa_init_pub_key(ec_pub_key *out_pub, const ec_priv_key *in_priv,
173 ec_alg_type key_type)
174 {
175 prj_pt_src_t G;
176 int ret, cmp;
177 nn_src_t q;
178
179 MUST_HAVE((out_pub != NULL), ret, err);
180
181 /* Zero init public key to be generated */
182 ret = local_memset(out_pub, 0, sizeof(ec_pub_key)); EG(ret, err);
183
184 ret = priv_key_check_initialized_and_type(in_priv, key_type); EG(ret, err);
185 q = &(in_priv->params->ec_gen_order);
186
187 /* Sanity check on key compliance */
188 MUST_HAVE((!nn_cmp(&(in_priv->x), q, &cmp)) && (cmp < 0), ret, err);
189
190 /* Y = xG */
191 G = &(in_priv->params->ec_gen);
192 /* Use blinding when computing point scalar multiplication */
193 ret = prj_pt_mul_blind(&(out_pub->y), &(in_priv->x), G); EG(ret, err);
194
195 out_pub->key_type = key_type;
196 out_pub->params = in_priv->params;
197 out_pub->magic = PUB_KEY_MAGIC;
198
199 err:
200 return ret;
201 }
202
__ecdsa_siglen(u16 p_bit_len,u16 q_bit_len,u8 hsize,u8 blocksize,u8 * siglen)203 int __ecdsa_siglen(u16 p_bit_len, u16 q_bit_len, u8 hsize, u8 blocksize, u8 *siglen)
204 {
205 int ret;
206
207 MUST_HAVE(siglen != NULL, ret, err);
208 MUST_HAVE((p_bit_len <= CURVES_MAX_P_BIT_LEN) &&
209 (q_bit_len <= CURVES_MAX_Q_BIT_LEN) &&
210 (hsize <= MAX_DIGEST_SIZE) && (blocksize <= MAX_BLOCK_SIZE), ret, err);
211 (*siglen) = (u8)ECDSA_SIGLEN(q_bit_len);
212 ret = 0;
213
214 err:
215 return ret;
216 }
217
218 /*
219 * Generic *internal* ECDSA signature functions (init, update and finalize).
220 * Their purpose is to allow passing a specific hash function (along with
221 * its output size) and the random ephemeral key k, so that compliance
222 * tests against test vectors can be made without ugly hack in the code
223 * itself.
224 *
225 * Global EC-DSA signature process is as follows (I,U,F provides
226 * information in which function(s) (init(), update() or finalize())
227 * a specific step is performed):
228 *
229 *| IUF - ECDSA signature
230 *|
231 *| UF 1. Compute h = H(m)
232 *| F 2. If |h| > bitlen(q), set h to bitlen(q)
233 *| leftmost (most significant) bits of h
234 *| F 3. e = OS2I(h) mod q
235 *| F 4. Get a random value k in ]0,q[
236 *| F 5. Compute W = (W_x,W_y) = kG
237 *| F 6. Compute r = W_x mod q
238 *| F 7. If r is 0, restart the process at step 4.
239 *| F 8. If e == rx, restart the process at step 4.
240 *| F 9. Compute s = k^-1 * (xr + e) mod q
241 *| F 10. If s is 0, restart the process at step 4.
242 *| F 11. Return (r,s)
243 *
244 * Implementation notes:
245 *
246 * a) Usually (this is for instance the case in ISO 14888-3 and X9.62), the
247 * process starts with steps 4 to 7 and is followed by steps 1 to 3.
248 * The order is modified here w/o impact on the result and the security
249 * in order to allow the algorithm to be compatible with an
250 * init/update/finish API. More explicitly, the generation of k, which
251 * may later result in a (unlikely) restart of the whole process is
252 * postponed until the hash of the message has been computed.
253 * b) sig is built as the concatenation of r and s. Both r and s are
254 * encoded on ceil(bitlen(q)/8) bytes.
255 * c) in EC-DSA, the public part of the key is not needed per se during the
256 * signature but - as it is needed in other signature algs implemented
257 * in the library - the whole key pair is passed instead of just the
258 * private key.
259 */
260
261 #define ECDSA_SIGN_MAGIC ((word_t)(0x80299a2bf630945bULL))
262 #define ECDSA_SIGN_CHECK_INITIALIZED(A, ret, err) \
263 MUST_HAVE((((void *)(A)) != NULL) && ((A)->magic == ECDSA_SIGN_MAGIC), ret, err)
264
__ecdsa_sign_init(struct ec_sign_context * ctx,ec_alg_type key_type)265 int __ecdsa_sign_init(struct ec_sign_context *ctx, ec_alg_type key_type)
266 {
267 int ret;
268
269 /* First, verify context has been initialized */
270 ret = sig_sign_check_initialized(ctx); EG(ret, err);
271
272 /* Additional sanity checks on input params from context */
273 ret = key_pair_check_initialized_and_type(ctx->key_pair, key_type); EG(ret, err);
274
275 MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) &&
276 (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err);
277
278 /*
279 * Initialize hash context stored in our private part of context
280 * and record data init has been done
281 */
282 /* Since we call a callback, sanity check our mapping */
283 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
284 ret = ctx->h->hfunc_init(&(ctx->sign_data.ecdsa.h_ctx)); EG(ret, err);
285
286 ctx->sign_data.ecdsa.magic = ECDSA_SIGN_MAGIC;
287
288 err:
289 return ret;
290 }
291
__ecdsa_sign_update(struct ec_sign_context * ctx,const u8 * chunk,u32 chunklen,ec_alg_type key_type)292 int __ecdsa_sign_update(struct ec_sign_context *ctx,
293 const u8 *chunk, u32 chunklen, ec_alg_type key_type)
294 {
295 int ret;
296
297 /*
298 * First, verify context has been initialized and private
299 * part too. This guarantees the context is an ECDSA
300 * signature one and we do not update() or finalize()
301 * before init().
302 */
303 ret = sig_sign_check_initialized(ctx); EG(ret, err);
304 ECDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecdsa), ret, err);
305
306 /* Additional sanity checks on input params from context */
307 ret = key_pair_check_initialized_and_type(ctx->key_pair, key_type); EG(ret, err);
308
309 /* 1. Compute h = H(m) */
310 /* Since we call a callback, sanity check our mapping */
311 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
312 ret = ctx->h->hfunc_update(&(ctx->sign_data.ecdsa.h_ctx), chunk, chunklen);
313
314 err:
315 return ret;
316 }
317
__ecdsa_sign_finalize(struct ec_sign_context * ctx,u8 * sig,u8 siglen,ec_alg_type key_type)318 int __ecdsa_sign_finalize(struct ec_sign_context *ctx, u8 *sig, u8 siglen,
319 ec_alg_type key_type)
320 {
321 int ret, iszero, cmp;
322 const ec_priv_key *priv_key;
323 prj_pt_src_t G;
324 u8 hash[MAX_DIGEST_SIZE];
325 bitcnt_t rshift, q_bit_len;
326 prj_pt kG;
327 nn_src_t q, x;
328 u8 hsize, q_len;
329 nn k, r, e, tmp, s, kinv;
330 #ifdef USE_SIG_BLINDING
331 /* b is the blinding mask */
332 nn b;
333 b.magic = WORD(0);
334 #endif
335
336 k.magic = r.magic = e.magic = WORD(0);
337 tmp.magic = s.magic = kinv.magic = WORD(0);
338 kG.magic = WORD(0);
339
340 /*
341 * First, verify context has been initialized and private
342 * part too. This guarantees the context is an ECDSA
343 * signature one and we do not finalize() before init().
344 */
345 ret = sig_sign_check_initialized(ctx); EG(ret, err);
346 ECDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecdsa), ret, err);
347 MUST_HAVE((sig != NULL), ret, err);
348
349 /* Additional sanity checks on input params from context */
350 ret = key_pair_check_initialized_and_type(ctx->key_pair, key_type); EG(ret, err);
351
352 /* Zero init out point */
353 ret = local_memset(&kG, 0, sizeof(prj_pt)); EG(ret, err);
354
355 /* Make things more readable */
356 priv_key = &(ctx->key_pair->priv_key);
357 q = &(priv_key->params->ec_gen_order);
358 q_bit_len = priv_key->params->ec_gen_order_bitlen;
359 G = &(priv_key->params->ec_gen);
360 q_len = (u8)BYTECEIL(q_bit_len);
361 x = &(priv_key->x);
362 hsize = ctx->h->digest_size;
363
364 MUST_HAVE((priv_key->key_type == key_type), ret, err);
365
366 /* Sanity check */
367 ret = nn_cmp(x, q, &cmp); EG(ret, err);
368 /* This should not happen and means that our
369 * private key is not compliant!
370 */
371 MUST_HAVE((cmp < 0), ret, err);
372
373 dbg_nn_print("p", &(priv_key->params->ec_fp.p));
374 dbg_nn_print("q", &(priv_key->params->ec_gen_order));
375 dbg_priv_key_print("x", priv_key);
376 dbg_ec_point_print("G", &(priv_key->params->ec_gen));
377 dbg_pub_key_print("Y", &(ctx->key_pair->pub_key));
378
379 /* Check given signature buffer length has the expected size */
380 MUST_HAVE((siglen == ECDSA_SIGLEN(q_bit_len)), ret, err);
381
382 /* 1. Compute h = H(m) */
383 ret = local_memset(hash, 0, hsize); EG(ret, err);
384 /* Since we call a callback, sanity check our mapping */
385 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
386 ret = ctx->h->hfunc_finalize(&(ctx->sign_data.ecdsa.h_ctx), hash); EG(ret, err);
387 dbg_buf_print("h", hash, hsize);
388
389 /*
390 * 2. If |h| > bitlen(q), set h to bitlen(q)
391 * leftmost bits of h.
392 *
393 * Note that it's easier to check if the truncation has
394 * to be done here but only implement it using a logical
395 * shift at the beginning of step 3. below once the hash
396 * has been converted to an integer.
397 */
398 rshift = 0;
399 if ((hsize * 8) > q_bit_len) {
400 rshift = (bitcnt_t)((hsize * 8) - q_bit_len);
401 }
402
403 /*
404 * 3. Compute e = OS2I(h) mod q, i.e. by converting h to an
405 * integer and reducing it mod q
406 */
407 ret = nn_init_from_buf(&e, hash, hsize); EG(ret, err);
408 dbg_nn_print("h initial import as nn", &e);
409 if (rshift) {
410 ret = nn_rshift_fixedlen(&e, &e, rshift); EG(ret, err);
411 }
412 dbg_nn_print("h final import as nn", &e);
413 ret = nn_mod(&e, &e, q); EG(ret, err);
414 dbg_nn_print("e", &e);
415
416 restart:
417 /* 4. get a random value k in ]0,q[ */
418 #ifdef NO_KNOWN_VECTORS
419 /* NOTE: when we do not need self tests for known vectors,
420 * we can be strict about random function handler!
421 * This allows us to avoid the corruption of such a pointer.
422 */
423 /* Sanity check on the handler before calling it */
424 if(ctx->rand != nn_get_random_mod){
425 #ifdef WITH_SIG_DECDSA
426 /* In deterministic ECDSA, nevermind! */
427 if(key_type != DECDSA)
428 #endif
429 {
430 ret = -1;
431 goto err;
432 }
433 }
434 #endif
435 if(ctx->rand != NULL){
436 /* Non-deterministic generation, or deterministic with
437 * test vectors.
438 */
439 ret = ctx->rand(&k, q);
440 }
441 else
442 #if defined(WITH_SIG_DECDSA)
443 {
444 /* Only applies for DETERMINISTIC ECDSA */
445 if(key_type != DECDSA){
446 ret = -1;
447 goto err;
448 }
449 /* Deterministically generate k as RFC6979 mandates */
450 ret = __ecdsa_rfc6979_nonce(&k, q, q_bit_len, &(priv_key->x),
451 hash, hsize, ctx->h->type);
452 }
453 #else
454 {
455 /* NULL rand function is not accepted for regular ECDSA */
456 ret = -1;
457 goto err;
458 }
459 #endif
460 if (ret) {
461 ret = -1;
462 goto err;
463 }
464 dbg_nn_print("k", &k);
465
466 #ifdef USE_SIG_BLINDING
467 /* Note: if we use blinding, r and e are multiplied by
468 * a random value b in ]0,q[ */
469 ret = nn_get_random_mod(&b, q); EG(ret, err);
470
471 dbg_nn_print("b", &b);
472 #endif /* USE_SIG_BLINDING */
473
474
475 /* 5. Compute W = (W_x,W_y) = kG */
476 #ifdef USE_SIG_BLINDING
477 ret = prj_pt_mul_blind(&kG, &k, G); EG(ret, err);
478 #else
479 ret = prj_pt_mul(&kG, &k, G); EG(ret, err);
480 #endif /* USE_SIG_BLINDING */
481 ret = prj_pt_unique(&kG, &kG); EG(ret, err);
482
483 dbg_nn_print("W_x", &(kG.X.fp_val));
484 dbg_nn_print("W_y", &(kG.Y.fp_val));
485
486 /* 6. Compute r = W_x mod q */
487 ret = nn_mod(&r, &(kG.X.fp_val), q); EG(ret, err);
488 dbg_nn_print("r", &r);
489
490 /* 7. If r is 0, restart the process at step 4. */
491 ret = nn_iszero(&r, &iszero); EG(ret, err);
492 if (iszero) {
493 goto restart;
494 }
495
496 /* Clean hash buffer as we do not need it anymore */
497 ret = local_memset(hash, 0, hsize); EG(ret, err);
498
499 /* Export r */
500 ret = nn_export_to_buf(sig, q_len, &r); EG(ret, err);
501
502 #ifdef USE_SIG_BLINDING
503 /* Blind r with b */
504 ret = nn_mod_mul(&r, &r, &b, q); EG(ret, err);
505
506 /* Blind the message e */
507 ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err);
508 #endif /* USE_SIG_BLINDING */
509
510 /* tmp = xr mod q */
511 ret = nn_mod_mul(&tmp, x, &r, q); EG(ret, err);
512 dbg_nn_print("x*r mod q", &tmp);
513
514 /* 8. If e == rx, restart the process at step 4. */
515 ret = nn_cmp(&e, &tmp, &cmp); EG(ret, err);
516 if (!cmp) {
517 goto restart;
518 }
519
520 /* 9. Compute s = k^-1 * (xr + e) mod q */
521
522 /* tmp = (e + xr) mod q */
523 ret = nn_mod_add(&tmp, &tmp, &e, q); EG(ret, err);
524 dbg_nn_print("(xr + e) mod q", &tmp);
525
526 #ifdef USE_SIG_BLINDING
527 /*
528 * In case of blinding, we compute (b*k)^-1, and b^-1 will
529 * automatically unblind (r*x) in the following.
530 */
531 ret = nn_mod_mul(&k, &k, &b, q); EG(ret, err);
532 #endif
533 /* Compute k^-1 mod q */
534 /* NOTE: we use Fermat's little theorem inversion for
535 * constant time here. This is possible since q is prime.
536 */
537 ret = nn_modinv_fermat(&kinv, &k, q); EG(ret, err);
538
539 dbg_nn_print("k^-1 mod q", &kinv);
540
541 /* s = k^-1 * tmp2 mod q */
542 ret = nn_mod_mul(&s, &tmp, &kinv, q); EG(ret, err);
543
544 dbg_nn_print("s", &s);
545
546 /* 10. If s is 0, restart the process at step 4. */
547 ret = nn_iszero(&s, &iszero); EG(ret, err);
548 if (iszero) {
549 goto restart;
550 }
551
552 /* 11. return (r,s) */
553 ret = nn_export_to_buf(sig + q_len, q_len, &s);
554
555 err:
556 nn_uninit(&k);
557 nn_uninit(&r);
558 nn_uninit(&e);
559 nn_uninit(&tmp);
560 nn_uninit(&s);
561 nn_uninit(&kinv);
562 prj_pt_uninit(&kG);
563 #ifdef USE_SIG_BLINDING
564 nn_uninit(&b);
565 #endif
566
567 /*
568 * We can now clear data part of the context. This will clear
569 * magic and avoid further reuse of the whole context.
570 */
571 if(ctx != NULL){
572 IGNORE_RET_VAL(local_memset(&(ctx->sign_data.ecdsa), 0, sizeof(ecdsa_sign_data)));
573 }
574
575 /* Clean what remains on the stack */
576 PTR_NULLIFY(priv_key);
577 PTR_NULLIFY(G);
578 PTR_NULLIFY(q);
579 PTR_NULLIFY(x);
580 VAR_ZEROIFY(q_len);
581 VAR_ZEROIFY(q_bit_len);
582 VAR_ZEROIFY(rshift);
583 VAR_ZEROIFY(hsize);
584
585 return ret;
586 }
587
588 /*
589 * Generic *internal* ECDSA verification functions (init, update and finalize).
590 * Their purpose is to allow passing a specific hash function (along with
591 * its output size) and the random ephemeral key k, so that compliance
592 * tests against test vectors can be made without ugly hack in the code
593 * itself.
594 *
595 * Global ECDSA verification process is as follows (I,U,F provides
596 * information in which function(s) (init(), update() or finalize())
597 * a specific step is performed):
598 *
599 *| IUF - ECDSA verification
600 *|
601 *| I 1. Reject the signature if r or s is 0.
602 *| UF 2. Compute h = H(m)
603 *| F 3. If |h| > bitlen(q), set h to bitlen(q)
604 *| leftmost (most significant) bits of h
605 *| F 4. Compute e = OS2I(h) mod q
606 *| F 5. Compute u = (s^-1)e mod q
607 *| F 6. Compute v = (s^-1)r mod q
608 *| F 7. Compute W' = uG + vY
609 *| F 8. If W' is the point at infinity, reject the signature.
610 *| F 9. Compute r' = W'_x mod q
611 *| F 10. Accept the signature if and only if r equals r'
612 *
613 */
614
615 #define ECDSA_VERIFY_MAGIC ((word_t)(0x5155fe73e7fd51beULL))
616 #define ECDSA_VERIFY_CHECK_INITIALIZED(A, ret, err) \
617 MUST_HAVE((((void *)(A)) != NULL) && ((A)->magic == ECDSA_VERIFY_MAGIC), ret, err)
618
__ecdsa_verify_init(struct ec_verify_context * ctx,const u8 * sig,u8 siglen,ec_alg_type key_type)619 int __ecdsa_verify_init(struct ec_verify_context *ctx, const u8 *sig, u8 siglen,
620 ec_alg_type key_type)
621 {
622 bitcnt_t q_bit_len;
623 u8 q_len;
624 nn_src_t q;
625 nn *r, *s;
626 int ret, cmp1, cmp2, iszero1, iszero2;
627
628 /* First, verify context has been initialized */
629 ret = sig_verify_check_initialized(ctx); EG(ret, err);
630
631 /* Do some sanity checks on input params */
632 ret = pub_key_check_initialized_and_type(ctx->pub_key, key_type); EG(ret, err);
633 MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) &&
634 (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err);
635 MUST_HAVE((sig != NULL), ret, err);
636
637 /* Make things more readable */
638 q = &(ctx->pub_key->params->ec_gen_order);
639 q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen;
640 q_len = (u8)BYTECEIL(q_bit_len);
641 r = &(ctx->verify_data.ecdsa.r);
642 s = &(ctx->verify_data.ecdsa.s);
643
644 /* Check given signature length is the expected one */
645 MUST_HAVE((siglen == ECDSA_SIGLEN(q_bit_len)), ret, err);
646
647 /* Import r and s values from signature buffer */
648 ret = nn_init_from_buf(r, sig, q_len); EG(ret, err);
649 ret = nn_init_from_buf(s, sig + q_len, q_len); EG(ret, err);
650 dbg_nn_print("r", r);
651 dbg_nn_print("s", s);
652
653 /* 1. Reject the signature if r or s is 0. */
654 ret = nn_iszero(r, &iszero1); EG(ret, err);
655 ret = nn_iszero(s, &iszero2); EG(ret, err);
656 ret = nn_cmp(r, q, &cmp1); EG(ret, err);
657 ret = nn_cmp(s, q, &cmp2); EG(ret, err);
658 MUST_HAVE(((!iszero1) && (cmp1 < 0) && !iszero2 && (cmp2 < 0)), ret, err);
659
660 /* Initialize the remaining of verify context. */
661 /* Since we call a callback, sanity check our mapping */
662 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
663 ret = ctx->h->hfunc_init(&(ctx->verify_data.ecdsa.h_ctx)); EG(ret, err);
664
665 ctx->verify_data.ecdsa.magic = ECDSA_VERIFY_MAGIC;
666
667 err:
668 VAR_ZEROIFY(q_len);
669 VAR_ZEROIFY(q_bit_len);
670 PTR_NULLIFY(q);
671 PTR_NULLIFY(r);
672 PTR_NULLIFY(s);
673
674 return ret;
675 }
676
__ecdsa_verify_update(struct ec_verify_context * ctx,const u8 * chunk,u32 chunklen,ec_alg_type key_type)677 int __ecdsa_verify_update(struct ec_verify_context *ctx,
678 const u8 *chunk, u32 chunklen, ec_alg_type key_type)
679 {
680 int ret;
681
682 /*
683 * First, verify context has been initialized and public
684 * part too. This guarantees the context is an ECDSA
685 * verification one and we do not update() or finalize()
686 * before init().
687 */
688 ret = sig_verify_check_initialized(ctx); EG(ret, err);
689 ECDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecdsa), ret, err);
690 /* Do some sanity checks on input params */
691 ret = pub_key_check_initialized_and_type(ctx->pub_key, key_type); EG(ret, err);
692
693 /* 2. Compute h = H(m) */
694 /* Since we call a callback, sanity check our mapping */
695 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
696 ret = ctx->h->hfunc_update(&(ctx->verify_data.ecdsa.h_ctx), chunk, chunklen);
697
698 err:
699 return ret;
700 }
701
__ecdsa_verify_finalize(struct ec_verify_context * ctx,ec_alg_type key_type)702 int __ecdsa_verify_finalize(struct ec_verify_context *ctx,
703 ec_alg_type key_type)
704 {
705 prj_pt uG, vY;
706 prj_pt_t W_prime;
707 nn e, sinv, uv, r_prime;
708 prj_pt_src_t G, Y;
709 u8 hash[MAX_DIGEST_SIZE];
710 bitcnt_t rshift, q_bit_len;
711 nn_src_t q;
712 nn *s, *r;
713 u8 hsize;
714 int ret, iszero, cmp;
715
716 uG.magic = vY.magic = WORD(0);
717 e.magic = sinv.magic = uv.magic = r_prime.magic = WORD(0);
718
719 /* NOTE: we reuse uG for W_prime to optimize local variables */
720 W_prime = &uG;
721
722 /*
723 * First, verify context has been initialized and public
724 * part too. This guarantees the context is an ECDSA
725 * verification one and we do not finalize() before init().
726 */
727 ret = sig_verify_check_initialized(ctx); EG(ret, err);
728 ECDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecdsa), ret, err);
729 /* Do some sanity checks on input params */
730 ret = pub_key_check_initialized_and_type(ctx->pub_key, key_type); EG(ret, err);
731
732 /* Zero init points */
733 ret = local_memset(&uG, 0, sizeof(prj_pt)); EG(ret, err);
734 ret = local_memset(&vY, 0, sizeof(prj_pt)); EG(ret, err);
735
736 /* Make things more readable */
737 G = &(ctx->pub_key->params->ec_gen);
738 Y = &(ctx->pub_key->y);
739 q = &(ctx->pub_key->params->ec_gen_order);
740 q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen;
741 hsize = ctx->h->digest_size;
742 r = &(ctx->verify_data.ecdsa.r);
743 s = &(ctx->verify_data.ecdsa.s);
744
745 /* 2. Compute h = H(m) */
746 /* Since we call a callback, sanity check our mapping */
747 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
748 ret = ctx->h->hfunc_finalize(&(ctx->verify_data.ecdsa.h_ctx), hash); EG(ret, err);
749 dbg_buf_print("h = H(m)", hash, hsize);
750
751 /*
752 * 3. If |h| > bitlen(q), set h to bitlen(q)
753 * leftmost bits of h.
754 *
755 * Note that it's easier to check here if the truncation
756 * needs to be done but implement it using a logical
757 * shift at the beginning of step 3. below once the hash
758 * has been converted to an integer.
759 */
760 rshift = 0;
761 if ((hsize * 8) > q_bit_len) {
762 rshift = (bitcnt_t)((hsize * 8) - q_bit_len);
763 }
764
765 /*
766 * 4. Compute e = OS2I(h) mod q, by converting h to an integer
767 * and reducing it mod q
768 */
769 ret = nn_init_from_buf(&e, hash, hsize); EG(ret, err);
770 ret = local_memset(hash, 0, hsize); EG(ret, err);
771 dbg_nn_print("h initial import as nn", &e);
772 if (rshift) {
773 ret = nn_rshift_fixedlen(&e, &e, rshift); EG(ret, err);
774 }
775 dbg_nn_print("h final import as nn", &e);
776
777 ret = nn_mod(&e, &e, q); EG(ret, err);
778 dbg_nn_print("e", &e);
779
780 /* Compute s^-1 mod q */
781 ret = nn_modinv(&sinv, s, q); EG(ret, err);
782 dbg_nn_print("s", s);
783 dbg_nn_print("sinv", &sinv);
784
785 /* 5. Compute u = (s^-1)e mod q */
786 ret = nn_mod_mul(&uv, &e, &sinv, q); EG(ret, err);
787 dbg_nn_print("u = (s^-1)e mod q", &uv);
788 ret = prj_pt_mul(&uG, &uv, G); EG(ret, err);
789
790 /* 6. Compute v = (s^-1)r mod q */
791 ret = nn_mod_mul(&uv, r, &sinv, q); EG(ret, err);
792 dbg_nn_print("v = (s^-1)r mod q", &uv);
793 ret = prj_pt_mul(&vY, &uv, Y); EG(ret, err);
794
795 /* 7. Compute W' = uG + vY */
796 ret = prj_pt_add(W_prime, &uG, &vY); EG(ret, err);
797
798 /* 8. If W' is the point at infinity, reject the signature. */
799 ret = prj_pt_iszero(W_prime, &iszero); EG(ret, err);
800 MUST_HAVE(!iszero, ret, err);
801
802 /* 9. Compute r' = W'_x mod q */
803 ret = prj_pt_unique(W_prime, W_prime); EG(ret, err);
804 dbg_nn_print("W'_x", &(W_prime->X.fp_val));
805 dbg_nn_print("W'_y", &(W_prime->Y.fp_val));
806 ret = nn_mod(&r_prime, &(W_prime->X.fp_val), q); EG(ret, err);
807
808 /* 10. Accept the signature if and only if r equals r' */
809 ret = nn_cmp(&r_prime, r, &cmp); EG(ret, err);
810 ret = (cmp != 0) ? -1 : 0;
811
812 err:
813 prj_pt_uninit(&uG);
814 prj_pt_uninit(&vY);
815 nn_uninit(&e);
816 nn_uninit(&sinv);
817 nn_uninit(&uv);
818 nn_uninit(&r_prime);
819
820 /*
821 * We can now clear data part of the context. This will clear
822 * magic and avoid further reuse of the whole context.
823 */
824 if(ctx != NULL){
825 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.ecdsa), 0, sizeof(ecdsa_verify_data)));
826 }
827
828 /* Clean what remains on the stack */
829 PTR_NULLIFY(W_prime);
830 PTR_NULLIFY(G);
831 PTR_NULLIFY(Y);
832 VAR_ZEROIFY(rshift);
833 VAR_ZEROIFY(q_bit_len);
834 PTR_NULLIFY(q);
835 PTR_NULLIFY(s);
836 PTR_NULLIFY(r);
837 VAR_ZEROIFY(hsize);
838
839 return ret;
840 }
841
842 /* Public key recovery from a signature.
843 * For ECDSA, it is possible to recover two possible public keys from
844 * a signature and a digest.
845 *
846 * Please note that this recovery is not perfect as some information is
847 * lost when reducing Rx modulo the order q during the signature. Hence,
848 * a few possible R points can provide the same r. The following algorithm
849 * assumes that Rx == r, i.e. Rx is < q and already reduced. This should
850 * happen with a probability q / p, and "bad" cases with probability
851 * (p - q) / p. Actually, some small multiples of r are also tested,
852 * but we give up after 10 tries as this can be very time consuming.
853 *
854 * With usual curve parameters, this last probability is negligible if
855 * everything is random (which should be the case for a "regular" signature
856 * algorithm) for curves with cofactor = 1. However, an adversary could
857 * willingly choose a Rx > q and the following algorithm will most certainly
858 * fail.
859 *
860 * For curves with cofactor > 1, q is usually some orders of magnitudes
861 * smaller than p and this function will certainly fail.
862 *
863 * Please use the resulting public keys with care and with all these
864 * warnings in mind!
865 *
866 */
__ecdsa_public_key_from_sig(ec_pub_key * out_pub1,ec_pub_key * out_pub2,const ec_params * params,const u8 * sig,u8 siglen,const u8 * hash,u8 hsize,ec_alg_type key_type)867 int __ecdsa_public_key_from_sig(ec_pub_key *out_pub1, ec_pub_key *out_pub2, const ec_params *params,
868 const u8 *sig, u8 siglen, const u8 *hash, u8 hsize,
869 ec_alg_type key_type)
870 {
871 int ret, iszero1, iszero2, cmp1, cmp2;
872 prj_pt uG;
873 prj_pt_t Y1, Y2;
874 prj_pt_src_t G;
875 nn u, v, e, r, s;
876 nn_src_t q, p;
877 bitcnt_t rshift, q_bit_len;
878 u8 q_len;
879 word_t order_multiplier = WORD(1);
880
881 uG.magic = WORD(0);
882 u.magic = v.magic = e.magic = r.magic = s.magic = WORD(0);
883
884 /* Zero init points */
885 ret = local_memset(&uG, 0, sizeof(prj_pt)); EG(ret, err);
886
887 /* Sanity checks */
888 MUST_HAVE((params != NULL) && (sig != NULL) && (hash != NULL) && (out_pub1 != NULL) && (out_pub2 != NULL), ret, err);
889
890 /* Import our params */
891 G = &(params->ec_gen);
892 p = &(params->ec_fp.p);
893 q = &(params->ec_gen_order);
894 q_bit_len = params->ec_gen_order_bitlen;
895 q_len = (u8)BYTECEIL(q_bit_len);
896 Y1 = &(out_pub1->y);
897 Y2 = &(out_pub2->y);
898
899 /* Check given signature length is the expected one */
900 MUST_HAVE((siglen == ECDSA_SIGLEN(q_bit_len)), ret, err);
901
902 restart:
903 /* Import r and s values from signature buffer */
904 ret = nn_init_from_buf(&r, sig, q_len); EG(ret, err);
905 ret = nn_init_from_buf(&s, sig + q_len, q_len); EG(ret, err);
906
907 /* Reject the signature if r or s is 0. */
908 ret = nn_iszero(&r, &iszero1); EG(ret, err);
909 ret = nn_iszero(&s, &iszero2); EG(ret, err);
910 ret = nn_cmp(&r, q, &cmp1); EG(ret, err);
911 ret = nn_cmp(&s, q, &cmp2); EG(ret, err);
912 MUST_HAVE(((!iszero1) && (cmp1 < 0) && !iszero2 && (cmp2 < 0)), ret, err);
913
914 /* Add a multiple of the order to r using our current order multiplier */
915 if(order_multiplier > 1){
916 int cmp;
917 ret = nn_init(&u, 0);
918 ret = nn_mul_word(&u, q, order_multiplier); EG(ret, err);
919 ret = nn_add(&r, &r, &u); EG(ret, err);
920 /* If we have reached > p, leave with an error */
921 ret = nn_cmp(&r, p, &cmp); EG(ret, err);
922 /* NOTE: we do not use a MUST_HAVE macro here since
923 * this condition can nominally happen, and we do not want
924 * a MUST_HAVE in debug mode (i.e. with an assert) to break
925 * the execution flow.
926 */
927 if(cmp < 0){
928 ret = -1;
929 goto err;
930 }
931 }
932
933 /*
934 * Compute e.
935 * If |h| > bitlen(q), set h to bitlen(q)
936 * leftmost bits of h.
937 *
938 * Note that it's easier to check here if the truncation
939 * needs to be done but implement it using a logical
940 * shift.
941 */
942 rshift = 0;
943 if ((hsize * 8) > q_bit_len) {
944 rshift = (bitcnt_t)((hsize * 8) - q_bit_len);
945 }
946 ret = nn_init_from_buf(&e, hash, hsize); EG(ret, err);
947 if (rshift) {
948 ret = nn_rshift_fixedlen(&e, &e, rshift); EG(ret, err);
949 }
950 ret = nn_mod(&e, &e, q); EG(ret, err);
951
952 /* Now to find the y coordinate by solving the curve equation.
953 * NOTE: we use uG as temporary storage.
954 */
955 ret = fp_init(&(uG.X), &(params->ec_fp)); EG(ret, err);
956 ret = fp_init(&(uG.Y), &(params->ec_fp)); EG(ret, err);
957 ret = fp_init(&(uG.Z), &(params->ec_fp)); EG(ret, err);
958 ret = fp_set_nn(&(uG.Z), &r); EG(ret, err);
959 ret = aff_pt_y_from_x(&(uG.X), &(uG.Y), &(uG.Z), &(params->ec_curve));
960 if(ret){
961 /* If we have failed here, this means that our r has certainly been
962 * reduced. Increment our multiplier and restart the process.
963 */
964 order_multiplier = (word_t)(order_multiplier + 1);
965 if(order_multiplier > 10){
966 /* Too much tries, leave ... */
967 ret = -1;
968 goto err;
969 }
970 goto restart;
971 }
972
973 /* Initialize Y1 and Y2 */
974 ret = fp_init(&(Y2->Z), &(params->ec_fp)); EG(ret, err);
975 ret = fp_one(&(Y2->Z)); EG(ret, err);
976 /* Y1 */
977 ret = prj_pt_init_from_coords(Y1, &(params->ec_curve), &(uG.Z), &(uG.X), &(Y2->Z)); EG(ret, err);
978 /* Y2 */
979 ret = prj_pt_init_from_coords(Y2, &(params->ec_curve), &(uG.Z), &(uG.Y), &(Y1->Z)); EG(ret, err);
980
981 /* Now compute u = (-e r^-1) mod q, and v = (s r^-1) mod q */
982 ret = nn_init(&u, 0); EG(ret, err);
983 ret = nn_init(&v, 0); EG(ret, err);
984 ret = nn_modinv(&r, &r, q); EG(ret, err);
985 /* u */
986 ret = nn_mod_mul(&u, &e, &r, q); EG(ret, err);
987 /* NOTE: -x mod q is (q - x) mod q, i.e. (q - x) when x is reduced, except for 0 */
988 ret = nn_mod_neg(&u, &u, q); EG(ret, err);
989 /* v */
990 ret = nn_mod_mul(&v, &s, &r, q); EG(ret, err);
991
992 /* Compute uG */
993 ret = prj_pt_mul(&uG, &u, G); EG(ret, err);
994 /* Compute vR1 and possible Y1 */
995 ret = prj_pt_mul(Y1, &v, Y1); EG(ret, err);
996 ret = prj_pt_add(Y1, Y1, &uG); EG(ret, err);
997 /* Compute vR2 and possible Y2 */
998 ret = prj_pt_mul(Y2, &v, Y2); EG(ret, err);
999 ret = prj_pt_add(Y2, Y2, &uG); EG(ret, err);
1000
1001 /* Now initialize our two public keys */
1002 /* out_pub1 */
1003 out_pub1->key_type = key_type;
1004 out_pub1->params = params;
1005 out_pub1->magic = PUB_KEY_MAGIC;
1006 /* out_pub2 */
1007 out_pub2->key_type = key_type;
1008 out_pub2->params = params;
1009 out_pub2->magic = PUB_KEY_MAGIC;
1010
1011 ret = 0;
1012
1013 err:
1014 prj_pt_uninit(&uG);
1015 nn_uninit(&r);
1016 nn_uninit(&s);
1017 nn_uninit(&u);
1018 nn_uninit(&v);
1019 nn_uninit(&e);
1020
1021 /* Clean what remains on the stack */
1022 PTR_NULLIFY(G);
1023 PTR_NULLIFY(Y1);
1024 PTR_NULLIFY(Y2);
1025 VAR_ZEROIFY(rshift);
1026 VAR_ZEROIFY(q_bit_len);
1027 PTR_NULLIFY(q);
1028 PTR_NULLIFY(p);
1029
1030 return ret;
1031 }
1032
1033 #else /* defined(WITH_SIG_ECDSA) || defined(WITH_SIG_DECDSA) */
1034
1035 /*
1036 * Dummy definition to avoid the empty translation unit ISO C warning
1037 */
1038 typedef int dummy;
1039 #endif /* WITH_SIG_ECDSA */
1040