Mathematical Methods of Cryptography

On probability characteristics of random graphs generated by algorithms for finding hash function collisions

G. A. Karpunin

M. V. Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics

Abstract: In the paper, a graph model of some algorithms for finding SHA-1 and RIPEMD collisions is described, and under the described model, an exact formula for calculating average complexity of these algorithms is given.

Keywords: cryptographic hash functions, collisions, random graphs.

UDC: 519.17, 004.056.2, 004.056.53