Document Type: Original Research Paper


1 Department of Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran

2 Health Management and Economics Research Center, Iran University of Medical Sciences, Tehran, Iran

3 N. Bagheri Electrical Engineering Department, Shahid Rajaee Teacher Training University, Tehran, Iran Postal code: 16788-15811, Tel/fax:+98-21-2297006

4 Iran Telecom Research Center


Search protocols are among the main applications of RFID systems. Since a search protocol should be able to locate a certain tag among many tags, not only it should be secure against RFID threats but also it should be affordable. In this article, an RFID-based search protocol will be presented. We use an encryption technique that is referred to as authenticated encryption in order to boost the security level, which can provide confidentiality and integrity, simultaneously. Furthermore, since the proposed protocol belongs to the lightweight protocols category, it is appropriate for applications that require many tags and costs must be low. In terms of the security, the analysis results give a satisfactory security level and it is robust against different RFID threats like replay, traceability and impersonation attacks. Using Ouafi-Phan model, BAN and AVISPA, we also checked the security correctness of the suggested protocol.


Main Subjects

[1] N. Kumar, K. Kaur, S. C. Misra, and R. Iqbal, “An intelligent RFID-enabled authentication scheme for healthcare

applications in vehicular mobile cloud,” Peer-to-Peer Networking and Applications, vol. 9, no. 5, pp. 824–840, 2016.
[2] A. Tewari and B. Gupta, “Cryptanalysis of a novel ultra-lightweight mutual authentication protocol for IoT devices using RFID tags,” The Journal of Supercomputing, vol. 73, no. 3, pp. 1085–1102, 2017.
[3] X. Lin, H. Wang, Y. Kwok, B. Chen, M. Dai, and L. Zhang, “Exploiting the prefix information to enhance the performance of FSA-based RFID systems,” Computer Communications, vol. 56, pp. 108–118, 2015.
[4] D. Litian, W. Zizhong, and D. Fu, “An identification algorithm in grouping and paralleling for data-intensive RFID systems,” in Proc. International Conference on Big Data Computing and Communications, pp. 337–346, 2015.
[5] Y. C. Lai, L. Y. Hsiao, and B. S. Lin, “Optimal slot assignment for binary tracking tree protocol in RFID tag identification,” IEEE/ACM Transactions on Networking, vol. 23, no. 1, pp. 255–268, 2015.
[6] X. Yan, Y. Liu, B. Li, and X. Liu, “A memoryless binary query tree based successive scheme for passive RFID tag collision resolution,” Information Fusion, vol. 22, pp. 26–38, 2015.
[7] C. Jin, C. Xu, X. Zhang, and F. Li, “A secure ECC-based RFID mutual authentication protocol to enhance patient medication safety,” Journal of medical systems, vol. 40, no, 1, pp. 1-6, 2016.
[8] H. Niu, E. Taqieddin, and S. Jagannathan, “EPC GEN2v2 RFID standard authentication and ownership management protocol,” IEEE Transactions on Mobile Computing, vol. 15, no. 1, pp. 137–149, 2016.
[9] H. Chien, “SASI: A new ultralightweight RFID authentication protocol providing strong authentication and strong integrity,” IEEE Transactions on Dependable and Secure Computing, vol. 4, no. 4, pp. 337–340, 2007.
[10] J. Kang, “Lightweight mutual authentication RFID protocol for secure multi-tag simultaneous authentication in ubiquitous environments,” The Journal of Supercomputing, DOI:10.1007/s11227-016-1788-6, 2016.
[11] P. Lopez, J. Castro, J. Estévez-Tapiador, and A. Ribagorda, “LMAP: A real lightweight mutual authentication protocol for low-cost RFID tags,” in Proc. Workshop on RFID security, pp. 12–14, 2006.
[12] P. Lopez, J. Castro, J. Tapiador, and A. Ribagorda, “EMAP: An efficient mutual-authentication protocol for low-cost RFID tags,” in Proc. OTM Confederated International Conferences, OTM 2006 Workshops, pp. 352–361, 2006.
[13] K. Wang, C. Chen, W. Fang, and T. Wu, “On the security of a new ultra-lightweight authentication protocol in IoT environment for RFID tags,” The Journal of Supercomputing, vol. 74, no. 1, pp. 65-70, 2017.
[14] P. Arco and A. Santis, “On ultralight weight RFID authentication protocols,” IEEE Transactions on Dependable and Secure Computing, vol. 8, no. 4, pp. 548–563, 2011.
[15] G. Avoine, X. Carpent, and B. Martin, “Strong authentication and strong integrity (SASI) is not that strong,” in Proc. International Workshop on Radio Frequency Identification: Security and Privacy Issues, pp. 50–64, 2010.
[16] K. Fan, N. Ge, Y. Gong, H. Li, R. Su, and Y. Yang, “An ultra-lightweight RFID authentication scheme for mobile commerce,” Peer-to-Peer Networking and Applications, vol. 10, no. 2, pp. 368–376, 2016.
[17] D. L. Lin, S. Tsaur, and K. Chang, “Lightweight and serverless RFID authentication and search protocol,” in Proc. Second International Conference on Computer and Electrical Engineering, pp. 95–99, 2009.
[18] Q. U. Ain, U. Mujahid, and M. Najam-ul-islam, “Hardware implementation of ultralight weight cryptographic protocols,” presented at the 2015 International Conference on Computing,
Communication and Security (ICCCS), Pamplemousses, Mauritius, 2015.
[19] Y. Liao and C. Hsiao, “A secure ECC-based RFID authentication scheme integrated with id-verifier transfer protocol,” Ad Hoc Networks, vol. 18, pp. 133-146, 2014.
[20] B. Wang, M. Niset, Y. Ma, H. Nguyen, and R. Paul, “Scaling tunneling oxide to 50å in floating-gate logic NVM at 65nm and beyond,” in Proc. 2007 IEEE International Integrated Reliability Workshop Final Report, pp. 48–51, 2007.
[21] Y. Ki Lee, L. Batina, D. Singelée, and I. Verbauwhede, “Low-cost untraceable authentication protocols for RFID,” in Proc. of the third ACM conference on Wireless network security, pp. 55–64, 2010.
[22] C. Tan, B. Sheng, and Q. Li, “Secure and serverless RFID authentication and search protocols,” IEEE Transactions on Wireless Communications, vol. 7, no. 4, pp. 1400–1407, 2008.
[23] S. Dhal and I. Sengupta, “A new object searching protocol for multi-tag RFID,” Wireless Personal Communications, vol. 97, no. 3, pp. 3547-3568, 2017.
[24] M. Safkhani, P. Peris-Lopez, N. Bagheri, M. Naderi, and J. Castro, “On the security of tan et al. serverless RFID authentication and search protocols,” in Proc. International Workshop on Radio Frequency Identification: Security and Privacy Issues, pp. 1–19, 2013.
[25] Z. Kim, J. Kim, K. Kim, I. Choi, and T. Shon, “Untraceable and serverless RFID authentication and search protocols,” in Proc. 2011 IEEE Ninth International Symposium on Parallel and Distributed Processing with Applications Workshops, pp. 278–283, 2011.
[26] M. Hoque, F. Rahman, S. Ahamed, and J. Park, “Enhancing privacy and security of RFID system with serverless authentication and search protocols in pervasive environments,” Wireless Personal Communications, vol. 55, no. 1, pp. 65–79, 2010.
[27] Y. Zuo, “Secure and private search protocols for RFID systems,” Information Systems Frontiers, vol. 12, no. 5, pp. 507–519, 2010.
[28] X. Yin and W. Li, “LP0: A RFID authentication protocol for low-cost tags without back-end database,” presented at 2012 International Conference on Computer Distributed Control and Intelligent Environmental Monitoring, Hunan, China, 2012.
[29] L. Kulseng, Z. Yu, Y. Wei, and Y. Guan, “Lightweight secure search protocols for low-cost RFID systems,” presented at the 2009 29th IEEE International Conference on Distributed Computing Systems, Montreal, Canada, 2009.
[30] C. Lv, H. Li, J. Ma, and B. Niu, “Vulnerability analysis of lightweight secure search protocols for low-cost RFID systems,” International Journal of Radio Frequency Identification Technology and Applications, vol. 4, no. 1, pp. 3–12, 2012.
[31] H. Jialiang, X. Youjun, and X. Zhiqiang, “Secure and private protocols for server-less RFID systems,” International Journal of Control and Automation, vol. 7, no. 2, pp. 131–142, 2014.
[32] S. Sundaresan, R. Doss, and W. Zhou, “A serverless ultra-lightweight secure search protocol for EPC class-1 GEN-2 UHF RFID tags,” in Proc. 2012 International Conference on Computer & Information Science (ICCIS), vol. 2, pp. 580–585, 2012.
[33] H. Yoon and H. Youm, “An anonymous search protocol for RFID systems,” Journal of Convergence Information Technology, vol. 6, no. 8, pp. 44-50, 2011.
[34] T. Won, J. Chun, and D. Lee, “Strong authentication protocol for secure RFID tag search without help of central database,” in Proc. 2008 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, vol. 2, pp. 153–158, 2008.
[35] W. Xie, L. Xie, C. Zhang, Q. Wang, J. Xu, Q. Zhang, and C. Tang, “RFID seeking: Finding a lost tag rather than only detecting its missing,” Journal of Network and Computer Applications, vol. 42, pp. 135–142, 2014.

