Home | History | Annotate | Download | only in ec 
      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 <openssl/bn.h>
     25 #include <openssl/mem.h>
     26 
     27 #include "../bn/internal.h"
     28 #include "../test/file_test.h"
     29 #include "p256-x86_64.h"
     30 
     31 
     32 // Disable tests if BORINGSSL_SHARED_LIBRARY is defined. These tests need access
     33 // to internal functions.
     34 #if !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86_64) && \
     35     !defined(OPENSSL_SMALL) && !defined(BORINGSSL_SHARED_LIBRARY)
     36 
     37 static bool TestSelectW5() {
     38   // Fill a table with some garbage input.
     39   P256_POINT table[16];
     40   for (size_t i = 0; i < 16; i++) {
     41     OPENSSL_memset(table[i].X, 3 * i, sizeof(table[i].X));
     42     OPENSSL_memset(table[i].Y, 3 * i + 1, sizeof(table[i].Y));
     43     OPENSSL_memset(table[i].Z, 3 * i + 2, sizeof(table[i].Z));
     44   }
     45 
     46   for (int i = 0; i <= 16; i++) {
     47     P256_POINT val;
     48     ecp_nistz256_select_w5(&val, table, i);
     49 
     50     P256_POINT expected;
     51     if (i == 0) {
     52       OPENSSL_memset(&expected, 0, sizeof(expected));
     53     } else {
     54       expected = table[i-1];
     55     }
     56 
     57     if (OPENSSL_memcmp(&val, &expected, sizeof(P256_POINT)) != 0) {
     58       fprintf(stderr, "ecp_nistz256_select_w5(%d) gave the wrong value.\n", i);
     59       return false;
     60     }
     61   }
     62 
     63   return true;
     64 }
     65 
     66 static bool TestSelectW7() {
     67   // Fill a table with some garbage input.
     68   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     if (OPENSSL_memcmp(&val, &expected, sizeof(P256_POINT_AFFINE)) != 0) {
     86       fprintf(stderr, "ecp_nistz256_select_w7(%d) gave the wrong value.\n", i);
     87       return false;
     88     }
     89   }
     90 
     91   return true;
     92 }
     93 
     94 static bool GetFieldElement(FileTest *t, BN_ULONG out[P256_LIMBS],
     95                             const char *name) {
     96   std::vector<uint8_t> bytes;
     97   if (!t->GetBytes(&bytes, name)) {
     98     return false;
     99   }
    100 
    101   if (bytes.size() != BN_BYTES * P256_LIMBS) {
    102     t->PrintLine("Invalid length: %s", name);
    103     return false;
    104   }
    105 
    106   // |byte| contains bytes in big-endian while |out| should contain |BN_ULONG|s
    107   // in little-endian.
    108   OPENSSL_memset(out, 0, P256_LIMBS * sizeof(BN_ULONG));
    109   for (size_t i = 0; i < bytes.size(); i++) {
    110     out[P256_LIMBS - 1 - (i / BN_BYTES)] <<= 8;
    111     out[P256_LIMBS - 1 - (i / BN_BYTES)] |= bytes[i];
    112   }
    113 
    114   return true;
    115 }
    116 
    117 static std::string FieldElementToString(const BN_ULONG a[P256_LIMBS]) {
    118   std::string ret;
    119   for (size_t i = P256_LIMBS-1; i < P256_LIMBS; i--) {
    120     char buf[2 * BN_BYTES + 1];
    121     BIO_snprintf(buf, sizeof(buf), BN_HEX_FMT2, a[i]);
    122     ret += buf;
    123   }
    124   return ret;
    125 }
    126 
    127 static bool ExpectFieldElementsEqual(FileTest *t, const char *message,
    128                                      const BN_ULONG expected[P256_LIMBS],
    129                                      const BN_ULONG actual[P256_LIMBS]) {
    130   if (OPENSSL_memcmp(expected, actual, sizeof(BN_ULONG) * P256_LIMBS) == 0) {
    131     return true;
    132   }
    133 
    134   t->PrintLine("%s", message);
    135   t->PrintLine("Expected: %s", FieldElementToString(expected).c_str());
    136   t->PrintLine("Actual:   %s", FieldElementToString(actual).c_str());
    137   return false;
    138 }
    139 
    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   OPENSSL_memset(out, 0, sizeof(P256_POINT_AFFINE));
    164 
    165   if (BN_is_zero(z.get())) {
    166     // The point at infinity is represented as (0, 0).
    167     return true;
    168   }
    169 
    170   bssl::UniquePtr<BN_CTX> ctx(BN_CTX_new());
    171   bssl::UniquePtr<BN_MONT_CTX> mont(BN_MONT_CTX_new());
    172   if (!ctx || !mont ||
    173       !BN_MONT_CTX_set(mont.get(), p.get(), ctx.get()) ||
    174       // Invert Z.
    175       !BN_from_montgomery(z.get(), z.get(), mont.get(), ctx.get()) ||
    176       !BN_mod_inverse(z.get(), z.get(), p.get(), ctx.get()) ||
    177       !BN_to_montgomery(z.get(), z.get(), mont.get(), ctx.get()) ||
    178       // Convert (X, Y, Z) to (X/Z^2, Y/Z^3).
    179       !BN_mod_mul_montgomery(x.get(), x.get(), z.get(), mont.get(),
    180                              ctx.get()) ||
    181       !BN_mod_mul_montgomery(x.get(), x.get(), z.get(), mont.get(),
    182                              ctx.get()) ||
    183       !BN_mod_mul_montgomery(y.get(), y.get(), z.get(), mont.get(),
    184                              ctx.get()) ||
    185       !BN_mod_mul_montgomery(y.get(), y.get(), z.get(), mont.get(),
    186                              ctx.get()) ||
    187       !BN_mod_mul_montgomery(y.get(), y.get(), z.get(), mont.get(),
    188                              ctx.get())) {
    189     return false;
    190   }
    191 
    192   OPENSSL_memcpy(out->X, x->d, sizeof(BN_ULONG) * x->top);
    193   OPENSSL_memcpy(out->Y, y->d, sizeof(BN_ULONG) * y->top);
    194   return true;
    195 }
    196 
    197 static bool ExpectPointsEqual(FileTest *t, const char *message,
    198                               const P256_POINT_AFFINE *expected,
    199                               const P256_POINT *point) {
    200   // There are multiple representations of the same |P256_POINT|, so convert to
    201   // |P256_POINT_AFFINE| and compare.
    202   P256_POINT_AFFINE affine;
    203   if (!PointToAffine(&affine, point)) {
    204     t->PrintLine("%s", message);
    205     t->PrintLine("Could not convert to affine: (%s, %s, %s)",
    206                  FieldElementToString(point->X).c_str(),
    207                  FieldElementToString(point->Y).c_str(),
    208                  FieldElementToString(point->Z).c_str());
    209     return false;
    210   }
    211 
    212   if (OPENSSL_memcmp(expected, &affine, sizeof(P256_POINT_AFFINE)) != 0) {
    213     t->PrintLine("%s", message);
    214     t->PrintLine("Expected: (%s, %s)",
    215                  FieldElementToString(expected->X).c_str(),
    216                  FieldElementToString(expected->Y).c_str());
    217     t->PrintLine("Actual:   (%s, %s)", FieldElementToString(affine.X).c_str(),
    218                  FieldElementToString(affine.Y).c_str());
    219     return false;
    220   }
    221 
    222   return true;
    223 }
    224 
    225 static bool TestNegate(FileTest *t) {
    226   BN_ULONG a[P256_LIMBS], b[P256_LIMBS];
    227   if (!GetFieldElement(t, a, "A") ||
    228       !GetFieldElement(t, b, "B")) {
    229     return false;
    230   }
    231 
    232   // Test that -A = B.
    233   BN_ULONG ret[P256_LIMBS];
    234   ecp_nistz256_neg(ret, a);
    235   if (!ExpectFieldElementsEqual(t, "ecp_nistz256_neg(A) was incorrect.", b,
    236                                 ret)) {
    237     return false;
    238   }
    239 
    240   OPENSSL_memcpy(ret, a, sizeof(ret));
    241   ecp_nistz256_neg(ret, ret);
    242   if (!ExpectFieldElementsEqual(
    243           t, "In-place ecp_nistz256_neg(A) was incorrect.", b, ret)) {
    244     return false;
    245   }
    246 
    247   // Test that -B = A.
    248   ecp_nistz256_neg(ret, b);
    249   if (!ExpectFieldElementsEqual(t, "ecp_nistz256_neg(B) was incorrect.", a,
    250                                 ret)) {
    251     return false;
    252   }
    253 
    254   OPENSSL_memcpy(ret, b, sizeof(ret));
    255   ecp_nistz256_neg(ret, ret);
    256   if (!ExpectFieldElementsEqual(
    257           t, "In-place ecp_nistz256_neg(B) was incorrect.", a, ret)) {
    258     return false;
    259   }
    260 
    261   return true;
    262 }
    263 
    264 static bool TestMulMont(FileTest *t) {
    265   BN_ULONG a[P256_LIMBS], b[P256_LIMBS], result[P256_LIMBS];
    266   if (!GetFieldElement(t, a, "A") ||
    267       !GetFieldElement(t, b, "B") ||
    268       !GetFieldElement(t, result, "Result")) {
    269     return false;
    270   }
    271 
    272   BN_ULONG ret[P256_LIMBS];
    273   ecp_nistz256_mul_mont(ret, a, b);
    274   if (!ExpectFieldElementsEqual(t, "ecp_nistz256_mul_mont(A, B) was incorrect.",
    275                                 result, ret)) {
    276     return false;
    277   }
    278 
    279   ecp_nistz256_mul_mont(ret, b, a);
    280   if (!ExpectFieldElementsEqual(t, "ecp_nistz256_mul_mont(B, A) was incorrect.",
    281                                 result, ret)) {
    282     return false;
    283   }
    284 
    285   OPENSSL_memcpy(ret, a, sizeof(ret));
    286   ecp_nistz256_mul_mont(ret, ret, b);
    287   if (!ExpectFieldElementsEqual(
    288           t, "ecp_nistz256_mul_mont(ret = A, B) was incorrect.", result, ret)) {
    289     return false;
    290   }
    291 
    292   OPENSSL_memcpy(ret, a, sizeof(ret));
    293   ecp_nistz256_mul_mont(ret, b, ret);
    294   if (!ExpectFieldElementsEqual(
    295           t, "ecp_nistz256_mul_mont(B, ret = A) was incorrect.", result, ret)) {
    296     return false;
    297   }
    298 
    299   OPENSSL_memcpy(ret, b, sizeof(ret));
    300   ecp_nistz256_mul_mont(ret, a, ret);
    301   if (!ExpectFieldElementsEqual(
    302           t, "ecp_nistz256_mul_mont(A, ret = B) was incorrect.", result, ret)) {
    303     return false;
    304   }
    305 
    306   OPENSSL_memcpy(ret, b, sizeof(ret));
    307   ecp_nistz256_mul_mont(ret, ret, a);
    308   if (!ExpectFieldElementsEqual(
    309           t, "ecp_nistz256_mul_mont(ret = B, A) was incorrect.", result, ret)) {
    310     return false;
    311   }
    312 
    313   if (OPENSSL_memcmp(a, b, sizeof(a)) == 0) {
    314     ecp_nistz256_sqr_mont(ret, a);
    315     if (!ExpectFieldElementsEqual(t, "ecp_nistz256_sqr_mont(A) was incorrect.",
    316                                   result, ret)) {
    317       return false;
    318     }
    319 
    320     OPENSSL_memcpy(ret, a, sizeof(ret));
    321     ecp_nistz256_sqr_mont(ret, ret);
    322     if (!ExpectFieldElementsEqual(
    323             t, "ecp_nistz256_sqr_mont(ret = A) was incorrect.", result, ret)) {
    324       return false;
    325     }
    326   }
    327 
    328   return true;
    329 }
    330 
    331 static bool TestFromMont(FileTest *t) {
    332   BN_ULONG a[P256_LIMBS], result[P256_LIMBS];
    333   if (!GetFieldElement(t, a, "A") ||
    334       !GetFieldElement(t, result, "Result")) {
    335     return false;
    336   }
    337 
    338   BN_ULONG ret[P256_LIMBS];
    339   ecp_nistz256_from_mont(ret, a);
    340   if (!ExpectFieldElementsEqual(t, "ecp_nistz256_from_mont(A) was incorrect.",
    341                                 result, ret)) {
    342     return false;
    343   }
    344 
    345   OPENSSL_memcpy(ret, a, sizeof(ret));
    346   ecp_nistz256_from_mont(ret, ret);
    347   if (!ExpectFieldElementsEqual(
    348           t, "ecp_nistz256_from_mont(ret = A) was incorrect.", result, ret)) {
    349     return false;
    350   }
    351 
    352   return true;
    353 }
    354 
    355 static bool TestPointAdd(FileTest *t) {
    356   P256_POINT a, b;
    357   P256_POINT_AFFINE result;
    358   if (!GetFieldElement(t, a.X, "A.X") ||
    359       !GetFieldElement(t, a.Y, "A.Y") ||
    360       !GetFieldElement(t, a.Z, "A.Z") ||
    361       !GetFieldElement(t, b.X, "B.X") ||
    362       !GetFieldElement(t, b.Y, "B.Y") ||
    363       !GetFieldElement(t, b.Z, "B.Z") ||
    364       !GetFieldElement(t, result.X, "Result.X") ||
    365       !GetFieldElement(t, result.Y, "Result.Y")) {
    366     return false;
    367   }
    368 
    369   P256_POINT ret;
    370   ecp_nistz256_point_add(&ret, &a, &b);
    371   if (!ExpectPointsEqual(t, "ecp_nistz256_point_add(A, B) was incorrect.",
    372                          &result, &ret)) {
    373     return false;
    374   }
    375 
    376   ecp_nistz256_point_add(&ret, &b, &a);
    377   if (!ExpectPointsEqual(t, "ecp_nistz256_point_add(B, A) was incorrect.",
    378                          &result, &ret)) {
    379     return false;
    380   }
    381 
    382   OPENSSL_memcpy(&ret, &a, sizeof(ret));
    383   ecp_nistz256_point_add(&ret, &ret, &b);
    384   if (!ExpectPointsEqual(t, "ecp_nistz256_point_add(ret = A, B) was incorrect.",
    385                          &result, &ret)) {
    386     return false;
    387   }
    388 
    389   OPENSSL_memcpy(&ret, &a, sizeof(ret));
    390   ecp_nistz256_point_add(&ret, &b, &ret);
    391   if (!ExpectPointsEqual(t, "ecp_nistz256_point_add(B, ret = A) was incorrect.",
    392                          &result, &ret)) {
    393     return false;
    394   }
    395 
    396   OPENSSL_memcpy(&ret, &b, sizeof(ret));
    397   ecp_nistz256_point_add(&ret, &a, &ret);
    398   if (!ExpectPointsEqual(t, "ecp_nistz256_point_add(ret = A, B) was incorrect.",
    399                          &result, &ret)) {
    400     return false;
    401   }
    402 
    403   OPENSSL_memcpy(&ret, &b, sizeof(ret));
    404   ecp_nistz256_point_add(&ret, &ret, &a);
    405   if (!ExpectPointsEqual(t, "ecp_nistz256_point_add(ret = B, A) was incorrect.",
    406                          &result, &ret)) {
    407     return false;
    408   }
    409 
    410   P256_POINT_AFFINE a_affine, b_affine, infinity;
    411   OPENSSL_memset(&infinity, 0, sizeof(infinity));
    412   if (!PointToAffine(&a_affine, &a) ||
    413       !PointToAffine(&b_affine, &b)) {
    414     return false;
    415   }
    416 
    417   // ecp_nistz256_point_add_affine does not work when a == b unless doubling the
    418   // point at infinity.
    419   if (OPENSSL_memcmp(&a_affine, &b_affine, sizeof(a_affine)) != 0 ||
    420       OPENSSL_memcmp(&a_affine, &infinity, sizeof(a_affine)) == 0) {
    421     ecp_nistz256_point_add_affine(&ret, &a, &b_affine);
    422     if (!ExpectPointsEqual(t,
    423                            "ecp_nistz256_point_add_affine(A, B) was incorrect.",
    424                            &result, &ret)) {
    425       return false;
    426     }
    427 
    428     OPENSSL_memcpy(&ret, &a, sizeof(ret));
    429     ecp_nistz256_point_add_affine(&ret, &ret, &b_affine);
    430     if (!ExpectPointsEqual(
    431             t, "ecp_nistz256_point_add_affine(ret = A, B) was incorrect.",
    432             &result, &ret)) {
    433       return false;
    434     }
    435 
    436     ecp_nistz256_point_add_affine(&ret, &b, &a_affine);
    437     if (!ExpectPointsEqual(t,
    438                            "ecp_nistz256_point_add_affine(B, A) was incorrect.",
    439                            &result, &ret)) {
    440       return false;
    441     }
    442 
    443     OPENSSL_memcpy(&ret, &b, sizeof(ret));
    444     ecp_nistz256_point_add_affine(&ret, &ret, &a_affine);
    445     if (!ExpectPointsEqual(
    446             t, "ecp_nistz256_point_add_affine(ret = B, A) was incorrect.",
    447             &result, &ret)) {
    448       return false;
    449     }
    450   }
    451 
    452   if (OPENSSL_memcmp(&a, &b, sizeof(a)) == 0) {
    453     ecp_nistz256_point_double(&ret, &a);
    454     if (!ExpectPointsEqual(t, "ecp_nistz256_point_double(A) was incorrect.",
    455                            &result, &ret)) {
    456       return false;
    457     }
    458 
    459     ret = a;
    460     ecp_nistz256_point_double(&ret, &ret);
    461     if (!ExpectPointsEqual(
    462             t, "In-place ecp_nistz256_point_double(A) was incorrect.", &result,
    463             &ret)) {
    464       return false;
    465     }
    466   }
    467 
    468   return true;
    469 }
    470 
    471 int main(int argc, char **argv) {
    472   if (argc != 2) {
    473     fprintf(stderr, "%s TEST_FILE\n", argv[0]);
    474     return 1;
    475   }
    476 
    477   if (!TestSelectW5() ||
    478       !TestSelectW7()) {
    479     return 1;
    480   }
    481 
    482   return FileTestMain([](FileTest *t, void *) -> bool {
    483     if (t->GetParameter() == "Negate") {
    484       return TestNegate(t);
    485     }
    486     if (t->GetParameter() == "MulMont") {
    487       return TestMulMont(t);
    488     }
    489     if (t->GetParameter() == "FromMont") {
    490       return TestFromMont(t);
    491     }
    492     if (t->GetParameter() == "PointAdd") {
    493       return TestPointAdd(t);
    494     }
    495 
    496     t->PrintLine("Unknown test type: %s", t->GetParameter().c_str());
    497     return false;
    498   }, nullptr, argv[1]);
    499 }
    500 
    501 #else
    502 
    503 int main() {
    504   printf("PASS\n");
    505   return 0;
    506 }
    507 
    508 #endif
    509