1 /* Copyright (c) 2016, Google Inc.
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 AUTHOR DISCLAIMS ALL WARRANTIES
8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR 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 #if !defined(__STDC_FORMAT_MACROS)
16 #define __STDC_FORMAT_MACROS
17 #endif
18
19 #include <openssl/base.h>
20
21 #include <stdio.h>
22 #include <string.h>
23
24 #include <gtest/gtest.h>
25
26 #include <openssl/bn.h>
27 #include <openssl/mem.h>
28
29 #include "../bn/internal.h"
30 #include "../../internal.h"
31 #include "../../test/file_test.h"
32 #include "../../test/test_util.h"
33 #include "p256-x86_64.h"
34
35
36 // Disable tests if BORINGSSL_SHARED_LIBRARY is defined. These tests need access
37 // to internal functions.
38 #if !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86_64) && \
39 !defined(OPENSSL_SMALL) && !defined(BORINGSSL_SHARED_LIBRARY)
40
TEST(P256_X86_64Test,SelectW5)41 TEST(P256_X86_64Test, SelectW5) {
42 // Fill a table with some garbage input.
43 alignas(64) P256_POINT table[16];
44 for (size_t i = 0; i < 16; i++) {
45 OPENSSL_memset(table[i].X, 3 * i, sizeof(table[i].X));
46 OPENSSL_memset(table[i].Y, 3 * i + 1, sizeof(table[i].Y));
47 OPENSSL_memset(table[i].Z, 3 * i + 2, sizeof(table[i].Z));
48 }
49
50 for (int i = 0; i <= 16; i++) {
51 P256_POINT val;
52 ecp_nistz256_select_w5(&val, table, i);
53
54 P256_POINT expected;
55 if (i == 0) {
56 OPENSSL_memset(&expected, 0, sizeof(expected));
57 } else {
58 expected = table[i-1];
59 }
60
61 EXPECT_EQ(Bytes(reinterpret_cast<const char *>(&expected), sizeof(expected)),
62 Bytes(reinterpret_cast<const char *>(&val), sizeof(val)));
63 }
64 }
65
TEST(P256_X86_64Test,SelectW7)66 TEST(P256_X86_64Test, SelectW7) {
67 // Fill a table with some garbage input.
68 alignas(64) P256_POINT_AFFINE table[64];
69 for (size_t i = 0; i < 64; i++) {
70 OPENSSL_memset(table[i].X, 2 * i, sizeof(table[i].X));
71 OPENSSL_memset(table[i].Y, 2 * i + 1, sizeof(table[i].Y));
72 }
73
74 for (int i = 0; i <= 64; i++) {
75 P256_POINT_AFFINE val;
76 ecp_nistz256_select_w7(&val, table, i);
77
78 P256_POINT_AFFINE expected;
79 if (i == 0) {
80 OPENSSL_memset(&expected, 0, sizeof(expected));
81 } else {
82 expected = table[i-1];
83 }
84
85 EXPECT_EQ(Bytes(reinterpret_cast<const char *>(&expected), sizeof(expected)),
86 Bytes(reinterpret_cast<const char *>(&val), sizeof(val)));
87 }
88 }
89
GetFieldElement(FileTest * t,BN_ULONG out[P256_LIMBS],const char * name)90 static bool GetFieldElement(FileTest *t, BN_ULONG out[P256_LIMBS],
91 const char *name) {
92 std::vector<uint8_t> bytes;
93 if (!t->GetBytes(&bytes, name)) {
94 return false;
95 }
96
97 if (bytes.size() != BN_BYTES * P256_LIMBS) {
98 ADD_FAILURE() << "Invalid length: " << name;
99 return false;
100 }
101
102 // |byte| contains bytes in big-endian while |out| should contain |BN_ULONG|s
103 // in little-endian.
104 OPENSSL_memset(out, 0, P256_LIMBS * sizeof(BN_ULONG));
105 for (size_t i = 0; i < bytes.size(); i++) {
106 out[P256_LIMBS - 1 - (i / BN_BYTES)] <<= 8;
107 out[P256_LIMBS - 1 - (i / BN_BYTES)] |= bytes[i];
108 }
109
110 return true;
111 }
112
FieldElementToString(const BN_ULONG a[P256_LIMBS])113 static std::string FieldElementToString(const BN_ULONG a[P256_LIMBS]) {
114 std::string ret;
115 for (size_t i = P256_LIMBS-1; i < P256_LIMBS; i--) {
116 char buf[2 * BN_BYTES + 1];
117 BIO_snprintf(buf, sizeof(buf), BN_HEX_FMT2, a[i]);
118 ret += buf;
119 }
120 return ret;
121 }
122
ExpectFieldElementsEqual(const char * expected_expr,const char * actual_expr,const BN_ULONG expected[P256_LIMBS],const BN_ULONG actual[P256_LIMBS])123 static testing::AssertionResult ExpectFieldElementsEqual(
124 const char *expected_expr, const char *actual_expr,
125 const BN_ULONG expected[P256_LIMBS], const BN_ULONG actual[P256_LIMBS]) {
126 if (OPENSSL_memcmp(expected, actual, sizeof(BN_ULONG) * P256_LIMBS) == 0) {
127 return testing::AssertionSuccess();
128 }
129
130 return testing::AssertionFailure()
131 << "Expected: " << FieldElementToString(expected) << " ("
132 << expected_expr << ")\n"
133 << "Actual: " << FieldElementToString(actual) << " (" << actual_expr
134 << ")";
135 }
136
137 #define EXPECT_FIELD_ELEMENTS_EQUAL(a, b) \
138 EXPECT_PRED_FORMAT2(ExpectFieldElementsEqual, a, b)
139
PointToAffine(P256_POINT_AFFINE * out,const P256_POINT * in)140 static bool PointToAffine(P256_POINT_AFFINE *out, const P256_POINT *in) {
141 static const uint8_t kP[] = {
142 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
143 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff,
144 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
145 };
146
147 bssl::UniquePtr<BIGNUM> x(BN_new()), y(BN_new()), z(BN_new());
148 bssl::UniquePtr<BIGNUM> p(BN_bin2bn(kP, sizeof(kP), nullptr));
149 if (!x || !y || !z || !p ||
150 !bn_set_words(x.get(), in->X, P256_LIMBS) ||
151 !bn_set_words(y.get(), in->Y, P256_LIMBS) ||
152 !bn_set_words(z.get(), in->Z, P256_LIMBS)) {
153 return false;
154 }
155
156 // Coordinates must be fully-reduced.
157 if (BN_cmp(x.get(), p.get()) >= 0 ||
158 BN_cmp(y.get(), p.get()) >= 0 ||
159 BN_cmp(z.get(), p.get()) >= 0) {
160 return false;
161 }
162
163 if (BN_is_zero(z.get())) {
164 // The point at infinity is represented as (0, 0).
165 OPENSSL_memset(out, 0, sizeof(P256_POINT_AFFINE));
166 return true;
167 }
168
169 bssl::UniquePtr<BN_CTX> ctx(BN_CTX_new());
170 bssl::UniquePtr<BN_MONT_CTX> mont(
171 BN_MONT_CTX_new_for_modulus(p.get(), ctx.get()));
172 if (!ctx || !mont ||
173 // Invert Z.
174 !BN_from_montgomery(z.get(), z.get(), mont.get(), ctx.get()) ||
175 !BN_mod_inverse(z.get(), z.get(), p.get(), ctx.get()) ||
176 !BN_to_montgomery(z.get(), z.get(), mont.get(), ctx.get()) ||
177 // Convert (X, Y, Z) to (X/Z^2, Y/Z^3).
178 !BN_mod_mul_montgomery(x.get(), x.get(), z.get(), mont.get(),
179 ctx.get()) ||
180 !BN_mod_mul_montgomery(x.get(), x.get(), z.get(), mont.get(),
181 ctx.get()) ||
182 !BN_mod_mul_montgomery(y.get(), y.get(), z.get(), mont.get(),
183 ctx.get()) ||
184 !BN_mod_mul_montgomery(y.get(), y.get(), z.get(), mont.get(),
185 ctx.get()) ||
186 !BN_mod_mul_montgomery(y.get(), y.get(), z.get(), mont.get(),
187 ctx.get()) ||
188 !bn_copy_words(out->X, P256_LIMBS, x.get()) ||
189 !bn_copy_words(out->Y, P256_LIMBS, y.get())) {
190 return false;
191 }
192 return true;
193 }
194
ExpectPointsEqual(const char * expected_expr,const char * actual_expr,const P256_POINT_AFFINE * expected,const P256_POINT * actual)195 static testing::AssertionResult ExpectPointsEqual(
196 const char *expected_expr, const char *actual_expr,
197 const P256_POINT_AFFINE *expected, const P256_POINT *actual) {
198 // There are multiple representations of the same |P256_POINT|, so convert to
199 // |P256_POINT_AFFINE| and compare.
200 P256_POINT_AFFINE affine;
201 if (!PointToAffine(&affine, actual)) {
202 return testing::AssertionFailure()
203 << "Could not convert " << actual_expr << " to affine: ("
204 << FieldElementToString(actual->X) << ", "
205 << FieldElementToString(actual->Y) << ", "
206 << FieldElementToString(actual->Z) << ")";
207 }
208
209 if (OPENSSL_memcmp(expected, &affine, sizeof(P256_POINT_AFFINE)) != 0) {
210 return testing::AssertionFailure()
211 << "Expected: (" << FieldElementToString(expected->X) << ", "
212 << FieldElementToString(expected->Y) << ") (" << expected_expr
213 << "; affine)\n"
214 << "Actual: (" << FieldElementToString(affine.X) << ", "
215 << FieldElementToString(affine.Y) << ") (" << actual_expr << ")";
216 }
217
218 return testing::AssertionSuccess();
219 }
220
221 #define EXPECT_POINTS_EQUAL(a, b) EXPECT_PRED_FORMAT2(ExpectPointsEqual, a, b)
222
TestNegate(FileTest * t)223 static void TestNegate(FileTest *t) {
224 BN_ULONG a[P256_LIMBS], b[P256_LIMBS];
225 ASSERT_TRUE(GetFieldElement(t, a, "A"));
226 ASSERT_TRUE(GetFieldElement(t, b, "B"));
227
228 // Test that -A = B.
229 BN_ULONG ret[P256_LIMBS];
230 ecp_nistz256_neg(ret, a);
231 EXPECT_FIELD_ELEMENTS_EQUAL(b, ret);
232
233 OPENSSL_memcpy(ret, a, sizeof(ret));
234 ecp_nistz256_neg(ret, ret /* a */);
235 EXPECT_FIELD_ELEMENTS_EQUAL(b, ret);
236
237 // Test that -B = A.
238 ecp_nistz256_neg(ret, b);
239 EXPECT_FIELD_ELEMENTS_EQUAL(a, ret);
240
241 OPENSSL_memcpy(ret, b, sizeof(ret));
242 ecp_nistz256_neg(ret, ret /* b */);
243 EXPECT_FIELD_ELEMENTS_EQUAL(a, ret);
244 }
245
TestMulMont(FileTest * t)246 static void TestMulMont(FileTest *t) {
247 BN_ULONG a[P256_LIMBS], b[P256_LIMBS], result[P256_LIMBS];
248 ASSERT_TRUE(GetFieldElement(t, a, "A"));
249 ASSERT_TRUE(GetFieldElement(t, b, "B"));
250 ASSERT_TRUE(GetFieldElement(t, result, "Result"));
251
252 BN_ULONG ret[P256_LIMBS];
253 ecp_nistz256_mul_mont(ret, a, b);
254 EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
255
256 ecp_nistz256_mul_mont(ret, b, a);
257 EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
258
259 OPENSSL_memcpy(ret, a, sizeof(ret));
260 ecp_nistz256_mul_mont(ret, ret /* a */, b);
261 EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
262
263 OPENSSL_memcpy(ret, a, sizeof(ret));
264 ecp_nistz256_mul_mont(ret, b, ret);
265 EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
266
267 OPENSSL_memcpy(ret, b, sizeof(ret));
268 ecp_nistz256_mul_mont(ret, a, ret /* b */);
269 EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
270
271 OPENSSL_memcpy(ret, b, sizeof(ret));
272 ecp_nistz256_mul_mont(ret, ret /* b */, a);
273 EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
274
275 if (OPENSSL_memcmp(a, b, sizeof(a)) == 0) {
276 ecp_nistz256_sqr_mont(ret, a);
277 EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
278
279 OPENSSL_memcpy(ret, a, sizeof(ret));
280 ecp_nistz256_sqr_mont(ret, ret /* a */);
281 EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
282 }
283 }
284
TestFromMont(FileTest * t)285 static void TestFromMont(FileTest *t) {
286 BN_ULONG a[P256_LIMBS], result[P256_LIMBS];
287 ASSERT_TRUE(GetFieldElement(t, a, "A"));
288 ASSERT_TRUE(GetFieldElement(t, result, "Result"));
289
290 BN_ULONG ret[P256_LIMBS];
291 ecp_nistz256_from_mont(ret, a);
292 EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
293
294 OPENSSL_memcpy(ret, a, sizeof(ret));
295 ecp_nistz256_from_mont(ret, ret /* a */);
296 EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
297 }
298
TestPointAdd(FileTest * t)299 static void TestPointAdd(FileTest *t) {
300 P256_POINT a, b;
301 P256_POINT_AFFINE result;
302 ASSERT_TRUE(GetFieldElement(t, a.X, "A.X"));
303 ASSERT_TRUE(GetFieldElement(t, a.Y, "A.Y"));
304 ASSERT_TRUE(GetFieldElement(t, a.Z, "A.Z"));
305 ASSERT_TRUE(GetFieldElement(t, b.X, "B.X"));
306 ASSERT_TRUE(GetFieldElement(t, b.Y, "B.Y"));
307 ASSERT_TRUE(GetFieldElement(t, b.Z, "B.Z"));
308 ASSERT_TRUE(GetFieldElement(t, result.X, "Result.X"));
309 ASSERT_TRUE(GetFieldElement(t, result.Y, "Result.Y"));
310
311 P256_POINT ret;
312 ecp_nistz256_point_add(&ret, &a, &b);
313 EXPECT_POINTS_EQUAL(&result, &ret);
314
315 ecp_nistz256_point_add(&ret, &b, &a);
316 EXPECT_POINTS_EQUAL(&result, &ret);
317
318 OPENSSL_memcpy(&ret, &a, sizeof(ret));
319 ecp_nistz256_point_add(&ret, &ret /* a */, &b);
320 EXPECT_POINTS_EQUAL(&result, &ret);
321
322 OPENSSL_memcpy(&ret, &a, sizeof(ret));
323 ecp_nistz256_point_add(&ret, &b, &ret /* a */);
324 EXPECT_POINTS_EQUAL(&result, &ret);
325
326 OPENSSL_memcpy(&ret, &b, sizeof(ret));
327 ecp_nistz256_point_add(&ret, &a, &ret /* b */);
328 EXPECT_POINTS_EQUAL(&result, &ret);
329
330 OPENSSL_memcpy(&ret, &b, sizeof(ret));
331 ecp_nistz256_point_add(&ret, &ret /* b */, &a);
332 EXPECT_POINTS_EQUAL(&result, &ret);
333
334 P256_POINT_AFFINE a_affine, b_affine, infinity;
335 OPENSSL_memset(&infinity, 0, sizeof(infinity));
336 ASSERT_TRUE(PointToAffine(&a_affine, &a));
337 ASSERT_TRUE(PointToAffine(&b_affine, &b));
338
339 // ecp_nistz256_point_add_affine does not work when a == b unless doubling the
340 // point at infinity.
341 if (OPENSSL_memcmp(&a_affine, &b_affine, sizeof(a_affine)) != 0 ||
342 OPENSSL_memcmp(&a_affine, &infinity, sizeof(a_affine)) == 0) {
343 ecp_nistz256_point_add_affine(&ret, &a, &b_affine);
344 EXPECT_POINTS_EQUAL(&result, &ret);
345
346 OPENSSL_memcpy(&ret, &a, sizeof(ret));
347 ecp_nistz256_point_add_affine(&ret, &ret /* a */, &b_affine);
348 EXPECT_POINTS_EQUAL(&result, &ret);
349
350 ecp_nistz256_point_add_affine(&ret, &b, &a_affine);
351 EXPECT_POINTS_EQUAL(&result, &ret);
352
353 OPENSSL_memcpy(&ret, &b, sizeof(ret));
354 ecp_nistz256_point_add_affine(&ret, &ret /* b */, &a_affine);
355 EXPECT_POINTS_EQUAL(&result, &ret);
356 }
357
358 if (OPENSSL_memcmp(&a, &b, sizeof(a)) == 0) {
359 ecp_nistz256_point_double(&ret, &a);
360 EXPECT_POINTS_EQUAL(&result, &ret);
361
362 ret = a;
363 ecp_nistz256_point_double(&ret, &ret /* a */);
364 EXPECT_POINTS_EQUAL(&result, &ret);
365 }
366 }
367
TEST(P256_X86_64Test,TestVectors)368 TEST(P256_X86_64Test, TestVectors) {
369 return FileTestGTest("crypto/fipsmodule/ec/p256-x86_64_tests.txt",
370 [](FileTest *t) {
371 if (t->GetParameter() == "Negate") {
372 TestNegate(t);
373 } else if (t->GetParameter() == "MulMont") {
374 TestMulMont(t);
375 } else if (t->GetParameter() == "FromMont") {
376 TestFromMont(t);
377 } else if (t->GetParameter() == "PointAdd") {
378 TestPointAdd(t);
379 } else {
380 FAIL() << "Unknown test type:" << t->GetParameter();
381 }
382 });
383 }
384
385 #endif
386