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 #ifdef WITH_SIG_ECKCDSA
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 #ifdef VERBOSE_INNER_VALUES
26 #define EC_SIG_ALG "ECKCDSA"
27 #endif
28 #include <libecc/utils/dbg_sig.h>
29
30 /*
31 * Initialize public key 'out_pub' from input private key 'in_priv'. The
32 * function returns 0 on success, -1 on error.
33 */
eckcdsa_init_pub_key(ec_pub_key * out_pub,const ec_priv_key * in_priv)34 int eckcdsa_init_pub_key(ec_pub_key *out_pub, const ec_priv_key *in_priv)
35 {
36 prj_pt_src_t G;
37 int ret, cmp;
38 nn xinv;
39 nn_src_t q;
40 xinv.magic = WORD(0);
41
42 MUST_HAVE((out_pub != NULL), ret, err);
43
44 ret = priv_key_check_initialized_and_type(in_priv, ECKCDSA); EG(ret, err);
45
46 /* For readability in the remaining of the function */
47 q = &(in_priv->params->ec_gen_order);
48
49 /* Zero init public key to be generated */
50 ret = local_memset(out_pub, 0, sizeof(ec_pub_key)); EG(ret, err);
51
52 /* Sanity check on key */
53 MUST_HAVE((!nn_cmp(&(in_priv->x), q, &cmp)) && (cmp < 0), ret, err);
54
55 /* Y = (x^-1)G */
56 G = &(in_priv->params->ec_gen);
57 /* NOTE: we use Fermat's little theorem inversion for
58 * constant time here. This is possible since q is prime.
59 */
60 ret = nn_modinv_fermat(&xinv, &(in_priv->x), q); EG(ret, err);
61
62 /* Use blinding when computing point scalar multiplication */
63 ret = prj_pt_mul_blind(&(out_pub->y), &xinv, G); EG(ret, err);
64
65 out_pub->key_type = ECKCDSA;
66 out_pub->params = in_priv->params;
67 out_pub->magic = PUB_KEY_MAGIC;
68
69 err:
70 nn_uninit(&xinv);
71
72 return ret;
73 }
74
75 /*
76 * Helper providing ECKCDSA signature length when exported to a buffer based on
77 * hash algorithm digest and block size, generator point order bit length, and
78 * underlying prime field order bit length. The function returns 0 on success,
79 * -1 on error. On success, signature length is provided via 'siglen' out
80 * parameter.
81 */
eckcdsa_siglen(u16 p_bit_len,u16 q_bit_len,u8 hsize,u8 blocksize,u8 * siglen)82 int eckcdsa_siglen(u16 p_bit_len, u16 q_bit_len, u8 hsize, u8 blocksize,
83 u8 *siglen)
84 {
85 int ret;
86
87 MUST_HAVE((siglen != NULL), ret, err);
88 MUST_HAVE((p_bit_len <= CURVES_MAX_P_BIT_LEN) &&
89 (q_bit_len <= CURVES_MAX_Q_BIT_LEN) &&
90 (hsize <= MAX_DIGEST_SIZE) &&
91 (blocksize <= MAX_BLOCK_SIZE), ret, err);
92
93 (*siglen) = (u8)ECKCDSA_SIGLEN(hsize, q_bit_len);
94 ret = 0;
95
96 err:
97 return ret;
98 }
99
100 /*
101 * ISO 14888-3:2016 has some insane specific case when the digest size
102 * (gamma) is larger than beta, the bit length of q (i.e. hsize >
103 * bitlen(q), i.e. gamma > beta). In that case, both the values of h
104 * (= H(z||m)) and r (= H(FE2OS(W_x))) must be post-processed/mangled
105 * in the following way:
106 *
107 * - h = I2BS(beta', (BS2I(gamma, h))) mod 2^beta'
108 * - r = I2BS(beta', (BS2I(gamma, r))) mod 2^beta'
109 *
110 * where beta' = 8 * ceil(beta / 8)
111 *
112 * There are two things to consider before implementing those steps
113 * using various conversions to/from nn, shifting and masking:
114 *
115 * - the expected post-processing work is simply clearing the first
116 * (gamma - beta') bits at the beginning of h and r to keep only
117 * last beta ones unmodified.
118 * - In the library, we do not work on bitstring but byte strings in
119 * all cases
120 * - In EC-KCDSA sig/verif, the result (h and then r) are then XORed
121 * together and then converted to an integer (the buffer being
122 * considered in big endian order)
123 *
124 * For that reason, this function simply takes a buffer 'buf' of
125 * 'buflen' bytes and shifts it 'shift' bytes to the left, clearing
126 * the trailing 'shift' bytes at the end of the buffer. The function
127 * is expected to be used with 'shift' parameter set to
128 * (gamma - beta') / 8.
129 *
130 * This is better presented on an example:
131 *
132 * shift = (gamma - beta') / 8 = 4
133 * before: buf = { 0xff, 0xff, 0xff, 0x12, 0x34, 0x56, 0x78}
134 * after : buf = { 0x34, 0x56, 0x78, 0x00, 0x00, 0x00, 0x00}
135 */
buf_lshift(u8 * buf,u8 buflen,u8 shift)136 ATTRIBUTE_WARN_UNUSED_RET static int buf_lshift(u8 *buf, u8 buflen, u8 shift)
137 {
138 u8 i;
139 int ret;
140
141 MUST_HAVE((buf != NULL), ret, err);
142
143 if (shift > buflen) {
144 shift = buflen;
145 }
146
147 /* Start by shifting all trailing bytes to the left ... */
148 for (i = shift; i < buflen; i++) {
149 buf[i - shift] = buf[i];
150 }
151
152 /* Let's now zeroize the end of the buffer ... */
153 for (i = 1; i <= shift; i++) {
154 buf[buflen - i] = 0;
155 }
156
157 ret = 0;
158
159 err:
160 return ret;
161 }
162
163 /*
164 * Generic *internal* EC-KCDSA signature functions (init, update and finalize).
165 * Their purpose is to allow passing a specific hash function (along with
166 * its output size) and the random ephemeral key k, so that compliance
167 * tests against test vectors can be made without ugly hack in the code
168 * itself.
169 *
170 * Global EC-KCDSA signature process is as follows (I,U,F provides
171 * information in which function(s) (init(), update() or finalize())
172 * a specific step is performed):
173 *
174 *| IUF - EC-KCDSA signature
175 *|
176 *| IUF 1. Compute h = H(z||m)
177 *| F 2. If |H| > bitlen(q), set h to beta' rightmost bits of
178 *| bitstring h (w/ beta' = 8 * ceil(bitlen(q) / 8)), i.e.
179 *| set h to I2BS(beta', BS2I(|H|, h) mod 2^beta')
180 *| F 3. Get a random value k in ]0,q[
181 *| F 4. Compute W = (W_x,W_y) = kG
182 *| F 5. Compute r = H(FE2OS(W_x)).
183 *| F 6. If |H| > bitlen(q), set r to beta' rightmost bits of
184 *| bitstring r (w/ beta' = 8 * ceil(bitlen(q) / 8)), i.e.
185 *| set r to I2BS(beta', BS2I(|H|, r) mod 2^beta')
186 *| F 7. Compute e = OS2I(r XOR h) mod q
187 *| F 8. Compute s = x(k - e) mod q
188 *| F 9. if s == 0, restart at step 3.
189 *| F 10. return (r,s)
190 *
191 */
192
193 #define ECKCDSA_SIGN_MAGIC ((word_t)(0x45503fcf5114bf1eULL))
194 #define ECKCDSA_SIGN_CHECK_INITIALIZED(A, ret, err) \
195 MUST_HAVE((((void *)(A)) != NULL) && \
196 ((A)->magic == ECKCDSA_SIGN_MAGIC), ret, err)
197
198 /*
199 * ECKCDSA signature initialization function. Returns 0 on success, -1 on
200 * error.
201 */
_eckcdsa_sign_init(struct ec_sign_context * ctx)202 int _eckcdsa_sign_init(struct ec_sign_context *ctx)
203 {
204 u8 tmp_buf[LOCAL_MAX(2 * BYTECEIL(CURVES_MAX_P_BIT_LEN), MAX_BLOCK_SIZE)];
205 const ec_pub_key *pub_key;
206 aff_pt y_aff;
207 u8 p_len;
208 u16 z_len;
209 int ret;
210 y_aff.magic = WORD(0);
211
212 /* First, verify context has been initialized */
213 ret = sig_sign_check_initialized(ctx); EG(ret, err);
214
215 /* Additional sanity checks on input params from context */
216 ret = key_pair_check_initialized_and_type(ctx->key_pair, ECKCDSA); EG(ret, err);
217 MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) &&
218 (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err);
219
220 /* Make things more readable */
221 pub_key = &(ctx->key_pair->pub_key);
222 p_len = (u8)BYTECEIL(pub_key->params->ec_fp.p_bitlen);
223 z_len = ctx->h->block_size;
224
225 /*
226 * 1. Compute h = H(z||m)
227 *
228 * We first need to compute z, the certificate data that will be
229 * prepended to the message m prior to hashing. In ISO-14888-3:2016,
230 * z is basically the concatenation of Yx and Yy (the affine coordinates
231 * of the public key Y) up to the block size of the hash function.
232 * If the concatenation of those coordinates is smaller than blocksize,
233 * 0 are appended.
234 *
235 * So, we convert the public key point to its affine representation and
236 * concatenate the two coordinates in a temporary (zeroized) buffer, of
237 * which the first z_len (i.e. blocksize) bytes are exported to z.
238 *
239 * Message m will be handled during following update() calls.
240 */
241 ret = prj_pt_to_aff(&y_aff, &(pub_key->y)); EG(ret, err);
242 ret = local_memset(tmp_buf, 0, sizeof(tmp_buf)); EG(ret, err);
243 ret = fp_export_to_buf(tmp_buf, p_len, &(y_aff.x)); EG(ret, err);
244 ret = fp_export_to_buf(tmp_buf + p_len, p_len, &(y_aff.y)); EG(ret, err);
245
246 dbg_pub_key_print("Y", pub_key);
247
248 /* Since we call a callback, sanity check our mapping */
249 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
250 ret = ctx->h->hfunc_init(&(ctx->sign_data.eckcdsa.h_ctx)); EG(ret, err);
251 ret = ctx->h->hfunc_update(&(ctx->sign_data.eckcdsa.h_ctx), tmp_buf, z_len); EG(ret, err);
252 ret = local_memset(tmp_buf, 0, sizeof(tmp_buf)); EG(ret, err);
253
254 /* Initialize data part of the context */
255 ctx->sign_data.eckcdsa.magic = ECKCDSA_SIGN_MAGIC;
256
257 err:
258 aff_pt_uninit(&y_aff);
259
260 VAR_ZEROIFY(p_len);
261 VAR_ZEROIFY(z_len);
262 PTR_NULLIFY(pub_key);
263
264 return ret;
265 }
266
267 /* ECKCDSA signature update function. Returns 0 on success, -1 on error. */
_eckcdsa_sign_update(struct ec_sign_context * ctx,const u8 * chunk,u32 chunklen)268 int _eckcdsa_sign_update(struct ec_sign_context *ctx,
269 const u8 *chunk, u32 chunklen)
270 {
271 int ret;
272
273 /*
274 * First, verify context has been initialized and private
275 * part too. This guarantees the context is an EC-KCDSA
276 * signature one and we do not update() or finalize()
277 * before init().
278 */
279 ret = sig_sign_check_initialized(ctx); EG(ret, err);
280 ECKCDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.eckcdsa), ret, err);
281
282 /* 1. Compute h = H(z||m) */
283 /* Since we call a callback, sanity check our mapping */
284 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
285 ret = ctx->h->hfunc_update(&(ctx->sign_data.eckcdsa.h_ctx), chunk, chunklen);
286
287 err:
288 return ret;
289 }
290
291 /*
292 * ECKCDSA signature finalization function. Returns 0 on success, -1 on
293 * error.
294 */
_eckcdsa_sign_finalize(struct ec_sign_context * ctx,u8 * sig,u8 siglen)295 int _eckcdsa_sign_finalize(struct ec_sign_context *ctx, u8 *sig, u8 siglen)
296 {
297 prj_pt_src_t G;
298 nn_src_t q, x;
299 prj_pt kG;
300 unsigned int i;
301 nn e, tmp, s, k;
302 u8 hzm[MAX_DIGEST_SIZE];
303 u8 r[MAX_DIGEST_SIZE];
304 u8 tmp_buf[BYTECEIL(CURVES_MAX_P_BIT_LEN)];
305 hash_context r_ctx;
306 const ec_priv_key *priv_key;
307 u8 p_len, r_len, s_len, hsize, shift;
308 bitcnt_t q_bit_len;
309 int ret, iszero, cmp;
310 #ifdef USE_SIG_BLINDING
311 /* b is the blinding mask */
312 nn b, binv;
313 b.magic = binv.magic = WORD(0);
314 #endif /* USE_SIG_BLINDING */
315
316 kG.magic = WORD(0);
317 e.magic = tmp.magic = s.magic = k.magic = WORD(0);
318
319 /*
320 * First, verify context has been initialized and private
321 * part too. This guarantees the context is an EC-KCDSA
322 * signature one and we do not finalize() before init().
323 */
324 ret = sig_sign_check_initialized(ctx); EG(ret, err);
325 ECKCDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.eckcdsa), ret, err);
326 MUST_HAVE((sig != NULL), ret, err);
327
328 /* Zero init points */
329 ret = local_memset(&kG, 0, sizeof(prj_pt)); EG(ret, err);
330
331 /* Make things more readable */
332 priv_key = &(ctx->key_pair->priv_key);
333 G = &(priv_key->params->ec_gen);
334 q = &(priv_key->params->ec_gen_order);
335 hsize = ctx->h->digest_size;
336 p_len = (u8)BYTECEIL(priv_key->params->ec_fp.p_bitlen);
337 q_bit_len = priv_key->params->ec_gen_order_bitlen;
338 r_len = (u8)ECKCDSA_R_LEN(hsize, q_bit_len);
339 s_len = (u8)ECKCDSA_S_LEN(q_bit_len);
340 x = &(priv_key->x);
341
342 /* Sanity check */
343 ret = nn_cmp(x, q, &cmp); EG(ret, err);
344 /* This should not happen and means that our
345 * private key is not compliant!
346 */
347 MUST_HAVE((cmp < 0), ret, err);
348
349 MUST_HAVE((siglen == ECKCDSA_SIGLEN(hsize, q_bit_len)), ret, err);
350
351 dbg_nn_print("p", &(priv_key->params->ec_fp.p));
352 dbg_nn_print("q", q);
353 dbg_priv_key_print("x", priv_key);
354 dbg_ec_point_print("G", G);
355
356 /* 1. Compute h = H(z||m) */
357 /* Since we call a callback, sanity check our mapping */
358 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
359 ret = ctx->h->hfunc_finalize(&(ctx->sign_data.eckcdsa.h_ctx), hzm); EG(ret, err);
360 dbg_buf_print("h = H(z||m) pre-mask", hzm, hsize);
361
362 /*
363 * 2. If |H| > bitlen(q), set h to beta' rightmost bits of
364 * bitstring h (w/ beta' = 8 * ceil(bitlen(q) / 8)), i.e.
365 * set h to I2BS(beta', BS2I(|H|, h) mod 2^beta')
366 */
367 shift = (u8)((hsize > r_len) ? (hsize - r_len) : 0);
368 MUST_HAVE((hsize <= sizeof(hzm)), ret, err);
369
370 ret = buf_lshift(hzm, hsize, shift); EG(ret, err);
371 dbg_buf_print("h = H(z||m) post-mask", hzm, r_len);
372
373 restart:
374 /* 3. Get a random value k in ]0,q[ */
375 #ifdef NO_KNOWN_VECTORS
376 /* NOTE: when we do not need self tests for known vectors,
377 * we can be strict about random function handler!
378 * This allows us to avoid the corruption of such a pointer.
379 */
380 /* Sanity check on the handler before calling it */
381 MUST_HAVE((ctx->rand == nn_get_random_mod), ret, err);
382 #endif
383 MUST_HAVE((ctx->rand != NULL), ret, err);
384 ret = ctx->rand(&k, q); EG(ret, err);
385 dbg_nn_print("k", &k);
386
387 #ifdef USE_SIG_BLINDING
388 /* Note: if we use blinding, k and e are multiplied by
389 * a random value b in ]0,q[ */
390 ret = nn_get_random_mod(&b, q); EG(ret, err);
391 dbg_nn_print("b", &b);
392 #endif /* USE_SIG_BLINDING */
393
394 /* 4. Compute W = (W_x,W_y) = kG */
395 #ifdef USE_SIG_BLINDING
396 /* We use blinding for the scalar multiplication */
397 ret = prj_pt_mul_blind(&kG, &k, G); EG(ret, err);
398 #else
399 ret = prj_pt_mul(&kG, &k, G); EG(ret, err);
400 #endif /* USE_SIG_BLINDING */
401 ret = prj_pt_unique(&kG, &kG); EG(ret, err);
402 dbg_nn_print("W_x", &(kG.X.fp_val));
403 dbg_nn_print("W_y", &(kG.Y.fp_val));
404
405 /* 5 Compute r = h(FE2OS(W_x)). */
406 ret = local_memset(tmp_buf, 0, sizeof(tmp_buf)); EG(ret, err);
407 ret = fp_export_to_buf(tmp_buf, p_len, &(kG.X)); EG(ret, err);
408 /* Since we call a callback, sanity check our mapping */
409 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
410 ret = ctx->h->hfunc_init(&r_ctx); EG(ret, err);
411 ret = ctx->h->hfunc_update(&r_ctx, tmp_buf, p_len); EG(ret, err);
412 ret = ctx->h->hfunc_finalize(&r_ctx, r); EG(ret, err);
413 ret = local_memset(tmp_buf, 0, p_len); EG(ret, err);
414 ret = local_memset(&r_ctx, 0, sizeof(hash_context)); EG(ret, err);
415
416 /*
417 * 6. If |H| > bitlen(q), set r to beta' rightmost bits of
418 * bitstring r (w/ beta' = 8 * ceil(bitlen(q) / 8)), i.e.
419 * set r to I2BS(beta', BS2I(|H|, r) mod 2^beta')
420 */
421 dbg_buf_print("r pre-mask", r, hsize);
422 MUST_HAVE((hsize <= sizeof(r)), ret, err);
423
424 ret = buf_lshift(r, hsize, shift); EG(ret, err);
425 dbg_buf_print("r post-mask", r, r_len);
426
427 /* 7. Compute e = OS2I(r XOR h) mod q */
428 for (i = 0; i < r_len; i++) {
429 hzm[i] ^= r[i];
430 }
431 ret = nn_init_from_buf(&tmp, hzm, r_len); EG(ret, err);
432 ret = local_memset(hzm, 0, r_len); EG(ret, err);
433 ret = nn_mod(&e, &tmp, q); EG(ret, err);
434 dbg_nn_print("e", &e);
435
436 #ifdef USE_SIG_BLINDING
437 /* In case of blinding, we compute (k*b - e*b) * x * b^-1 */
438 ret = nn_mod_mul(&k, &k, &b, q); EG(ret, err);
439 ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err);
440 /* NOTE: we use Fermat's little theorem inversion for
441 * constant time here. This is possible since q is prime.
442 */
443 ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err);
444 #endif /* USE_SIG_BLINDING */
445 /*
446 * 8. Compute s = x(k - e) mod q
447 *
448 * This is equivalent to computing s = x(k + (q - e)) mod q.
449 * This second version avoids checking if k < e before the
450 * subtraction, because e has already been reduced mod q
451 */
452 ret = nn_mod_neg(&tmp, &e, q); EG(ret, err);
453 ret = nn_mod_add(&tmp, &k, &tmp, q); EG(ret, err);
454 ret = nn_mod_mul(&s, x, &tmp, q); EG(ret, err);
455 #ifdef USE_SIG_BLINDING
456 /* Unblind s with b^-1 */
457 ret = nn_mod_mul(&s, &s, &binv, q); EG(ret, err);
458 #endif /* USE_SIG_BLINDING */
459
460 /* 9. if s == 0, restart at step 3. */
461 ret = nn_iszero(&s, &iszero); EG(ret, err);
462 if (iszero) {
463 goto restart;
464 }
465
466 dbg_nn_print("s", &s);
467
468 /* 10. return (r,s) */
469 ret = local_memcpy(sig, r, r_len); EG(ret, err);
470 ret = local_memset(r, 0, r_len); EG(ret, err);
471 ret = nn_export_to_buf(sig + r_len, s_len, &s);
472
473 err:
474 prj_pt_uninit(&kG);
475 nn_uninit(&e);
476 nn_uninit(&tmp);
477 nn_uninit(&s);
478 nn_uninit(&k);
479 #ifdef USE_SIG_BLINDING
480 nn_uninit(&b);
481 nn_uninit(&binv);
482 #endif /* USE_SIG_BLINDING */
483
484 /*
485 * We can now clear data part of the context. This will clear
486 * magic and avoid further reuse of the whole context.
487 */
488 if(ctx != NULL){
489 IGNORE_RET_VAL(local_memset(&(ctx->sign_data.eckcdsa), 0, sizeof(eckcdsa_sign_data)));
490 }
491
492 PTR_NULLIFY(G);
493 PTR_NULLIFY(q);
494 PTR_NULLIFY(x);
495 VAR_ZEROIFY(i);
496 PTR_NULLIFY(priv_key);
497 VAR_ZEROIFY(p_len);
498 VAR_ZEROIFY(r_len);
499 VAR_ZEROIFY(s_len);
500 VAR_ZEROIFY(q_bit_len);
501 VAR_ZEROIFY(hsize);
502
503 return ret;
504 }
505
506 /*
507 * Generic *internal* EC-KCDSA verification functions (init, update and
508 * finalize). Their purpose is to allow passing a specific hash function
509 * (along with its output size) and the random ephemeral key k, so that
510 * compliance tests against test vectors can be made without ugly hack
511 * in the code itself.
512 *
513 * Global EC-CKDSA verification process is as follows (I,U,F provides
514 * information in which function(s) (init(), update() or finalize())
515 * a specific step is performed):
516 *
517 *| IUF - EC-KCDSA verification
518 *|
519 *| I 1. Check the length of r:
520 *| - if |H| > bitlen(q), r must be of length
521 *| beta' = 8 * ceil(bitlen(q) / 8)
522 *| - if |H| <= bitlen(q), r must be of length hsize
523 *| I 2. Check that s is in ]0,q[
524 *| IUF 3. Compute h = H(z||m)
525 *| F 4. If |H| > bitlen(q), set h to beta' rightmost bits of
526 *| bitstring h (w/ beta' = 8 * ceil(bitlen(q) / 8)), i.e.
527 *| set h to I2BS(beta', BS2I(|H|, h) mod 2^beta')
528 *| F 5. Compute e = OS2I(r XOR h) mod q
529 *| F 6. Compute W' = sY + eG, where Y is the public key
530 *| F 7. Compute r' = h(W'x)
531 *| F 8. If |H| > bitlen(q), set r' to beta' rightmost bits of
532 *| bitstring r' (w/ beta' = 8 * ceil(bitlen(q) / 8)), i.e.
533 *| set r' to I2BS(beta', BS2I(|H|, r') mod 2^beta')
534 *| F 9. Check if r == r'
535 *
536 */
537
538 #define ECKCDSA_VERIFY_MAGIC ((word_t)(0xa836a75de66643aaULL))
539 #define ECKCDSA_VERIFY_CHECK_INITIALIZED(A, ret, err) \
540 MUST_HAVE((((void *)(A)) != NULL) && \
541 ((A)->magic == ECKCDSA_VERIFY_MAGIC), ret, err)
542
543 /*
544 * ECKCDSA verification finalization function. Returns 0 on success, -1 on error.
545 */
_eckcdsa_verify_init(struct ec_verify_context * ctx,const u8 * sig,u8 siglen)546 int _eckcdsa_verify_init(struct ec_verify_context *ctx,
547 const u8 *sig, u8 siglen)
548 {
549 u8 tmp_buf[LOCAL_MAX(2 * BYTECEIL(CURVES_MAX_P_BIT_LEN), MAX_BLOCK_SIZE)];
550 u8 p_len, r_len, s_len, z_len;
551 bitcnt_t q_bit_len;
552 const ec_pub_key *pub_key;
553 aff_pt y_aff;
554 nn_src_t q;
555 u8 hsize;
556 int ret, iszero, cmp;
557 nn s;
558 y_aff.magic = s.magic = WORD(0);
559
560 /* First, verify context has been initialized */
561 ret = sig_verify_check_initialized(ctx); EG(ret, err);
562 MUST_HAVE((sig != NULL), ret, err);
563
564 /* Do some sanity checks on input params */
565 ret = pub_key_check_initialized_and_type(ctx->pub_key, ECKCDSA); EG(ret, err);
566 MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) &&
567 (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err);
568 MUST_HAVE((sig != NULL), ret, err);
569
570 /* Make things more readable */
571 pub_key = ctx->pub_key;
572 p_len = (u8)BYTECEIL(pub_key->params->ec_fp.p_bitlen);
573 q_bit_len = pub_key->params->ec_gen_order_bitlen;
574 q = &(pub_key->params->ec_gen_order);
575 hsize = ctx->h->digest_size;
576 r_len = (u8)ECKCDSA_R_LEN(hsize, q_bit_len);
577 s_len = (u8)ECKCDSA_S_LEN(q_bit_len);
578 z_len = ctx->h->block_size;
579
580 /*
581 * 1. Check the length of r:
582 * - if |H| > bitlen(q), r must be of length
583 * beta' = 8 * ceil(bitlen(q) / 8)
584 * - if |H| <= bitlen(q), r must be of length hsize
585 *
586 * As we expect the signature as the concatenation of r and s, the check
587 * is done by verifying the length of the signature is the expected one.
588 */
589 MUST_HAVE((siglen == ECKCDSA_SIGLEN(hsize, q_bit_len)), ret, err);
590
591 /* 2. Check that s is in ]0,q[ */
592 ret = nn_init_from_buf(&s, sig + r_len, s_len); EG(ret, err);
593 ret = nn_iszero(&s, &iszero); EG(ret, err);
594 ret = nn_cmp(&s, q, &cmp); EG(ret, err);
595 MUST_HAVE((!iszero) && (cmp < 0), ret, err);
596 dbg_nn_print("s", &s);
597
598 /*
599 * 3. Compute h = H(z||m)
600 *
601 * We first need to compute z, the certificate data that will be
602 * prepended to the message m prior to hashing. In ISO-14888-3:2016,
603 * z is basically the concatenation of Yx and Yy (the affine coordinates
604 * of the public key Y) up to the block size of the hash function.
605 * If the concatenation of those coordinates is smaller than blocksize,
606 * 0 are appended.
607 *
608 * So, we convert the public key point to its affine representation and
609 * concatenate the two coordinates in a temporary (zeroized) buffer, of
610 * which the first z_len (i.e. blocksize) bytes are exported to z.
611 *
612 * Message m will be handled during following update() calls.
613 */
614 ret = prj_pt_to_aff(&y_aff, &(pub_key->y)); EG(ret, err);
615 ret = local_memset(tmp_buf, 0, sizeof(tmp_buf)); EG(ret, err);
616 ret = fp_export_to_buf(tmp_buf, p_len, &(y_aff.x)); EG(ret, err);
617 ret = fp_export_to_buf(tmp_buf + p_len, p_len, &(y_aff.y)); EG(ret, err);
618
619 dbg_pub_key_print("Y", pub_key);
620
621 /* Since we call a callback, sanity check our mapping */
622 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
623 ret = ctx->h->hfunc_init(&(ctx->verify_data.eckcdsa.h_ctx)); EG(ret, err);
624 ret = ctx->h->hfunc_update(&(ctx->verify_data.eckcdsa.h_ctx), tmp_buf,
625 z_len); EG(ret, err);
626 ret = local_memset(tmp_buf, 0, sizeof(tmp_buf)); EG(ret, err);
627
628 /*
629 * Initialize the verify context by storing r and s as imported
630 * from the signature
631 */
632 ret = local_memcpy(ctx->verify_data.eckcdsa.r, sig, r_len); EG(ret, err);
633 ret = nn_copy(&(ctx->verify_data.eckcdsa.s), &s); EG(ret, err);
634
635 ctx->verify_data.eckcdsa.magic = ECKCDSA_VERIFY_MAGIC;
636
637 err:
638 aff_pt_uninit(&y_aff);
639 nn_uninit(&s);
640
641 if (ret && (ctx != NULL)) {
642 /*
643 * Signature is invalid. Clear data part of the context.
644 * This will clear magic and avoid further reuse of the
645 * whole context.
646 */
647 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.eckcdsa), 0,
648 sizeof(eckcdsa_verify_data)));
649 }
650
651 /* Let's also clear what remains on the stack */
652 PTR_NULLIFY(q);
653 PTR_NULLIFY(pub_key);
654 VAR_ZEROIFY(p_len);
655 VAR_ZEROIFY(r_len);
656 VAR_ZEROIFY(s_len);
657 VAR_ZEROIFY(z_len);
658 VAR_ZEROIFY(q_bit_len);
659 VAR_ZEROIFY(hsize);
660
661 return ret;
662 }
663
664 /* ECKCDSA verification update function. Returns 0 on success, -1 on error. */
_eckcdsa_verify_update(struct ec_verify_context * ctx,const u8 * chunk,u32 chunklen)665 int _eckcdsa_verify_update(struct ec_verify_context *ctx,
666 const u8 *chunk, u32 chunklen)
667 {
668 int ret;
669
670 /*
671 * First, verify context has been initialized and public
672 * part too. This guarantees the context is an EC-KCDSA
673 * verification one and we do not update() or finalize()
674 * before init().
675 */
676 ret = sig_verify_check_initialized(ctx); EG(ret, err);
677 ECKCDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.eckcdsa), ret, err);
678
679 /* 3. Compute h = H(z||m) */
680 /* Since we call a callback, sanity check our mapping */
681 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
682 ret = ctx->h->hfunc_update(&(ctx->verify_data.eckcdsa.h_ctx),
683 chunk, chunklen);
684
685 err:
686 return ret;
687 }
688
689 /*
690 * ECKCDSA verification finalization function. Returns 0 on success, -1 on error.
691 */
_eckcdsa_verify_finalize(struct ec_verify_context * ctx)692 int _eckcdsa_verify_finalize(struct ec_verify_context *ctx)
693 {
694 u8 tmp_buf[BYTECEIL(CURVES_MAX_P_BIT_LEN)];
695 bitcnt_t q_bit_len, p_bit_len;
696 u8 p_len, r_len;
697 prj_pt sY, eG;
698 prj_pt_t Wprime;
699 prj_pt_src_t G, Y;
700 u8 r_prime[MAX_DIGEST_SIZE];
701 const ec_pub_key *pub_key;
702 hash_context r_prime_ctx;
703 u8 hzm[MAX_DIGEST_SIZE];
704 unsigned int i;
705 nn_src_t q;
706 nn e, tmp;
707 u8 hsize, shift;
708 int ret, check;
709 u8 *r;
710 nn *s;
711
712 sY.magic = eG.magic = WORD(0);
713 e.magic = tmp.magic = WORD(0);
714
715 /* NOTE: we reuse eG for Wprime to optimize local variables */
716 Wprime = &eG;
717
718 /*
719 * First, verify context has been initialized and public
720 * part too. This guarantees the context is an EC-KCDSA
721 * verification one and we do not finalize() before init().
722 */
723 ret = sig_verify_check_initialized(ctx); EG(ret, err);
724 ECKCDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.eckcdsa), ret, err);
725
726 /* Zero init points */
727 ret = local_memset(&sY, 0, sizeof(prj_pt)); EG(ret, err);
728 ret = local_memset(&eG, 0, sizeof(prj_pt)); EG(ret, err);
729
730 /* Make things more readable */
731 pub_key = ctx->pub_key;
732 G = &(pub_key->params->ec_gen);
733 Y = &(pub_key->y);
734 q = &(pub_key->params->ec_gen_order);
735 p_bit_len = pub_key->params->ec_fp.p_bitlen;
736 q_bit_len = pub_key->params->ec_gen_order_bitlen;
737 p_len = (u8)BYTECEIL(p_bit_len);
738 hsize = ctx->h->digest_size;
739 r_len = (u8)ECKCDSA_R_LEN(hsize, q_bit_len);
740 r = ctx->verify_data.eckcdsa.r;
741 s = &(ctx->verify_data.eckcdsa.s);
742
743 /* 3. Compute h = H(z||m) */
744 /* Since we call a callback, sanity check our mapping */
745 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
746 ret = ctx->h->hfunc_finalize(&(ctx->verify_data.eckcdsa.h_ctx), hzm); EG(ret, err);
747 dbg_buf_print("h = H(z||m) pre-mask", hzm, hsize);
748
749 /*
750 * 4. If |H| > bitlen(q), set h to beta' rightmost bits of
751 * bitstring h (w/ beta' = 8 * ceil(bitlen(q) / 8)), i.e.
752 * set h to I2BS(beta', BS2I(|H|, h) mod 2^beta')
753 */
754 shift = (u8)((hsize > r_len) ? (hsize - r_len) : 0);
755 MUST_HAVE(hsize <= sizeof(hzm), ret, err);
756 ret = buf_lshift(hzm, hsize, shift); EG(ret, err);
757 dbg_buf_print("h = H(z||m) post-mask", hzm, r_len);
758
759 /* 5. Compute e = OS2I(r XOR h) mod q */
760 for (i = 0; i < r_len; i++) {
761 hzm[i] ^= r[i];
762 }
763 ret = nn_init_from_buf(&tmp, hzm, r_len); EG(ret, err);
764 ret = local_memset(hzm, 0, hsize); EG(ret, err);
765 ret = nn_mod(&e, &tmp, q); EG(ret, err);
766
767 dbg_nn_print("e", &e);
768
769 /* 6. Compute W' = sY + eG, where Y is the public key */
770 ret = prj_pt_mul(&sY, s, Y); EG(ret, err);
771 ret = prj_pt_mul(&eG, &e, G); EG(ret, err);
772 ret = prj_pt_add(Wprime, &sY, &eG); EG(ret, err);
773 ret = prj_pt_unique(Wprime, Wprime); EG(ret, err);
774 dbg_nn_print("W'_x", &(Wprime->X.fp_val));
775 dbg_nn_print("W'_y", &(Wprime->Y.fp_val));
776
777 /* 7. Compute r' = h(W'x) */
778 ret = local_memset(tmp_buf, 0, sizeof(tmp_buf)); EG(ret, err);
779 ret = fp_export_to_buf(tmp_buf, p_len, &(Wprime->X)); EG(ret, err);
780 /* Since we call a callback, sanity check our mapping */
781 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
782 ret = ctx->h->hfunc_init(&r_prime_ctx); EG(ret, err);
783 ret = ctx->h->hfunc_update(&r_prime_ctx, tmp_buf, p_len); EG(ret, err);
784 ret = ctx->h->hfunc_finalize(&r_prime_ctx, r_prime); EG(ret, err);
785 ret = local_memset(tmp_buf, 0, p_len); EG(ret, err);
786 ret = local_memset(&r_prime_ctx, 0, sizeof(hash_context)); EG(ret, err);
787
788 /*
789 * 8. If |H| > bitlen(q), set r' to beta' rightmost bits of
790 * bitstring r' (w/ beta' = 8 * ceil(bitlen(q) / 8)), i.e.
791 * set r' to I2BS(beta', BS2I(|H|, r') mod 2^beta')
792 */
793 dbg_buf_print("r' pre-mask", r_prime, hsize);
794 ret = buf_lshift(r_prime, hsize, shift); EG(ret, err);
795 dbg_buf_print("r' post-mask", r_prime, r_len);
796 dbg_buf_print("r", r, r_len);
797
798 /* 9. Check if r == r' */
799 ret = are_equal(r, r_prime, r_len, &check); EG(ret, err);
800 ret = check ? 0 : -1;
801
802 err:
803 prj_pt_uninit(&sY);
804 prj_pt_uninit(&eG);
805 nn_uninit(&e);
806 nn_uninit(&tmp);
807
808 /*
809 * We can now clear data part of the context. This will clear
810 * magic and avoid further reuse of the whole context.
811 */
812 if(ctx != NULL){
813 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.eckcdsa), 0,
814 sizeof(eckcdsa_verify_data)));
815 }
816
817 /* Let's also clear what remains on the stack */
818 VAR_ZEROIFY(i);
819 PTR_NULLIFY(Wprime);
820 PTR_NULLIFY(G);
821 PTR_NULLIFY(Y);
822 PTR_NULLIFY(q);
823 VAR_ZEROIFY(p_len);
824 VAR_ZEROIFY(r_len);
825 VAR_ZEROIFY(q_bit_len);
826 VAR_ZEROIFY(p_bit_len);
827 PTR_NULLIFY(pub_key);
828 VAR_ZEROIFY(hsize);
829 PTR_NULLIFY(r);
830 PTR_NULLIFY(s);
831
832 return ret;
833 }
834
835 #else /* WITH_SIG_ECKCDSA */
836
837 /*
838 * Dummy definition to avoid the empty translation unit ISO C warning
839 */
840 typedef int dummy;
841 #endif /* WITH_SIG_ECKCDSA */
842