[148497] in cryptography@c2.net mail archive
Re: [Cryptography] Preimage Attacks on 41-Step SHA-256 and 46-Step
daemon@ATHENA.MIT.EDU (Phillip Hallam-Baker)
Tue Dec 17 17:13:24 2013
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <F03B8F5A-3D4F-4636-AADF-D81E92367ABA@lrw.com>
Date: Tue, 17 Dec 2013 16:55:22 -0500
From: Phillip Hallam-Baker <hallam@gmail.com>
To: Jerry Leichter <leichter@lrw.com>
Cc: Cryptography List <cryptography@metzdowd.com>,
Robert Hettinga <hettinga@gmail.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============3028769222902353204==
Content-Type: multipart/alternative; boundary=047d7b5d571037c9cc04edc1fcda
--047d7b5d571037c9cc04edc1fcda
Content-Type: text/plain; charset=ISO-8859-1
On Tue, Dec 17, 2013 at 4:20 PM, Jerry Leichter <leichter@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/
--047d7b5d571037c9cc04edc1fcda
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On T=
ue, Dec 17, 2013 at 4:20 PM, Jerry Leichter <span dir=3D"ltr"><<a href=
=3D"mailto:leichter@lrw.com" target=3D"_blank">leichter@lrw.com</a>></sp=
an> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div class=3D"im">On Dec 17, 2013, at 8:12 A=
M, Phillip Hallam-Baker wrote:<br>
> This is not particularly impressive or worrisome. The attack is on a r=
educe strength version of the algorithm and the time complexity is 2^253.5 =
for SHA256.<br>
><br>
> If this is the best that can be done, we are in good shape.<br></div><=
/blockquote><div>=A0</div><blockquote class=3D"gmail_quote" style=3D"margin=
:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class=3D"im">
</div>True - but mind that "if"!<br>
<br>
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. =A0We&=
#39;ve seen attacks of both kinds on other algorithms in the past.<br>
</blockquote><div><br></div><div>The full algorithms are 64 rounds for sha2=
56 and 80 for sha512.</div><div><br></div><div>These attacks only reduce th=
e time complexity by 2.5 bits over exhaustive brute force. So given that br=
ute force will typically return a result at the 50% point means we are talk=
ing about an improvement factor of 3.</div>
<div><br></div><div><br></div><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
If you look at the best attacks on SHA-1 to date, in and of themselves they=
don't amount to a significant risk. =A0What has people worried is that=
there seems to be a path forward - even if we haven't yet trodden it.<=
br>
</blockquote><div><br></div><div>We started getting worried about SHA-1 whe=
n Dobbertin published the attacks on MD5. We are a long way from having a u=
sable attack on SHA-1 but we are currently in the phaseout stage. SHA-1 wil=
l stop being acceptable for SSL certificates in the near future.=A0</div>
<div><br></div><div>=A0</div><blockquote class=3D"gmail_quote" style=3D"mar=
gin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I've become leery of any statements of the form "It's just an =
insignificant weakness". =A0</blockquote><div><br></div><div>If we wer=
e talking about any weakness in 64 round SHA256 then I think you would be s=
eeing a movement to switch away from it. A really significant improvement a=
gainst a reduced strength version of the algorithm might also be a concern.=
But these are neither.</div>
<div><br></div><div>=A0</div><blockquote class=3D"gmail_quote" style=3D"mar=
gin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">The fact is, we=
really don't understand our cryptographic primitives very well. =A0Tha=
t's what *any* unexpected new structure or weakness is telling us. =A0<=
/blockquote>
<div><br></div><div>I don't consider the result unexpected. We know tha=
t the strength of SHA-1 is less than 160 bits and that SHA-2 is very close =
in structure and approach.</div><div><br></div><div>=A0</div><blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;p=
adding-left:1ex">
As a matter of practical engineering, we have to somehow judge =A0when 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. =A0But the only way we should feel comfortable s=
aying "Oh, it doesn't matter" is if we have some strong indic=
ations 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 ex=
tend past k+1 rounds."<br>
</blockquote></div><br clear=3D"all"><div>I don't expect to use SHA-2 f=
orever. 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 r=
esult being significant in itself.</div>
<div><br></div><div><br></div>-- <br>Website: <a href=3D"http://hallambaker=
.com/">http://hallambaker.com/</a><br>
</div></div>
--047d7b5d571037c9cc04edc1fcda--
--===============3028769222902353204==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============3028769222902353204==--
