HB − MAC: Improving the Random − HB # Authentication Protocol

The

Random

 − 

HB

#

protocol is a significant improvement of the

HB

 + 

protocol introduced by Juels and Weis for the authentication of low-cost RFID tags.

Random

 − 

HB

#

improves

HB

 + 

in terms of both security and practicality. It is provably resistant against man-in-the-middle attacks, where the adversary can modify messages send from the reader to the tag and performs significantly better than

HB

 + 

, since it reduces the transmission costs and provides more practical error rates. The only problem with

Random

 − 

HB

#

is that the storage costs for the secret keys are insurmountable to low cost tags. The designers of the protocol have proposed also an enhanced variant which has less storage requirements, but it is not supported by a security proof. They call this variant just

HB

#

. In this paper we propose a variant of the

Random

 − 

HB

#

. The new proposal maintains the performance of the

Random

 − 

HB

#

, but it requires significantly less storage for the key. To achieve that we add a lightweight message authentication code to protect the integrity of all the exchanged messages.