test.c (8151B)
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 }