Pickpocketing.Mifare(M1卡破解).pdf

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

第1页 / 共13页

第2页 / 共13页

第3页 / 共13页

第4页 / 共13页

第5页 / 共13页

第6页 / 共13页

第7页 / 共13页

第8页 / 共13页

Introduction

Background

Communication

Memory structure of the Mifare Classic

CRYPTO1

Tag nonces

Authentication protocol and initialization

Rollback

Weaknesses

Parity weaknesses

Nested authentications

Attacks

Brute-force attack

Varying the reader nonce

Varying the tag nonce

Nested authentication attack

Conclusions

References

Wirelessly Pickpocketing a Mifare Classic Card Flavio D. Garcia Peter van Rossum Roel Verdult Ronny Wichers Schreur Radboud University Nijmegen, The Netherlands {flaviog,petervr,rverdult,ronny}@cs.ru.nl Abstract The Mifare Classic is the most widely used contactless smartcard on the market. The stream cipher CRYPTO1 used by the Classic has recently been reverse engi- neered and serious attacks have been proposed. The most serious of them retrieves a secret key in under a second. In order to clone a card, previously proposed attacks require that the adversary either has access to an eavesdropped communication session or exe- cutes a message-by-message man-in-the-middle attack between the victim and a legitimate reader. Although this is already disastrous from a cryptographic point of view, system integrators maintain that these attacks cannot be performed undetected. This paper proposes four attacks that can be ex- ecuted by an adversary having only wireless access to just a card (and not to a legitimate reader). The most serious of them recovers a secret key in less than a second on ordinary hardware. Besides the crypto- graphic weaknesses, we exploit other weaknesses in the protocol stack. A vulnerability in the computation of parity bits allows an adversary to establish a side channel. Another vulnerability regarding nested authentications provides enough plaintext for a speedy known-plaintext attack. 1. Introduction With more than one billion cards sold, the Mi- fare Classic covers more than 70% of the contactless smartcard market1. Such cards contain a slightly more powerful IC than classical RFID chips (developed for identiﬁcation only), equipping them with modest computational power and making them suitable for ap- plications beyond identiﬁcation, such as access control and ticketing systems. The Mifare Classic is widely used in public transport payment systems such as the Oyster card2 in London, 1. http://www.nxp.com 2. http://oyster.tﬂ.gov.uk the Charlie Card in Boston3, the SmartRider in Aus- tralia4, EasyCard in Taiwan5, and the OV-chipkaart6 in The Netherlands. It is also widely used for access con- trol in ofﬁce and governmental buildings and military objects. According to [MFS08] the Mifare Classic complies with parts 1 to 3 of the ISO standard 14443-A [ISO01], specifying the physical characteristics, the radio fre- quency interface, and the anti-collision protocol. The Mifare Classic does not implement part 4 of the standard, describing the transmission protocol, but in- stead uses its own secure communication layer. In this layer, the Mifare Classic uses the proprietary stream cipher CRYPTO1 to provide data conﬁdentiality and mutual authentication between card and reader. This ci- pher has recently been reversed engineered [NESP08], [GKM+08]. In this paper, we show serious vulnerabilities of the Mifare Classic that enable an attacker to retrieve all cryptographic keys of a card, just by wirelessly com- municating with it. Thus, the potential impact is much larger than that of the problems previously reported in [GKM+08], [CNO08], [KHG08], [Noh08], where the attacker either needs to have access to a legitimate reader or an eavesdropped communication session. The attacks described in this paper are fast enough to allow an attacker to wirelessly ‘pickpocket’ a victim’s Mifare Classic card, i.e., to clone it immediately. Vulnerabilities. The vulnerabilities we discovered concern the handling of parity bits and nested authen- tications. • The Mifare Classic sends a parity bit for each byte that is transmitted. Violating the standard, the Mifare Classic mixes the data link layer and secure communication layer: parity bits are computed over the plaintext instead of over the 3. http://www.mbta.com/fares and passes/charlie 4. http://www.transperth.wa.gov.au 5. http://www.easycard.com.tw 6. http://www.ov-chipkaart.nl To appear in IEEE Symposium on Security and Privacy (S&P ’09).

