added more keys (@equipter)
[RRG-proxmark3.git] / tools / mf_nonce_brute / mf_nonce_brute.c
blobb064f3683467444525c883403988b35d6dd752ac
1 #define __STDC_FORMAT_MACROS
3 #include <inttypes.h>
4 #include <stdio.h>
5 #include <stdbool.h>
6 #include <string.h>
7 #include <pthread.h>
8 #include <stdlib.h>
9 #include <unistd.h>
10 #include <ctype.h>
11 #include "crapto1/crapto1.h"
12 #include "protocol.h"
13 #include "iso14443crc.h"
14 #include "util_posix.h"
16 #define AEND "\x1b[0m"
17 #define _RED_(s) "\x1b[31m" s AEND
18 #define _GREEN_(s) "\x1b[32m" s AEND
19 #define _YELLOW_(s) "\x1b[33m" s AEND
20 #define _CYAN_(s) "\x1b[36m" s AEND
22 #define odd_parity(i) (( (i) ^ (i)>>1 ^ (i)>>2 ^ (i)>>3 ^ (i)>>4 ^ (i)>>5 ^ (i)>>6 ^ (i)>>7 ^ 1) & 0x01)
24 // a global mutex to prevent interlaced printing from different threads
25 pthread_mutex_t print_lock;
27 //--------------------- define options here
28 uint32_t uid = 0; // serial number
29 uint32_t nt_enc = 0; // Encrypted tag nonce
30 uint32_t nr_enc = 0; // encrypted reader challenge
31 uint32_t ar_enc = 0; // encrypted reader response
32 uint32_t at_enc = 0; // encrypted tag response
33 uint32_t cmd_enc = 0; // next encrypted command to sector
35 uint32_t nt_par_err = 0;
36 uint32_t ar_par_err = 0;
37 uint32_t at_par_err = 0;
39 typedef struct thread_args {
40 uint16_t xored;
41 int thread;
42 int idx;
43 bool ev1;
44 } targs;
46 #define ENC_LEN (200)
47 typedef struct thread_key_args {
48 int thread;
49 int idx;
50 uint32_t uid;
51 uint32_t part_key;
52 uint32_t nt_enc;
53 uint32_t nr_enc;
54 uint16_t enc_len;
55 uint8_t enc[ENC_LEN]; // next encrypted command + a full read/write
56 } targs_key;
58 //------------------------------------------------------------------
60 uint8_t cmds[8][2] = {
61 {ISO14443A_CMD_READBLOCK, 18},
62 {ISO14443A_CMD_WRITEBLOCK, 18},
63 {MIFARE_AUTH_KEYA, 0},
64 {MIFARE_AUTH_KEYB, 0},
65 {MIFARE_CMD_INC, 6},
66 {MIFARE_CMD_DEC, 6},
67 {MIFARE_CMD_RESTORE, 6},
68 {MIFARE_CMD_TRANSFER, 0}
71 //static int global_counter = 0;
72 static int global_found = 0;
73 static int global_found_candidate = 0;
74 static uint64_t global_candidate_key = 0;
75 static int thread_count = 2;
77 static int param_getptr(const char *line, int *bg, int *en, int paramnum) {
78 int i;
79 int len = strlen(line);
81 *bg = 0;
82 *en = 0;
84 // skip spaces
85 while (line[*bg] == ' ' || line[*bg] == '\t')(*bg)++;
86 if (*bg >= len) {
87 return 1;
90 for (i = 0; i < paramnum; i++) {
91 while (line[*bg] != ' ' && line[*bg] != '\t' && line[*bg] != '\0')(*bg)++;
92 while (line[*bg] == ' ' || line[*bg] == '\t')(*bg)++;
94 if (line[*bg] == '\0') return 1;
97 *en = *bg;
98 while (line[*en] != ' ' && line[*en] != '\t' && line[*en] != '\0')(*en)++;
100 (*en)--;
102 return 0;
105 static int param_gethex_to_eol(const char *line, int paramnum, uint8_t *data, int maxdatalen, int *datalen) {
106 int bg, en;
107 uint32_t temp;
108 char buf[5] = {0};
110 if (param_getptr(line, &bg, &en, paramnum)) return 1;
112 *datalen = 0;
114 int indx = bg;
115 while (line[indx]) {
116 if (line[indx] == '\t' || line[indx] == ' ') {
117 indx++;
118 continue;
121 if (isxdigit(line[indx])) {
122 buf[strlen(buf) + 1] = 0x00;
123 buf[strlen(buf)] = line[indx];
124 } else {
125 // if we have symbols other than spaces and hex
126 return 1;
129 if (*datalen >= maxdatalen) {
130 // if we dont have space in buffer and have symbols to translate
131 return 2;
134 if (strlen(buf) >= 2) {
135 sscanf(buf, "%x", &temp);
136 data[*datalen] = (uint8_t)(temp & 0xff);
137 *buf = 0;
138 (*datalen)++;
141 indx++;
144 if (strlen(buf) > 0)
145 //error when not completed hex bytes
146 return 3;
148 return 0;
151 static void hex_to_buffer(const uint8_t *buf, const uint8_t *hex_data, const size_t hex_len, const size_t hex_max_len,
152 const size_t min_str_len, const size_t spaces_between, bool uppercase) {
154 if (buf == NULL) return;
156 char *tmp = (char *)buf;
157 size_t i;
158 memset(tmp, 0x00, hex_max_len);
160 size_t max_len = (hex_len > hex_max_len) ? hex_max_len : hex_len;
162 for (i = 0; i < max_len; ++i, tmp += 2 + spaces_between) {
163 sprintf(tmp, (uppercase) ? "%02X" : "%02x", (unsigned int) hex_data[i]);
165 for (size_t j = 0; j < spaces_between; j++)
166 sprintf(tmp + 2 + j, " ");
169 i *= (2 + spaces_between);
171 size_t mlen = min_str_len > i ? min_str_len : 0;
172 if (mlen > hex_max_len)
173 mlen = hex_max_len;
175 for (; i < mlen; i++, tmp += 1)
176 sprintf(tmp, " ");
178 // remove last space
179 *tmp = '\0';
180 return;
183 static char *sprint_hex_inrow_ex(const uint8_t *data, const size_t len, const size_t min_str_len) {
184 static char buf[100] = {0};
185 hex_to_buffer((uint8_t *)buf, data, len, sizeof(buf) - 1, min_str_len, 0, true);
186 return buf;
189 static uint16_t parity_from_err(uint32_t data, uint16_t par_err) {
191 uint16_t par = 0;
192 par |= odd_parity((data >> 24) & 0xFF) ^ ((par_err >> 12) & 1);
193 par <<= 4;
195 par |= odd_parity((data >> 16) & 0xFF) ^ ((par_err >> 8) & 1);
196 par <<= 4;
198 par |= odd_parity((data >> 8) & 0xFF) ^ ((par_err >> 4) & 1);
199 par <<= 4;
201 par |= odd_parity(data & 0xFF) ^ (par_err & 1);
202 return par;
205 static uint16_t xored_bits(uint16_t nt_par, uint32_t ntenc, uint16_t ar_par, uint32_t arenc, uint16_t at_par, uint32_t atenc) {
206 uint16_t xored = 0;
208 uint8_t par;
209 //1st (1st nt)
210 par = (nt_par >> 12) & 1;
211 xored |= par ^ ((ntenc >> 16) & 1);
212 xored <<= 1;
214 //2nd (2nd nt)
215 par = (nt_par >> 8) & 1;
216 xored |= par ^ ((ntenc >> 8) & 1);
217 xored <<= 1;
219 //3rd (3rd nt)
220 par = (nt_par >> 4) & 1;
221 xored |= par ^ (ntenc & 1);
222 xored <<= 1;
224 //4th (1st ar)
225 par = (ar_par >> 12) & 1;
226 xored |= par ^ ((arenc >> 16) & 1);
227 xored <<= 1;
229 //5th (2nd ar)
230 par = (ar_par >> 8) & 1;
231 xored |= par ^ ((arenc >> 8) & 1);
232 xored <<= 1;
234 //6th (3rd ar)
235 par = (ar_par >> 4) & 1;
236 xored |= par ^ (arenc & 1);
237 xored <<= 1;
239 //7th (4th ar)
240 par = ar_par & 1;
241 xored |= par ^ ((atenc >> 24) & 1);
242 xored <<= 1;
244 //8th (1st at)
245 par = (at_par >> 12) & 1;
246 xored |= par ^ ((atenc >> 16) & 1);
247 xored <<= 1;
249 //9th (2nd at)
250 par = (at_par >> 8) & 1;
251 xored |= par ^ ((atenc >> 8) & 1);
252 xored <<= 1;
254 //10th (3rd at)
255 par = (at_par >> 4) & 1;
256 xored |= par ^ (atenc & 1);
258 return xored;
261 static bool candidate_nonce(uint32_t xored, uint32_t nt, bool ev1) {
262 uint8_t byte, check;
264 if (!ev1) {
265 //1st (1st nt)
266 byte = (nt >> 24) & 0xFF;
267 check = odd_parity(byte) ^ ((nt >> 16) & 1) ^ ((xored >> 9) & 1);
268 if (check) return false;
270 //2nd (2nd nt)
271 byte = (nt >> 16) & 0xFF;
272 check = odd_parity(byte) ^ ((nt >> 8) & 1) ^ ((xored >> 8) & 1);
273 if (check) return false;
276 //3rd (3rd nt)
277 byte = (nt >> 8) & 0xFF;
278 check = odd_parity(byte) ^ (nt & 1) ^ ((xored >> 7) & 1);
279 if (check) return false;
281 uint32_t ar = prng_successor(nt, 64);
283 //4th (1st ar)
284 byte = (ar >> 24) & 0xFF;
285 check = odd_parity(byte) ^ ((ar >> 16) & 1) ^ ((xored >> 6) & 1);
286 if (check) return false;
288 //5th (2nd ar)
289 byte = (ar >> 16) & 0x0FF;
290 check = odd_parity(byte) ^ ((ar >> 8) & 1) ^ ((xored >> 5) & 1);
291 if (check) return false;
293 //6th (3rd ar)
294 byte = (ar >> 8) & 0xFF;
295 check = odd_parity(byte) ^ (ar & 1) ^ ((xored >> 4) & 1);
296 if (check) return false;
298 uint32_t at = prng_successor(nt, 96);
300 //7th (4th ar)
301 byte = ar & 0xFF;
302 check = odd_parity(byte) ^ ((at >> 24) & 1) ^ ((xored >> 3) & 1);
303 if (check) return false;
305 //8th (1st at)
306 byte = (at >> 24) & 0xFF;
307 check = odd_parity(byte) ^ ((at >> 16) & 1) ^ ((xored >> 2) & 1);
308 if (check) return false;
310 //9th (2nd at)
311 byte = (at >> 16) & 0xFF;
312 check = odd_parity(byte) ^ ((at >> 8) & 1) ^ ((xored >> 1) & 1) ;
313 if (check) return false;
315 //10th (3rd at)
316 byte = (at >> 8) & 0xFF;
317 check = odd_parity(byte) ^ (at & 1) ^ (xored & 1);
318 if (check) return false;
320 return true;
323 static bool checkValidCmd(uint32_t decrypted) {
324 uint8_t cmd = (decrypted >> 24) & 0xFF;
325 for (int i = 0; i < 8; ++i) {
326 if (cmd == cmds[i][0])
327 return true;
329 return false;
332 static bool checkValidCmdByte(uint8_t *cmd, uint16_t n) {
334 bool ok = false;
335 for (int i = 0; i < 8; ++i) {
336 if (cmd[0] == cmds[i][0]) {
338 if (n >= 4)
339 ok = CheckCrc14443(CRC_14443_A, cmd, 4);
341 if (cmds[i][1] > 0 && n >= cmds[i][1])
342 ok = CheckCrc14443(CRC_14443_A, cmd + 4, cmds[i][1]);
344 if (ok) {
345 return true;
349 return false;
352 static bool checkCRC(uint32_t decrypted) {
353 uint8_t data[] = {
354 (decrypted >> 24) & 0xFF,
355 (decrypted >> 16) & 0xFF,
356 (decrypted >> 8) & 0xFF,
357 decrypted & 0xFF
359 return CheckCrc14443(CRC_14443_A, data, sizeof(data));
362 static void *brute_thread(void *arguments) {
364 //int shift = (int)arg;
365 struct thread_args *args = (struct thread_args *) arguments;
367 struct Crypto1State *revstate = NULL;
368 uint64_t key; // recovered key candidate
369 uint32_t ks2; // keystream used to encrypt reader response
370 uint32_t ks3; // keystream used to encrypt tag response
371 uint32_t ks4; // keystream used to encrypt next command
372 uint32_t nt; // current tag nonce
374 uint32_t p64 = 0;
375 uint32_t count;
376 // TC == 4 (
377 // threads calls 0 ev1 == false
378 // threads calls 0,1,2 ev1 == true
379 for (count = args->idx; count <= 0xFFFF; count += thread_count - 1) {
381 if (__atomic_load_n(&global_found, __ATOMIC_ACQUIRE) == 1) {
382 break;
385 nt = count << 16 | prng_successor(count, 16);
387 if (candidate_nonce(args->xored, nt, args->ev1) == false)
388 continue;
390 p64 = prng_successor(nt, 64);
391 ks2 = ar_enc ^ p64;
392 ks3 = at_enc ^ prng_successor(p64, 32);
393 revstate = lfsr_recovery64(ks2, ks3);
394 ks4 = crypto1_word(revstate, 0, 0);
396 if (ks4 != 0) {
398 // lock this section to avoid interlacing prints from different threats
399 pthread_mutex_lock(&print_lock);
400 if (args->ev1)
401 printf("\n**** Possible key candidate ****\n");
403 #if 0
404 printf("thread #%d idx %d %s\n", args->thread, args->idx, (args->ev1) ? "(Ev1)" : "");
405 printf("current nt(%08x) ar_enc(%08x) at_enc(%08x)\n", nt, ar_enc, at_enc);
406 printf("ks2:%08x\n", ks2);
407 printf("ks3:%08x\n", ks3);
408 printf("ks4:%08x\n", ks4);
409 #endif
410 if (cmd_enc) {
411 uint32_t decrypted = ks4 ^ cmd_enc;
412 printf("CMD enc( %08x )\n", cmd_enc);
413 printf(" dec( %08x ) ", decrypted);
415 // check if cmd exists
416 uint8_t isOK = checkValidCmd(decrypted);
417 if (isOK == false) {
418 printf(_RED_("<-- not a valid cmd\n"));
419 pthread_mutex_unlock(&print_lock);
420 continue;
423 // Add a crc-check.
424 isOK = checkCRC(decrypted);
425 if (isOK == false) {
426 printf(_RED_("<-- not a valid crc\n"));
427 pthread_mutex_unlock(&print_lock);
428 continue;
429 } else {
430 printf("<-- valid cmd\n");
434 lfsr_rollback_word(revstate, 0, 0);
435 lfsr_rollback_word(revstate, 0, 0);
436 lfsr_rollback_word(revstate, 0, 0);
437 lfsr_rollback_word(revstate, nr_enc, 1);
438 lfsr_rollback_word(revstate, uid ^ nt, 0);
439 crypto1_get_lfsr(revstate, &key);
441 if (args->ev1) {
442 // if it was EV1, we know for sure xxxAAAAAAAA recovery
443 printf("\nKey candidate [ " _YELLOW_("....%08" PRIx64)" ]\n\n", key & 0xFFFFFFFF);
444 __sync_fetch_and_add(&global_found_candidate, 1);
445 } else {
446 printf("\nKey candidate [ " _GREEN_("....%08" PRIx64) " ]\n\n", key & 0xFFFFFFFF);
447 __sync_fetch_and_add(&global_found, 1);
449 //release lock
450 pthread_mutex_unlock(&print_lock);
451 __sync_fetch_and_add(&global_candidate_key, key);
452 free(revstate);
453 break;
455 free(revstate);
457 free(args);
458 return NULL;
461 static void *brute_key_thread(void *arguments) {
463 struct thread_key_args *args = (struct thread_key_args *) arguments;
464 uint64_t key = args->part_key;
465 uint8_t local_enc[args->enc_len];
466 memcpy(local_enc, args->enc, args->enc_len);
468 for (uint64_t count = args->idx; count <= 0xFFFF; count += thread_count) {
470 if (__atomic_load_n(&global_found, __ATOMIC_ACQUIRE) == 1) {
471 break;
474 key = args->part_key | (count << 32);
476 // Init cipher with key
477 struct Crypto1State *pcs = crypto1_create(key);
479 // NESTED decrypt nt with help of new key
480 crypto1_word(pcs, args->nt_enc ^ args->uid, 1);
481 crypto1_word(pcs, args->nr_enc, 1);
482 crypto1_word(pcs, 0, 0);
483 crypto1_word(pcs, 0, 0);
485 // decrypt 22 bytes
486 uint8_t dec[args->enc_len];
487 for (int i = 0; i < args->enc_len; i++)
488 dec[i] = crypto1_byte(pcs, 0x00, 0) ^ local_enc[i];
490 crypto1_destroy(pcs);
492 // check if cmd exists
493 if (checkValidCmdByte(dec, args->enc_len) == false) {
494 continue;
496 __sync_fetch_and_add(&global_found, 1);
498 // lock this section to avoid interlacing prints from different threats
499 pthread_mutex_lock(&print_lock);
500 printf("\nenc: %s\n", sprint_hex_inrow_ex(local_enc, args->enc_len, 0));
501 printf("dec: %s\n", sprint_hex_inrow_ex(dec, args->enc_len, 0));
502 printf("\nValid Key found [ " _GREEN_("%012" PRIx64) " ]\n\n", key);
503 pthread_mutex_unlock(&print_lock);
504 break;
506 free(args);
507 return NULL;
510 static int usage(void) {
511 printf("\n");
512 printf("syntax: mf_nonce_brute <uid> <nt> <nt_par_err> <nr> <ar> <ar_par_err> <at> <at_par_err> [<next_command>]\n\n");
513 printf("how to convert trace data to needed input:\n");
514 printf(" nt in trace = 8c! 42 e6! 4e!\n");
515 printf(" nt = 8c42e64e\n");
516 printf(" nt_par_err = 1011\n\n");
517 printf("samples:\n");
518 printf("\n");
519 printf(" ./mf_nonce_brute fa247164 fb47c594 0000 71909d28 0c254817 1000 0dc7cfbd 1110\n");
520 printf("\n");
521 printf("**** Possible key candidate ****\n");
522 printf("Key candidate: [....ffffffff]\n");
523 printf("Too few next cmd bytes, skipping phase 2\n");
524 printf("\n");
525 printf(" ./mf_nonce_brute 96519578 d7e3c6ac 0011 cd311951 9da49e49 0010 2bb22e00 0100 a4f7f398ebdb4e484d1cb2b174b939d18b469f3fa5d9caab\n");
526 printf("\n");
527 printf("enc: A4F7F398EBDB4E484D1CB2B174B939D18B469F3FA5D9CAABBFA018EC7E0CC5721DE2E590F64BD0A5B4EFCE71\n");
528 printf("dec: 30084A24302F8102F44CA5020500A60881010104763930084A24302F8102F44CA5020500A608810101047639\n");
529 printf("Valid Key found: [3b7e4fd575ad]\n\n");
530 return 1;
533 int main(int argc, char *argv[]) {
534 printf("\nMifare classic nested auth key recovery\n\n");
536 if (argc < 9) return usage();
538 sscanf(argv[1], "%x", &uid);
539 sscanf(argv[2], "%x", &nt_enc);
540 sscanf(argv[3], "%x", &nt_par_err);
541 sscanf(argv[4], "%x", &nr_enc);
542 sscanf(argv[5], "%x", &ar_enc);
543 sscanf(argv[6], "%x", &ar_par_err);
544 sscanf(argv[7], "%x", &at_enc);
545 sscanf(argv[8], "%x", &at_par_err);
547 int enc_len = 0;
548 uint8_t enc[ENC_LEN] = {0}; // next encrypted command + a full read/write
549 if (argc > 9) {
550 // sscanf(argv[9], "%x", &cmd_enc);
551 param_gethex_to_eol(argv[9], 0, enc, sizeof(enc), &enc_len);
552 cmd_enc = (enc[0] << 24 | enc[1] << 16 | enc[2] << 8 | enc[3]);
555 printf("----------- " _CYAN_("Phase 1") " ------------------------\n");
556 printf("uid.................. %08x\n", uid);
557 printf("nt encrypted......... %08x\n", nt_enc);
558 printf("nt parity err........ %04x\n", nt_par_err);
559 printf("nr encrypted......... %08x\n", nr_enc);
560 printf("ar encrypted......... %08x\n", ar_enc);
561 printf("ar parity err........ %04x\n", ar_par_err);
562 printf("at encrypted......... %08x\n", at_enc);
563 printf("at parity err........ %04x\n", at_par_err);
565 if (argc > 9) {
566 printf("next encrypted cmd... %s\n", sprint_hex_inrow_ex(enc, enc_len, 0));
569 uint64_t t1 = msclock();
570 uint16_t nt_par = parity_from_err(nt_enc, nt_par_err);
571 uint16_t ar_par = parity_from_err(ar_enc, ar_par_err);
572 uint16_t at_par = parity_from_err(at_enc, at_par_err);
574 //calc (parity XOR corresponding nonce bit encoded with the same keystream bit)
575 uint16_t xored = xored_bits(nt_par, nt_enc, ar_par, ar_enc, at_par, at_enc);
577 #if !defined(_WIN32) || !defined(__WIN32__)
578 thread_count = sysconf(_SC_NPROCESSORS_CONF);
579 if (thread_count < 2)
580 thread_count = 2;
581 #endif /* _WIN32 */
583 printf("\nBruteforce using " _YELLOW_("%d") " threads\n", thread_count);
584 printf("looking for the last bytes of the encrypted tagnonce\n");
586 pthread_t threads[thread_count];
588 // create a mutex to avoid interlacing print commands from our different threads
589 pthread_mutex_init(&print_lock, NULL);
591 // one thread T0 for none EV1.
592 struct thread_args *a = calloc(1, sizeof(struct thread_args));
593 a->xored = xored;
594 a->thread = 0;
595 a->idx = 0;
596 a->ev1 = false;
597 pthread_create(&threads[0], NULL, brute_thread, (void *)a);
599 // the rest of available threads to EV1 scenario
600 for (int i = 0; i < thread_count - 1; ++i) {
601 struct thread_args *b = calloc(1, sizeof(struct thread_args));
602 b->xored = xored;
603 b->thread = i + 1;
604 b->idx = i;
605 b->ev1 = true;
606 pthread_create(&threads[i + 1], NULL, brute_thread, (void *)b);
609 // wait for threads to terminate:
610 for (int i = 0; i < thread_count; ++i)
611 pthread_join(threads[i], NULL);
613 t1 = msclock() - t1;
614 printf("execution time " _YELLOW_("%.2f") " sec\n", (float)t1 / 1000.0);
617 if (!global_found && !global_found_candidate) {
618 printf("\nFailed to find a key\n\n");
619 goto out;
622 if (enc_len < 4) {
623 printf("Too few next cmd bytes, skipping phase 2\n");
624 goto out;
627 // reset thread signals
628 global_found = 0;
629 global_found_candidate = 0;
631 printf("\n----------- " _CYAN_("Phase 2") " ------------------------\n");
632 printf("uid.................. %08x\n", uid);
633 printf("partial key.......... %08x\n", (uint32_t)(global_candidate_key & 0xFFFFFFFF));
634 printf("nt enc............... %08x\n", nt_enc);
635 printf("nr enc............... %08x\n", nr_enc);
636 printf("next encrypted cmd... %s\n", sprint_hex_inrow_ex(enc, enc_len, 0));
637 printf("\nlooking for the upper 16 bits of key\n");
638 fflush(stdout);
640 // threads
641 for (int i = 0; i < thread_count; ++i) {
642 struct thread_key_args *b = malloc(sizeof(struct thread_key_args));
643 b->thread = i;
644 b->idx = i;
645 b->uid = uid;
646 b->part_key = (uint32_t)(global_candidate_key & 0xFFFFFFFF);
647 b->nt_enc = nt_enc;
648 b->nr_enc = nr_enc;
649 b->enc_len = enc_len;
650 memcpy(b->enc, enc, enc_len);
651 pthread_create(&threads[i], NULL, brute_key_thread, (void *)b);
654 // wait for threads to terminate:
655 for (int i = 0; i < thread_count; ++i)
656 pthread_join(threads[i], NULL);
658 if (!global_found && !global_found_candidate) {
659 printf("\nfailed to find a key\n\n");
662 out:
663 // clean up mutex
664 pthread_mutex_destroy(&print_lock);
665 return 0;