AbstractRadio‐frequency identification (RFID) is a technology for automated identification of objects and people. RFID raises two main concerns: security and privacy. RFID tags are likely to proliferate into billions, and nowadays, security and privacy of RFID systems are to be continuously improved. In this context, we propose a new ultralightweight RFID mutual authentication protocol based on the Feistel cipher structure. This structure is based on substitutions and random permutations which create confusion and diffusion in the transmitted messages. The main contribution of this work is the application of Feistel cipher structure to design a low‐cost authentication protocol for RFID tags involving simple lightweight operations in the tag. Security analysis shows that the proposed protocol achieves the functionalities of mutual authentication, resists to various attacks, and presents a scalable security level. Copyright © 2017 John Wiley & Sons, Ltd.