i.e., the ciphertext. bits that are actually sent, This is, in fact, authenticate-then-encrypt which is generically insecure [Kra01]. Furthermore, parity bits are encrypted with the same bit of keystream that encrypts the ﬁrst bit of the next byte of plaintext. During the authenti- cation protocol, if the reader sends wrong parity bits, the card stops communicating. However, if the reader sends correct parity bits, but wrong authentication data, the card responds with an (encrypted) error code. This breaks the conﬁ- dentiality of the cipher, enabling an attacker to establish a side channel. • The memory of the Mifare Classic is divided into sectors, each of them having its own 48-bit secret key. To perform an operation on a speciﬁc sector, the reader must ﬁrst authenticate using the corresponding key. When an attacker has already authenticated for one sector (knowing the key for that sector) and subsequently attempts to authenticate for another sector (without knowing the key for this sector), that attempt leaks 32 bits of information about the secret key of that sector. Attacks. We describe four attacks exploiting these vulnerabilities to recover the cryptographic keys from a Mifare Classic card having only contactless com- munication with it (and not with a legitimate reader). These attacks make different trade-offs between online communication time (the time an attacker needs to communicate with a card), ofﬂine computation time (the time it takes to compute the cryptographic key using the data gathered from the card), precomputation time (one-time generation time of static tables), disk space usage (of the static tables) and special assump- tions (whether the attacker has already one sector key or not). • The ﬁrst attack exploits the weakness of the parity bits to mount an ofﬂine brute-force attack on the 48-bit key space. The attacker only needs to try to authenticate approximately 1500 times (which takes under a second). • The second attack also exploits the weakness of the parity bits but this time the attacker mounts an adaptive chosen ciphertext attack. The at- tacker needs approximately 28500 authentication attempts. In this attack, she needs to make sure that the challenge nonce of the card is constant, which is why this takes approximately ﬁfteen minutes. During these authentication attempts, the attacker adaptively chooses her challenge to the card, ultimately obtaining a challenge that guarantees that there are only 436 possibilities 2 for the odd-numbered bits of the internal state of the cipher. This reduces the ofﬂine search space to approximately 33 bits. On a standard desktop computer this search takes about one minute. • In the third attack the attacker keeps her own challenge constant, but varies the challenge of the tag, again ultimately obtaining a special internal state of the cipher. These special states have to be precomputed and stored in a 384 GB table. This attack requires on average 212 = 4096 authenti- cation attempts, which could in principle be done in about two minutes. A few extra authentication attempts allow efﬁcient lookup in the table. • The fourth attack assumes that the attacker has already recovered at least one sector key. When the attacker ﬁrst authenticates for this sector and then for another sector, the authentication protocol is slightly different, viz., the challenge nonce of the tag is not sent in the clear, but encrypted with the key of the new sector. Because the random number generator has only a 16-bit state, because parity bits leak three bits of information, and be- cause the tag’s random number generator runs in sync with the communication timing, this allows an attacker to guess the plaintext tag nonce and hence 32 bits of keystream. Due to weaknesses in the cipher [GKM+08], we can use these 32 bits of keystream to compute approximately 216 candidate keys. These can then be checked ofﬂine using another authentication attempt. Since this attack only requires three authentication attempts, the online time is negligible. The ofﬂine search takes under a second on ordinary hardware. Related work. De Koning Gans et al. [KHG08] have proposed an attack on a Mifare Classic tag that exploits the malleability of the CRYPTO1 stream cipher to read partial information from a tag, without even knowing the encryption algorithm. By slicing a Mifare Classic chip and taking pictures with a microscope, the cipher was reverse engineered by Nohl et al. [NESP08]. Courtois et al. claim in [CNO08] that the CRYPTO1 cipher is susceptible to algebraic attacks and Nohl shows a statistical weakness of the cipher in [Noh08]. A full description of the cipher was given by Garcia et al. in [GKM+08], together with a reverse engineered authentication protocol. They also describe an attack with which an attacker can recover a sector key by communicating with a genuine reader or by eavesdrop- ping a successful authentication. All attacks described in these papers have in com- mon that they need access to a legitimate reader or the attacks intercepted communication. In contrast,

