SHA-1 broken

*

| 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 : :' :
`. `'
`-

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

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

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

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?

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

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

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

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

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

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

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

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

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.