\documentclass[a4paper]{article}
\usepackage[english]{babel}
\usepackage{graphicx}
\usepackage{subfigure}
\pagestyle{plain}

\usepackage{url}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.5in}
%\setlength{\parindent}{0in}
\setlength{\parskip}{0.05in}

\begin{document}

\title{Security analysis of the EasyCard payment card in Taiwan}
\author{Harald Welte $<$laforge@gnumonks.org$>$}
\date{UNRELEASED (September XX, 2010}
\maketitle

\begin{abstract}
The EasyCard system, established in 2001, is the most popular store-valued card % FIXME: "store-valued"? Meinten Sie: "stored-value"?
in Taiwan.  With more than 18 million issued cards, it is the predominant means
of paying for public transportation services in the capital Taipei.

In 2010, use of the EasyCard was extended beyond transportation.  Card holders
can now pay in all major convenience stores and major retail companies like
Starbucks or even SOGO.

However, the system is still using the MIFARE Classic RFID transponder
technology, whose very limited security-by-obscurity proprietary encryption
system (CRYPTO1) has been broken years ago.

This document analyzes the results of combining the practical attacks
on the MIFARE Classic CRYPTO1 system in the context of the EasyCard payment
system.
\end{abstract}

\tableofcontents

\section{Foreword}

This document is the result of my personal research on the EasyCard
system.  It was done out of my personal interest in security research
on information technology.  No competitor of the EasyCard corporation,
or other business or political  stakeholder ever encouraged, supported or
funded this work in any way.

The result of this research is presented to the general public in the
hope it will make people re-consider the amount of trust they place
in proprietary systems that provide no evidence of their security,
and no option for the general public or the scientific community to
validate it.

This paper is also directed at the legislator and the regulatory authorities,
in the hope that it will help them to produce better rules and requirements on
the technology designed for and used by operators of security relevant systems
such as banking.

\section{Introducing the EasyCard}

FIXME

\section{Published security research on MIFARE Classic}

FIXME: Summarize the existing research on mifare classic systems

\section{Published tools for MIFARE Classic attacks}

\subsection{Crapto1}
\subsection{libnfc}
\subsection{MFOC}
\subsection{MFCUK}

\section{Analyzing the EasyCard}

A new, genuine EasyCard was obtained from one of the EasyCard vending machines
in a Taipei MRT station.

As it is public knowledge that the EasyCard system is based on MIFARE
technology, any MIFARE-compatible RFID reader (PCD, Proximity Coupling Device)
can be used to establish a physical communications link according to ISO
14443-1 and -2, as well as performing the anti-collision procedure according
to ISO 14443-3.

The author has used the OpenPCD RFID reader to do this, and has confirmed that
the EasyCard in fact is a card with ISO 14443-3 compatible anti-collision
procedure.  The ATQA response also looks like that of a standard MIFARE Classic
transponder.

\subsection{Attempting to use standard keys}

As some users of MIFARE Classic systems only use some sectors of a card, but
not all, an attempt was made to authenticate to any of the sectors using the
manufacturer-programmed standard keys.  However, none of the card sectors were
using those standard keys.

This also means that we could not use the key recovery method described in
FIXME, where keys of all other sectors are recovered based on the knowledge of
they key of at least one different sectors.

\subsection{Recovering the MIFARE CRYPTO1 keys}

Since none of the sector keys was known, the publicly available MFCUK (MiFare
Classic Universal toolKit) implementation of the ``Dark Side'' attack (Nicolas T.
Courtois) was used as a card-only attack.

All that was required was the MFCUK Free Software, as well as a RFID
reader as supported by libnfc.  Compatible readers are widely available,
among them one for EUR 30 from \url{http://www.touchatag.com/e-store}.

Using the MFCUK key recovery tool, the A and B keys for all sectors have
been recovered within FIXME.  This attack can definitely be optimized
by using special-purpose hardware such as the Proxmark, which gives
hard-realtime control over the communication with the EasyCard.

Furthermore, the key recovery can be optimized based on known-plaintext that is
common to all cards.

\subsection{Dumping the content of the EasyCard}

Once the sector keys have all been recovered, the full content of the EasyCard
can be dumped using any RFID reader supporting MIFARE Classic.  The author
chose to use the same reader that was used for the MFCUK key recovery combined
with the nfc-mfclassic program (part of libnfc).

A full dump of the newly-purchased, unused EasyCard revealed the following
content:

\begin{verbatim}
0000000 a193 c031 88c3 0004 ba46 1214 1051 1004
0000010 140e 0100 0207 0308 0409 1008 0000 0000
0000020 0000 0000 0000 0000 0000 0000 0000 0000
0000030 211a ccd0 f399 7708 008f 6ac6 53bf cf08
0000040 ff02 0300 0000 059f 804c c926 0171 3601
0000050 0000 1000 1027 0027 64de 0001 0000 bb00
0000060 f1d6 b4e8 0012 0000 0000 6400 0064 6900
0000070 2e64 f724 bd57 7708 008f 8917 3d48 5dcd
0000080 0190 0000 fe6f ffff 0190 0000 ff00 ff00
0000090 0190 0000 fe6f ffff 0190 0000 ff00 ff00
00000a0 0000 0000 0000 0000 0000 0000 0000 0000
00000b0 0d3d 782b 33cd 7708 008f 2411 4ce7 ea3f
00000c0 0001 0005 0000 0000 0000 0000 0000 0000
00000d0 0000 0000 0000 0000 0000 0000 0000 0000
00000e0 0000 0000 0000 0000 0000 0000 0000 0000
00000f0 2fb1 511f 85b4 7708 008f 8dc8 eef5 2850
0000100 0000 0000 0000 0000 0000 0000 0000 0000
0000110 0000 0000 0000 0000 0000 0000 0000 0000
0000120 0000 0000 0000 0000 0000 0000 0000 0000
0000130 4587 96bd 1f22 7708 008f 47ce 7619 1558
0000140 0000 0000 0000 0000 0000 0000 0000 0000
0000150 0000 0000 0000 0000 0000 0000 0000 0000
0000160 0000 0000 0000 0000 0000 0000 0000 0000
0000170 5583 7616 749e 7708 008f 9bf3 c129 8eb6
0000180 0c00 0400 0044 0000 0000 0000 0000 4c00
0000190 0200 2200 0022 0000 0000 0000 0200 0000
00001a0 0000 0005 0000 0000 0000 0000 0000 0000
00001b0 af5f 6aeb 3a2c 7708 008f c039 7a1d d248
00001c0 0000 0000 0000 0000 0000 0000 0000 0000
00001d0 0000 0000 0000 0000 0000 0000 0000 0000
00001e0 0000 0000 0000 0000 0000 0000 0000 0000
00001f0 aebf 906e f2bd 7708 008f e3e7 988f aaaa
0000200 0000 0000 0000 0000 0000 0000 0000 0000
0000210 0000 0000 0000 0000 0000 0000 0000 0000
0000220 0000 0000 0000 0000 0000 0000 0000 0000
0000230 ec9f 8bc6 4b89 7708 008f 53b0 2571 9e66
0000240 0000 0000 0000 0000 0000 0000 0000 0000
0000250 0000 0000 0000 0000 0000 0000 0000 0000
0000260 0000 0000 0000 0000 0000 0000 0000 0000
0000270 edc5 c17c 8a36 7708 008f 9a58 b6d9 5a8b
0000280 0000 0000 0000 0000 0000 0000 0000 0000
0000290 0000 0000 0000 0000 0000 0000 0000 0000
00002a0 0000 0000 0000 0000 0000 0000 0000 0000
00002b0 40f7 60bf 4b8a 7708 008f 3a00 c93a 63e8
00002c0 0000 0000 0000 0000 0000 0000 0000 0000
00002d0 0000 0000 0000 0000 0000 0000 0000 0000
00002e0 0000 0000 0000 0000 0000 0000 0000 0000
00002f0 b50a 9f96 d2e3 7708 008f 4855 7cdb 7dff
0000300 0000 0000 0000 0000 0000 0000 0000 0000
0000310 0000 0000 0000 0000 0000 0000 0000 0000
0000320 0000 0000 0000 0000 0000 0000 0000 0000
0000330 4c06 3ebc e595 7708 008f 9a5b 001b d14a
0000340 0000 0000 0000 0000 0000 0000 0000 0000
0000350 0000 0000 0000 0000 0000 0000 0000 0000
0000360 0000 0000 0000 0000 0000 0000 0000 0000
0000370 3fb0 45ce 6f6b 7708 008f c0bf adb0 d662
0000380 0000 0000 0000 0000 0000 0000 0000 0000
0000390 0000 0000 0000 0000 0000 0000 0000 0000
00003a0 0000 0000 0000 0000 0000 0000 0000 0000
00003b0 3320 9074 e84c 7708 008f 0094 85d5 7aaa
00003c0 8000 c926 0071 0000 0000 0000 0064 0064
00003d0 0000 0000 0000 0000 0000 0000 0000 0000
00003e0 0000 0000 0000 0000 0000 0000 0000 0000
00003f0 ea02 0bda b62a 7708 008f 0000 0000 0000
\end{verbatim}

\subsection{Re-engineering the on-card data format}

When the author started his research, there was no pre-existing public
knowledge on the data format used by the EasyCard system.  As such,
significant time was spent analyzing it.

The card was subsequently used to perform a number of transactions such as
use of public transportation and purchase of goods in stores.

After each transaction, again a full dump of the card contents was made,
and the difference to the previous dump analyzed carefully.  No particular
tools have been used for analysis.  Most of the work relied on hex-dumps
of the card content and using the {\tt diff} utility to visualize differences
between two consecutive versions.

During the analysis, it was quickly revealed that there are four
distinctive sets of changes that can be associated with a transaction:
\begin{itemize}
\item The card balance, stored as MIFARE value block
\item The transaction log
\item The transaction log index
\item The last MRT entry/exit record
\end{itemize}

Furthermore, a constant header has been identified. It was never changed during
any of the tested transactions.

The result of this analysis can be found in the next section:

\section{Re-engineered EasyCard Data Format}

\subsubsection{Sector 0 and 1: The header}
FIXME

\subsubsection{Sector 2: The card balance as value block}

The first two blocks of sector 2 store the current remaining debit account
balance as a MIFARE Classic VALUE BLOCK.  The format of this block is
documented in the official NXP vendor documentation on the MIFARE chip
used inside the card.

The value block is decremented every time payment is made with the card.

Given the MIFARE access bits, it is assumed that the RFID readers in public
transportation as well as stores use key A for this sector, as key A is
sufficient to read and decrement the VALUE block.

Re-charging the card must happen using authentication with key B, as only
key B has permissions to increment and/or write to this sector.

\subsubsection{Sector 3 through 5: The transaction log}

Every time a transaction is made with the card, an entry in the transaction log 
on the card itself is generated.  Every entry occupies one full 16-byte block.

The structure of a transaction log entry is as follows:
\begin{itemize}
\item 1 byte Transaction ID
\item 4 bytes Timestamp
\item 1 byte Transaction type
\item 2 bytes Cost charged for transaction
\item 2 bytes Remaining balance after transaction
\item 1 byte MRT Station ID
\item 1 byte Unknown
\item 2 bytes RFID Reader ID
\item 2 bytes Unknown
\end{itemize}

The {\em Transaction ID} is a monotonically increasing value, incrementing with
each transaction.

The {\em Timestamp} is a 32bit value in the standard UNIX time() format (Seconds
since January 1st 1970 00:00:00).  However, it does not reference UTC but CST.

The {\em Transaction type} indicates the type of transaction.  Following codes
are known:
\begin{itemize}
\item {\tt 0x00} Entering MRT station
\item {\tt 0x11} Leaving MRT station
\item {\tt 0x80} Re-entering (connecting) MRT station
\item {\tt 0x20} Purchase of goods in shop
\item {\tt 0x30} Re-charging the card using an {\em Add value machine}
\end{itemize}

The {\em Cost} and {\em Remaining balance} fields are unsigned 16bit integer
values representing the price in NTD (New Taiwan Dollars).

In case of a MRT related transaction, the {\em MRT Station ID} encodes the MRT
station at which the transaction was performed.  By visiting the TRTC (Taiwan
Rapid Transport Corporation) website, one can see the same numeric identifiers
being used within the URLs that link from the MRT map to the per-station web
pages.  As such, a full table of MRT station names and corresponding
identifiers has been compiled and implemented as part of {\tt easytool}.

The {\em RFID Reader ID} is presumed to be a unique identifer for the specific
RFID Terminal.  Subsequent transactions at the same terminal will render
the same number in this field.

FIXME: Transaction log pointer

\subsubsection{Sector 7: The last MRT entry/exit record}

Block 2 (Offset 0x1e0) contains a record describing the last MRT station
that was entered using this EasyCard.
\begin{itemize}
\item Bytes 0...3 are unknown
\item Byte 4 contains the MRT station code
\item Bytes 6...8 are unknown
\item Bytes 9...12 contain the Timestamp
\item Bytes 13..15 are unknown
\end{itemize}

Block 1 (Offset 0xd0) of the same sector contains a record using the same
structure.  However, this record describes the last MRT station that was
left using this EasyCard.

It is assumed that this information is used by the system to compute both the
distance (and thus fee) to be paid by the current ride, as well as any
applicable discount in case a connection is made from MRT into a bus.

\subsubsection{Sector 15: Maximum daily spending}

Block 2 (Offset 0x3e0) contains a record used for keeping track of
the amount of money spent on a single day.  This is needed in order
to impose a daily spending limit of (currently) NTD 3,000.

The record is structured as follows:
\begin{itemize}
\item Bytes 0...10 are unknown (all zero in tested cards)
\item Byte 11 contains the day of the month
\item Byte 12 contains an unknown value (0x3d in tested cards)
\item Byte 13...14 contain the sum of all purchases on the indicated day
\end{itemize}

If multiple retail store purchases are made on the same day of the month, the
sum is incremented with every purchase.  If an EasyCard terminal in the store
detects that the current day-of-the-month is different from that stored on the
card, the sum is re-set and starts new for that day.

\section{Manipulating the EasyCard}

\subsection{Decreasing the Value of the card}

In order to decrease the account balance on the card, the following method
was tested:

\begin{itemize}
\item Make a purchase in a retail store that accepts the EasyCard
\item Find the transaction log entry regarding this purchase and increase the transaction cost by some value.  NTD 200 was chosen in this example.  Decrease the {\em amount remaining after transaction} field accordingly by the same amount.
\item Alter the two VALUE blocks in Sector 2 to reflect the subtracted amount. Make sure the backup copies (inverted and non-inverted) are updated, too.
\item Alter the {\em amount spent per day} in Sector 15 to reflect the increased amount spent.
\end{itemize}

Payment using the manipulated card was possible without any problem, provided
that the to-be-paid amount is less than what the card considers the remaining
balance.

Re-reading the card after the purchase indicates the full success of the
operation.  The purchase has left exactly the same changes in the card like
it would have with a card that has a genuine lower value.  None of the
erroneously increased (or decreased) numbers had been updated.

This specifically confirms that the vending terminal did not have an online
connection to a centralized database.  In that case, the erroneous values
on the card would have been corrected and the original value restored.

\subsection{Increasing the value of the card}

The approach works similar to the previous one.  First, a purchase in a store
is being made, preferrably with relatively high value.  Later, the transaction
log record, card balance and amount spent per day fields are modified to make
this purchase appear cheaper than it actually was.  So after purchasing an item
with 1000 NTD, the card will look like only 100 NTD were spent for the purchase,
giving an extra balance of 900 NTD to the attacker.

\subsection{Bypassing the maximum daily spending of NTD 3000}

As the sum of all purchases on a given day-of-the-month is stored in Sector 15,
there are two methods of evading the per-day payment limit:
\begin{itemize}
\item Simply zero-out the amount of money spent today, or
\item simply alter the day-of-the-month field to a different day.
\end{itemize}
Both options might cause problems in case the terminal does consistency checks
with the transaction log.  So it would be wise for an attacker to also modify
all purchases in the transaction log to appear as if they were made on a
previous day.

\section{Mistakes of the EasyCard Corporation}

Based on this research as well as publicly known information on the
EasyCard Corporation, we can identify a series of mistakes with cumulative
effect.

\subsection{Deploying old technology}

The Taipei Smart Card corporation (predecessor to the EasyCard Company) was
established in 2000, and it took until June 2002 to deploy the first EasyCard
system.

The underlying Mifare Classic product was launched in 1994, and thus already
relatively old and outdated technology at that time.

It was publicly documented by NXP that the security of the system is based on a
{\em proprietary, symmetric, 48bit cipher}.  Symmetric 48-bit encryption
was definitely no longer state-of-the-art in the year 2000.  At that time,
the popular web-browser Netscape Navigator (used e.g. for web-based online
banking) had already introduced support for symmetric 128bit ciphers.

\subsection{Deploying proprietary security technology}

There are two concepts of achieving security in any system: {\em Security by
design} and {\em Security by obscurity}.

In the former systems, security is achieved by using well-designed systems
that have undergone public peer review and have been subject to cryptanalysis.
As a result, the system is secure because it has undergone the review and
scrutiny of the international community of cryptographers and security experts.

So, despite making all details of the system, particularly the cryptographic
algorithms open, an attacker is not able to circumvent the system's security.

A system relying on {\em Security by obscurity} is only secure because
nobody knows the details of how it works.  As soon as this information
has either leaked or recovered e.g. using reverse engineering techniques,
the system is broken.

FIXME: Link to Bruce Schneier

\subsection{Not reacting to academic research in the field}

Starting in 2007, researchers have published a variety of attacks on
the CRYPTO-1 cipher and MIFARE Classic system.  For a list of related
publications, see the bibliography of this paper.

\subsection{Not reacting to public availability of MIFARE attack tools}

Following-up the scientific publications, tools implementing practical
attacks on MIFARE Classic have been developed and published.  Such
tools implement a variety of attacks, including card-only key-recovery
attacks.

\subsection{No upgrade to more secure cards as they become available}

In the same year the EasyCard was first deployed (2002), the supplier of the
MIFARE Classic system has already been shipping a much more secure system
called DESfire.  The improvements include: 112-bit key length, and the use
of the internationally verified and audited DES algorithm in its 3DES variant.

Despite its availability for 8 years since 2002, the EasyCard corporation has
apparently never updated their system to a more secure card like the DESfire
card.

Based on the authors experience with the RFID card market, the price difference
of DESfire compared to MIFARE Classic has been on the order of USD 1 per card
from 2006 on.

So, in order to save USD 1 per each issued card, the EasyCard corporation has
artificially kept down the security level of their system,  not catching
up with state-of-the-art commercially available technology.

\subsection{Extending EasyCard to generic payment outside public transport}

The security of any system always has to be analyzed in the context of the
threat model, i.e. what can an attacker gain from compromising the system.

As the key derivation of the EasyCard is not (yet?) broken, it is thus
currently not possible to completely manufacture forged cards.  However,
technically, cards can be re-charged without making actual payment for it.

As far as cards are only used for public transportation, the incentive
for fraudulent use is relatively small and contained.  Also, the amount
of money for each transaction is relatively small.

Thus, while the author would still disagree, it might be the case that
the business risk analysis inside EasyCard Corporation would have deemed the
risk of fraud in the public transport sector as acceptable.

When such a card is used as an electronic payment system in stores where
goods of much higher value can be purchased, the threat model is quite
different, though.

The 2010 introduction of the EasyCard as means of payment in retail
stores -- while still relying on known-broken, 16 year old technology --
can thus only be seen as ignorant and incompetent.

It does not help that EasyCard corporation has to provide a full refund
and keep all deposits in a bank trust.  It also doesn't help that fraudulent
use is detected using analysis of the transaction data long after it happened.

EasyCard fraud is simple to perform and will inevitably happen.  Somebody
has to pay for the losses incurred due to fraud.  Even if such losses
only reflect themselves in increased transaction fees for retail stores, in the
end it will be the consumer who pays them indirectly due to higher prices
including such fees.

\section{Proposed Changes / Improvements}

The author of this paper argues that use of the current EasyCard system
should immediately be restricted to payment for public transportation,
and the decision to authorize it as form of payment in retail stores
as of April 1st, 2010 reverted.

A new system, based on state-of-the-art technology and algorithms
and the {\em Security by Design} principle should be developed.  Such
a system should go through independent, open academic review.

The approval of such a system, or technical security requirements for
such a system should not be within EasyCard itself, but should be
made by a regulatory authority, consulted by independent technical experts
in the field.

A changing roll-over to the new system can be made by starting to issue
the new cards using a more secure RFID system whenever new EasyCards are
bought.  Whenever a consumer wants to re-charge their card, the old MIFARE
Classic based card should be retracted and a new, more secure card be issued.
Existing EasyCards can be circulated in the system for a grace period.

Depending on the technical details of the existing deployed RFID
reader/terminal base in public transportation and retail stores, either
a software-only update is sufficient or replacement hardware has to be
introduced.

EasyCard corporation should be liable for the complete system
upgrade/transition cost, as the fault of the system can only be blamed
on them.

\section{Credits}

The author of this paper expresses his gratitude to the many people
involved in trying to uncover the weaknesses of proprietary and ultimately
insecure RFID systems worldwide.

\begin{description}
\item[Milosch and Brita Meriac]
	for their great work on OpenPCD and OpenPICC
\item[Henryk Ploetz, Karsten Nohl, starbug]
	for their work on MIFARE, Crypto1 and tiresome research into all kinds of proprietary snake-oil
\item[Jonathan Westhues]
	for designing and openly publishing the Proxmark
\item[Nethemba]
	for the Open Source implementation of the nested key attack in MFOC
\item[Roel Verdult]
	for his research on RFID security at Radboud University and libnfc
\item[Nicolas T. Courtois]
	for his {\em darkside} paper
\item[Andrei Costin ]
	for his Open Source implementation of the darkside paper (MFCUK)
	\url{http://andreicostin.com/}
\end{description}


\section{Bibliography}
%1. [WPMCC09] - "Wirelessly Pickpocketing a Mifare Classic Card"
%2. [ESO08] - "2008-esorics.pdf"
%3. [ESOSL08] - "2008-esorics-slides-updated.pdf"
%4. [KON08] - "2008-koning-thesis.pdf"
%5. [VER08] - "2008-verdult-thesis.pdf"
%6. [PATMC] - "A Practical Attack on the MIFARE Classic.pdf"
%7. [NCOURFIDSEC09] - "mifare_courtois_rfidsec09.pdf"
%8. [MFCLTRB09] - "MifareClassicTroubles.ppt"
%9. [TEEP08] - "p2008-teepe-classic_mistakes.pdf"
%10. [RFIDSANJ] - "RFID Attacks_WCA_San_Jose.pdf"
%11. [ROSS] - "rossum-mifare.pdf"
%12. [PLOTZ08] - "SAR-PR-2008-21_.pdf"
%13. [ROSSSASG] - "SASG35_Peter_v_Rossum_Mifare.pdf"
%14. [DARK2009] - "THE DARK SIDE OF SECURITY BY OBSCURITY and Cloning MiFare Classic Rail and Building Passes, Anywhere, Anytime"

\end{document}
