Geodesic
Keyed Streebog is a secure PRF and MAC
Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 2, pp. 77-96 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

One of the most popular ways to turn a keyless hash function into a keyed one is the HMAC algorithm. This approach is too expensive in some cases due to double hashing. Excessive overhead can be avoided by using features of the hash function. The paper presents a simple and safe keyed cryptoalgorithm (conventionally called «Streebog-K») from hash function Streebog $\mathsf{H}(M)$. Let $K$ be a secret key, then $\mathsf{KH}(K,M)=\mathsf{H}(K||M)$ is a secure pseudorandom function (PRF) and, therefore, a good message authentification code (MAC). The proof is obtained by reduction of the security of the presented construction to the resistance of the underlying compression function to the related key attacks (PRF-RKA). The security bounds of Streebog-K are essentially the same as those of HMAC-Streebog, but the computing speed doubles when short messages are used. 
@article{MVK_2023_14_2_a4,
     author = {V. A. Kiryukhin},
     title = {Keyed {Streebog} is a secure {PRF} and {MAC}},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {77--96},
     year = {2023},
     volume = {14},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a4/}
}
TY  - JOUR
AU  - V. A. Kiryukhin
TI  - Keyed Streebog is a secure PRF and MAC
JO  - Matematičeskie voprosy kriptografii
PY  - 2023
SP  - 77
EP  - 96
VL  - 14
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a4/
LA  - en
ID  - MVK_2023_14_2_a4
ER  - 
%0 Journal Article
%A V. A. Kiryukhin
%T Keyed Streebog is a secure PRF and MAC
%J Matematičeskie voprosy kriptografii
%D 2023
%P 77-96
%V 14
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a4/
%G en
%F MVK_2023_14_2_a4
V. A. Kiryukhin. Keyed Streebog is a secure PRF and MAC. Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 2, pp. 77-96. http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a4/

[1] GOST R 34.11-2012-Information technology-Cryptographic data security-Hash function, National standard of the Russian Federation, STANDARTINFORM, M., 2012 (In Russian)

[2] GOST R 34.11-94-Information technology-Cryptographic data security-Hash function, National standard of the Russian Federation, STANDARTINFORM, M., 1994 (In Russian)

[3] R 50.1.113-2016-Information technology-Cryptographic data security-Cryptographic algorithms accompanying the use of electronic digital signature algorithms and hash functions, STANDARTINFORM, M., 2016 (In Russian)

[4] R 1323565.1.003-2017-Information technology-Cryptographic data security-Cryptographic algorithms for generating encryption keys and authentication vectors intended for implementation in hardware trust modules for use in mobile communication, STANDARTINFORM, M., 2017 (In Russian)

[5] Grebnev S., Dmukh A., Dygin D., Matyukhin D., Rudskoy V., Shishkin V., “Asymmetrical reply to SHA-3: Russian hash function draft standard”, CTCrypt 2012, 2012

[6] 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

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

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

[9] Bellare M., Canetti R., Krawczyk H., “Pseudorandom functions revisited: The cascade construction and its concrete security”, Proc. 37th FOCS, IEEE, 1996, 514–523 | MR

[10] 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

[11] Preneel B., van Oorschot P.C., “On the security of iterated message authentication codes”, IEEE Trans. Inf. Theory, 45 (1999), 188–199 | DOI | MR | Zbl

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

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

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

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

[16] Alekseev E.K., Oshkin I.B., Popov V.O., Smyshlyaev S.V., “On the cryptographic properties of algorithms accompanying the applications of standards GOST R 34.11-2012 and 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., Rogaway P., Introduction to Modern Cryptography, 2005, 283 pp. https://web.cs.ucdavis.edu

[19] Goldreich O., Foundations of Cryptography, v. 1, Basic Tools, Cambridge Univ. Press, 2008, 396 pp. | MR

[20] Joux A., “Multicollisions in iterated hash functions. Application to cascaded constructions”, CRYPTO 2004, Lect. Notes Comput. Sci., 3152, 2004, 306–316 | DOI | MR | Zbl

[21] Biham E., Dunkelman O., A framework for iterative hash functions (HAIFA), Cryptology ePrint Archive, Report 2007/278, 2007

[22] 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

[23] 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

[24] 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

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

[26] Kiryukhin V., “Related-key attacks on the compression function of Streebog”, Matematicheskie Voprosy Kriptografii, 14:2 (2023), 59–76 | MR

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

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

[29] Lin D., Xu S., Yung M., “Cryptanalysis of the round-reduced GOST hash function”, INSCRYPT 2013, Lect. Notes Comput. Sci., 8567, 2014, 309–322 | DOI | MR | Zbl

[30] 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

[31] Wang Z., Yu H., Wang X., “Cryptanalysis of GOST R hash function”, Inf. Process. Letters, 114 (2014), 655–662 | DOI | Zbl

[32] 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

[33] 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

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

[35] Kiryukhin V., Keyed Streebog is a secure PRF and MAC, https://eprint.iacr.org/2022/972.pdf