“Calhoun

Institutional Archive of the Naval Postgraduate School

Calhoun: The NPS Institutional Archive DSpace Repository

Theses and Dissertations 1. Thesis and Dissertation Collection, all items

2009-09

Design considerations for a computationally-lightweight authentication mechanism for passive RFID tags

Frushour, John H.

Monterey, California. Naval Postgraduate School

http://hdl.handle.net/10945/4511

Downloaded from NPS Archive: Calhoun

Calhoun is the Naval Postgraduate School's public access digital repository for

D U DL EY research materials and institutional publications created by the NPS community. «iis Calhoun is named for Professor of Mathematics Guy K. Calhoun, NPS's first

KNOX appointed and published -- scholarly author.

hl LIBRARY Dudley Knox Library / Naval Postgraduate School

411 Dyer Road / 1 University Circle

http://www.nps.edu/library Monterey, California USA 93943

NAVAL POSTGRADUATE SCHOOL

MONTEREY, CALIFORNIA

THESIS

DESIGN CONSIDERATIONS FOR A COMPUTATIONALLY-LIGHTWEIGHT AUTHENTICATION MECHANISM FOR PASSIVE RFID TAGS

by John H. Frushour

September 2009

Thesis Co-Advisors: J.D. Fulp Ted Huffmire

Approved for public release; distribution is unlimited

THIS PAGE INTENTIONALLY LEFT BLANK

Public reporting burden for this collection of information is estimated to average | hour per response, including the time for reviewing instruction, searching existing data sources, gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden, to Washington headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington, VA 22202-4302, and to the Office of Management and Budget, Paperwork Reduction Project (0704-0188) Washington DC 20503.

1. AGENCY USE ONLY (Leave blank) 2. REPORT DATE 3. REPORT TYPE AND DATES COVERED September 2009 Master’s Thesis

4. TITLE AND SUBTITLE Design Considerations for a Computationally- 5. FUNDING NUMBERS Lightweight Authentication Mechanism for Passive RFID Tags

6. AUTHOR(S) John H. Frushour

|6. AUTHOR(S) John H.Frushour

7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 8. PERFORMING ORGANIZATION Naval Postgraduate School REPORT NUMBER Monterey, CA 93943-5000

9. SPONSORING /MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSORING/MONITORING N/A AGENCY REPORT NUMBER

11. SUPPLEMENTARY NOTES The views expressed in this thesis are those of the author and do not reflect the official policy or position of the Department of Defense or the U.S. Government.

12a. DISTRIBUTION / AVAILABILITY STATEMENT 12b. DISTRIBUTION CODE Approved for public release, distribution is unlimited

13. ABSTRACT (maximum 200 words)

Passive RFID tags are attractive for their low cost, small footprint, and ability to function without batteries. The lack of onboard power, however, limits the complexity of operations that can be performed by the tags’ integrated circuits, and this limitation prevents the tags from being able to perform typical functions required to support e-authentication. This thesis quantifies the delta between the power that would be required to perform MAC-based authentication, and the power made available to a tag via the reader. A modified MAC protocol is then proposed that would theoretically close this delta while still providing sufficient authentication assurance.

14. SUBJECT TERMS Passive RFID Systems, Tags, Clock, Electro-magnetic induction, 15. NUMBER OF authentication, hash, SHA—1 PAGES 81

16. PRICE CODE

17. SECURITY 18. SECURITY 19. SECURITY 20. LIMITATION OF CLASSIFICATION OF CLASSIFICATION OF THIS CLASSIFICATION OF ABSTRACT REPORT PAGE ABSTRACT

Unclassified Unclassified Unclassified UU

NSN 7540-01-280-5500 Standard Form 298 (Rev. 2-89) Prescribed by ANSI Std. 239-18

THIS PAGE INTENTIONALLY LEFT BLANK

il

Approved for public release, distribution is unlimited

DESIGN CONSIDERATIONS FOR A COMPUTATIONALLY-LIGHTWEIGHT AUTHENTICATION MECHANISM FOR PASSIVE RFID TAGS

John H. Frushour Captain, United States Marine Corps B.S., University of Kentucky, 1998

Submitted in partial fulfillment of the requirements for the degree of

MASTER OF SCIENCE IN COMPUTER SCIENCE

from the

NAVAL POSTGRADUATE SCHOOL

September 2009 Author: John H. Frushour Approved by: J.D. Fulp Co-Advisor Ted Huffmire Co-Advisor

Peter Denning Chairman, Department of Computer Science

ill

THIS PAGE INTENTIONALLY LEFT BLANK

iv

ABSTRACT

Passive RFID tags are attractive for their low cost, small footprint, and ability to function without batteries. The lack of onboard power, however, limits the complexity of operations that can be performed by the tags’ integrated circuits, and this limitation prevents the tags from being able to perform typical functions required to support e- authentication. This thesis quantifies the delta between the power that would be required to perform MAC-based authentication, and the power made available to a tag via the interrogator. A modified MAC protocol is then proposed that would theoretically close

this delta while still providing sufficient authentication assurance.

THIS PAGE INTENTIONALLY LEFT BLANK

vi

Il.

Il.

IV.

TABLE OF CONTENTS

