Cryptographic Protocols for RFID Tags Study & Defense

PhD Dissertation Defense A Study on Cryptographic Protocols for RFID Tags PhD candidate: Dang Nguyen Duc Advisor: Prof. Kwangjo Kim Information and Communications Engineering KAIST 1st December, 2009 Cryptography and Information Security Lab @ KAIST

Contents IV. Scalable Grouping IV. Scalable Grouping- -Proof Protocol for RFID Tag for RFID Tag Proof Protocol I. Introduction I. Introduction 1.1. Overview 1.2. What is RFID? 1.3. RFID: Security Threats & Requirements 1.4. Cryptographic Primitives 1.5. What Do Cryptographers Do? 5.1. Previous Grouping-Proof Protocols 5.2. Scalability Issues of Previous Protocols 5.3. Security Definition 5.4. Scalable Construction from (n, n)-Secret Sharing II. HB*: Lightweight Authentication II. HB*: Lightweight Authentication Protocol Secure Against MIM Protocol Secure Against MIM V. Conclusion V. Conclusion 2.1. LPN Problem 2.2. HB Protocol 2.3. HB+ Protocol 2.4. Man-in-the-middle Attack on HB+ 2.5. HB* Protocol VI. Future Work VI. Future Work Publications Publications III. Preventing III. Preventing DoS Authentication Protocols Authentication Protocols DoS Attacks in RFID Attacks in RFID 3.1. Privacy vs Performance 3.2. OSK Protocol 3.3. O-FRAP and O-RAP Protocols 3.4. DoS Attack on O-FRAP and O-RAP 3.5. O-FRAP+ and O-RAP+ Protocols 2

I. Introduction I. Introduction - - Overview Overview The contribution of this thesis is three-fold: HB*: a lightweight authentication protocol Secure against man-in-the-middle attack. Defending some RFID authentication protocols against DoS attack Two-phase Authentication Grouping-proof protocol for RFID tags Scalability issues of previous protocols Proper security definition A scalable construction based on (n, n)-secret sharing 3

I. Introduction I. Introduction What is RFID? (1/2) What is RFID? (1/2) Ti T1 T2 Tn Reader T3 T6 T4 T5 T7 RFID Radio Frequency Identification Each RFID tag emits an unique number (EPC) serving as identity of tagged item whose information is stored in back-end database Backend Database 4

I. Introduction I. Introduction What is RFID? (2/2) What is RFID? (2/2) A typical application of RFID: Automatic supply chain management A typical RFID tag costs about 5 cents 5

I. Introduction I. Introduction RFID Security Threats (1/3) RFID Security Threats (1/3) Ti T1 T2 Malicious Reader Tn T3 T6 T4 T5 T7 Malicious readers scan legitimate tags to collect EPC numbers to make cloned tags Cloned tags can be placed on counterfeiting items (goods, passport, driving license, etc) 6

I. Introduction I. Introduction RFID Security Threats (2/3) RFID Security Threats (2/3) @ Ari Juels Privacy invasion #1: malicious readers can scan tagged items carried by end-users. Privacy invasion #1: malicious can used the unique EPC to track user s movement / build preferences 7

I. Introduction I. Introduction RFID Security Threats (3/3) RFID Security Threats (3/3) cloned tag T4 T2 T4 legitimate tag T1 T2 Ti Reader Tn T3 T3 T3 T5 Tn T3 T5 T4 T4 T6 T4 Large scale deployment of legitimate & cloned tags can overwhelm/abuse server s computational resources 8 Backend Database

I. Introduction I. Introduction RFID Security Requirements RFID Security Requirements A secure RFID system should provide: Mutual authentication between tag and reader Prevent EPC harvesting & cloned tags Privacy protection of end-users No tracking possible Resistant against DoS Filter out unwanted data as early as possible Key Exchange Share session key to securely transmit data (EPC) between tag and reader We need to integrate cryptographic protocols into RFID (especially, between tag and reader) 9

I. Introduction I. Introduction Cryptographic Primitives (1/4) Cryptographic Primitives (1/4) All of security threats to RFID are well- studied issues in cryptography. Why new? Computational functionalities of RFID tag is extremely limited. Public-key cryptography and block ciphers are beyond the capacity of low-cost tags (passive tags). Pseudo-random number generators, pseudorandom function and hash function (lightweight primitives) are our main tools. 10

