Geodesic
About $k$-bit security>> of MACs based on hash function Streebog
Matematičeskie voprosy kriptografii, Tome 15 (2024) no. 2, pp. 47-68 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Various message authentication codes (MACs), including HMAC-Streebog and Streebog-K, are based on the keyless hash function Streebog. Under the assumption that the compression function of Streebog is resistant to the related key attacks, the security proofs of these algorithms (in the single key setting) were recently presented at CTCrypt 2022. Generic related key attacks have the great impact on the security bounds. Guessing any one of the $q$ related keys can be $q$ times faster than guessing a single secret key. However, if different related keys are used to process different inputs, then the adversary should choose a specific key when guessing, not any one. This simple observation fortunately holds for MACs based on Streebog. We carefully detail the resources of the adversary in the related key settings, revisit the proof, and obtain new security bounds. Let $n$ be the bit length of the hash function state. If the amount of processed data is less than about $2^{n-k}$ blocks, then for HMAC-Streebog-512 and Streebog-K, the only effective method of forgery (or distinguishing) is guessing the $k$-bit secret key or the tag if it is shorter than the key. So, we can speak about «$k$-bit security» without specifying the amount of material, if the key length is no longer than half of a state. The bound for HMAC-Streebog-256 is worse and equal to $2^{\frac{n}{2}-k}$ blocks. We describe several attacks that show the tightness of the obtained security bounds. Hence, the latter cannot be significantly improved further. 
@article{MVK_2024_15_2_a3,
     author = {V. A. Kiryukhin},
     title = {About <<$k$-bit security>> of {MACs} based on hash function {Streebog}},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {47--68},
     year = {2024},
     volume = {15},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2024_15_2_a3/}
}
TY  - JOUR
AU  - V. A. Kiryukhin
TI  - About <<$k$-bit security>> of MACs based on hash function Streebog
JO  - Matematičeskie voprosy kriptografii
PY  - 2024
SP  - 47
EP  - 68
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2024_15_2_a3/
LA  - ru
ID  - MVK_2024_15_2_a3
ER  - 
%0 Journal Article
%A V. A. Kiryukhin
%T About <<$k$-bit security>> of MACs based on hash function Streebog
%J Matematičeskie voprosy kriptografii
%D 2024
%P 47-68
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2024_15_2_a3/
%G ru
%F MVK_2024_15_2_a3
V. A. Kiryukhin. About <<$k$-bit security>> of MACs based on hash function Streebog. Matematičeskie voprosy kriptografii, Tome 15 (2024) no. 2, pp. 47-68. http://geodesic.mathdoc.fr/item/MVK_2024_15_2_a3/

[1] GOST R 34.11-2012. Informatsionnaya tekhnologiya. Kriptograficheskaya zaschita informatsii. Funktsiya kheshirovaniya, Standartinform, M., 2012

[2] R 50.1.113-2016 Informatsionnaya tekhnologiya. Kriptograficheskaya zaschita informatsii. Kriptograficheskie algoritmy, soputstvuyuschie primeneniyu algoritmov elektronnoi tsifrovoi podpisi i funktsii kheshirovaniya, Standartinform, M., 2016

[3] Smyshlyaev S., Alekseev E., Oshkin I., Popov V., Leontiev S., Podobaev V., Belyavsky D., RFC 7836 - Guidelines on the Cryptographic Algorithms to Accompany the Usage of Standards GOST R 34.10-2012 and GOST R 34.11-2012, March 2016 | MR

[4] Secure Hash Standard (SHS), NIST FIPS – 180-4, 2015

[5] SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, NIST FIPS – 202, 2015

[6] Damgård I., “A design principle for hash functions”, CRYPTO 1989, Lect. Notes Comput. Sci., 435, 1990, 416–427 | DOI | MR | Zbl

[7] Merkle R., “One way wash functions and DES”, CRYPTO 1989, Lect. Notes Comput. Sci., 435, 1990, 428–446 | DOI | MR | Zbl

[8] Bellare M., Canetti R., Krawczyk H., “Keying Hash Functions for Message Authentication”, Crypto'96, Lect. Notes Comput. Sci., 1109, 1996, 1–15 | DOI | MR | Zbl

[9] Bellare M., Goldreich O., Mityagin A., The power of verification queries in message authentication and authenticated encryption, Cryptology ePrint Archive: Report 2004/304, 2004

[10] Bertoni G., Daemen J., Peeters M., Van Assche G., “On the security of the keyed sponge construction”, Symmetric Key Encryption Workshop, 2011

[11] Koblitz N., Menezes A., “Another look at HMAC”, J. Math. Cryptol., 7:3 (2013), 225–251 | DOI | MR | Zbl

[12] Bellare M., “New proofs for NMAC and HMAC: security without collision-resistance”, CRYPTO 2006, Lect. Notes Comput. Sci., 4117, April 2014, 602–619 | DOI | MR