EN TROD U CITLON si cateusetsicevecouvsoscisiensesossdessedaccottuebavousubsbessovdcoenstouasonecsobussexbscesanstisoased 1 A. IMPACT OF REID TECHNOLOGY sissscseehesiccsh cceecitstenslnieca ciety 1 B. PASSIVE TAG STRUCTURE sis icsssisonsseccssssccticcsacsscinsscscecnncbeaesndesetivsasecasberecs 3 C. SCOPE OE THESES viiisstss exis cacecsasiouiseoscncsasbias ouispsetecasnschbsenssecaavssssortosateattos 10 PASSIVE TAG FOUNDATIONS AND CHALLENGES ............ccssssssssssssccsscceeees 13 A. AUTHENTICATION CAPABILITIES ............ccccssscssscsccssscsecceccsescscsssccnees 13 B. CURRENT PHYSICAL CHARACTERISTICS OF PASSIVE TAGS....15 1. Near- and Far-field Power Generation. .............ccsssccssssscsssssceseescess 15

2 POWer CONSUMPULOM sss vesscsnscssccsscevecesseensscbevevscessonnacvosencssnsnevetonasenacones 19

3. Time and Charging Requirements..............ccsssccsssssccssssscssssccssssseees 20

4. Hardware Clocking and Physical Layout. ...............sccssssccssssscssscesees 22

C. SECURITY MECHANISMS wiscseciseccssssticesctescssectesdcsngescccbotasvacsncssacceotesbieonel 25 1. Symmetric and Asymmetric Design Criteria ................sccscessseseeeees 25

Zs Hash Authentication AIgorithms.............cccscccsssccssssscssssscssscecsssssceess 27

D. KNOWN VULNERABILITIES ..........ccsccssssssssccsscssccssscsesseccssscsecsssssssssesseees 29 1. Exxon Mobil SpeedPass...........-cccsssssssssssssssssssssssssesssssssssssessecssasecees 29

RFID SECURE AUTHENTICATION CONCERNG...........cccssscsssseccsesssecsscsssseneees 33 A. AFFORDABLE COMPLEXITY scsvosicsscicsscicotisisscotsestessvsesceosscesconevisecssnasiecs 33 1. Defi Omin= Cerin sicciscseccastsseucasuesscesicdsevasiscocteoutsoassgincsocsadeapecusiveasaes 33

ps DESIST PPO SPESSION siaiccaisiscvisdastesccusitevandecddicedsel svbdetesdesdsdesdeievsadaceave 34

B. KEY: DISTRIBUTION ‘isssssevesccssevcscesnesessesssvccancstsctiescesouvevesiveves dsasteacvotsecsecsveees 36 1, Roll-over Key Set Expiration and Management...............csscssssscees 36

C. SECURE CHANNEL TRANSMISSION REQUIREMENTS ...........00000 38 1. Real-tinmie Tr aching ocicc. ice cisicsccss catsvcteicssueseavsac covandecestacsvecsincnoscratenvenes 38

2; Provision against Spoofing ............cccccccsssccssssccssssccssssccsssscssssccsssescees 38

A MODEL FOR SECURE PASSIVE TAG AUTHENTICATION ...........ccesscesees 41 A. DESTIGN:AGOAES « ssccsctocsicaspocuieds iucnsvess so gevCeabvave tctpossecupbaveban soshscadbysaebenipuoniosnes 41 B. HARDWARE ARCHITECTURE wu.........ccsscsssssscsscssccsccssccsescsessoscsescsecsescsere! 42 C. MESSAGE EXCHANGE PROTOCOL 2.0... .ccsscsscssssssccssscsesceccssccsescsessees 43 D. HAS HIVE CHA NES Mi octcccsstecceatascatiecis schecccclactcves setecezhccsecenceicasttageneeetethccesd 45 1. CD PETZ ACION sie cccsievssisucssavecsostues sicunaeneasvsveselcvanesvenatevnensuanndshienesseoasotee 45

pe PO WOE USA be visi sasscusctasatuscatsverletieveres dusnvessdeacooasoaseioncdoutedilaastavedeuuvaateed 46

3. CTOCK SEM COU PE asic ccs sensi shcneiksssacetgssstencaoianedbsceacanestadasidjsstcansaniosebhiscecds 50

E PRE-SHARED KEY STORAGE .uu........ccssssssssssssccsscssccsescescscscsecssscsecssesseees 51 i. Benefits of Roll-over System .............ssccssssccssssccssssccsssccssssscssssssssssseees 51

F. HARDWARE CONSTRAINTS ....ccssscsssssssscosssscssessscsssscsescsocsscssesssossensoenseess 51 G. ANALYSIS OF MODEL iisiscsccctsccessssesveceesecucessssnedassevvt cose satesdeetass secsvvuvescsunives 52 1. Resistance to Known AttackS.............scccccccsssscsssecssscecssscessccsessssseees 52

a. LON TIAE sah itn ssahett ase AADC EO: 52

b. RODD cssisiicteweadiginsdeisdaniaadsiien apa ne 53

Vv CONCLUSION sssissees ccna staisaavicussienrevasteiautsostsctet ong ateuceseseducechsunsictdeseedecpstedscavousue deters A. BEST PRACTICE SUGGESTIONS sissscsicsscscsciecestiecnsecsecsecessccssvoneccvecestcucece B. SATISFACTION OF PASSIVE DESIGN CRITERION............cccssssssseees C. BUITURE, WORK 6 sscsasiniesesicticaleastets cocscsusbcdissseestcessecuistsGsosubencsbcnecs eoontaeeusGnsdeess LIST OF REPRE RENCE scssetsissccestnissdessddeccosseitasesiusestesdstadcessddescadsen secede tloveesssieddenecdoosesessveeas INTETA BL DISTRIBUTION DAS © cczicccssseisncusiwestdostibanessscaoarnatendedssanescvesceacecsssscoceseeahesssaneases

