Cryptanalysis of the Improved SPRS Protocol: an Authentication Protocol for RFID Systems

Authentication protocols are tools used to ensure the identity of the parties in cyberspace. If these protocols are compromised, the cyber security is threatened. These threats are of paramount importance in military applications. Recently, in [1] an authentication protocol, called SPRS has been considered and several attacks such as secret disclosure attack, tag impersonation attack and tag traceability attack have been applied on it. In addition, authors of that paper, presented the improved version of the protocol and claimed the improved protocol, unlike its predecessor, is secure against the attacks applied on the predecessor version and also other active and passive attacks.In this paper, we show that unfortunately, the security claims of authors do not hold and the improved protocol is also vulnerable against secret disclosure attack and tag traceability attack. We offer two versions of the secret disclosure attack which are offline and online versions. The basis of the attacks presented in this paper is that given Y=PRNG(X) and PRNG function is a public function and X and Y are 16 bits, performing an exhaustive search to find X as a pre-image of Y with a maximum of 216 off-line evaluations of PRNG function is possible. The offline version of the attack with the complexity of one run of protocol eavesdropping and doing 233 evaluations of PRNG function can disclose 4 secret values of protocol i.e. Ki, Pi, NT and EPCS which are 16 bits and the online version of the attack with the complexity of two times impersonating the reader and doing 217 evaluations of PRNG function can disclose these 4 secret values of protocol. Given these secret disclosure attacks, the improved protocol is not secure against other active and passive attacks as well. In addition, we propose a tag traceability attack to trace a given tag which does not depend on the length of the output of the PRNG function. Given this attack, an adversary can trace a given tag between any two sessions with the reader.