Cryptanalysis of the GOST Hash Function

Florian Mendel; Norbert Pramstaller; Christian Rechberger; Marcin Kontak; Janusz Szmidt

doi:10.1007/978-3-540-85174-5_10

Cryptanalysis of the GOST Hash Function

Florian Mendel
, Norbert Pramstaller
, Christian Rechberger
, Marcin Kontak
, Janusz Szmidt

Institute of Information Security (7050)

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

Abstract

In this article, we analyze the security of the GOST hash function. The GOST hash function, defined in the Russian standard GOST 34.11-94, is an iterated hash function producing a 256-bit hash value. As opposed to most commonly used hash functions such as MD5 and SHA-1, the GOST hash function defines, in addition to the common iterative structure, a checksum computed over all input message blocks. This checksum is then part of the final hash value computation.

As a result of our security analysis of the GOST hash function, we present the first collision attack with a complexity of about 2105 evaluations of the compression function. Furthermore, we are able to significantly improve upon the results of Mendel et al. with respect to preimage and second preimage attacks. Our improved attacks have a complexity of about 2192 evaluations of the compression function.

Originalsprache	englisch
Titel	Advances in Cryptology - Proceedings CRYPTO 2008
Redakteure/-innen	Dongdai Lin
Herausgeber (Verlag)	Springer
Seiten	162-178
ISBN (Print)	978-3-540-85173-8
DOIs	https://doi.org/10.1007/978-3-540-85174-5_10
Publikationsstatus	Veröffentlicht - 2008
Veranstaltung	Crypto 2008: CRYPTO 2008 - Santa Barbara, USA / Vereinigte Staaten Dauer: 17 Aug. 2008 → 21 Aug. 2008

Publikationsreihe

Name	Lecture Notes in Computer Science
Herausgeber (Verlag)	Springer
Band	5157

Konferenz

Konferenz	Crypto 2008
Kurztitel	CRYPTO 2008
Land/Gebiet	USA / Vereinigte Staaten
Ort	Santa Barbara
Zeitraum	17/08/08 → 21/08/08

Zugriff auf Dokument

10.1007/978-3-540-85174-5_10

web_mendelEndgültige, publizierte Fassung, 341 KB

FWF - Kryptoanalyse - Kryptoanalyse basierend auf numerischen Methoden
Schläffer, M. (Teilnehmer / Mitarbeiter), Lamberger, M. (Teilnehmer / Mitarbeiter), Rechberger, C. (Teilnehmer / Mitarbeiter), Nad, T. (Teilnehmer / Mitarbeiter), Rijmen, V. (Projektleiter) & Mendel, F. (Teilnehmer / Mitarbeiter)
1/10/07 → 30/09/09
Projekt: Forschungsprojekt
A-SIT - Zentrum für sichere Informationstechnologie Austria
Posch, R. (Projektleiter), Oswald, M. E. (Sonstige Funktion), Payer, U. (Sonstige Funktion), Neuherz, E. (Sonstige Funktion), Ivkovic, M. (Teilnehmer), Tauber, A. (Teilnehmer), Reiter, A. (Teilnehmer), Zefferer, T. (Teilnehmer), Kreuzhuber, S. (Teilnehmer), Rössler, T. (Sonstige Funktion), Mangard, S. (Teilnehmer), Bratko, H. (Sonstige Funktion), Dietrich, K. (Teilnehmer), Stranacher, K. (Teilnehmer), Bonato, M. (Sonstige Funktion), Bauer, W. (Teilnehmer), Orthacker, C. (Teilnehmer), Wolkerstorfer, J. (Teilnehmer), Zwattendorfer, B. (Teilnehmer), Aigner, M. J. (Sonstige Funktion), Scheibelhofer, K. (Sonstige Funktion), Suzic, B. (Teilnehmer), Knall, T. (Sonstige Funktion), Leitold, H. (Koordinator), Bratko, D. (Teilnehmer), Dominikus, S. (Teilnehmer), Lipp, P. (Teilnehmer), Marsalek, A. (Teilnehmer), Reimair, F. (Teilnehmer), Feichtner, J. (Teilnehmer) & Teufl, P. (Teilnehmer)
21/05/99 → 31/12/24
Projekt: Arbeitsgebiet
Cryptography
Schläffer, M. (Teilnehmer), Rijmen, V. (Koordinator), Oswald, M. E. (Kontaktperson), Rechberger, C. (Teilnehmer), Posch, R. (Kontaktperson), Lamberger, M. (Teilnehmer), Mendel, F. (Teilnehmer), Eichlseder, M. (Teilnehmer), Nad, T. (Teilnehmer), Dobraunig, C. E. (Teilnehmer) & Lipp, P. (Teilnehmer)
1/01/95 → 31/01/19
Projekt: Arbeitsgebiet