described in our paper only need access to a card. Impact. The implications of the attacks described in this paper are vast. Many ticketing and payment systems using the Mifare Classic sequentially authenticate for several sectors verifying the data in the card. In case of invalid data, the protocol aborts. With previous attacks, this means that an attacker has to either eavesdrop a full trace or walk from the reader to the card holder several times, executing a message-by-message man- in-the-middle attack. In practice, both options are hard to accomplish undetected. Furthermore, there is no guarantee that this allows an attacker to recover all useful data in the card, since some sectors might not be read in this particular instance. Our attacks always enable an attacker to retrieve all data from the card. Our fourth attack, where the attacker already knows a single key, is extremely fast (less than one second per key on ordinary hardware). The ﬁrst key can be re- trieved using one of our ﬁrst three attacks, but in many situations this is not even necessary. Most deployed systems leave default keys for unused sectors or do not diversify keys at all. Nearly all deployed systems that do diversify have at least one sector key that is not diversiﬁed, namely for storing the diversiﬁcation information. This is even speciﬁed in NXP’s guideline for system integrators [MAD07]. This means that it is possible for an adversary to recover all keys necessary to read and write the sixteen sectors of a Mifare Classic 1k tag in less than sixteen seconds. Overview. We start by gathering the relevant informa- tion that is already known about the Mifare Classic in Section 2: its logical structure, the encryption algo- rithm, the authentication protocol and the initialization of the stream cipher, how to undo the initialization of the stream cipher, and information about how the tag generates its random numbers. In Section 3, we continue with a precise description of the discovered weaknesses in the handling of the parity bits and nested authentications. In Section 4, we show how these weaknesses can be exploited to recover a sector key by communication with just a card. Section 5 gives some concluding remarks. 2. Background 2.1. Communication Figure 2.1. Memory layout of the Mifare Classic 14443-A. We have used the Proxmark III7 for commu- nication; this device implements, among others, these two layers of this standard and can emulate both a card and a reader. codes of Using information from [KHG08] about the Mifare Classic the command and from [GKM+08], [NESP08] about the cryptographic aspects of the Mifare Classic, we implemented the functionality of a Mifare Classic reader on the Proxmark. Note that we can observe a tag’s communication at the data link level, implying that we can observe the parity bits as well. Furthermore, we have the freedom to send arbitrary parity bits, which is not possible using stock commercial Mifare Classic readers. However, many newer NFC readers can be used to communicate with a Mifare Classic card as well and are capable of sending and receiving arbitrary parity bits.8 We have also executed the attacks described in this paper using an inexpensive (30 USD) stock commercial NFC reader. However, these readers are typically connected to a host PC using USB and it is harder to obtain accurate communication timing. 2.2. Memory structure of the Mifare Classic The Mifare Classic tag is essentially a memory chip with secure wireless communication capabilities. The memory of the tag is divided into sectors, each of which is further divided into blocks of sixteen bytes each. The last block of each sector is the sector trailer and stores two secret keys and the access conditions for that sector. To perform an operation on a speciﬁc block, the reader must ﬁrst authenticate for the sector containing The physical layer and data link layer of the Mifare family of cards are described in the ISO standard 7. http://www.proxmark.org/ 8. http://www.libnfc.org/ 3

