Radio Frequency Identification (RFID) technology will become one of the most popular technologies to identify objects in the near future. However, the major barrier that the RFID system is facing presently is the security and privacy issue. Recently, an ultralightweight RFID authentication protocol with permutation has been proposed to provide security and prevent all possible attacks. However, it is discovered that a type of desynchronization attack can successfully break the proposed scheme. To overcome the vulnerability under the desynchronization attacks, we propose an approximate ultralightweight RFID authentication protocol which integrates the operation of the XOR operator, build-in CRC-16 function, the permutation and secret key backup technology to improve the security functions without increasing any security cost. We formally verify the security functionality of the proposed scheme by using Simple Promela Interpreter (SPIN). Analysis shows that our proposal has a strong ability to prevent existing possible attacks.