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