that block. The access conditions determine which of the two keys must be used. See Figure 2.1 for an overview of the memory of a Mifare Classic tag. 2.3. CRYPTO1 After authentication, the communication between tag and reader is encrypted with the CRYPTO1 stream cipher. This cipher consists of a 48-bit linear feed- back shift register (LFSR) with generating polynomial x48+x43+x39+x38+x36+x34+x33+x31+x29+x24+ x23 + x21 + x19 + x13 + x9 + x7 + x6 + x5 + 1 and a non-linear ﬁlter function f [NESP08]. Each clock tick, twenty bits of the LFSR are put through the ﬁlter function, generating one bit of keystream. Then the LFSR shifts one bit to the left, using the generating polynomial to generate a new bit on the right. See Figure 2.2 for a schematic representation. We let F2 = {0, 1} the ﬁeld of two elements (or the set of Booleans). The symbol ⊕ denotes addition (XOR). Deﬁnition 2.1. The feedback function L : F48 2 → F2 is deﬁned by L(x0x1 . . . x47) := x0 ⊕ x5 ⊕ x9 ⊕ x10 ⊕ x12 ⊕ x14 ⊕ x15 ⊕ x17 ⊕ x19 ⊕ x24 ⊕ x25 ⊕ x27 ⊕ x29 ⊕ x35 ⊕ x39 ⊕ x41 ⊕ x42 ⊕ x43. The speciﬁcs of the ﬁlter function are taken from [GKM+08]. Deﬁnition 2.2. The ﬁlter function f : F48 deﬁned by 2 → F2 is f (x0x1 . . . x47) := fc(fa(x9, x11, x13, x15), fb(x17, x19, x21, x23), fb(x25, x27, x29, x31), fa(x33, x35, x37, x39), fb(x41, x43, x45, x47)). 2 → F2 and fc : F5 Here fa, fb : F4 2 → F2 are deﬁned by fa(y0, y1, y2, y3) := ((y0 ∨ y1) ⊕ (y0 ∧ y3)) ⊕ (y2 ∧ ((y0 ⊕ y1) ∨ y3)), fb(y0, y1, y2, y3) := ((y0 ∧ y1) ∨ y2)⊕((y0⊕y1)∧(y2∨y3)), and fc(y0, y1, y2, y3, y4) := (y0 ∨((y1 ∨y4)∧(y3 ⊕y4)))⊕((y0 ⊕(y1 ∧y3))∧((y2 ⊕ y3)∨(y1∧y4))). Because f (x0x1 . . . x47) only depends on x9, x11, . . . , x47, we shall overload notation and see f as a function F20 2 → F2, writing f (x0x1 . . . x47) as f (x9, x11, . . . , x47). Note that fa and fb here are negated when compared to [GKM+08] and fc is changed accordingly. The expressions for fa, fb, and fc given here have the min- imal number of logical operators in {∧, ∨, ⊕, ¬}; in practice, this allows for a fast bitsliced implementation of f [Bih97]. For future reference, note that each of the building blocks of f (and hence f itself) have the property that it gives zero for half of the possible inputs (respectively one). Theorem 2.3. Let Y0, Y1, . . . , Y4 be independent uni- formly distributed variables over F2. Then P [fa(Y0, Y1, Y2, Y3) = 0] = 1/2 P [fb(Y0, Y1, Y2, Y3) = 0] = 1/2 P [fc(Y0, Y1, Y2, Y3, Y4) = 0] = 1/2. Proof. By inspection. 2.4. Tag nonces For use in the authentication protocol, described in Section 2.5 below, Mifare Classic tags possess a pseudo-random generator. In [NP07] it was revealed that the 32-bit tag nonces are generated by a 16-bit LFSR with generating polynomial x16 + x14 + x13 + x11 + 1. Every clock tick the LFSR shifts to the left and the feedback bit is computed using L16. Deﬁnition 2.4. The feedback function L16 : F16 of the pseudo-random generator is deﬁned by 2 → F2 L16(x0x1 . . . x15) := x0 ⊕ x2 ⊕ x3 ⊕ x5. Let us deﬁne the function suc that computes the next 32-bit LFSR sequence of the 16-bit LFSR. This func- tion is used later on in Section 2.5 in the authentication protocol. Deﬁnition 2.5. The successor function suc : F32 F32 2 is deﬁned by 2 → suc(x0x1 . . . x31) := x1x2 . . . x31L16(x16x17 . . . x31) . Because the period of the pseudo-random generator is only 65535 and because it shifts every 9.44µs, it cycles in 618ms. Under similar physical conditions (i.e., do not move the tag or the reader), the challenge nonce that the tag generates only depends on the time between the mo- ment the reader switches on the electromagnetic ﬁeld and the moment it sends the authentication request. In practice, this means that an attacker who has physical control of the tag, can get the tag to send the same nonce every time. To do so, the attacker just has to drop the ﬁeld (for approximately 30µs) to discharge all capacitors in the tag, switch the ﬁeld back on, and wait for a constant amount of time before authenticating. Alternatively, by waiting exactly the right amount of time before authenticating again, the attacker can control the challenge nonce that the tag will send. This works whenever the tag does not leave the electromag- netic ﬁeld in the mean time. On average, this takes 618ms/2 = 309ms. 4

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 fb fb fc fa fb Figure 2.2. Structure of the CRYPTO1 stream cipher 2.5. Authentication protocol and initialization Here the ai ∈ F2 are given by The authentication protocol was reverse engineered in [GKM+08]. During the anti-collision phase, the tag sends its uid u to the reader. The reader then asks to authenticate for a speciﬁc sector. The tag sends a challenge nT . From this point on, communication is encrypted, i.e., XOR-ed with the keystream. The reader responds with its own challenge nR and the answer aR := suc64(nT ) to the challenge of the tag; the tag ﬁnishes with its answer aT := suc96(nT ) to the challenge of the reader. See Figure 2.3. Note that later on we will send messages aR that deviate from this protocol; this will be explained in Section 4. −−−−−−−−−−−−−−−−−−−−−−−−→ −−−−−−−−−−−−−−−−−−−−−−−−→ u nT ←−−−−−−−−−−−−−−−−−−−−−−−− {nR}{aR} {aT } Tag Reader −−−−−−−−−−−−−−−−−−−−−−−−→ Figure 2.3. Authentication protocol During the authentication protocol, the internal state of the stream cipher is initialized. It starts out as the sector key k, then nT ⊕ u is shifted in, then nR is shifted in. Because communication is encrypted from nR onwards, the encryption of the later bits of nR is inﬂuenced by the earlier bits of nR. Authentication is achieved by reaching the same internal state of the cipher after shifting in nR. The following precisely deﬁnes the initialization of the cipher and the generation of the LFSR-stream a0a1 . . . and the keystream b0b1 . . . . Deﬁnition 2.6. Given a key k = k0k1 . . . k47 ∈ F48 2 , a tag nonce nT = nT,0nT,1 . . . nT,31 ∈ F32 2 , a uid u = u0u1 . . . u31 ∈ F32 2 , and a reader nonce 2 , the internal state of nR = nR,0nR,1 . . . nR,31 ∈ F32 the cipher at time i is αi := aiai+1 . . . ai+47 ∈ F48 2 . 5 ai := ki ∀i ∈ [0, 47] a48+i := L(ai, . . . , a47+i) ⊕ nT,i ⊕ ui ∀i ∈ [0, 31] ∀i ∈ [0, 31] a80+i := L(a32+i, . . . , a79+i) ⊕ nR,i a112+i := L(a64+i, . . . , a111+i) ∀i ∈ N. Furthermore, we deﬁne the keystream bit bi ∈ F2 at time i by bi := f (aia1+i . . . a47+i) ∀i ∈ N. denote We {nR,i}, {aR,i} ∈ F2 by encryptions by {−} and deﬁne {nR,i} := nR,i ⊕ b32+i {aR,i} := aR,i ⊕ b64+i ∀i ∈ [0, 31] ∀i ∈ [0, 31]. Note that the ai, αi, bi, {nR,i}, and {aR,i} are formally functions of k, nT , u, and nR. Instead of making this explicit by writing, e.g., ai(k, nT , u, nR), we just write ai where k, nT , u, and nR are clear from the context. 2.6. Rollback For our attacks it is important to realize that to recover the key, it is sufﬁcient to learn the internal state of the cipher αi at any point i in time. Since an attacker knows u, nT , and {nR}, the LFSR can then be rolled back to time zero. This is explained in Section 6.2 of [GKM+08]; below we show their method translated into our notation. Deﬁnition 2.7. The rollback function R : F48 2 → F2 is deﬁned by R(x1x2 . . . x48) := x5 ⊕ x9 ⊕ x10 ⊕ x12 ⊕ x14 ⊕ x15 ⊕ x17 ⊕ x19 ⊕ x24 ⊕ x25 ⊕ x27 ⊕ x29 ⊕ x35 ⊕ x39 ⊕ x41 ⊕ x42 ⊕ x43 ⊕ x48. If one ﬁrst shifts the LFSR left using L to generate a new bit on the right, then R recovers the bit that dropped out on the left, i.e., R(x1x2 . . . x47 L(x0x1 . . . x47)) = x0. (1) o o o o

