Re: [Cfrg] would it be a good idea for CFRG to try review algorithm documents?

["Blumenthal, Uri - 0553 - MITLL" <[e-mail]>]

On 12/11/15, 11:57 , "Tom Ritter" <[e-mail]> wrote:

>On 10 December 2015 at 09:00, Blumenthal, Uri - 0553 - MITLL
><[e-mail]> wrote:
>> GOST has been reviewed and analyzed by the cryptographic community
>> (academia included) for ages (well, decades, really). I’ve seen several
>> publications. As I recall, the only significant weakness found was
>>related
>> to related-keys <pun intended :>. Of course it uses 64-bit blocks in the
>> world where (most) everybody embraced 128-bit, and some toy with 256-bit
>> block ciphers.
>
>I thought there were several slide attacks on GOST (I assume the old
>'Magma' version, but I am unsure) that significantly weaken it from
>it's purported keylength (but are still not computable breaks.)  I
>believe they kicked off with Isobe's paper in 2011[0] and then were
>improved by a number of people e.g. [1].
>
>[0] https://www.iacr.org/archive/fse2011/67330297/67330297.pdf
>[1] https://eprint.iacr.org/2011/558.pdf

Funny, I missed the Dinur--Shamir’s paper! Oh well. Yes, it’s against the
old GOST, now named “Magma” (as opposed to the new one named “Grasshopper”
or “Kuznechik").

The summary is: Isobe’s attack is 2^224 time complexity, 2^32 known
plaintext pairs (half the dictionary), 2^64 memory.
Shamir’s attack: either 2^192 time complexity, 2^64 data (full
dictionary), and 2^36 memory - or 2^236 time complexity, 2^32 data, and
2^19 memory.

The best attack shaves 64 bits (a lot!) off the 256-bit key, at the cost
of pretty much having the complete dictionary, and still impractical
computations. The authors pointed out that GOST’s simplistic key schedule
contributes to the effectiveness of these attacks.

Very neat result. Of course those, whose data is protected by “Magma”
don’t need to lose sleep just yet, as the authors stated. :-)