vill

Figure 1.

Figure 2. Figure 3. Figure 4. Figure 5. Figure 6. Figure 7.

Figure 8.

Figure 9.

Figure 10.

Figure 11.

Figure 12. Figure 13.

Figure 14.

Figure 15.

LIST OF FIGURES

A Passive RFID tag developed by Texas Instruments for use in anti-theft

BCS CS ar erica a sts dnlcee gets bos capo geen hen olan aus RIG ehesta ae edu nunaumipeageak Ma Meanie 2 Electro-magnetic induction in relation to passive RFID systems. From [1]......6 Far-field RFID interaction, otherwise known as backscatter. From [1] ............ 8 A simple authentication scheme for passive tags ..........::ccescceeseeesseeeseeetseeeseeees 14 The logical flow of a passive tag authentication mechanism .............:eeeees 15 The EPC Buttertly tae: From [71,12] cc.scsaesquendeceaesannedatatescecudadadecsatuaetacavies 18 Logical depiction of RFID voltage sensor, which determines whether the

system’s capacitor is fully charged. From [14]........ cc ceeeeeeeeceteeneeeteeeeeeeeeeeees 20 The MDS hashing algorithm as simulated on a Virtex V XFT70, using

PTS: TOONS iss seo elaiaesbaci ive ese Si hss ich ciciceerae ctv earsinreaeeoyacaeie, aan ayaa 22

An inductive oscillator for passive RFID tags (125 KHz band). After [16]....24 A symmetric key authentication mechanism for passive RFID tags UtZing A hash: Mn HOM aceite snciadteeedaseicle castes a atie aati AEA anes 2f The serialized hash functions at the core of SHA—1. x, y, and z are 32-bit words from the 512-bit block size. Each function (Ch, Parity, and Maj) is called depending on the position in the 80-round iterative round count. LENS) 40 ce 9 Perret ment Mitek eee Mee See an neste SER oa ree AORN Cena nae ENT Ree art eleay Inte mn 44 Power consumption of the un-optimized SHA-1 core on an Actel Igloo PLGLGOQOV Daca iss coucesstisces onsale pu hice ie telecesp tu dendasea nist vag sates gine steaNecstoveastacassvedecss 47 The regression line used for an estimate of power consumption at lower COCK IREQUCNCICS so oassd etre tute Magsiued ied wan oeeslued ete woman aa eed ts 48 Slope equation for line of best fit in least squares regression. X; represents an individual clock frequency measurement, X is the associated mean. Y;

is the power consumption and Y is the MEAN. .........e eee ecceeeseceeeeeeeeeeeceeeteeeeaeeees 48 Power consumption of the optimized SHA-1 core on an Actel Igloo AGL600V2 at 1500 KHz clock speed. 000... cee eccecssecsteceteceeeeeeseeceeeceteeseneeeaeees 49

ix

THIS PAGE INTENTIONALLY LEFT BLANK

Table 1. Table 2. Table 3.

Table 4.

LIST OF TABLES

Frequency characteristics of RFID systems. After [1].......... ce ceeseseeseeeeeeeeeeees 4 Power consumption of SHA—1 simulation. From [18] ........ cece ceeeeeseeeeeeeees 28 Clock frequency/power consumption of pre-optimized SHA—1 core on an