[13] Krzysztof Pietrzak, A Closer Look at HMAC, Cryptology ePrint Archive 2013/212, , 2013 https://eprint.iacr.org/2013/212

[14] Gaži P., Pietrzak K., Rybár M., “The Exact PRF-Security of NMAC and HMAC”, CRYPTO 2014, Lect. Notes Comput. Sci., 8616, August 2014, 113–130 | DOI | MR | Zbl

[15] Bernstein D.J., Lange T., “Non-uniform cracks in the concrete: the power of free precomputation”, ASIACRYPT 2013, Lect. Notes Comput. Sci., 8270, 2013, 321–340 | DOI | MR | Zbl

[16] Alekseev E.K., Oshkin I.B., Popov V.O., Smyshlyaev S.V., “O kriptograficheskikh svoistvakh algoritmov, soputstvuyuschikh primeneniyu standartov GOST R 34.11-2012 i GOST R 34.10-2012”, Matematicheskie voprosy kriptografii, 7:1 (2016), 5–38 | DOI | MR | Zbl

[17] Nandi M., A New and Improved Reduction Proof of Cascade PRF, Cryptology ePrint Archive: Report 2021/097, 2021

[18] Bellare M., “Practice-Oriented Provable-Security”, ISW 97, Lect. Notes Comput. Sci., 1396, 1998, 221–231 | DOI | Zbl

[19] Guo J., Jean J., Leurent G., Peyrin T., Wang L., “The usage of counter revisited: second-preimage attack on new Russian standardized hash function”, SAC 2014, Lect. Notes Comput. Sci., 8781, 2014, 195–211 | DOI | MR | Zbl

[20] Dinur I., Leurent G., “Improved generic attacks against hash-based MACs and HAIFA”, CRYPTO 2014, Lect. Notes Comput. Sci., 8616, 2014, 149–168 | DOI | MR | Zbl

[21] Abdelkhalek A., AlTawy R., Youssef A. M., “Impossible differential properties of reduced round Streebog”, C2SI 2015, Lect. Notes Comput. Sci., 9084, 2015, 274–286 | DOI | MR | Zbl

[22] Kiryukhin V. A., “Streebog compression function as PRF in secret-key settings”, Matematicheskie voprosy kriptografii, 13:2 (2022), 99–116 | DOI | MR | Zbl

[23] Kiryukhin V. A., “Related-key attacks on the compression function of Streebog”, Matematicheskie voprosy kriptografii, 14:2 (2023), 59–76 | DOI | MR | Zbl

[24] AlTawy R., Youssef A. M., “Preimage attacks on reduced-round Stribog”, AFRICACRYPT 2014, Lect. Notes Comput. Sci., 8469, 2014, 109–125 | DOI | MR | Zbl

[25] AlTawy R., Kircanski A., Youssef A. M., “Rebound attacks on Stribog”, ICISC 2013, Lect. Notes Comput. Sci., 8565, 2014, 175–188 | DOI | MR | Zbl

[26] Jian Zou, Wenling Wu, and Shuang Wu, “Cryptanalysis of the round-reduced GOST hash function”, Inscrypt 2013, Lect. Notes Comput. Sci., 8567, 2014, 309–322 | DOI | Zbl

[27] Ma B., Li B., Hao R., Li X., “Improved cryptanalysis on reduced-round GOST and Whirlpool hash function”, ACNS 2014, Lect. Notes Comput. Sci., 8479, 2014, 289–307 | DOI | Zbl

[28] Wang Z., Yu H., Wang X., “Cryptanalysis of GOST R Hash Function”, Information Processing Letters, 114 (2014), 655–662 | DOI | Zbl

[29] Kölbl S., Rechberger C., “Practical attacks on AES-like cryptographic hash functions”, LATINCRYPT 2014, Lect. Notes Comput. Sci., 8895, 2014, 259–273 | DOI | MR

[30] Ma B., Li B., Hao R., Li X., “Improved (pseudo) preimage attacks on reduced-round GOST and Grøstl-256 and studies on several truncation patterns for AES-like compression functions”, IWSEC 2015, Lect. Notes Comput. Sci., 9241, 2015, 79–96 | DOI | Zbl

[31] Hua J., Dong X., Sun S., Zhang Z., Hu L., Wang X., Improved MITM Cryptanalysis on Streebog, Cryptology ePrint Archive, Paper 2022/568, 2022

[32] Kiryukhin V. A., “Keyed Streebog is a secure PRF and MAC”, Matematicheskie voprosy kriptografii, 14:2 (2023), 77–96 | DOI | MR | Zbl

[33] Kiryukhin V. A., About "$k$-bit security" of MACs based on hash function Streebog, Cryptology ePrint Archive, Paper 2023/1305, 2023