Insecurity of Mifare Classic (Part 1)

We all know these cards and keychains used for physically accessing something or even paying with them. The most popular trademark is MIFARE, which includes four different types of NFC cards. Even though the “Classic” version is almost 30 years old, and its followers are much safer, companies and even government organizations still use this type for important operations - simply because it’s cheap. In the next 2 parts of this topic, we will discuss the theory behind security vulnerabilities and practical approaches to exploiting them. If you are only interested in practical attacks and only a bit of theory, you should check out the next part.

Memory layout

A Mifare Classic card is just a storage device, where the memory is divided into segments and blocks with simple security mechanisms for access control. There are three versions of the Classic family with different memory sizes (in bytes): 320, 1K, 2K and 4K Let’s look at their layout closer:

Each sector has the same layout, consisting of multiple blocks with 16 bytes each. 1K cards, being the most common, have 16 sectors with 4 blocks each. 4K version, starting from sector 32, has 16 blocks in each sector. As you can see by color, sector 0 is “special”. Block 0 contains the UID - “unique ID” of the card. Original Mifare cards do not have duplicate IDs, but as there are clones out there, their uniqueness cannot be guaranteed. Since block 0 is read-only from the beginning, some people rely on it and use the UID for authentication, which is a bad idea, as we will later see. Please note, that the actual UID is only 4 bytes long, not 16! This is what we get from Proxmark documentation:

11223344440804006263646566676869
^^^^^^^^                         UID
        ^^                       BCC
          ^^                     SAK(*)
            ^^^^                 ATQA
                ^^^^^^^^^^^^^^^^ Manufacturer data
(*) some cards have a different SAK in their anticollision and in block0: +0x80 in the block0 (e.g. 08->88, 18->98)

Therefore, if you want to clone UID (and it’s possible, as we will later see) from a larger card to a smaller, you should either only clone the first 4 bytes or change SAK and ATQA values according to given tables:

📘 Note: SAK is the manufacturer and generic product identification code. According to this note, this number in block 0 does not always correspond to what you see during communication with the card (because real ones are burnt into chips during manufacturing). Thus, if you will do a full block 0 copy of such a card, this inconsistency can easily be spotted. A simple solution is to overwrite SAK in the dump file with the correct one.

Blocks 1 and 2 are reserved for Mifare Application Directory (MAD), which specifies use-case of a card. It allows readers to check if a card is compatible with them and modify data afterwards. This data is almost always written during manufacturing process and is irrelevant for our research.

The last block of each sector has always the same structure. It contains two different keys, called A (green) and B (orange), used to protect the whole sector. Default keys are 0xff*6 for A and 0x00*6 for B, but they can and should be changed. Each key can be programmed to allow operations such as reading, writing, increasing value blocks, etc. These permissions are stored in access bits (purple).

appendixA_6

The one gray byte is reserved for “user-data”~~, even though you have hundreds of other bytes to store data in~~. Knowing this basic info, we can continue to the interesting part.

Communication

Let’s go through unencrypted communication and initial authentication process. The picture you see below was taken from a wonderful research paper, which you will see many more times below:

26 - “Who is there?”
04 00 - “It’s me, Mifare Classic 1K - ATQA 0x04”
93 20 - “What’s your name (UID)?”
c2 a8 2d f4 b3 - UID
93 70 ... ba a3 - “Okay, I wanna talk with you, UID. CRC of this message is ba a3”
08 <CRC> - “Okay, I’m Mifare Classic 1K btw (SAK 0x08), just to remind you”
60 30 <CRC> - “I want to access your block 30 using key A (0x60 at the beginning, 0x61 means key B)”

42 97 c0 a4 - “Sure! Here’s a randomly generated nonce nT. Use Crypto-1 function with my UID, sector key and your random nonce as parameters”
Reader generates keystream ks1 using given parameters. It then picks its own random nonce nR and uses it combined with previous parameters to generate keystream 2 (ks2) by using the same Crypto-1 function
7d db 9b ... - “Okay, here is my random nonce (nR) nR XORed with ks1 you created. I also generated next 64 bits (successor) based on your nonce (using LSFR) and XORed 32 last bits with ks2”
Tag recovers nR by XORing first received result with ks1 it knows. It can then calculate the same ks2 using the same Crypto-1 function as the reader. As a result, it can also verify, that suc2(nT) are in fact the next 32 bits of its nonce nT (by XORing the second result with ks2 it calculated)

