RFID is one of the most prominent identification schemes in the field of pervasive systems. Nonline of sight capability makes RFID systems much better choice than its contended systems (such as barcode, magnetic tape, etc.). Since the RFID uses wireless channel for communication with its associated devices, there should be some optimal encryption methods to secure the communicating data from adversaries. Several researchers have proposed ultralightweight mutual authentication protocols (UMAPs) to secure the RFID systems in cost effective manner. Unfortunately most of the previously proposed UMAPs are later found to be vulnerable against various desynchronization, Denial of Service (DoS), traceability, and full disclosure attacks. In this paper, we present a more sophisticated UMAP to provide Strong Authentication and Strong Integrity (SASI) using recursive hash function. The proposed protocol incorporates only simple bitwise logical operators XOR, Rot, and nontriangular function (recursive hash) in its design, which can be efficiently implemented with a low cost passive RFID tag. The performance analysis of the protocol proves the conformation of the proposed protocol with EPC-C1G2 passive tags. In addition to privacy and security, small chip area (miniaturization) is another design constraint (which is mandatory requirement for a protocol to be considered as ultralightweight authentication protocol). We have also proposed and implemented the efficient hardware design of the proposed protocol for EPC-C1G2 tags. Both the FPGA and ASIC implementation flows have been adopted. The FPGA flow is primarily used to validate the functionality of the proposed hardware design whereas ASIC flow (using TSMC 0.35 μm library) is used to validate the gate count. To the best of our knowledge, this is the first FPGA and ASIC implementation of any ultralightweight RFID authentication protocol. [ABSTRACT FROM AUTHOR]