[36] S. Jeon and E. Yoon, “An ultra-lightweight RFID seeking protocol for low-cost tags,” Applied Mathematical Sciences, vol. 8, no. 125, pp. 6245–6255, 2014.

[37] C. Mtita, M. Laurent, and J. Delort, “Efficient serverless radiofrequency identification mutual authentication and secure tag search protocols with untrusted readers,” IET Information Security, vol. 10, no. 5, pp. 262–271, 2016.

[38] S. Sundaresan, R. Doss, S. Piramuthu, and W. Zhou, “Secure tag search in RFID systems using mobile readers,” IEEE Transactions on Dependable and Secure Computing, vol. 12, no. 2, pp. 230–242, 2015.

[39] M. Eslamnezhad Namin, M. Hosseinzadeh, N. Bagheri, and A. Khademzadeh, “A secure search protocol for lightweight and low-cost RFID systems,” Telecommunication Systems, vol. 67, no. 4, pp. 539–552, 2018.

[40] S. Sundaresan, R. Doss, S. Piramuthu, and W. Zhou, “A secure search protocol for low cost passive RFID tags,” Computer Networks, vol. 122, pp. 70–82, 2017.

[41] L. Bolotnyy and G. Robins, “Physically unclonable functionbased security and privacy in RFID systems,” presented at the Fifth Annual IEEE International Conference on Pervasive Computing and Communications (PerCom'07), White Plains, NY, USA, 2007.

[42] C. Mtita, M. Laurent, D. Sauveron, R. Akram, K. Markantonakis, and S. Chaumette, “Serverless protocols for inventory and tracking with a UAV,” in Proc. 2017 IEEE/AIAA 36th Digital Avionics Systems Conference (DASC), pp. 1–11, 2017.

[43] Y. Li, J. XIE, and Z. MAO, “Secure RFID system based on des encrypt algorithm,” Modern Electronics Technique, Available: 200901028. html.

[44] M. Feldhofer, S. Dominikus, and J. Wolkerstorfer, “Strong authentication for RFID systems using the AES algorithm,” in Proc. International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2004), pp. 357–370, 2004. [45] T. Pham, M. Hasan, and H. Yu, “A RFID mutual authentication protocol based on AES algorithm,” in Proc. 2012 UKACC International Conference on Control, pp. 997–1002. IEEE, 2012.