Actel Igloo AGLGOOYV 2: Frome [23 | vecsssiicstecckseGiccesscvcanceasesiectess beaded viantieatenbenss 46

Clock frequency/power consumption of the optimized SHA-—1 algorithm. ....50

x1

THIS PAGE INTENTIONALLY LEFT BLANK

Xii

LIST OF ACRONYMS AND ABBREVIATIONS

RFID: Radio Frequency Identification

ASIC: Application Specific Integrated Circuit

SAW: Surface Acoustic Wave

ALU: Arithmetic Logic Unit

RF: Radio-Frequency

CRC: Cyclic Redundancy Check

Ie: Integrated-Circuit

FPGA: Field Programmable Gate Array

CMOS: Complementary Metal-Oxide Semiconductor

PIE: Pulse-interval encoding

IDT: Inter-digital transducer

AES: Advanced Encryption Standard

EEPROM: Electrically Erasable Programmable Read-Only Memory

VHDL: Very High Speed Integrated Circuit Hardware Description Language

MAC: Message Authentication Code

xiii

THIS PAGE INTENTIONALLY LEFT BLANK

X1V

EXECUTIVE SUMMARY

Radio frequency identification (RFID) devices are becoming more and more popular as their usage scope moves from an environment purely of logistical tracking to one of information retrieval, cataloging, and personal information management. Passive tags, in particular, offer several advantages when used in this environment. Their absence of power makes them more eco-friendly, their size makes them adaptable to any environment, and their cost makes them producible en-masse with minimal concern for bloated production control issues. However, these advantages are not without their drawbacks. Because of their lack of an onboard power source, passive tags must make several compromises. For instance, they cannot perform complex cryptographic security calculations and, thus, are less capable of supporting electronic authentication protocols than their cousins, active tags. Passive tags also typically do not involve a microcontroller or any other high gate-count application-specific integrated circuit (ASIC). Their lack of onboard power means that the tag interrogation procedure must be performed at relatively close distances. Even given these restrictions, passive tags still represent the natural progression towards smaller, more versatile, and more ubiquitous

identification mechanisms.

Passive RFID tags can potentially be used for tracking vehicles through checkpoints in combat environments, displaying a soldier’s shot record, and other uses as trivial as warranty tracking of high-end consumer goods. Unfortunately, passive RFID tags currently offer only minimalistic versions of authentication mechanisms that do not elicit the necessary level of trust to be used in the above listed applications. These authentication mechanisms include simple XOR and shift ciphers that, when paralleled, create rather rudimentary authentication schemes. Such rudimentary schemes are subject to being impersonated; typically via an attack called “cloning.” Additionally, the use of a singular pre-shared key among all production tags dramatically increases the viability of

such malicious attacks.

XV

Current advances in low-power mechanisms—which normally are involved in more complex cryptographic algorithms—are now feasible for implementation in low- power environments, such as for passive RFID tags. Until they can be used effectively, however, several considerations must be made for their employment including power efficiency, clock synchronization, key management, and resistance to attack. A secure, passive RFID environment must be robust enough to provide real-time tag authentication, powerful enough to energize tags from a prescribed distance, and secure enough so that would-be attackers do not easily gain mission-critical information. Thus, there are several design considerations involved in the fielding and production of a secure passive RFID system. The main research question pursued in this thesis is: Given the current state of passive RFID technology, is it possible to support a sufficiently secure, keyed-

hash (MAC) authentication mechanism on an RFID tag void of a native power source?

Through the use of component analysis, this thesis analyzes the major factors in designing a lightweight authentication scheme for passive RFID tags. Each component of the RFID system is critical to its success. For instance, inducing an electromagnetic field onto a passive tag must generate a native clock signal via its carrier wave that successfully drives the tag’s circuitry. This induced electromagnetic field must be fast enough so that the tag receives a sufficient amount of power, both to generate a security response and broadcast that response back to the tag reader. So, in this thesis, we ask: Is it feasible that a sufficiently complex security algorithm such as SHA~1, can be employed on a passive tag? If the answer is “no,” then what reductions might be made to any existing MAC authentication mechanism so that it can be employed on a passive tag

without losing too much entropy?

This thesis presents a model that answers the aforementioned question, and is scrutinized against the foundational metrics of passive tags. Questions surrounding key management, proximity, and malicious attacks are all satisfied in fulfillment of the model

specifications.

XVI

ACKNOWLEDGMENTS

This work is dedicated to my wife, who has tirelessly endured the endless frustrations of a master’s student trying to garner hardened facts in the myriad of

theorems, hypotheses, and conjectures that is Computer Science.

I would specifically like to thank Peter Ateshian, Doug Fouts, and Dan Zulaica for their exhaustive aid in circuit design and hardware coding. Their selfless donation of time towards aiding me in understanding the technical aspects of FPGA construction was

invaluable in the completion of this thesis.

XVil

THIS PAGE INTENTIONALLY LEFT BLANK

XViil

I. INTRODUCTION

A. IMPACT OF RFID TECHNOLOGY

RFID technology is one of the fastest growing areas of identification and tracking management today. The potential ubiquity of such a technology has become evident from its adoption by major global corporations such as Wal-Mart. At a 2003 Retail Systems conference at the McCormick Center in Chicago, Wal-Mart announced it was mandating RFID tracking technology from its suppliers “in the near future” [1]. Shortly thereafter, the EPCGlobal standard was released in 2005 [2]. This standard, designed to augment and eventually replace traditional bar code scanning, has become wildly popular in Europe but has been slow to saturate the U.S. market. Regardless, the integration of EPC information into RFID systems has been the single-largest reason for the recent

prevalence of RFID tags.

Owing to their extremely small size, RFID tags offer an impressive range of capabilities in both powered and unpowered forms. Powered tags, or those with a native on-board power source such as a battery, are also known as “active tags.” These tags can be programmed to continuously broadcast their information, aiding in the use of real-time tracking. For instance, active tags are widely used in vehicle tracking systems by the U.S. Department of Defense (DoD) [3]. Active tags are affixed to vehicles so that a tag reader can accurately read their information, wirelessly, even while on the move. Unpowered tags—those without a native power source, also called “passive” tags—do not continuously broadcast any information. Passive tags obtain all their operating energy wirelessly from a tag reader. This reader can be mounted in a relatively fixed location, or can be a handheld device. One such method of implementing this wireless power generation is called electromagnetic induction, and this is the most common

method of energizing a passive tag.

While passive tags suffer from several limitations, such as energy, distance, and efficiency, they represent the forefront of RFID design. Passive tags can be fabricated to

be wafer-thin, some less than a micrometer in thickness. Their size also enables a low 1

manufacturing cost and simplistic distribution scheme. For instance, many DVD cases now include RFID security mechanisms with an adhesive backing that can simply be

affixed to the inside of the case (Figure 1).

Figure 1. | A Passive RFID tag developed by Texas Instruments for use in anti-theft DVD cases

Because of their low cost (often under $0.15 per tag [3]), passive tags often take on a disposable role. That is, the cost to manufacture the tags is so minute that companies consider them to be expendable. This is not to say that passive tags are not without their importance, however. Passive tags are preferred in generating the aforementioned EPC code in logistical tracking applications, and thus must have the appropriate measures of security. If the EPC code placed on a passive tag is “exploitable” for whatever reason, necessary security precautions must be made to guarantee the tag’s authenticity. Otherwise, opportunities are abundant for attacks such as tag cloning, replaying, falsifying codes, etc. By “exploitable,” we mean that there exists some motivation for a bad actor to impersonate the EPC code. As a simple example, we might imagine containers queued-up for a security inspection of their contents prior to being loaded onto a commercial container ship. Each container receives an RFID tag after it passes inspection, and the tag’s EPC is entered into a database that is made available to security screeners at the port of debarkation. If a bad actor can

impersonate the EPC of a tag that has already been affixed to a cleared container, and

affix this “cloned” tag to an un-screened container, he may be successful in getting

contraband through the security screening at the port of debarkation.

Therefore, our intent is to determine whether, given the limitations of passive tags, it is possible to support a sufficiently secure authentication mechanism on an RFID tag void of a native power source. This sufficiency might be satisfied with a keyed hash solution, as hash algorithms are traditionally less computationally expensive than reversible cryptographic mechanisms (i.e., symmetric and asymmetric encryption algorithms) [4]. Later, this thesis will explore a model that attempts to answer this question, and then scrutinize the model against the foundational principles of passive tags. Such questions of proximity, efficiency, and policy satisfaction will be answered in

fulfillment of the model’s design goals. B. PASSIVE TAG STRUCTURE

Passive RFID tags operate via one of three power generation methodologies. Overwhelmingly, power generation dominates the capabilities and limitations of a passive tag. To answer any question involving the choice of a security mechanism on a passive tag, a thorough understanding of how power is obtained by the tag must be considered. Two of the power generation methodologies (near and far-field coupling) are quite popular and a third (Surface Acoustic Wave, SAW) is just becoming popular. Each has strengths and weaknesses, mostly related to the operating range at which the reader interacts with the tag, and the frequency at which the tag can be energized. A summary is

given below in Table 1.

Near/Far Field

ISO/IEC 18000-6 EPC class-0, class-1

Passive or active

Supply chain pallet and box tagging, baggage handling, electronic toll collection

Table 1. Frequency characteristics of RFID systems. After [1]

Near-field coupling is typically produced at close-range distances and at lower frequencies, due to the magnetic properties of an induced current. Suppose there are two pieces of conductive material, or conductors, placed relatively close together. When a current is applied to the first (primary) conductor, the alternating movement of electrons forms a magnetic field around that conductor. Because this magnetic field was produced via the use of electricity, we call it an electromagnetic field. The electromagnetic field is polarized either north or south. When the second (secondary) conductor is brought within a prescribed distance of the first, the electromagnetic field induces electron flow (current) in the second conductor. Note that this second conductor had no electrical current to begin with. This is the foundational principle of Faraday’s electromagnetic induction, which is key to the operation of passive tags. The new, induced, current in the second conductor has similar properties to the first. It has a measurable current, voltage, and frequency. The induced current is somewhat smaller than that of the primary due to less than 100% coupling efficiency, but enough energy is transmitted to perform

electrical work on the secondary side.

Passive tags that operate via near-field coupling (Figure 2) use the energy gained from the above described transaction to perform some type of computation. They then transmit the result of this computation back via their own antenna (the secondary conductor in the above description), again generating an electromagnetic field. This time, however, the electromagnetic field induces a current on the reader’s antenna (the primary conductor). If this current is the same as the one originally used to generate the electromagnetic field traveling from reader to tag, the reader will never be able to distinguish this new current, from the original one. So, the reader continually varies the current that generates its electromagnetic field via varying the load on its antenna coil. This technique is called load modulation. This variation in current can be seen as a variation in current on the reader’s antenna coil, due to the mutual inductance between the two. One might assume that it would be more efficient for the reader to transmit energy, and then proceed towards a “listen mode” where it is not transmitting energy, so that any current received is known to be from a tag. However, passive tags do not contain any onboard power source. For tags to generate a current, and thus an electromagnetic field, strong enough to propagate back to the reader, continual energy must arrive from the reader. Additionally, a passive tag reader could potentially read tens, or hundreds, of tags concurrently. The wait periods accrued for “listen mode” can

accumulate quickly and give rise to massive inefficiency.

Power and data [SE , Tag inlay

Network interface

am me% Data transmitted ra rare via changes in field strength

Alternating magnetic field in near field region

Figure 2. Electro-magnetic induction in relation to passive RFID systems. From [1]

Far-field coupling differs from near-field coupling in that there is no restriction on the field boundary [1]. The field boundary is the distance at which near-field coupling becomes inefficient, and far-field coupling becomes more attractive. In other words, this is the boundary distance at which the tag’s modulated current cannot be seen in the antenna coil of the reader. In the equation below, dpoundary 18 the boundary distance, c is

the speed of light, and f is the frequency of the electromagnetic wave:

Gpoundary =¢/ nf el 1)

Equation (1.1) shows the inversely proportional relationship of frequency to the boundary distance. Because of this, only higher frequencies are used in far-field coupling [5]. In other words, as the frequency of the electromagnetic wave increases, the boundary distance decreases, meaning that near-field coupling is only applicable at smaller distances between tag and reader. Thus, low frequencies lend themselves better to near-field power transfers at greater distances, while higher frequencies are more attractive for far-field power transfers, where greater distances between tag and reader are

possible.

In far-field coupling, a current is applied to the primary conductor at (typically) a much higher frequency, due to (1.1). Again, this current creates an electromagnetic field that radiates outward. A portion of this electromagnetic field (a form of energy) is captured upon the second conductor as a potential difference [1]. Because higher frequencies produce greater amounts of energy, as will be explained shortly, far-field coupling does not require a dependence on the continual application of energy from one conductor to the next as in near-field coupling. The electromagnetic energy is high enough that it can be reflected back from the secondary (receiving) conductor. Intelligence can be reflected back to the primary conductor due to an impedance mismatch between the secondary conductor and whatever circuit it is connected to. By changing the mismatch with a varying load (load modulation), as in near-field coupling, the second conductor can encode a message on the reflected transmission. This technique is known as backscatter. The portion of energy not reflected back can be used for electric

work, including varying the load on the antenna.

Far-field coupling (Figure 3) supports greater distances between an RFID tag and reader than does near-field coupling. This is due to the fact that signal attenuation, as a function of distance, is less dramatic with far-field techniques than with near-field techniques. The attenuation of the EM field in the far-field region is proportional to 1/d’, where d is the distance between tag and reader [5]. In the near-field this attenuation is 1/d°, a considerably larger value [1]. However, while the greater distances can be achieved due to reduced attenuation over distance, more energy must be dedicated to changing the impedance mismatch of the reflected wave. This starves the processing subsystem of crucial energy needed for complex computation. In this thesis, we will

explore just how much energy is needed for computation.

Power and data [NE

Tag inlay

Control/

memory/ crypto

——

Network

interface

wee wwe eee ee ee

es Data transmitted via backscattering

Antenna

Propagating electro- magnetic field

Near field region <¢— far field region

Figure 3. _ Far-field RFID interaction, otherwise known as backscatter. From [1]

A third methodology for the wireless transfer of operating power to passive tags is surface acoustic wave technology (SAW). SAW technology relies on an inter-digital transducer (IDT), which converts radio wave pulses into an airborne pressure differential, or acoustic wave, and vice versa. The inter-digital transducer relies on the piezoelectric effect and, thus, does not require a DC power source. First, an electromagnetic wave is transferred from reader to tag in the normal way. Next, the IDT converts the electromagnetic wave to an acoustic wave and propagates it across a tag’s circuitry into a set of programmed reflectors. These acoustic reflectors are tuned only to react/respond to the appropriate frequencies and pulse widths of the original (sender’s) signal. Their reflected signal is sent back through the transducer and transmitted again as a radio wave to the tag reader. This reflected signal usually will contain the EPC code of the tag. While SAW technology is already quite advanced, recent innovations in device miniaturization have allowed SAW RFID devices to be built even smaller and faster than

their traditional silicon counterparts. Unfortunately, acoustic waves cannot be used for

complex computation because they deteriorate rapidly [1] and would not be a good

choice for tag circuits, such as authentication mechanisms.

Closely tied to how a tag receives its wireless power, is how that tag uses the power to perform its computation. Passive RFID tags typically operate on the micro-watt scale, with 20 micro-watts being the notional mean among tags. Although as much as 1 watt of power can be transmitted in the near-field design, hardly any of that power is induced onto the tag’s processing subsystem. Therefore, the circuitry on the passive tags must be efficient enough to not only use this power for generating a response, but also to broadcast that response back to the tag reader. Additionally, certain useful circuit components, such as a clock, are very costly in terms of their power consumption. Complex symmetric and asymmetric cryptography mechanisms also have hefty

processing and power requirements.

Passive RFID technology operates in an area where a plethora of factors all work together to generate a result. The near- and far-field boundaries correlate a distance and frequency with how much power can be induced onto the tag itself. The storage mechanism for the induced energy must be small enough to keep the tag size, and thus the production cost, down while still being large enough to deliver voltage at the prescribed levels for the duration of the communication session. Finally, any security mechanism on the tag will add to the total amount of energy necessary. Conversely, for a fixed amount of power, the complexity of any security mechanism will be limited accordingly. The security mechanism is typically a single-purpose gate array instead of

more power-hungry arithmetic-logic-unit (ALU) style circuits.

Currently, there are few passive RFID security mechanisms that are both in production, and have shown resistance to exploitation. In 2005 [6], a team from Johns Hopkins University successfully cracked a passive RFID tag with relatively simple brute force strategies. The tag they cracked, built by Texas Instruments, was used in thousands of Mobil gas station Speedpass pay-at-the-pump systems, as well as the keyed anti-theft security device used by Ford Motor Vehicles. In a relatively short amount of time, the Johns Hopkins team of graduate students not only brute-forced the encryption

mechanism, but were also able to completely reverse engineer the passive tags’ circuitry 9

so as to clone them. Their attack enabled them to demonstrate stealing a car and purchasing gas, all with a cloned RFID tag instead of the real one. The paper they published raised awareness of an issue not seriously considered before. That is, passive tags are so inexpensive and have such a disposable nature that their security was never given much priority. However, we now see passive tags used in a broader spectrum of environments and applications, many of which involve the access to information of a sensitive nature. Medical prescriptions, credit cards, and even luggage have been “tagged.” These areas offer a wealth of information to any would-be attacker, far more than a free tank of gas. A security mechanism must be used that offers adequate

protection while maximizing power economy and cost. C. SCOPE OF THESIS

This thesis explores the technical considerations and limitations of passive RFID systems. Power generation alone generates a plethora of factors that must be analyzed and decided on before a passive RFID tag structure can begin to evolve. Additionally, physical proximity boundaries must be weighed, as well as the complexity of any security algorithm employed. Such analysis produces a measure of affordable complexity in a passive RFID system. This “affordable” complexity is a synergy of all the mitigating factors of passive RFID tag technology to produce a system that can provide a sufficient measure of authenticity. Ultimately, the question is whether a sufficiently secure

authentication mechanism can be employed on a tag void of a native power source.

This thesis is organized into the following chapters. Chapter II covers the basic physical characteristics of an RFID system, as well as current physical characteristics of production-grade passive tags. A brief description is given of historical attacks against

passive tags that have garnered massive success.

Chapter HI addresses security concerns for a passive RFID system, in relation to secret key distribution, a roll-over keyset, and transmission requirements. Chapter IV proposes a lightweight tag authentication mechanism utilizing the SHA-—1 hashing algorithm on a passive tag. In this chapter, several of the fundamentals of passive tag

design are used as metrics for judging the effectiveness of the proposed mechanism. The 10

mechanism is scrutinized in order to satisfy the primary research question by showing that the proposed mechanism is sufficiently “lightweight,” sufficiently secure, and

operational via one of the aforementioned passive power delivery coupling schemes.

Chapter V is a discussion of the best practice uses of such a mechanism as proposed in Chapter IV. Also included, is a description of how the proposed mechanism

satisfies the design criteria for a passive tag of this nature.

11

THIS PAGE INTENTIONALLY LEFT BLANK

12

Il. PASSIVE TAG FOUNDATIONS AND CHALLENGES

A. AUTHENTICATION CAPABILITIES

Passive RFID systems can exhibit several aspects of authentication mechanisms. From a minimalistic point of view, passive tags can exhibit no authentication mechanism at all. In this way, a passive tag simply reports a serial number or other piece of information hardwired to the tag [7]. Neither the reader nor the tag authenticates the other device, so no real security mechanism exists. In order to properly authenticate either side (reader or tag) of the message exchange, one of the known factors for authentication must be used: something you know, something you have, or something you are. Some active RFID systems use the “something you have” factor for authentication, relying on a complex cryptographic function involving a public key infrastructure [8]. Calculations surrounding the public key systems are usually processor intensive and require a significant amount of power, neither of which is available to a

passive tag.

Now consider a passive RFID system that authenticates both the tag and reader with a simple pre-shared key and cryptographic function. Every tag would need a copy not only of its own key, but a copy of the key for every reader in the system. Ina passive RFID tag, the additional circuitry required for storing all this excess information, not to mention the cryptographic mechanism’s additional power requirement, is far too extreme. Most passive tags avoid this by performing no authentication at all, as

mentioned above.

In Figure 4, a simple tag authentication mechanism is shown. First, a challenge is generated from the reader. This challenge is a bit string of sufficient length and randomness so as to mitigate the possibility of a replay attack. Second, the challenge is sent to the tag, which uses one of the power capture methods mentioned in Chapter I to generate a response. The response can be generated with a simple XOR operation, shift cipher, or hash mechanism. It is critical to the response, however, for the response to

involve some secret known only to the tag and reader (or back-end system, which is 13

available to the reader). Without the secret, the response could easily be analyzed and reconstructed by someone intent on subverting the authenticity of the tag’s data. Therefore, the shared secret provides authenticity to the exchange. The third and fourth steps involve concatenating some identification string to the response to authenticate the tag. This identity string gives the reader a critical piece of information. The reader can now look up the associated shared secret applicable to that tag, and then process the sent challenge itself and compare the result with that received from the tag. If the response the reader generates is the same as the one received from the tag, then the tag is proven to

be authentic.

2) Tag generates response

RFID Passive Tag 3) Response is

