編碼密碼與計算理論實驗室

1、編碼密碼與計算理論實驗室1An Efficient Forward Private RFID ProtocolCme Berbain, Olivier Billet, Jonathan Etrog, and Henri GilbertACM CCS 2009編碼密碼與計算理論實驗室2Outlineo Abstracto Introductiono Assumptions on the authentication protocolo Forward privacyo Forward Private scheme - the OSK protocolo A Forward Private Pro

2、tocol Without Hash Functions: PFPo Conclusiono References編碼密碼與計算理論實驗室3Abstracto Ohkubo, Suzuki, and Kinoshita first proposed an appealing RFID protocol that meets the highest privacy requirements.o OSKs scheme suffer from limitations in terms of computational complexity and provable securityo Author

3、s propose a novel forward private authentication scheme built upon less computationally expensive cryptographic ingredientsIntroductiono a protocol that allows to identify a tag but does not prevent impersonation is named an RFID identification protocolo a protocol that allows both identifying and a

4、uthenticating a tag is named an RFID authentication protocolo The needs for authentication and privacy coexist in many applications, e.g. transportation tickets編碼密碼與計算理論實驗室4Introductiono To prevent a tag that has been tampered with the attacker, the authors rely on two one-way functions:1. update th

5、e internal state of the tag2. produce an identification value that does not allow a passive attacker to recover the internal state of the tag編碼密碼與計算理論實驗室5Assumptions on the authentication protocol1. Each tag Ti has a secret internal state initialised with a secret Ki, this secret is also known from

6、the back-end system2. the secrets Ki of the tags are uncorrelated3. a tag cannot handle several authentication exchanges simultaneously編碼密碼與計算理論實驗室6Forward privacyo First phase1. an adversary A interacts with any two legitimate tags Ti0 and Ti1 , and a legitimate reader2. A is allowed to observe and

7、 disturb at most q authentication exchanges involving Ti0 (Ti1) and (possibly) the reader編碼密碼與計算理論實驗室7Forward privacyo Second phase1. A again interacts with a tag Tib randomly selected among the two tags Ti0 and Ti1 , (b is concealed to A)2. A is allowed to observe and disturb at most q additional a

8、uthentication exchanges involving Tib3. A is given access to the corresponding authentication outcome編碼密碼與計算理論實驗室8Forward privacy4. Then, A is given access to the internal state value of Tib5. Eventually, A outputs a guess b0 for the value of b, and succeeds if b0 = bo An RFID authentication protoco

9、l is said private iff a adversary A has an advantage at most :編碼密碼與計算理論實驗室9Forward Private scheme- the OSK protocolo each tag embeds an internal state i, which has a secret initialized state 0 stored by the back-end systems1. When an identification request is received, the tag sends H2(i) to the rea

10、der2. the tag updates its internal state by using H1: i+1 = H1(i)編碼密碼與計算理論實驗室10Forward Private scheme- the OSK protocolo To recover the identity of a tag, the system computes the hash functions H1 and H2 at most times until the received value is found or the limit is reached編碼密碼與計算理論實驗室11Forward Pri

11、vate scheme- the OSK protocolo OSKs drawbacks1. Cryptographic hash functions cannot be efficiently implemented in hardware2. an adversary can invalidate a tag by sending + 1 random queries3. does not prevent from replay attacks, i.e, only provides identication and not authentication編碼密碼與計算理論實驗室12A F

12、orward Private Protocol Without Hash Functions: PFP o PFP: an efficient and Provably Forward Private authentication scheme for RFIDso update the internal state of the tags which is much more efficient1. rely on a PRNG to refresh the internal state of the tag with some part of the sequence2. use anot

13、her part for the purpose of authentication編碼密碼與計算理論實驗室13A Forward Private Protocol Without Hash Functions: PFPo a pseudo-random number generator g : 0,1n 0,1n+ko a universal hash functions familyo g1: the partial function that maps gs input to gs n first output bitso g2: the partial function that ma

