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(USE_CRYPTOFUZZ)
18
19 #include <libecc/nn/nn_rand.h>
20 #include <libecc/nn/nn_mul.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 /* NOTE: the following versions of ECDSA are "raw" with
32 * no hash functions and nonce override. They are DANGEROUS and
33 * should NOT be used in production mode! They are however useful
34 * for corner cases tests and fuzzing.
35 */
36
37 #define ECDSA_SIGN_MAGIC ((word_t)(0x80299a2bf630945bULL))
38 #define ECDSA_SIGN_CHECK_INITIALIZED(A, ret, err) \
39 MUST_HAVE((((void *)(A)) != NULL) && ((A)->magic == ECDSA_SIGN_MAGIC), ret, err)
40
ecdsa_sign_raw(struct ec_sign_context * ctx,const u8 * input,u8 inputlen,u8 * sig,u8 siglen,const u8 * nonce,u8 noncelen)41 int ecdsa_sign_raw(struct ec_sign_context *ctx, const u8 *input, u8 inputlen, u8 *sig, u8 siglen, const u8 *nonce, u8 noncelen)
42 {
43 const ec_priv_key *priv_key;
44 prj_pt_src_t G;
45 /* NOTE: hash here is not really a hash ... */
46 u8 hash[LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8))];
47 bitcnt_t rshift, q_bit_len;
48 prj_pt kG;
49 nn_src_t q, x;
50 u8 hsize, q_len;
51 int ret, iszero, cmp;
52 nn k, r, e, tmp, s, kinv;
53 #ifdef USE_SIG_BLINDING
54 /* b is the blinding mask */
55 nn b;
56 b.magic = WORD(0);
57 #endif
58 k.magic = r.magic = e.magic = WORD(0);
59 tmp.magic = s.magic = kinv.magic = WORD(0);
60 kG.magic = WORD(0);
61
62 /*
63 * First, verify context has been initialized and private
64 * part too. This guarantees the context is an ECDSA
65 * signature one and we do not finalize() before init().
66 */
67 ret = sig_sign_check_initialized(ctx); EG(ret, err);
68 ECDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecdsa), ret, err);
69 MUST_HAVE((input != NULL) && (sig != NULL), ret, err);
70
71 /* Zero init out poiny */
72 ret = local_memset(&kG, 0, sizeof(prj_pt)); EG(ret, err);
73
74 /* Make things more readable */
75 priv_key = &(ctx->key_pair->priv_key);
76 q = &(priv_key->params->ec_gen_order);
77 q_bit_len = priv_key->params->ec_gen_order_bitlen;
78 G = &(priv_key->params->ec_gen);
79 q_len = (u8)BYTECEIL(q_bit_len);
80 x = &(priv_key->x);
81 hsize = inputlen;
82
83 dbg_nn_print("p", &(priv_key->params->ec_fp.p));
84 dbg_nn_print("q", &(priv_key->params->ec_gen_order));
85 dbg_priv_key_print("x", priv_key);
86 dbg_ec_point_print("G", &(priv_key->params->ec_gen));
87 dbg_pub_key_print("Y", &(ctx->key_pair->pub_key));
88
89 /* Check given signature buffer length has the expected size */
90 MUST_HAVE((siglen == ECDSA_SIGLEN(q_bit_len)), ret, err);
91
92 /* 1. Compute h = H(m) */
93 /* NOTE: here we have raw ECDSA, this is the raw input */
94 /* NOTE: the MUST_HAVE is protected by a preprocessing check
95 * to avoid -Werror=type-limits errors:
96 * "error: comparison is always true due to limited range of data type"
97 */
98 #if LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8)) < 255
99 MUST_HAVE(((u32)inputlen <= sizeof(hash)), ret, err);
100 #endif
101 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err);
102 ret = local_memcpy(hash, input, hsize); EG(ret, err);
103
104 dbg_buf_print("h", hash, hsize);
105
106 /*
107 * 2. If |h| > bitlen(q), set h to bitlen(q)
108 * leftmost bits of h.
109 *
110 * Note that it's easier to check if the truncation has
111 * to be done here but only implement it using a logical
112 * shift at the beginning of step 3. below once the hash
113 * has been converted to an integer.
114 */
115 rshift = 0;
116 if ((hsize * 8) > q_bit_len) {
117 rshift = (bitcnt_t)((hsize * 8) - q_bit_len);
118 }
119
120 /*
121 * 3. Compute e = OS2I(h) mod q, i.e. by converting h to an
122 * integer and reducing it mod q
123 */
124 ret = nn_init_from_buf(&e, hash, hsize); EG(ret, err);
125 ret = local_memset(hash, 0, hsize); EG(ret, err);
126 dbg_nn_print("h initial import as nn", &e);
127 if (rshift) {
128 ret = nn_rshift_fixedlen(&e, &e, rshift); EG(ret, err);
129 }
130 dbg_nn_print("h final import as nn", &e);
131 ret = nn_mod(&e, &e, q); EG(ret, err);
132 dbg_nn_print("e", &e);
133
134 /*
135 NOTE: the restart label is removed in CRYPTOFUZZ mode as
136 we trigger MUST_HAVE instead of restarting in this mode.
137 restart:
138 */
139 /* 4. get a random value k in ]0,q[ */
140 /* NOTE: copy our input nonce if not NULL */
141 if(nonce != NULL){
142 MUST_HAVE((noncelen <= (u8)(BYTECEIL(q_bit_len))), ret, err);
143 ret = nn_init_from_buf(&k, nonce, noncelen); EG(ret, err);
144 }
145 else{
146 ret = ctx->rand(&k, q); EG(ret, err);
147 }
148 dbg_nn_print("k", &k);
149
150 #ifdef USE_SIG_BLINDING
151 /* Note: if we use blinding, r and e are multiplied by
152 * a random value b in ]0,q[ */
153 ret = nn_get_random_mod(&b, q); EG(ret, err);
154 dbg_nn_print("b", &b);
155 #endif /* USE_SIG_BLINDING */
156
157
158 /* 5. Compute W = (W_x,W_y) = kG */
159 #ifdef USE_SIG_BLINDING
160 ret = prj_pt_mul_blind(&kG, &k, G); EG(ret, err);
161 #else
162 ret = prj_pt_mul(&kG, &k, G); EG(ret, err);
163 #endif /* USE_SIG_BLINDING */
164 ret = prj_pt_unique(&kG, &kG); EG(ret, err);
165
166 dbg_nn_print("W_x", &(kG.X.fp_val));
167 dbg_nn_print("W_y", &(kG.Y.fp_val));
168
169 /* 6. Compute r = W_x mod q */
170 ret = nn_mod(&r, &(kG.X.fp_val), q); EG(ret, err);
171 dbg_nn_print("r", &r);
172
173 /* 7. If r is 0, restart the process at step 4. */
174 /* NOTE: for the CRYPTOFUZZ mode, we do not restart
175 * the procedure but throw an assert exception instead.
176 */
177 ret = nn_iszero(&r, &iszero); EG(ret, err);
178 MUST_HAVE((!iszero), ret, err);
179
180 /* Export r */
181 ret = nn_export_to_buf(sig, q_len, &r); EG(ret, err);
182
183 #ifdef USE_SIG_BLINDING
184 /* Blind r with b */
185 ret = nn_mod_mul(&r, &r, &b, q); EG(ret, err);
186
187 /* Blind the message e */
188 ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err);
189 #endif /* USE_SIG_BLINDING */
190
191 /* tmp = xr mod q */
192 ret = nn_mod_mul(&tmp, x, &r, q); EG(ret, err);
193 dbg_nn_print("x*r mod q", &tmp);
194
195 /* 8. If e == rx, restart the process at step 4. */
196 /* NOTE: for the CRYPTOFUZZ mode, we do not restart
197 * the procedure but throw an assert exception instead.
198 */
199 ret = nn_cmp(&e, &tmp, &cmp); EG(ret, err);
200 MUST_HAVE(cmp, ret, err);
201
202 /* 9. Compute s = k^-1 * (xr + e) mod q */
203
204 /* tmp2 = (e + xr) mod q */
205 ret = nn_mod_add(&tmp, &tmp, &e, q); EG(ret, err);
206 dbg_nn_print("(xr + e) mod q", &tmp);
207
208 #ifdef USE_SIG_BLINDING
209 /* In case of blinding, we compute (b*k)^-1, and
210 * b^-1 will automatically unblind (r*x) in the following
211 */
212 ret = nn_mod_mul(&k, &k, &b, q); EG(ret, err);
213 #endif
214 /* Compute k^-1 mod q */
215 /* NOTE: we use Fermat's little theorem inversion for
216 * constant time here. This is possible since q is prime.
217 */
218 ret = nn_modinv_fermat(&kinv, &k, q); EG(ret, err);
219
220 dbg_nn_print("k^-1 mod q", &kinv);
221
222 /* s = k^-1 * tmp2 mod q */
223 ret = nn_mod_mul(&s, &tmp, &kinv, q); EG(ret, err);
224
225 dbg_nn_print("s", &s);
226
227 /* 10. If s is 0, restart the process at step 4. */
228 /* NOTE: for the CRYPTOFUZZ mode, we do not restart
229 * the procedure but throw an assert exception instead.
230 */
231 ret = nn_iszero(&s, &iszero); EG(ret, err);
232 MUST_HAVE((!iszero), ret, err);
233
234 /* 11. return (r,s) */
235 ret = nn_export_to_buf(sig + q_len, q_len, &s);
236
237 err:
238
239 nn_uninit(&r);
240 nn_uninit(&s);
241 nn_uninit(&e);
242 nn_uninit(&tmp);
243 nn_uninit(&k);
244 nn_uninit(&kinv);
245 prj_pt_uninit(&kG);
246
247 /*
248 * We can now clear data part of the context. This will clear
249 * magic and avoid further reuse of the whole context.
250 */
251 if(ctx != NULL){
252 IGNORE_RET_VAL(local_memset(&(ctx->sign_data.ecdsa), 0, sizeof(ecdsa_sign_data)));
253 }
254
255 /* Clean what remains on the stack */
256 PTR_NULLIFY(priv_key);
257 PTR_NULLIFY(G);
258 PTR_NULLIFY(q);
259 PTR_NULLIFY(x);
260 VAR_ZEROIFY(q_len);
261 VAR_ZEROIFY(q_bit_len);
262 VAR_ZEROIFY(rshift);
263 VAR_ZEROIFY(hsize);
264
265 #ifdef USE_SIG_BLINDING
266 nn_uninit(&b);
267 #endif /* USE_SIG_BLINDING */
268
269 return ret;
270 }
271
272 /******************************/
273 #define ECDSA_VERIFY_MAGIC ((word_t)(0x5155fe73e7fd51beULL))
274 #define ECDSA_VERIFY_CHECK_INITIALIZED(A, ret, err) \
275 MUST_HAVE((((void *)(A)) != NULL) && ((A)->magic == ECDSA_VERIFY_MAGIC), ret, err)
276
ecdsa_verify_raw(struct ec_verify_context * ctx,const u8 * input,u8 inputlen)277 int ecdsa_verify_raw(struct ec_verify_context *ctx, const u8 *input, u8 inputlen)
278 {
279 prj_pt uG, vY;
280 prj_pt_t W_prime;
281 nn e, sinv, uv, r_prime;
282 prj_pt_src_t G, Y;
283 /* NOTE: hash here is not really a hash ... */
284 u8 hash[LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8))];
285 bitcnt_t rshift, q_bit_len;
286 nn_src_t q;
287 nn *s, *r;
288 u8 hsize;
289 int ret, iszero, cmp;
290
291 e.magic = sinv.magic = uv.magic = r_prime.magic = WORD(0);
292 uG.magic = vY.magic = WORD(0);
293
294 /* NOTE: we reuse uG for W_prime to optimize local variables */
295 W_prime = &uG;
296
297 /*
298 * First, verify context has been initialized and public
299 * part too. This guarantees the context is an ECDSA
300 * verification one and we do not finalize() before init().
301 */
302 ret = sig_verify_check_initialized(ctx); EG(ret, err);
303 ECDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecdsa), ret, err);
304 MUST_HAVE((input != NULL), ret, err);
305
306 /* Zero init points */
307 ret = local_memset(&uG, 0, sizeof(prj_pt)); EG(ret, err);
308 ret = local_memset(&vY, 0, sizeof(prj_pt)); EG(ret, err);
309
310 /* Make things more readable */
311 G = &(ctx->pub_key->params->ec_gen);
312 Y = &(ctx->pub_key->y);
313 q = &(ctx->pub_key->params->ec_gen_order);
314 q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen;
315 hsize = inputlen;
316 r = &(ctx->verify_data.ecdsa.r);
317 s = &(ctx->verify_data.ecdsa.s);
318
319 /* 2. Compute h = H(m) */
320 /* NOTE: here we have raw ECDSA, this is the raw input */
321 MUST_HAVE((input != NULL), ret, err);
322 /* NOTE: the MUST_HAVE is protected by a preprocessing check
323 * to avoid -Werror=type-limits errors:
324 * "error: comparison is always true due to limited range of data type"
325 */
326 #if LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8)) < 255
327 MUST_HAVE(((u32)inputlen <= sizeof(hash)), ret, err);
328 #endif
329
330 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err);
331 ret = local_memcpy(hash, input, hsize); EG(ret, err);
332
333 dbg_buf_print("h = H(m)", hash, hsize);
334
335 /*
336 * 3. If |h| > bitlen(q), set h to bitlen(q)
337 * leftmost bits of h.
338 *
339 * Note that it's easier to check here if the truncation
340 * needs to be done but implement it using a logical
341 * shift at the beginning of step 3. below once the hash
342 * has been converted to an integer.
343 */
344 rshift = 0;
345 if ((hsize * 8) > q_bit_len) {
346 rshift = (bitcnt_t)((hsize * 8) - q_bit_len);
347 }
348
349 /*
350 * 4. Compute e = OS2I(h) mod q, by converting h to an integer
351 * and reducing it mod q
352 */
353 ret = nn_init_from_buf(&e, hash, hsize); EG(ret, err);
354 ret = local_memset(hash, 0, hsize); EG(ret, err);
355 dbg_nn_print("h initial import as nn", &e);
356 if (rshift) {
357 ret = nn_rshift_fixedlen(&e, &e, rshift); EG(ret, err);
358 }
359 dbg_nn_print("h final import as nn", &e);
360
361 ret = nn_mod(&e, &e, q); EG(ret, err);
362 dbg_nn_print("e", &e);
363
364 /* Compute s^-1 mod q */
365 ret = nn_modinv(&sinv, s, q); EG(ret, err);
366 dbg_nn_print("s", s);
367 dbg_nn_print("sinv", &sinv);
368 nn_uninit(s);
369
370 /* 5. Compute u = (s^-1)e mod q */
371 ret = nn_mod_mul(&uv, &e, &sinv, q); EG(ret, err);
372 dbg_nn_print("u = (s^-1)e mod q", &uv);
373 ret = prj_pt_mul(&uG, &uv, G); EG(ret, err);
374
375 /* 6. Compute v = (s^-1)r mod q */
376 ret = nn_mod_mul(&uv, r, &sinv, q); EG(ret, err);
377 dbg_nn_print("v = (s^-1)r mod q", &uv);
378 ret = prj_pt_mul(&vY, &uv, Y); EG(ret, err);
379
380 /* 7. Compute W' = uG + vY */
381 ret = prj_pt_add(W_prime, &uG, &vY); EG(ret, err);
382
383 /* 8. If W' is the point at infinity, reject the signature. */
384 ret = prj_pt_iszero(W_prime, &iszero); EG(ret, err);
385 MUST_HAVE((!iszero), ret, err);
386
387 /* 9. Compute r' = W'_x mod q */
388 ret = prj_pt_unique(W_prime, W_prime); EG(ret, err);
389 dbg_nn_print("W'_x", &(W_prime->X.fp_val));
390 dbg_nn_print("W'_y", &(W_prime->Y.fp_val));
391 ret = nn_mod(&r_prime, &(W_prime->X.fp_val), q); EG(ret, err);
392
393 /* 10. Accept the signature if and only if r equals r' */
394 ret = nn_cmp(&r_prime, r, &cmp); EG(ret, err);
395 ret = (cmp != 0) ? -1 : 0;
396
397 err:
398 nn_uninit(&r_prime);
399 nn_uninit(&uv);
400 nn_uninit(&e);
401 nn_uninit(&sinv);
402 prj_pt_uninit(&uG);
403 prj_pt_uninit(&vY);
404
405 /*
406 * We can now clear data part of the context. This will clear
407 * magic and avoid further reuse of the whole context.
408 */
409 if(ctx != NULL){
410 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.ecdsa), 0, sizeof(ecdsa_verify_data)));
411 }
412
413 /* Clean what remains on the stack */
414 PTR_NULLIFY(W_prime);
415 PTR_NULLIFY(G);
416 PTR_NULLIFY(Y);
417 VAR_ZEROIFY(rshift);
418 VAR_ZEROIFY(q_bit_len);
419 PTR_NULLIFY(q);
420 PTR_NULLIFY(s);
421 PTR_NULLIFY(r);
422 VAR_ZEROIFY(hsize);
423
424 return ret;
425 }
426
427
428 #else /* WITH_SIG_ECDSA && USE_CRYPTOFUZZ */
429
430 /*
431 * Dummy definition to avoid the empty translation unit ISO C warning
432 */
433 typedef int dummy;
434 #endif /* WITH_SIG_ECDSA */
435