+// 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
+typedef\r
+ struct {\r
+ union {\r
+ struct Crypto1State *slhead;\r
+ uint64_t *keyhead;\r
+ } head;\r
+ union {\r
+ struct Crypto1State *sltail;\r
+ uint64_t *keytail;\r
+ } tail;\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->head.slhead = lfsr_recovery32(statelist->ks1, statelist->nt ^ statelist->uid);\r
+ for (p1 = statelist->head.slhead; *(uint64_t *)p1 != 0; p1++);\r
+ statelist->len = p1 - statelist->head.slhead;\r
+ statelist->tail.sltail = --p1;\r
+ qsort(statelist->head.slhead, statelist->len, sizeof(uint64_t), Compare16Bits);\r
+\r
+ return statelist->head.slhead;\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
+ uint16_t i;\r
+ uint32_t uid;\r
+ UsbCommand resp;\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 * 0x100, trgBlockNo + trgKeyType * 0x100, calibrate}};\r
+ memcpy(c.d.asBytes, key, 6);\r
+ SendCommand(&c);\r
+\r
+ if (!WaitForResponseTimeout(CMD_ACK, &resp, 1500)) {\r
+ return -1;\r
+ }\r
+\r
+ if (resp.arg[0]) {\r
+ return resp.arg[0]; // error during nested\r
+ }\r
+\r
+ memcpy(&uid, resp.d.asBytes, 4);\r
+ PrintAndLog("uid:%08x trgbl=%d trgkey=%x", uid, (uint16_t)resp.arg[2] & 0xff, (uint16_t)resp.arg[2] >> 8);\r
+\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
+ 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
+ // calc keys\r
+\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
+ // wait for threads to terminate:\r
+ for (i = 0; i < 2; i++) {\r
+ pthread_join(thread_id[i], (void*)&statelists[i].head.slhead);\r
+ }\r
+\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].head.slhead;\r
+ p2 = p4 = statelists[1].head.slhead;\r
+ while (p1 <= statelists[0].tail.sltail && p2 <= statelists[1].tail.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].tail.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].tail.sltail) {\r
+ *p4 = *p2;\r
+ lfsr_rollback_word(p4, statelists[1].nt ^ statelists[1].uid, 0);\r
+ p4++;\r
+ p2++;\r
+ }\r
+ }\r
+ else {\r
+ while (Compare16Bits(p1, p2) == -1) p1++;\r
+ while (Compare16Bits(p1, p2) == 1) p2++;\r
+ }\r
+ }\r
+ *(uint64_t*)p3 = -1;\r
+ *(uint64_t*)p4 = -1;\r
+ statelists[0].len = p3 - statelists[0].head.slhead;\r
+ statelists[1].len = p4 - statelists[1].head.slhead;\r
+ statelists[0].tail.sltail=--p3;\r
+ statelists[1].tail.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].head.keyhead, statelists[0].len, sizeof(uint64_t), compare_uint64);\r
+ qsort(statelists[1].head.keyhead, statelists[1].len, sizeof(uint64_t), compare_uint64);\r
+ statelists[0].len = intersection(statelists[0].head.keyhead, statelists[1].head.keyhead);\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].head.slhead + i, &key64);\r
+ num_to_bytes(key64, 6, keyBlock);\r
+ key64 = 0;\r
+ if (!mfCheckKeys(statelists[0].blockNo, statelists[0].keyType, false, 1, keyBlock, &key64)) {\r
+ num_to_bytes(key64, 6, resultKey);\r
+ break;\r
+ }\r
+ }\r
+\r
+ free(statelists[0].head.slhead);\r
+ free(statelists[1].head.slhead);\r
+\r
+ return 0;\r
+}\r
+\r