1// Copyright 2015-2016 Brian Smith.
2//
3// Permission to use, copy, modify, and/or distribute this software for any
4// purpose with or without fee is hereby granted, provided that the above
5// copyright notice and this permission notice appear in all copies.
6//
7// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHORS DISCLAIM ALL WARRANTIES
8// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY
10// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
14
15//! ECDSA Signatures using the P-256 and P-384 curves.
16
17use super::digest_scalar::digest_scalar;
18use crate::{
19 arithmetic::montgomery::*,
20 cpu, digest,
21 ec::suite_b::{ops::*, public_key::*, verify_jacobian_point_is_on_the_curve},
22 error,
23 io::der,
24 limb, sealed, signature,
25};
26
27/// An ECDSA verification algorithm.
28pub struct EcdsaVerificationAlgorithm {
29 ops: &'static PublicScalarOps,
30 digest_alg: &'static digest::Algorithm,
31 split_rs:
32 for<'a> fn(
33 ops: &'static ScalarOps,
34 input: &mut untrusted::Reader<'a>,
35 )
36 -> Result<(untrusted::Input<'a>, untrusted::Input<'a>), error::Unspecified>,
37 id: AlgorithmID,
38}
39
40#[derive(Debug)]
41enum AlgorithmID {
42 ECDSA_P256_SHA256_ASN1,
43 ECDSA_P256_SHA256_FIXED,
44 ECDSA_P256_SHA384_ASN1,
45 ECDSA_P384_SHA256_ASN1,
46 ECDSA_P384_SHA384_ASN1,
47 ECDSA_P384_SHA384_FIXED,
48}
49
50derive_debug_via_id!(EcdsaVerificationAlgorithm);
51
52impl signature::VerificationAlgorithm for EcdsaVerificationAlgorithm {
53 fn verify(
54 &self,
55 public_key: untrusted::Input,
56 msg: untrusted::Input,
57 signature: untrusted::Input,
58 ) -> Result<(), error::Unspecified> {
59 let cpu: Features = cpu::features();
60 let e: Elem = {
61 // NSA Guide Step 2: "Use the selected hash function to compute H =
62 // Hash(M)."
63 let h: Digest = digest::digest(self.digest_alg, data:msg.as_slice_less_safe());
64
65 // NSA Guide Step 3: "Convert the bit string H to an integer e as
66 // described in Appendix B.2."
67 let n: &Modulus = &self.ops.scalar_ops.scalar_modulus(cpu);
68 digest_scalar(n, msg:h)
69 };
70
71 self.verify_digest(public_key, e, signature)
72 }
73}
74
75impl EcdsaVerificationAlgorithm {
76 /// This is intentionally not public.
77 fn verify_digest(
78 &self,
79 public_key: untrusted::Input,
80 e: Scalar,
81 signature: untrusted::Input,
82 ) -> Result<(), error::Unspecified> {
83 let cpu = cpu::features();
84
85 // NSA Suite B Implementer's Guide to ECDSA Section 3.4.2.
86
87 let public_key_ops = self.ops.public_key_ops;
88 let scalar_ops = self.ops.scalar_ops;
89 let q = &public_key_ops.common.elem_modulus(cpu);
90 let n = &scalar_ops.scalar_modulus(cpu);
91
92 // NSA Guide Prerequisites:
93 //
94 // Prior to accepting a verified digital signature as valid the
95 // verifier shall have:
96 //
97 // 1. assurance of the signatory’s claimed identity,
98 // 2. an authentic copy of the domain parameters, (q, FR, a, b, SEED,
99 // G, n, h),
100 // 3. assurance of the validity of the public key, and
101 // 4. assurance that the claimed signatory actually possessed the
102 // private key that was used to generate the digital signature at
103 // the time that the signature was generated.
104 //
105 // Prerequisites #1 and #4 are outside the scope of what this function
106 // can do. Prerequisite #2 is handled implicitly as the domain
107 // parameters are hard-coded into the source. Prerequisite #3 is
108 // handled by `parse_uncompressed_point`.
109 let peer_pub_key = parse_uncompressed_point(public_key_ops, q, public_key)?;
110
111 let (r, s) = signature.read_all(error::Unspecified, |input| {
112 (self.split_rs)(scalar_ops, input)
113 })?;
114
115 // NSA Guide Step 1: "If r and s are not both integers in the interval
116 // [1, n − 1], output INVALID."
117 let r = scalar_parse_big_endian_variable(n, limb::AllowZero::No, r)?;
118 let s = scalar_parse_big_endian_variable(n, limb::AllowZero::No, s)?;
119
120 // NSA Guide Step 4: "Compute w = s**−1 mod n, using the routine in
121 // Appendix B.1."
122 let w = self.ops.scalar_inv_to_mont_vartime(&s, cpu);
123
124 // NSA Guide Step 5: "Compute u1 = (e * w) mod n, and compute
125 // u2 = (r * w) mod n."
126 let u1 = scalar_ops.scalar_product(&e, &w, cpu);
127 let u2 = scalar_ops.scalar_product(&r, &w, cpu);
128
129 // NSA Guide Step 6: "Compute the elliptic curve point
130 // R = (xR, yR) = u1*G + u2*Q, using EC scalar multiplication and EC
131 // addition. If R is equal to the point at infinity, output INVALID."
132 let product = (self.ops.twin_mul)(&u1, &u2, &peer_pub_key, cpu);
133
134 // Verify that the point we computed is on the curve; see
135 // `verify_affine_point_is_on_the_curve_scaled` for details on why. It
136 // would be more secure to do the check on the affine coordinates if we
137 // were going to convert to affine form (again, see
138 // `verify_affine_point_is_on_the_curve_scaled` for details on why).
139 // But, we're going to avoid converting to affine for performance
140 // reasons, so we do the verification using the Jacobian coordinates.
141 let z2 = verify_jacobian_point_is_on_the_curve(q, &product)?;
142
143 // NSA Guide Step 7: "Compute v = xR mod n."
144 // NSA Guide Step 8: "Compare v and r0. If v = r0, output VALID;
145 // otherwise, output INVALID."
146 //
147 // Instead, we use Greg Maxwell's trick to avoid the inversion mod `q`
148 // that would be necessary to compute the affine X coordinate.
149 let x = q.point_x(&product);
150 fn sig_r_equals_x(q: &Modulus<Q>, r: &Elem<Unencoded>, x: &Elem<R>, z2: &Elem<R>) -> bool {
151 let r_jacobian = q.elem_product(z2, r);
152 let x = q.elem_unencoded(x);
153 q.elems_are_equal(&r_jacobian, &x).leak()
154 }
155 let mut r = self.ops.scalar_as_elem(&r);
156 if sig_r_equals_x(q, &r, &x, &z2) {
157 return Ok(());
158 }
159 if q.elem_less_than_vartime(&r, &self.ops.q_minus_n) {
160 let n = Elem::from(self.ops.n());
161 q.add_assign(&mut r, &n);
162 if sig_r_equals_x(q, &r, &x, &z2) {
163 return Ok(());
164 }
165 }
166
167 Err(error::Unspecified)
168 }
169}
170
171impl sealed::Sealed for EcdsaVerificationAlgorithm {}
172
173fn split_rs_fixed<'a>(
174 ops: &'static ScalarOps,
175 input: &mut untrusted::Reader<'a>,
176) -> Result<(untrusted::Input<'a>, untrusted::Input<'a>), error::Unspecified> {
177 let scalar_len: usize = ops.scalar_bytes_len();
178 let r: Input<'a> = input.read_bytes(num_bytes:scalar_len)?;
179 let s: Input<'a> = input.read_bytes(num_bytes:scalar_len)?;
180 Ok((r, s))
181}
182
183fn split_rs_asn1<'a>(
184 _ops: &'static ScalarOps,
185 input: &mut untrusted::Reader<'a>,
186) -> Result<(untrusted::Input<'a>, untrusted::Input<'a>), error::Unspecified> {
187 der::nested(input, der::Tag::Sequence, error:error::Unspecified, |input: &mut Reader<'_>| {
188 let r: Input<'_> = der::positive_integer(input)?.big_endian_without_leading_zero_as_input();
189 let s: Input<'_> = der::positive_integer(input)?.big_endian_without_leading_zero_as_input();
190 Ok((r, s))
191 })
192}
193
194/// Verification of fixed-length (PKCS#11 style) ECDSA signatures using the
195/// P-256 curve and SHA-256.
196///
197/// See "`ECDSA_*_FIXED` Details" in `ring::signature`'s module-level
198/// documentation for more details.
199pub static ECDSA_P256_SHA256_FIXED: EcdsaVerificationAlgorithm = EcdsaVerificationAlgorithm {
200 ops: &p256::PUBLIC_SCALAR_OPS,
201 digest_alg: &digest::SHA256,
202 split_rs: split_rs_fixed,
203 id: AlgorithmID::ECDSA_P256_SHA256_FIXED,
204};
205
206/// Verification of fixed-length (PKCS#11 style) ECDSA signatures using the
207/// P-384 curve and SHA-384.
208///
209/// See "`ECDSA_*_FIXED` Details" in `ring::signature`'s module-level
210/// documentation for more details.
211pub static ECDSA_P384_SHA384_FIXED: EcdsaVerificationAlgorithm = EcdsaVerificationAlgorithm {
212 ops: &p384::PUBLIC_SCALAR_OPS,
213 digest_alg: &digest::SHA384,
214 split_rs: split_rs_fixed,
215 id: AlgorithmID::ECDSA_P384_SHA384_FIXED,
216};
217
218/// Verification of ASN.1 DER-encoded ECDSA signatures using the P-256 curve
219/// and SHA-256.
220///
221/// See "`ECDSA_*_ASN1` Details" in `ring::signature`'s module-level
222/// documentation for more details.
223pub static ECDSA_P256_SHA256_ASN1: EcdsaVerificationAlgorithm = EcdsaVerificationAlgorithm {
224 ops: &p256::PUBLIC_SCALAR_OPS,
225 digest_alg: &digest::SHA256,
226 split_rs: split_rs_asn1,
227 id: AlgorithmID::ECDSA_P256_SHA256_ASN1,
228};
229
230/// *Not recommended*. Verification of ASN.1 DER-encoded ECDSA signatures using
231/// the P-256 curve and SHA-384.
232///
233/// In most situations, P-256 should be used only with SHA-256 and P-384
234/// should be used only with SHA-384. However, in some cases, particularly TLS
235/// on the web, it is necessary to support P-256 with SHA-384 for compatibility
236/// with widely-deployed implementations that do not follow these guidelines.
237///
238/// See "`ECDSA_*_ASN1` Details" in `ring::signature`'s module-level
239/// documentation for more details.
240pub static ECDSA_P256_SHA384_ASN1: EcdsaVerificationAlgorithm = EcdsaVerificationAlgorithm {
241 ops: &p256::PUBLIC_SCALAR_OPS,
242 digest_alg: &digest::SHA384,
243 split_rs: split_rs_asn1,
244 id: AlgorithmID::ECDSA_P256_SHA384_ASN1,
245};
246
247/// *Not recommended*. Verification of ASN.1 DER-encoded ECDSA signatures using
248/// the P-384 curve and SHA-256.
249///
250/// In most situations, P-256 should be used only with SHA-256 and P-384
251/// should be used only with SHA-384. However, in some cases, particularly TLS
252/// on the web, it is necessary to support P-256 with SHA-384 for compatibility
253/// with widely-deployed implementations that do not follow these guidelines.
254///
255/// See "`ECDSA_*_ASN1` Details" in `ring::signature`'s module-level
256/// documentation for more details.
257pub static ECDSA_P384_SHA256_ASN1: EcdsaVerificationAlgorithm = EcdsaVerificationAlgorithm {
258 ops: &p384::PUBLIC_SCALAR_OPS,
259 digest_alg: &digest::SHA256,
260 split_rs: split_rs_asn1,
261 id: AlgorithmID::ECDSA_P384_SHA256_ASN1,
262};
263
264/// Verification of ASN.1 DER-encoded ECDSA signatures using the P-384 curve
265/// and SHA-384.
266///
267/// See "`ECDSA_*_ASN1` Details" in `ring::signature`'s module-level
268/// documentation for more details.
269pub static ECDSA_P384_SHA384_ASN1: EcdsaVerificationAlgorithm = EcdsaVerificationAlgorithm {
270 ops: &p384::PUBLIC_SCALAR_OPS,
271 digest_alg: &digest::SHA384,
272 split_rs: split_rs_asn1,
273 id: AlgorithmID::ECDSA_P384_SHA384_ASN1,
274};
275
276#[cfg(test)]
277mod tests {
278 extern crate alloc;
279 use super::*;
280 use crate::test;
281 use alloc::{vec, vec::Vec};
282
283 #[test]
284 fn test_digest_based_test_vectors() {
285 let cpu = cpu::features();
286 test::run(
287 test_file!("../../../../crypto/fipsmodule/ecdsa/ecdsa_verify_tests.txt"),
288 |section, test_case| {
289 assert_eq!(section, "");
290
291 let curve_name = test_case.consume_string("Curve");
292
293 let public_key = {
294 let mut public_key = vec![0x04];
295 public_key.extend(&test_case.consume_bytes("X"));
296 public_key.extend(&test_case.consume_bytes("Y"));
297 public_key
298 };
299
300 let digest = test_case.consume_bytes("Digest");
301
302 let sig = {
303 let mut sig = Vec::new();
304 sig.extend(&test_case.consume_bytes("R"));
305 sig.extend(&test_case.consume_bytes("S"));
306 sig
307 };
308
309 let invalid = test_case.consume_optional_string("Invalid");
310
311 let alg = match curve_name.as_str() {
312 "P-256" => &ECDSA_P256_SHA256_FIXED,
313 "P-384" => &ECDSA_P384_SHA384_FIXED,
314 _ => {
315 panic!("Unsupported curve: {}", curve_name);
316 }
317 };
318 let n = &alg.ops.scalar_ops.scalar_modulus(cpu);
319
320 let digest = super::super::digest_scalar::digest_bytes_scalar(n, &digest[..]);
321 let actual_result = alg.verify_digest(
322 untrusted::Input::from(&public_key[..]),
323 digest,
324 untrusted::Input::from(&sig[..]),
325 );
326 assert_eq!(actual_result.is_ok(), invalid.is_none());
327
328 Ok(())
329 },
330 );
331 }
332}
333