Probabilistic Recursive Cryptanalysis of Ultralightweight Mutual Authentication Protocols for Passive RFID Systems

Umar Mujahid, M. Najam-ul-islam


Security and privacy are the fundamental concerns of RFID systems. Several ultralightweight mutual authentication protocols have been proposed to ensure the security of RFID systems in cost effective manner. These protocols usually involve simple bitwise logical operations such as XOR, AND, OR and some special purpose ultralightweight primitives. In this paper, we identify the vulnerabilities of the two recently proposed ultralightweight mutual authentication protocols: SASI and Yeh. et al. We have used Recursive Linear Cryptanalysis (RLC) for security analysis of SASI protocol, which requires only two authentication sessions to reveal concealed secret ID of the tags. For Yeh et al. protocol, we have proposed an active Quasi-Linear attack, which requires approximately 213 authentication sessions to disclose the tag’s secret ID.

Full Text:



Hung-Yu Chien,” SASI: A New Ultralightweight RFID Authentication Protocol Providing Strong Authentication and Strong Integrity”, IEEE Transaction on Dependable and Secure Computing, Vol. 4, No. 4, pp. 337 – 340, 2007.

Umar Mujahid, M. Najam-ul-Islam, and M. Ali Shami, “RCIA: A New Ultralightweight RFID Authentication Protocol Using Recursive Hash,” International Journal of Distributed Sensor Networks, vol. 2015, Article ID 642180, 8 pages, 2015. doi:10.1155/2015/642180

Hung-Min Sun, Wei-Chih Tiang et al.,”On the Security of Chein’s Ultralightweight RFID Authentication Protocol”, IEEE Transactions on Dependable and Secure Computing, Vol.8, No.2, pp.315-317, 2011.

Pedro Peris-Lopez, Julio Hernandez-Castro et al. "LMAP: A real lightweight mutual authentication protocol for low-cost RFID tag.", Proceedings of 2nd Workshop on RFID Security, Austria, pp.100-112, 2006.

Tieyan Li,” Security Analysis of family of Ultra-Lightweight RFID Authentication Protocols”, Journal of Software, Vol. 3, No. 3, pp. 1-10, 2008.

Peris-Lopez, Pedro, Julio Cesar Hernandez "EMAP: An efficient mutual-authentication protocol for low-cost RFID tags.", The 1st International Workshop on Information security (OTM-2006), France, pp. 352-361, 2006.

Peris-Lopez, J.C. Hernandez-Castro, J.M.E. Tapiador, A.Ribagorda,”M2AP: a minimalist mutual-authentication protocol for low cost RFID tags”, International Conference on Ubiquitous Intelligence and Computing, pp.912- 923, 2006.

Tianjie, Elisa Bertin et al. "Security analysis of the SASI protocol", IEEE Transactions on Dependable and Secure Computing, Vol.6, No. 1, pp. 73 – 77, 2009.

Peris-Lopez,Hernandez-Castro et al. "Advances in ultralightweight cryptography for low-cost RFID tags: Gossamer protocol.", The 9th International Workshop on Information Security Applications, pp. 56-68, 2009.

Yeh, Kuo-Hui, and N. W. Lo. "Improvement of two lightweight RFID authentication protocols", Information Assurance and Security Letters Vol.1, No.1, pp 6-11, 2010.

Bilal, Zeeshan, Ashraf Masood, and Firdous Kausar. "Security analysis of ultra-lightweight cryptographic protocol for low-cost RFID tags: Gossamer protocol", The 12th International Conference on Network-Based Information Systems, Indianapolis, USA, pp. 260-267, 2009.

Muhammad Zubair, Umar Mujahid,” Cryptanalysis of RFID Ultralightweight protocols and comparison between its solution approaches”, Bahria University Journal of information & communication technology (BUJICT), Vol.5, No. 1, pp. 58-63, 2012.

David, Mathieu, and Neeli R. Prasad. "Providing strong security and high privacy in low-cost RFID networks", International conference on Security and privacy in mobile information and communication systems, Italy, pp.172-179, 2009.

Barrero, David "A genetic tango attack against the David–Prasad RFID ultra‐lightweight authentication protocol", Expert Systems (Journal) Vol. 31, no. 1, pp. 9- 19, 2014.

Tian, Yun, Gongliang Chen, and Jianhua Li. "A new ultralightweight RFID authentication protocol with permutation", IEEE Communications Letters, Vol.16, no. 5, pp.702- 705, 2012.

Bagheri, Nasour, Masoumeh Safkhani et al. "Cryptanalysis of RAPP, an RFID Authentication Protocol", Cryptology ePrint Archive, Report 2012/702,, 2012.

Tingyuan, and Teng Zhang. "A study of DES and Blowfish encryption algorithm.", IEEE Region 10 Conference, TENCON-2009, Singapore, pp. 1-4, 2009.