[46] R. Doss, W. Zhou, and S. Yu, “Secure RFID tag ownership transfer based on quadratic residues,” IEEE Transactions on Information Forensics and Security, vol. 8, no. 2, pp. 390–401, 2013.

[47] Y. Huang, C. Yuan, M. Chen, W. Lin, and H. Teng, “Hardware implementation of RFID mutual authentication protocol,” IEEE Transactions on Industrial Electronics, vol. 57, no. 5, pp. 1573– 1582, 2010.

[48] L. Batina, J. Guajardo, T. Kerins, N. Mentens, P. Tuyls, and I. Verbauwhede, “An elliptic curve processor suitable for RFIDtags," in Proc. 1st Benelux Workshop on Information and System Security, pp. 1-17, 2006.

[49] A. Juels and S. Weis, “Authenticating pervasive devices with human protocols,” in Proc. Annual International Cryptology Conference, pp. 293–308, 2005.

[50] Y. Ki Lee, K. Sakiyama, L. Batina, and I. Verbauwhede, “Ellipticcurve-based security processor for RFID,” IEEE Transactions on Computers, vol. 57, no. 11, pp. 1514–1527, 2008.

[51] P. Urien and S. Piramuthu, “Elliptic curve-based RFID/NFC authentication with temperature sensor input for relay attacks,” Decision Support Systems, vol. 59, pp. 28–36, 2014.

