Abstract: As RFID becomes more and more popular, it is imperative to design authentication protocols to resist all possible attacks and threats. In order to overcome counterfeits of readers, a new authentication protocol is proposed based on key array. The new protocol can deal with the synchronization of key update by adding flags of key update. It can resist several possible attacks, including reply, tracking, blocking, proofing and inner attacks. Compared with other authentication protocols, the new protocol can improve the security of RFID systems effectively and does not increase the complexity of protocol.