Prev: Solve the code
Next: Secret Sharing - Error Correction Coding (Shamir)
From: nobody on 7 Jul 2010 19:29
i read on wiki that the gost hash was broke and was wondering if someone
could explain at what level? like to a newbie, is it now worthless or is
the attack minor? any opinions on the hash or the actually algorithm
welcomed.

From: Francois Grieu on 8 Jul 2010 02:42
On 08/07/2010 01:29, it was asked:
> i read on wiki that the gost hash was broke and was wondering if someone
> could explain at what level? like to a newbie, is it now worthless or is
> the attack minor? any opinions on the hash or the actually algorithm
> welcomed.

The best cryptanalysis of the GOST 34.11-94 hash that I could locate are

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

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

both available at
<http://www.iaik.tugraz.at/content/about_iaik/people/mendel_florian/>

The attacks do break the algorithm, i nthe sense that they are
significantly faster than brute force would be: 2^128 compression
functions for collision, 2^256 for preimage.

These attacks are theoretical : the cost of the "fastest" one if about
2^105 evaluations of the compression function (and only aims at finding
a collision, not a preimage). This is about a million million times more
than the biggest attack on hashes I know to have ever been attempted in
practice. You can rest assured that direct implementation of these
attacks is infeasible for a very long time, and is not a practical
threat in the foreseeable future.

However, attacks only get better. I would not bet the house that Florian
Mendel will be surpassed significantly, but it is perfectly conceivable
that much better attacks could appear.


Francois Grieu
 | 
Pages: 1
Prev: Solve the code
Next: Secret Sharing - Error Correction Coding (Shamir)