[52] Y. Liao and C. Hsiao, “A secure ECC-based RFID authentication scheme integrated with id-verifier transfer protocol,” Ad Hoc Networks, vol. 18, pp. 133–146, 2014.

[53] M. Feldhofer and C. Rechberger, “A case against currently used hash functions in RFID protocols,” in Proc. In OTM Confederated International Conferences, pp. 372–381, 2006.

[54] M. Bellare and C. Namprempre, “Authenticated encryption: Relations among notions and analysis of the generic composition paradigm,” in Proc. International Conference on the Theory and Application of Cryptology and Information Security, pp. 531–545, 2000.

[55] A. Adomnicai, J. Fournier, and L. Masson, “Masking the lightweight authenticated ciphers acorn and ASCON in software,” Cryptography and Information Security in the Balkans, Available:, 2018. [56] H. Groß, E. Wenger, C. Dobraunig, and C. Ehrenhöfer, “Suit up!– made-to-measure hardware implementations of ASCON,” in Proc. 2015 Euromicro Conference on Digital System Design, pp. 645–652, 2015.

[57] G. Zhou, H. Michalik, and L. Hinsenkamp, “Efficient and highthroughput implementations of AES-GCM on FPGAs,” in Proc. 2007 International Conference on Field-Programmable Technology, pp. 185–192, 2007.

[58] M. Dworkin, “Recommendation for block cipher modes of operation: The CCM mode for authentication and confidentiality,” National Institute of Standards and Technology, U.S. department of commerce, Technical report, 2004. [59] D. McGrew and J. Viega, “The security and performance of the galois/counter mode (GCM) of operation,” in Proc. International Conference on Cryptology in India, pp. 343–355, 2004.

[60] S. Cogliani, D. Maimuţ, D. Naccache, R. Canto, R. Reyhanitabar, S. Vaudenay, and D. Vizár, “OMD: A compression function mode of operation for authenticated encryption,” in Proc. International Conference on Selected Areas in Cryptography, pp. 112–128, 2014.

[61] Y. Niwa, K. Ohashi, K. Minematsu, and T. Iwata, “CM security bounds reconsidered,” in Proc. International Workshop on Fast Software Encryption, pp. 385–407, 2015.

