Onderwerp: SHA-1 broken

Now, we've all seen this coming for a while.
http://www.schneier.com/blog/archive...a1_broken.html

Where do we go from here?

Gadi.

On Wed, Feb 16, 2005 at 02:56:27PM +0200, Gadi Evron wrote:
> Now, we've all seen this coming for a while.
> http://www.schneier.com/blog/archive...a1_broken.html
>
> Where do we go from here?

I am feeling smug that in a project I am working on I earlier decided
our integrity hashes would be a concatenation of MD5 and SHA-1, not
that that's a fix, but it helps.

I am also appreciating that hashes are used (this project included)
for many different things, not all of which are directly affected by
this break. Yes, this is a bad omen for the longevity of SHA-1 for
other uses, so we will keep an eye on it.

Something I am intrigued about is more sophiticated compositions of,
say, SHA-1 and MD5.

-kb

The standard response to "where to now" seems to be Whirlpool
[http://planeta.terra.com.br/informat...lpoolPage.html].
That or Tiger [http://www.cs.technion.ac.il/~biham/Reports/Tiger/].

The team which has cracked SHA1 is the same that cracked MD5 and
exposed weaknesses in the RIPEMD model. They're good. And they've
shown that what I would've thought to be the Next Best Thing - RIPEMD
- is yet another flawed system.

-mjec
--
http://mine.mjec.net/

On Wed, 16 Feb 2005 14:56:27 +0200, Gadi Evron <gadi@tehila.gov.il> wrote:
> Now, we've all seen this coming for a while.
> http://www.schneier.com/blog/archive...a1_broken.html
>
> Where do we go from here?
>
> Gadi.
>

On Feb 16, 2005, at 4:56 AM, Gadi Evron wrote:

> Now, we've all seen this coming for a while.
> http://www.schneier.com/blog/archive...a1_broken.html
>
> Where do we go from here?
>
We abandon the requirement of collision resistance. This is a strange
requirement, and is not supported by experience. Collision resistance
is not a "hard" problem in the sense that factoring large numbers or
computing discrete logs is hard. Collision resistance in deterministic
hash functions smells too much like generating entropy without secrets.
I have no reason to believe that careful analysis of *any* publicly
known deterministic many-to-one function will not allow me to produce a
collision, assuming I control all inputs into the function.

From my point of view, the issue is what weaker assumption do we
replace collision resistance with -- how about:

target collision resistance, with the "strength" of resistance equal to
the average advantage an attacker would gain in matching a fixed
target, as the target is averaged over all possible inputs in a measure
space? Then, producing "rare" messages which could be targeted would
not weaken the hash, as the probability of such messages occurring
would be low.

On Wed, Feb 16, 2005 at 02:56:27PM +0200, Gadi Evron wrote:
> Now, we've all seen this coming for a while.
> http://www.schneier.com/blog/archive...a1_broken.html
>
> Where do we go from here?

.... and to those that are not sure what "here" means, a pretty good
introduction to secure hashes can be found here, helping put all this
in context.

Unixwiz.net Tech Tip: Illustrated Guide to Cryptographic Hashes
http://www.unixwiz.net/techtips/igui...to-hashes.html

Steve :-)

--
Stephen J Friedl | Security Consultant | UNIX Wizard | +1 714 544-6561
www.unixwiz.net | Tustin, Calif. USA | Microsoft MVP | steve@unixwiz.net

A Chinese research group now says that collisions can be found in the full
SHA-1 in 2**69 hash operations, much less than the brute-force attack of
2**80 operations based on the hash length.

If I am eyeballing this correctly, this makes the "cracked" SHA-1 just a
little tougher (32x) than MD-5 was thought to be (2**64 operations) before
MD5 was cracked. (I believe, and I could be wrong, that MD5 is now
considered to be 2**42 operations strong; one of the papers referenced
below suggests the "1 hour IBM" MD5 crack was performed at a 2**25
operation level of difficulty which would only be possible with some
additional knowledge.)

Again, if I am eyeballing this correctly, SHA-1 is still currently
134,217,728x more secure than MD5. Before the SHA-1 announcement, SHA1 was
thought to be 274,877,906,944x more secure than MD5, and originally, SHA-1
was thought to be just 65,536x more secure than MD5. (MD5 has been "more
cracked" than SHA-1 in recent months.)

According to Bruce Schneier, "It pretty much puts a bullet into SHA-1 as a
hash function for digital signatures (although it doesn't affect
applications such as HMAC where collisions aren't important)"

Schneier also lists the likely alternatives in the near future in another
article. "The National Institute of Standards and Technology (NIST)
already has standards for longer --and harder-to-break -- hash functions:
SHA-224, SHA-256, SHA-384 and SHA-512. They're already government standards
and can already be used. This is a good stopgap, but I'd like to see more. "

See:
http://www.schneier.com/blog/archive...a1_broken.html
http://it.slashdot.org/comments.pl?s...2&cid=11686181
http://eprint.iacr.org/2004/199.pdf
http://eprint.iacr.org/2004/264.pdf

- Jonathan Lampe
- jonathan.lampe@standardnetworks.com

At 06:56 AM 2/16/2005, Gadi Evron wrote:
>Now, we've all seen this coming for a while.
>Where do we go from here?
> Gadi.

******************* PLEASE NOTE *******************

This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed.
If you are not the named addressee you should not disseminate, distribute or copy this e-mail. Please delete this e-mail from your system. If you are not the intended recipient you are notified that disclosing, copying, distributing or taking any action i
n reliance on the contents of this information is strictly prohibited.

Kent--

Compositions won't really help very much. Lets say (I'm sure the exact
numbers are wrong here) that it takes brute-forcing MD5 takes 2**80, and
brute-forcing SHA-1 takes 2**90. And due to recent discoveries, we can
push those down to 2**50 and 2**55 respectively. Breaking a composition
would still take on the order of 2**55 (the harder of the two)-- you're
not going to make it exponentially harder to crack by composing. Doing
something a little more slick like interweaving the bits of the two
algorithms would make it geometrically harder, but not exponentially.
You'd really have to get a new algorithm.

Of course, this is assuming that the actual attack allows one to take
some predefined input A, and compute some evil input A' such that
Hash(A)=3DHash(A'). If the attacks are simply to create colliding input
data, then the underlying algorithm is still safe for most applications.

Of course, I'm not a crypto-expert, so this may all be totally wrong.

Michael Scovetta
Computer Associates
Senior Application Developer


-----Original Message-----
From: Kent Borg [mailto:kentborg@borg.org]=20
Sent: Wednesday, February 16, 2005 6:27 PM
To: Gadi Evron
Cc: bugtraq@securityfocus.com
Subject: Re: SHA-1 broken

On Wed, Feb 16, 2005 at 02:56:27PM +0200, Gadi Evron wrote:
> Now, we've all seen this coming for a while.
> http://www.schneier.com/blog/archive...a1_broken.html
>=20
> Where do we go from here?

I am feeling smug that in a project I am working on I earlier decided
our integrity hashes would be a concatenation of MD5 and SHA-1, not
that that's a fix, but it helps.

I am also appreciating that hashes are used (this project included)
for many different things, not all of which are directly affected by
this break. Yes, this is a bad omen for the longevity of SHA-1 for
other uses, so we will keep an eye on it.

Something I am intrigued about is more sophiticated compositions of,
say, SHA-1 and MD5.

-kb

Hey all,

> shown that what I would've thought to be the Next Best Thing - RIPEMD
> - is yet another flawed system.

As far as I know, RIPEMD-160 is unbroken, and
unlikely to be broken quickly because of the need to find
collisions for the two "separate channels". Or did they publish
a RIPEMD-160 attack together with the MD5 breaks ?

Cheers,
Thomas Dullien

Hey all,

> We abandon the requirement of collision resistance. This is a strange
> requirement, and is not supported by experience. Collision resistance

we might think of changing the requirement of collision resistance
to "collision resistance in input data that is valid ASCII text". The
attacks on MD5 used the weak avalanche of the highest-order bit
in 32-bit words for producing the collision, basically precluding the
possibility of generating colliding ASCII text.

Cheers,
Thomas Dullien

Michael,

But wouldn't it render a login-based hashing system resistant to the
current hashing problems if it is implemented something like:

--
result = hashFunc1( input + hashFunc1(input) + salt )
//
// instead of
//
result = hashFunc1( input + salt )
--

We can see that the input to the functions is the same, so although a
collision could be found within one or the other but it would not give
the correct result unless the hashFunc1( foo ) = hashFunc2( foo )
where foo is the magical input that gives the same result as "bar"
(the initial password).

-- Michael


> -----Original Message-----
> From: Scovetta, Michael V [mailto:Michael.Scovetta@ca.com]
> Sent: Friday, 18 February 2005 8:34 AM
> To: Kent Borg; Gadi Evron
> Cc: bugtraq@securityfocus.com
> Subject: RE: SHA-1 broken
>
> Kent--
>
> Compositions won't really help very much. Lets say (I'm sure
> the exact numbers are wrong here) that it takes brute-forcing
> MD5 takes 2**80, and brute-forcing SHA-1 takes 2**90. And due
> to recent discoveries, we can push those down to 2**50 and
> 2**55 respectively. Breaking a composition would still take
> on the order of 2**55 (the harder of the two)-- you're not
> going to make it exponentially harder to crack by composing.
> Doing something a little more slick like interweaving the
> bits of the two algorithms would make it geometrically
> harder, but not exponentially.
> You'd really have to get a new algorithm.
>
> Of course, this is assuming that the actual attack allows one
> to take some predefined input A, and compute some evil input
> A' such that Hash(A)=Hash(A'). If the attacks are simply to
> create colliding input data, then the underlying algorithm is
> still safe for most applications.
>
> Of course, I'm not a crypto-expert, so this may all be totally wrong.
>
> Michael Scovetta
> Computer Associates
> Senior Application Developer
>
>
> -----Original Message-----
> From: Kent Borg [mailto:kentborg@borg.org]
> Sent: Wednesday, February 16, 2005 6:27 PM
> To: Gadi Evron
> Cc: bugtraq@securityfocus.com
> Subject: Re: SHA-1 broken
>
> On Wed, Feb 16, 2005 at 02:56:27PM +0200, Gadi Evron wrote:
> > Now, we've all seen this coming for a while.
> > http://www.schneier.com/blog/archive...a1_broken.html
> >
> > Where do we go from here?
>
> I am feeling smug that in a project I am working on I earlier
> decided our integrity hashes would be a concatenation of MD5
> and SHA-1, not that that's a fix, but it helps.
>
> I am also appreciating that hashes are used (this project
> included) for many different things, not all of which are
> directly affected by this break. Yes, this is a bad omen for
> the longevity of SHA-1 for other uses, so we will keep an eye on it.
>
> Something I am intrigued about is more sophiticated
> compositions of, say, SHA-1 and MD5.
>
> -kb

--- Michael Cordover <michael.cordover@gmail.com>
wrote:

> The standard response to "where to now" seems
> to be Whirlpool
>
[http://planeta.terra.com.br/informat...lpoolPage.html].
> That or Tiger
>
[http://www.cs.technion.ac.il/~biham/Reports/Tiger/].
>
> The team which has cracked SHA1 is the same
> that cracked MD5 and
> exposed weaknesses in the RIPEMD model.
> They're good. And they've
> shown that what I would've thought to be the
> Next Best Thing - RIPEMD
> - is yet another flawed system.
>
> -mjec
> --
> http://mine.mjec.net/
>
> On Wed, 16 Feb 2005 14:56:27 +0200, Gadi Evron
> <gadi@tehila.gov.il> wrote:
> > Now, we've all seen this coming for a while.
> >
>
http://www.schneier.com/blog/archive...a1_broken.html
> >
> > Where do we go from here?
> >
> > Gadi.
> >
>

I think Whirlpool and Tiger are both quite
untested at the moment. The reason these
algorithms haven't contained any weaknesses thus
far is likely due to the fact that they haven't
been extensively tested. It seems likely that in
only a few months someone will devise a
theoretical attack against these as well.

A few months ago, assuming that we would soon be
in this situation, I designed some modifications
to SHA-256 and SHA-512 that will keep the
algorithms quite respectably protected under a
partial break. I think the easiest way to
charactize the approach would be that it changes
the algorithm from a many->one approach to a
many->many approach as more than one hash can be
generated per datastream. This allows for the
inevitability that SHA-256 and SHA-512 will one
day suffer a partial-break similar to MD5, MD4,
RIPEMD, SHA-0 and SHA-1. Due to it's design,
even if one hash is broken, another also needs to
be broken in tandem which effectively
exponentially raises the likelyhood of collision
as an attacker has to collide with multiple
hashes at once. Also, some reordering is tossed
in to help hinder exploitation of the appendable
cascading issue. (Hinder mind you, not stop.)

I floated this idea on this list a month ago in
the form of a paper I wrote, a copy can be found
here: http://arxiv.org/abs/cs.CR/0501038

The only sticking points that have been shown at
this point is the re-order modification prevents
hashing of unbound data-streams. Although this
is unfortunate, the algorithm seems fine for
bounded datastreams. (Unbounded datastreams as
well, assuming they are reordered in advance.)

~D.J. Capelis




__________________________________
Do you Yahoo!?
Meet the all-new My Yahoo! - Try it today!
http://my.yahoo.com

Michael,

But with such functions the point is that "input" isn't a function,
it's a string - and it can only be the inverse of one, not both; i.e.
the result of "invHashFunc1( foo )" _wont_ equal "invHashFunc2( foo
)".

So if the user is attempting to break a login screen with his
invHashFunc's, and the hash of the users password is implemented as
described, they can't possibly provide the right inversions for _both_
functions in one string; unless they happen to be the same.

No?

-- Michael


On Fri, 18 Feb 2005 00:45:24 -0500, Scovetta, Michael V
<Michael.Scovetta@ca.com> wrote:
> Michael,
> I'm not sure that it would help significantly. If the end-result of
> this research on breaking hash algorithms is to create "inverse-MD5" and "inverse-SHA" functions, then:
> input = invHashFunc2( substring(invHashFunc1(result)) )
>
> By our assumptions, invHashFunc1 and invHashFunc2 are both tractable, the substring function would simply add a polynomial factor to the calculation to guess it right.
>
> You could create arbitrarily complex functions, like:
> MD5(SHA(input+salt)+MD5(input+salt)+salt)
> But in the end, if invHashFunc1 and invHashFunc2 are both tractable, then nothing you do could help it (beyond a polynomial factor). And keeping the actual algorithm-composition secret wouldn't help much either.
>
> -Mike
>
> -----Original Message-----
> From: Michael Silk [mailto:michaelsilk@gmail.com]
> Sent: Thu 2/17/2005 10:30 PM
> To: Scovetta, Michael V; bugtraq@securityfocus.com
> Cc:
> Subject: RE: SHA-1 broken
> Michael,
>
> But wouldn't it render a login-based hashing system resistant to the
> current hashing problems if it is implemented something like:
>
> --
> result = hashFunc1( input + hashFunc1(input) + salt )
> //
> // instead of
> //
> result = hashFunc1( input + salt )
> --
>
> We can see that the input to the functions is the same, so although a
> collision could be found within one or the other but it would not give
> the correct result unless the hashFunc1( foo ) = hashFunc2( foo )
> where foo is the magical input that gives the same result as "bar"
> (the initial password).
>
> -- Michael
>
> > -----Original Message-----
> > From: Scovetta, Michael V [mailto:Michael.Scovetta@ca.com]
> > Sent: Friday, 18 February 2005 8:34 AM
> > To: Kent Borg; Gadi Evron
> > Cc: bugtraq@securityfocus.com
> > Subject: RE: SHA-1 broken
> >
> > Kent--
> >
> > Compositions won't really help very much. Lets say (I'm sure
> > the exact numbers are wrong here) that it takes brute-forcing
> > MD5 takes 2**80, and brute-forcing SHA-1 takes 2**90. And due
> > to recent discoveries, we can push those down to 2**50 and
> > 2**55 respectively. Breaking a composition would still take
> > on the order of 2**55 (the harder of the two)-- you're not
> > going to make it exponentially harder to crack by composing.
> > Doing something a little more slick like interweaving the
> > bits of the two algorithms would make it geometrically
> > harder, but not exponentially.
> > You'd really have to get a new algorithm.
> >
> > Of course, this is assuming that the actual attack allows one
> > to take some predefined input A, and compute some evil input
> > A' such that Hash(A)=Hash(A'). If the attacks are simply to
> > create colliding input data, then the underlying algorithm is
> > still safe for most applications.
> >
> > Of course, I'm not a crypto-expert, so this may all be totally wrong.
> >
> > Michael Scovetta
> > Computer Associates
> > Senior Application Developer
> >
> >
> > -----Original Message-----
> > From: Kent Borg [mailto:kentborg@borg.org]
> > Sent: Wednesday, February 16, 2005 6:27 PM
> > To: Gadi Evron
> > Cc: bugtraq@securityfocus.com
> > Subject: Re: SHA-1 broken
> >
> > On Wed, Feb 16, 2005 at 02:56:27PM +0200, Gadi Evron wrote:
> > > Now, we've all seen this coming for a while.
> > > http://www.schneier.com/blog/archive...a1_broken.html
> > >
> > > Where do we go from here?
> >
> > I am feeling smug that in a project I am working on I earlier
> > decided our integrity hashes would be a concatenation of MD5
> > and SHA-1, not that that's a fix, but it helps.
> >
> > I am also appreciating that hashes are used (this project
> > included) for many different things, not all of which are
> > directly affected by this break. Yes, this is a bad omen for
> > the longevity of SHA-1 for other uses, so we will keep an eye on it.
> >
> > Something I am intrigued about is more sophiticated
> > compositions of, say, SHA-1 and MD5.
> >
> > -kb
>
>
>

