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_ECRDSA) && 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 "ECRDSA"
28 #endif
29 #include <libecc/utils/dbg_sig.h>
30
31 /* NOTE: the following versions of ECRDSA 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 /*
38 * NOTE: ISO/IEC 14888-3 standard seems to diverge from the existing implementations
39 * of ECRDSA when treating the message hash, and from the examples of certificates provided
40 * in RFC 7091 and draft-deremin-rfc4491-bis. While in ISO/IEC 14888-3 it is explicitely asked
41 * to proceed with the hash of the message as big endian, the RFCs derived from the Russian
42 * standard expect the hash value to be treated as little endian when importing it as an integer
43 * (this discrepancy is exhibited and confirmed by test vectors present in ISO/IEC 14888-3, and
44 * by X.509 certificates present in the RFCs). This seems (to be confirmed) to be a discrepancy of
45 * ISO/IEC 14888-3 algorithm description that must be fixed there.
46 *
47 * In order to be conservative, libecc uses the Russian standard behavior as expected to be in line with
48 * other implemetations, but keeps the ISO/IEC 14888-3 behavior if forced/asked by the user using
49 * the USE_ISO14888_3_ECRDSA toggle. This allows to keep backward compatibility with previous versions of the
50 * library if needed.
51 *
52 */
53 #ifndef USE_ISO14888_3_ECRDSA
54 /* Reverses the endiannes of a buffer in place */
_reverse_endianness(u8 * buf,u16 buf_size)55 ATTRIBUTE_WARN_UNUSED_RET static inline int _reverse_endianness(u8 *buf, u16 buf_size)
56 {
57 u16 i;
58 u8 tmp;
59 int ret;
60
61 MUST_HAVE((buf != NULL), ret, err);
62
63 if(buf_size > 1){
64 for(i = 0; i < (buf_size / 2); i++){
65 tmp = buf[i];
66 buf[i] = buf[buf_size - 1 - i];
67 buf[buf_size - 1 - i] = tmp;
68 }
69 }
70
71 ret = 0;
72 err:
73 return ret;
74 }
75 #endif
76
77 #define ECRDSA_SIGN_MAGIC ((word_t)(0xcc97bbc8ada8973cULL))
78 #define ECRDSA_SIGN_CHECK_INITIALIZED(A, ret, err) \
79 MUST_HAVE((((const void *)(A)) != NULL) && \
80 ((A)->magic == ECRDSA_SIGN_MAGIC), ret, err)
81
ecrdsa_sign_raw(struct ec_sign_context * ctx,const u8 * input,u8 inputlen,u8 * sig,u8 siglen,const u8 * nonce,u8 noncelen)82 int ecrdsa_sign_raw(struct ec_sign_context *ctx, const u8 *input, u8 inputlen, u8 *sig, u8 siglen, const u8 *nonce, u8 noncelen)
83 {
84 bitcnt_t q_bit_len, p_bit_len;
85 const ec_priv_key *priv_key;
86 /* NOTE: hash here is not really a hash ... */
87 u8 h_buf[LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8))];
88 prj_pt_src_t G;
89 prj_pt kG;
90 nn_src_t q, x;
91 u8 hsize, r_len, s_len;
92 int ret, iszero;
93 nn tmp, s, rx, ke, k, r, e;
94 #ifdef USE_SIG_BLINDING
95 /* b is the blinding mask */
96 nn b, binv;
97 b.magic = binv.magic = WORD(0);
98 #endif /* USE_SIG_BLINDING */
99
100 tmp.magic = s.magic = rx.magic = ke.magic = WORD(0);
101 k.magic = r.magic = e.magic = WORD(0);
102 kG.magic = WORD(0);
103
104 /*
105 * First, verify context has been initialized and private
106 * part too. This guarantees the context is an EC-RDSA
107 * signature one and we do not finalize() before init().
108 */
109 ret = sig_sign_check_initialized(ctx); EG(ret, err);
110 ECRDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecrdsa), ret, err);
111
112 /* Zero init points */
113 ret = local_memset(&kG, 0, sizeof(prj_pt)); EG(ret, err);
114
115 /* Make things more readable */
116 priv_key = &(ctx->key_pair->priv_key);
117 G = &(priv_key->params->ec_gen);
118 q = &(priv_key->params->ec_gen_order);
119 p_bit_len = priv_key->params->ec_fp.p_bitlen;
120 q_bit_len = priv_key->params->ec_gen_order_bitlen;
121 x = &(priv_key->x);
122 r_len = (u8)ECRDSA_R_LEN(q_bit_len);
123 s_len = (u8)ECRDSA_S_LEN(q_bit_len);
124 hsize = inputlen;
125
126 MUST_HAVE((NN_MAX_BIT_LEN >= p_bit_len), ret, err);
127
128 MUST_HAVE((siglen == ECRDSA_SIGLEN(q_bit_len)), ret, err);
129
130 dbg_nn_print("p", &(priv_key->params->ec_fp.p));
131 dbg_nn_print("q", q);
132 dbg_priv_key_print("x", priv_key);
133 dbg_pub_key_print("Y", &(ctx->key_pair->pub_key));
134 dbg_ec_point_print("G", G);
135
136 /*
137 NOTE: the restart label is removed in CRYPTOFUZZ mode as
138 we trigger MUST_HAVE instead of restarting in this mode.
139 restart:
140 */
141 /* 2. Get a random value k in ]0, q[ ... */
142 /* NOTE: copy our input nonce if not NULL */
143 if(nonce != NULL){
144 MUST_HAVE((noncelen <= (u8)(BYTECEIL(q_bit_len))), ret, err);
145 ret = nn_init_from_buf(&k, nonce, noncelen); EG(ret, err);
146 }
147 else{
148 ret = ctx->rand(&k, q); EG(ret, err);
149 }
150
151 dbg_nn_print("k", &k);
152 #ifdef USE_SIG_BLINDING
153 /* Note: if we use blinding, k and e are multiplied by
154 * a random value b in ]0,q[ */
155 ret = nn_get_random_mod(&b, q); EG(ret, err);
156 dbg_nn_print("b", &b);
157 #endif /* USE_SIG_BLINDING */
158
159 /* 3. Compute W = kG = (Wx, Wy) */
160 #ifdef USE_SIG_BLINDING
161 /* We use blinding for the scalar multiplication */
162 ret = prj_pt_mul_blind(&kG, &k, G); EG(ret, err);
163 #else
164 ret = prj_pt_mul(&kG, &k, G); EG(ret, err);
165 #endif /* USE_SIG_BLINDING */
166 ret = prj_pt_unique(&kG, &kG); EG(ret, err);
167 dbg_nn_print("W_x", &(kG.X.fp_val));
168 dbg_nn_print("W_y", &(kG.Y.fp_val));
169
170 /* 4. Compute r = Wx mod q */
171 ret = nn_mod(&r, &(kG.X.fp_val), q); EG(ret, err);
172
173 /* 5. If r is 0, restart the process at step 2. */
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 dbg_nn_print("r", &r);
181
182 /* Export r */
183 ret = nn_export_to_buf(sig, r_len, &r); EG(ret, err);
184
185 /* 6. Compute e = OS2I(h) mod q. If e is 0, set e to 1. */
186 /* NOTE: here we have raw ECRDSA, this is the raw input */
187 MUST_HAVE((input != NULL), ret, err);
188 /* NOTE: the MUST_HAVE is protected by a preprocessing check
189 * to avoid -Werror=type-limits errors:
190 * "error: comparison is always true due to limited range of data type"
191 */
192 #if LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8)) < 255
193 MUST_HAVE(((u32)inputlen <= sizeof(h_buf)), ret, err);
194 #endif
195 ret = local_memset(h_buf, 0, sizeof(h_buf)); EG(ret, err);
196 ret = local_memcpy(h_buf, input, hsize); EG(ret, err);
197 dbg_buf_print("H(m)", h_buf, hsize);
198 /* NOTE: this handles a discrepancy between ISO/IEC 14888-3 and
199 * Russian standard based RFCs.
200 */
201 #ifndef USE_ISO14888_3_ECRDSA
202 ret = _reverse_endianness(h_buf, hsize); EG(ret, err);
203 #endif
204
205 ret = nn_init_from_buf(&tmp, h_buf, hsize); EG(ret, err);
206 ret = local_memset(h_buf, 0, hsize); EG(ret, err);
207 ret = nn_mod(&e, &tmp, q); EG(ret, err);
208 ret = nn_iszero(&e, &iszero); EG(ret, err);
209 if (iszero) {
210 ret = nn_inc(&e, &e); EG(ret, err);
211 }
212 dbg_nn_print("e", &e);
213
214 #ifdef USE_SIG_BLINDING
215 /* In case of blinding, we blind r and e */
216 ret = nn_mod_mul(&r, &r, &b, q); EG(ret, err);
217 ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err);
218 #endif /* USE_SIG_BLINDING */
219
220 /* Compute s = (rx + ke) mod q */
221 ret = nn_mod_mul(&rx, &r, x, q); EG(ret, err);
222 ret = nn_mod_mul(&ke, &k, &e, q); EG(ret, err);
223 ret = nn_mod_add(&s, &rx, &ke, q); EG(ret, err);
224 #ifdef USE_SIG_BLINDING
225 /* Unblind s */
226 /* NOTE: we use Fermat's little theorem inversion for
227 * constant time here. This is possible since q is prime.
228 */
229 ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err);
230 ret = nn_mod_mul(&s, &s, &binv, q); EG(ret, err);
231 #endif /* USE_SIG_BLINDING */
232
233 /* If s is 0, restart the process at step 2. */
234 /* 10. If s is 0, restart the process at step 4. */
235 /* NOTE: for the CRYPTOFUZZ mode, we do not restart
236 * the procedure but throw an assert exception instead.
237 */
238 ret = nn_iszero(&s, &iszero); EG(ret, err);
239 MUST_HAVE((!iszero), ret, err);
240
241 dbg_nn_print("s", &s);
242
243 /* Return (r,s) */
244 ret = nn_export_to_buf(sig + r_len, s_len, &s); EG(ret, err);
245
246 err:
247 nn_uninit(&r);
248 nn_uninit(&s);
249 nn_uninit(&tmp);
250 nn_uninit(&rx);
251 nn_uninit(&ke);
252 nn_uninit(&k);
253 nn_uninit(&e);
254 prj_pt_uninit(&kG);
255
256 /*
257 * We can now clear data part of the context. This will clear
258 * magic and avoid further reuse of the whole context.
259 */
260 if(ctx != NULL){
261 IGNORE_RET_VAL(local_memset(&(ctx->sign_data.ecrdsa), 0, sizeof(ecrdsa_sign_data)));
262 }
263
264 /* Clean what remains on the stack */
265 VAR_ZEROIFY(r_len);
266 VAR_ZEROIFY(s_len);
267 VAR_ZEROIFY(q_bit_len);
268 VAR_ZEROIFY(p_bit_len);
269 VAR_ZEROIFY(hsize);
270 PTR_NULLIFY(priv_key);
271 PTR_NULLIFY(G);
272 PTR_NULLIFY(q);
273 PTR_NULLIFY(x);
274
275 #ifdef USE_SIG_BLINDING
276 nn_uninit(&b);
277 nn_uninit(&binv);
278 #endif /* USE_SIG_BLINDING */
279
280 return ret;
281 }
282
283 /******************************/
284 #define ECRDSA_VERIFY_MAGIC ((word_t)(0xa8e16b7e8180cb9aULL))
285 #define ECRDSA_VERIFY_CHECK_INITIALIZED(A, ret, err) \
286 MUST_HAVE((((const void *)(A)) != NULL) && \
287 ((A)->magic == ECRDSA_VERIFY_MAGIC), ret, err)
288
ecrdsa_verify_raw(struct ec_verify_context * ctx,const u8 * input,u8 inputlen)289 int ecrdsa_verify_raw(struct ec_verify_context *ctx, const u8 *input, u8 inputlen)
290 {
291 prj_pt_src_t G, Y;
292 nn_src_t q;
293 nn tmp, h, r_prime, e, v, u;
294 prj_pt vY, uG;
295 prj_pt_t Wprime;
296 /* NOTE: hash here is not really a hash ... */
297 u8 h_buf[LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8))];
298 nn *r, *s;
299 u8 hsize;
300 int ret, iszero, cmp;
301
302 tmp.magic = h.magic = r_prime.magic = e.magic = WORD(0);
303 v.magic = u.magic = WORD(0);
304 vY.magic = uG.magic = WORD(0);
305
306 /* NOTE: we reuse uG for Wprime to optimize local variables */
307 Wprime = &uG;
308
309 /*
310 * First, verify context has been initialized and public
311 * part too. This guarantees the context is an EC-RDSA
312 * verification one and we do not finalize() before init().
313 */
314 ret = sig_verify_check_initialized(ctx); EG(ret, err);
315 ECRDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecrdsa), ret, err);
316
317 /* Zero init points */
318 ret = local_memset(&uG, 0, sizeof(prj_pt)); EG(ret, err);
319 ret = local_memset(&vY, 0, sizeof(prj_pt)); EG(ret, err);
320
321 /* Make things more readable */
322 G = &(ctx->pub_key->params->ec_gen);
323 Y = &(ctx->pub_key->y);
324 q = &(ctx->pub_key->params->ec_gen_order);
325 r = &(ctx->verify_data.ecrdsa.r);
326 s = &(ctx->verify_data.ecrdsa.s);
327 hsize = inputlen;
328
329 /* 2. Compute h = H(m) */
330 /* NOTE: here we have raw ECRDSA, this is the raw input */
331 MUST_HAVE((input != NULL), ret, err);
332 /* NOTE: the MUST_HAVE is protected by a preprocessing check
333 * to avoid -Werror=type-limits errors:
334 * "error: comparison is always true due to limited range of data type"
335 */
336 #if LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8)) < 255
337 MUST_HAVE(((u32)inputlen <= sizeof(h_buf)), ret, err);
338 #endif
339
340 ret = local_memset(h_buf, 0, sizeof(h_buf)); EG(ret, err);
341 ret = local_memcpy(h_buf, input, hsize); EG(ret, err);
342 dbg_buf_print("H(m)", h_buf, hsize);
343 /* NOTE: this handles a discrepancy between ISO/IEC 14888-3 and
344 * Russian standard based RFCs.
345 */
346 #ifndef USE_ISO14888_3_ECRDSA
347 ret = _reverse_endianness(h_buf, hsize); EG(ret, err);
348 #endif
349
350 /* 3. Compute e = OS2I(h)^-1 mod q */
351 ret = nn_init_from_buf(&tmp, h_buf, hsize); EG(ret, err);
352 ret = local_memset(h_buf, 0, hsize); EG(ret, err);
353 ret = nn_mod(&h, &tmp, q); EG(ret, err); /* h = OS2I(h) mod q */
354 ret = nn_iszero(&h, &iszero); EG(ret, err);
355 if (iszero) { /* If h is equal to 0, set it to 1 */
356 ret = nn_inc(&h, &h); EG(ret, err);
357 }
358 ret = nn_modinv(&e, &h, q); EG(ret, err); /* e = h^-1 mod q */
359
360 /* 4. Compute u = es mod q */
361 ret = nn_mul(&tmp, &e, s); EG(ret, err);
362 ret = nn_mod(&u, &tmp, q); EG(ret, err);
363
364 /* 5. Compute v = -er mod q
365 *
366 * Because we only support positive integers, we compute
367 * v = -er mod q = q - (er mod q) (except when er is 0).
368 */
369 ret = nn_mul(&tmp, &e, r); EG(ret, err); /* tmp = er */
370 ret = nn_mod(&tmp, &tmp, q); EG(ret, err); /* tmp = er mod q */
371 ret = nn_mod_neg(&v, &tmp, q); EG(ret, err); /* negate tmp */
372
373 /* 6. Compute W' = uG + vY = (W'_x, W'_y) */
374 ret = prj_pt_mul(&uG, &u, G); EG(ret, err);
375 ret = prj_pt_mul(&vY, &v, Y); EG(ret, err);
376 ret = prj_pt_add(Wprime, &uG, &vY); EG(ret, err);
377 ret = prj_pt_unique(Wprime, Wprime); EG(ret, err);
378 dbg_nn_print("W'_x", &(Wprime->X.fp_val));
379 dbg_nn_print("W'_y", &(Wprime->Y.fp_val));
380
381 /* 7. Compute r' = W'_x mod q */
382 ret = nn_mod(&r_prime, &(Wprime->X.fp_val), q); EG(ret, err);
383
384 /* 8. Check r and r' are the same */
385 ret = nn_cmp(r, &r_prime, &cmp); EG(ret, err);
386 ret = (cmp == 0) ? 0 : -1;
387
388 err:
389 nn_uninit(&r_prime);
390 nn_uninit(&tmp);
391 nn_uninit(&h);
392 nn_uninit(&e);
393 nn_uninit(&u);
394 nn_uninit(&v);
395 prj_pt_uninit(&vY);
396 prj_pt_uninit(&uG);
397
398 /*
399 * We can now clear data part of the context. This will clear
400 * magic and avoid further reuse of the whole context.
401 */
402 if(ctx != NULL){
403 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.ecrdsa), 0,
404 sizeof(ecrdsa_verify_data)));
405 }
406
407 /* Clean what remains on the stack */
408 PTR_NULLIFY(Wprime);
409 PTR_NULLIFY(G);
410 PTR_NULLIFY(Y);
411 PTR_NULLIFY(q);
412 PTR_NULLIFY(r);
413 PTR_NULLIFY(s);
414 VAR_ZEROIFY(hsize);
415
416 return ret;
417 }
418
419 #else /* WITH_SIG_ECRDSA && USE_CRYPTOFUZZ */
420
421 /*
422 * Dummy definition to avoid the empty translation unit ISO C warning
423 */
424 typedef int dummy;
425 #endif /* WITH_SIG_ECRDSA */
426