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_ECGDSA) && 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 "ECGDSA"
28 #endif
29 #include <libecc/utils/dbg_sig.h>
30
31 /* NOTE: the following versions of ECGDSA 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 #define ECGDSA_SIGN_MAGIC ((word_t)(0xe2f60ea3353ecc9eULL))
37 #define ECGDSA_SIGN_CHECK_INITIALIZED(A, ret, err) \
38 MUST_HAVE((((const void *)(A)) != NULL) && \
39 ((A)->magic == ECGDSA_SIGN_MAGIC), ret, err)
40
ecgdsa_sign_raw(struct ec_sign_context * ctx,const u8 * input,u8 inputlen,u8 * sig,u8 siglen,const u8 * nonce,u8 noncelen)41 int ecgdsa_sign_raw(struct ec_sign_context *ctx, const u8 *input, u8 inputlen, u8 *sig, u8 siglen, const u8 *nonce, u8 noncelen)
42 {
43 nn_src_t q, x;
44 /* NOTE: hash here is not really a hash ... */
45 u8 e_buf[LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8))];
46 const ec_priv_key *priv_key;
47 prj_pt_src_t G;
48 u8 hsize, r_len, s_len;
49 bitcnt_t q_bit_len, p_bit_len, rshift;
50 prj_pt kG;
51 int ret, iszero;
52 nn tmp, tmp2, s, e, kr, k, r;
53 #ifdef USE_SIG_BLINDING
54 /* b is the blinding mask */
55 nn b, binv;
56 b.magic = binv.magic = WORD(0);
57 #endif
58 tmp.magic = tmp2.magic = s.magic = e.magic = WORD(0);
59 kr.magic = k.magic = r.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 EC-GDSA
65 * signature one and we do not finalize() before init().
66 */
67 ret = sig_sign_check_initialized(ctx); EG(ret, err);
68 ECGDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecgdsa), ret, err);
69 MUST_HAVE((sig != NULL) && (input != NULL), ret, err);
70
71 /* Zero init points */
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 G = &(priv_key->params->ec_gen);
77 q = &(priv_key->params->ec_gen_order);
78 x = &(priv_key->x);
79 q_bit_len = priv_key->params->ec_gen_order_bitlen;
80 p_bit_len = priv_key->params->ec_fp.p_bitlen;
81 MUST_HAVE(((u32)BYTECEIL(p_bit_len) <= NN_MAX_BYTE_LEN), ret, err);
82 r_len = (u8)ECGDSA_R_LEN(q_bit_len);
83 s_len = (u8)ECGDSA_S_LEN(q_bit_len);
84 hsize = inputlen;
85
86 MUST_HAVE((siglen == ECGDSA_SIGLEN(q_bit_len)), ret, err);
87
88 dbg_nn_print("p", &(priv_key->params->ec_fp.p));
89 dbg_nn_print("q", q);
90 dbg_priv_key_print("x", priv_key);
91 dbg_ec_point_print("G", G);
92 dbg_pub_key_print("Y", &(ctx->key_pair->pub_key));
93
94 /* 1. Compute h = H(m) */
95 /* NOTE: here we have raw ECGDSA, this is the raw input */
96 /* NOTE: the MUST_HAVE is protected by a preprocessing check
97 * to avoid -Werror=type-limits errors:
98 * "error: comparison is always true due to limited range of data type"
99 */
100 #if LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8)) < 255
101 MUST_HAVE(((u32)inputlen <= sizeof(e_buf)), ret, err);
102 #endif
103 ret = local_memset(e_buf, 0, sizeof(e_buf)); EG(ret, err);
104 ret = local_memcpy(e_buf, input, hsize); EG(ret, err);
105 dbg_buf_print("H(m)", e_buf, hsize);
106
107 /*
108 * If |h| > bitlen(q), set h to bitlen(q)
109 * leftmost bits of h.
110 *
111 */
112 rshift = 0;
113 if ((hsize * 8) > q_bit_len) {
114 rshift = (bitcnt_t)((hsize * 8) - q_bit_len);
115 }
116 ret = nn_init_from_buf(&tmp, e_buf, hsize); EG(ret, err);
117 ret = local_memset(e_buf, 0, hsize); EG(ret, err);
118 if (rshift) {
119 ret = nn_rshift_fixedlen(&tmp, &tmp, rshift); EG(ret, err);
120 }
121 dbg_nn_print("H(m) truncated as nn", &tmp);
122
123 /*
124 * 2. Convert h to an integer and then compute e = -h mod q,
125 * i.e. compute e = - OS2I(h) mod q
126 *
127 * Because we only support positive integers, we compute
128 * e = q - (h mod q) (except when h is 0).
129 */
130 ret = nn_mod(&tmp2, &tmp, q); EG(ret, err);
131 ret = nn_mod_neg(&e, &tmp2, q); EG(ret, err);
132
133 /*
134 NOTE: the restart label is removed in CRYPTOFUZZ mode as
135 we trigger MUST_HAVE instead of restarting in this mode.
136 restart:
137 */
138 /* 3. Get a random value k in ]0,q[ */
139 /* NOTE: copy our input nonce if not NULL */
140 if(nonce != NULL){
141 MUST_HAVE((noncelen <= (u8)(BYTECEIL(q_bit_len))), ret, err);
142 ret = nn_init_from_buf(&k, nonce, noncelen); EG(ret, err);
143 }
144 else{
145 ret = ctx->rand(&k, q); EG(ret, err);
146 }
147
148 #ifdef USE_SIG_BLINDING
149 /* Note: if we use blinding, e and e are multiplied by
150 * a random value b in ]0,q[ */
151 ret = nn_get_random_mod(&b, q); EG(ret, err);
152 dbg_nn_print("b", &b);
153 #endif /* USE_SIG_BLINDING */
154
155
156 /* 4. Compute W = kG = (Wx, Wy) */
157 #ifdef USE_SIG_BLINDING
158 /* We use blinding for the scalar multiplication */
159 ret = prj_pt_mul_blind(&kG, &k, G); EG(ret, err);
160 #else
161 ret = prj_pt_mul(&kG, &k, G); EG(ret, err);
162 #endif /* USE_SIG_BLINDING */
163 ret = prj_pt_unique(&kG, &kG); EG(ret, err);
164
165 dbg_nn_print("W_x", &(kG.X.fp_val));
166 dbg_nn_print("W_y", &(kG.Y.fp_val));
167
168 /* 5. Compute r = Wx mod q */
169 ret = nn_mod(&r, &(kG.X.fp_val), q); EG(ret, err);
170 dbg_nn_print("r", &r);
171
172 /* 6. If r is 0, restart the process at step 4. */
173 /* NOTE: for the CRYPTOFUZZ mode, we do not restart
174 * the procedure but throw an assert exception instead.
175 */
176 ret = nn_iszero(&r, &iszero); EG(ret, err);
177 MUST_HAVE((!iszero), ret, err);
178
179 /* Export r */
180 ret = nn_export_to_buf(sig, r_len, &r); EG(ret, err);
181
182 #ifdef USE_SIG_BLINDING
183 /* Blind e and r with b */
184 ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err);
185 ret = nn_mod_mul(&r, &r, &b, q); EG(ret, err);
186 #endif /* USE_SIG_BLINDING */
187 /* 7. Compute s = x(kr + e) mod q */
188 ret = nn_mod_mul(&kr, &k, &r, q); EG(ret, err);
189 ret = nn_mod_add(&tmp2, &kr, &e, q); EG(ret, err);
190 ret = nn_mod_mul(&s, x, &tmp2, q); EG(ret, err);
191 #ifdef USE_SIG_BLINDING
192 /* Unblind s */
193 /* NOTE: we use Fermat's little theorem inversion for
194 * constant time here. This is possible since q is prime.
195 */
196 ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err);
197 ret = nn_mod_mul(&s, &s, &binv, q); EG(ret, err);
198 #endif
199 dbg_nn_print("s", &s);
200
201 /* 8. If s is 0, restart the process at step 4. */
202 /* NOTE: for the CRYPTOFUZZ mode, we do not restart
203 * the procedure but throw an assert exception instead.
204 */
205 ret = nn_iszero(&s, &iszero); EG(ret, err);
206 MUST_HAVE((!iszero), ret, err);
207
208 /* 9. Return (r,s) */
209 ret = nn_export_to_buf(sig + r_len, s_len, &s);
210
211 err:
212 nn_uninit(&r);
213 nn_uninit(&s);
214 nn_uninit(&tmp2);
215 nn_uninit(&tmp);
216 nn_uninit(&e);
217 nn_uninit(&kr);
218 nn_uninit(&k);
219
220 prj_pt_uninit(&kG);
221
222 /*
223 * We can now clear data part of the context. This will clear
224 * magic and avoid further reuse of the whole context.
225 */
226 if(ctx != NULL){
227 IGNORE_RET_VAL(local_memset(&(ctx->sign_data.ecgdsa), 0, sizeof(ecgdsa_sign_data)));
228 }
229
230 /* Clean what remains on the stack */
231 VAR_ZEROIFY(q_bit_len);
232 VAR_ZEROIFY(p_bit_len);
233 VAR_ZEROIFY(r_len);
234 VAR_ZEROIFY(s_len);
235 VAR_ZEROIFY(hsize);
236 PTR_NULLIFY(q);
237 PTR_NULLIFY(x);
238 PTR_NULLIFY(priv_key);
239 PTR_NULLIFY(G);
240
241 #ifdef USE_SIG_BLINDING
242 nn_uninit(&b);
243 nn_uninit(&binv);
244 #endif /* USE_SIG_BLINDING */
245
246 return ret;
247 }
248
249 /******************************/
250 #define ECGDSA_VERIFY_MAGIC ((word_t)(0xd4da37527288d1b6ULL))
251 #define ECGDSA_VERIFY_CHECK_INITIALIZED(A, ret, err) \
252 MUST_HAVE((((const void *)(A)) != NULL) && \
253 ((A)->magic == ECGDSA_VERIFY_MAGIC), ret, err)
254
ecgdsa_verify_raw(struct ec_verify_context * ctx,const u8 * input,u8 inputlen)255 int ecgdsa_verify_raw(struct ec_verify_context *ctx, const u8 *input, u8 inputlen)
256 {
257 nn tmp, e, r_prime, rinv, uv, *r, *s;
258 prj_pt uG, vY;
259 prj_pt_t Wprime;
260 prj_pt_src_t G, Y;
261 /* NOTE: hash here is not really a hash ... */
262 u8 e_buf[LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8))];
263 nn_src_t q;
264 u8 hsize;
265 bitcnt_t q_bit_len, rshift;
266 int ret, cmp;
267
268 tmp.magic = e.magic = r_prime.magic = rinv.magic = uv.magic = WORD(0);
269 uG.magic = vY.magic = WORD(0);
270
271 /* NOTE: we reuse uG for Wprime to optimize local variables */
272 Wprime = &uG;
273
274 /*
275 * First, verify context has been initialized and public
276 * part too. This guarantees the context is an EC-GDSA
277 * verification one and we do not finalize() before init().
278 */
279 ret = sig_verify_check_initialized(ctx); EG(ret, err);
280 ECGDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecgdsa), ret, err);
281 MUST_HAVE((input != NULL), ret, err);
282
283 /* Zero init points */
284 ret = local_memset(&uG, 0, sizeof(prj_pt)); EG(ret, err);
285 ret = local_memset(&vY, 0, sizeof(prj_pt)); EG(ret, err);
286
287 /* Make things more readable */
288 G = &(ctx->pub_key->params->ec_gen);
289 Y = &(ctx->pub_key->y);
290 q = &(ctx->pub_key->params->ec_gen_order);
291 r = &(ctx->verify_data.ecgdsa.r);
292 s = &(ctx->verify_data.ecgdsa.s);
293 q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen;
294 hsize = inputlen;
295
296 /* 2. Compute h = H(m) */
297 /* NOTE: here we have raw ECGDSA, this is the raw input */
298 MUST_HAVE((input != NULL), ret, err);
299 /* NOTE: the MUST_HAVE is protected by a preprocessing check
300 * to avoid -Werror=type-limits errors:
301 * "error: comparison is always true due to limited range of data type"
302 */
303 #if LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8)) < 255
304 MUST_HAVE(((u32)inputlen <= sizeof(e_buf)), ret, err);
305 #endif
306
307 ret = local_memset(e_buf, 0, sizeof(e_buf)); EG(ret, err);
308 ret = local_memcpy(e_buf, input, hsize); EG(ret, err);
309 dbg_buf_print("H(m)", e_buf, hsize);
310
311 /*
312 * If |h| > bitlen(q), set h to bitlen(q)
313 * leftmost bits of h.
314 *
315 */
316 rshift = 0;
317 if ((hsize * 8) > q_bit_len) {
318 rshift = (bitcnt_t)((hsize * 8) - q_bit_len);
319 }
320 ret = nn_init_from_buf(&tmp, e_buf, hsize); EG(ret, err);
321 ret = local_memset(e_buf, 0, hsize); EG(ret, err);
322 if (rshift) {
323 ret = nn_rshift_fixedlen(&tmp, &tmp, rshift); EG(ret, err);
324 }
325 dbg_nn_print("H(m) truncated as nn", &tmp);
326
327 /* 3. Compute e by converting h to an integer and reducing it mod q */
328 ret = nn_mod(&e, &tmp, q); EG(ret, err);
329
330 /* 4. Compute u = (r^-1)e mod q */
331 ret = nn_modinv(&rinv, r, q); EG(ret, err); /* r^-1 */
332 ret = nn_mul(&tmp, &rinv, &e); EG(ret, err); /* r^-1 * e */
333 ret = nn_mod(&uv, &tmp, q); EG(ret, err); /* (r^-1 * e) mod q */
334 ret = prj_pt_mul(&uG, &uv, G); EG(ret, err);
335
336 /* 5. Compute v = (r^-1)s mod q */
337 ret = nn_mul(&tmp, &rinv, s); EG(ret, err); /* r^-1 * s */
338 ret = nn_mod(&uv, &tmp, q); EG(ret, err); /* (r^-1 * s) mod q */
339 ret = prj_pt_mul(&vY, &uv, Y); EG(ret, err);
340
341 /* 6. Compute W' = uG + vY */
342 ret = prj_pt_add(Wprime, &uG, &vY); EG(ret, err);
343
344 /* 7. Compute r' = W'_x mod q */
345 ret = prj_pt_unique(Wprime, Wprime); EG(ret, err);
346 dbg_nn_print("W'_x", &(Wprime->X.fp_val));
347 dbg_nn_print("W'_y", &(Wprime->Y.fp_val));
348 ret = nn_mod(&r_prime, &(Wprime->X.fp_val), q); EG(ret, err);
349
350 /* 8. Accept the signature if and only if r equals r' */
351 ret = nn_cmp(r, &r_prime, &cmp); EG(ret, err);
352 ret = (cmp != 0) ? -1 : 0;
353
354 err:
355 nn_uninit(&r_prime);
356 nn_uninit(&e);
357 nn_uninit(&uv);
358 nn_uninit(&tmp);
359 nn_uninit(&rinv);
360
361 prj_pt_uninit(&uG);
362 prj_pt_uninit(&vY);
363
364 /*
365 * We can now clear data part of the context. This will clear
366 * magic and avoid further reuse of the whole context.
367 */
368 if(ctx != NULL){
369 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.ecgdsa), 0,
370 sizeof(ecgdsa_verify_data)));
371 }
372
373 PTR_NULLIFY(Wprime);
374 PTR_NULLIFY(r);
375 PTR_NULLIFY(s);
376 PTR_NULLIFY(G);
377 PTR_NULLIFY(Y);
378 PTR_NULLIFY(q);
379 VAR_ZEROIFY(hsize);
380
381 return ret;
382 }
383
384
385 #else /* WITH_SIG_ECGDSA && USE_CRYPTOFUZZ */
386
387 /*
388 * Dummy definition to avoid the empty translation unit ISO C warning
389 */
390 typedef int dummy;
391 #endif /* WITH_SIG_ECGDSA */
392