On February 17, 2005, Michael Cordover <michael.cordover@gmail.com> wrote:
> On Wed, 16 Feb 2005 14:56:27 +0200, Gadi Evron <gadi@tehila.gov.il> wrote:
> >
> > Where do we go from here?
>
> The standard response to "where to now" seems to be Whirlpool
> [http://planeta.terra.com.br/informat...lpoolPage.html].
> That or Tiger [http://www.cs.technion.ac.il/~biham/Reports/Tiger/].

There has indeed been a lot of positive buzz about Whirlpool. I have seen
comments, though, that Whirlpool is quite slow, but that Tiger is pretty
reasonable on 64-bit CPUs.

No doubt we'll see more analyses of these as the old standbys start to look
more and more shaky.

> The team which has cracked SHA1 is the same that cracked MD5 and
> exposed weaknesses in the RIPEMD model. They're good. And they've
> shown that what I would've thought to be the Next Best Thing - RIPEMD

Yeah, for instance RIPEMD-160 is the only other message digest algorithm
currently implemented in the OpenSSL library that would be worth using
(other than perhaps MDC2, which I haven't seen much discussion of -- it's
apparently a method of constructing a 128-bit output hash function out of a
block cipher -- the OpenSSL implementation uses DES).

> - is yet another flawed system.

The original RIPEMD is indeed flawed, as shown by Hans Dobbertin in '95 for
a reduced-round version and by the Chinese team for the full-round version.
However, I have not seen analysis saying that this weakness also applies to
RIPEMD-128 / RIPEMD-160 / RIPEMD-256 / RIPEMD-320
(<http://www.esat.kuleuven.ac.be/~bosselae/ripemd160.html>), the
strengthened versions which were co-developed by Dobbertin in '96, partially
in response to the weakness that he found.

Pages like The Hashing Function Lounge
(<http://planeta.terra.com.br/informat.../hflounge.html>) agree
with this separation of RIPEMD vs. the RIPEMD-160 family.

--
Dan Harkless
http://harkless.org/dan/

Hey all,

> And what about the case for (uncompressed) binary images ?

Base64-encode them before hashing.

On top of that, let me sketch under what scenario a collision on binaries is
relevant:

Mallory generates a collision-byte-string, a and a'. In order to do anything
evil she has to construct two innocent-looking executables containing these
strings of which one has to be signed. She can then replace the "good"
version
with the "evil" version. So far the theory. Now how does the practical part
of
it look ?

Let's begin this by fixing one assumption:
1) Whoever signs the executables is sane, e.g. will refuse to sign
executables
that he cannot analyze, e.g. stuff that depends on self-decrypting code etc.
He
will furthermore reject executables containing non-standard constructs
(stuff that
a compiler won't emit, which is relatively easy to check).

Claim: a and a' have to be valid, executable code in order for Mallory to
be evil. Reasoning: If a and a' are merely data, the program containing them
has to interpret them, and as such have all the code (API calls etc) that is
later-on
used for evil deeds present in the executable (both the "good" and the "bad"
one),
and a sane signer won't sign them.
Now we have a really tight restriction on a and a', namely that it is valid,
executable
code does not contain anything a compiler wouldn't emit. Wow. Try generating
a
collision with that :-)

I am not trying to claim that the attacks aren't a major breakthrough, but
unless
someone goes out produces better collisions or solves second preimage MD4
(or better), we need not be overly worried.

Cheers,
Thomas Dullien

In some mail from dullien@gmx.de, sie said:
>
> Hey all,
>
> > We abandon the requirement of collision resistance. This is a strange
> > requirement, and is not supported by experience. Collision resistance
>
> we might think of changing the requirement of collision resistance
> to "collision resistance in input data that is valid ASCII text". The
> attacks on MD5 used the weak avalanche of the highest-order bit
> in 32-bit words for producing the collision, basically precluding the
> possibility of generating colliding ASCII text.

And what about the case for (uncompressed) binary images ?

Darren