#include <stdio.h>\r
#include <stdlib.h> \r
#include <string.h>\r
+#include <pthread.h>\r
#include "mifarehost.h"\r
#include "proxmark3.h"\r
\r
// MIFARE\r
int compar_int(const void * a, const void * b) {\r
- return (*(uint64_t*)b - *(uint64_t*)a);\r
+ // didn't work: (the result is truncated to 32 bits)\r
+ //return (*(uint64_t*)b - *(uint64_t*)a);\r
+\r
+ // better:\r
+ if (*(uint64_t*)b == *(uint64_t*)a) return 0;\r
+ else if (*(uint64_t*)b > *(uint64_t*)a) return 1;\r
+ else return -1;\r
}\r
\r
-// Compare countKeys structure\r
-int compar_special_int(const void * a, const void * b) {\r
- return (((countKeys *)b)->count - ((countKeys *)a)->count);\r
+\r
+\r
+// Compare 16 Bits out of cryptostate\r
+int Compare16Bits(const void * a, const void * b) {\r
+ if ((*(uint64_t*)b & 0x00ff000000ff0000) == (*(uint64_t*)a & 0x00ff000000ff0000)) return 0;\r
+ else if ((*(uint64_t*)b & 0x00ff000000ff0000) > (*(uint64_t*)a & 0x00ff000000ff0000)) return 1;\r
+ else return -1;\r
}\r
\r
-countKeys * uniqsort(uint64_t * possibleKeys, uint32_t size) {\r
- int i, j = 0;\r
- int count = 0;\r
- countKeys *our_counts;\r
- \r
- qsort(possibleKeys, size, sizeof (uint64_t), compar_int);\r
- \r
- our_counts = calloc(size, sizeof(countKeys));\r
- if (our_counts == NULL) {\r
- PrintAndLog("Memory allocation error for our_counts");\r
- return NULL;\r
- }\r
+\r
+typedef \r
+ struct {\r
+ union {\r
+ struct Crypto1State *slhead;\r
+ uint64_t *keyhead;\r
+ };\r
+ union {\r
+ struct Crypto1State *sltail;\r
+ uint64_t *keytail;\r
+ };\r
+ uint32_t len;\r
+ uint32_t uid;\r
+ uint32_t blockNo;\r
+ uint32_t keyType;\r
+ uint32_t nt;\r
+ uint32_t ks1;\r
+ } StateList_t;\r
+\r
+\r
+// wrapper function for multi-threaded lfsr_recovery32\r
+void* nested_worker_thread(void *arg)\r
+{\r
+ struct Crypto1State *p1;\r
+ StateList_t *statelist = arg;\r
+\r
+ statelist->slhead = lfsr_recovery32(statelist->ks1, statelist->nt ^ statelist->uid);\r
+ for (p1 = statelist->slhead; *(uint64_t *)p1 != 0; p1++);\r
+ statelist->len = p1 - statelist->slhead;\r
+ statelist->sltail = --p1;\r
+ qsort(statelist->slhead, statelist->len, sizeof(uint64_t), Compare16Bits);\r
\r
- for (i = 0; i < size; i++) {\r
- if (possibleKeys[i+1] == possibleKeys[i]) { \r
- count++;\r
- } else {\r
- our_counts[j].key = possibleKeys[i];\r
- our_counts[j].count = count;\r
- j++;\r
- count=0;\r
- }\r
- }\r
- qsort(our_counts, j, sizeof(countKeys), compar_special_int);\r
- return (our_counts);\r
+ return statelist->slhead;\r
}\r
\r
-int mfnested(uint8_t blockNo, uint8_t keyType, uint8_t * key, uint8_t trgBlockNo, uint8_t trgKeyType, uint8_t * resultKeys) \r
+\r
+\r
+\r
+int mfnested(uint8_t blockNo, uint8_t keyType, uint8_t * key, uint8_t trgBlockNo, uint8_t trgKeyType, uint8_t * resultKey, bool calibrate) \r
{\r
- int i, m, len;\r
- uint8_t isEOF;\r
+ uint16_t i, len;\r
uint32_t uid;\r
- fnVector * vector = NULL;\r
- countKeys *ck;\r
- int lenVector = 0;\r
UsbCommand resp;\r
- \r
- memset(resultKeys, 0x00, 16 * 6);\r
\r
+ \r
+ StateList_t statelists[2];\r
+ struct Crypto1State *p1, *p2, *p3, *p4;\r
+ \r
// flush queue\r
WaitForResponseTimeout(CMD_ACK,NULL,100);\r
\r
- UsbCommand c = {CMD_MIFARE_NESTED, {blockNo, keyType, trgBlockNo + trgKeyType * 0x100}};\r
+ UsbCommand c = {CMD_MIFARE_NESTED, {blockNo + keyType * 0x100, trgBlockNo + trgKeyType * 0x100, calibrate}};\r
memcpy(c.d.asBytes, key, 6);\r
- SendCommand(&c);\r
-\r
- PrintAndLog("\n");\r
-\r
- // wait cycle\r
- while (true) {\r
- printf(".");\r
- if (ukbhit()) {\r
- getchar();\r
- printf("\naborted via keyboard!\n");\r
- break;\r
- }\r
-\r
- if (WaitForResponseTimeout(CMD_ACK,&resp,1500)) {\r
- isEOF = resp.arg[0] & 0xff;\r
+ SendCommand(&c);\r
\r
- if (isEOF) break;\r
- \r
- len = resp.arg[1] & 0xff;\r
- if (len == 0) continue;\r
- \r
+ if (WaitForResponseTimeout(CMD_ACK,&resp,1500)) {\r
+ len = resp.arg[1];\r
+ if (len == 2) { \r
memcpy(&uid, resp.d.asBytes, 4);\r
- PrintAndLog("uid:%08x len=%d trgbl=%d trgkey=%x", uid, len, resp.arg[2] & 0xff, (resp.arg[2] >> 8) & 0xff);\r
- vector = (fnVector *) realloc((void *)vector, (lenVector + len) * sizeof(fnVector) + 200);\r
- if (vector == NULL) {\r
- PrintAndLog("Memory allocation error for fnVector. len: %d bytes: %d", lenVector + len, (lenVector + len) * sizeof(fnVector)); \r
- break;\r
- }\r
+ PrintAndLog("uid:%08x len=%d trgbl=%d trgkey=%x", uid, len, (uint16_t)resp.arg[2] & 0xff, (uint16_t)resp.arg[2] >> 8);\r
\r
- for (i = 0; i < len; i++) {\r
- vector[lenVector + i].blockNo = resp.arg[2] & 0xff;\r
- vector[lenVector + i].keyType = (resp.arg[2] >> 8) & 0xff;\r
- vector[lenVector + i].uid = uid;\r
+ for (i = 0; i < 2; i++) {\r
+ statelists[i].blockNo = resp.arg[2] & 0xff;\r
+ statelists[i].keyType = (resp.arg[2] >> 8) & 0xff;\r
+ statelists[i].uid = uid;\r
\r
- memcpy(&vector[lenVector + i].nt, (void *)(resp.d.asBytes + 8 + i * 8 + 0), 4);\r
- memcpy(&vector[lenVector + i].ks1, (void *)(resp.d.asBytes + 8 + i * 8 + 4), 4);\r
+ memcpy(&statelists[i].nt, (void *)(resp.d.asBytes + 4 + i * 8 + 0), 4);\r
+ memcpy(&statelists[i].ks1, (void *)(resp.d.asBytes + 4 + i * 8 + 4), 4);\r
}\r
-\r
- lenVector += len;\r
+ }\r
+ else {\r
+ PrintAndLog("Got 0 keys from proxmark."); \r
+ return 1;\r
}\r
}\r
\r
- if (!lenVector) {\r
- PrintAndLog("Got 0 keys from proxmark."); \r
- return 1;\r
- }\r
- printf("------------------------------------------------------------------\n");\r
- \r
// calc keys\r
- struct Crypto1State* revstate = NULL;\r
- struct Crypto1State* revstate_start = NULL;\r
- uint64_t lfsr;\r
- int kcount = 0;\r
- pKeys *pk;\r
- \r
- if ((pk = (void *) malloc(sizeof(pKeys))) == NULL) return 1;\r
- memset(pk, 0x00, sizeof(pKeys));\r
\r
- for (m = 0; m < lenVector; m++) {\r
- // And finally recover the first 32 bits of the key\r
- revstate = lfsr_recovery32(vector[m].ks1, vector[m].nt ^ vector[m].uid);\r
- if (revstate_start == NULL) revstate_start = revstate;\r
+ pthread_t thread_id[2];\r
+ \r
+ // create and run worker threads\r
+ for (i = 0; i < 2; i++) {\r
+ pthread_create(thread_id + i, NULL, nested_worker_thread, &statelists[i]);\r
+ }\r
\r
- while ((revstate->odd != 0x0) || (revstate->even != 0x0)) {\r
- lfsr_rollback_word(revstate, vector[m].nt ^ vector[m].uid, 0);\r
- crypto1_get_lfsr(revstate, &lfsr);\r
+ // wait for threads to terminate:\r
+ for (i = 0; i < 2; i++) {\r
+ pthread_join(thread_id[i], (void*)&statelists[i].slhead);\r
+ }\r
+\r
\r
- // Allocate a new space for keys\r
- if (((kcount % MEM_CHUNK) == 0) || (kcount >= pk->size)) {\r
- pk->size += MEM_CHUNK;\r
-//fprintf(stdout, "New chunk by %d, sizeof %d\n", kcount, pk->size * sizeof(uint64_t));\r
- pk->possibleKeys = (uint64_t *) realloc((void *)pk->possibleKeys, pk->size * sizeof(uint64_t));\r
- if (pk->possibleKeys == NULL) {\r
- PrintAndLog("Memory allocation error for pk->possibleKeys"); \r
- return 1;\r
- }\r
+ // the first 16 Bits of the cryptostate already contain part of our key.\r
+ // Create the intersection of the two lists based on these 16 Bits and\r
+ // roll back the cryptostate\r
+ p1 = p3 = statelists[0].slhead; \r
+ p2 = p4 = statelists[1].slhead;\r
+ while (p1 <= statelists[0].sltail && p2 <= statelists[1].sltail) {\r
+ if (Compare16Bits(p1, p2) == 0) {\r
+ struct Crypto1State savestate, *savep = &savestate;\r
+ savestate = *p1;\r
+ while(Compare16Bits(p1, savep) == 0 && p1 <= statelists[0].sltail) {\r
+ *p3 = *p1;\r
+ lfsr_rollback_word(p3, statelists[0].nt ^ statelists[0].uid, 0);\r
+ p3++;\r
+ p1++;\r
+ }\r
+ savestate = *p2;\r
+ while(Compare16Bits(p2, savep) == 0 && p2 <= statelists[1].sltail) {\r
+ *p4 = *p2;\r
+ lfsr_rollback_word(p4, statelists[1].nt ^ statelists[1].uid, 0);\r
+ p4++;\r
+ p2++;\r
}\r
- pk->possibleKeys[kcount] = lfsr;\r
- kcount++;\r
- revstate++;\r
}\r
- free(revstate_start);\r
- revstate_start = NULL;\r
-\r
+ else {\r
+ while (Compare16Bits(p1, p2) == -1) p1++;\r
+ while (Compare16Bits(p1, p2) == 1) p2++;\r
+ }\r
}\r
- \r
- // Truncate\r
- if (kcount != 0) {\r
- pk->size = --kcount;\r
- if ((pk->possibleKeys = (uint64_t *) realloc((void *)pk->possibleKeys, pk->size * sizeof(uint64_t))) == NULL) {\r
- PrintAndLog("Memory allocation error for pk->possibleKeys"); \r
- return 1;\r
- } \r
+ p3->even = 0; p3->odd = 0;\r
+ p4->even = 0; p4->odd = 0;\r
+ statelists[0].len = p3 - statelists[0].slhead;\r
+ statelists[1].len = p4 - statelists[1].slhead;\r
+ statelists[0].sltail=--p3;\r
+ statelists[1].sltail=--p4;\r
+\r
+ // the statelists now contain possible keys. The key we are searching for must be in the\r
+ // intersection of both lists. Create the intersection:\r
+ qsort(statelists[0].keyhead, statelists[0].len, sizeof(uint64_t), compar_int);\r
+ qsort(statelists[1].keyhead, statelists[1].len, sizeof(uint64_t), compar_int);\r
+\r
+ uint64_t *p5, *p6, *p7;\r
+ p5 = p7 = statelists[0].keyhead; \r
+ p6 = statelists[1].keyhead;\r
+ while (p5 <= statelists[0].keytail && p6 <= statelists[1].keytail) {\r
+ if (compar_int(p5, p6) == 0) {\r
+ *p7++ = *p5++;\r
+ p6++;\r
+ }\r
+ else {\r
+ while (compar_int(p5, p6) == -1) p5++;\r
+ while (compar_int(p5, p6) == 1) p6++;\r
+ }\r
}\r
-\r
- PrintAndLog("Total keys count:%d", kcount);\r
- ck = uniqsort(pk->possibleKeys, pk->size);\r
-\r
- // fill key array\r
- for (i = 0; i < 16 ; i++) {\r
- num_to_bytes(ck[i].key, 6, (uint8_t*)(resultKeys + i * 6));\r
+ statelists[0].len = p7 - statelists[0].keyhead;\r
+ statelists[0].keytail=--p7;\r
+\r
+ memset(resultKey, 0, 6);\r
+ // The list may still contain several key candidates. Test each of them with mfCheckKeys\r
+ for (i = 0; i < statelists[0].len; i++) {\r
+ uint8_t keyBlock[6];\r
+ uint64_t key64;\r
+ crypto1_get_lfsr(statelists[0].slhead + i, &key64);\r
+ num_to_bytes(key64, 6, keyBlock);\r
+ key64 = 0;\r
+ if (!mfCheckKeys(statelists[0].blockNo, statelists[0].keyType, 1, keyBlock, &key64)) {\r
+ num_to_bytes(key64, 6, resultKey);\r
+ break;\r
+ }\r
}\r
-\r
- // finalize\r
- free(pk->possibleKeys);\r
- free(pk);\r
- free(ck);\r
- free(vector);\r
-\r
+ \r
+ free(statelists[0].slhead);\r
+ free(statelists[1].slhead);\r
+ \r
return 0;\r
}\r
\r
int mfCheckKeys (uint8_t blockNo, uint8_t keyType, uint8_t keycnt, uint8_t * keyBlock, uint64_t * key){\r
+\r
*key = 0;\r
\r
- UsbCommand c = {CMD_MIFARE_CHKKEYS, {blockNo, keyType, keycnt}};\r
+ UsbCommand c = {CMD_MIFARE_CHKKEYS, {blockNo, keyType, keycnt}};\r
memcpy(c.d.asBytes, keyBlock, 6 * keycnt);\r
- SendCommand(&c);\r
+ SendCommand(&c);\r
\r
UsbCommand resp;\r
if (!WaitForResponseTimeout(CMD_ACK,&resp,3000)) return 1;\r
projects / proxmark3-svn / blobdiff