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
17use self::ops::*;
18use 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//
32fn verify_affine_point_is_on_the_curve(
33 ops: &CommonOps,
34 (x: &Elem, y: &Elem): (&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.
48fn 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.
136fn verify_affine_point_is_on_the_curve_scaled(
137 ops: &CommonOps,
138 (x: &Elem, y: &Elem): (&Elem<R>, &Elem<R>),
139 a_scaled: &Elem<R>,
140 b_scaled: &Elem<R>,
141) -> Result<(), error::Unspecified> {
142 let lhs: Elem = ops.elem_squared(y);
143
144 let mut rhs: Elem = ops.elem_squared(x);
145 ops.elem_add(&mut rhs, b:a_scaled);
146 ops.elem_mul(&mut rhs, b: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
156pub(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: Input<'_>, _) = pkcs8::unwrap_key(template, pkcs8::Version::V1Only, input)?;
163 let (private_key: Input<'_>, public_key: Input<'_>) =
164 ec_private_key.read_all(incomplete_read:error::KeyRejected::invalid_encoding(), |input: &mut Reader<'_>| {
165 // https://tools.ietf.org/html/rfc5915#section-3
166 der::nested(
167 input,
168 der::Tag::Sequence,
169 error:error::KeyRejected::invalid_encoding(),
170 |input: &mut Reader<'_>| key_pair_from_pkcs8_(template, input),
171 )
172 })?;
173 key_pair_from_bytes(curve, private_key_bytes:private_key, public_key_bytes:public_key, cpu_features)
174}
175
176fn 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.as_slice_less_safe() != template.curve_oid().as_slice_less_safe() {
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
212pub(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: Seed = ec::Seed::from_bytes(curve, private_key_bytes, cpu_features)
219 .map_err(|error::Unspecified| error::KeyRejected::invalid_component())?;
220
221 let r: KeyPair = ec::KeyPair::derive(seed)
222 .map_err(|error::Unspecified| error::KeyRejected::unexpected_error())?;
223 if public_key_bytes.as_slice_less_safe() != r.public_key().as_ref() {
224 return Err(error::KeyRejected::inconsistent_components());
225 }
226
227 Ok(r)
228}
229
230pub mod curve;
231
232pub mod ecdh;
233
234pub mod ecdsa;
235
236mod ops;
237
238mod private_key;
239mod public_key;
240