ed25519/ed25519-donna/test.c

   1 /*
   2         Validate ed25519 implementation against the official test vectors from
   3         http://ed25519.cr.yp.to/software.html
   4 */
   5
   6 #include <stdio.h>
   7 #include <string.h>
   8 #include "ed25519.h"
   9
  10 #include "test-ticks.h"
  11
  12 static void
  13 edassert(int check, int round, const char *failreason) {
  14         if (check)
  15                 return;
  16         printf("round %d, %s\n", round, failreason);
  17         exit(1);
  18 }
  19
  20 static void
  21 edassert_die(const unsigned char *a, const unsigned char *b, size_t len, int round, const char *failreason) {
  22         size_t i;
  23         if (round > 0)
  24                 printf("round %d, %s\n", round, failreason);
  25         else
  26                 printf("%s\n", failreason);
  27         printf("want: "); for (i = 0; i < len; i++) printf("%02x,", a[i]); printf("\n");
  28         printf("got : "); for (i = 0; i < len; i++) printf("%02x,", b[i]); printf("\n");
  29         printf("diff: "); for (i = 0; i < len; i++) if (a[i] ^ b[i]) printf("%02x,", a[i] ^ b[i]); else printf("  ,"); printf("\n\n");
  30         exit(1);
  31 }
  32
  33 static void
  34 edassert_equal(const unsigned char *a, const unsigned char *b, size_t len, const char *failreason) {
  35         if (memcmp(a, b, len) == 0)
  36                 return;
  37         edassert_die(a, b, len, -1, failreason);
  38 }
  39
  40 static void
  41 edassert_equal_round(const unsigned char *a, const unsigned char *b, size_t len, int round, const char *failreason) {
  42         if (memcmp(a, b, len) == 0)
  43                 return;
  44         edassert_die(a, b, len, round, failreason);
  45 }
  46
  47
  48 /* test data */
  49 typedef struct test_data_t {
  50         unsigned char sk[32], pk[32], sig[64];
  51         const char *m;
  52 } test_data;
  53
  54
  55 test_data dataset[] = {
  56 #include "regression.h"
  57 };
  58
  59 /* result of the curve25519 scalarmult ((|255| * basepoint) * basepoint)... 1024 times */
  60 const curved25519_key curved25519_expected = {
  61         0xac,0xce,0x24,0xb1,0xd4,0xa2,0x36,0x21,
  62         0x15,0xe2,0x3e,0x84,0x3c,0x23,0x2b,0x5f,
  63         0x95,0x6c,0xc0,0x7b,0x95,0x82,0xd7,0x93,
  64         0xd5,0x19,0xb6,0xf1,0xfb,0x96,0xd6,0x04
  65 };
  66
  67
  68 /* from ed25519-donna-batchverify.h */
  69 extern unsigned char batch_point_buffer[3][32];
  70
  71 /* y coordinate of the final point from 'amd64-51-30k' with the same random generator */
  72 static const unsigned char batch_verify_y[32] = {
  73         0x51,0xe7,0x68,0xe0,0xf7,0xa1,0x88,0x45,
  74         0xde,0xa1,0xcb,0xd9,0x37,0xd4,0x78,0x53,
  75         0x1b,0x95,0xdb,0xbe,0x66,0x59,0x29,0x3b,
  76         0x94,0x51,0x2f,0xbc,0x0d,0x66,0xba,0x3f
  77 };
  78
  79 /*
  80 static const unsigned char batch_verify_y[32] = {
  81         0x5c,0x63,0x96,0x26,0xca,0xfe,0xfd,0xc4,
  82         0x2d,0x11,0xa8,0xe4,0xc4,0x46,0x42,0x97,
  83         0x97,0x92,0xbe,0xe0,0x3c,0xef,0x96,0x01,
  84         0x50,0xa1,0xcc,0x8f,0x50,0x85,0x76,0x7d
  85 };
  86
  87 Introducing the 128 bit r scalars to the heap _before_ the largest scalar
  88 fits in to 128 bits alters the heap shape and produces a different,
  89 yet still neutral/valid y/z value.
  90
  91 This was the value of introducing the r scalars when the largest scalar fit
  92 in to 135-256 bits. You can produce it with amd64-64-24k / amd64-51-32k
  93 with the random sequence used in the first pass by changing
  94
  95     unsigned long long hlen=((npoints+1)/2)|1;
  96
  97 to
  98
  99     unsigned long long hlen=npoints;
 100
 101 in ge25519_multi_scalarmult.c
 102
 103 ed25519-donna-batchverify.h has been modified to match the
 104 default amd64-64-24k / amd64-51-32k behaviour
 105 */
 106
 107
 108
 109 /* batch test */
 110 #define test_batch_count 64
 111 #define test_batch_rounds 96
 112
 113 typedef enum batch_test_t {
 114         batch_no_errors = 0,
 115         batch_wrong_message = 1,
 116         batch_wrong_pk = 2,
 117         batch_wrong_sig = 3
 118 } batch_test;
 119
 120 static int
 121 test_batch_instance(batch_test type, uint64_t *ticks) {
 122         ed25519_secret_key sks[test_batch_count];
 123         ed25519_public_key pks[test_batch_count];
 124         ed25519_signature sigs[test_batch_count];
 125         unsigned char messages[test_batch_count][128];
 126         size_t message_lengths[test_batch_count];
 127         const unsigned char *message_pointers[test_batch_count];
 128         const unsigned char *pk_pointers[test_batch_count];
 129         const unsigned char *sig_pointers[test_batch_count];
 130         int valid[test_batch_count], ret, validret;
 131         size_t i;
 132         uint64_t t;
 133
 134         /* generate keys */
 135         for (i = 0; i < test_batch_count; i++) {
 136                 ed25519_randombytes_unsafe(sks[i], sizeof(sks[i]));
 137                 ed25519_publickey(sks[i], pks[i]);
 138                 pk_pointers[i] = pks[i];
 139         }
 140
 141         /* generate messages */
 142         ed25519_randombytes_unsafe(messages, sizeof(messages));
 143         for (i = 0; i < test_batch_count; i++) {
 144                 message_pointers[i] = messages[i];
 145                 message_lengths[i] = (i & 127) + 1;
 146         }
 147
 148         /* sign messages */
 149         for (i = 0; i < test_batch_count; i++) {
 150                 ed25519_sign(message_pointers[i], message_lengths[i], sks[i], pks[i], sigs[i]);
 151                 sig_pointers[i] = sigs[i];
 152         }
 153
 154         validret = 0;
 155         if (type == batch_wrong_message) {
 156                 message_pointers[0] = message_pointers[1];
 157                 validret = 1|2;
 158         } else if (type == batch_wrong_pk) {
 159                 pk_pointers[0] = pk_pointers[1];
 160                 validret = 1|2;
 161         } else if (type == batch_wrong_sig) {
 162                 sig_pointers[0] = sig_pointers[1];
 163                 validret = 1|2;
 164         }
 165
 166         /* batch verify */
 167         t = get_ticks();
 168         ret = ed25519_sign_open_batch(message_pointers, message_lengths, pk_pointers, sig_pointers, test_batch_count, valid);
 169         *ticks = get_ticks() - t;
 170         edassert_equal((unsigned char *)&validret, (unsigned char *)&ret, sizeof(int), "batch return code");
 171         for (i = 0; i < test_batch_count; i++) {
 172                 validret = ((type == batch_no_errors) || (i != 0)) ? 1 : 0;
 173                 edassert_equal((unsigned char *)&validret, (unsigned char *)&valid[i], sizeof(int), "individual batch return code");
 174         }
 175         return ret;
 176 }
 177
 178 static void
 179 test_batch(void) {
 180         uint64_t dummy_ticks, ticks[test_batch_rounds], best = maxticks, sum;
 181         size_t i, count;
 182
 183         /* check the first pass for the expected result */
 184         test_batch_instance(batch_no_errors, &dummy_ticks);
 185         edassert_equal(batch_verify_y, batch_point_buffer[1], 32, "failed to generate expected result");
 186
 187         /* make sure ge25519_multi_scalarmult_vartime throws an error on the entire batch with wrong data */
 188         for (i = 0; i < 4; i++) {
 189                 test_batch_instance(batch_wrong_message, &dummy_ticks);
 190                 test_batch_instance(batch_wrong_pk, &dummy_ticks);
 191                 test_batch_instance(batch_wrong_sig, &dummy_ticks);
 192         }
 193
 194         /* speed test */
 195         for (i = 0; i < test_batch_rounds; i++) {
 196                 test_batch_instance(batch_no_errors, &ticks[i]);
 197                 if (ticks[i] < best)
 198                         best = ticks[i];
 199         }
 200
 201         /* take anything within 1% of the best time */
 202         for (i = 0, sum = 0, count = 0; i < test_batch_rounds; i++) {
 203                 if (ticks[i] < (best * 1.01)) {
 204                         sum += ticks[i];
 205                         count++;
 206                 }
 207         }
 208         printf("%.0f ticks/verification\n", (double)sum / (count * test_batch_count));
 209 }
 210
 211 static void
 212 test_main(void) {
 213         int i, res;
 214         ed25519_public_key pk;
 215         ed25519_signature sig;
 216         unsigned char forge[1024] = {'x'};
 217         curved25519_key csk[2] = {{255}};
 218         uint64_t ticks, pkticks = maxticks, signticks = maxticks, openticks = maxticks, curvedticks = maxticks;
 219
 220         for (i = 0; i < 1024; i++) {
 221                 ed25519_publickey(dataset[i].sk, pk);
 222                 edassert_equal_round(dataset[i].pk, pk, sizeof(pk), i, "public key didn't match");
 223                 ed25519_sign((unsigned char *)dataset[i].m, i, dataset[i].sk, pk, sig);
 224                 edassert_equal_round(dataset[i].sig, sig, sizeof(sig), i, "signature didn't match");
 225                 edassert(!ed25519_sign_open((unsigned char *)dataset[i].m, i, pk, sig), i, "failed to open message");
 226
 227                 memcpy(forge, dataset[i].m, i);
 228                 if (i)
 229                         forge[i - 1] += 1;
 230
 231                 edassert(ed25519_sign_open(forge, (i) ? i : 1, pk, sig), i, "opened forged message");
 232         }
 233
 234         for (i = 0; i < 1024; i++)
 235                 curved25519_scalarmult_basepoint(csk[(i & 1) ^ 1], csk[i & 1]);
 236         edassert_equal(curved25519_expected, csk[0], sizeof(curved25519_key), "curve25519 failed to generate correct value");
 237
 238         for (i = 0; i < 2048; i++) {
 239                 timeit(ed25519_publickey(dataset[0].sk, pk), pkticks)
 240                 edassert_equal_round(dataset[0].pk, pk, sizeof(pk), i, "public key didn't match");
 241                 timeit(ed25519_sign((unsigned char *)dataset[0].m, 0, dataset[0].sk, pk, sig), signticks)
 242                 edassert_equal_round(dataset[0].sig, sig, sizeof(sig), i, "signature didn't match");
 243                 timeit(res = ed25519_sign_open((unsigned char *)dataset[0].m, 0, pk, sig), openticks)
 244                 edassert(!res, 0, "failed to open message");
 245                 timeit(curved25519_scalarmult_basepoint(csk[1], csk[0]), curvedticks);
 246         }
 247
 248         printf("%.0f ticks/public key generation\n", (double)pkticks);
 249         printf("%.0f ticks/signature\n", (double)signticks);
 250         printf("%.0f ticks/signature verification\n", (double)openticks);
 251         printf("%.0f ticks/curve25519 basepoint scalarmult\n", (double)curvedticks);
 252 }
 253
 254 int
 255 main(void) {
 256         test_main();
 257         test_batch();
 258         return 0;
 259 }
 260