I. Introduction I. Introduction Cryptographic Primitives (2/4) Cryptographic Primitives (2/4) Cryptographic hash function h(.): Compression: h: {0, 1}* {0, 1}n, n = 128 or more. Pre-image resistance: Given h(x), hard to find x Second pre-image resistance: Given x1, find x2 such that h(x1) = h(x2) Collision resistance: Hard to find any pair (x1, x2) such that h(x1) = h(x2) Practical cryptographic hash function SHA-1, MD5 (Soon to be replaced by SHA-3) Most hash functions are easy to implement on low-cost hardware 11

I. Introduction I. Introduction Cryptographic Primitives (3/4) Cryptographic Primitives (3/4) Pseudorandom Number Generator (PRNG): Random expansion: from random seed to a longer random string PRNG: {0, 1}n {0, 1}n+m Lightweight Implementation by using LFSR or block ciphers. Pseudorandom function (PRF) No random seed needed: take anything and output a random string PRF: {0, 1}* {0, 1}n Lightweight Implementation by using PRNG, block ciphers, etc. 12

I. Introduction I. Introduction Cryptographic Primitives (4/4) Cryptographic Primitives (4/4) Message Authentication Code (MAC): Require a secret key shared between sender and receiver: MAC: K M Origin of message can be verified: Compute MAC, and compare with received one Lightweight Implementation Adding secret key to hash function (HMAC) 13 @ Wikipedia

I. Introduction I. Introduction Cryptographer s Job (1/2) Cryptographer s Job (1/2) Two jobs of a cryptographer: Designing secure systems. Verifyingsecurity properties of claim-to-be-secure systems. Verification of security properties: Scheme A is secure We need to define what we means by secure (security definition) We need to quantify secure (security analysis) 14

I. Introduction I. Introduction Cryptographer s Job (2/2) Cryptographer s Job (2/2) Provable Security and Reductionism: Hard to measure security quantity directly Reducing breaking security to doing something else that is believed to be hard Polynomial-time Reduction Breaking Security of A Solving Hard Problem Polynomial-time Reduction Breaking Security of A Breaking Security of B 15

I. Introduction I. Introduction Authentication Protocol Authentication Protocol Authentication Process of verifying object s identity Authentication factors Something object knows: pre-shared secret Something object has: digital certificate Prover Verifier Random challenge Response Challenge-response Authentication Protocol 16

I. Introduction I. Introduction Notation Notation 17

II. HB* Protocol II. HB* Protocol LPN Problem (1/2) LPN Problem (1/2) Binary inner-product between two k-bit values a and x: B(a, x) = a x = (a0 x0) (a1 x1) (ak-1 xk-1) Very easy to implement on low-cost hardware 4-bit buffer memory is sufficient Is it useful for cryptography? Maybe, it has been used to construct (theoretical) PRNG (hard-core bit) For more cryptographic applications, where is the hard problem? 18

II. HB* Protocol II. HB* Protocol LPN Problem (2/2) LPN Problem (2/2) LPN (Learning Parity with noise) problem: Well-known problem in machine learning a1 x LPN: Compute x from noisy sampled data? a2 x a3 x a4 x NP-Complete problem: best algorithm takes 2O(k/logk) a5 x Hidden Value x a6 x LPN problem implies pseudo-randomness: (a, B(a, x) v)) appears as (k+1)-bit random string an-1 x an x 19 Noisy data Noise-free data

II. HB* Protocol II. HB* Protocol HB Protocol (1/2) HB Protocol (1/2) HB Human Authentication Protocol: Secure against passive adversary, i.e., one that only eavesdrops communication channel between Human and Computer. H (k-bit secret x, ) C (k-bit secret x, , ) {0, 1|Prob[ =1] = } a R {0, 1}k a z = (a x) z Check if z = a x Repeat above step q times (possibly concurrently). Accept only if C receives about q incorrectresponses from H A collection of (a, z) forms an instance of LPN problem HB suffers so-called incompleteness problem as the criteria about q incorrectresponses is not well defined 20

II. HB* Protocol II. HB* Protocol HB Protocol (2/2) HB Protocol (2/2) Is HB suitable for RFID Tags? No, secret key is leaked if C is malicious (no problem if H is human but an-autonomous device). Tag (k-bit secret x, ) Malicious Reader i {0, 1|Prob[ =1] = } a=a1=a2= =ak z1 = (a x) 1 z2 = (a x) 2 z1 = (a x) k z1, z2, , zk As there are more correct responses than incorrect ones, C can easily obtain error-free equation a x = z 21

