Cryptanalysis of a Cayley hash function based on affine maps in one variable over a finite field (Q6564022)

This paper provides an in-depth analysis of the security vulnerabilities present in the Ghaffari and Mostaghim hash functions [\textit{M. H. Ghaffari} and \textit{Z. Mostaghim}, Groups Complex. Cryptol. 10, No. 1, 29--32 (2018; Zbl 1391.94753)], which were introduced as a variation of the earlier Shpilrain and Sosnovski hash function [\textit{V. Shpilrain} and \textit{B. Sosnovski}, ibid. 8, No. 2, 155--161 (2016; Zbl 1353.94073)]. The findings reveal significant weaknesses in the Ghaffari and Mostaghim hash function, particularly in its collision resistance, by leveraging known vulnerabilities in its predecessor.\N\NHash functions play a crucial role in cryptographic systems, serving as foundational elements in a wide range of applications including database indexing, data compression, password storage, digital signatures, encryption schemes, and key derivation systems. Essential properties of cryptographic hash functions include preimage resistance and collision resistance, which are critical for ensuring the security of these applications.\N\NThe paper highlights the looming threat posed by quantum computing to classical cryptographic systems. Although practical quantum computers are not yet a reality, advancements in this field could eventually render many current cryptographic protocols vulnerable. This underscores the importance of developing cryptographic techniques that are resilient to quantum attacks.\N\NThe concept of provably secure hash functions, which derive their security from the hardness of specific mathematical problems, is discussed. An example provided is a Cayley hash function, which is constructed from Cayley graphs of groups. These hash functions are theoretically robust against certain types of attacks, assuming the underlying mathematical problems remain hard.\N\NThe paper references a 2016 hash function proposed by Shpilrain and Sosnovski [loc.cit.], based on affine maps over finite fields, which was proven insecure under certain parameters. This forms the basis for the analysis of the Ghaffari and Mostaghim hash function, introduced in [Ghaffari and Mostaghim, loc. cit.] as a variation but also found to be insecure.\N\NThe core contribution of this paper is the demonstration that the Ghaffari and Mostaghim hash function lacks collision resistance. By applying \textit{C. Monico}'s algorithm [ibid. 11, No. 1, 17--23 (2019; Zbl 1434.94075)], which was originally used to find second preimages for the Shpilrain-Sosnovski hash function, the authors successfully generate collisions for the Ghaffari and Mostaghim hash function. This result is significant as it directly challenges the security claims of the Ghaffari and Mostaghim hash functions.\N\NThe paper is well-organized, with a clear structure that guides the reader through the key points. Section 2 revisits basic definitions and properties of cryptographic hash functions; Section 3 provides a brief description of both the Shpilrain-Sosnovski and Ghaffari-Mostaghim hash functions; Section 4 summarizes the cryptanalysis of the Shpilrain-Sosnovski hash function. Finally, Section 5 presents the main results, demonstrating the insecurity of the Ghaffari and Mostaghim hash function.\N\NThis paper makes a valuable contribution to the field by exposing critical vulnerabilities in a recent hash function proposal. The rigorous cryptanalysis and clear exposition of results provide a strong foundation for future research and highlight the ongoing need for robust, quantum-resistant cryptographic primitives.