• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /* ====================================================================
2  * Copyright (c) 1998-2005 The OpenSSL Project.  All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  *
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in
13  *    the documentation and/or other materials provided with the
14  *    distribution.
15  *
16  * 3. All advertising materials mentioning features or use of this
17  *    software must display the following acknowledgment:
18  *    "This product includes software developed by the OpenSSL Project
19  *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
20  *
21  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
22  *    endorse or promote products derived from this software without
23  *    prior written permission. For written permission, please contact
24  *    openssl-core@OpenSSL.org.
25  *
26  * 5. Products derived from this software may not be called "OpenSSL"
27  *    nor may "OpenSSL" appear in their names without prior written
28  *    permission of the OpenSSL Project.
29  *
30  * 6. Redistributions of any form whatsoever must retain the following
31  *    acknowledgment:
32  *    "This product includes software developed by the OpenSSL Project
33  *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
34  *
35  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
36  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
37  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
38  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
39  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
41  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
42  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
43  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
44  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
45  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
46  * OF THE POSSIBILITY OF SUCH DAMAGE.
47  * ====================================================================
48  *
49  * This product includes cryptographic software written by Eric Young
50  * (eay@cryptsoft.com).  This product includes software written by Tim
51  * Hudson (tjh@cryptsoft.com). */
52 
53 #include <openssl/ecdsa.h>
54 
55 #include <assert.h>
56 #include <string.h>
57 
58 #include <openssl/bn.h>
59 #include <openssl/err.h>
60 #include <openssl/mem.h>
61 #include <openssl/sha.h>
62 #include <openssl/type_check.h>
63 
64 #include "../bn/internal.h"
65 #include "../ec/internal.h"
66 #include "../../internal.h"
67 
68 
69 // digest_to_scalar interprets |digest_len| bytes from |digest| as a scalar for
70 // ECDSA. Note this value is not fully reduced modulo the order, only the
71 // correct number of bits.
digest_to_scalar(const EC_GROUP * group,EC_SCALAR * out,const uint8_t * digest,size_t digest_len)72 static void digest_to_scalar(const EC_GROUP *group, EC_SCALAR *out,
73                              const uint8_t *digest, size_t digest_len) {
74   const BIGNUM *order = &group->order;
75   size_t num_bits = BN_num_bits(order);
76   // Need to truncate digest if it is too long: first truncate whole bytes.
77   size_t num_bytes = (num_bits + 7) / 8;
78   if (digest_len > num_bytes) {
79     digest_len = num_bytes;
80   }
81   OPENSSL_memset(out, 0, sizeof(EC_SCALAR));
82   for (size_t i = 0; i < digest_len; i++) {
83     out->bytes[i] = digest[digest_len - 1 - i];
84   }
85 
86   // If it is still too long, truncate remaining bits with a shift.
87   if (8 * digest_len > num_bits) {
88     bn_rshift_words(out->words, out->words, 8 - (num_bits & 0x7), order->width);
89   }
90 
91   // |out| now has the same bit width as |order|, but this only bounds by
92   // 2*|order|. Subtract the order if out of range.
93   //
94   // Montgomery multiplication accepts the looser bounds, so this isn't strictly
95   // necessary, but it is a cleaner abstraction and has no performance impact.
96   BN_ULONG tmp[EC_MAX_WORDS];
97   bn_reduce_once_in_place(out->words, 0 /* no carry */, order->d, tmp,
98                           order->width);
99 }
100 
ECDSA_SIG_new(void)101 ECDSA_SIG *ECDSA_SIG_new(void) {
102   ECDSA_SIG *sig = OPENSSL_malloc(sizeof(ECDSA_SIG));
103   if (sig == NULL) {
104     return NULL;
105   }
106   sig->r = BN_new();
107   sig->s = BN_new();
108   if (sig->r == NULL || sig->s == NULL) {
109     ECDSA_SIG_free(sig);
110     return NULL;
111   }
112   return sig;
113 }
114 
ECDSA_SIG_free(ECDSA_SIG * sig)115 void ECDSA_SIG_free(ECDSA_SIG *sig) {
116   if (sig == NULL) {
117     return;
118   }
119 
120   BN_free(sig->r);
121   BN_free(sig->s);
122   OPENSSL_free(sig);
123 }
124 
ECDSA_SIG_get0(const ECDSA_SIG * sig,const BIGNUM ** out_r,const BIGNUM ** out_s)125 void ECDSA_SIG_get0(const ECDSA_SIG *sig, const BIGNUM **out_r,
126                     const BIGNUM **out_s) {
127   if (out_r != NULL) {
128     *out_r = sig->r;
129   }
130   if (out_s != NULL) {
131     *out_s = sig->s;
132   }
133 }
134 
ECDSA_SIG_set0(ECDSA_SIG * sig,BIGNUM * r,BIGNUM * s)135 int ECDSA_SIG_set0(ECDSA_SIG *sig, BIGNUM *r, BIGNUM *s) {
136   if (r == NULL || s == NULL) {
137     return 0;
138   }
139   BN_free(sig->r);
140   BN_free(sig->s);
141   sig->r = r;
142   sig->s = s;
143   return 1;
144 }
145 
ECDSA_do_verify(const uint8_t * digest,size_t digest_len,const ECDSA_SIG * sig,const EC_KEY * eckey)146 int ECDSA_do_verify(const uint8_t *digest, size_t digest_len,
147                     const ECDSA_SIG *sig, const EC_KEY *eckey) {
148   const EC_GROUP *group = EC_KEY_get0_group(eckey);
149   const EC_POINT *pub_key = EC_KEY_get0_public_key(eckey);
150   if (group == NULL || pub_key == NULL || sig == NULL) {
151     OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_MISSING_PARAMETERS);
152     return 0;
153   }
154 
155   EC_SCALAR r, s, u1, u2, s_inv_mont, m;
156   if (BN_is_zero(sig->r) ||
157       !ec_bignum_to_scalar(group, &r, sig->r) ||
158       BN_is_zero(sig->s) ||
159       !ec_bignum_to_scalar(group, &s, sig->s)) {
160     OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_BAD_SIGNATURE);
161     return 0;
162   }
163 
164   // s_inv_mont = s^-1 in the Montgomery domain. This is
165   ec_scalar_inv_montgomery_vartime(group, &s_inv_mont, &s);
166 
167   // u1 = m * s^-1 mod order
168   // u2 = r * s^-1 mod order
169   //
170   // |s_inv_mont| is in Montgomery form while |m| and |r| are not, so |u1| and
171   // |u2| will be taken out of Montgomery form, as desired.
172   digest_to_scalar(group, &m, digest, digest_len);
173   ec_scalar_mul_montgomery(group, &u1, &m, &s_inv_mont);
174   ec_scalar_mul_montgomery(group, &u2, &r, &s_inv_mont);
175 
176   EC_RAW_POINT point;
177   if (!ec_point_mul_scalar_public(group, &point, &u1, &pub_key->raw, &u2)) {
178     OPENSSL_PUT_ERROR(ECDSA, ERR_R_EC_LIB);
179     return 0;
180   }
181 
182   if (!ec_cmp_x_coordinate(group, &point, &r)) {
183     OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_BAD_SIGNATURE);
184     return 0;
185   }
186 
187   return 1;
188 }
189 
ecdsa_sign_setup(const EC_KEY * eckey,EC_SCALAR * out_kinv_mont,EC_SCALAR * out_r,const uint8_t * digest,size_t digest_len,const EC_SCALAR * priv_key)190 static int ecdsa_sign_setup(const EC_KEY *eckey, EC_SCALAR *out_kinv_mont,
191                             EC_SCALAR *out_r, const uint8_t *digest,
192                             size_t digest_len, const EC_SCALAR *priv_key) {
193   // Check that the size of the group order is FIPS compliant (FIPS 186-4
194   // B.5.2).
195   const EC_GROUP *group = EC_KEY_get0_group(eckey);
196   const BIGNUM *order = EC_GROUP_get0_order(group);
197   if (BN_num_bits(order) < 160) {
198     OPENSSL_PUT_ERROR(ECDSA, EC_R_INVALID_GROUP_ORDER);
199     return 0;
200   }
201 
202   int ret = 0;
203   EC_SCALAR k;
204   EC_RAW_POINT tmp_point;
205   do {
206     // Include the private key and message digest in the k generation.
207     if (eckey->fixed_k != NULL) {
208       if (!ec_bignum_to_scalar(group, &k, eckey->fixed_k)) {
209         goto err;
210       }
211     } else {
212       // Pass a SHA512 hash of the private key and digest as additional data
213       // into the RBG. This is a hardening measure against entropy failure.
214       OPENSSL_STATIC_ASSERT(SHA512_DIGEST_LENGTH >= 32,
215                             "additional_data is too large for SHA-512");
216       SHA512_CTX sha;
217       uint8_t additional_data[SHA512_DIGEST_LENGTH];
218       SHA512_Init(&sha);
219       SHA512_Update(&sha, priv_key->words, order->width * sizeof(BN_ULONG));
220       SHA512_Update(&sha, digest, digest_len);
221       SHA512_Final(additional_data, &sha);
222       if (!ec_random_nonzero_scalar(group, &k, additional_data)) {
223         goto err;
224       }
225     }
226 
227     // Compute k^-1 in the Montgomery domain. This is |ec_scalar_to_montgomery|
228     // followed by |ec_scalar_inv_montgomery|, but |ec_scalar_inv_montgomery|
229     // followed by |ec_scalar_from_montgomery| is equivalent and slightly more
230     // efficient.
231     ec_scalar_inv_montgomery(group, out_kinv_mont, &k);
232     ec_scalar_from_montgomery(group, out_kinv_mont, out_kinv_mont);
233 
234     // Compute r, the x-coordinate of generator * k.
235     if (!ec_point_mul_scalar(group, &tmp_point, &k, NULL, NULL) ||
236         !ec_get_x_coordinate_as_scalar(group, out_r, &tmp_point)) {
237       goto err;
238     }
239   } while (ec_scalar_is_zero(group, out_r));
240 
241   ret = 1;
242 
243 err:
244   OPENSSL_cleanse(&k, sizeof(k));
245   return ret;
246 }
247 
ECDSA_do_sign(const uint8_t * digest,size_t digest_len,const EC_KEY * eckey)248 ECDSA_SIG *ECDSA_do_sign(const uint8_t *digest, size_t digest_len,
249                          const EC_KEY *eckey) {
250   if (eckey->ecdsa_meth && eckey->ecdsa_meth->sign) {
251     OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_NOT_IMPLEMENTED);
252     return NULL;
253   }
254 
255   const EC_GROUP *group = EC_KEY_get0_group(eckey);
256   if (group == NULL || eckey->priv_key == NULL) {
257     OPENSSL_PUT_ERROR(ECDSA, ERR_R_PASSED_NULL_PARAMETER);
258     return NULL;
259   }
260   const BIGNUM *order = EC_GROUP_get0_order(group);
261   const EC_SCALAR *priv_key = &eckey->priv_key->scalar;
262 
263   int ok = 0;
264   ECDSA_SIG *ret = ECDSA_SIG_new();
265   EC_SCALAR kinv_mont, r_mont, s, m, tmp;
266   if (ret == NULL) {
267     OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE);
268     return NULL;
269   }
270 
271   digest_to_scalar(group, &m, digest, digest_len);
272   for (;;) {
273     if (!ecdsa_sign_setup(eckey, &kinv_mont, &r_mont, digest, digest_len,
274                           priv_key) ||
275         !bn_set_words(ret->r, r_mont.words, order->width)) {
276       goto err;
277     }
278 
279     // Compute priv_key * r (mod order). Note if only one parameter is in the
280     // Montgomery domain, |ec_scalar_mod_mul_montgomery| will compute the answer
281     // in the normal domain.
282     ec_scalar_to_montgomery(group, &r_mont, &r_mont);
283     ec_scalar_mul_montgomery(group, &s, priv_key, &r_mont);
284 
285     // Compute tmp = m + priv_key * r.
286     ec_scalar_add(group, &tmp, &m, &s);
287 
288     // Finally, multiply s by k^-1. That was retained in Montgomery form, so the
289     // same technique as the previous multiplication works.
290     ec_scalar_mul_montgomery(group, &s, &tmp, &kinv_mont);
291     if (!bn_set_words(ret->s, s.words, order->width)) {
292       goto err;
293     }
294     if (!BN_is_zero(ret->s)) {
295       // s != 0 => we have a valid signature
296       break;
297     }
298   }
299 
300   ok = 1;
301 
302 err:
303   if (!ok) {
304     ECDSA_SIG_free(ret);
305     ret = NULL;
306   }
307   OPENSSL_cleanse(&kinv_mont, sizeof(kinv_mont));
308   OPENSSL_cleanse(&r_mont, sizeof(r_mont));
309   OPENSSL_cleanse(&s, sizeof(s));
310   OPENSSL_cleanse(&tmp, sizeof(tmp));
311   OPENSSL_cleanse(&m, sizeof(m));
312   return ret;
313 }
314