II. HB* Protocol II. HB* Protocol HB+ Protocol HB+ Protocol HB+ by Juels and Weis Secure against active adversaries, i.e., adversary can pretend to be a reader. Tag (k-bit secret x and y , ) Reader (k-bit secret x and y; ) b R {0, 1}k b a R {0, 1}k {0, 1|Prob[ =1] = } a z = (a x) (b y) z Verify z = (a x) (b y) Repeat above step q times (possibly concurrently). Accept only if about q responses of Tag are incorrect HB+ also has incompleteness problem 22

II. HB* Protocol II. HB* Protocol GRS MIM Attack on HB+ GRS MIM Attack on HB+ HB+ is insecure against man-in-the-middle attack Tag (k-bit secret x, y; ) Reader (k-bit secret x, y) b R {0, 1}k b a R {0, 1}k a = a a .. {0, 1|Prob[ =1] = } z z = (a x) (b y) Check if z = (a x) (b y) If authentication succeeds, it is likely that (a x) (b y) = (a x) (b y) , but (a x) = (a ) x = (a x) ( x), therefore x = 0. Otherwise, x = 1 Attacker uses k linear independent s, it can calculate x using Gaussian elimination 23

II. HB* Protocol II. HB* Protocol HB* Protocol (1/4) HB* Protocol (1/4) HB-protocol family is one of the most interesting protocols for low-cost devices Very efficient (no hash, no block cipher) Security is based on a well-studied hard problem (LPN problem) In this thesis, I propose HB* A variant of HB+ secure against MIM attack. Can be used to exchange session key. 2-round (challenger-response) instead of 3-round in case of HB+ Twice the size of secret keys. 24

II. HB* Protocol II. HB* Protocol HB* Protocol (1/4) HB* Protocol (1/4) Why man-in-the-middle attack work on HB+ Binary inner-product is linear x is always associated with challenge a (and y with b) for no particular reason. My approach to prevent GRS MIM attack: Secretly swap the role of x and y when computing the response z. Introduce two new secret keys r and t to decide how the response z should be (secretly) computed and verified. 25

II. HB* Protocol II. HB* Protocol HB* Protocol (2/4) HB* Protocol (2/4) Tag (k-bit secret x, y, r, t) Reader (k-bit secret x, y, r, t) b R {0, 1}k R{0, 1} w' = (b t) a R {0, 1}k R{0, 1} w = (a r) a, w If = (a r) w Otherwise, z = (a x) (b y) b, w , z z = (b x) (a y) If = (b t) w Check if z = (a x) (b y) Otherwise, Check if z = (a y) (b x) Repeat above step q times Accept only if all responses from Tag are correct No noise applied to z 26

II. HB* Protocol II. HB* Protocol HB* Protocol (3/4) HB* Protocol (3/4) HB* is secure against generalized GRS man-in-the- middle attack if secret keys are chosen carefully Observe that, under assumption LPN is hard : Tag and Reader securely exchange two bits via (b, w ) and (a, w) Furthermore, (b, w) and (a, w ) come from single entity, therefore inherently secure against man-in-the-middle attack Original GRS attack does not work since, attacker does not know which secret keys (x or y) is associated with a. Observe that, attacker can only learn useful information about bits of x and y by modifying bits at the same position of a and b: Attacker learns useful information only when xi = yi = ri = ti = 0. We can prevent the attack by choosing secret keys so that the above case is avoided. 27

II. HB* Protocol II. HB* Protocol HB* Protocol (4/4) HB* Protocol (4/4) Comparison HB* can be used as an implicit key exchange protocol such that each round the tag and reader shares 1 secret bit ( ). 28

III. RFID and III. RFID and DoS DoS Attack Attack Privacy Privacy vs vs Performance Performance No privacy protection (Class-1 Gen-2 Spec) except kill tags Tag always backscatter its unique EPC number Good for performance: easy to look up the tag in DB Privacy protection (many protocols, not HB+ and HB*): Tag backscatters different EPC (pseudonym) for every session. Bad for performance: how to look up the tag if the EPC always change? 29

III. RFID and III. RFID and DoS DoS Attack Attack OSK Protocol OSK Protocol OSK Protocol Authentication Token = Hash(Current EPC) Next EPC = Hash(Current EPC) Server scan through the whole DB to identify a tag 30

