Dismantling MIFARE Classic.pdf

发布时间：2022-04-13 发布人：admin 分类：互联网资料大小：0.55M 资料格式：pdf 举报版权申诉

第1页 / 共18页

第2页 / 共18页

第3页 / 共18页

第4页 / 共18页

第5页 / 共18页

第6页 / 共18页

第7页 / 共18页

第8页 / 共18页

Introduction

Hardware Setup

Logical Structure of the MIFARE Classic Tags

Authentication Protocol

Known Plaintext

CRYPTO1 Cipher

Initialization

Filter function

MIFARE Weaknesses and Exploits

LFSR State Recovery

LFSR Rollback

Odd Inputs to the Filter Function

Parity Bits

Attacking MIFARE

Multiple-Sector Authentication

Consequences and Conclusions

Dismantling MIFARE Classic Flavio D. Garcia, Gerhard de Koning Gans, Ruben Muijrers, Peter van Rossum, Roel Verdult, Ronny Wichers Schreur, and Bart Jacobs Institute for Computing and Information Sciences, Radboud University Nijmegen, The Netherlands {flaviog,petervr,ronny,bart}@cs.ru.nl {gkoningg,rmuijrer,rverdult}@sci.ru.nl Abstract. The mifare Classic is a contactless smart card that is used extensively in access control for oﬃce buildings, payment systems for public transport, and other applications. We reverse engineered the se- curity mechanisms of this chip: the authentication protocol, the symmet- ric cipher, and the initialization mechanism. We describe several security vulnerabilities in these mechanisms and exploit these vulnerabilities with two attacks; both are capable of retrieving the secret key from a genuine reader. The most serious one recovers the secret key from just one or two authentication attempts with a genuine reader in less than a second on ordinary hardware and without any pre-computation. Using the same methods, an attacker can also eavesdrop the communication between a tag and a reader, and decrypt the whole trace, even if it involves multiple authentications. This enables an attacker to clone a card or to restore a real card to a previous state. 1 Introduction Over the last few years, more and more systems adopted RFID and contactless smart cards as replacement for bar codes, magnetic stripe cards and paper tickets for a wide variety of applications. Contactless smart cards consist of a small piece of memory that can be accessed wirelessly, but unlike RFID tags, they also have some computing capabilities. Most of these cards implement some sort of simple symmetric-key cryptography, making them suitable for applications that require access control to the smart card’s memory. A number of large-scale applications make use of contactless smart cards. For example, they are used for payment in several public transport systems like the Oyster card1 in London and the OV-Chipkaart2 in The Netherlands, among oth- ers. Many countries have already incorporated a contactless smart card in their electronic passports [HHJ+06]. Many oﬃce buildings and even secured facilities like airports and military bases use contactless smart cards for access control. There is a huge variety of cards on the market. They diﬀer in size, casing, mem- ory, and computing power. They also diﬀer in the security features they provide. 1 http://oyster.tfl.gov.uk 2 http://www.ov-chipkaart.nl S. Jajodia, and J. Lopez (Eds.): ESORICS 2008, LNCS 5283, pp. 97–114, 2008. c Springer-Verlag Berlin Heidelberg 2008

