tools/hitag2crack/crack2/ht2crack2search.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
   9 #define INPUTFILE "sorted/%02x/%02x.bin"
  10 #define DATASIZE 10
  11
  12 struct rngdata {
  13     unsigned char *data;
  14     int len;
  15 };
  16
  17
  18
  19 static int datacmp(const void *p1, const void *p2) {
  20     unsigned char *d1 = (unsigned char *)p1;
  21     unsigned char *d2 = (unsigned char *)p2;
  22
  23     return memcmp(d1, d2, DATASIZE - 6);
  24 }
  25
  26 static int loadrngdata(struct rngdata *r, char *file) {
  27     int fd;
  28     int i, j;
  29     int nibble;
  30     struct stat filestat;
  31     unsigned char *data;
  32
  33     if (!r || !file) {
  34         printf("loadrngdata: invalid params\n");
  35         return 0;
  36     }
  37
  38     fd = open(file, O_RDONLY);
  39
  40     if (fd <= 0) {
  41         printf("cannot open file %s\n", file);
  42         exit(1);
  43     }
  44
  45     if (fstat(fd, &filestat)) {
  46         printf("cannot stat file %s\n", file);
  47         exit(1);
  48     }
  49
  50     if (filestat.st_size < 6) {
  51         printf("file %s is too small\n", file);
  52         exit(1);
  53     }
  54
  55     data = mmap((caddr_t)0, filestat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
  56     if (data == MAP_FAILED) {
  57         printf("cannot mmap file %s\n", file);
  58         exit(1);
  59     }
  60
  61     r->len = filestat.st_size / 2;
  62 //    printf("r->len = %d\n", r->len);
  63
  64     r->data = (unsigned char *)malloc(r->len);
  65     if (!(r->data)) {
  66         printf("cannot malloc\n");
  67         exit(1);
  68     }
  69
  70     j = 0;
  71     nibble = 0;
  72     for (i = 0; (i < filestat.st_size) && (j < r->len); i++) {
  73         if ((data[i] != 0x0a) && (data[i] != 0x0d) && (data[i] != 0x20)) {
  74             if (!nibble) {
  75                 r->data[j] = hex2bin(data[i]) << 4;
  76                 nibble = 1;
  77             } else {
  78                 r->data[j] |= hex2bin(data[i]);
  79                 nibble = 0;
  80                 j++;
  81             }
  82         }
  83     }
  84
  85     r->len = j;
  86
  87     munmap(data, filestat.st_size);
  88     close(fd);
  89
  90     return 1;
  91 }
  92
  93 static int makecand(unsigned char *c, struct rngdata *r, int bitoffset) {
  94     int bytenum;
  95     int bitnum;
  96     int i;
  97
  98     if (!c || !r || (bitoffset > ((r->len * 8) - 48))) {
  99         printf("makecand: invalid params\n");
 100         return 0;
 101     }
 102
 103     bytenum = bitoffset / 8;
 104     bitnum = bitoffset % 8;
 105
 106     for (i = 0; i < 6; i++) {
 107         if (!bitnum) {
 108             c[i] = r->data[bytenum + i];
 109         } else {
 110             c[i] = (r->data[bytenum + i] << bitnum) | (r->data[bytenum + i + 1] >> (8 - bitnum));
 111         }
 112     }
 113
 114     return 1;
 115 }
 116
 117
 118 // test the candidate against the next or previous rng data
 119 static int testcand(unsigned char *f, unsigned char *rt, int fwd) {
 120     Hitag_State hstate;
 121     int i;
 122     uint32_t ks1;
 123     uint32_t ks2;
 124     unsigned char buf[6];
 125
 126     // build the prng state at the candidate
 127     hstate.shiftreg = 0;
 128     for (i = 0; i < 6; i++) {
 129         hstate.shiftreg = (hstate.shiftreg << 8) | f[i + 4];
 130     }
 131     buildlfsr(&hstate);
 132
 133     if (fwd) {
 134         // roll forwards 48 bits
 135         hitag2_nstep(&hstate, 48);
 136     } else {
 137         // roll backwards 48 bits
 138         rollback(&hstate, 48);
 139         buildlfsr(&hstate);
 140     }
 141
 142     // get 48 bits of RNG from the rolled to state
 143     ks1 = hitag2_nstep(&hstate, 24);
 144     ks2 = hitag2_nstep(&hstate, 24);
 145
 146     writebuf(buf, ks1, 3);
 147     writebuf(buf + 3, ks2, 3);
 148
 149     // compare them
 150     if (!memcmp(buf, rt, 6)) {
 151         return 1;
 152     } else {
 153         return 0;
 154     }
 155 }
 156
 157 static int searchcand(unsigned char *c, unsigned char *rt, int fwd, unsigned char *m, unsigned char *s) {
 158     int fd;
 159     struct stat filestat;
 160     char file[64];
 161     unsigned char *data;
 162     unsigned char item[10];
 163     unsigned char *found = NULL;
 164
 165
 166     if (!c || !rt || !m || !s) {
 167         printf("searchcand: invalid params\n");
 168         return 0;
 169     }
 170
 171     sprintf(file, INPUTFILE, c[0], c[1]);
 172
 173     fd = open(file, O_RDONLY);
 174     if (fd <= 0) {
 175         printf("cannot open table file %s\n", file);
 176         exit(1);
 177     }
 178
 179     if (fstat(fd, &filestat)) {
 180         printf("cannot stat file %s\n", file);
 181         exit(1);
 182     }
 183
 184     data = mmap((caddr_t)0, filestat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
 185     if (data == MAP_FAILED) {
 186         printf("cannot mmap file %s\n", file);
 187         exit(1);
 188     }
 189
 190     memcpy(item, c + 2, 4);
 191
 192     found = (unsigned char *)bsearch(item, data, filestat.st_size / DATASIZE, DATASIZE, datacmp);
 193
 194     if (found) {
 195
 196         // our candidate is in the table
 197         // go backwards and see if there are other matches
 198         while (((found - data) >= DATASIZE) && (!memcmp(found - DATASIZE, item, 4))) {
 199             found = found - DATASIZE;
 200         }
 201
 202         // now test all matches
 203         while (((found - data) <= (filestat.st_size - DATASIZE)) && (!memcmp(found, item, 4))) {
 204             if (testcand(found, rt, fwd)) {
 205                 memcpy(m, c, 2);
 206                 memcpy(m + 2, found, 4);
 207                 memcpy(s, found + 4, 6);
 208
 209                 munmap(data, filestat.st_size);
 210                 close(fd);
 211                 return 1;
 212             }
 213
 214             found = found + DATASIZE;
 215         }
 216     }
 217
 218     munmap(data, filestat.st_size);
 219     close(fd);
 220
 221     return 0;
 222
 223 }
 224
 225 static int findmatch(struct rngdata *r, unsigned char *outmatch, unsigned char *outstate, int *bitoffset) {
 226     int i;
 227     int bitlen;
 228     unsigned char cand[6];
 229     unsigned char rngtest[6];
 230     int fwd;
 231
 232     if (!r || !outmatch || !outstate || !bitoffset) {
 233         printf("findmatch: invalid params\n");
 234         return 0;
 235     }
 236
 237     bitlen = r->len * 8;
 238
 239     for (i = 0; i <= bitlen - 48; i++) {
 240         // print progress
 241         if ((i % 100) == 0) {
 242             printf("searching on bit %d\n", i);
 243         }
 244
 245         if (!makecand(cand, r, i)) {
 246             printf("cannot makecand, %d\n", i);
 247             return 0;
 248         }
 249 //        printf("cand: %02x %02x %02x %02x %02x %02x : ", cand[0], cand[1], cand[2], cand[3], cand[4], cand[5]);
 250 //        printbin(cand);
 251
 252         /* make following or preceding RNG test data to confirm match */
 253         if (i < (bitlen - 96)) {
 254             if (!makecand(rngtest, r, i + 48)) {
 255                 printf("cannot makecand rngtest %d + 48\n", i);
 256                 return 0;
 257             }
 258             fwd = 1;
 259         } else {
 260             if (!makecand(rngtest, r, i - 48)) {
 261                 printf("cannot makecand rngtest %d - 48\n", i);
 262                 return 0;
 263             }
 264             fwd = 0;
 265         }
 266
 267         if (searchcand(cand, rngtest, fwd, outmatch, outstate)) {
 268             *bitoffset = i;
 269             return 1;
 270         }
 271     }
 272
 273     return 0;
 274 }
 275
 276
 277
 278
 279 static void rollbackrng(Hitag_State *hstate, unsigned char *s, int offset) {
 280     int i;
 281
 282     if (!s) {
 283         printf("rollbackrng: invalid params\n");
 284         return;
 285     }
 286
 287     // build prng at recovered offset
 288     hstate->shiftreg = 0;
 289     for (i = 0; i < 6; i++) {
 290         hstate->shiftreg = (hstate->shiftreg << 8) | s[i];
 291     }
 292
 293     printf("recovered prng state at offset %d:\n", offset);
 294     printstate(hstate);
 295
 296     // rollback to state after auth
 297     rollback(hstate, offset);
 298
 299     // rollback through auth (aR, p3)
 300     rollback(hstate, 64);
 301
 302     printf("prng state after initialisation:\n");
 303     printstate(hstate);
 304
 305
 306 }
 307
 308 static uint64_t recoverkey(Hitag_State *hstate, char *uidstr, char *nRstr) {
 309     uint64_t key;
 310     uint64_t keyupper;
 311     uint32_t uid;
 312     uint32_t uidtmp;
 313     uint32_t nRenc;
 314     uint32_t nR;
 315     uint32_t nRxork;
 316     uint32_t b = 0;
 317     int i;
 318
 319     // key lower 16 bits are lower 16 bits of prng state
 320     key = hstate->shiftreg & 0xffff;
 321     nRxork = (hstate->shiftreg >> 16) & 0xffffffff;
 322     uid = rev32(hexreversetoulong(uidstr));
 323     nRenc = rev32(hexreversetoulong(nRstr));
 324
 325     uidtmp = uid;
 326     // rollback and extract bits b
 327     for (i = 0; i < 32; i++) {
 328         hstate->shiftreg = ((hstate->shiftreg) << 1) | ((uidtmp >> 31) & 0x1);
 329         uidtmp = uidtmp << 1;
 330         b = (b << 1) | fnf(hstate->shiftreg);
 331     }
 332
 333     printf("end state:\n");
 334     printstate(hstate);
 335     printf("b:\t\t");
 336     printbin2(b, 32);
 337     printf("\n");
 338     printf("nRenc:\t\t");
 339     printbin2(nRenc, 32);
 340     printf("\n");
 341
 342     nR = nRenc ^ b;
 343
 344     printf("nR:\t\t");
 345     printbin2(nR, 32);
 346     printf("\n");
 347
 348     keyupper = nRxork ^ nR;
 349     key = key | (keyupper << 16);
 350     printf("key:\t\t");
 351     printbin2(key, 48);
 352     printf("\n");
 353
 354     return key;
 355 }
 356
 357
 358 int main(int argc, char *argv[]) {
 359     Hitag_State hstate;
 360     struct rngdata rng;
 361     int bitoffset = 0;
 362     unsigned char rngmatch[6];
 363     unsigned char rngstate[6];
 364     char *uidstr;
 365     char *nRstr;
 366     uint64_t keyrev;
 367     uint64_t key;
 368     int i;
 369
 370     if (argc < 4) {
 371         printf("%s rngdatafile UID nR\n", argv[0]);
 372         exit(1);
 373     }
 374
 375     if (!loadrngdata(&rng, argv[1])) {
 376         printf("loadrngdata failed\n");
 377         exit(1);
 378     }
 379
 380     if (!strncmp(argv[2], "0x", 2)) {
 381         uidstr = argv[2] + 2;
 382     } else {
 383         uidstr = argv[2];
 384     }
 385
 386     if (!strncmp(argv[3], "0x", 2)) {
 387         nRstr = argv[3] + 2;
 388     } else {
 389         nRstr = argv[3];
 390     }
 391
 392
 393     if (!findmatch(&rng, rngmatch, rngstate, &bitoffset)) {
 394         printf("couldn't find a match\n");
 395         exit(1);
 396     }
 397
 398     printf("found match:\n");
 399     printf("rngmatch = %02x %02x %02x %02x %02x %02x\n", rngmatch[0], rngmatch[1], rngmatch[2], rngmatch[3], rngmatch[4], rngmatch[5]);
 400     printf("rngstate = %02x %02x %02x %02x %02x %02x\n", rngstate[0], rngstate[1], rngstate[2], rngstate[3], rngstate[4], rngstate[5]);
 401     printf("bitoffset = %d\n", bitoffset);
 402
 403     rollbackrng(&hstate, rngstate, bitoffset);
 404
 405     keyrev = recoverkey(&hstate, uidstr, nRstr);
 406     key = rev64(keyrev);
 407
 408     printf("keyrev:\t\t");
 409     printbin2(key, 48);
 410     printf("\n");
 411
 412     printf("KEY:\t\t");
 413     for (i = 0; i < 6; i++) {
 414         printf("%02X", (int)(key & 0xff));
 415         key = key >> 8;
 416     }
 417     printf("\n");
 418
 419     return 0;
 420
 421 }
 422
 423