tools/hitag2crack/crack2/ht2crack2search_multi.c

   1 /*
   2  * ht2crack2search.c
   3  * this searches the sorted tables for the given RNG data, retrieves the matching
   4  * PRNG state, checks it is correct, and then rolls back the PRNG to recover the key
   5  */
   6
   7 #include "ht2crackutils.h"
   8 #include <pthread.h>
   9 #include <stdbool.h>
  10 #include <strings.h>
  11
  12 // a global mutex to prevent interlaced printing from different threads
  13 pthread_mutex_t print_lock;
  14
  15 static int global_found = 0;
  16 static int thread_count = 2;
  17 static int g_bitoffset = 0;
  18 static uint8_t g_rngmatch[6];
  19 static uint8_t g_rngstate[6];
  20
  21 typedef struct {
  22     int len;
  23     uint8_t *data;
  24 }  rngdata_t;
  25
  26 typedef struct thread_args {
  27     int thread;
  28     int idx;
  29     rngdata_t r;
  30 } targs;
  31
  32 #define AEND            "\x1b[0m"
  33 #define _RED_(s)        "\x1b[31m" s AEND
  34 #define _GREEN_(s)      "\x1b[32m" s AEND
  35 #define _YELLOW_(s)     "\x1b[33m" s AEND
  36 #define _CYAN_(s)       "\x1b[36m" s AEND
  37
  38 #define INPUTFILE       "sorted/%02x/%02x.bin"
  39 #define DATASIZE        10
  40
  41 static void print_hex(const uint8_t *data, const size_t len) {
  42     if (data == NULL || len == 0) return;
  43
  44     for (size_t i = 0; i < len; i++) {
  45         printf("%02X", data[i]);
  46     }
  47
  48     printf("\n");
  49 }
  50
  51 static int datacmp(const void *p1, const void *p2) {
  52     unsigned char *d1 = (unsigned char *)p1;
  53     unsigned char *d2 = (unsigned char *)p2;
  54
  55     return memcmp(d1, d2, DATASIZE - 6);
  56 }
  57
  58 static int loadrngdata(rngdata_t *r, char *file) {
  59     int fd;
  60     int i, j;
  61     int nibble;
  62     struct stat filestat;
  63     unsigned char *data;
  64
  65     if (!r || !file) {
  66         printf("loadrngdata: invalid params\n");
  67         return 0;
  68     }
  69
  70     fd = open(file, O_RDONLY);
  71
  72     if (fd <= 0) {
  73         printf("cannot open file %s\n", file);
  74         exit(1);
  75     }
  76
  77     if (fstat(fd, &filestat)) {
  78         printf("cannot stat file %s\n", file);
  79         exit(1);
  80     }
  81
  82     if (filestat.st_size < 6) {
  83         printf("file %s is too small\n", file);
  84         exit(1);
  85     }
  86
  87     data = mmap((caddr_t)0, filestat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
  88     if (data == MAP_FAILED) {
  89         printf("cannot mmap file %s\n", file);
  90         exit(1);
  91     }
  92
  93     r->len = filestat.st_size / 2;
  94 //    printf("r->len = %d\n", r->len);
  95
  96     r->data = (unsigned char *)calloc(1, r->len);
  97     if (!(r->data)) {
  98         printf("cannot calloc\n");
  99         exit(1);
 100     }
 101
 102     j = 0;
 103     nibble = 0;
 104     for (i = 0; (i < filestat.st_size) && (j < r->len); i++) {
 105         if ((data[i] != 0x0a) && (data[i] != 0x0d) && (data[i] != 0x20)) {
 106             if (!nibble) {
 107                 r->data[j] = hex2bin(data[i]) << 4;
 108                 nibble = 1;
 109             } else {
 110                 r->data[j] |= hex2bin(data[i]);
 111                 nibble = 0;
 112                 j++;
 113             }
 114         }
 115     }
 116
 117     r->len = j;
 118
 119     munmap(data, filestat.st_size);
 120     close(fd);
 121
 122     return 1;
 123 }
 124
 125 static int makecand(unsigned char *c, rngdata_t *r, int bitoffset) {
 126     int bytenum;
 127     int bitnum;
 128     int i;
 129
 130     if (!c || !r || (bitoffset > ((r->len * 8) - 48))) {
 131         printf("makecand: invalid params\n");
 132         return 0;
 133     }
 134
 135     bytenum = bitoffset / 8;
 136     bitnum = bitoffset % 8;
 137
 138     for (i = 0; i < 6; i++) {
 139         if (!bitnum) {
 140             c[i] = r->data[bytenum + i];
 141         } else {
 142             c[i] = (r->data[bytenum + i] << bitnum) | (r->data[bytenum + i + 1] >> (8 - bitnum));
 143         }
 144     }
 145
 146     return 1;
 147 }
 148
 149 // test the candidate against the next or previous rng data
 150 static int testcand(const unsigned char *f, unsigned char *rt, int fwd) {
 151     Hitag_State hstate;
 152     int i;
 153     uint32_t ks1;
 154     uint32_t ks2;
 155     unsigned char buf[6];
 156
 157     // build the prng state at the candidate
 158     hstate.shiftreg = 0;
 159     for (i = 0; i < 6; i++) {
 160         hstate.shiftreg = (hstate.shiftreg << 8) | f[i + 4];
 161     }
 162     buildlfsr(&hstate);
 163
 164     if (fwd) {
 165         // roll forwards 48 bits
 166         hitag2_nstep(&hstate, 48);
 167     } else {
 168         // roll backwards 48 bits
 169         rollback(&hstate, 48);
 170         buildlfsr(&hstate);
 171     }
 172
 173     // get 48 bits of RNG from the rolled to state
 174     ks1 = hitag2_nstep(&hstate, 24);
 175     ks2 = hitag2_nstep(&hstate, 24);
 176
 177     writebuf(buf, ks1, 3);
 178     writebuf(buf + 3, ks2, 3);
 179
 180     // compare them
 181     if (!memcmp(buf, rt, 6)) {
 182         return 1;
 183     } else {
 184         return 0;
 185     }
 186 }
 187
 188 static int searchcand(unsigned char *c, unsigned char *rt, int fwd, unsigned char *m, unsigned char *s) {
 189
 190     if (!c || !rt || !m || !s) {
 191         printf("searchcand: invalid params\n");
 192         return 0;
 193     }
 194
 195     char file[64];
 196     unsigned char *data;
 197     unsigned char item[10];
 198     unsigned char *found = NULL;
 199
 200     snprintf(file, sizeof(file), INPUTFILE, c[0], c[1]);
 201
 202     int fd = open(file, O_RDONLY);
 203     if (fd <= 0) {
 204         printf("cannot open table file %s\n", file);
 205         exit(1);
 206     }
 207
 208     struct stat filestat;
 209     if (fstat(fd, &filestat)) {
 210         printf("cannot stat file %s\n", file);
 211         exit(1);
 212     }
 213
 214     data = mmap((caddr_t)0, filestat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
 215     if (data == MAP_FAILED) {
 216         printf("cannot mmap file %s\n", file);
 217         exit(1);
 218     }
 219
 220     memcpy(item, c + 2, 4);
 221
 222     found = (unsigned char *)bsearch(item, data, filestat.st_size / DATASIZE, DATASIZE, datacmp);
 223
 224     if (found) {
 225
 226         // our candidate is in the table
 227         // go backwards and see if there are other matches
 228         while (((found - data) >= DATASIZE) && (!memcmp(found - DATASIZE, item, 4))) {
 229             found = found - DATASIZE;
 230         }
 231
 232         // now test all matches
 233         while (((found - data) <= (filestat.st_size - DATASIZE)) && (!memcmp(found, item, 4))) {
 234             if (testcand(found, rt, fwd)) {
 235                 memcpy(m, c, 2);
 236                 memcpy(m + 2, found, 4);
 237                 memcpy(s, found + 4, 6);
 238
 239                 munmap(data, filestat.st_size);
 240                 close(fd);
 241                 return 1;
 242             }
 243
 244             found = found + DATASIZE;
 245         }
 246     }
 247
 248     munmap(data, filestat.st_size);
 249     close(fd);
 250
 251     return 0;
 252
 253 }
 254
 255 static void *brute_thread(void *arguments) {
 256
 257     struct thread_args *args = (struct thread_args *) arguments;
 258
 259     rngdata_t r;
 260     r.len = args->r.len;
 261     r.data = calloc(1, args->r.len);
 262     memcpy(r.data, args->r.data, args->r.len);
 263
 264     int bitlen = (r.len * 8);
 265
 266     for (int i = args->idx; i <= bitlen - 48; i += thread_count) {
 267
 268         // print progress
 269         if ((i % 100) == 0) {
 270             pthread_mutex_lock(&print_lock);
 271             printf("searching on bit %d\n", i);
 272             pthread_mutex_unlock(&print_lock);
 273         }
 274
 275         if (__atomic_load_n(&global_found, __ATOMIC_ACQUIRE) == 1) {
 276             break;
 277         }
 278
 279         uint8_t l_cand[6] = {0};
 280         if (makecand(l_cand, &r, i) == 0) {
 281             pthread_mutex_lock(&print_lock);
 282             printf("cannot makecand, %d\n", i);
 283             pthread_mutex_unlock(&print_lock);
 284             break;
 285         }
 286 //        printf("cand: %02x %02x %02x %02x %02x %02x : ", cand[0], cand[1], cand[2], cand[3], cand[4], cand[5]);
 287 //        printbin(cand);
 288
 289         int fwd = 0;
 290         /* make following or preceding RNG test data to confirm match */
 291         uint8_t l_rngtest[6] = {0};
 292         if (i < (bitlen - 96)) {
 293
 294             if (makecand(l_rngtest, &r, i + 48) == 0) {
 295                 pthread_mutex_lock(&print_lock);
 296                 printf("cannot makecand rngtest %d + 48\n", i);
 297                 pthread_mutex_unlock(&print_lock);
 298                 break;
 299             }
 300             fwd = 1;
 301
 302         } else {
 303
 304             if (makecand(l_rngtest, &r, i - 48) == 0) {
 305                 pthread_mutex_lock(&print_lock);
 306                 printf("cannot makecand rngtest %d - 48\n", i);
 307                 pthread_mutex_unlock(&print_lock);
 308                 break;
 309             }
 310             fwd = 0;
 311         }
 312
 313         uint8_t l_match[6] ;
 314         uint8_t l_state[6] ;
 315         if (searchcand(l_cand, l_rngtest, fwd, l_match, l_state)) {
 316             __sync_fetch_and_add(&global_found, 1);
 317             __sync_fetch_and_add(&g_bitoffset, i);
 318             memcpy(g_rngmatch, l_match, sizeof(l_match));
 319             memcpy(g_rngstate, l_state, sizeof(l_state));
 320             break;
 321         }
 322     }
 323
 324     free(r.data);
 325     free(args);
 326     return NULL;
 327 }
 328
 329 static void rollbackrng(Hitag_State *hstate, const unsigned char *s, int offset) {
 330     int i;
 331
 332     if (!s) {
 333         printf("rollbackrng: invalid params\n");
 334         return;
 335     }
 336
 337     // build prng at recovered offset
 338     hstate->shiftreg = 0;
 339     for (i = 0; i < 6; i++) {
 340         hstate->shiftreg = (hstate->shiftreg << 8) | s[i];
 341     }
 342
 343     printf("recovered prng state at offset %d:\n", offset);
 344     printstate(hstate);
 345
 346     // rollback to state after auth
 347     rollback(hstate, offset);
 348
 349     // rollback through auth (aR, p3)
 350     rollback(hstate, 64);
 351
 352     printf("prng state after initialisation:\n");
 353     printstate(hstate);
 354
 355
 356 }
 357
 358 static uint64_t recoverkey(Hitag_State *hstate, char *uidstr, char *nRstr) {
 359     uint64_t key;
 360     uint64_t keyupper;
 361     uint32_t uid;
 362     uint32_t uidtmp;
 363     uint32_t nRenc;
 364     uint32_t nR;
 365     uint32_t nRxork;
 366     uint32_t b = 0;
 367     int i;
 368
 369     // key lower 16 bits are lower 16 bits of prng state
 370     key = hstate->shiftreg & 0xffff;
 371     nRxork = (hstate->shiftreg >> 16) & 0xffffffff;
 372     uid = rev32(hexreversetoulong(uidstr));
 373     nRenc = rev32(hexreversetoulong(nRstr));
 374
 375     uidtmp = uid;
 376     // rollback and extract bits b
 377     for (i = 0; i < 32; i++) {
 378         hstate->shiftreg = ((hstate->shiftreg) << 1) | ((uidtmp >> 31) & 0x1);
 379         uidtmp = uidtmp << 1;
 380         b = (b << 1) | fnf(hstate->shiftreg);
 381     }
 382
 383     printf("end state:\n");
 384     printstate(hstate);
 385     printf("b:\t\t");
 386     printbin2(b, 32);
 387     printf("\n");
 388     printf("nRenc:\t\t");
 389     printbin2(nRenc, 32);
 390     printf("\n");
 391
 392     nR = nRenc ^ b;
 393
 394     printf("nR:\t\t");
 395     printbin2(nR, 32);
 396     printf("\n");
 397
 398     keyupper = nRxork ^ nR;
 399     key = key | (keyupper << 16);
 400     printf("key:\t\t");
 401     printbin2(key, 48);
 402     printf("\n");
 403
 404     return key;
 405 }
 406
 407
 408 int main(int argc, char *argv[]) {
 409
 410     if (argc < 4) {
 411         printf("%s rngdatafile UID nR\n", argv[0]);
 412         exit(1);
 413     }
 414
 415     rngdata_t rng;
 416     if (!loadrngdata(&rng, argv[1])) {
 417         printf("loadrngdata failed\n");
 418         exit(1);
 419     }
 420
 421     char *uidstr;
 422     if (!strncmp(argv[2], "0x", 2)) {
 423         uidstr = argv[2] + 2;
 424     } else {
 425         uidstr = argv[2];
 426     }
 427
 428     char *nRstr;
 429     if (!strncmp(argv[3], "0x", 2)) {
 430         nRstr = argv[3] + 2;
 431     } else {
 432         nRstr = argv[3];
 433     }
 434
 435 #if !defined(_WIN32) || !defined(__WIN32__)
 436     thread_count = sysconf(_SC_NPROCESSORS_CONF);
 437     if (thread_count < 2)
 438         thread_count = 2;
 439 #endif  /* _WIN32 */
 440
 441     printf("\nBruteforce using " _YELLOW_("%d") " threads\n", thread_count);
 442
 443     pthread_t threads[thread_count];
 444     void *res;
 445
 446     // create a mutex to avoid interlacing print commands from our different threads
 447     pthread_mutex_init(&print_lock, NULL);
 448
 449     // findmatch(&rng, rngmatch, rngstate, &bitoffset)
 450
 451     // threads
 452     for (int i = 0; i < thread_count; ++i) {
 453         targs *a = calloc(1, rng.len + sizeof(targs));
 454         a->r.data = calloc(1, rng.len);
 455
 456         a->thread = i;
 457         a->idx = i;
 458         a->r.len = rng.len;
 459         memcpy(a->r.data, rng.data, rng.len);
 460
 461         pthread_create(&threads[i], NULL, brute_thread, (void *)a);
 462     }
 463
 464     // wait for threads to terminate:
 465     for (int i = 0; i < thread_count; ++i) {
 466         pthread_join(threads[i], &res);
 467         free(res);
 468     }
 469
 470     if (global_found == false) {
 471         printf("\n" _RED_("!!!") " failed to find a key\n\n");
 472     } else {
 473         printf("Found match:\n");
 474         printf("rngmatch.... ");  print_hex(g_rngmatch, sizeof(g_rngmatch));
 475         printf("rngstate.... ");  print_hex(g_rngstate, sizeof(g_rngstate));
 476         printf("bitoffset... %d\n", g_bitoffset);
 477
 478         Hitag_State hstate;
 479         rollbackrng(&hstate, g_rngstate, g_bitoffset);
 480
 481         uint64_t keyrev = recoverkey(&hstate, uidstr, nRstr);
 482         uint64_t key = rev64(keyrev);
 483
 484         printf("keyrev:\t\t");
 485         printbin2(key, 48);
 486         printf("\n");
 487
 488         printf("KEY:\t\t");
 489         for (int i = 0; i < 6; i++) {
 490             printf("%02X", (int)(key & 0xff));
 491             key = key >> 8;
 492         }
 493         printf("\n");
 494     }
 495     // clean up mutex
 496     pthread_mutex_destroy(&print_lock);
 497
 498     free(rng.data);
 499     return 0;
 500 }
 501
 502