RFID authentication has raised many concerns about the security risks and privacy issues due to its lightweight authentication properties. Many research achievements in RFID focus on strengthening the entire RFID system and solving the security problems. Recently, a hashbased RFID security protocol with the intension of updating the identifier of the tag in both the reader side and the tag side itself was proposed. However, there exists inherent risk in the IDupdating procedure. In the scenario that the adversary blocks the legal messages continuously for several times, the backend processing system (BPS) cannot recognize the tag due to the desynchronization of the identifier in last several sessions. Thus the tag will be invalid and cannot be reused again. In this paper, we propose an enhanced ID-updating hash-based RFID authentication protocol with strong privacy protection. In our protocol the ID-updating procedure is resistant to de-synchronization attack. Additionally, the possible feedbacks towards different cases of the tag are taken into consideration. Our proposed protocol is proved to be effective and secure in real applications. Above all, the de-synchronization attack towards the communication between the tag and reader can be prevented according to our design. The identifier of the RFID tag is assumed to be updated with cryptographic hash functions during every session. In this way the identifier can be synchronized in both the BPS side and the RFID tag side. The location privacy of the tag can be protected in our protocol.