Cryptanalysis of the David-Prasad RFID ultralightweight authentication protocol

In September 2009, David and Prasad proposed at MobiSec'09 an interesting new ultralightweight mutual authentication protocol for low-cost RFID tags. In this paper, we present a quite powerful cryptanalytic attack against their proposal: we start with a traceability attack, then describe how it can be extended to leak long-term stored secrets, and finally present a full disclosure attack (named Tango attack) where all the secrets that the protocol is designed to conceal are shown to be retrievable, even by a passive attacker after eavesdropping only a small number of authentication sessions. These results imply that very realistic attack scenarios are completely possible. The Tango attack constitutes a new, simple, yet powerful technique of cryptanalysis which is based on the computation and full exploitation of multiple approximations to the secret values, using Hamming distances and the representation of variables in an n-dimensional space.