Theorem 2.8. In the situation from Deﬁnition 2.6, we have a64+i = R(a65+i . . . a112+i) a32+i = R(a33+i . . . a80+i) ⊕ {nR,i} ⊕ f (0 a33+i . . . a79+i) ai = R(a1+i . . . a48+i) ⊕ nT,i ⊕ ui ∀i ∈ N ∀i ∈ [0, 31] ∀i ∈ [0, 31]. Proof. Straightforward, using Deﬁnition 2.6 and Equa- tion (1). For the second equation, note that f does not depend on its leftmost input. Therefore f (0 a33+i . . . a79+i) = f (a32+i . . . a79+i) = b32+i and hence {nR,i} ⊕ f (0 a33+i . . . a79+i) = nR,i. Consequently, if an attacker somehow recovers the internal state of the LFSR αi = aiai+1 . . . ai+47 at some time i, then she can repeatedly apply Theo- rem 2.8 to recover α0 = a0a1 . . . a47, which is the sector key. 3. Weaknesses This section describes weaknesses in the design of the Mifare Classic. We ﬁrst treat weaknesses in the way the Mifare Classic handles parity bits and then the ones concerning nested authentications. These weaknesses will be exploited in Section 4. 3.1. Parity weaknesses The ISO standard 14443-A [ISO01] speciﬁes that is followed by a parity bit. The every byte sent Mifare Classic computes parity bits over the plaintext instead of over the ciphertext. Additionally, the bit of keystream used to encrypt the parity bits is reused to encrypt the next bit of plaintext. This already breaks the conﬁdentiality of the encryp- tion scheme. In this paper we shall only be concerned with the four parity bits of nT , nR, and aR. The ISO standard speciﬁes odd parity, hence the “⊕1” in the deﬁnition below. Deﬁnition 3.1. In the situation from Deﬁnition 2.6, we deﬁne the parity bits pj ∈ F2 by pj := nT,8j ⊕ nT,8j+1 ⊕ · · · ⊕ nT,8j+7 ⊕ 1 pj+4 := nR,8j ⊕ nR,8j+1 ⊕ · · · ⊕ nR,8j+7 ⊕ 1 pj+8 := aR,8j ⊕ aR,8j+1 ⊕ · · · ⊕ aR,8j+7 ⊕ 1 reader sends {nR} and {aR}, the tag checks the parity bits before the answer of the reader. If at least one of the eight parity bits is wrong, the tag does not respond. 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 all eight parity bits are correct and the answer aR is also correct, the tag responds, of course, with its answer aT . Furthermore, in case the reader sends the correct parity, but the wrong answer, the 4-bit error code 0x5 is sent encrypted. This happens even though the reader has not authenticated itself and hence cannot be assumed to be able to decrypt. Figure 3.1 shows an authentication trace where the attacker sends incorrect authentication data but correct parity bits. The exclamation marks represent parity bits that deviate from what is speciﬁed in the standard. The ﬁnal message of this trace is the encrypted error message 0x5. 3.2. Nested authentications Once an attacker knows a single sector key of a Mifare Classic, there is a vulnerability that allows an adversary to recover more keys. When a reader is already communicating (encrypted) with a tag, a subsequent authentication command for a new sector also has to be sent encrypted. After this authentication command, the internal state of the cipher is set to the key for the new sector and the authentication protocol from Section 2.5 starts again. This time, however, the challenge of the tag is also sent encrypted. Because there are only 216 possible nonces, an attacker can simply try to guess a nonce to recover 32 bits of keystream. Also here, the information that leaks through the parity bits can be used to speed up the attack. Although there are 216 tag nonces, we show below that the parity bits sent with the encrypted tag nonce leak three bits of information, so that there are only 213 tag nonces possible. Deﬁnition 3.2. In the situation from Deﬁnition 2.6, we deﬁne {nT,i} ∈ F2 by ∀j ∈ [0, 3] {nT,i} := nT,i ⊕ bi ∀i ∈ [0, 31]. and the encryptions {pj} of these by {pj} := pj ⊕ b8+8j ∀j ∈ [0, 11]. There is a further weakness concerning the parity bits. During the authentication protocol, when the Theorem 3.3. For every j ∈ {0, 1, 2} we have nT,8j ⊕ nT,8j+1 ⊕ · · · ⊕ nT,8j+7 ⊕ nT,8j+8 = {pj} ⊕ {nT,8j+8} ⊕ 1 6

