Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2014 | OriginalPaper | Chapter

Lightweight Authentication Protocols on Ultra-Constrained RFIDs - Myths and Facts

Authors : Frederik Armknecht, Matthias Hamann, Vasily Mikhalev

Published in: Radio Frequency Identification: Security and Privacy Issues

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

While most lightweight authentication protocols have been well analyzed with respect to their security, often only little (or even nothing) is known with respect to their suitability for low-cost RFIDs in the range of $0.05 to $0.10. Probably this is mainly due to the fact that open literature rarely provides information on what conditions need to be met by a scheme in practice, hindering a sound development and analysis of schemes.
We provide a comprehensive collection of several conditions that should be met by lightweight authentication schemes if deployed in low-cost RFID systems. Afterwards, we show that none of the existing authentication protocols that are based on the hardness of the Learning Parity with Noise (LPN) problem complies to these conditions, leaving the design of an LPN-based protocol for low-cost RFIDs as an open question.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
next chapter High-Speed Dating Privacy-Preserving Attribute Matching for RFID
Appendix
Available only for authorised users
Footnotes
1
In [6], it is stated that “in accordance with C1G2, a maximum tag to reader data transmission rate of 640 kbps and a reader to tag data transmission rate of 126 kbps based on equi-probable binary ones and zeros in the transmission can be calculated” and that “performance criteria of an RFID system demand a minimum label reading speed in excess of 200 labels per second”.
 
2
In [2], a 0.13 \({\upmu }\)m CMOS process is used. For comparison, the AES implementation in [8] is based on a 0.35 \({\upmu }\)m CMOS process and occupies 0.25 mm\(^2\), which “compares roughly to 3400 gate equivalents” in this context.
 
3
For the sake of simplicity, in this subsection, the term key will always be used to refer to the shared secret’s unique representation as a binary vector in the corresponding scheme, irrespective of potential blow-up measures like, e.g., the use of Toeplitz matrices. In particular, the key size lower bounds the size of the individual key storage required on each tag.
 
4
At the current state, Lapin was omitted from the table in Appendix B as, according to its authors, it is actually “targeting lightweight tags that are equipped with (small) CPUs” as compared to “ultra constrained tokens (such as RFIDs in the price range of few cents targeting the EPC market)” [17]. (See also [11] for a very recent suggestion of an FPGA implementation for Lapin, which, however, is still not feasible when transferred to low-cost ASICs. Again, the details of this will be discussed in the full version of the paper.)
 
