SHA-1 broken

[Gadi Evron]

Now, we've all seen this coming for a while.
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

Where do we go from here?

Gadi.

[Kent Borg]

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/archives/2005/02/sha1_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]

The standard response to "where to now" seems to be Whirlpool
[http://planeta.terra.com.br/informatica/paulobarreto/WhirlpoolPage.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/archives/2005/02/sha1_broken.html
>
> Where do we go from here?
>
> Gadi.
>

[Robert Sussland]

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/archives/2005/02/sha1_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.

[Steve Friedl]

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/archives/2005/02/sha1_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/iguide-crypto-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

[Jonathan G. Lampe]

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/archives/2005/02/sha1_broken.html
http://it.slashdot.org/comments.pl?sid=139602&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.

[Scovetta, Michael V]

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/archives/2005/02/sha1_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 Silk]

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/archives/2005/02/sha1_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

[D.J. Capelis]

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

> The standard response to "where to now" seems
> to be Whirlpool
>
[http://planeta.terra.com.br/informatica/paulobarreto/WhirlpoolPage.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/archives/2005/02/sha1_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 Silk]

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/archives/2005/02/sha1_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
>
>
>

[Dan Harkless]

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/informatica/paulobarreto/WhirlpoolPage.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/informatica/paulobarreto/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

[Darren Reed]

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

[Tollef Fog Heen]

*

| 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.

That's not really useful is you want to sign something in non-English
languages. Valid UTF8 might be a decent requirement, though.

--
Tollef Fog Heen ,''`.
UNIX is user friendly, it's just picky about who its friends are : :' :
`. `'
`-

[Michael Silk]

I agree that an anaylsis of their results is nice and important, but
also I don't think that it will neccessarily lead to a new "perfect"
hashing function we can implement and forget about.

A nicer idea is to implement better code that allows us to modify our
internal hashing algorithms whenever we like, so that if (and when?)
new hashing strategies are broken (even by virtue of faster computing
power) we can adapt easily.

At least, this is the approach I'll be taking to the problem.

-- Michael


On Sat, 19 Feb 2005 00:42:56 -0500, Anatole Shaw
<shaw_bugtraq20050218@autoloop.com> wrote:
> Sadly, there is no magic bullet for the SHA-1 problem. Let me say, in
> classic Bugtraq style, that I believe the "temporary workaround for this
> vulnerability" is to move to SHA-512 as quickly as possible.
>
> NIST was going to recommend SHA-256 and SHA-512 by 2010, but for the
> security-conscious the time is now.
>
> The "computer security response" should not be to re-jigger the hashes,
> bet on crypto tricks that haven't seen any review, and guess at the
> computational complexity of the result.
>
> The only fix will be informed analysis of the new paper from the Chinese
> team (which hasn't even been released yet) and the informed development
> of a solid cryptographic response.
>
> Anatole

[Anatole Shaw]

Sadly, there is no magic bullet for the SHA-1 problem. Let me say, in
classic Bugtraq style, that I believe the "temporary workaround for this
vulnerability" is to move to SHA-512 as quickly as possible.

NIST was going to recommend SHA-256 and SHA-512 by 2010, but for the
security-conscious the time is now.

The "computer security response" should not be to re-jigger the hashes,
bet on crypto tricks that haven't seen any review, and guess at the
computational complexity of the result.

The only fix will be informed analysis of the new paper from the Chinese
team (which hasn't even been released yet) and the informed development
of a solid cryptographic response.

Anatole


On Fri, Feb 18, 2005 at 05:06:42PM +1100, Michael Silk wrote:
> 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/archives/2005/02/sha1_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
> >
> >
> >

In-Reply-To: <011401c51541$fdafedb0$0400a8c0@p14n>

I think Thomas has a good point here. We must separate the academic mathematical arguement about collisions from it's application in the real world. It may be that there are collisions in both MD5 and SHA-1 but have they any actual bearing on the use and
application of these hashes in the real world?

In human fingerprint forensics it is possible for 2 finger prints to be 'apparently' identical. However if we are looking for a 'cat burgular' in Los Angeles and the 'identical' match is from a 6 year old boy in Cape Town the collision in this case is aca
demic.

In much the same way if the original text was 'I owe you 1 million dollars' and the collision text was 'sdf86*&6989h,mni lkj99j' its not significant.

Both MD5 and SHA-1 are still useful in the real world.

Nick Pringle


>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
>
>

[Brian May]

Michael Silk wrote:
> 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 )
<snip>

wouldn't that create an infinite loop?

[exon]

Michael Silk wrote:
> 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 )
> --
>

I assume you mean hashFUnc2 inside the parentheses (I'll refer to it as
that anyway, for clarity).

No it won't, because if hashFunc2 has collisions the resulting output
will collide in hashFunc1 as well. The collision resistance in this case
is somewhat less than that of hashFunc2 (because two different outputs
of hashFunc2 might collide in hashFunc1, and collisions in hashFunc2
will always produce the same output from hashFunc1) and not, as someone
else suggested, the smallest of the two.

If the attacker doesn't know this is how the algorithm works, he might
be stumped for a whole five minutes or so, but a strong hash isn't
supposed to depend on the algorithm not being known.

If you didn't mean hashFunc2 inside the parentheses, you have actually
lessened the collision resistance, owing to the possibility that two
different outputs might collide as well.

> 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/archives/2005/02/sha1_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]