c1 08 41 6a e2 Reader 26 Tag 02 00 Reader 93 20 Tag Reader 93 70 c1 08 41 6a e2 e4 7c Tag Reader 60 00 f5 7b Tag ab cd 19 49 Reader 59! d5 92 0f! 15 b9 d5! 53! {nR}{aR} Tag req type A answer req select uid, bcc select(uid) Mifare Classic 4k auth(block 0) nT 18 37 cd a {5} Figure 3.1. Trace of a failed authentication attempt Proof. We compute as follows. nT,8j ⊕ nT,8j+1 ⊕ · · · ⊕ nT,8j+7 ⊕ nT,8j+8 (by Dfn. 3.1) = pj ⊕ 1 ⊕ nT,8j+8 = pj ⊕ b8+8j ⊕ nT,8j+8 ⊕ b8+8j ⊕ 1 = {pj} ⊕ {nT,8j+8} ⊕ 1 (by Dfns. 3.1 and 3.2) Since the attacker can observe {pj} and {nT,8j+8}, this theorem gives an attacker three bits of information about nT . In practice, timing information between the ﬁrst and second authentication attempt leaks so much additional information that the attacker can accurately predict what the challenge nonce will be. It turns out that the distance between the tag nonces used in consecutive authentication attempts strongly depends on the time between those attempts. Here distance is deﬁned as follows. Deﬁnition 3.4. Let nT and n′ deﬁne the distance between nT and n′ T be two tag nonces. We T as suci(nT ) = n′ T . d(nT , n′ T ) := min i∈N 4. Attacks This section shows how the weaknesses described in the previous section can be exploited. 4.1. Brute-force attack The attacker plays the role of a reader and tries to authenticate for a sector of her choice. She answers the challenge of the tag with eight random bytes (and eight random parity bits) for {nR} and {aR}. With probability 1/256, the parity bits are correct and the tag responds with the encrypted 4-bit error code. A success leaks 12 bits of entropy (out of 48). 7 Repeating the above procedure sufﬁciently many times (in practice six is enough) uniquely determines the key. Since the key length is only 48 bits, the attacker can now brute force the key: she can just check which of the 248 keys produces all six times the correct parity bits and received response. In practice, gathering those six authentication sessions with correct parity bits only takes on average 6 · 256 = 1536 authentication attempts which can be done in less than one second. The time it takes to perform the ofﬂine brute-force attack of course is strongly dependent on the resources the attacker has at her disposal. We give an estimate based on the performance of COPA- COBANA [KPP+06]; this is a code-cracker built from off-the-shelf hardware costing approximately 10000 USD. Based on the fact that COPACOBANA ﬁnds a 56-bit DES key in on average 6.4 days, pessimisti- cally assuming that one can ﬁt the same number of CRYPTO1 checks on an FPGA as DES-decryptions, and realizing that the search space is a factor of 256 smaller, we estimate that this takes on average 6.4 days/256 = 36 min. In Sections 4.2 and 4.3 the same idea is exploited in a different way, trading online communication for computation time. 4.2. Varying the reader nonce This section shows how an attacker can mount a chosen ciphertext attack by adaptively varying the encryption of nR. We assume that the attacker can control the power up timing of the tag, thereby causing the tag to produce the same nT every time. We ﬁrst give the idea of the attack. The attacker runs authentication sessions until she guesses the correct parity bits. The internal state of the stream cipher just after feeding in nR is α64. She then runs another authentication session, keeping the ﬁrst 31 bits of {nR} (and the three parity bits) the same, ﬂipping the last

