Implementation and Performance Testing of the SQUASH RFID Authentication Protocol

We implement and test the performance of an RFID hash algorithm recently proposed by Adi Shamir [1] using a C++ simulation. The algorithm, called SQUASH (short for “SQUare-hASH”), allows for an RFID tag design that is simple enough to be implemented on low-cost RFID tags. Shamir has proved mathematically that his SQUASH algorithm is at least as secure as the Rabin cryptosystem [2], which has been extensively tested and scrutinized for nearly 30 years. The SQUASH algorithm is designed to minimize processing time and cost without sacrificing security. Shamir's SQUASH algorithm was developed as a lightweight version of a hash function from the Rabin cryptosystem, ${\mbi c}={\mbi m}^{2}\ {\mbi mod}\ {\mbi n}$. The SQUASH algorithm is theoretically faster because rather than storing, computing, and transmitting a large ciphertext, the algorithm allows a low cost RFID tag to compute the bits of the ciphertext in real-time, bit by bit, transmitting them as they are calculated. Although the SQUASH algorithm is provably as secure as the Rabin cryptosystem, the performance of the algorithm has not been carefully scrutinized. Shamir writes that the performance of the SQUASH algorithm should scale linearly as the size of a tag's register increases; we attempt to test this specific claim by using a software simulation.