On this topic, I might actually say that a concatenation of two hashes
is very secure if the two hashes are sufficiently different.

Although MD5 and SHA1 are reasonably similar, let's suppose for a
moment that they use entirely different mechanisms. If this were so
and the crack time for MD5 was 2**50, for SHA1 2**65, then the crack
time for CONCAT(MD5(string), SHA1(string)) would be about 2**115.
This is because you need to find something that colides for both.
This is *far* more difficult and therefore far more collision
resistant. Unfortunately this requires 288 bits - far more than each
of the old hashes. Still, that much memory doesn't tend to be a
problem ;).

Regards,

Michael Cordover

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

[Michael Silk]

Inline.

> -----Original Message-----
> From: exon [mailto:exon@home.se]
> Sent: Saturday, 19 February 2005 8:58 PM
> To: bugtraq@securityfocus.com
> Subject: Re: SHA-1 broken
>
> Michael Silk wrote:
> > 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 + hashFunc2(input) + salt )
> > //
> > // instead of
> > //
> > result = hashFunc1( input + salt )
> > --
> >
>
> I assume you mean hashFUnc2 inside the parentheses

Yes.


> No it won't, because if hashFunc2 has collisions the
> resulting output will collide in hashFunc1 as well.

How?

The attackers input is "input". He can only choose to enter a
collision for "hashFunc1" _OR_ "hashFunc2". He can't enter a
collision for both, but that is what he needs to pass this
function with a different string from the original.


> The
> collision resistance in this case is somewhat less than that
> of hashFunc2 (because two different outputs of hashFunc2
> might collide in hashFunc1,

Sure, hashFunc2 might give collisions, but it doesn't mean anything
unless _THOSE_ collisions are collisions in hashFunc1 that lead to the
original hash.


> but a
> strong hash isn't supposed to depend on the algorithm not being known.

Obviously.

-- Michael

[Frank Knobbe]

--=-LfMNAhGbllotgE0HcPGL
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable

On Thu, 2005-02-17 at 16:34 -0500, Scovetta, Michael V wrote:
> [...] 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)

If the two algorithms are different, finding a collision in one of them
does not deliver a working collision in the other, no? Don't you have to
find a "common" collision between the two? Wouldn't that require an
effort of 2**(50+55)?

Regards,
Frank


--=-LfMNAhGbllotgE0HcPGL
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (FreeBSD)

iD8DBQBCGMzvwBQKb2zelzoRAvyvAJ9DrHfGdLL0d6OMmyZ2nT pN6cAeiACeJUNh
yWZ5ntCAmyQOe/u9zHQK3Hk=
=0WLp
-----END PGP SIGNATURE-----

--=-LfMNAhGbllotgE0HcPGL--

[exon]

Michael Silk wrote:
> Inline.
>

Naturally. Likewise.

