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

[Jerry Leichter]

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.

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.

I've become leery of any statements of the form "It's just an insignificant weakness".  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.  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."
                                                        -- Jerry