III. RFID and III. RFID and DoS DoS Attack Attack O O- -FRAP and O FRAP and O- -RAP (1/4) RAP (1/4) Optimistic Behavior: Performance is optimal if there is no attack. Anonymity: Tag should use a randomly chosen Pseudonym for each authentication session. Pseudonym is used to index tag database (index is updated regularly) Forward-security: Refreshing secret key after every successful authentication session. But, this often leads to de-synchronization of secret Attacker can block/alternate the message so that only either tag or reader authenticates successfully. 31

III. RFID and III. RFID and DoS DoS Attack Attack O O- -FRAP and O FRAP and O- -RAP (2/4) RAP (2/4) How to defeat de-synchronization attack? Server keeps track of two versions of secret for each Tag {Kold, Kcurrent} In an authentication session, if Tag uses Kcurrent, Kold = Kcurrent Kcurrent = Knew If Tag uses Kold, then preserve Kold and let Kcurrent = Knew Why don t we update Kold = Kcurrent? Because attacker can prevent tag from updating its key for two successive sessions to cause de-synchronization. 32

III. RFID and III. RFID and DoS DoS Attack Attack O O- -FRAP and O FRAP and O- -RAP (3/4) RAP (3/4) O-FRAP Protocol Prevj = (Secret Key, Pseudonym) of Tag Tj in previous session Curj = (Secret Key, Pseudonym) of Tag Tj in current session 33

III. RFID and III. RFID and DoS DoS Attack Attack O O- -FRAP and O FRAP and O- -RAP (4/4) RAP (4/4) O-RAP Protocol (O-FRAP without updating secret key: no forward security) 34

III. RFID and DoS Attack III. RFID and DoS Attack DoS Attack on O DoS Attack on O- -RAP RAP Attacker can cause Server to search its whole database by sending any invalid pseudonym 35

III. RFID and III. RFID and DoS DoS Attack Attack O O- -RAP+ and O RAP+ and O- -FRAP+ (1/4) FRAP+ (1/4) Key idea: Two-phase authentication Reader authenticates tag s pseudonym first We can use a fixed key to this. The tag can also uses this key to verify the sever at first and updates its secret key and pseudonym (no more de-synchronization) Only tags pass this first round of verification can be passed to the server. Tags authenticated in the first round are then identified again at back-end server 36

III. RFID and III. RFID and DoS DoS Attack Attack O O- -RAP+ and O RAP+ and O- -FRAP+ (2/4) FRAP+ (2/4) O-RAP+ Protocol (O-FRAP+ without key updating) 37

III. RFID and III. RFID and DoS DoS Attack Attack O O- -RAP+ and O RAP+ and O- -FRAP+ (3/4) FRAP+ (3/4) Reducing O-FRAP+ and O-RAP+ to 3- round protocol: O-FRAP+ can be 3-round protocol: Tag initiates protocol first (sending tsys) but this is usually not case in practice. Indeed, the first message by server is usually a broadcast message, any tag in range will response with tsys Once a tag is isolated, reader can send rsys to start an authentication session. Therefore, O-FRAP+ and O-RAP+ are essentially a 3-round protocol. 38

III. RFID and III. RFID and DoS DoS Attack Attack O O- -RAP+ and O RAP+ and O- -FRAP+ (4/4) FRAP+ (4/4) Security: O-FRAP+ and O-FRAP+ are at least as secure as O-FRAP and O-RAP Comparison 39

IV. Grouping IV. Grouping- -Proof Protocol Proof Protocol Previous Protocols (1/6) Previous Protocols (1/6) Grouping-proof Protocols for RFID tags : Generate a proof that multiple tags are present at the time of scanning. For example, tags attached on different parts of a car should stay together. Previous protocols: Yoking-Proof and variants Timestamp-based Yoking-Proof Saitoh-Sakurai s Grouping-Proof 40

IV. Grouping IV. Grouping- -Proof Protocol Proof Protocol Previous Protocols (2/6) Previous Protocols (2/6) Yoking-Proof: Verifier (6) P Reader Tag T1 Tag T2 (1) left proof Choose r1at random (2) T1, r1 Choose r2at random m2 = MACK2[r1] (3) right proof , r1 (4) T2, r2, m2 (4) r2 m1 = MACK1[r2] (5) m1 P = (T1, r1, m1, T2, r2, m2) 41