Engels, Daniel, et al. "Hummingbird: ultra-lightweight cryptography for resource-constrained device." The 14th International Conference on Financial Cryptography and Data Security, Spain, pp.3-18, 2010.

Boyeon song and Chris J. Mitchell. "RFID authentication protocol for low-cost tags" The 1st ACM conference on Wireless network security, USA, pp. 140-147, 2008.

Rizomiliotis, Panagiotise"Security analysis of the Song-Mitchell authentication protocol for low-cost RFID tag.", IEEE Communications Letters, Vol.13, No. 4, pp. 274-276, 2009.

Peris-López,” Lightweight Cryptography in Radio Frequency Identification (RFID) Systems”, PhD thesis, UNIVERSIDAD CARLOS III DE MADRID, 2008.

Pedro Peris-Lopez, "Quasi-linear cryptanalysis of a secure RFID ultralightweight authentication protocol ", The 6th International Conference on Information Security and Cryptology, China, pp. 427-442, 2011.

Yeh, Kuo-Hui, N. W. Lo, and Enrico Winata. "An efficient ultralightweight authentication protocol for RFID systems", Workshop on RFID Security and Privacy, Turkey, pp 49-60, 2010.

Zahra Ahmadian, Mahmoud. “Recursive linear and differential cryptanalysis of ultralightweight authentication protocols”, IEEE Transactions on Information Forensics and Security, Vol.8. No.7, pp.1140–1151, 2013.

Julio C. Hernandez. "Cryptanalysis of the SASI ultralightweight RFID authentication protocol with modular rotations.", ArXiv, Cryptography and Security, Report; 0811.4257,, 2008.

Avoine, Gildas, Xavier Carpent, and Benjamin Martin. "Privacy-friendly synchronized ultralightweight authentication protocols in the storm", Journal of Network and Computer Applications, Vol.35, No. 2, pp. 826-843, 2012.

A. Klimov and A. Shamir. “New Applications of T-functions in Block Ciphers and hash functions”. Proc. of FSE’05, LNCS vol. 3557, pp. 18–31. Springer-Verlag,2005.

Xu Zhuang, Yan Zhu and Chin-Chen Chang,” A New Ultralightweight RFID Protocol for Low- Cost Tags: R2AP”, Wireless Personal Communications, Vol. 79, No.3, pp 1787-1802, 2014.

Zeeshan Bilal, Keith Martin and Qasim Saeed, “Multiple Attacks on Authentication Protocols for Low-Cost RFID Tags”, Applied Mathematics & Information Sciences, Vol.9, No.2, pp-561-569, 2015.

Soo Jeon and Eun-Jun Yoon,” Cryptanalysis and Improvement of a New Ultra-lightweight RFID Authentication Protocol with Permutation” Applied Mathematical Sciences, Vol. 7, 2013, No. 69, pp. 3433 – 3444, 2013.

Umar Mujahid, M.Najam-ul-Islam,” Ultralightweight Cryptography for Passive RFID systems”, International Journal of Communication Networks and Information Security, Vol.6, No.3, pp.173-181, 2014.

Zahra Ahmadian, Mahmoud Salmasizadeh and Mohammad Reza Aref, "Desynchronization attack on RAPP ultralightweight authentication protocol." Information processing letters, Vol.113, No.7, pp. 205-209, 2013.

G. Marsaglia and W.W. Tsang. “Some difficult-to-pass tests of randomness”, Journal of Statistical Software, Vol. 7, No. 3, pp.37–51, 2002.

J. Walker. ENT Randomness Test., 1998.

C. Suresh, Charanjit J., J.R. Rao, and P. Rohatgi,”A cautionary note regarding evaluation of AES candidates on smart-cards”. In Second Advanced Encryption Standard (AES) Candidate Conference, 1999.

Lee. Y.C., Hsieh.Y.C., et al.,”A new ultralightweight RFID authentication protocol with mutual authentication “, International Conference on Information Engineering, Vol. 1, pp.55-61, 2009.

Peris-Lopez, Hernandez Castro, J.C., Tapiador and Van der Lubbe,” Security flaws in a recent ultralightweight RFID authentication protocol”, Workshop on RFID security- RFIDSec Asia’10, Singapore, 2010.

Wang, S., Han, Z., Lui, S. and chen,D,” Security analysis of RAPP: an RFID authentication protocol based on permutation”, Cryptology ePrint Archive, Report 2012/327.

Gildas Avoine, Xavier Carpent and Benjamin Martin,” Strong Authentication and Strong Integrity (SASI) is not that strong”, RFID Security and Privacy Issues, LNCS, Vol.6370, pp-50-64, 2010.

Li. T and Wang.G, “Security analysis of two ultralightweight RFID authentication protocols” The second information security conference, Sandton, Ganteng, South Africa, 2007.

Copyright (c) 2016 Umar Mujahid, M. Najam-ul-islam

Powered By KICS