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 office 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 office 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 differ in size, casing, mem-
ory, and computing power. They also differ 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 different 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 first 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 offline 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 efficient as a lookup operation on a table. Therefore, it is much
more efficient than an exhaustive search over the whole 48 bit key space.
The second and more efficient 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 sufficient 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 differs 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 findings have been made public. Their
research takes a very different, 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 specific gates and connections.
Their presentation has been of great stimulus in our discovery process. Our
approach, however, is radically different 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 briefly 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 difference 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 significant bit of the
byte on the left, while the latter writes the least significant 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 significant 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 specific
block, the reader must first 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 field of the reader and powers up, it
immediately starts the anti-collision protocol by sending its uid. The reader then
selects this tag as specified in ISO14443-A [ISO01].
According to the manufacturer’s documentation, the reader then sends an
authentication request for a specific 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 finishes
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 fixing 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 first 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 different 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 modified 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 field 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 first 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 finishes 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 filter 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 filter 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 first
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
verified 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 simplified 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 affect 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 difference 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 filter function f.
5.2 Filter function
The first time the filter function f is used, is when the first 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 first task is now to determine which bits of the LFSR are inputs to the
filter 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