98 F.D. Garcia et al. A well known and widely used system is mifare. This is a product family from NXP Semiconductors (formerly Philips Semiconductors), currently consisting of four diﬀerent types of cards: Ultralight, Classic, DESFire and SmartMX. Ac- cording to NXP, more than 1 billion mifare cards have been sold and there are about 200 million mifare Classic tags in use around the world, covering about 85% of the contactless smart card market. Throughout this paper we focus on this tag. mifare Classic tags provide mutual authentication and data secrecy by means of the so called CRYPTO1 cipher. This is a stream cipher using a 48 bit secret key. It is proprietary of NXP and its design is kept secret. Our Contribution. This paper describes the reverse engineering of the mifare Classic chip. We do so by recording and studying traces from communication between tags and readers. We recover the encryption algorithm and the authen- tication protocol. It also unveils several vulnerabilities in the design and imple- mentation of the mifare Classic chip. This results in two attacks that recover a secret key from a mifare reader. The ﬁrst attack uses a vulnerability in the way the cipher is initialized to split the 48 bit search space in a k bit online search space and 48− k bit oﬄine search space. To mount this attack, the attacker needs to gather a modest amount of data from a genuine reader. Once this data has been gathered, recovering the secret key is as eﬃcient as a lookup operation on a table. Therefore, it is much more eﬃcient than an exhaustive search over the whole 48 bit key space. The second and more eﬃcient attack uses a cryptographic weakness of the CRYPTO1 cipher allowing us to recover the internal state of the cipher given a small part of the keystream. To mount this attack, one only needs one or two partial authentication from a reader to recover the secret key within one second, on ordinary hardware. This attack does not require any pre-computation and only needs about 8 MB of memory to be executed. When an attacker eavesdrops communication between a tag and a reader, the same methods enable us to recover all keys used in the trace and decrypt it. This gives us suﬃcient information to read a card, clone a card, or restore a card to a previous state. We have successfully executed these attacks against real systems, including the London Oyster Card and the Dutch OV-Chipkaart. Related Work. De Koning Gans, Hoepman and Garcia [KHG08] proposed an attack that exploits the malleability of the CRYPTO1 cipher to read partial information from a mifare Classic tag. Our paper diﬀers from [KHG08] since the attacks proposed here focus on the reader. Nohl and Pl¨otz have partly reverse engineered the mifare Classic tag earlier [NP07], although not all details of their ﬁndings have been made public. Their research takes a very diﬀerent, hardware oriented, approach. They recovered the algorithm, partially, by slicing the chip and taking pictures with a microscope. They then analyzed these pictures, looking for speciﬁc gates and connections. Their presentation has been of great stimulus in our discovery process. Our approach, however, is radically diﬀerent as our reverse engineering is based on the study of the communication behavior of tags and readers. Furthermore,

Dismantling MIFARE Classic 99 the recovery of the authentication protocol, the cryptanalysis, and the attacks presented here are totally novel. Overview. In Section 2 we brieﬂy describe the hardware used to analyze the mifare Classic. Section 3 summarizes the logical structure of the mifare Classic. Section 4 then describes the way a tag and a reader authenticate each other. It also details how we reverse engineered this authentication protocol and points out a weakness in this protocol enabling an attacker to discover 64 bits of the keystream. Section 5 describes how we recovered the CRYPTO1 cipher by interacting with genuine readers and tags. Section 6 then describes four concrete weaknesses in the authentication protocol and the cipher and how they can be exploited. Section 7 describes how this leads to concrete attacks against a reader. Section 8 shows that these attacks are also applicable if the reader authenticates for more than a single block of memory. Section 9 describes consequences and conclusions. 2 Hardware Setup For this experiment we designed and built a custom device for tag emulation and eavesdropping. This device, called Ghost, is able to communicate with a contactless smart card reader, emulating a tag, and eavesdrop communication between a genuine tag and reader. The Ghost is completely programmable and is able to send arbitrary messages. We can also set the uid of the Ghost which is not possible with manufacturer tags. The hardware cost of the Ghost is approxi- mately e40. We also used a ProxMark3, a generic device for communication with RFID tags and readers, and programmed it to handle the ISO14443-A standard. As it provides similar functionality to the Ghost, we do not make a distinction between these devices in the remainder of the paper. On the reader side we used an OpenPCD reader4 and an Omnikey reader5. These readers contain a mifare chip implementing the CRYPTO1 cipher and are fully programmable. Notation. In mifare, there is a diﬀerence between the way bytes are repre- sented in most tools and the way they are being sent over the air. The former, consistent with the ISO14443 standard, writes the most signiﬁcant bit of the byte on the left, while the latter writes the least signiﬁcant bit on the left. This means that most tools represent the value 0x0a0b0c as 0x50d030 while it is sent as 0x0a0b0c on the air. Throughout this paper we adopt the latter convention (with the most signiﬁcant bit left, since that has nicer mathematical proper- ties) everywhere except when we show traces so that the command codes are consistent with the ISO standard. Finally, we number bits (in keys, nonces, and cipher states) from left to right, starting with 0. For data that is transmitted, this means that lower numbered bits are transmitted before higher numbered bits. 3 http://cq.cx/proxmark3.pl,http://www.proxmark.org 4 http://www.openpcd.org 5 http://omnikey.aaitg.com