Literature
1.
Abyaneh, M.R.S.: On the security of non-linear HB (NLHB) protocol against passive attack. In: 2010 IEEE/IFIP 8th International Conference on Embedded and Ubiquitous Computing (EUC), pp. 523–528. IEEE (2010)
2.
Balachandran, G.K., Barnett, R.E.: A 440-nA true random number generator for passive RFID tags. IEEE Trans. Circ. Syst. I: Regular Pap. 55(11), 3723–3732 (2008)CrossRefMathSciNet
3.
Bosley, C., Haralambiev, K., Nicolosi, A.: HB\(^{N}\): An HB-like protocol secure against man-in-the-middle attacks. IACR Cryptology ePrint Archive 2011, p. 350 (2011)
4.
Bringer, J., Chabanne, H.:. Trusted-HB: A low-cost version of HB\(^{+}\) secure against man-in-the-middle attacks. arXiv preprint (2008). arXiv:​0802.​0603
5.
Bringer, J., Chabanne, H., Dottax, E.: HB\(^{++}\): A lightweight authentication protocol secure against some attacks. In: Second International Workshop on Security, Privacy and Trust in Pervasive and Ubiquitous Computing, 2006, SecPerU 2006, pp. 28–33. IEEE (2006)
6.
Cole, P.H., Ranasinghe, D.C.: Networked RFID Systems and Lightweight Cryptography: Raising Barriers to Product Counterfeiting, 1st edn. Springer, Berlin Heidelberg (2008)CrossRef
7.
Duc, D.N., Kim, K.: Securing HB\(^{+}\) against GRS man-in-the-middle attack. In: Institute of Electronics, Information and Communication Engineers, Symposium on Cryptography and Information Security (2007)
8.
Feldhofer, M., Wolkerstorfer, J., Rijmen, V.: AES implementation on a grain of sand. IEE Proc.: Inf. Secur. 152(1), 13–20 (2005)CrossRef
9.
Feldhofer, M., Dominikus, S., Wolkerstorfer, J.: Strong authentication for RFID systems using the AES algorithm. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 357–370. Springer, Heidelberg (2004)CrossRef
10.
Frumkin, D., Shamir, A.: Untrusted-HB: Security vulnerabilities of Trusted-HB. Cryptology ePrint Archive, Report 2009/044 (2009)
11.
Gaspar, L., Leurent, G., Standaert, F.-X.: Hardware implementation and side-channel analysis of lapin. In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 206–226. Springer, Heidelberg (2014)CrossRef
12.
Gilbert, H., Robshaw, M., Sibert, H.: Active attack against \(\text{ HB }^+\): A provably secure lightweight authentication protocol. Electron. Lett. 41(21), 1169–1170 (2005)CrossRef
13.
Gilbert, H., Robshaw, M., Seurin, Y.: Good variants of HB\(^ \text{+ } \) are hard to find. In: Tsudik, G. (ed.) FC 2008. LNCS, vol. 5143, pp. 156–170. Springer, Heidelberg (2008)CrossRef
14.
Gilbert, H., Robshaw, M., Seurin, Y.: https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-13066-8_1/MediaObjects/332001_1_En_1_Figb_HTML.gif : Increasing the security and efficiency of HB\(^{+}\). In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 361–378. Springer, Heidelberg (2008) CrossRef
15.
Gold, R.: Maximal recursive sequences with 3-valued recursive cross-correlation functions (corresp.). IEEE Trans. Inf. Theory 14(1), 154–156 (1968)CrossRefMATH
16.
Hammouri, G., Sunar, B.: PUF-HB: A tamper-resilient HB based authentication protocol. In: Bellovin, S.M., Gennaro, R., Keromytis, A.D., Yung, M. (eds.) ACNS 2008. LNCS, vol. 5037, pp. 346–365. Springer, Heidelberg (2008)CrossRef
17.
Heyse, S., Kiltz, E., Lyubashevsky, V., Paar, C., Pietrzak, K.: Lapin: An efficient authentication protocol based on Ring-LPN. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 346–365. Springer, Heidelberg (2012)CrossRef
18.
Hopper, N.J., Blum, M.: Secure human identification protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 52–66. Springer, Heidelberg (2001)CrossRef
19.
20.
Juels, A., Weis, S.A.: Authenticating pervasive devices with human protocols. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 293–308. Springer, Heidelberg (2005)CrossRef
21.
Katz, J., Shin, J.S.: Parallel and concurrent security of the HB and HB\(^{+}\) protocols. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 73–87. Springer, Heidelberg (2006)CrossRef
22.
Katz, J., Shin, J.S., Smith, A.: Parallel and concurrent security of the HB and HB\(^{+}\) protocols. J. Cryptol. 23(3), 402–421 (2010)CrossRefMATHMathSciNet
23.
Kiltz, E., Pietrzak, K., Cash, D., Jain, A., Venturi, D.: Efficient authentication from hard learning problems. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 7–26. Springer, Heidelberg (2011)CrossRef
24.
Krawczyk, H.: LFSR-based hashing and authentication. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 129–139. Springer, Heidelberg (1994)
25.
Leng, X., Mayes, K., Markantonakis, K.: HB-MP\(^{+}\) protocol: An improvement on the HB-MP protocol. In: 2008 IEEE International Conference on RFID, pp. 118–124. IEEE (2008)
26.
Levieil, É., Fouque, P.-A.: An improved LPN algorithm. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 348–359. Springer, Heidelberg (2006)CrossRef
27.
Madhavan, M., Thangaraj, A., Sankarasubramanian, Y., Viswanathan, K.: NLHB: A non-linear Hopper-Blum protocol. In: 2010 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 2498–2502. IEEE (2010)
28.
Martin, H., Millán, E.S., Entrena, L., Castro, J.C.H., Peris-Lopez, P.: AKARI-X: A pseudorandom number generator for secure lightweight systems. In: IOLTS, pp. 228–233 (2011)
29.
Melià-Seguí, J., Garcia-Alfaro, J., Herrera-Joancomartí, J.: J3Gen: A PRNG for low-cost passive RFID. Sensors 13(3), 3816–3830 (2013)CrossRef
30.
Munilla, J., Peinado, A.: HB-MP: A further step in the HB-family of lightweight authentication protocols. Comput. Netw. 51(9), 2262–2267 (2007)CrossRefMATH
31.
Ouafi, K., Overbeck, R., Vaudenay, S.: On the security of https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-13066-8_1/MediaObjects/332001_1_En_1_Figc_HTML.gif against a man-in-the-middle attack. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 108–124. Springer, Heidelberg (2008)CrossRef
32.
Peris-Lopez, P., Hernandez-Castro, J.C., Estevez-Tapiador, J.M., Ribagorda, A.: LAMED - A PRNG for EPC Class-1 generation-2 RFID specification. Comput. Stand. Interfaces 31(1), 88–97 (2009)CrossRef
33.
34.
Piramuthu, S., TU, Y.-J.: Modified HB authentication protocol. In: WEWoRC, pp. 41–44 (2007)
35.
Poschmann, A.: Lightweight cryptography: Cryptographic engineering for a pervasive world (2009)
36.
Poschmann, A., Moradi, A., Khoo, K., Lim, C., Wang, H., Ling, S.: Side-channel resistant crypto for less than 2,300 GE. J. Cryptol. 24(2), 322–345 (2011)CrossRefMATHMathSciNet
37.
Ranasinghe, D.C., Engels, D.W., Cole, P.H.: Low-cost RFID systems: Confronting security and privacy. In: Auto-ID Labs Research Workshop, Portal (2005)
38.
39.
Rizomiliotis, P., Gritzalis, S.: https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-13066-8_1/MediaObjects/332001_1_En_1_Figd_HTML.gif : A provably secure HB-like lightweight authentication protocol. In: Bao, F., Samarati, P., Zhou, J. (eds.) ACNS 2012. LNCS, vol. 7341, pp. 489–506. Springer, Heidelberg (2012)CrossRef
40.
Rizomiliotis, P.: HB \(-\) MAC: Improving the Random \(-\) https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-13066-8_1/MediaObjects/332001_1_En_1_Fige_HTML.gif authentication protocol. In: Fischer-Hübner, S., Lambrinoudakis, C., Pernul, G. (eds.) TrustBus 2009. LNCS, vol. 5695, pp. 159–168. Springer, Heidelberg (2009) CrossRef
41.
Rolfes, C., Poschmann, A., Leander, G., Paar, C.: Ultra-lightweight implementations for smart devices – Security for 1000 gate equivalents. In: Grimaud, G., Standaert, F.-X. (eds.) CARDIS 2008. LNCS, vol. 5189, pp. 89–103. Springer, Heidelberg (2008)CrossRef
42.
Saarinen, M.-J.O., Engels, D.W.: A do-it-all-cipher for RFID: Design requirements (extended abstract). IACR Cryptology ePrint Archive, 2012, p. 317 (2012) (informal publication)
43.
Song, X., Kobara, K., Imafuku, K., Imai, H.: HB\(^{b}\) protocol for lightweight authentication; Its information theoretic indistinguishability against MITM attack watching reader’s response. In: 2012 International Symposium on Information Theory and its Applications (ISITA), pp. 536–540. IEEE (2012)
44.
Susini, J., Chabanne, H., Urien, P.: RFID and the Internet of Things, p. 304. ISTE - Wiley, London (2011)
45.
Tokunaga, C., Blaauw, D., Mudge, T.: True random number generator with a metastability-based quality control. In: Solid-State Circuits Conference, 2007, ISSCC 2007. Digest of Technical Papers. IEEE International, pp. 404–611, Feb 2007
46.
Wu, W., Zhang, L.: LBlock: A lightweight block cipher. In: Lopez, J., Tsudik, G. (eds.) ACNS 2011. LNCS, vol. 6715, pp. 327–344. Springer, Heidelberg (2011)CrossRef
Metadata
Title
Lightweight Authentication Protocols on Ultra-Constrained RFIDs - Myths and Facts
Authors
Frederik Armknecht
Matthias Hamann
Vasily Mikhalev
Copyright Year
2014
Book
Radio Frequency Identification: Security and Privacy Issues

Print ISBN: 978-3-319-13065-1

Electronic ISBN: 978-3-319-13066-8

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-13066-8_1

Premium Partner

    Image Credits