1 // Copyright 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 //! Elliptic curve operations on P-256 & P-384. 16 17 use self::ops::*; 18 use crate::{arithmetic::montgomery::*, cpu, ec, error, io::der, limb::LimbMask, pkcs8}; 19 20 // NIST SP 800-56A Step 3: "If q is an odd prime p, verify that 21 // yQ**2 = xQ**3 + axQ + b in GF(p), where the arithmetic is performed modulo 22 // p." 23 // 24 // That is, verify that (x, y) is on the curve, which is true iif: 25 // 26 // y**2 == x**3 + a*x + b (mod q) 27 // 28 // Or, equivalently, but more efficiently: 29 // 30 // y**2 == (x**2 + a)*x + b (mod q) 31 // 32 fn verify_affine_point_is_on_the_curve( 33 ops: &CommonOps, 34 (x, y): (&Elem<R>, &Elem<R>), 35 ) -> Result<(), error::Unspecified> { 36 verify_affine_point_is_on_the_curve_scaled(ops, (x, y), &ops.a, &ops.b) 37 } 38 39 // Use `verify_affine_point_is_on_the_curve` instead of this function whenever 40 // the affine coordinates are available or will become available. This function 41 // should only be used then the affine coordinates are never calculated. See 42 // the notes for `verify_affine_point_is_on_the_curve_scaled`. 43 // 44 // The value `z**2` is returned on success because it is useful for ECDSA 45 // verification. 46 // 47 // This function also verifies that the point is not at infinity. 48 fn verify_jacobian_point_is_on_the_curve( 49 ops: &CommonOps, 50 p: &Point, 51 ) -> Result<Elem<R>, error::Unspecified> { 52 let z = ops.point_z(p); 53 54 // Verify that the point is not at infinity. 55 ops.elem_verify_is_not_zero(&z)?; 56 57 let x = ops.point_x(p); 58 let y = ops.point_y(p); 59 60 // We are given Jacobian coordinates (x, y, z). So, we have: 61 // 62 // (x/z**2, y/z**3) == (x', y'), 63 // 64 // where (x', y') are the affine coordinates. The curve equation is: 65 // 66 // y'**2 == x'**3 + a*x' + b == (x'**2 + a)*x' + b 67 // 68 // Substituting our Jacobian coordinates, we get: 69 // 70 // / y \**2 / / x \**2 \ / x \ 71 // | ---- | == | | ---- | + a | * | ---- | + b 72 // \ z**3 / \ \ z**2 / / \ z**2 / 73 // 74 // Simplify: 75 // 76 // y**2 / x**2 \ x 77 // ---- == | ---- + a | * ---- + b 78 // z**6 \ z**4 / z**2 79 // 80 // Multiply both sides by z**6: 81 // 82 // z**6 / x**2 \ z**6 83 // ---- * y**2 == | ---- + a | * ---- * x + (z**6) * b 84 // z**6 \ z**4 / z**2 85 // 86 // Simplify: 87 // 88 // / x**2 \ 89 // y**2 == | ---- + a | * z**4 * x + (z**6) * b 90 // \ z**4 / 91 // 92 // Distribute z**4: 93 // 94 // / z**4 \ 95 // y**2 == | ---- * x**2 + z**4 * a | * x + (z**6) * b 96 // \ z**4 / 97 // 98 // Simplify: 99 // 100 // y**2 == (x**2 + z**4 * a) * x + (z**6) * b 101 // 102 let z2 = ops.elem_squared(&z); 103 let z4 = ops.elem_squared(&z2); 104 let z4_a = ops.elem_product(&z4, &ops.a); 105 let z6 = ops.elem_product(&z4, &z2); 106 let z6_b = ops.elem_product(&z6, &ops.b); 107 verify_affine_point_is_on_the_curve_scaled(ops, (&x, &y), &z4_a, &z6_b)?; 108 Ok(z2) 109 } 110 111 // Handles the common logic of point-is-on-the-curve checks for both affine and 112 // Jacobian cases. 113 // 114 // When doing the check that the point is on the curve after a computation, 115 // to avoid fault attacks or mitigate potential bugs, it is better for security 116 // to use `verify_affine_point_is_on_the_curve` on the affine coordinates, 117 // because it provides some protection against faults that occur in the 118 // computation of the inverse of `z`. See the paper and presentation "Fault 119 // Attacks on Projective-to-Affine Coordinates Conversion" by Diana Maimuţ, 120 // Cédric Murdica, David Naccache, Mehdi Tibouchi. That presentation concluded 121 // simply "Check the validity of the result after conversion to affine 122 // coordinates." (It seems like a good idea to verify that 123 // z_inv * z == 1 mod q too). 124 // 125 // In the case of affine coordinates (x, y), `a_scaled` and `b_scaled` are 126 // `a` and `b`, respectively. In the case of Jacobian coordinates (x, y, z), 127 // the computation and comparison is the same, except `a_scaled` and `b_scaled` 128 // are (z**4 * a) and (z**6 * b), respectively. Thus, performance is another 129 // reason to prefer doing the check on the affine coordinates, as Jacobian 130 // computation requires 3 extra multiplications and 2 extra squarings. 131 // 132 // An example of a fault attack that isn't mitigated by a point-on-the-curve 133 // check after multiplication is given in "Sign Change Fault Attacks On 134 // Elliptic Curve Cryptosystems" by Johannes Blömer, Martin Otto, and 135 // Jean-Pierre Seifert. 136 fn verify_affine_point_is_on_the_curve_scaled( 137 ops: &CommonOps, 138 (x, y): (&Elem<R>, &Elem<R>), 139 a_scaled: &Elem<R>, 140 b_scaled: &Elem<R>, 141 ) -> Result<(), error::Unspecified> { 142 let lhs = ops.elem_squared(y); 143 144 let mut rhs = ops.elem_squared(x); 145 ops.elem_add(&mut rhs, a_scaled); 146 ops.elem_mul(&mut rhs, x); 147 ops.elem_add(&mut rhs, b_scaled); 148 149 if ops.elems_are_equal(&lhs, &rhs) != LimbMask::True { 150 return Err(error::Unspecified); 151 } 152 153 Ok(()) 154 } 155 156 pub(crate) fn key_pair_from_pkcs8( 157 curve: &'static ec::Curve, 158 template: &pkcs8::Template, 159 input: untrusted::Input, 160 cpu_features: cpu::Features, 161 ) -> Result<ec::KeyPair, error::KeyRejected> { 162 let (ec_private_key, _) = pkcs8::unwrap_key(template, pkcs8::Version::V1Only, input)?; 163 let (private_key, public_key) = 164 ec_private_key.read_all(error::KeyRejected::invalid_encoding(), |input| { 165 // https://tools.ietf.org/html/rfc5915#section-3 166 der::nested( 167 input, 168 der::Tag::Sequence, 169 error::KeyRejected::invalid_encoding(), 170 |input| key_pair_from_pkcs8_(template, input), 171 ) 172 })?; 173 key_pair_from_bytes(curve, private_key, public_key, cpu_features) 174 } 175 176 fn key_pair_from_pkcs8_<'a>( 177 template: &pkcs8::Template, 178 input: &mut untrusted::Reader<'a>, 179 ) -> Result<(untrusted::Input<'a>, untrusted::Input<'a>), error::KeyRejected> { 180 let version = der::small_nonnegative_integer(input) 181 .map_err(|error::Unspecified| error::KeyRejected::invalid_encoding())?; 182 if version != 1 { 183 return Err(error::KeyRejected::version_not_supported()); 184 } 185 186 let private_key = der::expect_tag_and_get_value(input, der::Tag::OctetString) 187 .map_err(|error::Unspecified| error::KeyRejected::invalid_encoding())?; 188 189 // [0] parameters (optional). 190 if input.peek(u8::from(der::Tag::ContextSpecificConstructed0)) { 191 let actual_alg_id = 192 der::expect_tag_and_get_value(input, der::Tag::ContextSpecificConstructed0) 193 .map_err(|error::Unspecified| error::KeyRejected::invalid_encoding())?; 194 if actual_alg_id != template.curve_oid() { 195 return Err(error::KeyRejected::wrong_algorithm()); 196 } 197 } 198 199 // [1] publicKey. The RFC says it is optional, but we require it 200 // to be present. 201 let public_key = der::nested( 202 input, 203 der::Tag::ContextSpecificConstructed1, 204 error::Unspecified, 205 der::bit_string_with_no_unused_bits, 206 ) 207 .map_err(|error::Unspecified| error::KeyRejected::invalid_encoding())?; 208 209 Ok((private_key, public_key)) 210 } 211 212 pub(crate) fn key_pair_from_bytes( 213 curve: &'static ec::Curve, 214 private_key_bytes: untrusted::Input, 215 public_key_bytes: untrusted::Input, 216 cpu_features: cpu::Features, 217 ) -> Result<ec::KeyPair, error::KeyRejected> { 218 let seed = ec::Seed::from_bytes(curve, private_key_bytes, cpu_features) 219 .map_err(|error::Unspecified| error::KeyRejected::invalid_component())?; 220 221 let r = ec::KeyPair::derive(seed) 222 .map_err(|error::Unspecified| error::KeyRejected::unexpected_error())?; 223 if public_key_bytes != *r.public_key().as_ref() { 224 return Err(error::KeyRejected::inconsistent_components()); 225 } 226 227 Ok(r) 228 } 229 230 pub mod curve; 231 pub mod ecdh; 232 pub mod ecdsa; 233 234 mod ops; 235 236 mod private_key; 237 mod public_key; 238