  Security in passive resource-constrained Radio Frequency Identification
(RFID) tags is of much interest nowadays. Resistance against illegal tracking,
cloning, timing, and replay attacks are necessary for a secure RFID
authentication scheme. Reader authentication is also necessary to thwart any
illegal attempt to read the tags. With an objective to design a secure and
low-cost RFID authentication protocol, Gene Tsudik proposed a timestamp-based
protocol using symmetric keys, named YA-TRAP*. Although YA-TRAP* achieves its
target security properties, it is susceptible to timing attacks, where the
timestamp to be sent by the reader to the tag can be freely selected by an
adversary. Moreover, in YA-TRAP*, reader authentication is not provided, and a
tag can become inoperative after exceeding its pre-stored threshold timestamp
value. In this paper, we propose two mutual RFID authentication protocols that
aim to improve YA-TRAP* by preventing timing attack, and by providing reader
authentication. Also, a tag is allowed to refresh its pre-stored threshold
value in our protocols, so that it does not become inoperative after exceeding
the threshold. Our protocols also achieve other security properties like
forward security, resistance against cloning, replay, and tracking attacks.
Moreover, the computation and communication costs are kept as low as possible
for the tags. It is important to keep the communication cost as low as possible
when many tags are authenticated in batch-mode. By introducing aggregate
function for the reader-to-server communication, the communication cost is
reduced. We also discuss different possible applications of our protocols. Our
protocols thus capture more security properties and more efficiency than
YA-TRAP*. Finally, we show that our protocols can be implemented using the
current standard low-cost RFID infrastructures.
