/src/boringssl/crypto/fipsmodule/ecdsa/ecdsa.c.inc
Line | Count | Source (jump to first uncovered line) |
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 | | |
62 | | #include "../../internal.h" |
63 | | #include "../bn/internal.h" |
64 | | #include "../ec/internal.h" |
65 | | #include "../service_indicator/internal.h" |
66 | | #include "internal.h" |
67 | | |
68 | | |
69 | | // digest_to_scalar interprets |digest_len| bytes from |digest| as a scalar for |
70 | | // ECDSA. |
71 | | static void digest_to_scalar(const EC_GROUP *group, EC_SCALAR *out, |
72 | 13 | const uint8_t *digest, size_t digest_len) { |
73 | 13 | const BIGNUM *order = EC_GROUP_get0_order(group); |
74 | 13 | size_t num_bits = BN_num_bits(order); |
75 | | // Need to truncate digest if it is too long: first truncate whole bytes. |
76 | 13 | size_t num_bytes = (num_bits + 7) / 8; |
77 | 13 | if (digest_len > num_bytes) { |
78 | 2 | digest_len = num_bytes; |
79 | 2 | } |
80 | 13 | bn_big_endian_to_words(out->words, order->width, digest, digest_len); |
81 | | |
82 | | // If it is still too long, truncate remaining bits with a shift. |
83 | 13 | if (8 * digest_len > num_bits) { |
84 | 2 | bn_rshift_words(out->words, out->words, 8 - (num_bits & 0x7), order->width); |
85 | 2 | } |
86 | | |
87 | | // |out| now has the same bit width as |order|, but this only bounds by |
88 | | // 2*|order|. Subtract the order if out of range. |
89 | | // |
90 | | // Montgomery multiplication accepts the looser bounds, so this isn't strictly |
91 | | // necessary, but it is a cleaner abstraction and has no performance impact. |
92 | 13 | BN_ULONG tmp[EC_MAX_WORDS]; |
93 | 13 | bn_reduce_once_in_place(out->words, 0 /* no carry */, order->d, tmp, |
94 | 13 | order->width); |
95 | 13 | } |
96 | | |
97 | | int ecdsa_verify_fixed_no_self_test(const uint8_t *digest, size_t digest_len, |
98 | | const uint8_t *sig, size_t sig_len, |
99 | 13 | const EC_KEY *eckey) { |
100 | 13 | const EC_GROUP *group = EC_KEY_get0_group(eckey); |
101 | 13 | const EC_POINT *pub_key = EC_KEY_get0_public_key(eckey); |
102 | 13 | if (group == NULL || pub_key == NULL || sig == NULL) { |
103 | 0 | OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_MISSING_PARAMETERS); |
104 | 0 | return 0; |
105 | 0 | } |
106 | | |
107 | 13 | size_t scalar_len = BN_num_bytes(EC_GROUP_get0_order(group)); |
108 | 13 | EC_SCALAR r, s, u1, u2, s_inv_mont, m; |
109 | 13 | if (sig_len != 2 * scalar_len || |
110 | 13 | !ec_scalar_from_bytes(group, &r, sig, scalar_len) || |
111 | 13 | ec_scalar_is_zero(group, &r) || |
112 | 13 | !ec_scalar_from_bytes(group, &s, sig + scalar_len, scalar_len) || |
113 | 13 | ec_scalar_is_zero(group, &s)) { |
114 | 0 | OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_BAD_SIGNATURE); |
115 | 0 | return 0; |
116 | 0 | } |
117 | | |
118 | | // s_inv_mont = s^-1 in the Montgomery domain. |
119 | 13 | if (!ec_scalar_to_montgomery_inv_vartime(group, &s_inv_mont, &s)) { |
120 | 0 | OPENSSL_PUT_ERROR(ECDSA, ERR_R_INTERNAL_ERROR); |
121 | 0 | return 0; |
122 | 0 | } |
123 | | |
124 | | // u1 = m * s^-1 mod order |
125 | | // u2 = r * s^-1 mod order |
126 | | // |
127 | | // |s_inv_mont| is in Montgomery form while |m| and |r| are not, so |u1| and |
128 | | // |u2| will be taken out of Montgomery form, as desired. |
129 | 13 | digest_to_scalar(group, &m, digest, digest_len); |
130 | 13 | ec_scalar_mul_montgomery(group, &u1, &m, &s_inv_mont); |
131 | 13 | ec_scalar_mul_montgomery(group, &u2, &r, &s_inv_mont); |
132 | | |
133 | 13 | EC_JACOBIAN point; |
134 | 13 | if (!ec_point_mul_scalar_public(group, &point, &u1, &pub_key->raw, &u2)) { |
135 | 0 | OPENSSL_PUT_ERROR(ECDSA, ERR_R_EC_LIB); |
136 | 0 | return 0; |
137 | 0 | } |
138 | | |
139 | 13 | if (!ec_cmp_x_coordinate(group, &point, &r)) { |
140 | 10 | OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_BAD_SIGNATURE); |
141 | 10 | return 0; |
142 | 10 | } |
143 | | |
144 | 3 | return 1; |
145 | 13 | } |
146 | | |
147 | | int ecdsa_verify_fixed(const uint8_t *digest, size_t digest_len, |
148 | 13 | const uint8_t *sig, size_t sig_len, const EC_KEY *key) { |
149 | 13 | boringssl_ensure_ecc_self_test(); |
150 | | |
151 | 13 | return ecdsa_verify_fixed_no_self_test(digest, digest_len, sig, sig_len, key); |
152 | 13 | } |
153 | | |
154 | | static int ecdsa_sign_impl(const EC_GROUP *group, int *out_retry, uint8_t *sig, |
155 | | size_t *out_sig_len, size_t max_sig_len, |
156 | | const EC_SCALAR *priv_key, const EC_SCALAR *k, |
157 | 0 | const uint8_t *digest, size_t digest_len) { |
158 | 0 | *out_retry = 0; |
159 | | |
160 | | // Check that the size of the group order is FIPS compliant (FIPS 186-4 |
161 | | // B.5.2). |
162 | 0 | const BIGNUM *order = EC_GROUP_get0_order(group); |
163 | 0 | if (BN_num_bits(order) < 160) { |
164 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_INVALID_GROUP_ORDER); |
165 | 0 | return 0; |
166 | 0 | } |
167 | | |
168 | 0 | size_t sig_len = 2 * BN_num_bytes(order); |
169 | 0 | if (sig_len > max_sig_len) { |
170 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_BUFFER_TOO_SMALL); |
171 | 0 | return 0; |
172 | 0 | } |
173 | | |
174 | | // Compute r, the x-coordinate of k * generator. |
175 | 0 | EC_JACOBIAN tmp_point; |
176 | 0 | EC_SCALAR r; |
177 | 0 | if (!ec_point_mul_scalar_base(group, &tmp_point, k) || |
178 | 0 | !ec_get_x_coordinate_as_scalar(group, &r, &tmp_point)) { |
179 | 0 | return 0; |
180 | 0 | } |
181 | | |
182 | 0 | if (constant_time_declassify_int(ec_scalar_is_zero(group, &r))) { |
183 | 0 | *out_retry = 1; |
184 | 0 | return 0; |
185 | 0 | } |
186 | | |
187 | | // s = priv_key * r. Note if only one parameter is in the Montgomery domain, |
188 | | // |ec_scalar_mod_mul_montgomery| will compute the answer in the normal |
189 | | // domain. |
190 | 0 | EC_SCALAR s; |
191 | 0 | ec_scalar_to_montgomery(group, &s, &r); |
192 | 0 | ec_scalar_mul_montgomery(group, &s, priv_key, &s); |
193 | | |
194 | | // s = m + priv_key * r. |
195 | 0 | EC_SCALAR tmp; |
196 | 0 | digest_to_scalar(group, &tmp, digest, digest_len); |
197 | 0 | ec_scalar_add(group, &s, &s, &tmp); |
198 | | |
199 | | // s = k^-1 * (m + priv_key * r). First, we compute k^-1 in the Montgomery |
200 | | // domain. This is |ec_scalar_to_montgomery| followed by |
201 | | // |ec_scalar_inv0_montgomery|, but |ec_scalar_inv0_montgomery| followed by |
202 | | // |ec_scalar_from_montgomery| is equivalent and slightly more efficient. |
203 | | // Then, as above, only one parameter is in the Montgomery domain, so the |
204 | | // result is in the normal domain. Finally, note k is non-zero (or computing r |
205 | | // would fail), so the inverse must exist. |
206 | 0 | ec_scalar_inv0_montgomery(group, &tmp, k); // tmp = k^-1 R^2 |
207 | 0 | ec_scalar_from_montgomery(group, &tmp, &tmp); // tmp = k^-1 R |
208 | 0 | ec_scalar_mul_montgomery(group, &s, &s, &tmp); |
209 | 0 | if (constant_time_declassify_int(ec_scalar_is_zero(group, &s))) { |
210 | 0 | *out_retry = 1; |
211 | 0 | return 0; |
212 | 0 | } |
213 | | |
214 | 0 | CONSTTIME_DECLASSIFY(r.words, sizeof(r.words)); |
215 | 0 | CONSTTIME_DECLASSIFY(s.words, sizeof(r.words)); |
216 | 0 | size_t len; |
217 | 0 | ec_scalar_to_bytes(group, sig, &len, &r); |
218 | 0 | assert(len == sig_len / 2); |
219 | 0 | ec_scalar_to_bytes(group, sig + len, &len, &s); |
220 | 0 | assert(len == sig_len / 2); |
221 | 0 | *out_sig_len = sig_len; |
222 | 0 | return 1; |
223 | 0 | } |
224 | | |
225 | | int ecdsa_sign_fixed_with_nonce_for_known_answer_test( |
226 | | const uint8_t *digest, size_t digest_len, uint8_t *sig, size_t *out_sig_len, |
227 | | size_t max_sig_len, const EC_KEY *eckey, const uint8_t *nonce, |
228 | 0 | size_t nonce_len) { |
229 | 0 | if (eckey->ecdsa_meth && eckey->ecdsa_meth->sign) { |
230 | 0 | OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_NOT_IMPLEMENTED); |
231 | 0 | return 0; |
232 | 0 | } |
233 | | |
234 | 0 | const EC_GROUP *group = EC_KEY_get0_group(eckey); |
235 | 0 | if (group == NULL || eckey->priv_key == NULL) { |
236 | 0 | OPENSSL_PUT_ERROR(ECDSA, ERR_R_PASSED_NULL_PARAMETER); |
237 | 0 | return 0; |
238 | 0 | } |
239 | 0 | const EC_SCALAR *priv_key = &eckey->priv_key->scalar; |
240 | |
|
241 | 0 | EC_SCALAR k; |
242 | 0 | if (!ec_scalar_from_bytes(group, &k, nonce, nonce_len)) { |
243 | 0 | return 0; |
244 | 0 | } |
245 | 0 | int retry_ignored; |
246 | 0 | return ecdsa_sign_impl(group, &retry_ignored, sig, out_sig_len, max_sig_len, |
247 | 0 | priv_key, &k, digest, digest_len); |
248 | 0 | } |
249 | | |
250 | | int ecdsa_sign_fixed(const uint8_t *digest, size_t digest_len, uint8_t *sig, |
251 | | size_t *out_sig_len, size_t max_sig_len, |
252 | 0 | const EC_KEY *eckey) { |
253 | 0 | boringssl_ensure_ecc_self_test(); |
254 | |
|
255 | 0 | if (eckey->ecdsa_meth && eckey->ecdsa_meth->sign) { |
256 | 0 | OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_NOT_IMPLEMENTED); |
257 | 0 | return 0; |
258 | 0 | } |
259 | | |
260 | 0 | const EC_GROUP *group = EC_KEY_get0_group(eckey); |
261 | 0 | if (group == NULL || eckey->priv_key == NULL) { |
262 | 0 | OPENSSL_PUT_ERROR(ECDSA, ERR_R_PASSED_NULL_PARAMETER); |
263 | 0 | return 0; |
264 | 0 | } |
265 | 0 | const BIGNUM *order = EC_GROUP_get0_order(group); |
266 | 0 | const EC_SCALAR *priv_key = &eckey->priv_key->scalar; |
267 | | |
268 | | // Pass a SHA512 hash of the private key and digest as additional data |
269 | | // into the RBG. This is a hardening measure against entropy failure. |
270 | 0 | static_assert(BCM_SHA512_DIGEST_LENGTH >= 32, |
271 | 0 | "additional_data is too large for SHA-512"); |
272 | |
|
273 | 0 | FIPS_service_indicator_lock_state(); |
274 | |
|
275 | 0 | SHA512_CTX sha; |
276 | 0 | uint8_t additional_data[BCM_SHA512_DIGEST_LENGTH]; |
277 | 0 | BCM_sha512_init(&sha); |
278 | 0 | BCM_sha512_update(&sha, priv_key->words, order->width * sizeof(BN_ULONG)); |
279 | 0 | BCM_sha512_update(&sha, digest, digest_len); |
280 | 0 | BCM_sha512_final(additional_data, &sha); |
281 | | |
282 | | // Cap iterations so callers who supply invalid values as custom groups do not |
283 | | // infinite loop. This does not impact valid parameters (e.g. those covered by |
284 | | // FIPS) because the probability of requiring even one retry is negligible, |
285 | | // let alone 32. |
286 | 0 | static const int kMaxIterations = 32; |
287 | 0 | int ret = 0; |
288 | 0 | int iters = 0; |
289 | 0 | for (;;) { |
290 | 0 | EC_SCALAR k; |
291 | 0 | if (!ec_random_nonzero_scalar(group, &k, additional_data)) { |
292 | 0 | goto out; |
293 | 0 | } |
294 | | |
295 | | // TODO(davidben): Move this inside |ec_random_nonzero_scalar| or lower, so |
296 | | // that all scalars we generate are, by default, secret. |
297 | 0 | CONSTTIME_SECRET(k.words, sizeof(k.words)); |
298 | |
|
299 | 0 | int retry; |
300 | 0 | ret = ecdsa_sign_impl(group, &retry, sig, out_sig_len, max_sig_len, |
301 | 0 | priv_key, &k, digest, digest_len); |
302 | 0 | if (ret || !retry) { |
303 | 0 | goto out; |
304 | 0 | } |
305 | | |
306 | 0 | iters++; |
307 | 0 | if (iters > kMaxIterations) { |
308 | 0 | OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_TOO_MANY_ITERATIONS); |
309 | 0 | goto out; |
310 | 0 | } |
311 | 0 | } |
312 | | |
313 | 0 | out: |
314 | 0 | FIPS_service_indicator_unlock_state(); |
315 | 0 | return ret; |
316 | 0 | } |