bit of {nR} (and randomly picking the rest until the parity is ok). Now the state of the stream cipher just after feeding in the reader nonce is α64 ⊕ 1, i.e., α64 with the last bit ﬂipped. Since the parity of the last byte of nR changed (since the attacker ﬂipped just the last bit), and since its parity in the ﬁrst run is encrypted with f (α64) and in the second run with f (α64⊕1), she can deduce whether or not the last bit of nR inﬂuences the encryption of the next bit, i.e., whether or not f (α64) = f (α64 ⊕ 1). Approx. 9.4% of the possible α64’s has f (α64) 6= f (α64) ⊕ 1 and they can easily be generated since only the twenty bits that are input to f are relevant. By repeating this, the attacker eventually (on average after 10.6 tries) ﬁnds an instance in which α64 is in those 9.4% and then she only has to search, ofﬂine, 9.4% of all possible states. We now make this idea precise and at the same time generalize it to the last bit of each of the four bytes in the reader nonce. The following deﬁnition says that a reader nonce has property Fj (for j ∈ {0, 1, 2, 3}) if ﬂipping the last bit of the (j + 1)th byte of the reader nonce changes the encryption of the next bit. Deﬁnition 4.1. Let j ∈ {0, 1, 2, 3} and let nR and R be reader nonces with the property that n′ n′ R,8j+7 = R,i = nR,i for all i < 8j + 7 (and no nR,8j+7 and n′ restrictions on nR,i and n′ R,i for i > 8j + 7). We say that nR has property Fj if b8j+40 6= b′ 8j+40. After the tags sends its challenge nT , the attacker answers {nR}, {aR}. Inside this answer, the attacker also has to send the (encryptions of) the parity bits: {p4}, . . . , {p11}. For these, she tries all 256 possibili- ties. After on average 128 authentication sessions, and after at most 256, with different choices for the {pi}, the parity bits are correct and the attacker recognizes this because the tag responds with an error code. Now the attacker deﬁnes {n′ R,8j+7} := {nR,8j+7}, i.e., she changes the last bit of the jth byte of {nR}. R} she chooses the same as The earlier bits of {n′ those of {nR}; R} the attacker chooses arbitrarily. Again, the attacker repeatedly tries to authenticate to ﬁnd the correct parity bits {p′ i} = {pi} for i ∈ {4, . . . , j + 3}, so this takes on average 27−j authentication attempts and at most 28−j. i} to send. Note that necessarily {p′ the later bits of {n′ R} and {a′ Now nR has property Fj if and only if {pj+4} 6= j+4}. {p′ the last bit of the jth byte of nR, Proof. Because the attacker modiﬁed the cipher- text of the last bit of the plaintext of this byte also changes: n′ R,8j+7 = {n′ R,8j+7} ⊕ b′ 8j+39 = {nR,8j+7} ⊕ b8j+39 = nR,8j+7 ⊕ b8j+39 ⊕ the parity of this byte b8j+39 = nR,8j+7. Hence, changes: p′ R,8j+7⊕1 = R,8j+6⊕n′ nR,8j ⊕ . . . nR,8j+6 ⊕ nR,8j+7 ⊕ 1 = pj+4. 8j+39 = {n′ R,8j+7} ⊕ b′ R,8j ⊕· · ·⊕n′ j+4 = n′ Formally this is not just a property of nR, but also of k, nT , and u. Now k and u of course do not vary, so we ignore that here. Furthermore, when deciding whether or not nR has property Fj in Protocol 4.2 below, the attacker also keeps nT constant. i, b′ The attacker does change the reader nonce. We use i to refer to the bits of the LFSR-stream where the a′ reader nonce n′ i, etc. I.e., a′ R is used and similarly for α′ i denotes ai(k, nT , n′ R). Note that α8j+40 (resp. α′ 8j+40 = f (α′ 8j+40) is the internal state of the cipher just after feeding in (j + 1)th byte of nR (resp. n′ R) and b8j+40 = f (α8j+40) (resp. b′ 8j+40), so that Fj does not depend on nR,i and n′ R,i for i > 8j + 7. Also observe that 8j+87, i.e., α8j+40 and α′ 8j+40 = a8j+40 . . . a8j+86a′ 8j+40 only differ in the last position. α′ The crucial idea is that an attacker can decide whether or not nR has property Fj, only knowing {nR}. (In practice, the attacker of course chooses {nR}.) Protocol 4.2. Given {nR}, an attacker can decide as follows whether or not nR has property Fj. She ﬁrst chooses {aR} arbitrary. She then starts, consec- utively, several authentication sessions with the tag. j+4} = pj+4 ⊕ b8j+40 ⊕ p′ Now {pj+4} ⊕ {p′ 8j+40 = pj+4 ⊕ b8j+40 ⊕ pj+4 ⊕ b′ b′ 8j+40. Hence {pj+4} = {p′ b′ b8j+40 = b′ if nR has property Fj. 8j+40, i.e., {pj+4} 6= {p′ j+4 ⊕ 8j+40 = b8j+40 ⊕ j+4} if and only if j+4} if and only The theorem below shows that the probability that nR has the property Fj is approximately 9.4%. Lemma 4.3. Let Y0, . . . , Y4 be independent uniformly distributed random variables over F2. Then P [fb(Y0, Y1, Y2, Y3) 6= fb(Y0, Y1, Y2, Y3)] = 1 4 P [fc(Y0, Y1, Y2, Y3, Y4) 6= fc(Y0, Y1, Y2, Y3, Y4)] = 3 8 . Proof. By inspection. Theorem 4.4. Let Y0, Y1, . . . , Y18, Y19 be independent uniformly distributed random variables over F2. Then P [f (Y0, . . . , Y18, Y19) 6= f (Y0, . . . , Y18, Y19)] = 3 32 . := fa(Y0, . . . , Y3), Z1 := fb(Y8, . . . , Y11), Z3 Proof. Write Z0 := fb(Y4, . . . , Y7), Z2 := fa(Y12, . . . , Y15), and Z4 := fb(Y16, . . . , Y19). Fur- thermore, write Z ′ 4 := fb(Y16, . . . , Y18, Y19). Note that Z0, . . . , Z4 are independent and, by Theorem 2.3, 8

分享到：

赞收藏

资料库

Pickpocketing.Mifare(M1卡破解).pdf

相关推荐

最新资料