The final keystream depends on following parameters: Sector key (K), UID, nT, nR. Specifying any of these wrongly will mess everything up. Every further command is encrypted using an according keystream. They are generated “on-demand” by both tag and reader simultaneously. Thus, if authentication was successful, both devices would have the same keystream at the same time to encrypt/decrypt data.

Exploitation

📘 Note: This section contains information from research papers with over 70 pages in total, as well as blog posts. I cannot guarantee reliability of information, but practical examples should be working, as I tested them myself. Overall, it’s really difficult to summarize this amount of information, but I will do my best.

What kinds of attacks can you perform on such a card? As I told you previously, Mifare Classic family has two interesting properties:

Unique, read-only UID
Protected data

Thanks to our Chinese friends we now have Mifare clones, so-called “magic cards”, which UID can be rewritten. These cards are called “CUID” or “custom UID” cards and are easy to get for under $2 per 5 pieces. We won’t discuss this process in this part, as no special theoretical knowledge is required.

The second point is a more complicated. Classic cards use proprietary Crypto-1 encryption, which may sound as an end to us, hobby researchers and pentesters, but not for professionals. Thanks to a research group from Radbond University, in 2008, we were able to get a full description of this cipher and card communication in general. The correctness of results was proved by NXP themselves, as they tried to stop paper publishing by judicial process. After reverse-engineering the new open-source library, people found the following attack vectors:

Keystream recovery
LSFR Rollback
Authentication replay
Nested attack
Darkside attack
Hardnested attack

Brute-force is a classical approach against security systems, but very inefficient with no known information at all. Considering high possibility count (2^48, since the key is 6 bytes long) and low transmission speed of 106 kbits/s, we would need at least

(2^48 [possib.] * 48 [bits]) / 106000 [kbit/s] / 60 [sec] / 60 [min] / 24 [hr] / 365 [days] = 4000+ years

For one sector, excluding time needed for a single authentication and a small delay inbetween. Nevertheless, looking at the variety of exploits, it can already be assumed that this system is still 99% doomed.

To better understand all following details, you need to know one thing, which causes all the chaos: PRNG (“Pseudo Ransom Number Generator”) is broken. The paper from “pioneers” of Crypto-1 mechanism explains this problem the best:

The random numbers on Mifare Classic tags are generated using a Linear Feedback Shift Register (“LFSR”) with constant initial condition. Each random value, therefore, only depends on the number of clock cycles elapsed between the time the tag is powered up (and the register starts shifting) and the time the random number is extracted. The numbers have a maximum length of 16-bit. Aside from the highly insufficient length of the random numbers, an attacker that controls the timing of the protocol controls the generated number. The weakness of the PRNG is amplified by the fact that the generating LFSR is reset to a known state every time the tag starts operating.

All attacks above are possible, because an attacker completely controls both reader and tag, knows card’s UID, nR, and, due to PRNG weakness, can control nT value.

📘 Note: Most attack vectors have been fixed in the hardened “EV1” version of Mifare Classic cards. They still use the same cipher though, and after some time researchers were able to develop the hardnested attack, especially for this type of tags.

Keystream recovery

Keystream recovery is the fundamental attack against Mifare Classic cards. Using the weakness in PRNG we are able to get a keystream and thus be able to read/modify memory contents! The following explanation was taken from this research paper:

To recover the keystream we exploit the weakness of the pseudo-random generator. As it is this random nonce in combination with only one valid response of the reader what determines the remaining keystream. For this attack we need complete control over the reader (Proxmark) and access to a (genuine) card. The attack consists of
the following steps:

1. Eavesdrop the communication between a reader and a card. This can be for example in an access control system or public transport system.
2. Make sure that the card will use the same keystream as in the recorded communication. This is possible because the card repeats the same nonce in reasonable time, and we completely control the reader.
3. Modify the plaintext, such that the card receives a command for which we know plaintext in the response (e.g., by changing the block number in a read command).
4. For each segment of known plaintext, compute the corresponding keystream segment.
5. Use this keystream to partially decrypt the trace obtained in 1.
6. Try recovering more keystream bits by shifting commands

