scripts/timeattack.c

   1 #include <stdio.h>
   2 #include <time.h>
   3
   4 #include <library.h>
   5
   6 typedef bool (*attackfn_t)(void *subj, u_char *data, size_t len);
   7
   8 static void start_timing(struct timespec *start)
   9 {
  10         clock_gettime(CLOCK_PROCESS_CPUTIME_ID, start);
  11 }
  12
  13 static u_int64_t end_timing(struct timespec *start)
  14 {
  15         struct timespec end;
  16
  17         clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
  18         return (end.tv_nsec - start->tv_nsec) +
  19                    (end.tv_sec - start->tv_sec) * 1000000000;
  20 }
  21
  22 static int intcmp(const void *a, const void *b)
  23 {
  24         return *(u_int64_t*)a - *(u_int64_t*)b;
  25 }
  26
  27 static u_int64_t median(u_int64_t *m, int count)
  28 {
  29         qsort(m, count, sizeof(u_int64_t), intcmp);
  30         return m[count / 2];
  31 }
  32
  33 static bool timeattack(attackfn_t attackfn, void *subj, size_t dlen,
  34                                            u_int iterations, u_int distance)
  35 {
  36         struct timespec start;
  37         u_char test[dlen];
  38         u_int64_t mini, maxi, t[256], m[256][10];
  39         float fastdist = 0, slowdist = 0;
  40         int i, j, k, l, byte, limit, retry = 0;
  41         int fastest = 0, slowest = 0;
  42
  43         memset(test, 0, dlen);
  44
  45         /* do some iterations to fill caches */
  46         for (i = 0; i < iterations; i++)
  47         {
  48                 attackfn(subj, test, dlen);
  49         }
  50
  51         for (byte = 0; byte < dlen;)
  52         {
  53                 memset(t, 0, sizeof(t));
  54                 memset(m, 0, sizeof(m));
  55
  56                 limit = iterations * (retry + 1);
  57
  58                 /* measure timing for all patterns in next byte */
  59                 for (k = 0; k < 10; k++)
  60                 {
  61                         for (j = 0; j < 256; j++)
  62                         {
  63                                 for (l = 0; l < 100; l++)
  64                                 {
  65                                         test[byte] = j;
  66                                         start_timing(&start);
  67                                         for (i = 0; i < limit; i++)
  68                                         {
  69                                                 attackfn(subj, test, dlen);
  70                                         }
  71                                         m[j][k] += end_timing(&start);
  72                                 }
  73                         }
  74                 }
  75
  76                 for (j = 0; j < 256; j++)
  77                 {
  78                         t[j] = median(m[j], countof(m[j]));
  79                 }
  80
  81                 /* find fastest/slowest runs */
  82                 mini = ~0;
  83                 maxi = 0;
  84                 for (j = 0; j < 256; j++)
  85                 {
  86                         if (t[j] < mini)
  87                         {
  88                                 mini = min(t[j], mini);
  89                                 fastest = j;
  90                         }
  91                         if (t[j] > maxi)
  92                         {
  93                                 maxi = max(t[j], maxi);
  94                                 slowest = j;
  95                         }
  96                 }
  97                 /* calculate distance to next result */
  98                 mini = ~0;
  99                 maxi = 0;
 100                 for (j = 0; j < 256; j++)
 101                 {
 102                         if (fastest != j && t[j] < mini)
 103                         {
 104                                 mini = min(t[j], mini);
 105                                 fastdist = (float)(t[j] - t[fastest]) / distance;
 106                         }
 107                         if (slowest != j && t[j] > maxi)
 108                         {
 109                                 maxi = max(t[j], maxi);
 110                                 slowdist = (float)(t[slowest] - t[j]) / distance;
 111                         }
 112                 }
 113                 if (fastdist > 1.0f)
 114                 {
 115                         fprintf(stderr, "byte %02d: %02x (fastest, dist %02.2f)\n",
 116                                         byte, fastest, fastdist);
 117                         test[byte] = fastest;
 118                         retry = 0;
 119                         byte++;
 120                 }
 121                 else if (slowdist > 1.0f)
 122                 {
 123                         fprintf(stderr, "byte %02d: %02x (slowest, dist %02.2f)\n",
 124                                         byte, slowest, slowdist);
 125                         test[byte] = slowest;
 126                         retry = 0;
 127                         byte++;
 128                 }
 129                 else
 130                 {
 131                         if (retry++ > 5 && byte > 0)
 132                         {
 133                                 fprintf(stderr, "distance fastest %02.2f (%02x), "
 134                                                 "slowest %02.2f (%02x), stepping back\n",
 135                                                 fastdist, fastest, slowdist, slowest);
 136                                 test[byte--] = 0;
 137                         }
 138                         else if (retry < 10)
 139                         {
 140                                 fprintf(stderr, "distance fastest %02.2f (%02x), "
 141                                                 "slowest %02.2f (%02x), retrying (%d)\n",
 142                                                 fastdist, fastest, slowdist, slowest, retry);
 143                         }
 144                         else
 145                         {
 146                                 printf("attack failed, giving up\n");
 147                                 return FALSE;
 148                         }
 149                 }
 150         }
 151         if (attackfn(subj, test, dlen))
 152         {
 153                 printf("attack successful with %b\n", test, dlen);
 154                 return TRUE;
 155         }
 156         printf("attack failed with %b\n", test, dlen);
 157         return FALSE;
 158 }
 159
 160 CALLBACK(attack_memeq1, bool,
 161         u_char *subj, u_char *data, size_t len)
 162 {
 163         return memeq(data, subj, len);
 164 }
 165
 166 CALLBACK(attack_memeq2, bool,
 167         u_char *subj, u_char *data, size_t len)
 168 {
 169         return memeq(subj, data, len);
 170 }
 171
 172 CALLBACK(attack_memeq3, bool,
 173         u_char *subj, u_char *data, size_t len)
 174 {
 175         int i;
 176
 177         for (i = 0; i < len; i++)
 178         {
 179                 if (subj[i] != data[i])
 180                 {
 181                         return FALSE;
 182                 }
 183         }
 184         return TRUE;
 185 }
 186
 187 CALLBACK(attack_memeq4, bool,
 188         u_char *subj, u_char *data, size_t len)
 189 {
 190         int i, m = 0;
 191
 192         for (i = 0; i < len; i++)
 193         {
 194                 m |= subj[i] != data[i];
 195         }
 196         return !m;
 197 }
 198
 199 CALLBACK(attack_memeq5, bool,
 200         u_char *subj, u_char *data, size_t len)
 201 {
 202         return memeq_const(subj, data, len);
 203 }
 204
 205 static bool attack_memeq(char *name, u_int iterations, u_int distance)
 206 {
 207         struct {
 208                 char *name;
 209                 attackfn_t fn;
 210         } attacks[] = {
 211                 { "memeq1", attack_memeq1 },
 212                 { "memeq2", attack_memeq2 },
 213                 { "memeq3", attack_memeq3 },
 214                 { "memeq4", attack_memeq4 },
 215                 { "memeq5", attack_memeq5 },
 216         };
 217         u_char exp[16];
 218         int i;
 219
 220         srandom(time(NULL));
 221         for (i = 0; i < sizeof(exp); i++)
 222         {
 223                 exp[i] = random();
 224         }
 225         fprintf(stderr, "attacking %b\n", exp, sizeof(exp));
 226
 227         for (i = 0; i < countof(attacks); i++)
 228         {
 229                 if (streq(name, attacks[i].name))
 230                 {
 231                         return timeattack(attacks[i].fn, exp, sizeof(exp),
 232                                                           iterations, distance);
 233                 }
 234         }
 235         return FALSE;
 236 }
 237
 238 CALLBACK(attack_chunk1, bool,
 239         u_char *subj, u_char *data, size_t len)
 240 {
 241         return chunk_equals(chunk_create(subj, len), chunk_create(data, len));
 242 }
 243
 244 CALLBACK(attack_chunk2, bool,
 245         u_char *subj, u_char *data, size_t len)
 246 {
 247         return chunk_equals_const(chunk_create(subj, len), chunk_create(data, len));
 248 }
 249
 250 static bool attack_chunk(char *name, u_int iterations, u_int distance)
 251 {
 252         struct {
 253                 char *name;
 254                 attackfn_t fn;
 255         } attacks[] = {
 256                 { "chunk1", attack_chunk1 },
 257                 { "chunk2", attack_chunk2 },
 258         };
 259         u_char exp[16];
 260         int i;
 261
 262         srandom(time(NULL));
 263         for (i = 0; i < sizeof(exp); i++)
 264         {
 265                 exp[i] = random();
 266         }
 267         fprintf(stderr, "attacking %b\n", exp, sizeof(exp));
 268
 269         for (i = 0; i < countof(attacks); i++)
 270         {
 271                 if (streq(name, attacks[i].name))
 272                 {
 273                         return timeattack(attacks[i].fn, exp, sizeof(exp),
 274                                                           iterations, distance);
 275                 }
 276         }
 277         return FALSE;
 278 }
 279
 280 CALLBACK(attack_aead, bool,
 281         aead_t *aead, u_char *data, size_t len)
 282 {
 283         u_char iv[aead->get_iv_size(aead)];
 284
 285         memset(iv, 0, sizeof(iv));
 286         return aead->decrypt(aead, chunk_create(data, len), chunk_empty,
 287                                                  chunk_from_thing(iv), NULL);
 288 }
 289
 290 static bool attack_aeads(encryption_algorithm_t alg, size_t key_size,
 291                                                  u_int iterations, u_int distance)
 292 {
 293         u_char buf[64];
 294         aead_t *aead;
 295         bool res;
 296
 297         aead = lib->crypto->create_aead(lib->crypto, alg, key_size, 0);
 298         if (!aead)
 299         {
 300                 fprintf(stderr, "creating AEAD %N failed\n",
 301                                 encryption_algorithm_names, alg);
 302                 return FALSE;
 303         }
 304         memset(buf, 0xe3, sizeof(buf));
 305         if (!aead->set_key(aead, chunk_create(buf, aead->get_key_size(aead))))
 306         {
 307                 aead->destroy(aead);
 308                 return FALSE;
 309         }
 310         memset(buf, 0, aead->get_iv_size(aead));
 311         if (!aead->encrypt(aead, chunk_create(buf, 0), chunk_empty,
 312                                            chunk_create(buf, aead->get_iv_size(aead)), NULL))
 313         {
 314                 aead->destroy(aead);
 315                 return FALSE;
 316         }
 317         fprintf(stderr, "attacking %b\n", buf, aead->get_icv_size(aead));
 318
 319         res = timeattack(attack_aead, aead, aead->get_icv_size(aead),
 320                                          iterations, distance);
 321         aead->destroy(aead);
 322         return res;
 323 }
 324
 325 CALLBACK(attack_signer, bool,
 326         signer_t *signer, u_char *data, size_t len)
 327 {
 328         return signer->verify_signature(signer, chunk_empty, chunk_create(data, len));
 329 }
 330
 331 static bool attack_signers(integrity_algorithm_t alg,
 332                                                    u_int iterations, u_int distance)
 333 {
 334         u_char buf[64];
 335         signer_t *signer;
 336         bool res;
 337
 338         signer = lib->crypto->create_signer(lib->crypto, alg);
 339         if (!signer)
 340         {
 341                 fprintf(stderr, "creating signer %N failed\n",
 342                                 integrity_algorithm_names, alg);
 343                 return FALSE;
 344         }
 345         memset(buf, 0xe3, sizeof(buf));
 346         if (!signer->set_key(signer, chunk_create(buf, signer->get_key_size(signer))))
 347         {
 348                 signer->destroy(signer);
 349                 return FALSE;
 350         }
 351         if (!signer->get_signature(signer, chunk_empty, buf))
 352         {
 353                 signer->destroy(signer);
 354                 return FALSE;
 355         }
 356         fprintf(stderr, "attacking %b\n", buf, signer->get_block_size(signer));
 357
 358         res = timeattack(attack_signer, signer, signer->get_block_size(signer),
 359                                          iterations, distance);
 360         signer->destroy(signer);
 361         return res;
 362 }
 363
 364 static bool attack_transform(char *name, u_int iterations, u_int distance)
 365 {
 366         const proposal_token_t *token;
 367
 368         token = lib->proposal->get_token(lib->proposal, name);
 369         if (!token)
 370         {
 371                 fprintf(stderr, "algorithm '%s' unknown\n", name);
 372                 return FALSE;
 373         }
 374
 375         switch (token->type)
 376         {
 377                 case ENCRYPTION_ALGORITHM:
 378                         if (encryption_algorithm_is_aead(token->algorithm))
 379                         {
 380                                 return attack_aeads(token->algorithm, token->keysize / 8,
 381                                                                         iterations, distance);
 382                         }
 383                         fprintf(stderr, "can't attack a crypter\n");
 384                         return FALSE;
 385                 case INTEGRITY_ALGORITHM:
 386                         return attack_signers(token->algorithm, iterations, distance);
 387                 default:
 388                         fprintf(stderr, "can't attack a %N\n", transform_type_names, token->type);
 389                         return FALSE;
 390         }
 391 }
 392
 393 int main(int argc, char *argv[])
 394 {
 395         library_init(NULL, "timeattack");
 396         atexit(library_deinit);
 397         lib->plugins->load(lib->plugins, getenv("PLUGINS") ?: PLUGINS);
 398
 399         if (argc < 3)
 400         {
 401                 fprintf(stderr, "usage: %s <attack> <iterations> <distance>\n", argv[0]);
 402                 fprintf(stderr, "  <attack>: memeq[1-5] / chunk[1-2] / aead / signer\n");
 403                 fprintf(stderr, "  <iterations>: number of invocations * 1000\n");
 404                 fprintf(stderr, "  <distance>: time difference in ns for a hit\n");
 405                 fprintf(stderr, "  example: %s memeq1 100 500\n", argv[0]);
 406                 fprintf(stderr, "  example: %s aes128gcm16 100 4000\n", argv[0]);
 407                 return 1;
 408         }
 409         if (strpfx(argv[1], "memeq"))
 410         {
 411                 return !attack_memeq(argv[1], atoi(argv[2]), atoi(argv[3]));
 412         }
 413         if (strpfx(argv[1], "chunk"))
 414         {
 415                 return !attack_chunk(argv[1], atoi(argv[2]), atoi(argv[3]));
 416         }
 417         return !attack_transform(argv[1], atoi(argv[2]), atoi(argv[3]));
 418 }