Cryptanalysis of Tav-128 hash function

Ashish Kumar, Somitra Kumar Sanadhya, Praveen Gauravaram, Masoumeh Safkhani, Majid Naderi

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


    Many RFID protocols use cryptographic hash functions for their security. The resource constrained nature of RFID systems forces the use of light weight cryptographic algorithms. Tav-128 is one such 128-bit light weight hash function proposed by Peris-Lopez et al. for a low-cost RFID tag authentication protocol. Apart from some statistical tests for randomness by the designers themselves, Tav-128 has not undergone any other thorough security analysis. Based on these tests, the designers claimed that Tav-128 does not posses any trivial weaknesses. In this article, we carry out the first third party security analysis of Tav-128 and show that this hash function is neither collision resistant nor second preimage resistant. Firstly, we show a practical collision attack on Tav-128 having a complexity of 237 calls to the compression function and produce message pairs of arbitrary length which produce the same hash value under this hash function. We then show a second preimage attack on Tav-128 which succeeds with a complexity of 262 calls to the compression function. Finally, we study the constituent functions of Tav-128 and show that the concatenation of nonlinear functions A and B produces a 64-bit permutation from 32-bit messages. This could be a useful light weight primitive for future RFID protocols.
    Original languageEnglish
    Title of host publicationProceedings of Indocrypt 2010 : 11th International Conference on Cryptology in India
    EditorsGuang Gong, Kishan Chand Gupta
    Publication date2010
    ISBN (Print)978-3-642-17400-1
    Publication statusPublished - 2010
    Event11th International Conference on Cryptology in India - Hyderabad, India
    Duration: 12 Dec 201015 Dec 2010
    Conference number: 11


    Conference11th International Conference on Cryptology in India
    SeriesLecture Notes in Computer Science


    • Hash function
    • Compression function
    • RFID
    • Cryptanalysis
    • Tav-128

    Cite this

    Kumar, A., Sanadhya, S. K., Gauravaram, P., Safkhani, M., & Naderi, M. (2010). Cryptanalysis of Tav-128 hash function. In G. Gong, & K. C. Gupta (Eds.), Proceedings of Indocrypt 2010: 11th International Conference on Cryptology in India (pp. 118-130). Springer. Lecture Notes in Computer Science, Vol.. 6498