Unfortunately, I wasn’t able to fully understand the approach. But I’ll guess what’s going on here:

As said, an attacker controls power cycle of the card. Combined with predictable PRNG we can get a nonce nT (step 2 above) which corresponds to one in a recorded communication (step 1). Then, researchers made the following:

We can flip ciphertext bits to try to modify the first command [in a recording] such that it gives another result. Another result gives us another plaintextmemory-layout [...]
We recorded an increment followed by a transfer command. We used this trace to apply our attack and changed the first command to a read command which consists of 4 command bytes and delivers 18 response bytes. Together with the parity bits this makes it a 198 bit stream. The plaintext was known and therefore we recovered 198 keystream bits [...]
Take the recovered keystream and strip all the keystream bits from it that were at parity bit positions. The remaining keystream can be used to encrypt new messages. Every time a parity bit needs to be encrypted, use the next keystream bit without shifting the keystream, in all other cases use the next keystream bit and shift the keystream

Basically, returned cipher text is just plaintext XOR keystream. Knowing plaintext of a response (e.g if you are reading a block with 0 values) you can obtain a keystream. It can be used in next sessions with the same nonce nT to encrypt and decrypt about 198 bits of data, including commands and responses. If you need more - just “restart” the tag and initialize it with the same nonce nT.

As said, these are just my guesses about a practical demonstration in the same research paper linked above. Remember, that all used literature in the article is linked directly in text and at the bottom of the page, so feel free to learn more from original sources yourself.

Authentication Replay

This one is easier to understand. Imagine you top up your card with credits using an NFC terminal. The terminal knows the key and executes an INCREMENT on a value in a sector. You recorded this communication, what now? Since PRNG is predictable, we send authentication requests as long as we get the same nonce as one in the recorded communication. Because we access the same sector on the same card, we can replay step 9 from the picture above (to complete the authentication) and the INCREMENT request. The card will spot no difference from a valid NFC terminal, as both transactions share the same nonce and thus the same keystream. Here is the original explanation:

To replay an authentication we first need a trace of a successful authentication between a genuine mifare reader and card. An example of an authentication followed by one read command is shown below.

1 PCD 60 03 6e 49
2 TAG e0 92 93 98
3 PCD ad e7 96! 48! 20! 22 df 93
4 TAG bf 06 91! 82
5 PCD b5! 05! 47 3f
6 TAG 3f 14! 4f e9! 86 38! 96! 85 3e!
f3 e3! 3d! eb! 2b! a2 d4 dd 76!

After we recorded an authentication between card and reader, we do not modify the memory. This ensures that the memory of the card remains unaltered and therefore it will return the same plaintext. Now we will act like a mifare reader and try to initiate the same authentication. In short:

