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 
TestSelectW5()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 
TestSelectW7()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 
GetFieldElement(FileTest * t,BN_ULONG out[P256_LIMBS],const char * name)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 
FieldElementToString(const BN_ULONG a[P256_LIMBS])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 
ExpectFieldElementsEqual(FileTest * t,const char * message,const BN_ULONG expected[P256_LIMBS],const BN_ULONG actual[P256_LIMBS])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 
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   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 
ExpectPointsEqual(FileTest * t,const char * message,const P256_POINT_AFFINE * expected,const P256_POINT * point)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 
TestNegate(FileTest * t)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 
TestMulMont(FileTest * t)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 
TestFromMont(FileTest * t)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 
TestPointAdd(FileTest * t)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 
main(int argc,char ** argv)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 
main()503 int main() {
504   printf("PASS\n");
505   return 0;
506 }
507 
508 #endif
509