Geodesic
Evaluation of mixing characteristics for Merkle–Damgard hash functions
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 107-110 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The matrix-graph approach (MGA), which has been successfully applied to the evaluation of iterative block ciphers and key generators, is presented for the first time as a tool for estimating the mixing properties of hash algorithms. Feature of MGA application to hash functions is connected with the possibility of construction the mixing matrices which characterize dependence of the bits of the hash value on the bits of the input message. Mixing matrices of the order $512+n$ are constructed for hash functions MD4, MD5, SHA-1, SHA-256, where $n$ is the size of the digest produced by the compression function processing the $512$-bit block of the input message ($n=128$ for MD4 and MD5, $n=160$ for SHA-1 and $n=256$ for SHA-256). We calculate the local exponents of mixing matrices, i.e., for each matrix $M$, we obtain the smallest positive integer $\gamma$ such that for any natural $\tau \ge \gamma$ all the columns of $M^{\tau}$ with the numbers $513, 514, \ldots, 512+n$ are positive. The values of the local exponents are the lower bounds for the number of iterations, after which each bit of the output hash may essentially depend on all bits of the input message. The obtained values ($\gamma=21$ for MD4, MD5, SHA-256 and $\gamma=23$ for SHA-1) indirectly indicate the similar mixing properties of the considered hash algorithms despite the increase of block length and complexity of the compression function.
Keywords: hash functions, Merkle–Damgard structure, matrix-graph approach, mixing properties. 
@article{PDMA_2019_12_a32,
     author = {A. M. Koreneva},
     title = {Evaluation of mixing characteristics for {Merkle{\textendash}Damgard} hash functions},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {107--110},
     year = {2019},
     number = {12},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a32/}
}
TY  - JOUR
AU  - A. M. Koreneva
TI  - Evaluation of mixing characteristics for Merkle–Damgard hash functions
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 107
EP  - 110
IS  - 12
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a32/
LA  - ru
ID  - PDMA_2019_12_a32
ER  - 
%0 Journal Article
%A A. M. Koreneva
%T Evaluation of mixing characteristics for Merkle–Damgard hash functions
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 107-110
%N 12
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a32/
%G ru
%F PDMA_2019_12_a32
A. M. Koreneva. Evaluation of mixing characteristics for Merkle–Damgard hash functions. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 107-110. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a32/

[1] Fomichev V. M., Avezova Ya. E., Koreneva A. M., Kyazhin S. N., “Primitivity and local primitivity of digraphs and nonnegative matrices”, J. Appl. Industr. Math., 12:3 (2018), 453–469 | DOI | MR | Zbl

[2] Fomichev V. M., Koreneva A. M., Miftahutdinova A. R., Zadorozhniy D. I., “Evaluation of the maximum productivity for block encryption algorithms”, VII Simp. «Sovremennye tendentsii v kriptografii» CTCrypt 2018 https://ctcrypt.ru/files/files/2018/17_Koreneva.pdf | MR

[3] Fomichev V. M., Koreneva A. M., “Mixing properties of modified additive generators”, J. Appl. Industr. Math., 11:2 (2017), 215–226 | DOI | MR | Zbl

[4] Koreneva A. M., Martyshin V. N., “Eksperimentalnoe issledovanie eksponentov raundovykh peremeshivayuschikh matrits obobschennykh setei Feistelya”, Prikladnaya diskretnaya matematika. Prilozhenie, 2016, no. 9, 48–51

[5] Avezova Ya. E., “Sovremennye podkhody k postroeniyu khesh-funktsii na primere finalistov konkursa SHA-3”, Voprosy kiberbezopasnosti, 2015, no. 3(11), 60–67

[6] Cheremushkin A. V., Kriptograficheskie protokoly. Osnovnye svoistva i uyazvimosti, ucheb. posobie dlya stud. uchrezhdenii vyssh. prof. obrazovaniya, Izdatelskii tsentr «Akademiya», M., 2009, 272 pp.