Difference between revisions of "GOST"

From The ECRYPT Hash Function Website
(→‎Best Known Results)
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
== Specification ==
 
== Specification ==
  
 +
* digest size: 256 bits
 
<!--  
 
<!--  
−
* digest size: 160 bits
 
 
* max. message length: < 2<sup>64</sup> bits
 
* max. message length: < 2<sup>64</sup> bits
−
* compression function: 512-bit message block, 160-bit chaining variable
+
-->
 +
* compression function: 256-bit message block, 256-bit chaining variable
 
* Specification:  
 
* Specification:  
−
-->
+
 
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
Line 13: Line 14:
 
=== Best Known Results ===
 
=== Best Known Results ===
  
 +
The best collision attack on GOST was published by Mendel et al. It has complexity of 2<sup>105</sup> compression function evaluations. The best preimage and second preimage attack has complexity of 2<sup>192</sup> compression function evaluations.
 
----
 
----
  
Line 21: Line 23:
  
 
=== Collision Attacks ===
 
=== Collision Attacks ===
 +
 +
<bibtex>
 +
@inproceedings{cryptoMendelPRKS08,
 +
  author    = {Florian Mendel and Norbert Pramstaller and Christian Rechberger and Marcin Kontak and Janusz Szmidt},
 +
  title    = {Cryptanalysis of the GOST Hash Function},
 +
  booktitle = {CRYPTO},
 +
  year      = {2008},
 +
  pages    = {162-178},
 +
  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 2^105 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 2^192 evaluations of the compression function. },
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-85174-5_10},
 +
  editor    = {David Wagner},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {5157},
 +
  isbn      = {978-3-540-85173-8},
 +
}
 +
</bibtex>
  
 
----
 
----
Line 30: Line 49:
 
=== Preimage Attacks ===
 
=== Preimage Attacks ===
  
 +
<bibtex>
 +
@inproceedings{fseMendelPR08,
 +
  author    = {Florian Mendel and Norbert Pramstaller and Christian Rechberger},
 +
  title    = {A (Second) Preimage Attack on the GOST Hash Function},
 +
  booktitle = {FSE},
 +
  year      = {2008},
 +
  pages    = {224-234},
 +
  abstract  = {In this article, we analyze the security of the GOST hash function with respect to (second) preimage resistance. The GOST hash function, defined in the Russian standard GOST-R 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 iterated structure, a checksum computed over all input message blocks. This checksum is then part of the final hash value computation. For this hash function, we show how to construct second preimages and preimages with a complexity of about 2^225 compression function evaluations and a memory requirement of about 2^38 bytes. First, we show how to construct a pseudo-preimage for the compression function of GOST based on its structural properties. Second, this pseudo-preimage attack on the compression function is extended to a (second) preimage attack on the GOST hash function. The extension is possible by combining a multicollision attack and a meet-in-the-middle attack on the checksum.},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-71039-4_14},
 +
  editor    = {Kaisa Nyberg},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {5086},
 +
  isbn      = {978-3-540-71038-7},
 +
}
 +
</bibtex>
  
 
----
 
----
  
 
=== Others ===
 
=== Others ===
 +
 +
<bibtex>
 +
@inproceedings{ctrsaGauravaramK08,
 +
  author    = {Praveen Gauravaram and John Kelsey},
 +
  title    = {Linear-XOR and Additive Checksums Don't Protect Damg{\aa}rd-Merkle Hashes from Generic Attacks},
 +
  booktitle = {CT-RSA},
 +
  year      = {2008},
 +
  pages    = {36-51},
 +
  abstract  = {We consider the security of Damgaard-Merkle variants which compute linear-XOR or additive checksums over message blocks, intermediate hash values, or both, and process these checksums in computing the final hash value. We show that these Damgård-Merkle variants gain almost no security against generic attacks such as the long-message second preimage attacks of [10,21] and the herding attack of [9].},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-79263-5_3},
 +
  editor    = {Tal Malkin},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4964},
 +
  isbn      = {978-3-540-79262-8},
 +
}
 +
</bibtex>

Latest revision as of 12:03, 10 November 2008

1 Specification

  • digest size: 256 bits
  • compression function: 256-bit message block, 256-bit chaining variable
  • Specification:


2 Cryptanalysis

2.1 Best Known Results

The best collision attack on GOST was published by Mendel et al. It has complexity of 2105 compression function evaluations. The best preimage and second preimage attack has complexity of 2192 compression function evaluations.

2.2 Generic Attacks

2.3 Collision Attacks

Florian Mendel, Norbert Pramstaller, Christian Rechberger, Marcin Kontak, Janusz Szmidt - Cryptanalysis of the GOST Hash Function

CRYPTO 5157:162-178,2008
http://dx.doi.org/10.1007/978-3-540-85174-5_10
Bibtex
Author : Florian Mendel, Norbert Pramstaller, Christian Rechberger, Marcin Kontak, Janusz Szmidt
Title : Cryptanalysis of the GOST Hash Function
In : CRYPTO -
Address :
Date : 2008

2.4 Second Preimage Attacks

2.5 Preimage Attacks

Florian Mendel, Norbert Pramstaller, Christian Rechberger - A (Second) Preimage Attack on the GOST Hash Function

FSE 5086:224-234,2008
http://dx.doi.org/10.1007/978-3-540-71039-4_14
Bibtex
Author : Florian Mendel, Norbert Pramstaller, Christian Rechberger
Title : A (Second) Preimage Attack on the GOST Hash Function
In : FSE -
Address :
Date : 2008

2.6 Others

Praveen Gauravaram, John Kelsey - Linear-XOR and Additive Checksums Don't Protect Damg{\aa}rd-Merkle Hashes from Generic Attacks

CT-RSA 4964:36-51,2008
http://dx.doi.org/10.1007/978-3-540-79263-5_3
Bibtex
Author : Praveen Gauravaram, John Kelsey
Title : Linear-XOR and Additive Checksums Don't Protect Damg{\aa}rd-Merkle Hashes from Generic Attacks
In : CT-RSA -
Address :
Date : 2008
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=GOST&oldid=2254"