1. We recorded a trace of a successful authentication between a genuine card and reader.
2. We send authentication requests (#1) until we get a nonce that is equal to the one (#2) in the original trace.
3. We send the recorded response (#3) to this nonce. It consists of a valid response to the challenge nonce and a challenge from the reader.
4. We retrieve the response (#4) to the challenge from the card.
5. Now we are at the point where we could resend the same command (#5) or attempt to modify it.

LSFR Rollback

This is the second fundamental attack used by methods below to recover sector key in plaintext. LSFR is used to continuously generate keystream(s), but the process can be reversed! Using previously recovered (last) keystream, we can obtain current register state (its bits) and then use a weakness in the filter function (don’t ask me what it is) to roll LSFR back to the initial state when the sector key was put into. Knowing nT and UID (which are used to initialize cipher), we can obtain the key in plaintext. Here is the original explanation:

[...] However, the input to the filter function f does not include the leftmost bit of the LFSR. This weakness does enable us to recover this state (and the plaintext reader nonce) anyway. To do so we shift the LFSR to the right; the rightmost bit falls out and we set the leftmost bit to an arbitrary value r. Then we compute the function f and we get one bit of keystream that was used to encrypt the last bit nR,31 of the reader nonce. Note that the leftmost bit of the LFSR is not an input to the function f, and therefore our choice of r is irrelevant. Using the encrypted reader nonce we recover nR,31. Computing the feedback of the LFSR we can now set the bit r to the correct value, i.e., so that the LFSR is in the state prior to feeding nR,31. Repeating this procedure 31 times more, we recover the state of the LFSR before the reader nonce was fed in. Since the tag nonce and uid are sent as plaintext, we also recover the LFSR state before feeding in nT XOR uid (step 4). Note that this LFSR state is the secret key!

Nested attack

Knowing the basics of Mifare Classic weaknesses, researchers implemented the most popular “nested” attack, which requires only one known key and works the following way:

Authenticate to an exploit sector with known key (and receive nonce nT in clear)
Send an auth command with a request to use known A or B key (step 7 above). On success, communication will be encrypted and thus, new nonce nT' will be also sent encrypted
Obtain clear nonce nT2 from nT' by XORing encrypted version with keystream from step 1
Calculate median LSFR shift count (distance) x between first (nT) and second (nT2) nonce generation
Reset card and repeat step 1
Send an auth command with a request to use AN UNKNOWN A or B key. This will give us encrypted nonce nT' to brute-force
Generate a small pool of possible plaintext nonces for the encrypted one in range x-y - x+y, where y is tolerance of about 20 nonces
1. For each one, XOR it with nT' to obtain ks1. Check if ks1 is a valid keystream by checking parity bits. If correct, plaintext nonce nT2 is also correct
2. Perform LSFR Rollback and obtain the key
3. If not valid, generate next 2 bits of nT2 and loop, until we reach nonce at x+y (median distance + tolerance). This way we reduce possible nonce count to only a small pool, specified by tolerance y Nt ... x-y ... Correct Nt2 somewhere here ... x+y

To implement these steps, an easy to use tool called mfoc was created. Combined with libnfc, it allows one to recover all keys (both A and B) by knowing a single key to any sector. If someone is interested, here is the detailed explanation of what the tool does:

📘 Note: All following underscored names are variable/function names used in code. Everything else highlighted the same way (but without an underline) are placeholder names used only in this explanation

Probe default keys on all sectors
Use any exploit sector with default key for an attack
For each key:
1. For each sector:
  1. Try already found keys
  2. If A found, B should be revealed after read. If not, continue
  3. Function mf_enhanced_auth(... mode ...)
    1. Send auth request Auth with KNOWN KEY code (MC_AUTH_A/MC_AUTH_B)
    2. Receive tag nonce Nt
    3. Initialize cipher (pcs) with known key (KeyA/KeyB) in first place
    4. Append UID XOR Nt to LSFR
    5. Generate Nr, encrypt and send (ArEnc)
    6. Skip 32 bits of Nt (successor)
    7. XOR next byte (8 bit) with tag nonce Nt
    8. Transmit answer and verify received answer as suc3(Nt)
```
8 steps above represent just a normal authentication process
```
    9. “Get Distances” mode (mode == “d”):
      1. Encrypt the same auth command Auth with current keystream, send it and receive encrypted nonce Nt'
      2. Reinitialize cipher (pcs) with the SAME KNOWN KEY (KeyA/KeyB)
      3. Obtain plaintext nonce Nt2 by using Nt' XOR crypto1_word(Nt' XOR UID, is_encrypted=true) and validate it
      4. Calculate LSFR shift count between Nt and Nt2 (distances)
      5. Repeat steps 6-8 above to verify obtained Nt2
      6. Return median distance x between two given nonces (median)
    10. “Get Recovery” mode (mode == “r”):
      1. Repeat 9.1 and 9.2 with UNKNOWN KEY CODE and obtain encrypted nonce Nt' (NtEnc)
      2. Generate next x-y bits of Nt (plaintext auth), where y is DEFAULT_TOLERANCE = 20. Created plaintext nonce will be called Nt2 (NtProbe)
      3. Loop:
        
        “Recover” ks1 by XORing Nt' with Nt2
        
        Check if ks1 is a valid keystream by checking parity bits. If correct, plaintext nonce Nt2 is also correct
        
        Perform LSFR Rollback and obtain the key
        
        If not, generate next 2 bits of Nt2 and loop, until we reach nonce at x+y (median distance + tolerance). This way we reduce possible nonce count to only a small pool, specified by DEFAULT_TOLERANCE Nt ... x-y ... Correct Nt2 somewhere here ... x+y
  4. Execute mf_enhanced_auth("d") to obtain median distance
  5. Execute mf_enhanced_auth("r") to obtain the key

Darkside attack

Pretty easy to recover everything by knowing almost nothing at all, right? But what if we don’t know no keys at all? This is where “darkside” attack can help. It abuses encrypted NACK error code, when we send incorrect data, but correct parity bits. Since we know plaintext code of 0x5, we can recover 4 bits of keystream per attempt. After 8 attempts we would have enough info (32 bits) to perform LSFR Rollback and obtain the key. Since we can’t directly recover the whole keystream and rely on a lot of “guessing”, this approach is much slower than one showed above. Therefore, it is recommended to switch to nested attack after obtaining one key using the darkside one.

For this method, another tool called mfcuk was developed, which works the following way:

For each last block of a sector - call mfcuk_key_recovery_block(... ui64Key ...) with ui64Key set to 0
1. Send auth request (abtAuth) with key type to recover (bKeyType)
2. Save plaintext tag nonce Nt and check if it was already observed
  1. If not, add it to an array with unique nonces, generate fixed (hardcoded) reader nonce Nr (spoofNrEnc), wrong challenge response Ar (spoofArEnc), set parity bits P to 0 (spoofParBitsEnc) and current attempt Att to -1 (stage 1) (current_out_of_8)
  2. Else, validate count of checked parity possibilities against a known nonce
    1. If all 3-bit-parities (8 possibilities) checked OR (stage 2 (Att >= 0) AND above 32 combinations of the last 5 bits of parity bits which generated the first NACK)
    2. generate next Nr, reset P to 0 and Att to -1 (stage 1)
    3. Initialize Crypto-1 with key set to 0 and UID XOR Nt
    4. Encrypt Nr and P
    5. Skip 32 bits of Nt (successor)
    6. Encrypt Ar and P with new keystream
    7. If Att >= 0 (stage 2), increment
    8. Transmit 2 answers
      1. If transmission failed (nfc_initiator_transceive_bits == -1), increment P and start from beginning
      2. Else if response is 4 bit - parity bits are correct and encrypted NACK (0x5) response code received
      3. If we are at stage 1 (Att == -1)
        
        Save encrypted NACK response NACK' (spoofNackEnc)
        
        Get 4 bit keystream by XORing NACK' with known 0x5 value (will not be used later, I don’t know why)
        
        Save first 29 bits of Nr (nrEnc) and 3 bits of P (parBits)
        
        Switch to stage 2 (Att = 0)
      4. Else if we are at stage 2 (Att >= 0)
        
        Add encrypted NACK response NACK' into array nackEnc
        
        Decode another 4 bits of keystream as in step 2 of stage 1 above. Save this information into ks array
        
        Increment Att
        
        If Att == 8, then 32 bit keystream recovered
        
        Try to perform LSFR Rollback and obtain the key. If no success, reset Nr, P and Att to stage 1
      5. Else if response is 32 bits long - we were VERY lucky and the “dummy” key we initialized cipher with (ui64Key) is correct!

Hardnested attack

Remember the statement that a key brute-force is very inefficient? It is, unless it is an offline attack with a reduced key space. This is the approach hardnested attack uses. By collecting lots of encrypted nonces, it reduces possible key space and then performs an offline brute-force with LSFR Rollback, where it checks parity bits to find a valid key. However, more detailed explanation of this method is so (mathematically and generally) complex, that I won’t go too deep. If you are interested - the paper is linked above and at the bottom of the page :)

Conclusion

Unless you have a “hardened” EV1 version of the Classic card, above attacks guarantee 99% data recovery rate. Even with a 4K card and no known keys it takes under 15 minutes to fully clone a card by combining nested and darkside attacks. If you are interested in practical demonstrations, you should definitely check out part 2. I won’t say goodbye at this point, see you in the next article!

Memory layout#

Communication#

Exploitation#

Keystream recovery#

Authentication Replay#

LSFR Rollback#

Nested attack#

Darkside attack#

Hardnested attack#

Conclusion#

Literature#