[Cryptography] Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512 -

[Phillip Hallam-Baker]

On Tue, Dec 17, 2013 at 4:20 PM, Jerry Leichter <leichter at lrw.com> wrote:

> On Dec 17, 2013, at 8:12 AM, Phillip Hallam-Baker wrote:
> > This is not particularly impressive or worrisome. The attack is on a
> reduce strength version of the algorithm and the time complexity is 2^253.5
> for SHA256.
> >
> > If this is the best that can be done, we are in good shape.
>


> True - but mind that "if"!
>
> The question that one cannot answer from an abstract of the results - but,
> at best, from a careful reading of the full work, and perhaps not even then
> - is whether this is just some little special case or a new technique that,
> over time, will grow to weaken the algorithm in a significant way.  We've
> seen attacks of both kinds on other algorithms in the past.
>

The full algorithms are 64 rounds for sha256 and 80 for sha512.

These attacks only reduce the time complexity by 2.5 bits over exhaustive
brute force. So given that brute force will typically return a result at
the 50% point means we are talking about an improvement factor of 3.


If you look at the best attacks on SHA-1 to date, in and of themselves they
> don't amount to a significant risk.  What has people worried is that there
> seems to be a path forward - even if we haven't yet trodden it.
>

We started getting worried about SHA-1 when Dobbertin published the attacks
on MD5. We are a long way from having a usable attack on SHA-1 but we are
currently in the phaseout stage. SHA-1 will stop being acceptable for SSL
certificates in the near future.



> I've become leery of any statements of the form "It's just an
> insignificant weakness".


If we were talking about any weakness in 64 round SHA256 then I think you
would be seeing a movement to switch away from it. A really significant
improvement against a reduced strength version of the algorithm might also
be a concern. But these are neither.



> The fact is, we really don't understand our cryptographic primitives very
> well.  That's what *any* unexpected new structure or weakness is telling
> us.


I don't consider the result unexpected. We know that the strength of SHA-1
is less than 160 bits and that SHA-2 is very close in structure and
approach.



> As a matter of practical engineering, we have to somehow judge  when the
> risks are mounting to the point where a move - an expensive operation, and
> one whose cost is ever-growing with the volume of protected data an fielded
> equipment - is justified.  But the only way we should feel comfortable
> saying "Oh, it doesn't matter" is if we have some strong indications that,
> indeed, it doesn't matter - e.g., "yes, this attacks works on k rounds out
> of n, and theory convincingly shows that it cannot extend past k+1 rounds."
>

I don't expect to use SHA-2 forever. We are getting to a point where
deployment of SHA3 alongside SHA-2 as a backup algorithm should really be
expected. But I can't see this result being significant in itself.


-- 
Website: http://hallambaker.com/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131217/3db0b2f9/attachment.html>