[cryptography] philosophical question about strengths and attacks at impossible levels

Marsh Ray marsh at extendedsubset.com
Thu Oct 14 17:20:05 EDT 2010


On 10/14/2010 02:49 PM, Samuel Neves wrote:
>   On 14-10-2010 19:32, Marsh Ray wrote:
>> 3. There are quantum computer attacks theorized which appear to cut
>> the exponent in half again. Thus a 256 bit hash could possibly be
>> collided in 264 operations on some future machine.
> Is there a source for this? The only quantum approach I've heard of, the
> Brassard-Høyer-Tapp algorithm, takes 2^(n/3) time (and space!).

Keep in mind this was me guessing about someone else's reasoning, but it 
probably still holds for 2^(n/3).

I'd inferred people might be think that way from some security claims on 
a specific SHA-3 candidate function:
http://cubehash.cr.yp.to/submission2/strength.pdf dated 2009-09-14.
"256-bit preimage resistance. CubeHash–256 is expected to provide 
preimage resistance of approximately 256 bits, but quantum computers are 
expected to reduce preimage resistance to approximately 128 bits."

Of course, that was about preimage resistance of a specific function, 
CubeHash, not collision resistance in general. In fact, that same author 
claims that all current quantum collision attacks are actually worse 
than conventional ones: http://cr.yp.to/papers.html#collisioncost

CubeHash has a simple and highly regular internal structure with no 
resistance to meet-in-the-middle attacks other than its large 1024 bit 
internal state. Previously, it had been "observed" that for functions of 
this general design, (and I hope I'm stating this correctly) if anyone 
did the work to find a second preimage of the all-zeroes message, they 
would be then able to generate second preimages for any message at all 
for O(1). As you can expect, the practical significance of this was 
somewhat controversial.

But now it gets interesting:

Gaëtan Leurent then proposes a 2^192 quantum preimage attack (on this 
nominally 512-bit hash function):
      http://eprint.iacr.org/2010/506

It employs Grover's algorithm for O(N^(1/2)) searching:
     http://en.wikipedia.org/wiki/Grover%27s_algorithm

Given that a collision cannot be harder to find than a second preimage, 
and a second preimage cannot be harder to find than a first preiamge, 
and here was a proposed 2^192 on a 512-bit output-length function, it 
seemed like someone might have a tiny bit of justification to not feel 
entirely comfortable with "only" a 256-bit hash function.

- Marsh



More information about the cryptography mailing list