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

    Abstract

    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
    PublisherSpringer
    Publication date2010
    Pages118-130
    ISBN (Print)978-3-642-17400-1
    DOIs
    Publication statusPublished - 2010
    Event11th International Conference on Cryptology in India - Hyderabad, India
    Duration: 12 Dec 201015 Dec 2010
    Conference number: 11

    Conference

    Conference11th International Conference on Cryptology in India
    Number11
    CountryIndia
    CityHyderabad
    Period12/12/201015/12/2010
    SeriesLecture Notes in Computer Science
    Volume6498
    ISSN0302-9743

    Keywords

    • 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 https://doi.org/10.1007/978-3-642-17401-8_10
    Kumar, Ashish ; Sanadhya, Somitra Kumar ; Gauravaram, Praveen ; Safkhani, Masoumeh ; Naderi, Majid. / Cryptanalysis of Tav-128 hash function. Proceedings of Indocrypt 2010: 11th International Conference on Cryptology in India. editor / Guang Gong ; Kishan Chand Gupta. Springer, 2010. pp. 118-130 (Lecture Notes in Computer Science, Vol. 6498).
    @inproceedings{5d5d0b23a7cb40e2b8f6ea928bd7525f,
    title = "Cryptanalysis of Tav-128 hash function",
    abstract = "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.",
    keywords = "Hash function, Compression function, RFID, Cryptanalysis, Tav-128",
    author = "Ashish Kumar and Sanadhya, {Somitra Kumar} and Praveen Gauravaram and Masoumeh Safkhani and Majid Naderi",
    year = "2010",
    doi = "10.1007/978-3-642-17401-8_10",
    language = "English",
    isbn = "978-3-642-17400-1",
    pages = "118--130",
    editor = "Guang Gong and Gupta, {Kishan Chand}",
    booktitle = "Proceedings of Indocrypt 2010",
    publisher = "Springer",

    }

    Kumar, A, Sanadhya, SK, Gauravaram, P, Safkhani, M & Naderi, M 2010, Cryptanalysis of Tav-128 hash function. in G Gong & KC Gupta (eds), Proceedings of Indocrypt 2010: 11th International Conference on Cryptology in India. Springer, Lecture Notes in Computer Science, vol. 6498, pp. 118-130, 11th International Conference on Cryptology in India, Hyderabad, India, 12/12/2010. https://doi.org/10.1007/978-3-642-17401-8_10

    Cryptanalysis of Tav-128 hash function. / Kumar, Ashish; Sanadhya, Somitra Kumar; Gauravaram, Praveen; Safkhani, Masoumeh; Naderi, Majid.

    Proceedings of Indocrypt 2010: 11th International Conference on Cryptology in India. ed. / Guang Gong; Kishan Chand Gupta. Springer, 2010. p. 118-130 (Lecture Notes in Computer Science, Vol. 6498).

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

    TY - GEN

    T1 - Cryptanalysis of Tav-128 hash function

    AU - Kumar, Ashish

    AU - Sanadhya, Somitra Kumar

    AU - Gauravaram, Praveen

    AU - Safkhani, Masoumeh

    AU - Naderi, Majid

    PY - 2010

    Y1 - 2010

    N2 - 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.

    AB - 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.

    KW - Hash function

    KW - Compression function

    KW - RFID

    KW - Cryptanalysis

    KW - Tav-128

    U2 - 10.1007/978-3-642-17401-8_10

    DO - 10.1007/978-3-642-17401-8_10

    M3 - Article in proceedings

    SN - 978-3-642-17400-1

    SP - 118

    EP - 130

    BT - Proceedings of Indocrypt 2010

    A2 - Gong, Guang

    A2 - Gupta, Kishan Chand

    PB - Springer

    ER -

    Kumar A, Sanadhya SK, Gauravaram P, Safkhani M, Naderi M. Cryptanalysis of Tav-128 hash function. In Gong G, Gupta KC, editors, Proceedings of Indocrypt 2010: 11th International Conference on Cryptology in India. Springer. 2010. p. 118-130. (Lecture Notes in Computer Science, Vol. 6498). https://doi.org/10.1007/978-3-642-17401-8_10