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.
Download file
Counter downloads: 92
- Title “Sandwich”-like keyed algorithm based on the “Streebog” hash function
- Headline “Sandwich”-like keyed algorithm based on the “Streebog” hash function
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 63
- Date:
- DOI 10.17223/20710410/63/2
Keywords
Streebog, PRF, HMAC, provable securityAuthors
References
ГОСТ 34.11-2018. Информационная технология. Криптографическая защита информации. функция хэширования. М.: Стандартинформ, 2018.
Damgard I. A design principle for hash functions // LNCS. 1990. V.435. P.416-427.
Merkle R. One way hash functions and DES // LNCS. 1990. V.435. P.428-446.
P 50.1.113-2016. Информационная технология. Криптографическая защита информации. Криптографические алгоритмы, сопутствующие применению алгоритмов электронной цифровой подписи и функции хэширования. М.: Стандартинформ, 2016.
Kiryukhin V. A. Keyed Streebog is a secure PRF and MAC // Матем. вопр. криптогр. 2023. T. 14. №2. С. 77-96.
Kiryukhin V. A. About “fc-bit Security” of MACs Based on Hash Function Streebog. Cryptology ePrint Archive. Paper 2023/1305. 2023. https://eprint.iacr.org/2023/1305.
Kiryukhin V. A. Streebog compression function as PRF in secret-key settings // Матем. вопр. криптогр. 2022. T. 13. №2. С. 99-116. Ключевой криптоалгоритм по схеме «сэндвич» на основе хеш-функции «Стрибог» 45.
Kiryukhin V. A. Related-kev attacks on the compression function of Streebog // Матем. вопр. криптогр. 2023. T. 14. №2. С. 59-76.
Dinur I. and Leurent G. Improved generic attacks against hash-based MACs and HAIFA // LNCS. 2014. V. 8616. P. 149-168.
Goubin L. A Sound method for switching between Boolean and arithmetic masking // LNCS. 2001. V. 2162. P.3-15.
Coron J., Grofischadl J., Tibouchi M., and Vadnala P.K. Conversion from arithmetic to Boolean masking with Logarithmic complexity // LNCS. 2015. V. 9054. P. 130-149.
Yasuda K. “Sandwich” is indeed secure: How to authenticate a message with just one hashing // LNCS. 2007. V.4586. P.355-369.
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.
Bldmer J., Merchan J., and Krummel V. Provablv secure masking of AES // LNCS. 2004. V. 3357. P. 69-83.
Nikova S., Rechberger C., and Rijmen V. Threshold implementations against side-channel attacks and glitches // LNCS. 2006. V.4307. P.529-545.
Lavrenteva T. A. and Matveev S. V. Side-channel attacks countermeasure based on decomposed S-boxes for Kuznvechik // Матем. вопр. криптогр. 2021. T. 12. №2. С. 147-157.
Bellare М. and Rogaway Р.Introduction to Modern Cryptography. 2005. https://web.cs.ucdavis.edu/~rogaway/classes/227/spring05/book/main.pdf.
Bernstein D. J. and Lange T. Non-uniform cracks in the concrete: The power of free precomputation // LNCS. 2013. V.8270. P.321-340.
Guo J., Jean J., Leurent G., et al. The usage of counter revisited: Second-preimage attack on new Russian standardized hash function // LNCS. 2014. V. 8781. P. 195-211.
Abdelkhalek A., AlTawy R., and Youssef A. M. Impossible differential properties of reduced round Streebog // LNCS. 2015. V.9084. P.274-286.
Rogaway P. and Shrimpton T. Cryptographic hash-function basics: Definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance // LNCS. 2004. V.3017. P.371-388.
AlTawy R., Kircanski A., and Youssef A. M. Rebound attacks on Stribog // LNCS. 2014. V. 8565. P.175-188.
Lin D., Xu S., and Yung M. Cryptanalysis of the round-reduced GOST hash function // LNCS. 2014. V. 8567. P. 309 322'.
Ma B., Li B., Hao R., and Li X. Improved cryptanalysis on reduced-round GOST and Whirlpool hash function // LNCS. 2014. V.8479*. P.289-307.
Wang Z., Yu H., and Wang X. Cryptanalysis of GOST R hash function // Inform. Processing Lett. 2014. V. 114. P. 655-662.
Kolbl S. and Rechberger C. Practical attacks on AES-like cryptographic hash functions // LNCS. 2014. V.8895. P.259-273.
Van Oorschot P. C. and Wiener M. J. Parallel collision search with crvptanalvtic applications //j. Cryptology. 1999. V. 12. No. 1. P.1-28.
AlTawy R. and Youssef A. M. Preimage attacks on reduced-round Stribog // LNCS. 2014. V. 8469. P.109-125.
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. 2015. V.9241. P.79-96.
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.
Bellare M., Jaeger J., and Lend. Better than advertised: Improved collision-resistance guarantees for MD-based hash functions // Proc. CCS’17. N.Y.: ACM, 2017. P.891-906.
Bellare M. New proofs for NMAC and HMAC: Security without collision-resistance // LNCS. 2014. V.4117. P.602-619.
Koblitz N. and Menezes A. Another look at HMAC //j. Math. Cryptology. 2013. V. 7:3. P.225-251.
Репозиторий «Ключевой Стрибог». https://gitflic.ru/project/vkir/streebog.
ГОСТ Р 34.11-94. Информационная технология. Криптографическая защита информации. функция хэширования. М.: Издательство Стандартов, 1994.
ГОСТ 34.13-2018. Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров. М.: Стандартинформ, 2018.
Biham, Е. and Dunkelman О. A Framework for Iterative Hash Functions - HAIFA. Cryptology ePrint Archive. Report 2007/278. 2007. https://eprint.iacr.org/2007/278.
Ferguson N., Lucks S., Schneier B., et al. The Skein Hash Function Family. 2009. https: //api.semanticscholar.org/CorpusID:59739596.
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.
Kelsey J., Chang S., and Perlner R. SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash. NIST Special Publication 800-185. 2016. https: //doi.org/10.6028/NIST. SP.800-185.
Goubin L. and Patarin J. DES and differential power analysis. The “Duplication” Method // LNCS. 1999. V. 1717. P. 158-172.
Oswald E., Mangard S., Pramstaller N., and Rijmen V. A side-channel analysis resistant description of the AES S-Box // LNCS. 2005. V. 3557. P. 413-423.
Bilgin B., Nikova S., Nikov V., et al. Threshold implementations of all 3 x 3 and 4 x 4 S-boxes // LNCS. 2012. V.7428. P.76-91.
Daemen J. Changing of the guards: A simple and efficient method for achieving uniformity in threshold sharing // LNCS. 2017. V. 10529. P. 137-153.
Piccione E., Andreoli S., Budaghyan L., et al. An optimal universal construction for the threshold implementation of bijective S-boxes // IEEE Trans. Inform. Theory. 2023. V. 69. No. 10. P.6700-6710.
“Sandwich”-like keyed algorithm based on the “Streebog” hash function | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 63. DOI: 10.17223/20710410/63/2
Download full-text version
Counter downloads: 102