Add secure DSA nonce flag.
[openssl.git] / crypto / ecdsa / ecs_ossl.c
1 /* crypto/ecdsa/ecs_ossl.c */
2 /*
3  * Written by Nils Larsch for the OpenSSL project
4  */
5 /* ====================================================================
6  * Copyright (c) 1998-2004 The OpenSSL Project.  All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  *    notice, this list of conditions and the following disclaimer. 
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in
17  *    the documentation and/or other materials provided with the
18  *    distribution.
19  *
20  * 3. All advertising materials mentioning features or use of this
21  *    software must display the following acknowledgment:
22  *    "This product includes software developed by the OpenSSL Project
23  *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
24  *
25  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
26  *    endorse or promote products derived from this software without
27  *    prior written permission. For written permission, please contact
28  *    openssl-core@OpenSSL.org.
29  *
30  * 5. Products derived from this software may not be called "OpenSSL"
31  *    nor may "OpenSSL" appear in their names without prior written
32  *    permission of the OpenSSL Project.
33  *
34  * 6. Redistributions of any form whatsoever must retain the following
35  *    acknowledgment:
36  *    "This product includes software developed by the OpenSSL Project
37  *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
38  *
39  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
40  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
41  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
42  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
43  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
45  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
46  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
48  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
49  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
50  * OF THE POSSIBILITY OF SUCH DAMAGE.
51  * ====================================================================
52  *
53  * This product includes cryptographic software written by Eric Young
54  * (eay@cryptsoft.com).  This product includes software written by Tim
55  * Hudson (tjh@cryptsoft.com).
56  *
57  */
58
59 #define OPENSSL_FIPSAPI
60
61 #include "ecs_locl.h"
62 #include <openssl/err.h>
63 #include <openssl/obj_mac.h>
64 #include <openssl/bn.h>
65 #include <openssl/rand.h>
66
67 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen, 
68                 const BIGNUM *, const BIGNUM *, EC_KEY *eckey);
69 static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in,
70                             BIGNUM **kinvp, BIGNUM **rp,
71                             const unsigned char *dgst, int dlen);
72 static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, 
73                 const ECDSA_SIG *sig, EC_KEY *eckey);
74
75 static ECDSA_METHOD openssl_ecdsa_meth = {
76         "OpenSSL ECDSA method",
77         ecdsa_do_sign,
78         ecdsa_sign_setup,
79         ecdsa_do_verify,
80 #if 0
81         NULL, /* init     */
82         NULL, /* finish   */
83 #endif
84         ECDSA_FLAG_FIPS_METHOD,    /* flags    */
85         NULL  /* app_data */
86 };
87
88 const ECDSA_METHOD *ECDSA_OpenSSL(void)
89 {
90         return &openssl_ecdsa_meth;
91 }
92
93 static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in,
94                             BIGNUM **kinvp, BIGNUM **rp,
95                             const unsigned char *dgst, int dlen)
96 {
97         BN_CTX   *ctx = NULL;
98         BIGNUM   *k = NULL, *r = NULL, *order = NULL, *X = NULL;
99         EC_POINT *tmp_point=NULL;
100         const EC_GROUP *group;
101         int      ret = 0;
102
103         if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL)
104         {
105                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_PASSED_NULL_PARAMETER);
106                 return 0;
107         }
108
109         if (ctx_in == NULL) 
110         {
111                 if ((ctx = BN_CTX_new()) == NULL)
112                 {
113                         ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_MALLOC_FAILURE);
114                         return 0;
115                 }
116         }
117         else
118                 ctx = ctx_in;
119
120         k     = BN_new();       /* this value is later returned in *kinvp */
121         r     = BN_new();       /* this value is later returned in *rp    */
122         order = BN_new();
123         X     = BN_new();
124         if (!k || !r || !order || !X)
125         {
126                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE);
127                 goto err;
128         }
129         if ((tmp_point = EC_POINT_new(group)) == NULL)
130         {
131                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
132                 goto err;
133         }
134         if (!EC_GROUP_get_order(group, order, ctx))
135         {
136                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
137                 goto err;
138         }
139
140 #ifdef OPENSSL_FIPS
141         if (!fips_check_ec_prng(eckey))
142                 goto err;
143 #endif
144         
145         do
146         {
147                 /* get random k */      
148                 do
149 #ifndef OPENSSL_NO_SHA512
150                         if (EC_KEY_get_nonce_from_hash(eckey))
151                         {
152                                 if (!BN_generate_dsa_nonce(k, order, EC_KEY_get0_private_key(eckey),
153                                                            dgst, dlen, ctx))
154                                         {
155                                         ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
156                                                  ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);
157                                         goto err;
158                                         }
159                         }
160                         else
161 #endif
162                         {
163                                 if (!BN_rand_range(k, order))
164                                 {
165                                         ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
166                                                  ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);
167                                         goto err;
168                                 }
169                         }
170                 while (BN_is_zero(k));
171
172                 /* We do not want timing information to leak the length of k,
173                  * so we compute G*k using an equivalent scalar of fixed
174                  * bit-length. */
175
176                 if (!BN_add(k, k, order)) goto err;
177                 if (BN_num_bits(k) <= BN_num_bits(order))
178                         if (!BN_add(k, k, order)) goto err;
179
180                 /* compute r the x-coordinate of generator * k */
181                 if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx))
182                 {
183                         ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
184                         goto err;
185                 }
186                 if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == NID_X9_62_prime_field)
187                 {
188                         if (!EC_POINT_get_affine_coordinates_GFp(group,
189                                 tmp_point, X, NULL, ctx))
190                         {
191                                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_EC_LIB);
192                                 goto err;
193                         }
194                 }
195 #ifndef OPENSSL_NO_EC2M
196                 else /* NID_X9_62_characteristic_two_field */
197                 {
198                         if (!EC_POINT_get_affine_coordinates_GF2m(group,
199                                 tmp_point, X, NULL, ctx))
200                         {
201                                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_EC_LIB);
202                                 goto err;
203                         }
204                 }
205 #endif
206                 if (!BN_nnmod(r, X, order, ctx))
207                 {
208                         ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
209                         goto err;
210                 }
211         }
212         while (BN_is_zero(r));
213
214         /* compute the inverse of k */
215         if (!BN_mod_inverse(k, k, order, ctx))
216         {
217                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
218                 goto err;       
219         }
220         /* clear old values if necessary */
221         if (*rp != NULL)
222                 BN_clear_free(*rp);
223         if (*kinvp != NULL) 
224                 BN_clear_free(*kinvp);
225         /* save the pre-computed values  */
226         *rp    = r;
227         *kinvp = k;
228         ret = 1;
229 err:
230         if (!ret)
231         {
232                 if (k != NULL) BN_clear_free(k);
233                 if (r != NULL) BN_clear_free(r);
234         }
235         if (ctx_in == NULL) 
236                 BN_CTX_free(ctx);
237         if (order != NULL)
238                 BN_free(order);
239         if (tmp_point != NULL) 
240                 EC_POINT_free(tmp_point);
241         if (X)
242                 BN_clear_free(X);
243         return(ret);
244 }
245
246
247 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dgst_len, 
248                 const BIGNUM *in_kinv, const BIGNUM *in_r, EC_KEY *eckey)
249 {
250         int     ok = 0, i;
251         BIGNUM *kinv=NULL, *s, *m=NULL,*tmp=NULL,*order=NULL;
252         const BIGNUM *ckinv;
253         BN_CTX     *ctx = NULL;
254         const EC_GROUP   *group;
255         ECDSA_SIG  *ret;
256         ECDSA_DATA *ecdsa;
257         const BIGNUM *priv_key;
258
259 #ifdef OPENSSL_FIPS
260         if(FIPS_selftest_failed())
261                 {
262                 FIPSerr(FIPS_F_ECDSA_DO_SIGN,FIPS_R_FIPS_SELFTEST_FAILED);
263                 return NULL;
264                 }
265 #endif
266
267         ecdsa    = ecdsa_check(eckey);
268         group    = EC_KEY_get0_group(eckey);
269         priv_key = EC_KEY_get0_private_key(eckey);
270         
271         if (group == NULL || priv_key == NULL || ecdsa == NULL)
272         {
273                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_PASSED_NULL_PARAMETER);
274                 return NULL;
275         }
276
277 #ifdef OPENSSL_FIPS
278         if (!fips_check_ec_prng(eckey))
279                 return NULL;
280 #endif
281
282         ret = ECDSA_SIG_new();
283         if (!ret)
284         {
285                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE);
286                 return NULL;
287         }
288         s = ret->s;
289
290         if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL ||
291                 (tmp = BN_new()) == NULL || (m = BN_new()) == NULL)
292         {
293                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE);
294                 goto err;
295         }
296
297         if (!EC_GROUP_get_order(group, order, ctx))
298         {
299                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_EC_LIB);
300                 goto err;
301         }
302         i = BN_num_bits(order);
303         /* Need to truncate digest if it is too long: first truncate whole
304          * bytes.
305          */
306         if (8 * dgst_len > i)
307                 dgst_len = (i + 7)/8;
308         if (!BN_bin2bn(dgst, dgst_len, m))
309         {
310                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
311                 goto err;
312         }
313         /* If still too long truncate remaining bits with a shift */
314         if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7)))
315         {
316                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
317                 goto err;
318         }
319         do
320         {
321                 if (in_kinv == NULL || in_r == NULL)
322                 {
323                         if (!ecdsa->meth->ecdsa_sign_setup(eckey, ctx, &kinv, &ret->r, dgst, dgst_len))
324                         {
325                                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN,ERR_R_ECDSA_LIB);
326                                 goto err;
327                         }
328                         ckinv = kinv;
329                 }
330                 else
331                 {
332                         ckinv  = in_kinv;
333                         if (BN_copy(ret->r, in_r) == NULL)
334                         {
335                                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE);
336                                 goto err;
337                         }
338                 }
339
340                 if (!BN_mod_mul(tmp, priv_key, ret->r, order, ctx))
341                 {
342                         ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
343                         goto err;
344                 }
345                 if (!BN_mod_add_quick(s, tmp, m, order))
346                 {
347                         ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
348                         goto err;
349                 }
350                 if (!BN_mod_mul(s, s, ckinv, order, ctx))
351                 {
352                         ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
353                         goto err;
354                 }
355                 if (BN_is_zero(s))
356                 {
357                         /* if kinv and r have been supplied by the caller
358                          * don't to generate new kinv and r values */
359                         if (in_kinv != NULL && in_r != NULL)
360                         {
361                                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ECDSA_R_NEED_NEW_SETUP_VALUES);
362                                 goto err;
363                         }
364                 }
365                 else
366                         /* s != 0 => we have a valid signature */
367                         break;
368         }
369         while (1);
370
371         ok = 1;
372 err:
373         if (!ok)
374         {
375                 ECDSA_SIG_free(ret);
376                 ret = NULL;
377         }
378         if (ctx)
379                 BN_CTX_free(ctx);
380         if (m)
381                 BN_clear_free(m);
382         if (tmp)
383                 BN_clear_free(tmp);
384         if (order)
385                 BN_free(order);
386         if (kinv)
387                 BN_clear_free(kinv);
388         return ret;
389 }
390
391 static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len,
392                 const ECDSA_SIG *sig, EC_KEY *eckey)
393 {
394         int ret = -1, i;
395         BN_CTX   *ctx;
396         BIGNUM   *order, *u1, *u2, *m, *X;
397         EC_POINT *point = NULL;
398         const EC_GROUP *group;
399         const EC_POINT *pub_key;
400
401 #ifdef OPENSSL_FIPS
402         if(FIPS_selftest_failed())
403                 {
404                 FIPSerr(FIPS_F_ECDSA_DO_VERIFY,FIPS_R_FIPS_SELFTEST_FAILED);
405                 return -1;
406                 }
407 #endif
408
409         /* check input values */
410         if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL ||
411             (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL)
412         {
413                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_MISSING_PARAMETERS);
414                 return -1;
415         }
416
417         ctx = BN_CTX_new();
418         if (!ctx)
419         {
420                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE);
421                 return -1;
422         }
423         BN_CTX_start(ctx);
424         order = BN_CTX_get(ctx);        
425         u1    = BN_CTX_get(ctx);
426         u2    = BN_CTX_get(ctx);
427         m     = BN_CTX_get(ctx);
428         X     = BN_CTX_get(ctx);
429         if (!X)
430         {
431                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
432                 goto err;
433         }
434         
435         if (!EC_GROUP_get_order(group, order, ctx))
436         {
437                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB);
438                 goto err;
439         }
440
441         if (BN_is_zero(sig->r)          || BN_is_negative(sig->r) || 
442             BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s)  ||
443             BN_is_negative(sig->s)      || BN_ucmp(sig->s, order) >= 0)
444         {
445                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_BAD_SIGNATURE);
446                 ret = 0;        /* signature is invalid */
447                 goto err;
448         }
449         /* calculate tmp1 = inv(S) mod order */
450         if (!BN_mod_inverse(u2, sig->s, order, ctx))
451         {
452                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
453                 goto err;
454         }
455         /* digest -> m */
456         i = BN_num_bits(order);
457         /* Need to truncate digest if it is too long: first truncate whole
458          * bytes.
459          */
460         if (8 * dgst_len > i)
461                 dgst_len = (i + 7)/8;
462         if (!BN_bin2bn(dgst, dgst_len, m))
463         {
464                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
465                 goto err;
466         }
467         /* If still too long truncate remaining bits with a shift */
468         if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7)))
469         {
470                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
471                 goto err;
472         }
473         /* u1 = m * tmp mod order */
474         if (!BN_mod_mul(u1, m, u2, order, ctx))
475         {
476                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
477                 goto err;
478         }
479         /* u2 = r * w mod q */
480         if (!BN_mod_mul(u2, sig->r, u2, order, ctx))
481         {
482                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
483                 goto err;
484         }
485
486         if ((point = EC_POINT_new(group)) == NULL)
487         {
488                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE);
489                 goto err;
490         }
491         if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx))
492         {
493                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB);
494                 goto err;
495         }
496         if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == NID_X9_62_prime_field)
497         {
498                 if (!EC_POINT_get_affine_coordinates_GFp(group,
499                         point, X, NULL, ctx))
500                 {
501                         ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB);
502                         goto err;
503                 }
504         }
505 #ifndef OPENSSL_NO_EC2M
506         else /* NID_X9_62_characteristic_two_field */
507         {
508                 if (!EC_POINT_get_affine_coordinates_GF2m(group,
509                         point, X, NULL, ctx))
510                 {
511                         ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB);
512                         goto err;
513                 }
514         }
515 #endif  
516         if (!BN_nnmod(u1, X, order, ctx))
517         {
518                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
519                 goto err;
520         }
521         /*  if the signature is correct u1 is equal to sig->r */
522         ret = (BN_ucmp(u1, sig->r) == 0);
523 err:
524         BN_CTX_end(ctx);
525         BN_CTX_free(ctx);
526         if (point)
527                 EC_POINT_free(point);
528         return ret;
529 }
530
531 #ifdef OPENSSL_FIPSCANISTER
532 /* FIPS stanadlone version of ecdsa_check: just return FIPS method */
533 ECDSA_DATA *fips_ecdsa_check(EC_KEY *key)
534         {
535         static ECDSA_DATA rv = {
536                 0,0,0,
537                 &openssl_ecdsa_meth
538                 };
539         return &rv;
540         }
541 /* Standalone digest sign and verify */
542 int FIPS_ecdsa_verify_digest(EC_KEY *key,
543                         const unsigned char *dig, int dlen, ECDSA_SIG *s)
544         {
545         ECDSA_DATA *ecdsa = ecdsa_check(key);
546         if (ecdsa == NULL)
547                 return 0;
548         return ecdsa->meth->ecdsa_do_verify(dig, dlen, s, key);
549         }
550 ECDSA_SIG * FIPS_ecdsa_sign_digest(EC_KEY *key,
551                                         const unsigned char *dig, int dlen)
552         {
553         ECDSA_DATA *ecdsa = ecdsa_check(key);
554         if (ecdsa == NULL)
555                 return NULL;
556         return ecdsa->meth->ecdsa_do_sign(dig, dlen, NULL, NULL, key);
557         }
558 #endif