BLACK-BOX COLLISION ATTACKS ON THE COMPRESSION FUNCTION OF THE GOST HASH FUNCTION

Nicolas T. Courtois, Theodosis Mourouzis

2011

Abstract

The GOST hash function and more precisely GOST 34.11-94 is a cryptographic hash function and the official government standard of the Russian Federation. It is a key component in the national Russian digital signature standard. The GOST hash function is a 256-bit iterated hash function with an additional checksum computed over all input message blocks. Inside the GOST compression function, we find the standard GOST block cipher, which is an instantiation of the official Russian national encryption standard GOST 28147-89. In this paper we focus mostly on the problem of finding collisions on the GOST compression function. At Crypto 2008 a collision attack on the GOST compression function requiring $2^{96}$ evaluations of this function was found. In this paper, we present a new collision attack on the GOST compression function which is fundamentally different and more general than the attack published at Crypto 2008. Our new attack is a black-box attack which does not need any particular weakness to exist in the GOST block cipher, and works also if we replace GOST by another cipher with the same block and key size. Our attack is also slightly faster and we also show that the complexity of the previous attack can be slightly improved as well. Since GOST has an additional checksum computed over all blocks, it is not obvious how a collision attack on the GOST compression function can be extended to a collision attack on the hash function. In 2008 Gauravaram and Kelsey develop a technique to achieve this, in the case in which the checksum is linear or additive, using the Camion-Patarin-Wagner generalized birthday algorithm. Thus at Crypto 2008 the authors were also able to break the collision resistance of the complete GOST Hash function. Our attack is more generic and shows that the GOST compression function can be broken whatever is the underlying block cipher, but remains an attack on the compression function. It remains an open problem how and if this new attack can be extended to a collision attack on the full GOST hash function.

Paper Citation

in Harvard Style

T. Courtois N. and Mourouzis T. (2011). BLACK-BOX COLLISION ATTACKS ON THE COMPRESSION FUNCTION OF THE GOST HASH FUNCTION . In Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2011) ISBN 978-989-8425-71-3, pages 325-332. DOI: 10.5220/0003525103250332

in Bibtex Style

@conference{secrypt11,
author={Nicolas T. Courtois and Theodosis Mourouzis},
title={BLACK-BOX COLLISION ATTACKS ON THE COMPRESSION FUNCTION OF THE GOST HASH FUNCTION},
booktitle={Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2011)},
year={2011},
pages={325-332},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003525103250332},
isbn={978-989-8425-71-3},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2011)
TI - BLACK-BOX COLLISION ATTACKS ON THE COMPRESSION FUNCTION OF THE GOST HASH FUNCTION
SN - 978-989-8425-71-3
AU - T. Courtois N.
AU - Mourouzis T.
PY - 2011
SP - 325
EP - 332
DO - 10.5220/0003525103250332