[cryptography] philosophical question about strengths and attacks at impossible levels
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
But now it gets interesting:
Gaëtan Leurent then proposes a 2^192 quantum preimage attack (on this
nominally 512-bit hash function):
It employs Grover's algorithm for O(N^(1/2)) searching:
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.
More information about the cryptography