Dieses zitieren

@inproceedings{9000093ef1ac4956a26a206272ece839,

title = "Cryptanalysis of the GOST Hash Function",

abstract = "In this article, we analyze the security of the GOST hash function. The GOST hash function, defined in the Russian standard GOST 34.11-94, is an iterated hash function producing a 256-bit hash value. As opposed to most commonly used hash functions such as MD5 and SHA-1, the GOST hash function defines, in addition to the common iterative structure, a checksum computed over all input message blocks. This checksum is then part of the final hash value computation. As a result of our security analysis of the GOST hash function, we present the first collision attack with a complexity of about 2105 evaluations of the compression function. Furthermore, we are able to significantly improve upon the results of Mendel et al. with respect to preimage and second preimage attacks. Our improved attacks have a complexity of about 2192 evaluations of the compression function.",

author = "Florian Mendel and Norbert Pramstaller and Christian Rechberger and Marcin Kontak and Janusz Szmidt",

year = "2008",

doi = "10.1007/978-3-540-85174-5\_10",

language = "English",

isbn = "978-3-540-85173-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "162--178",

editor = "Dongdai Lin",

booktitle = "Advances in Cryptology - Proceedings CRYPTO 2008",

address = "United States",

note = "28th Annual International Cryptology Conference : CRYPTO 2008, CRYPTO 2008 ; Conference date: 17-08-2008 Through 21-08-2008",

}

TY - GEN

T1 - Cryptanalysis of the GOST Hash Function

AU - Mendel, Florian

AU - Pramstaller, Norbert

AU - Rechberger, Christian

AU - Kontak, Marcin

AU - Szmidt, Janusz

PY - 2008

Y1 - 2008

N2 - In this article, we analyze the security of the GOST hash function. The GOST hash function, defined in the Russian standard GOST 34.11-94, is an iterated hash function producing a 256-bit hash value. As opposed to most commonly used hash functions such as MD5 and SHA-1, the GOST hash function defines, in addition to the common iterative structure, a checksum computed over all input message blocks. This checksum is then part of the final hash value computation. As a result of our security analysis of the GOST hash function, we present the first collision attack with a complexity of about 2105 evaluations of the compression function. Furthermore, we are able to significantly improve upon the results of Mendel et al. with respect to preimage and second preimage attacks. Our improved attacks have a complexity of about 2192 evaluations of the compression function.

AB - In this article, we analyze the security of the GOST hash function. The GOST hash function, defined in the Russian standard GOST 34.11-94, is an iterated hash function producing a 256-bit hash value. As opposed to most commonly used hash functions such as MD5 and SHA-1, the GOST hash function defines, in addition to the common iterative structure, a checksum computed over all input message blocks. This checksum is then part of the final hash value computation. As a result of our security analysis of the GOST hash function, we present the first collision attack with a complexity of about 2105 evaluations of the compression function. Furthermore, we are able to significantly improve upon the results of Mendel et al. with respect to preimage and second preimage attacks. Our improved attacks have a complexity of about 2192 evaluations of the compression function.

U2 - 10.1007/978-3-540-85174-5_10

DO - 10.1007/978-3-540-85174-5_10

M3 - Conference paper

SN - 978-3-540-85173-8

T3 - Lecture Notes in Computer Science

SP - 162

EP - 178

BT - Advances in Cryptology - Proceedings CRYPTO 2008

A2 - Lin, Dongdai

PB - Springer

T2 - 28th Annual International Cryptology Conference

Y2 - 17 August 2008 through 21 August 2008

ER -

Cryptanalysis of the GOST Hash Function

Abstract

Publikationsreihe

Konferenz

Zugriff auf Dokument

Fingerprint

Projekte

FWF - Kryptoanalyse - Kryptoanalyse basierend auf numerischen Methoden

A-SIT - Zentrum für sichere Informationstechnologie Austria

Cryptography

Dieses zitieren