100 F.D. Garcia et al. 3 Logical Structure of the MIFARE Classic Tags The mifare Classic tag is essentially an eeprom memory chip with secure com- munication provisions. Basic operations like read, write, increment and decre- ment can be performed on this memory. The memory of the tag is divided into sectors. Each sector is further divided into blocks of 16 bytes each. The last block of each sector is called the sector trailer and stores two secret keys and access conditions corre- sponding to that sector. To perform an operation on a speciﬁc block, the reader must ﬁrst authenticate for the sector containing that block. The access conditions of that sector determine whether key A or B must be used. Figure 1 shows a schematic of the logical structure of the mem- ory of a mifare Classic tag. Fig. 1. Logical structure 4 Authentication Protocol When the tag enters the electromagnetic ﬁeld of the reader and powers up, it immediately starts the anti-collision protocol by sending its uid. The reader then selects this tag as speciﬁed in ISO14443-A [ISO01]. According to the manufacturer’s documentation, the reader then sends an authentication request for a speciﬁc block. Next, the tag picks a challenge nonce nT and sends it to the reader in the clear. Then the reader sends its own challenge nonce nR together with the answer aR to the challenge of the tag. The tag ﬁnishes authentication by replying aT to the challenge of the reader. Starting with nR, all communication is encrypted. This means that nR, aR, and aT are XOR-ed with the keystream ks1, ks2, ks3. Figure 2 shows an example. Hex Abstract Step Sender 01 02 03 04 05 06 07 08 09 10 req type A answer req select uid,bcc Reader 26 Tag 04 00 Reader 93 20 Tag Reader 93 70 c2 a8 2d f4 b3 ba a3 select(uid) mifare 1k Tag auth(block 30) Reader 60 30 76 4a Tag 42 97 c0 a4 nT nR ⊕ ks1, aR ⊕ ks2 Reader 7d db 9b 83 67 eb 5d 83 aT ⊕ ks3 Tag c2 a8 2d f4 b3 08 b6 dd 8b d4 10 08 Fig. 2. Authentication Trace

Dismantling MIFARE Classic 101 We started experimenting with the Ghost and an OpenPCD reader which we control. The pseudo-random generator in the tag is fully deterministic. Therefore the nonce it generates only depends on the time between power up and the start of communication [NP07]. Since we control the reader, we control this timing and therefore can get the same tag nonce every time. With the Ghost operating as a tag, we can choose custom challenge nonces and uids. Furthermore, by ﬁxing nT (and uid) and repeatedly authenticating, we found out that the reader produces the same sequence of nonces every time it is restarted. Unlike in the tag, the state of the pseudo-random generator in the reader does not update every clock tick but with every invocation. The pseudo-random generator in the tag used to generate nT is a 16 bit LFSR with generating polynomial x16+x14+x13+x11+1. Since nonces are 32 bits long and the LFSR has a 16 bit state, the ﬁrst half of nT determines the second half. This means that given a 32 bit value, we can tell if it is a proper tag nonce, i.e., if it could be generated by this LFSR. To be precise, a 32 bit value n0n1 . . . n31 is a proper tag nonce if and only if nk ⊕ nk+2 ⊕ nk+3 ⊕ nk+5 ⊕ nk+16 = 0 for all k ∈ {0, 1, . . . , 15}. Remark that the Ghost can send arbitrary values as nonces and is not restricted to sending proper tag nonces. Experimenting with authentication sessions with various uids and tag nonces, we noticed that if nT ⊕ uid remains constant, then the ciphertext of the en- crypted reader nonce also remains constant. The answers aT and aR, however, have diﬀerent ciphertexts in the two sessions. For example, in Figure 2 the uid is 0xc2a82df4 and nT is 0x4297c0a4, therefore nT ⊕ uid is 0x803fed50. If we instead take uid to be 0x1dfbe033 and nT to be 0x9dc40d63, then nt ⊕ uid still equals 0x803fed50. In both cases, the encrypted reader nonce nR ⊕ ks1 is 0x7ddb9b83. However, in Figure 2, aR ⊕ ks2 is 0x67eb5d83 and aT ⊕ ks3 is 0x8bd41008, while with the modiﬁed uid and nT they are, respectively, 0x4295c446 and 0xeb3ef7da. This suggests that the keystream in both runs is the same and it also suggests ⊕ ks2 that aT and aR depend on nT . By XOR-ing both answers aR ⊕ ks2 and a together we get aR⊕ a R is a proper tag nonce. Because the set of proper tag nonces is a linear subspace of F32 2 , where F2 is the ﬁeld of two elements, the XOR of proper tag nonces is also a proper tag nonce. This suggests that aR and a R. We noticed that aR⊕ a R are also proper tag nonces. R Given a 32 bit nonce nT generated by the LFSR, one can compute the suc- cessor suc(nT ) consisting of the next 32 generated bits. At this stage we could R = suc2(nT ⊕ n T ) = suc2(nT )⊕ suc2(n verify that aR ⊕ a T ) which suggests that aR = suc2(nT ) and a R = suc2(n T ). Similarly for the answer from the tag we could verify that aT = suc3(nT ) and a T = suc3(n Summarizing, the authentication protocol can be described as follows; see Figure 3. After the nonce nT is sent by the tag, both tag and reader initialize the cipher with the shared key K, the uid, and the nonce nT . The reader then picks its challenge nonce nR and sends it encrypted with the ﬁrst part of the keystream ks1. Then it updates the cipher state with nR. The reader authenticates by sending suc2(nT ) encrypted, i.e., suc2(nT ) ⊕ ks2. At this point the tag is able T ).

