``Sandwich''-like keyed algorithm based on the ``Streebog'' hash function

V. A. Kiryukhin ; A. M. Sergeev

Prikladnaâ diskretnaâ matematika, no. 1 (2024), pp. 24-48.

Résumé

We propose a keyed cryptographic algorithm based on the “Streebog” hash function. We do not make any structural changes to the hash function itself, but only introduce a special type of padding. As a result, the key appears on both sides of the message in so-called “sandwich” manner — hence the name Streebog-S for our construction. “Sandwich” properties make it possible to simplify defenses against side-channel attacks while maintaining their effectiveness. We prove that Streebog-S and other algorithms based on “Streebog”, HMAC-Streebog and Streebog-K, remain secure as pseudorandom functions (PRF) and message authentication codes (MAC) even when almost all internal states are leaked to the adversary. This leakage resistance requires additional properties from the underlying compression function, namely collision- and preimage-resistance.

Détail

Mots-clés : Streebog
Keywords: PRF, HMAC, provable security.

Bibliographie

[1] GOST R 34.11-2018. Information Technology. Cryptographic Data Security. Hash-function, Standartinform Publ., M., 2018 (in Russian)

[2] Damgard I., “A design principle for hash functions”, LNCS, 435, 1990, 416–427 | MR | Zbl

[3] Merkle R., “One way hash functions and DES”, LNCS, 435, 1990, 428–446 | MR

[4] R 50.1.113-2016. Information Technology. Cryptographic Data Security. Cryptographic Algorithms Accompanying the Use of Electronic Digital Signature Algorithms and Hash Functions, Standartinform Publ., M., 2016 (in Russian)

[5] Kiryukhin V. A., “Keyed Streebog is a secure PRF and MAC”, Mat. Vopr. Kriptogr., 14:2 (2023), 77–96 | DOI | MR | Zbl

[6] Kiryukhin V. A., About "$k$-bit Security" of MACs Based on Hash Function Streebog, Cryptology ePrint Archive. Paper 2023/1305, , 2023 https://eprint.iacr.org/2023/1305

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

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

[9] Dinur I. and Leurent G., “Improved generic attacks against hash-based MACs and HAIFA”, LNCS, 8616, 2014, 149–168 | MR | Zbl

[10] Goubin L., “A Sound method for switching between Boolean and arithmetic masking”, LNCS, 2162, 2001, 3–15 | MR | Zbl

[11] Coron J., Großschädl J., Tibouchi M., and Vadnala P. K., “Conversion from arithmetic to Boolean masking with Logarithmic complexity”, LNCS, 9054, 2015, 130–149 | Zbl

[12] Yasuda K., ““Sandwich” is indeed secure: How to authenticate a message with just one hashing”, LNCS, 4586, 2007, 355–369 | Zbl

[13] Bellare M., Goldreich O., and Mityagin A., The Power of Verification Queries in Message Authentication and Authenticated Encryption, Cryptology ePrint Archive. Paper 2004/304, , 2004 https://eprint.iacr.org/2004/304

[14] Blömer J., Merchan J., and Krummel V., “Provably secure masking of AES”, LNCS, 3357, 2004, 69–83 | MR

[15] Nikova S., Rechberger C., and Rijmen V., “Threshold implementations against side-channel attacks and glitches”, LNCS, 4307, 2006, 529–545 | MR | Zbl

[16] Lavrenteva T. A. and Matveev S. V., “Side-channel attacks countermeasure based on decomposed S-boxes for Kuznyechik”, Mat. vopr. kriptogr., 12:2 (2021), 147–157 | DOI | MR | Zbl

[17] Bellare M. and Rogaway P., Introduction to Modern Cryptography, 2005 https://web.cs.ucdavis.edu/r̃ogaway/classes/227/spring05/book/main.pdf

[18] Bernstein D. J. and Lange T., “Non-uniform cracks in the concrete: The power of free precomputation”, LNCS, 8270, 2013, 321–340 | MR | Zbl

[19] Guo J., Jean J., Leurent G., et al., “The usage of counter revisited: Second-preimage attack on new Russian standardized hash function”, LNCS, 8781, 2014, 195–211 | MR | Zbl

[20] Abdelkhalek A., AlTawy R., and Youssef A. M., “Impossible differential properties of reduced round Streebog”, LNCS, 9084, 2015, 274–286 | MR | Zbl

