UCL  IRIS
Institutional Research Information Service
UCL Logo
Please report any queries concerning the funding data grouped in the sections named "Externally Awarded" or "Internally Disbursed" (shown on the profile page) to your Research Finance Administrator. Your can find your Research Finance Administrator at http://www.ucl.ac.uk/finance/research/post_award/post_award_contacts.php by entering your department
Please report any queries concerning the student data shown on the profile page to:

Email: portico-services@ucl.ac.uk

Help Desk: http://www.ucl.ac.uk/ras/portico/helpdesk
Publication Detail
Black-Box Collision Attacks on the Compression Function of the GOST Hash Function
  • Publication Type:
    Conference
  • Authors:
    COURTOIS N, Mourouzis T
  • Publisher:
    SciTePress 2011
  • Place of publication:
    Seville, Spain
  • Published proceedings:
    SECRYPT 2011, Proceedings of the 6th International Conference on Security and Cryptography
  • Series:
    SECRYPT is part of ICETE - The International Joint Conference on E-Business and Telecom Networks
  • Status:
    In preparation
  • Name of conference:
    SECRYPT 2011
  • Conference place:
    Seville, Spain
  • Conference start date:
    18/07/2011
  • Conference finish date:
    21/07/2011
  • Keywords:
    hash functions, block ciphers, GOST, compression function, cryptanalysis, generic attacks, collisions
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 296 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 blackbox 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.
Publication data is maintained in RPS. Visit https://rps.ucl.ac.uk
 More search options
UCL Researchers
Author
Dept of Computer Science
University College London - Gower Street - London - WC1E 6BT Tel:+44 (0)20 7679 2000

© UCL 1999–2011

Search by