Remove a strict aliasing issue with pre-computed curve448 constants
[openssl.git] / crypto / ec / ecdsa_ossl.c
1 /*
2  * Copyright 2002-2018 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the OpenSSL license (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 #include <string.h>
11 #include <openssl/err.h>
12 #include <openssl/obj_mac.h>
13 #include <openssl/bn.h>
14 #include <openssl/rand.h>
15 #include <openssl/ec.h>
16 #include "ec_lcl.h"
17
18 int ossl_ecdsa_sign(int type, const unsigned char *dgst, int dlen,
19                     unsigned char *sig, unsigned int *siglen,
20                     const BIGNUM *kinv, const BIGNUM *r, EC_KEY *eckey)
21 {
22     ECDSA_SIG *s;
23
24     s = ECDSA_do_sign_ex(dgst, dlen, kinv, r, eckey);
25     if (s == NULL) {
26         *siglen = 0;
27         return 0;
28     }
29     *siglen = i2d_ECDSA_SIG(s, &sig);
30     ECDSA_SIG_free(s);
31     return 1;
32 }
33
34 static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in,
35                             BIGNUM **kinvp, BIGNUM **rp,
36                             const unsigned char *dgst, int dlen)
37 {
38     BN_CTX *ctx = NULL;
39     BIGNUM *k = NULL, *r = NULL, *X = NULL;
40     const BIGNUM *order;
41     EC_POINT *tmp_point = NULL;
42     const EC_GROUP *group;
43     int ret = 0;
44     int order_bits;
45
46     if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) {
47         ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_PASSED_NULL_PARAMETER);
48         return 0;
49     }
50
51     if (!EC_KEY_can_sign(eckey)) {
52         ECerr(EC_F_ECDSA_SIGN_SETUP, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING);
53         return 0;
54     }
55
56     if (ctx_in == NULL) {
57         if ((ctx = BN_CTX_new()) == NULL) {
58             ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE);
59             return 0;
60         }
61     } else
62         ctx = ctx_in;
63
64     k = BN_new();               /* this value is later returned in *kinvp */
65     r = BN_new();               /* this value is later returned in *rp */
66     X = BN_new();
67     if (k == NULL || r == NULL || X == NULL) {
68         ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE);
69         goto err;
70     }
71     if ((tmp_point = EC_POINT_new(group)) == NULL) {
72         ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
73         goto err;
74     }
75     order = EC_GROUP_get0_order(group);
76     if (order == NULL) {
77         ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
78         goto err;
79     }
80
81     /* Preallocate space */
82     order_bits = BN_num_bits(order);
83     if (!BN_set_bit(k, order_bits)
84         || !BN_set_bit(r, order_bits)
85         || !BN_set_bit(X, order_bits))
86         goto err;
87
88     do {
89         /* get random k */
90         do
91             if (dgst != NULL) {
92                 if (!BN_generate_dsa_nonce
93                     (k, order, EC_KEY_get0_private_key(eckey), dgst, dlen,
94                      ctx)) {
95                     ECerr(EC_F_ECDSA_SIGN_SETUP,
96                              EC_R_RANDOM_NUMBER_GENERATION_FAILED);
97                     goto err;
98                 }
99             } else {
100                 if (!BN_priv_rand_range(k, order)) {
101                     ECerr(EC_F_ECDSA_SIGN_SETUP,
102                              EC_R_RANDOM_NUMBER_GENERATION_FAILED);
103                     goto err;
104                 }
105             }
106         while (BN_is_zero(k));
107
108         /*
109          * We do not want timing information to leak the length of k, so we
110          * compute G*k using an equivalent scalar of fixed bit-length.
111          *
112          * We unconditionally perform both of these additions to prevent a
113          * small timing information leakage.  We then choose the sum that is
114          * one bit longer than the order.  This guarantees the code
115          * path used in the constant time implementations elsewhere.
116          *
117          * TODO: revisit the BN_copy aiming for a memory access agnostic
118          * conditional copy.
119          */
120         if (!BN_add(r, k, order)
121             || !BN_add(X, r, order)
122             || !BN_copy(k, BN_num_bits(r) > order_bits ? r : X))
123             goto err;
124
125         /* compute r the x-coordinate of generator * k */
126         if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) {
127             ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
128             goto err;
129         }
130         if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) ==
131             NID_X9_62_prime_field) {
132             if (!EC_POINT_get_affine_coordinates_GFp
133                 (group, tmp_point, X, NULL, ctx)) {
134                 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
135                 goto err;
136             }
137         }
138 #ifndef OPENSSL_NO_EC2M
139         else {                  /* NID_X9_62_characteristic_two_field */
140
141             if (!EC_POINT_get_affine_coordinates_GF2m(group,
142                                                       tmp_point, X, NULL,
143                                                       ctx)) {
144                 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
145                 goto err;
146             }
147         }
148 #endif
149         if (!BN_nnmod(r, X, order, ctx)) {
150             ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
151             goto err;
152         }
153     }
154     while (BN_is_zero(r));
155
156     /* Check if optimized inverse is implemented */
157     if (EC_GROUP_do_inverse_ord(group, k, k, ctx) == 0) {
158         /* compute the inverse of k */
159         if (group->mont_data != NULL) {
160             /*
161              * We want inverse in constant time, therefore we utilize the fact
162              * order must be prime and use Fermats Little Theorem instead.
163              */
164             if (!BN_set_word(X, 2)) {
165                 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
166                 goto err;
167             }
168             if (!BN_mod_sub(X, order, X, order, ctx)) {
169                 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
170                 goto err;
171             }
172             BN_set_flags(X, BN_FLG_CONSTTIME);
173             if (!BN_mod_exp_mont_consttime(k, k, X, order, ctx,
174                                            group->mont_data)) {
175                 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
176                 goto err;
177             }
178         } else {
179             if (!BN_mod_inverse(k, k, order, ctx)) {
180                 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
181                 goto err;
182             }
183         }
184     }
185
186     /* clear old values if necessary */
187     BN_clear_free(*rp);
188     BN_clear_free(*kinvp);
189     /* save the pre-computed values  */
190     *rp = r;
191     *kinvp = k;
192     ret = 1;
193  err:
194     if (!ret) {
195         BN_clear_free(k);
196         BN_clear_free(r);
197     }
198     if (ctx != ctx_in)
199         BN_CTX_free(ctx);
200     EC_POINT_free(tmp_point);
201     BN_clear_free(X);
202     return ret;
203 }
204
205 int ossl_ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
206                           BIGNUM **rp)
207 {
208     return ecdsa_sign_setup(eckey, ctx_in, kinvp, rp, NULL, 0);
209 }
210
211 ECDSA_SIG *ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len,
212                                const BIGNUM *in_kinv, const BIGNUM *in_r,
213                                EC_KEY *eckey)
214 {
215     int ok = 0, i;
216     BIGNUM *kinv = NULL, *s, *m = NULL, *tmp = NULL;
217     const BIGNUM *order, *ckinv;
218     BN_CTX *ctx = NULL;
219     const EC_GROUP *group;
220     ECDSA_SIG *ret;
221     const BIGNUM *priv_key;
222
223     group = EC_KEY_get0_group(eckey);
224     priv_key = EC_KEY_get0_private_key(eckey);
225
226     if (group == NULL || priv_key == NULL) {
227         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_PASSED_NULL_PARAMETER);
228         return NULL;
229     }
230
231     if (!EC_KEY_can_sign(eckey)) {
232         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING);
233         return NULL;
234     }
235
236     ret = ECDSA_SIG_new();
237     if (ret == NULL) {
238         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE);
239         return NULL;
240     }
241     ret->r = BN_new();
242     ret->s = BN_new();
243     if (ret->r == NULL || ret->s == NULL) {
244         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE);
245         goto err;
246     }
247     s = ret->s;
248
249     if ((ctx = BN_CTX_new()) == NULL ||
250         (tmp = BN_new()) == NULL || (m = BN_new()) == NULL) {
251         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE);
252         goto err;
253     }
254
255     order = EC_GROUP_get0_order(group);
256     if (order == NULL) {
257         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_EC_LIB);
258         goto err;
259     }
260     i = BN_num_bits(order);
261     /*
262      * Need to truncate digest if it is too long: first truncate whole bytes.
263      */
264     if (8 * dgst_len > i)
265         dgst_len = (i + 7) / 8;
266     if (!BN_bin2bn(dgst, dgst_len, m)) {
267         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB);
268         goto err;
269     }
270     /* If still too long truncate remaining bits with a shift */
271     if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) {
272         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB);
273         goto err;
274     }
275     do {
276         if (in_kinv == NULL || in_r == NULL) {
277             if (!ecdsa_sign_setup(eckey, ctx, &kinv, &ret->r, dgst, dgst_len)) {
278                 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_ECDSA_LIB);
279                 goto err;
280             }
281             ckinv = kinv;
282         } else {
283             ckinv = in_kinv;
284             if (BN_copy(ret->r, in_r) == NULL) {
285                 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE);
286                 goto err;
287             }
288         }
289
290         if (!BN_mod_mul(tmp, priv_key, ret->r, order, ctx)) {
291             ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB);
292             goto err;
293         }
294         if (!BN_mod_add_quick(s, tmp, m, order)) {
295             ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB);
296             goto err;
297         }
298         if (!BN_mod_mul(s, s, ckinv, order, ctx)) {
299             ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB);
300             goto err;
301         }
302         if (BN_is_zero(s)) {
303             /*
304              * if kinv and r have been supplied by the caller, don't
305              * generate new kinv and r values
306              */
307             if (in_kinv != NULL && in_r != NULL) {
308                 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, EC_R_NEED_NEW_SETUP_VALUES);
309                 goto err;
310             }
311         } else
312             /* s != 0 => we have a valid signature */
313             break;
314     }
315     while (1);
316
317     ok = 1;
318  err:
319     if (!ok) {
320         ECDSA_SIG_free(ret);
321         ret = NULL;
322     }
323     BN_CTX_free(ctx);
324     BN_clear_free(m);
325     BN_clear_free(tmp);
326     BN_clear_free(kinv);
327     return ret;
328 }
329
330 /*-
331  * returns
332  *      1: correct signature
333  *      0: incorrect signature
334  *     -1: error
335  */
336 int ossl_ecdsa_verify(int type, const unsigned char *dgst, int dgst_len,
337                       const unsigned char *sigbuf, int sig_len, EC_KEY *eckey)
338 {
339     ECDSA_SIG *s;
340     const unsigned char *p = sigbuf;
341     unsigned char *der = NULL;
342     int derlen = -1;
343     int ret = -1;
344
345     s = ECDSA_SIG_new();
346     if (s == NULL)
347         return ret;
348     if (d2i_ECDSA_SIG(&s, &p, sig_len) == NULL)
349         goto err;
350     /* Ensure signature uses DER and doesn't have trailing garbage */
351     derlen = i2d_ECDSA_SIG(s, &der);
352     if (derlen != sig_len || memcmp(sigbuf, der, derlen) != 0)
353         goto err;
354     ret = ECDSA_do_verify(dgst, dgst_len, s, eckey);
355  err:
356     OPENSSL_clear_free(der, derlen);
357     ECDSA_SIG_free(s);
358     return ret;
359 }
360
361 int ossl_ecdsa_verify_sig(const unsigned char *dgst, int dgst_len,
362                           const ECDSA_SIG *sig, EC_KEY *eckey)
363 {
364     int ret = -1, i;
365     BN_CTX *ctx;
366     const BIGNUM *order;
367     BIGNUM *u1, *u2, *m, *X;
368     EC_POINT *point = NULL;
369     const EC_GROUP *group;
370     const EC_POINT *pub_key;
371
372     /* check input values */
373     if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL ||
374         (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) {
375         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, EC_R_MISSING_PARAMETERS);
376         return -1;
377     }
378
379     if (!EC_KEY_can_sign(eckey)) {
380         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING);
381         return -1;
382     }
383
384     ctx = BN_CTX_new();
385     if (ctx == NULL) {
386         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_MALLOC_FAILURE);
387         return -1;
388     }
389     BN_CTX_start(ctx);
390     u1 = BN_CTX_get(ctx);
391     u2 = BN_CTX_get(ctx);
392     m = BN_CTX_get(ctx);
393     X = BN_CTX_get(ctx);
394     if (X == NULL) {
395         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
396         goto err;
397     }
398
399     order = EC_GROUP_get0_order(group);
400     if (order == NULL) {
401         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_EC_LIB);
402         goto err;
403     }
404
405     if (BN_is_zero(sig->r) || BN_is_negative(sig->r) ||
406         BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) ||
407         BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) {
408         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, EC_R_BAD_SIGNATURE);
409         ret = 0;                /* signature is invalid */
410         goto err;
411     }
412     /* calculate tmp1 = inv(S) mod order */
413     /* Check if optimized inverse is implemented */
414     if (EC_GROUP_do_inverse_ord(group, u2, sig->s, ctx) == 0) {
415         if (!BN_mod_inverse(u2, sig->s, order, ctx)) {
416             ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
417             goto err;
418         }
419     }
420     /* digest -> m */
421     i = BN_num_bits(order);
422     /*
423      * Need to truncate digest if it is too long: first truncate whole bytes.
424      */
425     if (8 * dgst_len > i)
426         dgst_len = (i + 7) / 8;
427     if (!BN_bin2bn(dgst, dgst_len, m)) {
428         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
429         goto err;
430     }
431     /* If still too long truncate remaining bits with a shift */
432     if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) {
433         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
434         goto err;
435     }
436     /* u1 = m * tmp mod order */
437     if (!BN_mod_mul(u1, m, u2, order, ctx)) {
438         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
439         goto err;
440     }
441     /* u2 = r * w mod q */
442     if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) {
443         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
444         goto err;
445     }
446
447     if ((point = EC_POINT_new(group)) == NULL) {
448         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_MALLOC_FAILURE);
449         goto err;
450     }
451     if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) {
452         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_EC_LIB);
453         goto err;
454     }
455     if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) ==
456         NID_X9_62_prime_field) {
457         if (!EC_POINT_get_affine_coordinates_GFp(group, point, X, NULL, ctx)) {
458             ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_EC_LIB);
459             goto err;
460         }
461     }
462 #ifndef OPENSSL_NO_EC2M
463     else {                      /* NID_X9_62_characteristic_two_field */
464
465         if (!EC_POINT_get_affine_coordinates_GF2m(group, point, X, NULL, ctx)) {
466             ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_EC_LIB);
467             goto err;
468         }
469     }
470 #endif
471     if (!BN_nnmod(u1, X, order, ctx)) {
472         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
473         goto err;
474     }
475     /*  if the signature is correct u1 is equal to sig->r */
476     ret = (BN_ucmp(u1, sig->r) == 0);
477  err:
478     BN_CTX_end(ctx);
479     BN_CTX_free(ctx);
480     EC_POINT_free(point);
481     return ret;
482 }