From 838c15a6433b1cf1726aede99fa8dcdc7862473a Mon Sep 17 00:00:00 2001 From: iceman1001 Date: Wed, 17 Feb 2016 17:30:37 +0100 Subject: [PATCH] ADD: added some time debug statements to be able to measure execution time. CHG: change the auth_ex method to send usb package faster, REM: removed some bucketsort changes. --- armsrc/mifarecmd.c | 10 +-- armsrc/mifareutil.c | 10 ++- client/mifarehost.c | 70 +++++++++++---------- client/nonce2key/crapto1.c | 6 +- tools/mfkey/crapto1.c | 57 ++++++----------- tools/mfkey/crapto1.h | 4 +- tools/mfkey/crypto1.c | 7 ++- tools/mfkey/example_trace.txt | 12 +++- tools/mfkey/mfkey32.c | 86 +++++++++++++------------- tools/mfkey/mfkey32v2.c | 15 ++--- tools/mfkey/mfkey64.c | 111 +++++++++++++++++----------------- tools/nonce2key/Makefile | 2 +- tools/nonce2key/crapto1.c | 58 ++++++------------ tools/nonce2key/crapto1.h | 4 +- tools/nonce2key/crypto1.c | 7 ++- tools/nonce2key/nonce2key.c | 100 ++++++++++++++++-------------- 16 files changed, 275 insertions(+), 284 deletions(-) diff --git a/armsrc/mifarecmd.c b/armsrc/mifarecmd.c index 22f499aa..c097cfd5 100644 --- a/armsrc/mifarecmd.c +++ b/armsrc/mifarecmd.c @@ -998,8 +998,6 @@ void MifareChkKeys(uint16_t arg0, uint8_t arg1, uint8_t arg2, uint8_t *datain) set_tracing(TRUE); for (i = 0; i < keyCount; ++i) { - if (mifare_classic_halt(pcs, cuid)) - if (MF_DBGLEVEL >= 1) Dbprintf("ChkKeys: Halt error"); if (!iso14443a_select_card(uid, NULL, &cuid, true, 0)) { if (OLD_MF_DBGLEVEL >= 1) Dbprintf("ChkKeys: Can't select card"); @@ -1007,19 +1005,23 @@ void MifareChkKeys(uint16_t arg0, uint8_t arg1, uint8_t arg2, uint8_t *datain) } ui64Key = bytes_to_num(datain + i * 6, 6); - if (mifare_classic_auth(pcs, cuid, blockNo, keyType, ui64Key, AUTH_FIRST)) + if (mifare_classic_auth(pcs, cuid, blockNo, keyType, ui64Key, AUTH_FIRST)) { + if (mifare_classic_halt(pcs, cuid)) + if (MF_DBGLEVEL >= 1) Dbprintf("ChkKeys: Halt error"); continue; + } isOK = 1; break; } - crypto1_destroy(pcs); LED_B_ON(); cmd_send(CMD_ACK,isOK,0,0,datain + i * 6,6); + FpgaWriteConfWord(FPGA_MAJOR_MODE_OFF); LEDsoff(); set_tracing(FALSE); + crypto1_destroy(pcs); // restore debug level MF_DBGLEVEL = OLD_MF_DBGLEVEL; diff --git a/armsrc/mifareutil.c b/armsrc/mifareutil.c index 20d4b68b..1956e88a 100644 --- a/armsrc/mifareutil.c +++ b/armsrc/mifareutil.c @@ -139,12 +139,11 @@ int mifare_classic_authex(struct Crypto1State *pcs, uint32_t uid, uint8_t blockN // variables int len; uint32_t pos; - uint8_t tmp4[4] = {0x00}; uint8_t par[1] = {0x00}; // "random" reader nonce: - byte_t nr[4] = {0x55, 0x41, 0x49, 0x92}; - //byte_t nr[4] = {0x01, 0x01, 0x01, 0x01}; + //byte_t nr[4] = {0x55, 0x41, 0x49, 0x92}; + byte_t nr[4] = {0x01, 0x01, 0x01, 0x01}; uint32_t nt, ntpp; // Supplied tag nonce @@ -210,10 +209,9 @@ int mifare_classic_authex(struct Crypto1State *pcs, uint32_t uid, uint8_t blockN return 2; } - memcpy(tmp4, receivedAnswer, 4); ntpp = prng_successor(nt, 32) ^ crypto1_word(pcs, 0,0); - - if (ntpp != bytes_to_num(tmp4, 4)) { + + if (ntpp != bytes_to_num(receivedAnswer, 4)) { if (MF_DBGLEVEL >= 1) Dbprintf("Authentication failed. Error card response."); return 3; } diff --git a/client/mifarehost.c b/client/mifarehost.c index 3aaf9e07..916fba8f 100644 --- a/client/mifarehost.c +++ b/client/mifarehost.c @@ -15,6 +15,7 @@ #include "mifarehost.h" #include "proxmark3.h" //#include "radixsort.h" +#include // MIFARE int compar_int(const void * a, const void * b) { @@ -22,26 +23,25 @@ int compar_int(const void * a, const void * b) { //return (*(uint64_t*)b - *(uint64_t*)a); // better: - /*if (*(uint64_t*)b < *(uint64_t*)a) return -1; if (*(uint64_t*)b > *(uint64_t*)a) return 1; + if (*(uint64_t*)b < *(uint64_t*)a) return -1; return 0; -*/ - return (*(uint64_t*)b > *(uint64_t*)a) - (*(uint64_t*)b < *(uint64_t*)a); + + //return (*(uint64_t*)b > *(uint64_t*)a) - (*(uint64_t*)b < *(uint64_t*)a); } // Compare 16 Bits out of cryptostate int Compare16Bits(const void * a, const void * b) { - -/* - if ((*(uint64_t*)b & 0x00ff000000ff0000) < (*(uint64_t*)a & 0x00ff000000ff0000)) return -1; if ((*(uint64_t*)b & 0x00ff000000ff0000) > (*(uint64_t*)a & 0x00ff000000ff0000)) return 1; + if ((*(uint64_t*)b & 0x00ff000000ff0000) < (*(uint64_t*)a & 0x00ff000000ff0000)) return -1; return 0; -*/ - return + +/* return ((*(uint64_t*)b & 0x00ff000000ff0000) > (*(uint64_t*)a & 0x00ff000000ff0000)) - ((*(uint64_t*)b & 0x00ff000000ff0000) < (*(uint64_t*)a & 0x00ff000000ff0000)) ; +*/ } typedef @@ -66,6 +66,7 @@ typedef // wrapper function for multi-threaded lfsr_recovery32 void* nested_worker_thread(void *arg) { + clock_t t1 = clock(); struct Crypto1State *p1; StateList_t *statelist = arg; @@ -77,6 +78,9 @@ void* nested_worker_thread(void *arg) statelist->tail.sltail = --p1; qsort(statelist->head.slhead, statelist->len, sizeof(uint64_t), Compare16Bits); + + t1 = clock() - t1; + printf("lfsr_recovery32 takes %.0f ticks \n", (float)t1); return statelist->head.slhead; } @@ -148,7 +152,7 @@ int mfnested(uint8_t blockNo, uint8_t keyType, uint8_t * key, uint8_t trgBlockNo while (Compare16Bits(p1, p2) == 1) p2++; } } - + p3->even = 0; p3->odd = 0; p4->even = 0; p4->odd = 0; statelists[0].len = p3 - statelists[0].head.slhead; @@ -160,10 +164,11 @@ int mfnested(uint8_t blockNo, uint8_t keyType, uint8_t * key, uint8_t trgBlockNo // intersection of both lists. Create the intersection: qsort(statelists[0].head.keyhead, statelists[0].len, sizeof(uint64_t), compar_int); qsort(statelists[1].head.keyhead, statelists[1].len, sizeof(uint64_t), compar_int); - + uint64_t *p5, *p6, *p7; p5 = p7 = statelists[0].head.keyhead; p6 = statelists[1].head.keyhead; + while (p5 <= statelists[0].tail.keytail && p6 <= statelists[1].tail.keytail) { if (compar_int(p5, p6) == 0) { *p7++ = *p5++; @@ -177,37 +182,40 @@ int mfnested(uint8_t blockNo, uint8_t keyType, uint8_t * key, uint8_t trgBlockNo statelists[0].len = p7 - statelists[0].head.keyhead; statelists[0].tail.keytail = --p7; + uint32_t numOfCandidates = statelists[0].len; + if ( numOfCandidates == 0 ) goto out; + memset(resultKey, 0, 6); uint64_t key64 = 0; // The list may still contain several key candidates. Test each of them with mfCheckKeys // uint32_t max_keys = keycnt > (USB_CMD_DATA_SIZE/6) ? (USB_CMD_DATA_SIZE/6) : keycnt; + uint8_t keyBlock[USB_CMD_DATA_SIZE] = {0x00}; - uint32_t numOfCandidates = statelists[0].len; - if ( numOfCandidates > 0 ) { - - uint8_t keyBlock[USB_CMD_DATA_SIZE] = {0x00}; + clock_t t1 = clock(); + for (i = 0; i < numOfCandidates; ++i){ + crypto1_get_lfsr(statelists[0].head.slhead + i, &key64); + num_to_bytes(key64, 6, keyBlock + i * 6); + } - for (i = 0; i < numOfCandidates; ++i){ - crypto1_get_lfsr(statelists[0].head.slhead + i, &key64); - num_to_bytes(key64, 6, keyBlock + i * 6); - } + if (!mfCheckKeys(statelists[0].blockNo, statelists[0].keyType, false, numOfCandidates, keyBlock, &key64)) { + free(statelists[0].head.slhead); + free(statelists[1].head.slhead); + num_to_bytes(key64, 6, resultKey); - if (!mfCheckKeys(statelists[0].blockNo, statelists[0].keyType, false, numOfCandidates, keyBlock, &key64)) { - free(statelists[0].head.slhead); - free(statelists[1].head.slhead); - num_to_bytes(key64, 6, resultKey); - - PrintAndLog("UID: %08x target block:%3u key type: %c -- Found key [%012"llx"]", - uid, - (uint16_t)resp.arg[2] & 0xff, - (resp.arg[2] >> 8) ? 'B' : 'A', - key64 - ); - return -5; - } + t1 = clock() - t1; + printf("Check candidates takes %.0f ticks \n", (float)t1); + PrintAndLog("UID: %08x target block:%3u key type: %c -- Found key [%012"llx"]", + uid, + (uint16_t)resp.arg[2] & 0xff, + (resp.arg[2] >> 8) ? 'B' : 'A', + key64 + ); + return -5; } + +out: PrintAndLog("UID: %08x target block:%3u key type: %c", uid, (uint16_t)resp.arg[2] & 0xff, diff --git a/client/nonce2key/crapto1.c b/client/nonce2key/crapto1.c index 626823f8..0339190f 100644 --- a/client/nonce2key/crapto1.c +++ b/client/nonce2key/crapto1.c @@ -26,7 +26,7 @@ static void __attribute__((constructor)) fill_lut() { uint32_t i; for(i = 0; i < 1 << 20; ++i) - filterlut[i] = filter(i); + filterlut[i] = filter(i); } #define filter(x) (filterlut[(x) & 0xfffff]) #endif @@ -196,7 +196,7 @@ out: return statelist; } -static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214, +static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214, 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83, 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA}; static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60, @@ -490,7 +490,7 @@ struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8] if(!s || !odd || !even) { free(statelist); statelist = 0; - goto out; + goto out; } for(o = odd; *o + 1; ++o) diff --git a/tools/mfkey/crapto1.c b/tools/mfkey/crapto1.c index ef08e7ad..b6e0e87d 100755 --- a/tools/mfkey/crapto1.c +++ b/tools/mfkey/crapto1.c @@ -95,26 +95,11 @@ static void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop, } } -/** binsearch - * Binary search for the first occurence of *stop's MSB in sorted [start,stop] - */ -static inline uint32_t* binsearch(uint32_t *start, uint32_t *stop) -{ - uint32_t mid, val = *stop & 0xff000000; - while(start != stop) - if(start[mid = (stop - start) >> 1] > val) - stop = &start[mid]; - else - start += mid + 1; - - return start; -} /** update_contribution * helper, calculates the partial linear feedback contributions and puts in MSB */ -static inline void -update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) +static inline void update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) { uint32_t p = *item >> 25; @@ -126,8 +111,7 @@ update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) /** extend_table * using a bit of the keystream extend the table of possible lfsr states */ -static inline void -extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in) +static inline void extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in) { in <<= 24; for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) @@ -150,14 +134,16 @@ extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in */ static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit) { - for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) + for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) { if(filter(*tbl) ^ filter(*tbl | 1)) { // replace *tbl |= filter(*tbl) ^ bit; } else if(filter(*tbl) == bit) { // insert *++*end = *++tbl; *tbl = tbl[-1] | 1; - } else // drop + } else { // drop *tbl-- = *(*end)--; + } + } } /** recover * recursively narrow down the search space, 4 bits of keystream at a time @@ -186,13 +172,11 @@ recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks, oks >>= 1; eks >>= 1; in >>= 2; - extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1, - LF_POLY_ODD << 1, 0); + extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0); if(o_head > o_tail) return sl; - extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD, - LF_POLY_EVEN << 1 | 1, in & 3); + extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, in & 3); if(e_head > e_tail) return sl; } @@ -238,14 +222,15 @@ struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in) // allocate memory for out of place bucket_sort bucket_array_t bucket; - for (uint32_t i = 0; i < 2; i++) + + for (uint32_t i = 0; i < 2; i++) { for (uint32_t j = 0; j <= 0xff; j++) { bucket[i][j].head = malloc(sizeof(uint32_t)<<14); if (!bucket[i][j].head) { goto out; } } - + } // initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream for(i = 1 << 20; i >= 0; --i) { @@ -265,17 +250,14 @@ struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in) // 22 bits to go to recover 32 bits in total. From now on, we need to take the "in" // parameter into account. in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); // Byte swapping - recover(odd_head, odd_tail, oks, - even_head, even_tail, eks, 11, statelist, in << 1, bucket); - + recover(odd_head, odd_tail, oks, even_head, even_tail, eks, 11, statelist, in << 1, bucket); out: - free(odd_head); - free(even_head); for (uint32_t i = 0; i < 2; i++) for (uint32_t j = 0; j <= 0xff; j++) free(bucket[i][j].head); - + free(odd_head); + free(even_head); return statelist; } @@ -569,12 +551,11 @@ struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8] odd = lfsr_prefix_ks(ks, 1); even = lfsr_prefix_ks(ks, 0); - s = statelist = malloc((sizeof *statelist) << 21); + s = statelist = malloc((sizeof *statelist) << 20); if(!s || !odd || !even) { free(statelist); - free(odd); - free(even); - return 0; + statelist = 0; + goto out; } for(o = odd; *o + 1; ++o) @@ -586,8 +567,8 @@ struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8] } s->odd = s->even = 0; - +out: free(odd); free(even); return statelist; -} \ No newline at end of file +} diff --git a/tools/mfkey/crapto1.h b/tools/mfkey/crapto1.h index 555de2fe..65c57021 100755 --- a/tools/mfkey/crapto1.h +++ b/tools/mfkey/crapto1.h @@ -17,8 +17,8 @@ Copyright (C) 2008-2014 bla */ -#ifndef CRAPTO1_INCLUDED -#define CRAPTO1_INCLUDED +#ifndef CRAPTO1_H__ +#define CRAPTO1_H__ #include #ifdef __cplusplus extern "C" { diff --git a/tools/mfkey/crypto1.c b/tools/mfkey/crypto1.c index 57a6c1df..f49a0722 100755 --- a/tools/mfkey/crypto1.c +++ b/tools/mfkey/crypto1.c @@ -23,10 +23,13 @@ struct Crypto1State * crypto1_create(uint64_t key) { struct Crypto1State *s = malloc(sizeof(*s)); + if ( !s ) return NULL; + s->odd = s->even = 0; + int i; - - for(i = 47;s && i > 0; i -= 2) { + //for(i = 47;s && i > 0; i -= 2) { + for(i = 47; i > 0; i -= 2) { s->odd = s->odd << 1 | BIT(key, (i - 1) ^ 7); s->even = s->even << 1 | BIT(key, i ^ 7); } diff --git a/tools/mfkey/example_trace.txt b/tools/mfkey/example_trace.txt index f2587fcd..83dd157c 100644 --- a/tools/mfkey/example_trace.txt +++ b/tools/mfkey/example_trace.txt @@ -11,5 +11,15 @@ + 1287: : a1 e4 58 ce 6e ea 41 e0 + 64: 0: TAG 5c ad f4 39 -./mfkey64 9c599b32 82a4166c a1e458ce 6eea41e0 5cadf439 +:: Sample values +:: +./mfkey32 52B0F519 5417D1F8 4D545EA7 E15AC8C2 dac1a7f4 5ae5c37f + +:: +./mfkey32v2 12345678 1AD8DF2B 1D316024 620EF048 30D6CB07 C52077E2 837AC61A +./mfkey32v2 52B0F519 5417D1F8 4D545EA7 E15AC8C2 A1BA88C6 DAC1A7F4 5AE5C37F + +:: +./mfkey64 9C599B32 82A4166C A1E458CE 6EEA41E0 5CADF439 +./mfkey64 52B0F519 5417D1F8 4D545EA7 E15AC8C2 5056e41b diff --git a/tools/mfkey/mfkey32.c b/tools/mfkey/mfkey32.c index 0af15cdc..c122b77b 100755 --- a/tools/mfkey/mfkey32.c +++ b/tools/mfkey/mfkey32.c @@ -1,56 +1,57 @@ #define __STDC_FORMAT_MACROS #include -#define llx PRIx64 -#define lli PRIi64 - -// Test-file: test2.c #include "crapto1.h" #include #include +#include +#define llx PRIx64 +#define lli PRIi64 int main (int argc, char *argv[]) { - struct Crypto1State *s,*t; - uint64_t key; // recovered key - uint32_t uid; // serial number - uint32_t nt; // tag challenge - uint32_t nr0_enc; // first encrypted reader challenge - uint32_t ar0_enc; // first encrypted reader response - uint32_t nr1_enc; // second encrypted reader challenge - uint32_t ar1_enc; // second encrypted reader response - uint32_t ks2; // keystream used to encrypt reader response + struct Crypto1State *s,*t; + uint64_t key; // recovered key + uint32_t uid; // serial number + uint32_t nt; // tag challenge + uint32_t nr0_enc; // first encrypted reader challenge + uint32_t ar0_enc; // first encrypted reader response + uint32_t nr1_enc; // second encrypted reader challenge + uint32_t ar1_enc; // second encrypted reader response + uint32_t ks2; // keystream used to encrypt reader response - printf("MIFARE Classic key recovery - based 32 bits of keystream\n"); - printf("Recover key from two 32-bit reader authentication answers only!\n\n"); + printf("MIFARE Classic key recovery - based 32 bits of keystream\n"); + printf("Recover key from two 32-bit reader authentication answers only!\n\n"); - if (argc < 7) { - printf(" syntax: %s <{nr_0}> <{ar_0}> <{nr_1}> <{ar_1}>\n\n",argv[0]); - return 1; - } + if (argc < 7) { + printf(" syntax: %s \n\n",argv[0]); + return 1; + } - sscanf(argv[1],"%x",&uid); - sscanf(argv[2],"%x",&nt); - sscanf(argv[3],"%x",&nr0_enc); - sscanf(argv[4],"%x",&ar0_enc); - sscanf(argv[5],"%x",&nr1_enc); - sscanf(argv[6],"%x",&ar1_enc); + sscanf(argv[1],"%x",&uid); + sscanf(argv[2],"%x",&nt); + sscanf(argv[3],"%x",&nr0_enc); + sscanf(argv[4],"%x",&ar0_enc); + sscanf(argv[5],"%x",&nr1_enc); + sscanf(argv[6],"%x",&ar1_enc); - printf("Recovering key for:\n"); - printf(" uid: %08x\n",uid); - printf(" nt: %08x\n",nt); - printf(" {nr_0}: %08x\n",nr0_enc); - printf(" {ar_0}: %08x\n",ar0_enc); - printf(" {nr_1}: %08x\n",nr1_enc); - printf(" {ar_1}: %08x\n",ar1_enc); + printf("Recovering key for:\n"); + printf(" uid: %08x\n",uid); + printf(" nt: %08x\n",nt); + printf(" {nr_0}: %08x\n",nr0_enc); + printf(" {ar_0}: %08x\n",ar0_enc); + printf(" {nr_1}: %08x\n",nr1_enc); + printf(" {ar_1}: %08x\n",ar1_enc); // Generate lfsr succesors of the tag challenge - printf("\nLFSR succesors of the tag challenge:\n"); - printf(" nt': %08x\n",prng_successor(nt, 64)); - printf(" nt'': %08x\n",prng_successor(nt, 96)); + printf("\nLFSR succesors of the tag challenge:\n"); + printf(" nt': %08x\n",prng_successor(nt, 64)); + printf(" nt'': %08x\n",prng_successor(nt, 96)); - // Extract the keystream from the messages - printf("\nKeystream used to generate {ar} and {at}:\n"); - ks2 = ar0_enc ^ prng_successor(nt, 64); - printf(" ks2: %08x\n",ks2); + clock_t t1 = clock(); + + // Extract the keystream from the messages + printf("\nKeystream used to generate {ar} and {at}:\n"); + ks2 = ar0_enc ^ prng_successor(nt, 64); + printf(" ks2: %08x\n",ks2); s = lfsr_recovery32(ar0_enc ^ prng_successor(nt, 64), 0); @@ -65,7 +66,8 @@ int main (int argc, char *argv[]) { printf("\nFound Key: [%012"llx"]\n\n",key); break;} } - free(s); - - return 0; + free(s); + t1 = clock() - t1; + if ( t1 > 0 ) printf("Time : %.0f ticks \n", (float)t1); + return 0; } diff --git a/tools/mfkey/mfkey32v2.c b/tools/mfkey/mfkey32v2.c index 7183a547..349b31e7 100644 --- a/tools/mfkey/mfkey32v2.c +++ b/tools/mfkey/mfkey32v2.c @@ -1,13 +1,12 @@ #define __STDC_FORMAT_MACROS #include -#define llx PRIx64 -#define lli PRIi64 - -// Test-file: test2.c #include "crapto1.h" #include #include +#include +#define llx PRIx64 +#define lli PRIi64 int main (int argc, char *argv[]) { struct Crypto1State *s,*t; uint64_t key; // recovered key @@ -21,11 +20,11 @@ int main (int argc, char *argv[]) { uint32_t ks2; // keystream used to encrypt reader response printf("MIFARE Classic key recovery - based 32 bits of keystream VERSION2\n"); - printf("Recover key from two 32-bit reader authentication answers only"); + printf("Recover key from two 32-bit reader authentication answers only\n"); printf("This version implements Moebius two different nonce solution (like the supercard)\n\n"); if (argc < 8) { - printf(" syntax: %s <{nr_0}> <{ar_0}> <{nr_1}> <{ar_1}>\n\n",argv[0]); + printf("syntax: %s \n\n", argv[0]); return 1; } @@ -50,6 +49,7 @@ int main (int argc, char *argv[]) { printf("\nLFSR succesors of the tag challenge:\n"); printf(" nt': %08x\n",prng_successor(nt0, 64)); printf(" nt'': %08x\n",prng_successor(nt0, 96)); + clock_t t1 = clock(); // Extract the keystream from the messages printf("\nKeystream used to generate {ar} and {at}:\n"); @@ -71,6 +71,7 @@ int main (int argc, char *argv[]) { break;} } free(s); - + t1 = clock() - t1; + if ( t1 > 0 ) printf("Time : %.0f ticks \n", (float)t1 ); return 0; } diff --git a/tools/mfkey/mfkey64.c b/tools/mfkey/mfkey64.c index 448cb2ac..8bb59ecc 100755 --- a/tools/mfkey/mfkey64.c +++ b/tools/mfkey/mfkey64.c @@ -1,71 +1,68 @@ #define __STDC_FORMAT_MACROS #include -#define llx PRIx64 -#define lli PRIi64 - -// Test-file: test2.c #include "crapto1.h" #include +#include + +#define llx PRIx64 +#define lli PRIi64 int main (int argc, char *argv[]) { - struct Crypto1State *revstate; - uint64_t key; // recovered key - uint32_t uid; // serial number - uint32_t nt; // tag challenge - uint32_t nr_enc; // encrypted reader challenge - uint32_t ar_enc; // encrypted reader response - uint32_t at_enc; // encrypted tag response - uint32_t ks2; // keystream used to encrypt reader response - uint32_t ks3; // keystream used to encrypt tag response + struct Crypto1State *revstate; + uint64_t key; // recovered key + uint32_t uid; // serial number + uint32_t nt; // tag challenge + uint32_t nr_enc; // encrypted reader challenge + uint32_t ar_enc; // encrypted reader response + uint32_t at_enc; // encrypted tag response + uint32_t ks2; // keystream used to encrypt reader response + uint32_t ks3; // keystream used to encrypt tag response - printf("MIFARE Classic key recovery - based 64 bits of keystream\n"); - printf("Recover key from only one complete authentication!\n\n"); + printf("MIFARE Classic key recovery - based 64 bits of keystream\n"); + printf("Recover key from only one complete authentication!\n\n"); - if (argc < 6) { - printf(" syntax: %s <{nr}> <{ar}> <{at}>\n\n",argv[0]); - return 1; - } + if (argc < 6) { + printf(" syntax: %s \n\n",argv[0]); + return 1; + } - sscanf(argv[1],"%x",&uid); - sscanf(argv[2],"%x",&nt); - sscanf(argv[3],"%x",&nr_enc); - sscanf(argv[4],"%x",&ar_enc); - sscanf(argv[5],"%x",&at_enc); + sscanf(argv[1],"%x",&uid); + sscanf(argv[2],"%x",&nt); + sscanf(argv[3],"%x",&nr_enc); + sscanf(argv[4],"%x",&ar_enc); + sscanf(argv[5],"%x",&at_enc); - printf("Recovering key for:\n"); - printf(" uid: %08x\n",uid); - printf(" nt: %08x\n",nt); - printf(" {nr}: %08x\n",nr_enc); - printf(" {ar}: %08x\n",ar_enc); - printf(" {at}: %08x\n",at_enc); + printf("Recovering key for:\n"); + printf(" uid: %08x\n",uid); + printf(" nt: %08x\n",nt); + printf(" {nr}: %08x\n",nr_enc); + printf(" {ar}: %08x\n",ar_enc); + printf(" {at}: %08x\n",at_enc); -/* - uint32_t uid = 0x9c599b32; - uint32_t tag_challenge = 0x82a4166c; - uint32_t nr_enc = 0xa1e458ce; - uint32_t reader_response = 0x6eea41e0; - uint32_t tag_response = 0x5cadf439; -*/ // Generate lfsr succesors of the tag challenge - printf("\nLFSR succesors of the tag challenge:\n"); - printf(" nt': %08x\n",prng_successor(nt, 64)); - printf(" nt'': %08x\n",prng_successor(nt, 96)); - - // Extract the keystream from the messages - printf("\nKeystream used to generate {ar} and {at}:\n"); - ks2 = ar_enc ^ prng_successor(nt, 64); - ks3 = at_enc ^ prng_successor(nt, 96); - printf(" ks2: %08x\n",ks2); - printf(" ks3: %08x\n",ks3); - - revstate = lfsr_recovery64(ks2, ks3); - lfsr_rollback_word(revstate, 0, 0); - lfsr_rollback_word(revstate, 0, 0); - lfsr_rollback_word(revstate, nr_enc, 1); - lfsr_rollback_word(revstate, uid ^ nt, 0); - crypto1_get_lfsr(revstate, &key); - printf("\nFound Key: [%012"llx"]\n\n",key); - crypto1_destroy(revstate); + printf("\nLFSR succesors of the tag challenge:\n"); + printf(" nt': %08x\n",prng_successor(nt, 64)); + printf(" nt'': %08x\n",prng_successor(nt, 96)); + + clock_t t1 = clock(); + + // Extract the keystream from the messages + printf("\nKeystream used to generate {ar} and {at}:\n"); + ks2 = ar_enc ^ prng_successor(nt, 64); + ks3 = at_enc ^ prng_successor(nt, 96); + printf(" ks2: %08x\n",ks2); + printf(" ks3: %08x\n",ks3); - return 0; + revstate = lfsr_recovery64(ks2, ks3); + lfsr_rollback_word(revstate, 0, 0); + lfsr_rollback_word(revstate, 0, 0); + lfsr_rollback_word(revstate, nr_enc, 1); + lfsr_rollback_word(revstate, uid ^ nt, 0); + crypto1_get_lfsr(revstate, &key); + printf("\nFound Key: [%012"llx"]\n\n",key); + crypto1_destroy(revstate); + + t1 = clock() - t1; + if ( t1 > 0 ) printf("Time : %.0f ticks \n", (float)t1); + return 0; } diff --git a/tools/nonce2key/Makefile b/tools/nonce2key/Makefile index b84c9bbb..bfab6fd8 100644 --- a/tools/nonce2key/Makefile +++ b/tools/nonce2key/Makefile @@ -1,6 +1,6 @@ CC = gcc LD = gcc -CFLAGS = -Wall -O3 -c +CFLAGS = -std=c99 -Wall -O3 -c LDFLAGS = OBJS = crypto1.o crapto1.o diff --git a/tools/nonce2key/crapto1.c b/tools/nonce2key/crapto1.c index 61922481..1d854d96 100644 --- a/tools/nonce2key/crapto1.c +++ b/tools/nonce2key/crapto1.c @@ -95,26 +95,10 @@ static void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop, } } -/** binsearch - * Binary search for the first occurence of *stop's MSB in sorted [start,stop] - */ -static inline uint32_t* binsearch(uint32_t *start, uint32_t *stop) -{ - uint32_t mid, val = *stop & 0xff000000; - while(start != stop) - if(start[mid = (stop - start) >> 1] > val) - stop = &start[mid]; - else - start += mid + 1; - - return start; -} - /** update_contribution * helper, calculates the partial linear feedback contributions and puts in MSB */ -static inline void -update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) +static inline void update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) { uint32_t p = *item >> 25; @@ -126,8 +110,7 @@ update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) /** extend_table * using a bit of the keystream extend the table of possible lfsr states */ -static inline void -extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in) +static inline void extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in) { in <<= 24; for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) @@ -150,14 +133,16 @@ extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in */ static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit) { - for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) + for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) { if(filter(*tbl) ^ filter(*tbl | 1)) { // replace *tbl |= filter(*tbl) ^ bit; } else if(filter(*tbl) == bit) { // insert *++*end = *++tbl; *tbl = tbl[-1] | 1; - } else // drop + } else { // drop *tbl-- = *(*end)--; + } + } } /** recover * recursively narrow down the search space, 4 bits of keystream at a time @@ -186,13 +171,11 @@ recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks, oks >>= 1; eks >>= 1; in >>= 2; - extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1, - LF_POLY_ODD << 1, 0); + extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0); if(o_head > o_tail) return sl; - extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD, - LF_POLY_EVEN << 1 | 1, in & 3); + extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, in & 3); if(e_head > e_tail) return sl; } @@ -238,14 +221,15 @@ struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in) // allocate memory for out of place bucket_sort bucket_array_t bucket; - for (uint32_t i = 0; i < 2; i++) + + for (uint32_t i = 0; i < 2; i++) { for (uint32_t j = 0; j <= 0xff; j++) { bucket[i][j].head = malloc(sizeof(uint32_t)<<14); if (!bucket[i][j].head) { goto out; } } - + } // initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream for(i = 1 << 20; i >= 0; --i) { @@ -265,17 +249,14 @@ struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in) // 22 bits to go to recover 32 bits in total. From now on, we need to take the "in" // parameter into account. in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); // Byte swapping - recover(odd_head, odd_tail, oks, - even_head, even_tail, eks, 11, statelist, in << 1, bucket); - + recover(odd_head, odd_tail, oks, even_head, even_tail, eks, 11, statelist, in << 1, bucket); out: - free(odd_head); - free(even_head); for (uint32_t i = 0; i < 2; i++) for (uint32_t j = 0; j <= 0xff; j++) free(bucket[i][j].head); - + free(odd_head); + free(even_head); return statelist; } @@ -569,12 +550,11 @@ struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8] odd = lfsr_prefix_ks(ks, 1); even = lfsr_prefix_ks(ks, 0); - s = statelist = malloc((sizeof *statelist) << 21); + s = statelist = malloc((sizeof *statelist) << 20); if(!s || !odd || !even) { free(statelist); - free(odd); - free(even); - return 0; + statelist = 0; + goto out; } for(o = odd; *o + 1; ++o) @@ -586,8 +566,8 @@ struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8] } s->odd = s->even = 0; - +out: free(odd); free(even); return statelist; -} \ No newline at end of file +} diff --git a/tools/nonce2key/crapto1.h b/tools/nonce2key/crapto1.h index d3a71eb0..3eaf88b7 100644 --- a/tools/nonce2key/crapto1.h +++ b/tools/nonce2key/crapto1.h @@ -17,8 +17,8 @@ Copyright (C) 2008-2014 bla */ -#ifndef CRAPTO1_INCLUDED -#define CRAPTO1_INCLUDED +#ifndef CRAPTO1_H__ +#define CRAPTO1_H__ #include #ifdef __cplusplus extern "C" { diff --git a/tools/nonce2key/crypto1.c b/tools/nonce2key/crypto1.c index 57a6c1df..f49a0722 100644 --- a/tools/nonce2key/crypto1.c +++ b/tools/nonce2key/crypto1.c @@ -23,10 +23,13 @@ struct Crypto1State * crypto1_create(uint64_t key) { struct Crypto1State *s = malloc(sizeof(*s)); + if ( !s ) return NULL; + s->odd = s->even = 0; + int i; - - for(i = 47;s && i > 0; i -= 2) { + //for(i = 47;s && i > 0; i -= 2) { + for(i = 47; i > 0; i -= 2) { s->odd = s->odd << 1 | BIT(key, (i - 1) ^ 7); s->even = s->even << 1 | BIT(key, i ^ 7); } diff --git a/tools/nonce2key/nonce2key.c b/tools/nonce2key/nonce2key.c index 32ea0a68..b08c5cd2 100644 --- a/tools/nonce2key/nonce2key.c +++ b/tools/nonce2key/nonce2key.c @@ -3,57 +3,63 @@ #include #define llx PRIx64 #include +#include typedef unsigned char byte_t; int main(const int argc, const char* argv[]) { - struct Crypto1State *state; - uint32_t pos, uid, nt, nr, rr, nr_diff, ks1, ks2; - byte_t bt, i, ks3x[8], par[8][8]; - uint64_t key, key_recovered; - uint64_t par_info; - uint64_t ks_info; - nr = rr = 0; - - if (argc < 5) { - printf("\nsyntax: %s \n\n",argv[0]); - return 1; - } - sscanf(argv[1],"%08x",&uid); - sscanf(argv[2],"%08x",&nt); - sscanf(argv[3],"%016"llx,&par_info); - sscanf(argv[4],"%016"llx,&ks_info); - - // Reset the last three significant bits of the reader nonce - nr &= 0xffffff1f; + struct Crypto1State *state; + uint32_t pos, uid, nt, nr, rr, nr_diff, ks1, ks2; + byte_t bt, i, ks3x[8], par[8][8]; + uint64_t key, key_recovered; + uint64_t par_info; + uint64_t ks_info; + nr = rr = 0; + + if (argc < 5) { + printf("\nsyntax: %s \n\n",argv[0]); + return 1; + } + sscanf(argv[1],"%08x",&uid); + sscanf(argv[2],"%08x",&nt); + sscanf(argv[3],"%016"llx,&par_info); + sscanf(argv[4],"%016"llx,&ks_info); - printf("\nuid(%08x) nt(%08x) par(%016"llx") ks(%016"llx")\n\n",uid,nt,par_info,ks_info); - - for (pos=0; pos<8; pos++) - { - ks3x[7-pos] = (ks_info >> (pos*8)) & 0x0f; - bt = (par_info >> (pos*8)) & 0xff; - for (i=0; i<8; i++) - { - par[7-pos][i] = (bt >> i) & 0x01; - } - } - - printf("|diff|{nr} |ks3|ks3^5|parity |\n"); - printf("+----+--------+---+-----+---------------+\n"); - for (i=0; i<8; i++) - { - nr_diff = nr | i << 5; - printf("| %02x |%08x|",i << 5, nr_diff); - printf(" %01x | %01x |",ks3x[i], ks3x[i]^5); - for (pos=0; pos<7; pos++) printf("%01x,",par[i][pos]); - printf("%01x|\n",par[i][7]); - } + // Reset the last three significant bits of the reader nonce + nr &= 0xffffff1f; + + printf("\nuid(%08x) nt(%08x) par(%016"llx") ks(%016"llx")\n\n",uid,nt,par_info,ks_info); + + for ( pos = 0; pos < 8; pos++ ) { + ks3x[7-pos] = (ks_info >> (pos*8)) & 0x0f; + bt = (par_info >> (pos*8)) & 0xff; + + for ( i = 0; i < 8; i++) { + par[7-pos][i] = (bt >> i) & 0x01; + } + } + + printf("|diff|{nr} |ks3|ks3^5|parity |\n"); + printf("+----+--------+---+-----+---------------+\n"); + + for ( i = 0; i < 8; i++) { + nr_diff = nr | i << 5; + printf("| %02x |%08x| %01x | %01x |", i << 5, nr_diff, ks3x[i], ks3x[i]^5); + + for ( pos = 0; pos < 7; pos++) + printf("%01x,", par[i][pos]); + printf("%01x|\n", par[i][7]); + } + printf("+----+--------+---+-----+---------------+\n"); + + clock_t t1 = clock(); - state = lfsr_common_prefix(nr,rr,ks3x,par); - lfsr_rollback_word(state,uid^nt,0); - crypto1_get_lfsr(state,&key_recovered); - printf("\nkey recovered: %012"llx"\n\n",key_recovered); - crypto1_destroy(state); + state = lfsr_common_prefix(nr,rr,ks3x,par); + lfsr_rollback_word(state,uid^nt,0); + crypto1_get_lfsr(state,&key_recovered); + printf("\nkey recovered: %012"llx"\n\n",key_recovered); + crypto1_destroy(state); - return 0; + t1 = clock() - t1; + if ( t1 > 0 ) printf("Time in nonce2key: %.0f ticks \n", (float)t1); + return 0; } -- 2.39.2