1 /*
2 * Copyright (C) 2022 - 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 *
8 * This software is licensed under a dual BSD and GPL v2 license.
9 * See LICENSE file at the root folder of the project.
10 */
11 #include <libecc/lib_ecc_config.h>
12 #if defined(WITH_SIG_BIP0340)
13
14 /* BIP0340 needs SHA-256: check it */
15 #if !defined(WITH_HASH_SHA256)
16 #error "Error: BIP0340 needs SHA-256 to be defined! Please define it in libecc config file"
17 #endif
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/sig_algs.h>
25 #include <libecc/sig/ec_key.h>
26 #ifdef VERBOSE_INNER_VALUES
27 #define EC_SIG_ALG "BIP0340"
28 #endif
29 #include <libecc/utils/dbg_sig.h>
30
31 /*
32 * The current implementation is for the BIP0340 signature as described
33 * in https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
34 *
35 * The BIP0340 signature is only compatible with SHA-256 and secp256k1,
36 * but we extend it to any hash function or curve.
37 *
38 */
39
40 /* The "hash" function static prefixes */
41 #define BIP0340_AUX "BIP0340/aux"
42 #define BIP0340_NONCE "BIP0340/nonce"
43 #define BIP0340_CHALLENGE "BIP0340/challenge"
44
_bip0340_hash(const u8 * tag,u32 tag_len,const u8 * m,u32 m_len,const hash_mapping * hm,hash_context * h_ctx)45 ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_hash(const u8 *tag, u32 tag_len,
46 const u8 *m, u32 m_len,
47 const hash_mapping *hm, hash_context *h_ctx)
48 {
49 int ret;
50 u8 hash[MAX_DIGEST_SIZE];
51
52 MUST_HAVE((h_ctx != NULL), ret, err);
53
54 ret = hash_mapping_callbacks_sanity_check(hm); EG(ret, err);
55
56 ret = hm->hfunc_init(h_ctx); EG(ret, err);
57 ret = hm->hfunc_update(h_ctx, tag, tag_len); EG(ret, err);
58 ret = hm->hfunc_finalize(h_ctx, hash); EG(ret, err);
59
60 /* Now compute hash(hash(tag) || hash(tag) || m) */
61 ret = hm->hfunc_init(h_ctx); EG(ret, err);
62 ret = hm->hfunc_update(h_ctx, hash, hm->digest_size); EG(ret, err);
63 ret = hm->hfunc_update(h_ctx, hash, hm->digest_size); EG(ret, err);
64 ret = hm->hfunc_update(h_ctx, m, m_len); EG(ret, err);
65
66 ret = 0;
67 err:
68 return ret;
69 }
70
71 /* Set the scalar value depending on the parity bit of the input
72 * point y coordinate.
73 */
_bip0340_set_scalar(nn_t scalar,nn_src_t q,prj_pt_src_t P)74 ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_set_scalar(nn_t scalar,
75 nn_src_t q,
76 prj_pt_src_t P)
77 {
78 int ret, isodd, isone;
79
80 /* Sanity check */
81 ret = prj_pt_check_initialized(P); EG(ret, err);
82
83 /* This operation is only meaningful on the "affine" representative.
84 * Check it.
85 */
86 ret = nn_isone(&(P->Z.fp_val), &isone); EG(ret, err);
87 MUST_HAVE((isone), ret, err);
88
89 /* Check if Py is odd or even */
90 ret = nn_isodd(&(P->Y.fp_val), &isodd); EG(ret, err);
91
92 if(isodd){
93 /* Replace the input scalar by (q - scalar)
94 * (its opposite modulo q)
95 */
96 ret = nn_mod_neg(scalar, scalar, q); EG(ret, err);
97 }
98
99 err:
100 return ret;
101 }
102
103 /*
104 * Generic *internal* helper for BIP340 public key initialization
105 * functions. The function returns 0 on success, -1 on error.
106 */
bip0340_init_pub_key(ec_pub_key * out_pub,const ec_priv_key * in_priv)107 int bip0340_init_pub_key(ec_pub_key *out_pub, const ec_priv_key *in_priv)
108 {
109 prj_pt_src_t G;
110 int ret;
111
112 MUST_HAVE((out_pub != NULL), ret, err);
113
114 /* Zero init public key to be generated */
115 ret = local_memset(out_pub, 0, sizeof(ec_pub_key)); EG(ret, err);
116
117 ret = priv_key_check_initialized_and_type(in_priv, BIP0340); EG(ret, err);
118
119 /* Y = xG */
120 G = &(in_priv->params->ec_gen);
121 /* Use blinding when computing point scalar multiplication */
122 ret = prj_pt_mul_blind(&(out_pub->y), &(in_priv->x), G); EG(ret, err);
123
124 out_pub->key_type = BIP0340;
125 out_pub->params = in_priv->params;
126 out_pub->magic = PUB_KEY_MAGIC;
127
128 err:
129 return ret;
130 }
131
132 /*
133 * Generic *internal* helper for BIP0340 signature length functions.
134 */
bip0340_siglen(u16 p_bit_len,u16 q_bit_len,u8 hsize,u8 blocksize,u8 * siglen)135 int bip0340_siglen(u16 p_bit_len, u16 q_bit_len, u8 hsize, u8 blocksize,
136 u8 *siglen)
137 {
138 int ret;
139
140 MUST_HAVE((siglen != NULL), ret, err);
141 MUST_HAVE(((p_bit_len <= CURVES_MAX_P_BIT_LEN) &&
142 (q_bit_len <= CURVES_MAX_Q_BIT_LEN) &&
143 (hsize <= MAX_DIGEST_SIZE) && (blocksize <= MAX_BLOCK_SIZE)),
144 ret, err);
145
146 (*siglen) = (u8)BIP0340_SIGLEN(p_bit_len, q_bit_len);
147 ret = 0;
148
149 err:
150 return ret;
151 }
152
153 /*
154 * Generic *internal* helper for BIP0340 signature.
155 * NOTE: because of the semi-deterministinc nonce generation
156 * process, streaming mode is NOT supported for signing.
157 * Hence the following all-in-one signature function.
158 *
159 * The function returns 0 on success, -1 on error.
160 */
_bip0340_sign(u8 * sig,u8 siglen,const ec_key_pair * key_pair,const u8 * m,u32 mlen,int (* rand)(nn_t out,nn_src_t q),ec_alg_type sig_type,hash_alg_type hash_type,const u8 * adata,u16 adata_len)161 int _bip0340_sign(u8 *sig, u8 siglen, const ec_key_pair *key_pair,
162 const u8 *m, u32 mlen, int (*rand) (nn_t out, nn_src_t q),
163 ec_alg_type sig_type, hash_alg_type hash_type,
164 const u8 *adata, u16 adata_len)
165 {
166 prj_pt_src_t G;
167 prj_pt Y;
168 nn_src_t q;
169 nn k, d, e;
170 prj_pt kG;
171 const ec_priv_key *priv_key;
172 const ec_pub_key *pub_key;
173 bitcnt_t p_bit_len, q_bit_len;
174 u8 i, p_len, q_len;
175 int ret, cmp, iszero;
176 hash_context h_ctx;
177 const hash_mapping *hm;
178 u8 buff[MAX_DIGEST_SIZE];
179 #ifdef USE_SIG_BLINDING
180 /* b is the blinding mask */
181 nn b, binv;
182 b.magic = binv.magic = WORD(0);
183 #endif /* USE_SIG_BLINDING */
184
185 k.magic = d.magic = e.magic = kG.magic = Y.magic = WORD(0);
186
187 FORCE_USED_VAR(adata_len);
188
189 /* No ancillary data is expected with BIP0340 */
190 MUST_HAVE((key_pair != NULL) && (sig != NULL) && (adata == NULL), ret, err);
191
192 /* Check our algorithm type */
193 MUST_HAVE((sig_type == BIP0340), ret, err);
194
195 /* Check that keypair is initialized */
196 ret = key_pair_check_initialized_and_type(key_pair, BIP0340); EG(ret, err);
197
198 /* Get the hash mapping */
199 ret = get_hash_by_type(hash_type, &hm); EG(ret, err);
200 MUST_HAVE((hm != NULL), ret, err);
201 ret = hash_mapping_callbacks_sanity_check(hm); EG(ret, err);
202
203 /* Make things more readable */
204 priv_key = &(key_pair->priv_key);
205 pub_key = &(key_pair->pub_key);
206 G = &(priv_key->params->ec_gen);
207 q = &(priv_key->params->ec_gen_order);
208 p_bit_len = priv_key->params->ec_fp.p_bitlen;
209 q_bit_len = priv_key->params->ec_gen_order_bitlen;
210 q_len = (u8)BYTECEIL(q_bit_len);
211 p_len = (u8)BYTECEIL(p_bit_len);
212
213 /* Copy the public key point to work on the unique
214 * affine representative.
215 */
216 ret = prj_pt_copy(&Y, &(pub_key->y)); EG(ret, err);
217 ret = prj_pt_unique(&Y, &Y); EG(ret, err);
218
219 ret = nn_init(&d, 0); EG(ret, err);
220 ret = nn_copy(&d, &(priv_key->x)); EG(ret, err);
221
222 dbg_nn_print("d", &d);
223
224 /* Check signature size */
225 MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err);
226 MUST_HAVE((p_len == BIP0340_R_LEN(p_bit_len)), ret, err);
227 MUST_HAVE((q_len == BIP0340_S_LEN(q_bit_len)), ret, err);
228
229 /* Fail if d = 0 or d >= q */
230 ret = nn_iszero(&d, &iszero); EG(ret, err);
231 ret = nn_cmp(&d, q, &cmp); EG(ret, err);
232 MUST_HAVE((!iszero) && (cmp < 0), ret, err);
233
234 /* Adjust d depending on public key y */
235 ret = _bip0340_set_scalar(&d, q, &Y); EG(ret, err);
236
237 /* Compute the nonce in a deterministic way.
238 * First, we get the random auxilary data.
239 */
240 #ifdef NO_KNOWN_VECTORS
241 /* NOTE: when we do not need self tests for known vectors,
242 * we can be strict about random function handler!
243 * This allows us to avoid the corruption of such a pointer.
244 */
245 /* Sanity check on the handler before calling it */
246 MUST_HAVE((rand == nn_get_random_mod), ret, err);
247 #endif
248 ret = nn_init(&e, 0); EG(ret, err);
249 ret = nn_one(&e); EG(ret, err);
250 ret = nn_lshift(&e, &e, (bitcnt_t)(8 * q_len)); EG(ret, err);
251 if(rand == NULL){
252 rand = nn_get_random_mod;
253 }
254 ret = rand(&k, &e); EG(ret, err);
255 dbg_nn_print("a", &k);
256
257 MUST_HAVE((siglen >= q_len), ret, err);
258 ret = nn_export_to_buf(&sig[0], q_len, &k); EG(ret, err);
259
260 /* Compute the seed for the nonce computation */
261 ret = _bip0340_hash((const u8*)BIP0340_AUX, sizeof(BIP0340_AUX) - 1,
262 &sig[0], q_len, hm, &h_ctx); EG(ret, err);
263 ret = hm->hfunc_finalize(&h_ctx, buff); EG(ret, err);
264
265 ret = nn_export_to_buf(&sig[0], q_len, &d); EG(ret, err);
266
267 if(q_len > hm->digest_size){
268 for(i = 0; i < hm->digest_size; i++){
269 sig[i] ^= buff[i];
270 }
271 ret = _bip0340_hash((const u8*)BIP0340_NONCE, sizeof(BIP0340_NONCE) - 1,
272 &sig[0], q_len, hm, &h_ctx); EG(ret, err);
273 }
274 else{
275 for(i = 0; i < q_len; i++){
276 buff[i] ^= sig[i];
277 }
278 ret = _bip0340_hash((const u8*)BIP0340_NONCE, sizeof(BIP0340_NONCE) - 1,
279 &buff[0], hm->digest_size, hm, &h_ctx); EG(ret, err);
280 }
281 ret = fp_export_to_buf(&sig[0], p_len, &(Y.X)); EG(ret, err);
282 ret = hm->hfunc_update(&h_ctx, &sig[0], p_len); EG(ret, err);
283 ret = hm->hfunc_update(&h_ctx, m, mlen); EG(ret, err);
284 ret = hm->hfunc_finalize(&h_ctx, buff); EG(ret, err);
285
286 /* Now import the semi-deterministic nonce modulo q */
287 ret = nn_init_from_buf(&k, buff, hm->digest_size); EG(ret, err);
288 ret = nn_mod(&k, &k, q); EG(ret, err);
289
290 dbg_nn_print("k", &k);
291
292 /* Fail if the nonce is zero */
293 ret = nn_iszero(&k, &iszero); EG(ret, err);
294 MUST_HAVE((!iszero), ret, err);
295
296 /* Proceed with the modulation exponentiation kG */
297 #ifdef USE_SIG_BLINDING
298 /* We use blinding for the scalar multiplication */
299 ret = prj_pt_mul_blind(&kG, &k, G); EG(ret, err);
300 #else
301 ret = prj_pt_mul(&kG, &k, G); EG(ret, err);
302 #endif
303 ret = prj_pt_unique(&kG, &kG); EG(ret, err);
304
305 dbg_ec_point_print("(k G)", &kG);
306
307 /* Update k depending on the kG y coordinate */
308 ret = _bip0340_set_scalar(&k, q, &kG); EG(ret, err);
309
310 /* Compute e */
311 /* We export our r here */
312 ret = fp_export_to_buf(&sig[0], p_len, &(kG.X)); EG(ret, err);
313 ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1,
314 &sig[0], p_len, hm, &h_ctx); EG(ret, err);
315 /* Export our public key */
316 ret = fp_export_to_buf(&sig[0], p_len, &(Y.X)); EG(ret, err);
317 ret = hm->hfunc_update(&h_ctx, &sig[0], p_len); EG(ret, err);
318 /* Update with the message */
319 ret = hm->hfunc_update(&h_ctx, m, mlen); EG(ret, err);
320 ret = hm->hfunc_finalize(&h_ctx, buff); EG(ret, err);
321 ret = nn_init_from_buf(&e, buff, hm->digest_size); EG(ret, err);
322 ret = nn_mod(&e, &e, q); EG(ret, err);
323 dbg_nn_print("e", &e);
324
325 /* Export our r in the signature */
326 dbg_nn_print("r", &(kG.X.fp_val));
327 ret = fp_export_to_buf(&sig[0], p_len, &(kG.X)); EG(ret, err);
328
329 /* Compute (k + ed) mod n */
330 #ifdef USE_SIG_BLINDING
331 ret = nn_get_random_mod(&b, q); EG(ret, err);
332 dbg_nn_print("b", &b);
333 #endif /* USE_SIG_BLINDING */
334
335 #ifdef USE_SIG_BLINDING
336 /* Blind e with b */
337 ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err);
338 /* Blind k with b */
339 ret = nn_mod_mul(&k, &k, &b, q); EG(ret, err);
340 #endif /* USE_SIG_BLINDING */
341
342 ret = nn_mod_mul(&e, &e, &d, q); EG(ret, err);
343 ret = nn_mod_add(&e, &k, &e, q); EG(ret, err);
344
345 #ifdef USE_SIG_BLINDING
346 /* Unblind */
347 /* NOTE: we use Fermat's little theorem inversion for
348 * constant time here. This is possible since q is prime.
349 */
350 ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err);
351 ret = nn_mod_mul(&e, &e, &binv, q); EG(ret, err);
352 #endif /* USE_SIG_BLINDING */
353
354 /* Export our s in the signature */
355 dbg_nn_print("s", &e);
356 ret = nn_export_to_buf(&sig[p_len], q_len, &e); EG(ret, err);
357
358 err:
359 PTR_NULLIFY(G);
360 PTR_NULLIFY(q);
361 PTR_NULLIFY(priv_key);
362 PTR_NULLIFY(pub_key);
363 PTR_NULLIFY(hm);
364
365 prj_pt_uninit(&Y);
366 nn_uninit(&k);
367 nn_uninit(&e);
368 nn_uninit(&d);
369
370 return ret;
371 }
372
373 /* local helper for context sanity checks. Returns 0 on success, -1 on error. */
374 #define BIP0340_VERIFY_MAGIC ((word_t)(0x340175910abafcddULL))
375 #define BIP0340_VERIFY_CHECK_INITIALIZED(A, ret, err) \
376 MUST_HAVE((((const void *)(A)) != NULL) && \
377 ((A)->magic == BIP0340_VERIFY_MAGIC), ret, err)
378
379 /*
380 * Generic *internal* helper for BIP0340 verification initialization functions.
381 * The function returns 0 on success, -1 on error.
382 */
_bip0340_verify_init(struct ec_verify_context * ctx,const u8 * sig,u8 siglen)383 int _bip0340_verify_init(struct ec_verify_context *ctx,
384 const u8 *sig, u8 siglen)
385 {
386 bitcnt_t p_bit_len, q_bit_len;
387 u8 p_len, q_len;
388 int ret, cmp;
389 nn_src_t q;
390 prj_pt Y;
391 fp *rx;
392 nn *s;
393 u8 Pubx[NN_MAX_BYTE_LEN];
394
395 /* First, verify context has been initialized */
396 ret = sig_verify_check_initialized(ctx); EG(ret, err);
397
398 /* Do some sanity checks on input params */
399 ret = pub_key_check_initialized_and_type(ctx->pub_key, BIP0340); EG(ret, err);
400 MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) &&
401 (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err);
402 MUST_HAVE((sig != NULL), ret, err);
403
404 /* Since we call a callback, sanity check our mapping */
405 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
406
407 /* Make things more readable */
408 q = &(ctx->pub_key->params->ec_gen_order);
409 p_bit_len = ctx->pub_key->params->ec_fp.p_bitlen;
410 q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen;
411 p_len = (u8)BYTECEIL(p_bit_len);
412 q_len = (u8)BYTECEIL(q_bit_len);
413 s = &(ctx->verify_data.bip0340.s);
414 rx = &(ctx->verify_data.bip0340.r);
415
416 MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err);
417 MUST_HAVE((p_len == BIP0340_R_LEN(p_bit_len)), ret, err);
418 MUST_HAVE((q_len == BIP0340_S_LEN(q_bit_len)), ret, err);
419
420 /* Copy the public key point to work on the unique
421 * affine representative.
422 */
423 ret = prj_pt_copy(&Y, &(ctx->pub_key->y)); EG(ret, err);
424 ret = prj_pt_unique(&Y, &Y); EG(ret, err);
425
426 /* Extract r and s */
427 ret = fp_init(rx, ctx->pub_key->params->ec_curve.a.ctx); EG(ret, err);
428 ret = fp_import_from_buf(rx, &sig[0], p_len); EG(ret, err);
429 ret = nn_init_from_buf(s, &sig[p_len], q_len); EG(ret, err);
430 ret = nn_cmp(s, q, &cmp); EG(ret, err);
431 MUST_HAVE((cmp < 0), ret, err);
432
433 dbg_nn_print("r", &(rx->fp_val));
434 dbg_nn_print("s", s);
435
436 /* Initialize our hash context */
437 ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1,
438 &sig[0], p_len, ctx->h,
439 &(ctx->verify_data.bip0340.h_ctx)); EG(ret, err);
440 ret = fp_export_to_buf(&Pubx[0], p_len, &(Y.X)); EG(ret, err);
441 ret = ctx->h->hfunc_update(&(ctx->verify_data.bip0340.h_ctx), &Pubx[0], p_len); EG(ret, err);
442 ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err);
443
444 ctx->verify_data.bip0340.magic = BIP0340_VERIFY_MAGIC;
445
446 err:
447 PTR_NULLIFY(q);
448 PTR_NULLIFY(rx);
449 PTR_NULLIFY(s);
450
451 prj_pt_uninit(&Y);
452
453 if (ret && (ctx != NULL)) {
454 /*
455 * Signature is invalid. Clear data part of the context.
456 * This will clear magic and avoid further reuse of the
457 * whole context.
458 */
459 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.bip0340), 0,
460 sizeof(bip0340_verify_data)));
461 }
462
463 return ret;
464 }
465
466 /*
467 * Generic *internal* helper for BIP0340 verification update functions.
468 * The function returns 0 on success, -1 on error.
469 */
_bip0340_verify_update(struct ec_verify_context * ctx,const u8 * chunk,u32 chunklen)470 int _bip0340_verify_update(struct ec_verify_context *ctx,
471 const u8 *chunk, u32 chunklen)
472 {
473 int ret;
474
475 /*
476 * First, verify context has been initialized and public
477 * part too. This guarantees the context is an BIP0340
478 * verification one and we do not update() or finalize()
479 * before init().
480 */
481 ret = sig_verify_check_initialized(ctx); EG(ret, err);
482 BIP0340_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.bip0340), ret, err);
483
484 /* Since we call a callback, sanity check our mapping */
485 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
486 ret = ctx->h->hfunc_update(&(ctx->verify_data.bip0340.h_ctx), chunk,
487 chunklen);
488
489 err:
490 return ret;
491 }
492
493 /*
494 * Generic *internal* helper for BIP0340 verification finalization
495 * functions. The function returns 0 on success, -1 on error.
496 */
_bip0340_verify_finalize(struct ec_verify_context * ctx)497 int _bip0340_verify_finalize(struct ec_verify_context *ctx)
498 {
499 prj_pt_src_t G;
500 nn_src_t s, q;
501 fp_src_t r;
502 nn e;
503 prj_pt sG, eY, Y;
504 u8 e_buf[MAX_DIGEST_SIZE];
505 u8 hsize;
506 int ret, iszero, isodd, cmp;
507
508 ret = sig_verify_check_initialized(ctx); EG(ret, err);
509 BIP0340_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.bip0340), ret, err);
510
511 /* Since we call a callback, sanity check our mapping */
512 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
513
514 /* Zero init points */
515 ret = local_memset(&sG, 0, sizeof(prj_pt)); EG(ret, err);
516 ret = local_memset(&eY, 0, sizeof(prj_pt)); EG(ret, err);
517
518 /* Make things more readable */
519 G = &(ctx->pub_key->params->ec_gen);
520 hsize = ctx->h->digest_size;
521 q = &(ctx->pub_key->params->ec_gen_order);
522 s = &(ctx->verify_data.bip0340.s);
523 r = &(ctx->verify_data.bip0340.r);
524
525 /* Copy the public key point to work on the unique
526 * affine representative.
527 */
528 ret = prj_pt_copy(&Y, &(ctx->pub_key->y)); EG(ret, err);
529 ret = prj_pt_unique(&Y, &Y); EG(ret, err);
530
531 /* Compute e */
532 ret = ctx->h->hfunc_finalize(&(ctx->verify_data.bip0340.h_ctx),
533 &e_buf[0]); EG(ret, err);
534 ret = nn_init_from_buf(&e, e_buf, hsize); EG(ret, err);
535 ret = nn_mod(&e, &e, q); EG(ret, err);
536
537 dbg_nn_print("e", &e);
538
539 /* Compute s G - e Y */
540 ret = prj_pt_mul(&sG, s, G); EG(ret, err);
541 ret = nn_mod_neg(&e, &e, q); EG(ret, err); /* compute -e = (q - e) mod q */
542 /* Do we have to "lift" Y the public key ? */
543 ret = nn_isodd(&(Y.Y.fp_val), &isodd); EG(ret, err);
544 if(isodd){
545 /* If yes, negate the y coordinate */
546 ret = fp_neg(&(Y.Y), &(Y.Y)); EG(ret, err);
547 }
548 ret = prj_pt_mul(&eY, &e, &Y); EG(ret, err);
549 ret = prj_pt_add(&sG, &sG, &eY); EG(ret, err);
550 ret = prj_pt_unique(&sG, &sG); EG(ret, err);
551
552 dbg_ec_point_print("(s G - e Y)", &sG);
553
554 /* Reject point at infinity */
555 ret = prj_pt_iszero(&sG, &iszero); EG(ret, err);
556 MUST_HAVE((!iszero), ret, err);
557
558 /* Reject non even Y coordinate */
559 ret = nn_isodd(&(sG.Y.fp_val), &isodd); EG(ret, err);
560 MUST_HAVE((!isodd), ret, err);
561
562 /* Check the x coordinate against r */
563 ret = nn_cmp(&(r->fp_val), &(sG.X.fp_val), &cmp); EG(ret, err);
564 ret = (cmp == 0) ? 0 : -1;
565
566 err:
567 PTR_NULLIFY(G);
568 PTR_NULLIFY(s);
569 PTR_NULLIFY(q);
570 PTR_NULLIFY(r);
571
572 nn_uninit(&e);
573 prj_pt_uninit(&sG);
574 prj_pt_uninit(&eY);
575 prj_pt_uninit(&Y);
576
577 /*
578 * We can now clear data part of the context. This will clear
579 * magic and avoid further reuse of the whole context.
580 */
581 if(ctx != NULL){
582 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.bip0340), 0,
583 sizeof(bip0340_verify_data)));
584 }
585
586 return ret;
587 }
588
589 /*
590 * Helper to compute the seed to generate batch verification randomizing scalars.
591 *
592 */
593 /****************************************************/
594 /*
595 * 32-bit integer manipulation macros (big endian)
596 */
597 #ifndef GET_UINT32_LE
598 #define GET_UINT32_LE(n, b, i) \
599 do { \
600 (n) = ( ((u32) (b)[(i) + 3]) << 24 ) \
601 | ( ((u32) (b)[(i) + 2]) << 16 ) \
602 | ( ((u32) (b)[(i) + 1]) << 8 ) \
603 | ( ((u32) (b)[(i) ]) ); \
604 } while( 0 )
605 #endif
606
607 #ifndef PUT_UINT32_LE
608 #define PUT_UINT32_LE(n, b, i) \
609 do { \
610 (b)[(i) + 3] = (u8) ( (n) >> 24 ); \
611 (b)[(i) + 2] = (u8) ( (n) >> 16 ); \
612 (b)[(i) + 1] = (u8) ( (n) >> 8 ); \
613 (b)[(i) ] = (u8) ( (n) ); \
614 } while( 0 )
615 #endif
616
617 #ifndef PUT_UINT32_BE
618 #define PUT_UINT32_BE(n, b, i) \
619 do { \
620 (b)[(i) ] = (u8) ( (n) >> 24 ); \
621 (b)[(i) + 1] = (u8) ( (n) >> 16 ); \
622 (b)[(i) + 2] = (u8) ( (n) >> 8 ); \
623 (b)[(i) + 3] = (u8) ( (n) ); \
624 } while( 0 )
625 #endif
626
627 #define _CHACHA20_ROTL_(x, y) (((x) << (y)) | ((x) >> ((sizeof(u32) * 8) - (y))))
628 #define CHACA20_ROTL(x, y) ((((y) < (sizeof(u32) * 8)) && ((y) > 0)) ? (_CHACHA20_ROTL_(x, y)) : (x))
629
630 #define CHACHA20_QROUND(a, b, c, d) do { \
631 (a) += (b); \
632 (d) ^= (a); \
633 (d) = CHACA20_ROTL((d), 16); \
634 (c) += (d); \
635 (b) ^= (c); \
636 (b) = CHACA20_ROTL((b), 12); \
637 (a) += (b); \
638 (d) ^= (a); \
639 (d) = CHACA20_ROTL((d), 8); \
640 (c) += (d); \
641 (b) ^= (c); \
642 (b) = CHACA20_ROTL((b), 7); \
643 } while(0)
644
645 #define CHACHA20_INNER_BLOCK(s) do { \
646 CHACHA20_QROUND(s[0], s[4], s[ 8], s[12]); \
647 CHACHA20_QROUND(s[1], s[5], s[ 9], s[13]); \
648 CHACHA20_QROUND(s[2], s[6], s[10], s[14]); \
649 CHACHA20_QROUND(s[3], s[7], s[11], s[15]); \
650 CHACHA20_QROUND(s[0], s[5], s[10], s[15]); \
651 CHACHA20_QROUND(s[1], s[6], s[11], s[12]); \
652 CHACHA20_QROUND(s[2], s[7], s[ 8], s[13]); \
653 CHACHA20_QROUND(s[3], s[4], s[ 9], s[14]); \
654 } while(0)
655
656 #define CHACHA20_MAX_ASKED_LEN 64
657
_bip0340_chacha20_block(const u8 key[32],const u8 nonce[12],u32 block_counter,u8 * stream,u32 stream_len)658 ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_chacha20_block(const u8 key[32], const u8 nonce[12], u32 block_counter, u8 *stream, u32 stream_len){
659 int ret;
660 u32 state[16];
661 u32 initial_state[16];
662 unsigned int i;
663
664 MUST_HAVE((stream != NULL), ret, err);
665 MUST_HAVE((stream_len <= CHACHA20_MAX_ASKED_LEN), ret, err);
666
667 /* Initial state */
668 state[0] = 0x61707865;
669 state[1] = 0x3320646e;
670 state[2] = 0x79622d32;
671 state[3] = 0x6b206574;
672
673 for(i = 4; i < 12; i++){
674 GET_UINT32_LE(state[i], key, (4 * (i - 4)));
675 }
676 state[12] = block_counter;
677 for(i = 13; i < 16; i++){
678 GET_UINT32_LE(state[i], nonce, (4 * (i - 13)));
679 }
680
681 /* Core loop */
682 ret = local_memcpy(initial_state, state, sizeof(state)); EG(ret, err);
683 for(i = 0; i < 10; i++){
684 CHACHA20_INNER_BLOCK(state);
685 }
686 /* Serialize and output the block */
687 for(i = 0; i < 16; i++){
688 u32 tmp = (u32)(state[i] + initial_state[i]);
689 PUT_UINT32_LE(tmp, (u8*)(&state[i]), 0);
690 }
691 ret = local_memcpy(stream, &state[0], stream_len);
692
693 err:
694 return ret;
695 }
696
_bip0340_compute_batch_csprng_one_scalar(const u8 * seed,u32 seedlen,u8 * scalar,u32 scalar_len,u32 num)697 ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_compute_batch_csprng_one_scalar(const u8 *seed, u32 seedlen,
698 u8 *scalar, u32 scalar_len, u32 num)
699 {
700 int ret;
701 u8 nonce[12];
702
703 /* Sanity check for ChaCha20 */
704 MUST_HAVE((seedlen == SHA256_DIGEST_SIZE) && (scalar_len <= CHACHA20_MAX_ASKED_LEN), ret, err);
705
706 /* NOTE: nothing in the BIP340 specification fixes the nonce for
707 * ChaCha20. We simply use 0 here for the nonce. */
708 ret = local_memset(nonce, 0, sizeof(nonce)); EG(ret, err);
709
710 /* Use our CSPRNG based on ChaCha20 to generate the scalars */
711 ret = _bip0340_chacha20_block(seed, nonce, num, scalar, scalar_len);
712
713 err:
714 return ret;
715 }
716
_bip0340_compute_batch_csprng_scalars(const u8 * seed,u32 seedlen,u8 * scalar,u32 scalar_len,u32 * num,nn_src_t q,bitcnt_t q_bit_len,u8 q_len,nn_t a)717 ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_compute_batch_csprng_scalars(const u8 *seed, u32 seedlen,
718 u8 *scalar, u32 scalar_len,
719 u32 *num, nn_src_t q,
720 bitcnt_t q_bit_len, u8 q_len,
721 nn_t a)
722 {
723 int ret, iszero, cmp;
724 u32 size, remain;
725
726 MUST_HAVE((seed != NULL) && (scalar != NULL) && (num != NULL) && (a != NULL), ret, err);
727 MUST_HAVE((scalar_len >= q_len), ret, err);
728
729 gen_scalar_again:
730 size = remain = 0;
731 while(size < q_len){
732 MUST_HAVE((*num) < 0xffffffff, ret, err);
733 remain = ((q_len - size) < CHACHA20_MAX_ASKED_LEN) ? (q_len - size): CHACHA20_MAX_ASKED_LEN;
734 ret = _bip0340_compute_batch_csprng_one_scalar(seed, seedlen,
735 &scalar[size], remain,
736 (*num)); EG(ret, err);
737 (*num)++;
738 size += remain;
739 }
740 if((q_bit_len % 8) != 0){
741 /* Handle the cutoff when q_bit_len is not a byte multiple */
742 scalar[0] &= (u8)((0x1 << (q_bit_len % 8)) - 1);
743 }
744 /* Import the scalar */
745 ret = nn_init_from_buf(a, scalar, q_len); EG(ret, err);
746 /* Check if the scalar is between 1 and q-1 */
747 ret = nn_iszero(a, &iszero); EG(ret, err);
748 ret = nn_cmp(a, q, &cmp); EG(ret, err);
749 if((iszero) || (cmp >= 0)){
750 goto gen_scalar_again;
751 }
752
753 ret = 0;
754 err:
755 return ret;
756 }
757
_bip0340_compute_batch_csprng_seed(const u8 ** s,const u8 * s_len,const ec_pub_key ** pub_keys,const u8 ** m,const u32 * m_len,u32 num,u8 p_len,u8 * seed,u32 seedlen)758 ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_compute_batch_csprng_seed(const u8 **s, const u8 *s_len,
759 const ec_pub_key **pub_keys,
760 const u8 **m, const u32 *m_len, u32 num,
761 u8 p_len, u8 *seed, u32 seedlen)
762 {
763 int ret;
764 u32 i;
765 hash_context h_ctx;
766 u8 Pubx[NN_MAX_BYTE_LEN];
767 const hash_mapping *hm;
768
769 /* NOTE: sanity checks on inputs are performed by the upper layer */
770
771 ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err);
772
773 /* Get our hash mapping for SHA-256 as we need a fixed 256-bit key
774 * for keying our ChaCha20 CSPRNG
775 */
776 ret = get_hash_by_type(SHA256, &hm); EG(ret, err);
777 MUST_HAVE((hm != NULL), ret, err);
778
779 MUST_HAVE((seedlen == hm->digest_size), ret, err);
780
781 /* As per specification, seed = seed_hash(pk1..pku || m1..mu || sig1..sigu), instantiated
782 * with SHA-256 */
783 ret = hm->hfunc_init(&h_ctx); EG(ret, err);
784 for(i = 0; i < num; i++){
785 ret = fp_export_to_buf(&Pubx[0], p_len, &(pub_keys[i]->y.X)); EG(ret, err);
786 ret = hm->hfunc_update(&h_ctx, &Pubx[0], p_len); EG(ret, err);
787 }
788 for(i = 0; i < num; i++){
789 ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err);
790 }
791 for(i = 0; i < num; i++){
792 ret = hm->hfunc_update(&h_ctx, s[i], s_len[i]); EG(ret, err);
793 }
794 ret = hm->hfunc_finalize(&h_ctx, seed);
795
796 err:
797 return ret;
798 }
799
800 /* Batch verification function:
801 * This function takes multiple signatures/messages/public keys, and
802 * checks in an optimized way all the signatures.
803 *
804 * This returns 0 if *all* the signatures are correct, and -1 if at least
805 * one signature is not correct.
806 *
807 */
_bip0340_verify_batch_no_memory(const u8 ** s,const u8 * s_len,const ec_pub_key ** pub_keys,const u8 ** m,const u32 * m_len,u32 num,ec_alg_type sig_type,hash_alg_type hash_type,const u8 ** adata,const u16 * adata_len)808 static int _bip0340_verify_batch_no_memory(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys,
809 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type,
810 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len)
811 {
812 nn_src_t q = NULL;
813 prj_pt_src_t G = NULL;
814 prj_pt_t R = NULL, Y = NULL;
815 prj_pt Tmp, R_sum, P_sum;
816 nn S, S_sum, e, a;
817 fp rx;
818 u8 hash[MAX_DIGEST_SIZE];
819 u8 Pubx[NN_MAX_BYTE_LEN];
820 const ec_pub_key *pub_key, *pub_key0;
821 int ret, iszero, isodd, cmp;
822 prj_pt_src_t pub_key_y;
823 hash_context h_ctx;
824 const hash_mapping *hm;
825 ec_shortw_crv_src_t shortw_curve;
826 ec_alg_type key_type = UNKNOWN_ALG;
827 bitcnt_t p_bit_len, q_bit_len;
828 u8 p_len, q_len;
829 u16 hsize;
830 u32 i;
831 u8 chacha20_seed[SHA256_DIGEST_SIZE];
832 u8 chacha20_scalar[BYTECEIL(CURVES_MAX_Q_BIT_LEN)];
833 u32 chacha20_scalar_counter = 1;
834
835 Tmp.magic = R_sum.magic = P_sum.magic = WORD(0);
836 S.magic = S_sum.magic = e.magic = a.magic = WORD(0);
837 rx.magic = WORD(0);
838
839 FORCE_USED_VAR(adata_len);
840 FORCE_USED_VAR(adata);
841
842 /* First, some sanity checks */
843 MUST_HAVE((s != NULL) && (pub_keys != NULL) && (m != NULL), ret, err);
844 /* We need at least one element in our batch data bags */
845 MUST_HAVE((num > 0), ret, err);
846
847 /* Zeroize buffers */
848 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err);
849 ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err);
850 ret = local_memset(chacha20_seed, 0,sizeof(chacha20_seed)); EG(ret, err);
851 ret = local_memset(chacha20_scalar, 0,sizeof(chacha20_scalar)); EG(ret, err);
852
853 pub_key0 = pub_keys[0];
854 MUST_HAVE((pub_key0 != NULL), ret, err);
855
856 /* Get our hash mapping */
857 ret = get_hash_by_type(hash_type, &hm); EG(ret, err);
858 hsize = hm->digest_size;
859 MUST_HAVE((hm != NULL), ret, err);
860
861 for(i = 0; i < num; i++){
862 u8 siglen;
863 const u8 *sig = NULL;
864
865 ret = pub_key_check_initialized_and_type(pub_keys[i], BIP0340); EG(ret, err);
866
867 /* Make things more readable */
868 pub_key = pub_keys[i];
869
870 /* Sanity check that all our public keys have the same parameters */
871 MUST_HAVE((pub_key->params) == (pub_key0->params), ret, err);
872
873 q = &(pub_key->params->ec_gen_order);
874 shortw_curve = &(pub_key->params->ec_curve);
875 pub_key_y = &(pub_key->y);
876 key_type = pub_key->key_type;
877 G = &(pub_key->params->ec_gen);
878 p_bit_len = pub_key->params->ec_fp.p_bitlen;
879 q_bit_len = pub_key->params->ec_gen_order_bitlen;
880 p_len = (u8)BYTECEIL(p_bit_len);
881 q_len = (u8)BYTECEIL(q_bit_len);
882
883 /* Check given signature length is the expected one */
884 siglen = s_len[i];
885 sig = s[i];
886 MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err);
887 MUST_HAVE((siglen == (BIP0340_R_LEN(p_bit_len) + BIP0340_S_LEN(q_bit_len))), ret, err);
888
889 /* Check the key type versus the algorithm */
890 MUST_HAVE((key_type == sig_type), ret, err);
891
892 if(i == 0){
893 /* Initialize our sums to zero/point at infinity */
894 ret = nn_init(&S_sum, 0); EG(ret, err);
895 ret = prj_pt_init(&R_sum, shortw_curve); EG(ret, err);
896 ret = prj_pt_zero(&R_sum); EG(ret, err);
897 ret = prj_pt_init(&P_sum, shortw_curve); EG(ret, err);
898 ret = prj_pt_zero(&P_sum); EG(ret, err);
899 ret = prj_pt_init(&Tmp, shortw_curve); EG(ret, err);
900 ret = nn_init(&e, 0); EG(ret, err);
901 ret = nn_init(&a, 0); EG(ret, err);
902 /* Compute the ChaCha20 seed */
903 ret = _bip0340_compute_batch_csprng_seed(s, s_len, pub_keys, m, m_len, num,
904 p_len, chacha20_seed,
905 sizeof(chacha20_seed)); EG(ret, err);
906 }
907 else{
908 /* Get a pseudo-random scalar a for randomizing the linear combination */
909 ret = _bip0340_compute_batch_csprng_scalars(chacha20_seed, sizeof(chacha20_seed),
910 chacha20_scalar, sizeof(chacha20_scalar),
911 &chacha20_scalar_counter, q,
912 q_bit_len, q_len, &a); EG(ret, err);
913 }
914
915 /***************************************************/
916 /* Extract r and s */
917 ret = fp_init(&rx, pub_key->params->ec_curve.a.ctx); EG(ret, err);
918 ret = fp_import_from_buf(&rx, &sig[0], p_len); EG(ret, err);
919 ret = nn_init_from_buf(&S, &sig[p_len], q_len); EG(ret, err);
920 ret = nn_cmp(&S, q, &cmp); EG(ret, err);
921 MUST_HAVE((cmp < 0), ret, err);
922
923 dbg_nn_print("r", &(rx.fp_val));
924 dbg_nn_print("s", &S);
925
926 /***************************************************/
927 /* Add S to the sum */
928 /* Multiply S by a */
929 if(i != 0){
930 ret = nn_mod_mul(&S, &a, &S, q); EG(ret, err);
931 }
932 ret = nn_mod_add(&S_sum, &S_sum, &S, q); EG(ret, err);
933
934 /***************************************************/
935 R = &Tmp;
936 /* Compute R from rx */
937 ret = fp_copy(&(R->X), &rx); EG(ret, err);
938 ret = aff_pt_y_from_x(&(R->Y), &(R->Z), &rx, shortw_curve); EG(ret, err);
939 /* "Lift" R by choosing the even solution */
940 ret = nn_isodd(&(R->Y.fp_val), &isodd); EG(ret, err);
941 if(isodd){
942 ret = fp_copy(&(R->Y), &(R->Z)); EG(ret, err);
943 }
944 ret = fp_one(&(R->Z)); EG(ret, err);
945 /* Now multiply R by a */
946 if(i != 0){
947 ret = _prj_pt_unprotected_mult(R, &a, R); EG(ret, err);
948 }
949 /* Add to the sum */
950 ret = prj_pt_add(&R_sum, &R_sum, R); EG(ret, err);
951 dbg_ec_point_print("aR", R);
952
953 /***************************************************/
954 /* Compute P and add it to P_sum */
955 Y = &Tmp;
956 /* Copy the public key point to work on the unique
957 * affine representative.
958 */
959 ret = prj_pt_copy(Y, pub_key_y); EG(ret, err);
960 ret = prj_pt_unique(Y, Y); EG(ret, err);
961 /* Do we have to "lift" Y the public key ? */
962 ret = nn_isodd(&(Y->Y.fp_val), &isodd); EG(ret, err);
963 if(isodd){
964 /* If yes, negate the y coordinate */
965 ret = fp_neg(&(Y->Y), &(Y->Y)); EG(ret, err);
966 }
967 dbg_ec_point_print("Y", Y);
968 /* Compute e */
969 ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1,
970 &sig[0], p_len, hm,
971 &h_ctx); EG(ret, err);
972 ret = fp_export_to_buf(&Pubx[0], p_len, &(Y->X)); EG(ret, err);
973 ret = hm->hfunc_update(&h_ctx, &Pubx[0], p_len); EG(ret, err);
974 ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err);
975 ret = hm->hfunc_finalize(&h_ctx, hash); EG(ret, err);
976
977 ret = nn_init_from_buf(&e, hash, hsize); EG(ret, err);
978 ret = nn_mod(&e, &e, q); EG(ret, err);
979
980 dbg_nn_print("e", &e);
981
982 /* Multiply e by 'a' */
983 if(i != 0){
984 ret = nn_mod_mul(&e, &e, &a, q); EG(ret, err);
985 }
986 ret = _prj_pt_unprotected_mult(Y, &e, Y); EG(ret, err);
987 dbg_ec_point_print("eY", Y);
988 /* Add to the sum */
989 ret = prj_pt_add(&P_sum, &P_sum, Y); EG(ret, err);
990 }
991
992 /* Sanity check */
993 MUST_HAVE((q != NULL) && (G != NULL), ret, err);
994
995 /* Compute S_sum * G */
996 ret = nn_mod_neg(&S_sum, &S_sum, q); EG(ret, err); /* -S_sum = q - S_sum*/
997 ret = _prj_pt_unprotected_mult(&Tmp, &S_sum, G); EG(ret, err);
998 /* Add P_sum and R_sum */
999 ret = prj_pt_add(&Tmp, &Tmp, &R_sum); EG(ret, err);
1000 ret = prj_pt_add(&Tmp, &Tmp, &P_sum); EG(ret, err);
1001 /* The result should be point at infinity */
1002 ret = prj_pt_iszero(&Tmp, &iszero); EG(ret, err);
1003 ret = (iszero == 1) ? 0 : -1;
1004
1005 err:
1006 PTR_NULLIFY(q);
1007 PTR_NULLIFY(pub_key);
1008 PTR_NULLIFY(pub_key0);
1009 PTR_NULLIFY(shortw_curve);
1010 PTR_NULLIFY(pub_key_y);
1011 PTR_NULLIFY(G);
1012 PTR_NULLIFY(R);
1013 PTR_NULLIFY(Y);
1014
1015 prj_pt_uninit(&R_sum);
1016 prj_pt_uninit(&P_sum);
1017 prj_pt_uninit(&Tmp);
1018 nn_uninit(&S);
1019 nn_uninit(&S_sum);
1020 nn_uninit(&e);
1021 nn_uninit(&a);
1022 fp_uninit(&rx);
1023
1024 return ret;
1025 }
1026
_bip0340_verify_batch(const u8 ** s,const u8 * s_len,const ec_pub_key ** pub_keys,const u8 ** m,const u32 * m_len,u32 num,ec_alg_type sig_type,hash_alg_type hash_type,const u8 ** adata,const u16 * adata_len,verify_batch_scratch_pad * scratch_pad_area,u32 * scratch_pad_area_len)1027 static int _bip0340_verify_batch(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys,
1028 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type,
1029 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len,
1030 verify_batch_scratch_pad *scratch_pad_area, u32 *scratch_pad_area_len)
1031 {
1032 nn_src_t q = NULL;
1033 prj_pt_src_t G = NULL;
1034 prj_pt_t R = NULL, Y = NULL;
1035 nn S, a;
1036 nn_t e = NULL;
1037 fp rx;
1038 u8 hash[MAX_DIGEST_SIZE];
1039 u8 Pubx[NN_MAX_BYTE_LEN];
1040 const ec_pub_key *pub_key, *pub_key0;
1041 int ret, iszero, isodd, cmp;
1042 prj_pt_src_t pub_key_y;
1043 hash_context h_ctx;
1044 const hash_mapping *hm;
1045 ec_shortw_crv_src_t shortw_curve;
1046 ec_alg_type key_type = UNKNOWN_ALG;
1047 bitcnt_t p_bit_len, q_bit_len = 0;
1048 u8 p_len, q_len;
1049 u16 hsize;
1050 u32 i;
1051 /* NN numbers and points pointers */
1052 verify_batch_scratch_pad *elements = scratch_pad_area;
1053 u64 expected_len;
1054 u8 chacha20_seed[SHA256_DIGEST_SIZE];
1055 u8 chacha20_scalar[BYTECEIL(CURVES_MAX_Q_BIT_LEN)];
1056 u32 chacha20_scalar_counter = 1;
1057
1058 S.magic = a.magic = WORD(0);
1059 rx.magic = WORD(0);
1060
1061 FORCE_USED_VAR(adata_len);
1062 FORCE_USED_VAR(adata);
1063
1064 /* First, some sanity checks */
1065 MUST_HAVE((s != NULL) && (pub_keys != NULL) && (m != NULL), ret, err);
1066
1067 MUST_HAVE((scratch_pad_area_len != NULL), ret, err);
1068 MUST_HAVE(((2 * num) >= num), ret, err);
1069 MUST_HAVE(((2 * num) + 1) >= num, ret, err);
1070
1071 /* Zeroize buffers */
1072 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err);
1073 ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err);
1074 ret = local_memset(chacha20_seed, 0,sizeof(chacha20_seed)); EG(ret, err);
1075 ret = local_memset(chacha20_scalar, 0,sizeof(chacha20_scalar)); EG(ret, err);
1076
1077 /* In oder to apply the algorithm, we must have at least two
1078 * elements to verify. If this is not the case, we fallback to
1079 * the regular "no memory" version.
1080 */
1081 if(num <= 1){
1082 if(scratch_pad_area == NULL){
1083 /* We do not require any memory in this case */
1084 (*scratch_pad_area_len) = 0;
1085 ret = 0;
1086 goto err;
1087 }
1088 else{
1089 ret = _bip0340_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type,
1090 hash_type, adata, adata_len); EG(ret, err);
1091 goto err;
1092 }
1093 }
1094
1095 expected_len = ((2 * num) + 1) * sizeof(verify_batch_scratch_pad);
1096 MUST_HAVE((expected_len < 0xffffffff), ret, err);
1097
1098 if(scratch_pad_area == NULL){
1099 /* Return the needed size: we need to keep track of (2 * num) + 1 NN numbers
1100 * and (2 * num) + 1 projective points, plus (2 * num) + 1 indices
1101 */
1102 (*scratch_pad_area_len) = (u32)expected_len;
1103 ret = 0;
1104 goto err;
1105 }
1106 else{
1107 MUST_HAVE((*scratch_pad_area_len) >= expected_len, ret, err);
1108 }
1109
1110 pub_key0 = pub_keys[0];
1111 MUST_HAVE((pub_key0 != NULL), ret, err);
1112
1113 /* Get our hash mapping */
1114 ret = get_hash_by_type(hash_type, &hm); EG(ret, err);
1115 hsize = hm->digest_size;
1116 MUST_HAVE((hm != NULL), ret, err);
1117
1118 for(i = 0; i < num; i++){
1119 u8 siglen;
1120 const u8 *sig = NULL;
1121
1122 ret = pub_key_check_initialized_and_type(pub_keys[i], BIP0340); EG(ret, err);
1123
1124 /* Make things more readable */
1125 pub_key = pub_keys[i];
1126
1127 /* Sanity check that all our public keys have the same parameters */
1128 MUST_HAVE((pub_key->params) == (pub_key0->params), ret, err);
1129
1130 q = &(pub_key->params->ec_gen_order);
1131 shortw_curve = &(pub_key->params->ec_curve);
1132 pub_key_y = &(pub_key->y);
1133 key_type = pub_key->key_type;
1134 G = &(pub_key->params->ec_gen);
1135 p_bit_len = pub_key->params->ec_fp.p_bitlen;
1136 q_bit_len = pub_key->params->ec_gen_order_bitlen;
1137 p_len = (u8)BYTECEIL(p_bit_len);
1138 q_len = (u8)BYTECEIL(q_bit_len);
1139
1140 /* Check given signature length is the expected one */
1141 siglen = s_len[i];
1142 sig = s[i];
1143 MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err);
1144 MUST_HAVE((siglen == (BIP0340_R_LEN(p_bit_len) + BIP0340_S_LEN(q_bit_len))), ret, err);
1145
1146 /* Check the key type versus the algorithm */
1147 MUST_HAVE((key_type == sig_type), ret, err);
1148
1149 if(i == 0){
1150 /* Initialize our sums to zero/point at infinity */
1151 ret = nn_init(&a, 0); EG(ret, err);
1152 ret = nn_init(&elements[(2 * num)].number, 0); EG(ret, err);
1153 ret = prj_pt_copy(&elements[(2 * num)].point, G); EG(ret, err);
1154 /* Compute the ChaCha20 seed */
1155 ret = _bip0340_compute_batch_csprng_seed(s, s_len, pub_keys, m, m_len, num,
1156 p_len, chacha20_seed,
1157 sizeof(chacha20_seed)); EG(ret, err);
1158 }
1159 else{
1160 /* Get a pseudo-random scalar a for randomizing the linear combination */
1161 ret = _bip0340_compute_batch_csprng_scalars(chacha20_seed, sizeof(chacha20_seed),
1162 chacha20_scalar, sizeof(chacha20_scalar),
1163 &chacha20_scalar_counter, q,
1164 q_bit_len, q_len, &a); EG(ret, err);
1165 }
1166
1167 /***************************************************/
1168 /* Extract r and s */
1169 ret = fp_init(&rx, pub_key->params->ec_curve.a.ctx); EG(ret, err);
1170 ret = fp_import_from_buf(&rx, &sig[0], p_len); EG(ret, err);
1171 ret = nn_init_from_buf(&S, &sig[p_len], q_len); EG(ret, err);
1172 ret = nn_cmp(&S, q, &cmp); EG(ret, err);
1173 MUST_HAVE((cmp < 0), ret, err);
1174
1175 dbg_nn_print("r", &(rx.fp_val));
1176 dbg_nn_print("s", &S);
1177
1178 /***************************************************/
1179 /* Add S to the sum */
1180 /* Multiply S by a */
1181 if(i != 0){
1182 ret = nn_mod_mul(&S, &a, &S, q); EG(ret, err);
1183 }
1184 ret = nn_mod_add(&elements[(2 * num)].number, &elements[(2 * num)].number,
1185 &S, q); EG(ret, err);
1186
1187 /***************************************************/
1188 /* Initialize R */
1189 R = &elements[i].point;
1190 ret = prj_pt_init(R, shortw_curve); EG(ret, err);
1191 /* Compute R from rx */
1192 ret = fp_copy(&(R->X), &rx); EG(ret, err);
1193 ret = aff_pt_y_from_x(&(R->Y), &(R->Z), &rx, shortw_curve); EG(ret, err);
1194 /* "Lift" R by choosing the even solution */
1195 ret = nn_isodd(&(R->Y.fp_val), &isodd); EG(ret, err);
1196 if(isodd){
1197 ret = fp_copy(&(R->Y), &(R->Z)); EG(ret, err);
1198 }
1199 ret = fp_one(&(R->Z)); EG(ret, err);
1200
1201 if(i != 0){
1202 ret = nn_init(&elements[i].number, 0); EG(ret, err);
1203 ret = nn_copy(&elements[i].number, &a); EG(ret, err);
1204 }
1205 else{
1206 ret = nn_init(&elements[i].number, 0); EG(ret, err);
1207 ret = nn_one(&elements[i].number); EG(ret, err);
1208 }
1209 dbg_ec_point_print("R", R);
1210
1211 /***************************************************/
1212 /* Compute P and add it to P_sum */
1213 Y = &elements[num + i].point;
1214 /* Copy the public key point to work on the unique
1215 * affine representative.
1216 */
1217 ret = prj_pt_copy(Y, pub_key_y); EG(ret, err);
1218 ret = prj_pt_unique(Y, Y); EG(ret, err);
1219 /* Do we have to "lift" Y the public key ? */
1220 ret = nn_isodd(&(Y->Y.fp_val), &isodd); EG(ret, err);
1221 if(isodd){
1222 /* If yes, negate the y coordinate */
1223 ret = fp_neg(&(Y->Y), &(Y->Y)); EG(ret, err);
1224 }
1225 dbg_ec_point_print("Y", Y);
1226 /* Compute e */
1227 /* Store the coefficient */
1228 e = &elements[num + i].number;
1229 ret = nn_init(e, 0); EG(ret, err);
1230 ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1,
1231 &sig[0], p_len, hm,
1232 &h_ctx); EG(ret, err);
1233 ret = fp_export_to_buf(&Pubx[0], p_len, &(Y->X)); EG(ret, err);
1234 ret = hm->hfunc_update(&h_ctx, &Pubx[0], p_len); EG(ret, err);
1235 ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err);
1236 ret = hm->hfunc_finalize(&h_ctx, hash); EG(ret, err);
1237
1238 ret = nn_init_from_buf(e, hash, hsize); EG(ret, err);
1239 ret = nn_mod(e, e, q); EG(ret, err);
1240
1241 dbg_nn_print("e", e);
1242
1243 /* Multiply e by 'a' */
1244 if(i != 0){
1245 ret = nn_mod_mul(e, e, &a, q); EG(ret, err);
1246 }
1247 }
1248
1249 /* Sanity check */
1250 MUST_HAVE((q != NULL) && (G != NULL) && (q_bit_len != 0), ret, err);
1251
1252 /********************************************/
1253 /****** Bos-Coster algorithm ****************/
1254 ret = ec_verify_bos_coster(elements, (2 * num) + 1, q_bit_len);
1255 if(ret){
1256 if(ret == -2){
1257 /* In case of Bos-Coster time out, we fall back to the
1258 * slower regular batch verification.
1259 */
1260 ret = _bip0340_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type,
1261 hash_type, adata, adata_len); EG(ret, err);
1262 }
1263 goto err;
1264 }
1265
1266 /* The first element should contain the sum: it should
1267 * be equal to zero. Reject the signature if this is not
1268 * the case.
1269 */
1270 ret = prj_pt_iszero(&elements[elements[0].index].point, &iszero); EG(ret, err);
1271 ret = iszero ? 0 : -1;
1272
1273 err:
1274 PTR_NULLIFY(q);
1275 PTR_NULLIFY(e);
1276 PTR_NULLIFY(pub_key);
1277 PTR_NULLIFY(pub_key0);
1278 PTR_NULLIFY(shortw_curve);
1279 PTR_NULLIFY(pub_key_y);
1280 PTR_NULLIFY(G);
1281 PTR_NULLIFY(R);
1282 PTR_NULLIFY(Y);
1283
1284 /* Unitialize all our scratch_pad_area */
1285 if((scratch_pad_area != NULL) && (scratch_pad_area_len != NULL)){
1286 IGNORE_RET_VAL(local_memset((u8*)scratch_pad_area, 0, (*scratch_pad_area_len)));
1287 }
1288
1289 nn_uninit(&S);
1290 nn_uninit(&a);
1291 fp_uninit(&rx);
1292
1293 return ret;
1294 }
1295
bip0340_verify_batch(const u8 ** s,const u8 * s_len,const ec_pub_key ** pub_keys,const u8 ** m,const u32 * m_len,u32 num,ec_alg_type sig_type,hash_alg_type hash_type,const u8 ** adata,const u16 * adata_len,verify_batch_scratch_pad * scratch_pad_area,u32 * scratch_pad_area_len)1296 int bip0340_verify_batch(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys,
1297 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type,
1298 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len,
1299 verify_batch_scratch_pad *scratch_pad_area, u32 *scratch_pad_area_len)
1300 {
1301 int ret;
1302
1303 if(scratch_pad_area != NULL){
1304 MUST_HAVE((scratch_pad_area_len != NULL), ret, err);
1305 ret = _bip0340_verify_batch(s, s_len, pub_keys, m, m_len, num, sig_type,
1306 hash_type, adata, adata_len,
1307 scratch_pad_area, scratch_pad_area_len); EG(ret, err);
1308
1309 }
1310 else{
1311 ret = _bip0340_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type,
1312 hash_type, adata, adata_len); EG(ret, err);
1313 }
1314
1315 err:
1316 return ret;
1317 }
1318
1319 #else /* defined(WITH_SIG_BIP0340) */
1320
1321 /*
1322 * Dummy definition to avoid the empty translation unit ISO C warning
1323 */
1324 typedef int dummy;
1325 #endif /* defined(WITH_SIG_BIP0340) */
1326