[cryptography] GOST attack

Rose, Greg ggr at qualcomm.com
Tue Jun 14 14:34:43 EDT 2011


On 2011 Jun 14, at 10:47 , Jean-Philippe Aumasson wrote:

> On Tue, Jun 14, 2011 at 7:13 PM, Nico Williams <nico at cryptonector.com> wrote:
>> On Tue, Jun 14, 2011 at 7:31 AM, Jean-Philippe Aumasson
>> <jeanphilippe.aumasson at gmail.com> wrote:
>> 
>> (...)
>> 
>> It is not reasonable to consider an attack with a 2^228 work factor as
>> breaking a cipher, nor is it reasonable to say that because this 2^28
>> times faster than a brute force attack that this is a break (also, the
>> 2^64 storage requirement means that this attack is only ~2^23 times
>> faster than brute force, because the random access to that storage
>> won't be free).  Perhaps that's a typo and the author meant 2^28?
>> *That* would be a break, even with a 2^64 storage requirement.  But
>> skimming the paper it does not seem to be a typo.
> 
> Your argument perfectly makes sense. However, academic attack models
> generally consider a cipher as broken as soon as an attack is found
> that contradicts the claim of X-bit security, even when the reduction
> of complexity is practically insignificant. When the attack requires a
> non-negligible amount of memory, yet does fewer than 2^X
> "computations", it can be difficult to evaluate whether it really
> outperforms (in theory) bruteforce methods.

There are also "standard" Time-Memory-Trade-Off (TMTO)
attack methods that can sometimes be applied to things
like this. In this case it isn't clear to me that the
attack is any better than a generic TMTO attack on any
block cipher with 64-bit block and 256-bit key when 2^64
memory is available. Hence I'm in the "no attack here,
move on" camp.

Greg.


More information about the cryptography mailing list