Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame^] | 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 |