IV. Grouping IV. Grouping- -Proof Protocol Proof Protocol Previous Protocols (3/6) Previous Protocols (3/6) Timestamp-based Yoking-Proof Verifier (1)TS (8) P Reader Tag T1 Tag T2 (2) TS Choose r1at random (3) T1, r1 Choose r2at random m2 = MACK2[TS, r1] (4) TS, r1 (5) T2, r2, m2 (6) r2 m1 = MACK1[TS, r2] (7) m1 P = (TS, T1, r1, m1, T2, r2, m2) 42

IV. Grouping IV. Grouping- -Proof Protocol Proof Protocol Previous Protocols (4/6) Previous Protocols (4/6) Piramuthu s protocol Verifier (7) P Tag T1 Tag T2 Reader Choose r at random (1) r Choose r1at random (2) T1, r1 (3) r, r1 Choose r2at random m2 = MACK2[r, r1] (4) T2, r2, m2 (5) m2 m1 = MACK1[r1, m2] (6) m1 P = (r, r1, r2, T1, m1, T2, m2) 43

IV. Grouping IV. Grouping- -Proof Protocol Proof Protocol Previous Protocols (5/6) Previous Protocols (5/6) Lin et. al s protocol Online Verifier (1) S = SKx[r, TS] (6) P Tag T1 Tag T2 Reader (2) S m1 = MACK1[S] (3) T1, m1 (4) S, m1 m2 = MACK2[S, m1] (5) T2, m2 P = (S, T1, m1, T2, m2) 44

IV. Grouping IV. Grouping- -Proof Protocol Proof Protocol Previous Protocols (6/6) Previous Protocols (6/6) Saitoh-Sakurai s Protocol Verifier (1) TS (6) P (2) TS Reader Tag Ti Pallet Tag (4)TS m1 mi = MACKi[TS] . . . mn CP = SKK[TS, m1, , mn] (3) mi (5) Ti, mi P = (TS, CP) 45

IV. Grouping IV. Grouping- -Proof Protocol Proof Protocol Security Issue Security Issue No security model for multiple tag scanning protocol so far. No security proof for previous protocols. Mafia Fraud Attack (Distance fraud) Tag T1 Attacker Tag T2 Reader Challeng e Relayed Challenge Respons e Challenge Relayed Response Response Communication range of the reader 46

IV. Grouping IV. Grouping- -Proof Protocol Proof Protocol Scalability Issue Scalability Issue Poor Scalability: Reader has to relay messages from one tag to another one. If there are n tags, a reader needs to replay at least n(n-1) messages. Saitoh s grouping-proof protocol requires an additional entity (pallet tag) and the reader needs to relay n messages to the pallet tag. 47

IV. Grouping IV. Grouping- -Proof Protocol Proof Protocol Security Definition (1/2) Security Definition (1/2) The goal of adversary: Inject/replace/remove a tag into/from a valid proof. But the tag is not actually in the communication range of the reader. An adversary is active: Access to both tag and reader oracle. Reader can be malicious: But it is trusted to execute the protocol correctly. Malicious readers may try to replace a tag in a proof with a different one before reporting the proof to the verifier. 48

IV. Grouping IV. Grouping- -Proof Protocol Proof Protocol Security Definition (2/2) Security Definition (2/2) Experiment for adding a tag into a valid proof: Setup. Adversary queries tag and reader oracles. Adversary can corrupt reader after a protocol session is terminated. Challenge: n tags (T1, T2, , Tn) and the corresponding valid co- existence proof . Adversary output (T*, *) such that T* is not among (T1, T2, , Tn) and * is a valid co-existence proof of n+1 tags (T*, T1, T2, , Tn) Adversary can add one tag to the original proof bur the tag not in the communication range of the reader. A grouping-proof protocol is said to be secure if the success probability of the adversary in the above experiment is negligible 49

IV. Grouping IV. Grouping- -Proof Protocol Proof Protocol Proposed Protocol (1/5) Proposed Protocol (1/5) (n, n)-secret sharing scheme: a dealer splits a secret x into n shared secrets: x can only be recovered if all of n shared secrets are provided. Applying to grouping-proof: Each tags signs a shared secret (not other tags random numbers to avoid relaying). If shared secrets can be used to recover a random challenge chosen by the verifier, then proof is verified. A (n, n) trivial secret sharing scheme: A dealer chooses (n-1) random numbers for first (n-1) shared secrets, y1, y2, , yn-1. The last shared secret yn = x y1 y2 yn-1. 50