102 F.D. Garcia et al. Tag 0 1 2 picks nT 3 4 ks1 ← cipher(K, uid, nT ) 5 6 7 8 ks2, . . . ← cipher(nR) 9 −−−−−−−−−−−−−−−−−−−−→ ←−−−−−−−−−−−−−−−−−−−− anti-c(uid) auth(block) −−−−−−−−−−−−−−−−−−−−→ nT nR ⊕ ks1, suc2(nT ) ⊕ ks2 ←−−−−−−−−−−−−−−−−−−−− suc3(nT ) ⊕ ks3 −−−−−−−−−−−−−−−−−−−−→ Reader ks1 ← cipher(K, uid, nT ) picks nR ks2, . . . ← cipher(nR) Fig. 3. Authentication Protocol to update the cipher state in the same way and verify the authenticity of the reader. The remainder of the keystream ks3, ks4 . . . is now determined and from now on all communication is encrypted, i.e., XOR-ed with the keystream. The tag ﬁnishes the authentication protocol by sending suc3(nT ) ⊕ ks3. Now the reader is able to verify the authenticity of the tag. 4.1 Known Plaintext From the description of the authentication protocol it is easy to see that parts of the keystream can be recovered. Having seen nT and suc2(nT ) ⊕ ks2, one can recover ks2 (i.e., 32 bits of keystream) by computing suc2(nT ) and XOR-ing. Moreover, experiments show that if in step 9 of the authentication protocol the tag does not send anything, then most readers will time out and send a halt command. Since communication is encrypted it actually sends halt ⊕ ks3. Knowing the byte code of the halt command (0x500057cd [ISO01]) we recover ks3. Some readers do not send a halt command but instead continue as if au- thentication succeeded. This typically means that it sends an encrypted read command. As the byte code of the read command is also known [KHG08], this also enables us to recover ks3 by guessing the block number. It is important to note that one can obtain such an authentication session (or rather, a partial authentication session, as the Ghost never authenticates itself) from a reader (and hence ks2, ks3) without knowing the secret key and, in fact, without using a tag. If an attacker does have access to both a tag and a reader and can eavesdrop a successful (complete) authentication session, then both ks2 and ks3 can be recovered from the answers suc2(nT )⊕ ks2 and suc3(nT )⊕ ks3 of the tag and the reader. This works even if the reader does not send halt or read after timeout. 5 CRYPTO1 Cipher The core of the CRYPTO1 cipher is a 48-bit linear feedback shift register (LFSR) with generating polynomial g(x) = x48 + x43 + x39 + x38 + x36 + x34 + x33 +

