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