concatenated to tag identification string

1) Challenge “A

=~"

sent to ta ————S—S=——

RFID Reader

4) Remaining power is used to transmit response and tag ID

Figure 4. | A simple authentication scheme for passive tags

Figure 5 defines the protocol flow illustrated in Figure 4. This model is the foundation for most passive tag authentication mechanisms. A challenge is sent from reader to tag, the tag computes a response, based in some way on the challenge and a shared secret, and the response is returned to the reader along with some identification string. The “tag mech” is the security algorithm run on the tag and is the same as

“reader_mech.” Some passive tags such as those seen in [9] use a hash function for the

14

security mechanism. The mutual protocol in [9] is based on write-many passive tags that also include additional inputs to the hash function. Such a technique is known as salting the hash function. This salt is some additional input that makes the result of the hash function unique. A downside to the advantage of salting is that the passive tag must include some storage mechanism, such as flash memory cells, that can consistently be written and overwritten with a new salt value every time a tag and reader communicate. As will be discussed in Chapter IV, a sufficiently random challenge structure (Cyeader 1n

Figure 5) omits the necessity of using salt.

C = challenge Kk = shared secret P =result of security mechanism function (tag_mech or reader_mech) id = tag identification string = response string

iF Creader

2. {Cresaet 9 Kgared | ee aaedh =P tag

Sule ag tee

4. Resolve Ida. to Kharea

Sli eee Fy dived | scader neck = then authentic

Figure 5. The logical flow of a passive tag authentication mechanism

B. CURRENT PHYSICAL CHARACTERISTICS OF PASSIVE TAGS

1. Near- and Far-field Power Generation

Several factors contribute to the power available to a passive tag. First, the choice between near-field and far-field power generation must be made before tag production. Most often, the goal of a passive RFID system is to maximize the amount of power able to be garnered at the tag from the reader to tag interaction. The choice, then, involves a number of factors to be considered such as frequency, wavelength, distance, gain, efficiency, and path loss. At first glance, it would seem that Planck’s constant defines

enough information to make this choice simple:

E=hv (2.1) 15

Put simply, Plank’s constant (h) in Equation (2.1) defines a relationship such that, as frequency increases (v), the amount of energy produced (E) also increases. Thus, the backscatter methodology, with the use of higher frequencies producing more energy, is more mathematically justified. However, higher frequencies are also considerably more directional, something difficult to control in an RFID environment. We can imagine a scenario where several boxes are stacked on a shipping palette, all with RFID tags. Some of the tags on these boxes are not directly within the line-of-sight of the RFID reader. This line-of-sight means that both the tag and reader suffer from no occlusion or obstruction inside the path between them. Higher frequencies, being more directional, require a degree of clear line-of-sight because absorption affects them more drastically. In this example, if the higher frequency electromagnetic wave from the reader must travel through several boxes to reach the one of interest, the signal could be drastically reduced when it reaches the RFID tag. The boxes and their contents, as well as any reflections of the wave, all absorb energy from the higher frequency, thereby reducing its ability to induce as much energy as when it left the reader. A lower frequency, on the other hand, does not suffer as much from absorption. Thus, a lower frequency arrives at the box of interest not nearly as degraded from absorption as the higher frequency. The advantages of using higher frequencies are not without the requirements of line-of-sight, or in other

words, a minimization of the factors that contribute to absorption.

As we explore the advantages/disadvantages of using higher frequencies, we must also address the inverse relationship of frequency to wavelength. As frequency goes up, wavelength decreases, having effects of the size of the antenna used. Since antenna size is one of the more tangible elements controlled in the construction of a passive RFID tag,

it is useful to see Planck’s equation incorporating wavelength: v=c/iA (2.2) E=he/iz (2.3)

Equation (2.2) is the mathematical relationship showing that, as frequency

increases, wavelength decreases and vice versa (c is the speed of light). Thus, we can

16

create a new equation, Equation (2.3), that shows a relationship involving Planck’s constant, wavelength, and energy. It follows from Equation (2.3) that, as wavelength

decreases, the energy produced increases.

Up until this point, our discussion of the factors involved in power generation and the choice of near-field and far-field methodologies has been largely based around the RFID reader and the energy it is emitting. A more dominant factor, however, is the RFID tag’s ability to receive the energy transmitted from the reader. From Equation (2.3), it appears we desire a smaller wavelength (i.e., higher frequency) for reader to tag communication in order to produce more energy. As noted above, smaller wavelengths are directly proportional to the size of the antenna used to receive them. Notably, smaller antennas are less capable of garnering as much current via electromagnetic induction as are larger antennas. So again, it seems that higher frequencies (smaller wavelengths and

antennas) are unattractive for maximizing the energy received in the tag.

There must be some other factor that allows us to choose between near- or far- field power generation so as to maximize the positive aspects of higher frequencies (producing more power for complex computation), and mitigate the negative effects of smaller antennas. This factor is known as antenna gain. Antenna gain, or the measure of an antenna’s directional intensity, allows antennas to achieve the best of both worlds. Succinctly put, increasing an antenna’s gain allows it to more efficiently receive electromagnetic energy. The following equation (Frii’s equation) provides the basic mathematical structure for measuring how much power is available to a passive tag,

while incorporating the factor of antenna gain [3], [10]: Preceived = (Piransmitted xX Greceiver Xx Gtransmitter x He) / (4nd)° (2.4)

In Equation (2.4), Preceivea 18 the power received by the tag, Piransmittea 18 the power transmitted from the reader, G is the antenna gain, and d is the distance between tag and reader. At first glance, it would seem that maximizing wavelength, not gain, would have the greater effect on Preceived, but this is incorrect due to the calculation for antenna gain (G=4nA,/ 2? ). This new factor introduced, (A,), is the effective aperture of the antenna,

or the measure of the antenna’s efficiency inside a specific medium (air, space, etc.).

17

Preceived = (Prransmitted XA; X At ) / (A? x d’) (2.5)

Via substitution, Frii’s equation can be modeled as in Equation (2.5) using the equation for antenna gain. We now see again that smaller wavelengths (higher frequencies) produce more power; this time with the inclusion of the measure of distance between tag and

antenna, and the affective aperture (efficiency) of the respective antennas.

Antenna gain (and consequently effective aperture) can be achieved a number of different ways, but most popular is the looping of antenna elements (seen in Figure 6) so as to create an increased surface area for the captured wavelength. This increased surface area produces a semi-directional tag that maximizes the potential