>
>>-----Original Message-----
>>From: exon [mailto:exon@home.se]
>>Sent: Saturday, 19 February 2005 8:58 PM
>>To: bugtraq@securityfocus.com
>>Subject: Re: SHA-1 broken
>>
>>Michael Silk wrote:
>>
>>>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 + hashFunc2(input) + salt )
>>>//
>>>// instead of
>>>//
>>>result = hashFunc1( input + salt )
>>> --
>>>
>>
>>I assume you mean hashFUnc2 inside the parentheses
>
>
> Yes.
>
>
>
>>No it won't, because if hashFunc2 has collisions the
>>resulting output will collide in hashFunc1 as well.
>
>
> How?
>
> The attackers input is "input". He can only choose to enter a
> collision for "hashFunc1" _OR_ "hashFunc2". He can't enter a
> collision for both, but that is what he needs to pass this
> function with a different string from the original.
>
>
>
>>The
>>collision resistance in this case is somewhat less than that
>>of hashFunc2 (because two different outputs of hashFunc2
>>might collide in hashFunc1,
>
>
> Sure, hashFunc2 might give collisions, but it doesn't mean anything
> unless _THOSE_ collisions are collisions in hashFunc1 that lead to the
> original hash.
>

if(HF2(xxx) == HF2(XXX))
then
HF1(HF2(xxx)) == HF1(HF2(XXX))
regardless of collisions in HF1, since HF1 is fed the same input for
both those inputs. In effect, this means that if HF1 is a perfect hash
(no collisions, ever) it would still collide because it is given the
same input from HF2.

To force a collision to exist in both hashes you would have to do
something like this, which was posted to this list erlier by someone
whose name I can't recall (assume + means concatenation)
output = HF1(input + HF2(input))

Note that this is just off the top of my head and would most likely
depend on the algorithms used, but the input MUST be fed unaltered to
both hashing functions for it to be any stronger than the original
implementation (in theory, that is).

/exon

[peeon+securityfocus@peeon.net]

The Research Summary was posted to Yiqun Lisa Yin's MIT site.

http://theory.csail.mit.edu/~yiqun/

Only 2 pages, maybe the 90 page paper is forthcoming.

-Joel

On Sat, 19 Feb 2005, Anatole Shaw wrote:

> Sadly, there is no magic bullet for the SHA-1 problem. Let me say, in
> classic Bugtraq style, that I believe the "temporary workaround for this
> vulnerability" is to move to SHA-512 as quickly as possible.
>
> NIST was going to recommend SHA-256 and SHA-512 by 2010, but for the
> security-conscious the time is now.
>
> The "computer security response" should not be to re-jigger the hashes,
> bet on crypto tricks that haven't seen any review, and guess at the
> computational complexity of the result.
>
> The only fix will be informed analysis of the new paper from the Chinese
> team (which hasn't even been released yet) and the informed development
> of a solid cryptographic response.
>
> Anatole
>
>
> On Fri, Feb 18, 2005 at 05:06:42PM +1100, Michael Silk wrote:
>> 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/archives/2005/02/sha1_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
>>>
>>>
>>>
>

[Denis Jedig]

Tollef Fog Heen wrote:

> | 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.
>
> That's not really useful is you want to sign something in non-English
> languages. Valid UTF8 might be a decent requirement, though.

What about Word documents? PDF files? Executable code? Depending on the
context the meaning of "valid" will differ greatly. So you would have to
supply a validation engine together with the signed data.

I do not know enough about the characteristics of the MD5 attack to
judge if using Base64-encoding beforehand would strongly mitigate it,
however, an abstraction layer of encoding in a well-known format would
make validation of the encoded stream easier. The big question is if
there is a gain at all when using this validation - we still do not
validate the original data, just the abstraction layer.

Denis Jedig
syneticon GbR

[Damian Menscher]

On Sat, 19 Feb 2005 securityfocus@microtechnical.co.uk wrote:
>
> In much the same way if the original text was 'I owe you 1 million
> dollars' and the collision text was 'sdf86*&6989h,mni lkj99j' its not
> significant.

Hey, Nick. I want to confirm that I've installed GPG correctly. Would
you mind signing some random text, say, "sdf86*&6989h,mni lkj99j", so I
can test it?

I'll admit I agree with your point, though. The demonstrated collisions
in MD5 (none have been demonstrated in SHA-1 yet) varied four high-order
bits. So it'd be fairly unrealistic (in the real world) to generate a
useful collision. Here I define "useful" to mean at least one side has
to be intelligible (as opposed to your definition of having both sides
be intelligible).

Damian Menscher
--
-=#| Physics Grad Student & SysAdmin @ U Illinois Urbana-Champaign |#=-
-=#| 488 LLP, 1110 W. Green St, Urbana, IL 61801 Ofc:(217)333-0038 |#=-
-=#| 4602 Beckman, VMIL/MS, Imaging Technology Group:(217)244-3074 |#=-
-=#| <menscher@uiuc.edu> www.uiuc.edu/~menscher/ Fax:(217)333-9819 |#=-
-=#| The above opinions are not necessarily those of my employers. |#=-

[Paul Johnston]

Hi,

>In much the same way if the original text was 'I owe you 1 million dollars' and the collision text was 'sdf86*&6989h,mni lkj99j' its not significant.
>
>
I think that kind of collision affects the "non-repudiation" property of
digital signatures. In court, A produces message "I owe you 1 million
dollars" signed by B. B says, "No... I signed a random string provided
by A to prove my identity, I've been setup to sign this colliding message".

Regards,

Paul

--
Paul Johnston, GSEC
Internet Security Specialist
Westpoint Limited
Albion Wharf, 19 Albion Street,
Manchester, M1 5LN
England
Tel: +44 (0)161 237 1028
Fax: +44 (0)161 237 1031
email: paul@westpoint.ltd.uk
web: www.westpoint.ltd.uk

[Peter Jeremy]

On 2005-Feb-19 00:42:56 -0500, Anatole Shaw <shaw_bugtraq20050218@autoloop.com> wrote:
>Sadly, there is no magic bullet for the SHA-1 problem. Let me say, in
>classic Bugtraq style, that I believe the "temporary workaround for this
>vulnerability" is to move to SHA-512 as quickly as possible.

There are two difficulties with this. Firstly, SHA-512 generates a
hash that is somewhat over 3 times the size of SHA-1 - this may
present problems in some cases. It's definitely not going to be a
drop-in replacement.

Secondly, AFAIK, it's not yet clear that SHA-512 (or SHA-256) are
resistant to this break. Whilst a 2^11 reduction in collision resistance
would be unimportant in SHA-512, given the close relationship between the
SHA-* family, it's possible that that the _all_ of the SHA-* family have
a collision resistance similar to SHA-1 - around 2^70.

I agree that an alternative to SHA-1 is required fairly quickly. It's
less clear that SHA-512 is even a temporary work-around. I believe
that the immediate reaction would be to prepare a plan on how to
quickly replace SHA-1 with an alternative hash algorithm (probably
with a different sized result) and be ready to implement it once an
alternative is identified. If you do move to SHA-512 now, you should
probably be prepared to make another change in the near future.

>The only fix will be informed analysis of the new paper from the Chinese
>team (which hasn't even been released yet) and the informed development
>of a solid cryptographic response.

Agreed.

--
Peter Jeremy

This email may contain privileged/confidential information. You may not copy or disclose this email to anyone without the written permission of the sender. If you have received this email in error please kindly delete this message and notify the sender.
Opinions expressed in this email are those of the sender and not necessarily the opinions of the employer.

This email and any attached files should be scanned to detect viruses. No liability will be accepted by the employer for loss or damage (whether caused by negligence or not) as a result of email transmission.

[Peter J. Holzer]

--dDRMvlgZJXvWKvBx
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On 2005-02-19 10:58:23 +0100, exon wrote:
> Michael Silk wrote:
> > But wouldn't it render a login-based hashing system resistant to the
> >current hashing problems if it is implemented something like:
> >
> > --
> > result =3D hashFunc1( input + hashFunc1(input) + salt )
> > //
> > // instead of
> > //
> > result =3D hashFunc1( input + salt )
> > --
> >
>=20
> I assume you mean hashFUnc2 inside the parentheses (I'll refer to it as=
=20
> that anyway, for clarity).

I don't think so. Hashing functions for login (e.g., the BSD/Linux style
MD5-hash) usually call the same hashing function multiple times.


> No it won't, because if hashFunc2 has collisions the resulting output=20
> will collide in hashFunc1 as well.

No, it wont. (input1 + hashFunc2(input1)) and (input2 +
hashFunc2(input2)) are still different strings, even if
hashFunc2(input1) and hashFunc2(input2) collide, so you have to find an
input which collides in both hashes (well, not quite), which should be
harder to find than one which collides in only one.


> If you didn't mean hashFunc2 inside the parentheses, you have actually=20
> lessened the collision resistance, owing to the possibility that two=20
> different outputs might collide as well.

No, because again, (input1 + hashFunc1(input1)) and (input2 +
hashFunc1(input2)) are two different strings, even if hashFunc1(input1)
and hashFunc1(input2) collide, and they must collide as well.=20

hp

--=20
_ | Peter J. Holzer | If the code is old but the problem is new
|_|_) | Sysadmin WSR / LUGA | then the code probably isn't the problem.
| | | hjp@wsr.ac.at |
__/ | http://www.hjp.at/ | -- Tim Bunce on dbi-users, 2004-11-05

--dDRMvlgZJXvWKvBx
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iQDQAwUBQhjftVLjemazOuKpAQEyAgXTBYzDdnqsZ/1L6KgU6J+t7NYkYI5biREu
gH9arOFQ3LVbofLM/i5NTHYMvqGNQgRohPTSmJwVi3ohEy7FCWwomkPfr/Nh5+I1
NqKbS8IfzBT5sVB9v3AqmK4ddub9f0glhD8y2BRae5PJeo3ucR Jxrr8pMcIEecaH
DNvAl87vHH8gbAQKhI4Mb0Nz5H78qUBvwB70PoTGvpq99w/cDlceTPuC4hK+CrpF
F9qmx3nUUxKI2g5bEQJv+StqVQ==
=Htij
-----END PGP SIGNATURE-----

--dDRMvlgZJXvWKvBx--

[Pavel Machek]

Hi!

> In much the same way if the original text was 'I owe you 1 million dollars' and the collision text was 'sdf86*&6989h,mni lkj99j' its not significant.
>

See the demos I posted to bjgtraq some time ago... It had pretty reasonable
horse-selling texts with same md5 sum.
--
64 bytes from 195.113.31.123: icmp_seq=28 ttl=51 time=448769.1 ms