Paper 2014/675

The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function

Jian Guo, Jérémy Jean, Gaëtan Leurent, Thomas Peyrin, and Lei Wang

Abstract

Streebog is a new Russian hash function standard. It follows the HAIFA framework as domain extension algorithm and claims to resist recent generic second-preimage attacks with long messages. However, we demonstrate in this article that the specific instantiation of the HAIFA framework used in Streebog makes it weak against such attacks. More precisely, we observe that Streebog makes a rather poor usage of the HAIFA counter input in the compression function, which allows to construct second-preimages on the full Streebog-512 with a complexity as low as 2^{266} compression function evaluations for long messages. This complexity has to be compared with the expected 2^{512} computations bound that an ideal hash function should provide. Our work is a good example that one must be careful when using a design framework for which not all instances are secure. HAIFA helps designers to build a secure hash function, but one should pay attention to the way the counter is handled inside the compression function.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. SAC 2014
Keywords
Streebogcryptanalysissecond-preimage attackdiamond structureexpandable messageHAIFA
Contact author(s)
JJean @ ntu edu sg
History
2014-08-30: received
Short URL
https://ia.cr/2014/675
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/675,
      author = {Jian Guo and Jérémy Jean and Gaëtan Leurent and Thomas Peyrin and Lei Wang},
      title = {The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function},
      howpublished = {Cryptology ePrint Archive, Paper 2014/675},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/675}},
      url = {https://eprint.iacr.org/2014/675}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.