Dismantling MIFARE Classic 103 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 fa = 0x2c79 fb = 0x6671 fb = 0x6671 fb = 0x6671 fa = 0x2c79 fc = 0x7907287b keystream (initialization only) Fig. 4. The Hitag2 Cipher ⊕ ⊕/ input x31 + x29 + x24 + x23 + x21 + x19 + x13 + x9 + x7 + x6 + x5 + 1. This polynomial was given in [NESP08]; note it can also be deduced from the relation between uid and the secret key described in [NP07]. At every clock tick the register is shifted one bit to the left. The leftmost bit is discarded and the feedback bit is computed according to g(x). Additionally, the LFSR has an input bit that is XOR-ed with the feedback bit and then fed into the LFSR on the right. To be precise, if the state of the LFSR at time k is rkrk+1 . . . rk+47 and the input bit is i, then its state at time k + 1 is rk+1rk+2 . . . rk+48, where rk+48 = rk ⊕ rk+5 ⊕ rk+9 ⊕ rk+10 ⊕ rk+12 ⊕ rk+14 ⊕ rk+15 ⊕ rk+17 ⊕ rk+19 ⊕ (1) rk+24 ⊕ rk+27 ⊕ rk+29 ⊕ rk+35 ⊕ rk+39 ⊕ rk+41 ⊕ rk+42 ⊕ rk+43 ⊕ i. The input bit i is only used during initialization. To encrypt, selected bits of the LFSR are put through a ﬁlter function f. Exactly which bits of the LFSR are put through f and what f actually is, was not revealed in [NP07]. Note that the general structure of CRYPTO1 is very similar to that of the Hitag2. This is a low frequency tag from NXP; the description of the cipher used in the Hitag2 is available on the Internet6. We used this to make educated guesses about the details of the initialization of the cipher (see Section 5.1 below) and about the details of the ﬁlter function f (see Section 5.2 below). 5.1 Initialization The LFSR is initialized during the authenti- cation protocol. As before, we experimented running several authentication sessions with varying parameters. As we mention in Sec- tion 4, if nT ⊕ uid remains constant, then the encrypted reader nonce also remains con- stant. This suggests that nT ⊕ uid is ﬁrst fed into the LFSR. Moreover, experiments showed that, if special care is taken with the 6 http://cryptolib.com/ciphers/hitag2/ Fig. 5. Initialization Diagram o o o o O O O O /

F.D. Garcia et al. 104 feedback bits, it is possible to modify nT ⊕uid and the secret key K in such a way that the ciphertext after authentication also remains constant. Concretely, we veriﬁed that if nT ⊕uid⊕K⊕‘feedback bits’ remains constant, then the keystream generated after authentication is constant as well. Here the ‘feedback bits’ are computed according to g(x). This suggests that the secret key K is the initial state of the LFSR. This also suggests that the keystream feedback loop from the output back to the LFSR present in the Hitag2 cipher is not present on CRYPTO1, which greatly simpliﬁed the analysis. Proceeding to the next step in the authentication protocol, the reader nonce nR is fed into the LFSR as well. Note that earlier bits of nR already aﬀect the encryption of the later bits of nR. At this point, the initialization is complete and the input bit of the LFSR is no longer used. Figure 5 shows the initialization diagram for both reader and tag. The only diﬀerence is that the reader generates nR and then computes and sends nR ⊕ ks1, while the tag receives nR ⊕ ks1 and then computes nR. Note that we can, by selecting an appropriate key K, uid, and tag nonce nT , totally control the state of the LFSR just before feeding in the reader nonce. In practice, if we want to observe the behavior of the LFSR starting in state α, we often set the key to 0, let the Ghost select a uid of 0 and compute which nT we should let the Ghost send to reach the state α. Now, because nT is only 32 bits long and α is 48 bits long, this does not seem to allow us to control the leftmost 16 bits of α: they will always be 0. In practice, however, many readers accept and process tag nonces of arbitrary length. So by sending an appropriate 48 bit tag nonce nT , we can fully control the state of the LFSR just before the reader nonce. This will be very useful in the next section, where we describe how we recovered the ﬁlter function f. 5.2 Filter function The ﬁrst time the ﬁlter function f is used, is when the ﬁrst bit of the reader nonce, nR,0, is transmitted. At this point, we fully control the state α of the LFSR by setting the uid, the key, and the tag nonce. As before, we use the Ghost to send a uid of 0, use the key 0 on the reader, and use 48 bit tag nonces to set the LFSR state. So, for values α of our choice, we can observe nR,0⊕ f(α), since that is what is being sent by the reader. Since we power up the reader every time, the generated reader nonce is the same every time. Therefore, even though we do not know nR,0, it is a constant. The ﬁrst task is now to determine which bits of the LFSR are inputs to the ﬁlter function f. For this, we pick a random state α and observe nR,0⊕ f(α). We , and observe nR,0 ⊕ f(α ). then vary a single bit in α, say the ith, giving state α If f(α) = f(α ), then we can draw no conclusion about the ith bit, but if this happens for many choices of α, it is likely that the ith bit is not an input to f. ), then the ith bit must be input to f. If f(α) = f(α Figure 6 shows an example. The key in the reader (for block 0) is set to 0 and the Ghost sends a uid of 0. On the left hand side, the Ghost sends the tag nonce 0x6dc413abd0f3 and on the right hand side it sends the tag nonce

分享到：

赞收藏

资料库

Dismantling MIFARE Classic.pdf

相关推荐

最新资料