Proxmark3 community

piwi

Contributor

Registered: 2013-06-04

Posts: 704

PATCH: command buffer overflow with "data samples" command

The new command buffer (introduced in r729) overflows during the data samples command (at least when a significant number of samples is requested).

Instead of increasing the buffer size I propose to abstain from waiting (msleep(10)) when the buffer wasn't empty during the last getCommand attempt. This allows the client to retrieve commands from the buffer much faster, thus preventing unnecessary overflows.

Proposed patch (I also moved the unchanged getCommand and storeCommand code up to prevent "implicitly declared" compiler warnings - therefore the patch seems to be bigger than it really is):

Index: C:/proxmark3/client/cmdmain.c
===================================================================
--- C:/proxmark3/client/cmdmain.c	(revision 732)
+++ C:/proxmark3/client/cmdmain.c	(working copy)
@@ -65,6 +65,45 @@
   return 0;
 }
 /**
+ * @brief storeCommand stores a USB command in a circular buffer
+ * @param UC
+ */
+void storeCommand(UsbCommand *command)
+{
+    if( ( cmd_head+1) % CMD_BUFFER_SIZE == cmd_tail)
+    {
+        //If these two are equal, we're about to overwrite in the
+        // circular buffer.
+        PrintAndLog("WARNING: Command buffer about to overwrite command! This needs to be fixed!");
+    }
+    //Store the command at the 'head' location
+    UsbCommand* destination = &cmdBuffer[cmd_head];
+    memcpy(destination, command, sizeof(UsbCommand));
+
+    cmd_head = (cmd_head +1) % CMD_BUFFER_SIZE; //increment head and wrap
+
+}
+/**
+ * @brief getCommand gets a command from an internal circular buffer.
+ * @param response location to write command
+ * @return 1 if response was returned, 0 if nothing has been received
+ */
+int getCommand(UsbCommand* response)
+{
+    //If head == tail, there's nothing to read, or if we just got initialized
+    if(cmd_head == cmd_tail){
+        return 0;
+    }
+    //Pick out the next unread command
+    UsbCommand* last_unread = &cmdBuffer[cmd_tail];
+    memcpy(response, last_unread, sizeof(UsbCommand));
+    //Increment tail - this is a circular buffer, so modulo buffer size
+    cmd_tail = (cmd_tail +1 ) % CMD_BUFFER_SIZE;
+
+    return 1;
+
+}
+/**
  * Waits for a certain response type. This method waits for a maximum of
  * ms_timeout milliseconds for a specified response command.
  *@brief WaitForResponseTimeout
@@ -74,6 +113,8 @@
  * @return true if command was returned, otherwise false
  */
 bool WaitForResponseTimeout(uint32_t cmd, UsbCommand* response, size_t ms_timeout) {
+
+  int command_received;
   
   if (response == NULL) {
     UsbCommand resp;
@@ -83,15 +124,17 @@
   // Wait until the command is received
   for(size_t dm_seconds=0; dm_seconds < ms_timeout/10; dm_seconds++) {
 
-      if(getCommand(response) && response->cmd == cmd){
+      if((command_received = getCommand(response)) && response->cmd == cmd){
           //We got what we expected
           return true;
       }
+	  if (command_received==0) {  // buffer was empty, sleep a little bit before next try
         msleep(10); // XXX ugh
-        if (dm_seconds == 200) { // Two seconds elapsed
-          PrintAndLog("Waiting for a response from the proxmark...");
-          PrintAndLog("Don't forget to cancel its operation first by pressing on the button");
-        }
+		}
+      if (dm_seconds == 200) { // Two seconds elapsed
+        PrintAndLog("Waiting for a response from the proxmark...");
+        PrintAndLog("Don't forget to cancel its operation first by pressing on the button");
+      }
 	}
     return false;
 }
@@ -205,42 +248,3 @@
   storeCommand(UC);
 
 }
-/**
- * @brief storeCommand stores a USB command in a circular buffer
- * @param UC
- */
-void storeCommand(UsbCommand *command)
-{
-    if( ( cmd_head+1) % CMD_BUFFER_SIZE == cmd_tail)
-    {
-        //If these two are equal, we're about to overwrite in the
-        // circular buffer.
-        PrintAndLog("WARNING: Command buffer about to overwrite command! This needs to be fixed!");
-    }
-    //Store the command at the 'head' location
-    UsbCommand* destination = &cmdBuffer[cmd_head];
-    memcpy(destination, command, sizeof(UsbCommand));
-
-    cmd_head = (cmd_head +1) % CMD_BUFFER_SIZE; //increment head and wrap
-
-}
-/**
- * @brief getCommand gets a command from an internal circular buffer.
- * @param response location to write command
- * @return 1 if response was returned, 0 if nothing has been received
- */
-int getCommand(UsbCommand* response)
-{
-    //If head == tail, there's nothing to read, or if we just got initialized
-    if(cmd_head == cmd_tail){
-        return 0;
-    }
-    //Pick out the next unread command
-    UsbCommand* last_unread = &cmdBuffer[cmd_tail];
-    memcpy(response, last_unread, sizeof(UsbCommand));
-    //Increment tail - this is a circular buffer, so modulo buffer size
-    cmd_tail = (cmd_tail +1 ) % CMD_BUFFER_SIZE;
-
-    return 1;
-
-}

Can please someone check and committ?

holiman

Contributor

Registered: 2013-05-03

Posts: 566

Re: PATCH: command buffer overflow with "data samples" command

When you say buffer overflow, you mean that the circular buffer was overwritten, right? Not 'buffer overflow' as in crash?

Good work!

piwi

Contributor

Registered: 2013-06-04

Posts: 704

Re: PATCH: command buffer overflow with "data samples" command

Sorry, yes, I meant the circular buffer ("WARNING: Command buffer about to overwrite command! This needs to be fixed!").

holiman

Contributor

Registered: 2013-05-03

Posts: 566

Re: PATCH: command buffer overflow with "data samples" command

I've sort of implemented the patch (but in a different way) in the scripting-branch. But not moved the functions around yet. It gets messy trying to keep two branches in paralell, so I haven't commited to trunk yet. Anyway, it would be good if you could get svn access, but I don't have those kind of powers

holiman

Contributor

Registered: 2013-05-03

Posts: 566

Re: PATCH: command buffer overflow with "data samples" command

Oh and I can't tell you how much that freeze-situation has disturbed me. I have also searched for the cause but I didn't find it.

piwi

Contributor

Registered: 2013-06-04

Posts: 704

Re: PATCH: command buffer overflow with "data samples" command

svn access would indeed be fine - who could grant it?

btw: I think that I can fix hf mf mifare which seems to be broken since r473 - need some time for testing though.

holiman

Contributor

Registered: 2013-05-03

Posts: 566

Re: PATCH: command buffer overflow with "data samples" command

I've been going back in svn history to find a properly working version, but I never went that far back! Has it been broken since r473 !? I'm really curious about what you've found.

I emailed Roel about svn access.

piwi

Contributor

Registered: 2013-06-04

Posts: 704

Re: PATCH: command buffer overflow with "data samples" command

ReaderMifare in armsrc/iso14443a.c is timing critical. SpinDelay gives a resolution of 21.3 microseconds, while the LFSR on the mifare tag shifts every 9.44 microseconds. Therefore the proxmark may receive different tag nonces in each cycle. The implementation poorly deals with this from the very beginning. Since r473 the "detection" of unexpected tag nonces is completely broken (wrong calculation and usage of isNULL). In addition, the check for wrong tag nonces should not only be done when a NACK is successfully received, they should be discarded without incrementing nt_diff or par, ...

Additionally, the first SpinDelay had been reduced from 200 to 50ms at some later release. This seems to be too short to completely power down the mifare card - with the result of random tag nonces instead of fixed tag nonces.

I am currently fixing the timer (SpinDelay) - and found this to be dangerous ground (proxmark not responding, reboot with button pressed, reflashing, next try, ...).

holiman

Contributor

Registered: 2013-05-03

Posts: 566

Re: PATCH: command buffer overflow with "data samples" command

Great work!

Since your last post about r473, I also started deepdiving into readermifare. I also found strange things (null-thingy and that it does not abort if nt is wrong until a lot later). I saw that there was a high enthropy of nt, and that the implementation "locked on" on a specific nt, which seemed suboptimal. So I wrote an implementation which did not lock onto a specific nt, but keeps a list of potential attack states. However, it didn't click until this morning when I read about the fact that 50ms was too little time for power down the card - the enthropy was simply too high even with thousands of states. When I set it back to 200, my implemnetation cracked a card I haven't been able to crack before using hf mf mifare. (Interestingly - another card I don't have access to anymore works fine with 50ms. It seems there are significant hardware differences between cards).

So, I'm not committing anything yet, but I'll post my implementation here. Perhaps we can combine our approaches into something really stable and fast? With state-tables, we could notice when state table is filled, which signals that enthropy is too high (thus timing is off) and inform the user.

iso14443a.h

typedef struct AttackState{
    byte_t nt[4];
    //byte_t nt_attacked[4];
    byte_t par_list[8];
    byte_t ks_list[8];
    byte_t par;
    byte_t par_low;
    byte_t nt_diff;
    uint8_t mf_nr_ar[8];
} AttackState;

int continueAttack(AttackState* pState,uint8_t* receivedAnswer);
void reportResults(uint8_t uid[8],AttackState *pState, int isOK);

iso1443a.c

#define STATE_SIZE 100
void ReaderMifare(uint32_t parameter)
{

    /**
     *Allocate our state-table and initialize with zeroes
     **/
    AttackState states[STATE_SIZE] ;
   
    Dbprintf("Memory allocated ok! (%d bytes)",STATE_SIZE*sizeof(AttackState) );
    memset(states, 0, STATE_SIZE*sizeof(AttackState));
	// Mifare AUTH
	uint8_t mf_auth[]    = { 0x60,0x00,0xf5,0x7b };
    //uint8_t mf_nr_ar[]   = { 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00 };
	uint8_t* receivedAnswer = (((uint8_t *)BigBuf) + FREE_BUFFER_OFFSET);	// was 3560 - tied to other size changes

    traceLen = 0;
	tracing = false;

	iso14443a_setup();

	LED_A_ON();
	LED_B_OFF();
	LED_C_OFF();

	LED_A_OFF();
    //int led_on = TRUE;
	uint8_t uid[8];
	uint32_t cuid;

    byte_t nt_noattack[4];
    num_to_bytes(parameter, 4, nt_noattack);
    byte_t nt[4];
    int nts_attacked= 0;

    while(!BUTTON_PRESS())
	{
		LED_C_OFF();
		FpgaWriteConfWord(FPGA_MAJOR_MODE_OFF);
        SpinDelay(200);
		FpgaWriteConfWord(FPGA_MAJOR_MODE_HF_ISO14443A | FPGA_HF_ISO14443A_READER_MOD);
		LED_C_ON();
		SpinDelay(2);

		if(!iso14443a_select_card(uid, NULL, &cuid)) continue;

		// Transmit MIFARE_CLASSIC_AUTH
		ReaderTransmit(mf_auth, sizeof(mf_auth));

		// Receive the (16 bit) "random" nonce
		if (!ReaderReceive(receivedAnswer)) continue;
        memcpy(nt, receivedAnswer, 4);

        //Now we have the NT. Check if this NT is already under attack
        AttackState* pState = NULL;
        int i = 0;
        for(i = 0 ; i < nts_attacked && pState == NULL; i++)
        {
            if( memcmp(nt, states[i].nt, 4) == 0)
            {
                //we have it
                pState = &states[i];
                Dbprintf("Existing state found (%d)", i);
            }
        }

        int result = 3;//continue > 0

        if(pState == NULL && nts_attacked < STATE_SIZE )
        {
            //Initialize  a new state
            pState = &states[nts_attacked++];
            //Clear it before use
            memset(pState, 0, sizeof(AttackState));
            memcpy(pState->nt, nt, 4);
            i = nts_attacked;
            Dbprintf("New state created, nt=");
        }


        if(pState == NULL) continue;

        result = continueAttack(pState, receivedAnswer);

        if(result == 2){
            Dbprintf("Continue attack no answer, par is now %d", pState->par);
        }
        else if(result == 1){
            Dbprintf("State increased to %d in state %d!", pState->nt_diff, i);
        }
        else if(result == 0){
            Dbprintf("Finished");
            reportResults(uid,pState,1);
            return;
        }


    }
}

int continueAttack(AttackState* pState,uint8_t* receivedAnswer)
{
    // Transmit reader nonce and reader answer
    ReaderTransmitPar(pState->mf_nr_ar, sizeof(pState->mf_nr_ar),pState->par);

    // Receive 4 bit answer
    if (!ReaderReceive(receivedAnswer))
    {
        if (pState->nt_diff == 0)
        {
            pState->par++;
        } else {
            pState->par = (((pState->par >> 3) + 1) << 3) | pState->par_low;
        }
        return 2;
    }
    if(pState->nt_diff == 0)
    {
        pState->par_low = pState->par & 0x07;
    }
    //Dbprintf("answer received, parameter (%d), (memcmp(nt, nt_no)=%d",parameter,memcmp(nt, nt_noattack, 4));
    //if ( (parameter != 0) && (memcmp(nt, nt_noattack, 4) == 0) ) continue;
    //isNULL =  0;//|| !(nt_attacked[0] == 0) && (nt_attacked[1] == 0) && (nt_attacked[2] == 0) && (nt_attacked[3] == 0);
     //
      //  if ( /*(isNULL != 0 ) && */(memcmp(nt, nt_attacked, 4) != 0) ) continue;

    //led_on = !led_on;
    //if(led_on) LED_B_ON(); else LED_B_OFF();
    pState->par_list[pState->nt_diff] = pState->par;
    pState->ks_list[pState->nt_diff] = receivedAnswer[0] ^ 0x05;

    // Test if the information is complete
    if (pState->nt_diff == 0x07) {
        return 0;
    }

    pState->nt_diff = (pState->nt_diff + 1) & 0x07;
    pState->mf_nr_ar[3] = pState->nt_diff << 5;
    pState->par = pState->par_low;
    return 1;
}

void reportResults(uint8_t uid[8],AttackState *pState, int isOK)
{
    LogTrace(pState->nt, 4, 0, GetParity(pState->nt, 4), TRUE);
    LogTrace(pState->par_list, 8, 0, GetParity(pState->par_list, 8), TRUE);
    LogTrace(pState->ks_list, 8, 0, GetParity(pState->ks_list, 8), TRUE);

    byte_t buf[48];
    memcpy(buf + 0,  uid, 4);
    memcpy(buf + 4,  pState->nt, 4);
    memcpy(buf + 8,  pState->par_list, 8);
    memcpy(buf + 16, pState->ks_list, 8);

    LED_B_ON();
    cmd_send(CMD_ACK,isOK,0,0,buf,48);
    LED_B_OFF();

    // Thats it...
    FpgaWriteConfWord(FPGA_MAJOR_MODE_OFF);
    LEDsoff();
    tracing = TRUE;

    if (MF_DBGLEVEL >= 1)	DbpString("COMMAND mifare FINISHED");
}

Also, I'm not a fan of byte arrays: code becomes less readable using memcmp and memcpy than == and = . So I would like to use uint64 and the like instead, and bitwise operations where needed . But that's just a personal opinion, and I'm not saying it's right.

holiman

Contributor

Registered: 2013-05-03

Posts: 566

Re: PATCH: command buffer overflow with "data samples" command

I also implemented a 'tuning' functionality, which is also not yet committed. It looks like this when I run hf mf mifare:

#db# Tuning... testing a delay of 25 ms                 
#db#      ... results for 25 ms : 100 %                 
#db# Tuning... testing a delay of 50 ms                 
#db#      ... results for 50 ms : 100 %                 
#db# Tuning... testing a delay of 100 ms                 
#db#      ... results for 100 ms : 98 %                 
#db# Tuning... testing a delay of 200 ms                 
#db#      ... results for 200 ms : 33 %                 
#db# Using power-down-time of 200 ms, entropy 33 

The entropy corresponds to the how many percent of the nonces received were unique: it starts 100 auths, and counts how many unique nonces it received.It keeps going either until entropy goes under 50% or timeout is more than two seconds.
 
Turns out, one of my cards needed ~1200 ms in order to power down. So,  yes, timing is important...

However, even after all this work, I *still* get "Key not found (lfsr_common_prefix list is null). " errors. Once in a while, for certain nonces.

Afaict, the behaviour is pretty stable, a certain nonce will always produce this result, other nonces will always recover the key. I have also tested with the latest version of the crapto code, but that did not make any difference. Very annoying... any ideas?

piwi

Contributor

Registered: 2013-06-04

Posts: 704

Re: PATCH: command buffer overflow with "data samples" command

I had looked into that direction as well. My idea was to count how often each nonce is received and then use the most probable one as nt_attacked. However, I still feel that it is worth to look for the root cause.

Regarding still "Key not found": It is some time ago that I read the Dark Side paper but as far as i remember there was no 100% guarantee with this algorithm. Therefore we have the "no_attack" Option for a second try.

holiman

Contributor

Registered: 2013-05-03

Posts: 566

Re: PATCH: command buffer overflow with "data samples" command

I see, thanks!

To sum up the issues,:
1. Different cards have different power-down time. This we need to tune, we don't want to use 1200ms just because there is one such card out there.
2. We get different noncs. This could probably improve, if timing (let's call it offset-time, i.e the time after that elapses after a power-on. when the nonces start ticking) can be more consistent. It shouldn't matter exactly what the offset-time is, as long as it is consistent between loops. Unless the device is commicating over USB during this time, I don't really see how inconsistency here occurs, or how it can be improved. Anyway, the state-table should limit the effects from this.
3. There are 'bad nonces'. Using multiple states, we could wait just a little bit longer (when one state reaches 8, there are probably a few others that have reached pretty far also) and collect a few more nt-states to crack. I wonder if the device can do some basic sanity check to see if the right conditions are met for a crack to succeed?

Oh, and on another note; I wonder if the 1200ms on my card can be shortened by using lesser effect? I will experiment with this later, by increasing the distance between card and reader. If this approach works, perhaps (I haven't looked into it at all yet) we could lessen the effect programmatically in the tnuing-phase when such a card is encountered. But this is hypothetical, if anyone has any insights here, please share.

Last edited by holiman (2013-06-13 12:00:51)

holiman

Contributor

Registered: 2013-05-03

Posts: 566

Re: PATCH: command buffer overflow with "data samples" command

Oh, and on another note; I wonder if the 1200ms on my card can be shortened by using lesser effect? I will experiment with this later, by increasing the distance between card and reader. If this approach works, perhaps (I haven't looked into it at all yet) we could lessen the effect programmatically in the tnuing-phase when such a card is encountered. But this is hypothetical, if anyone has any insights here, please share.

This didn't work. I placed the reader on the bottom page of a book, and inserted the tag between two pages a bit higher up in the book, above the reader, and gradually moved the tag until it 14a read barely worked. However, it did not seem to affect the power-down time at all. oh well.

piwi

Contributor

Registered: 2013-06-04

Posts: 704

Re: PATCH: command buffer overflow with "data samples" command

2. We get different noncs. This could probably improve, if timing (let's call it offset-time, i.e the time after that elapses after a power-on. when the nonces start ticking) can be more consistent. It shouldn't matter exactly what the offset-time is, as long as it is consistent between loops. Unless the device is commicating over USB during this time, I don't really see how inconsistency here occurs, or how it can be improved. Anyway, the state-table should limit the effects from this.

Yes, we need a consistent timing between power on and sending the Reader nonce. The device shouldn't communicate via USB, but we have several other clocks ticking. So far I discovered the serial links to the FPGA (SPI and SSC) which are clocked differently. By syncing with these clocks before power up I tried to avoid varying waiting cycles - but it didn't improve the overall timing. I then had added a timing compensation by measuring the timing during a dry run, adding a few microseconds and then introducing waiting cycles in the next rounds to arrive at the very same time before sending the Reader nonce - again no success. The time for transmitting the reader nonce varies and so do the received tag nonces.

I will have a look at the FPGA code next week - there is another clock signal (13.56MHz - no surprise).

holiman

Contributor

Registered: 2013-05-03

Posts: 566

Re: PATCH: command buffer overflow with "data samples" command

I see, hadn't thought of the whole fpga-part at all... interesting.

I'll be away in the countryside next week, so probably won't do much at all. In the meantime, I'll commit the mifare-stuff in the 'scripting'-branch. I don't think it's ready for 'trunk' yet, I'd like to add capability to disable tuning or set power-down-time explicitly through a parameter (there's space left in the command packet for more parameters).

So, if anyone wants to test it and/or make improvements, it will be available there in a moment.

Edit : committed as r745

Last edited by holiman (2013-06-15 11:18:49)

holiman

Contributor

Registered: 2013-05-03

Posts: 566

Re: PATCH: command buffer overflow with "data samples" command

committed to trunk as r752, more info here : http://www.proxmark.org/forum/viewtopic.php?id=1665

piwi

Contributor

Registered: 2013-06-04

Posts: 704

Re: PATCH: command buffer overflow with "data samples" command

I finally succeeded with the hf mf mifare timing. I have implemented a new timer (in util.c) which runs on the ssp_ck (13,56MHz/16 from FPGA). Because this is the same frequency as the Mifare classic Random Generator clock, we now can exactly time the Classic Auth command. No more need to power down the Card - we can simply wait for the nonces to repeat after 2^16 cycles. Another Change: Instead of starting all over during the second try, I am incrementing the reader nonce - so we know the  first three parity bits already.

As a result, the algorithm is pretty fast now (25 seconds on average, including the sometimes required second try).

Committed as r754 to trunk.

holiman

Contributor

Registered: 2013-05-03

Posts: 566

Re: PATCH: command buffer overflow with "data samples" command

As I said here : http://www.proxmark.org/forum/viewtopic.php?pid=7740#p7740 , totally awesome!