[21] Rogaway P. and Shrimpton T., “Cryptographic hash-function basics: Definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance”, LNCS, 3017, 2004, 371–388 | Zbl

[22] AlTawy R., Kircanski A., and Youssef A. M., “Rebound attacks on Stribog”, LNCS, 8565, 2014, 175–188 | MR | Zbl

[23] Lin D., Xu S., and Yung M., “Cryptanalysis of the round-reduced GOST hash function”, LNCS, 8567, 2014, 309–322 | MR | Zbl

[24] Ma B., Li B., Hao R., and Li X., “Improved cryptanalysis on reduced-round GOST and Whirlpool hash function”, LNCS, 8479, 2014, 289–307 | Zbl

[25] Wang Z., Yu H., and Wang X., “Cryptanalysis of GOST R hash function”, Inform. Processing Lett., 114 (2014), 655–662 | DOI | Zbl

[26] Kölbl S. and Rechberger C., “Practical attacks on AES-like cryptographic hash functions”, LNCS, 8895, 2014, 259–273 | MR

[27] Van Oorschot P. C. and Wiener M. J., “Parallel collision search with cryptanalytic applications”, J. Cryptology, 12:1 (1999), 1–28 | DOI | MR | Zbl

[28] AlTawy R. and Youssef A. M., “Preimage attacks on reduced-round Stribog”, LNCS, 8469, 2014, 109–125 | Zbl

[29] Ma B., Li B., Hao R., and Li X., “Improved (pseudo) preimage attacks on reduced-round GOST and Grostl-256 and studies on several truncation patterns for AES-like compression functions”, LNCS, 9241, 2015, 79–96 | Zbl

[30] Hua J., Dong X., Sun S., et al., Improved MITM Cryptanalysis on Streebog, Cryptology ePrint Archive. Paper 2022/568, , 2022 https://eprint.iacr.org/2022/568 | MR

[31] Bellare M., Jaeger J., and Len J., “Better than advertised: Improved collision-resistance guarantees for MD-based hash functions”, Proc. CCS'17, ACM, N.Y., 2017, 891–906

[32] Bellare M., “New proofs for NMAC and HMAC: Security without collision-resistance”, LNCS, 4117, 2014, 602–619 | MR

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

[34] Repozitorii «Klyuchevoi Stribog», https://gitflic.ru/project/vkir/streebog

[35] GOST R 34.11-94. Information Technology. Cryptographic Data Security. Hash-function, Izdatelstvo Standartov, M., 1994 (in Russian)

[36] GOST 34.13-2018. Information Technology. Modes of Operation for Block Ciphers, Standartinform Publ., M., 2018 (in Russian)

[37] Biham E. and Dunkelman O., A Framework for Iterative Hash Functions — HAIFA, Cryptology ePrint Archive. Report 2007/278, , 2007 https://eprint.iacr.org/2007/278

[38] Ferguson N., Lucks S., Schneier B., et al., The Skein Hash Function Family, 2009 https://api.semanticscholar.org/CorpusID:59739596

[39] Aumasson J., Neves S., Wilcox-O'Hearn Z., and Winnerlein C., BLAKE2: Simpler, Smaller, Fast as MD5, IACR Cryptology ePrint Archive. Report 2013/322, , 2013 https://eprint.iacr.org/2013/322.pdf

[40] Kelsey J., Chang S., and Perlner R., SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash, NIST Special Publication 800-185, 2016 | DOI

[41] Goubin L. and Patarin J., “DES and differential power analysis. The “Duplication” Method”, LNCS, 1717, 1999, 158–172 | Zbl

[42] Oswald E., Mangard S., Pramstaller N., and Rijmen V., “A side-channel analysis resistant description of the AES S-Box”, LNCS, 3557, 2005, 413–423 | Zbl

[43] Bilgin B., Nikova S., Nikov V., et al., “Threshold implementations of all $3 \times3$ and $4\times4$ S-boxes”, LNCS, 7428, 2012, 76–91 | Zbl

[44] Daemen J., “Changing of the guards: A simple and efficient method for achieving uniformity in threshold sharing”, LNCS, 10529, 2017, 137–153 | Zbl

[45] Piccione E., Andreoli S., Budaghyan L., et al., “An optimal universal construction for the threshold implementation of bijective S-boxes”, IEEE Trans. Inform. Theory, 69:10 (2023), 6700–6710 | DOI | MR