Cryptanalysis of TS-Hash
Authors
Aleksei Udovenko
Aleksei Udovenko
SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg
aleksei at affine dot group
aleksei at affine dot group
Keywords:
Cryptanalysis
Hash function
LFSR
Lightweight
Low-weight
Generalized birthday paradox
Linearization
Quadratic equations
Abstract
This note presents attacks on the lightweight hash function TS-Hash proposed by Tsaban, including a polynomial-time preimage attack for short messages (at most $n/2$ bits), high-probability differentials, a general subexponential-time preimage attack, and linearization techniques.
References
[Aim21]
Laila El Aimani. A New Approach for Finding Low-Weight Polynomial Multiples. In Inscrypt, volume 13007 of Lecture Notes in Computer Science, pages 151–170. 2021. Springer. DOI: 10.1007/978-3-030-88323-2_8
[BSV15]
[BT23a]
Itay Bookstein and Boaz Tsaban. TS-Hash: a lightweight cryptographic hash family based on Galois LFSRs. Cryptology ePrint Archive, Paper 2023/179. 2023.
[BT23b]
Itay Bookstein and Boaz Tsaban. TS-Hash: a lightweight cryptographic hash family based on Galois LFSRs. Mathematical Cryptology, 3(1):96–106, Aug. 2023.
[CJM02]
Philippe Chose, Antoine Joux, and Michel Mitton. Fast Correlation Attacks: An Algorithmic Point of View. In Lars R. Knudsen, editor, EUROCRYPT 2002, volume 2332 of LNCS, pages 209–221. 2002. Springer, Heidelberg. DOI: 10.1007/3-540-46035-7_14
[GIMS11]
Markus Grassl, Ivana Ilic, Spyros S. Magliveras, and Rainer Steinwandt. Cryptanalysis of the Tillich-Zémor Hash Function. Journal of Cryptology, 24(1):148–156, January 2011. DOI: 10.1007/s00145-010-9063-0
[MS88]
Willi Meier and Othmar Staffelbach. Fast Correlation Attacks on Stream Ciphers (Extended Abstract). In C. G. Günther, editor, EUROCRYPT'88, volume 330 of LNCS, pages 301–314. May 1988. Springer, Heidelberg. DOI: 10.1007/3-540-45961-8_28
[PLQ07]
Christophe Petit, Kristin Lauter, and Jean-Jacques Quisquater. Cayley hashes: A class of efficient graph-based hash functions. preprint. 2007.
[PQ11]
Christophe Petit and Jean-Jacques Quisquater. Preimages for the Tillich-Zémor Hash Function. In Alex Biryukov, Guang Gong, and Douglas R. Stinson, editors, SAC 2010, volume 6544 of LNCS, pages 282–301. August 2011. Springer, Heidelberg. DOI: 10.1007/978-3-642-19574-7_20
[{Sag}24]
The Sage Developers. SageMath, the Sage Mathematics Software System (Version 10.4). , 2024.
[Sie86]
Thomas Siegenthaler. Cryptanalysts Representation of Nonlinearly Filtered ML-Sequences. In Franz Pichler, editor, EUROCRYPT'85, volume 219 of LNCS, pages 103–110. April 1986. Springer, Heidelberg. DOI: 10.1007/3-540-39805-8_12
[Tsa17]
Boaz Tsaban. [Examples of research problems for a master's thesis in mathematical aspects of cyber security and cryptography]. http://u.cs.biu.ac.il/ tsaban/CyberIntro.html. 2017.
[TZ94a]
Jean-Pierre Tillich and Gilles Zémor. Group-theoretic hash functions. In G. Cohen, S. Litsyn, A. Lobstein, and G. Zémor, editors, Algebraic Coding, pages 90–110, Berlin, Heidelberg. 1994. Springer Berlin Heidelberg. DOI: 10.1007/3-540-57843-9_12
[TZ94b]
Jean-Pierre Tillich and Gilles Zémor. Hashing with SL_2. In Yvo Desmedt, editor, CRYPTO'94, volume 839 of LNCS, pages 40–49. August 1994. Springer, Heidelberg. DOI: 10.1007/3-540-48658-5_5
[Wag02]
David Wagner. A Generalized Birthday Problem. In Moti Yung, editor, CRYPTO 2002, volume 2442 of LNCS, pages 288–303. August 2002. Springer, Heidelberg. DOI: 10.1007/3-540-45708-9_19
[Z{\'e}m94]
Gilles Zémor. Hash Functions and Cayley Graphs. DCC, 4(4):381–394, 1994. DOI: 10.1007/BF01388652
PDF
History
Submitted: 2024-07-06
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Aleksei Udovenko, Cryptanalysis of TS-Hash. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/akjbhey6b.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.