[62] P. Rogaway and T. Shrimpton, “A provable-security treatment of the key-wrap problem,” in Proc. Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 373–390, 2006.

[63] M. Saarinen, “Cycling attacks on GCM, GHASH and other polynomial macs and hashes,” in Proc. International Workshop on Fast Software Encryption, pp. 216–225, 2012.

[64] S. Neves J. Aumasson, and P. Jovanovic, “NORX V2.0,” Available: https://competitions .pdf /, 2015.

[65] H. Wu, “ACORN: A lightweight authenticated cipher,” Available:, 2015.

[66] C. Dobraunig, M. Eichlseder, F. Mendel, and M. Schläffer, “ASCON v1. 2,” Submission to the CAESAR Competition, Available: round3/asconv12. pdf, 2016.

[67] T. Peyrin, J. Jean, and I. Nikolic. 2015, Joltik v1.3, CAESAR Round 2 submission, Available: /round2/joltikv13.pdf

[68] J. Guo, T. Peyrin, and A. Poschmann, “The photon family of lightweight hash functions,” in Proc. Advances in Cryptology (CRYPTO 2011), pp. 222–239, 2011.

[69] G. Leander, C. Paar, A. Poschmann, and K. Schramm, “New lightweight DES variants,” in Proc. International Workshop on Fast Software Encryption, pp. 196–210, 2007.

[70] K. Ouafi and R. Phan, “Privacy of recent RFID authentication protocols,” in Proc. International Conference on Information Security Practice and Experience, pp. 263–277, 2008.

[71] S. Mandal, S. Mohanty, and B. Majhi, “Universally verifiable certificateless signcryption scheme for MANET,” in Proc. International Conference on Microelectronics, Computing & Communication Systems, pp. 77–89, 2018.

[72] Y. Boichut, P. Héam, and O. Kouchnarenko, “Automatic approximation for the verification of cryptographic protocols,” in Proc. AVIS, 2004.

[73] D. Basin, S. Mödersheim, and L. Vigano, “OFMC: A symbolic model checker for security protocols,” International Journal of Information Security, vol. 4, no. 3, pp. 181–208, 2005.

[74] A. Armando and L. Compagna, “An optimized intruder model for SAT-based model-checking of security protocols,” Electronic Notes in Theoretical Computer Science, vol. 125, no. 1, pp. 91–108, 2005.

[75] M. Turuani, “The CL-ATSE protocol analyzer,” in Proc. International Conference on Rewriting Techniques and Applications, pp. 277–286, 2006.

[76] M. Burrows, M. Abadi, and R. M Needham, “A logic of authentication,” in Proc. Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 426, pp. 233–271, 1989.

[77] H. Martn, E. Millán, L. Entrena, P. Lopez, and J. Castro, “AKARIx: a pseudorandom number generator for secure lightweight systems,” presented at the 2011 IEEE 17th International OnLine Testing, Athens, Greece, 2011.

[78] S. Sundaresan, R. Doss, S. Piramuthu, and W. Zhou, “Secure tag search in RFID systems using mobile readers,” IEEE Transactions on Dependable and Secure Computing, vol. 12, no. 2, PP. 230-242, 2014.

[79] R. Wessel, “Airbus signs contract for high-memory RFID tags,” RFID Journal, pp. 1-2, Available: https://www. rfidjournal. com / articles/pdf?7323, 2010.

[80] D. Dressen, “Large memory RFID system solutions,” ATMEL Applications Journal, pp. 48–49, Available:, 2011.

[81] M. Hossain and S. Ahamed, “Towards a simple secured searching protocol for future RFID applications,” presented at the 12th IEEE International Workshop on Future Trends of Distributed Computing Systems, Kunming, China, 2008.

[82] J. Chun, J. Hwang, and D. Hoon Lee, “RFID tag search protocol preserving privacy of mobile reader holders,” IEICE Electronics Express, vol. 8, no. 2, pp. 50–56, 2011.