14、ps gs input to gs k last output bitso g(x) = (g1(x), g2(x) for any input x of g編碼密碼與計算理論實驗室14A Forward Private Protocol Without Hash Functions: PFPo Every tag has its internal state setup with a randomly chosen secret seed 0 = x representing its identity編碼密碼與計算理論實驗室15A Forward Private Protocol Witho

15、ut Hash Functions: PFP1. a tag receives an authentication challenge from a reader2. the tag derives two values i+1 = g1(i) and s = g2(i) from the expansion of its internal state through g3. the tag authenticates to the reader by replying c = hs(a)編碼密碼與計算理論實驗室16A Forward Private Protocol Without Hash

16、 Functions: PFP4. the reader verifies c by searching its chainsn for each tag T in the system, the reader fetches the last known staten and runs through the set of possible values編碼密碼與計算理論實驗室17A Forward Private Protocol Without Hash Functions: PFP5. the outcome of the protocol is b = 1 (success): if

17、 a match is found for the tag T with last known staten the identified tag is Tn the new last known state for T becomes6. otherwise the outcome is b = 0 (failure)編碼密碼與計算理論實驗室18Conclusiono provide a privacy RFID authentication protocol supported by strong provable security argumentso PFP combined a st

18、rongly (or almost strongly) universal hash functions family and a computationally secure component such as a pseudo-random number generator編碼密碼與計算理論實驗室19編碼密碼與計算理論實驗室20Referenceso1 D. Arditti, C. Berbain, O. Billet, and H. Gilbert. Compact FPGA implementations of QUAD. In F. Bao and S. Miller, editor

19、s, ASIACCS 2007. ACM, 2007.o2 Auto-ID Center. 860MHz 960MHz Class I Radio Frequency Identication Tag Radio Frequency& Logical Communication Interface Specication, v1.0.0. Research Report MIT-AUTOID-TR-007, 2002.o3 G. Avoine. Privacy Issues in RFID Banknote Protection Schemes. In J.-J. Quisquater

20、, P. Paradinas, Y. Deswarte, and A. Abou El Kadam, editors, CARDIS 2004, pages 3348. Kluwer, 2004.o4 G. Avoine. Adversarial model for radio frequency identication. Cryptology ePrint Archive, Report 2005/049, /, 2005.o5 G. Avoine, E. Dysli, and P. Oechslin. Reducing Time Complexi

21、ty in RFID Systems. In B. Preneel and S. Tavares, editors, SAC 2005, LNCS. Springer, 2005.o6 G. Avoine and P. Oechslin. A Scalable and Provably Secure Hash Based RFID Protocol. In PerSec 2005. IEEE Computer Society Press, 2005.o7 G. Avoine and P. Oechslin. RFID traceability: A multilayer problem. In

22、 A. Patrick and M. Yung, editors, FC05, LNCS. Springer, 2005.o8 C. Berbain, H. Gilbert, and J. Patarin. QUAD: A Practical Stream Cipher with Provable Security. In S. Vaudenay, editor, EUROCRYPT 2006, LNCS. Springer, 2006.o9 S. Canard and I. Coisel. Data Synchronization in Privacy-Preserving RFID Aut

23、hentication Schemes. In Conference on RFID Security, 2008.o10 CASPIAN. http:/.o11 I. Damgard and M. stergaard. RFID Security: Tradeos between Security and Eciency. Cryptology ePrint Archive, Report 2006/234, 2006.o12 T. Dimitriou. A Lightweight RFID Protocol to protect against Traceability and Cloni

24、ng attacks. In SECURECOMM 05. IEEE Computer Society, 2005.編碼密碼與計算理論實驗室21Referenceso13 ECRYPT. The eSTREAM Project, 2008. /stream/index.html.o14 Electronic Product Code Global Inc. http:/.o15 M. Feldhofer and C. Rechberger. A Case Against Currently Used Hash Functions in RFID P

25、rotocols. In R. Meersman, Z. Tari, and P. Herrero, editors, OTM 2006, volume 4277 of LNCS. Springer, 2006.o16 T. Good and M. Benaissa. Asic hardware performance. In M. Robshaw and O. Billet, editors, New Stream Cipher Designs, LNCS, pages 267293. Springer, 2008.o17 M. Hellman. A Cryptanalytic Time-M

26、emory Trade-O. IEEE Transactions on Information Theory, 26(4):401406, July 1980.o18 J. E. Hennig, P. B. Ladkin, and B. Sieker. Privacy Enhancing Technology Concepts for RFID Technology Scrutinised. RVS-RR-04-02, Univ. of Bielefeld, 2004.o19 D. Henrici and P. Muller. Hash-based Enhancement of Locatio

27、n Privacy for Radio-Frequency Identication Devices using Varying Identiers. In Pervasive Computing and Communications Workshops, 2004.o20 International Organisation for Standardisation. .o21 A. Juels. Minimalist Cryptography for Low-Cost RFID Tags. In SCN 2004, LNCS. Springer, 2004.

28、o22 A. Juels and R. Pappu. Squealing Euros: Privacy Protection in RFID-Enabled Banknotes. In R. N. Wright, editor, FC 03, LNCS. Springer, 2003.o23 A. Juels, R. Rivest, and M. Szydlo. The Blocker Tag: Selective Blocking of RFID Tags for Consumer Privacy. In V. Atluri, editor, ACM CCS, 2003.o24 A. Jue

29、ls and S. Weis. Dening strong privacy for RFID. Cryptology ePrint Archive, Report 2006/137.Referenceso25 Y. Mansour, N. Nisan, and P. Tiwari. The computational complexity of universal hashing. In STOC 90, pages 235243. ACM, 1990.o26 D. Molnar and D. Wagner. Privacy and security in library RFID: Issu

30、es, practices, and architectures. In B. Ptzmann and P. Liu, editors, ACM CCS, pages 210219. ACM Press, 2004.o27 P. Oechslin. Making a faster cryptanalytic time-memory trade-o. In D. Boneh, editor, CRYPTO 2003, volume 2729 of LNCS. Springer, 2003.o28 O.Goldreich and L.Levin. A hard-core predicate for all one way-functions.