Paper 2014/319

Preimage attacks on Reduced-round Stribog

Riham AlTawy and Amr M. Youssef

Abstract

In August 2012, the Stribog hash function was selected as the new Russian cryptographic hash standard (GOST R 34.11-2012). Stribog employs twelve rounds of an AES-based compression function operating in Miyaguchi-Preneel mode. In this paper, we investigate the preimage resistance of the Stribog hash function. Specifically, we apply a meet in the middle preimage attack on the compression function which allows us to obtain a 5-round pseudo preimage for a given compression function output with time complexity of $2^{448}$ and memory complexity of $2^{64}$. Additionally, we adopt a guess and determine approach to obtain a 6-round chunk separation that balances the available degrees of freedom and the guess size. The proposed chunk separation allows us to attack 6 out of 12 rounds with time and memory complexities of $2^{496}$ and $2^{112}$, respectively. Finally, employing $2^t$ multicollision, we show that preimages of the 5 and 6-round reduced hash function can be generated with time complexity of $2^{481}$ and $2^{505}$, respectively. The two preimage attacks have equal memory complexity of $2^{256}$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. AfricaCrypt 2014
Keywords
CryptanalysisHash functionsMeet in the middlePreimage attackGOST R 34.11-2012Stribog
Contact author(s)
rihammahdy @ hotmail com
History
2014-05-06: received
Short URL
https://ia.cr/2014/319
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/319,
      author = {Riham AlTawy and Amr M.  Youssef},
      title = {Preimage attacks on Reduced-round Stribog},
      howpublished = {Cryptology ePrint Archive, Paper 2014/319},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/319}},
      url = {https://eprint.iacr.org/2014/319}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.