Re: Chinese Professor Cracks Fifth Data Security Algorithm (SHA-1)

[wac <waldoalvarez00 () gmail com>]

Hello:

On 3/24/07, Valdis.Kletnieks () vt edu <Valdis.Kletnieks () vt edu> wrote:
> On Sat, 24 Mar 2007 11:48:10 CDT, wac said:
>
> > Of course not, is enough to find a collision and you'll get for example
> a
> > message signed by somebody else that looks completely authentic since
> > signatures encrypt that hash with the private key.
>
> No, if you have a signature to some text, you need to find a collision to
> a
> specified value - the one the signature covers.


That is what I mean. If original hash was 0x1234 (assuming 16 bits) and you
want a signed text that looks signed by the private keys holder you have to
construct a text with the same 0x1234 hash. There is where collisions would
come into the game.

For instance, if you have
> a 16 bit hash, finding two texts that both have a hash value of 0x1F6E
> doesn't
> do you much good if the signature is for 0x4ED2.  And due to the birthday
> paradox, finding any pair of colliding hashes is a lot easier than finding
> a collision to a specific hash.


We are assuming that it was cracked right? I believe that it means if you
can find something let's call it Y that has the same output from the hash
function as the original H(X) = H(Y) let's call the original signed content
X. Of course does not seems to me that SHA-1 was cracked, it was IMHO at
most "weakened" and some collision was found but to call it cracked is
well... too strong. In my opinion is a claim made by the one who claims it
to be famous or something twisting a little the truth. To me something half
true is a lie. Also I was not referring of course to find a pair of
colliding hashes since that would be pointless (yes well maybe has some use
who knows). We all know that they collide and collisions exist. The pigeon
hole principle right? BTW somebody has a paper where that "SHA-1 crack" is
clearly explained? I would like to read it and not trust such claims just
because somebody says so (I don't mean that is not true just want to think
by myself, it could be possible that some rounds could be... well...
simplified). Haven't found any paper about it. Just things like this
http://theory.csail.mit.edu/~yiqun/shanote.pdf that just gives a collision
example. But nothing about the weaknesses of the algorithm. And this is old
news. BTW very interesting that birthday paradox.

And being able to force a collision to a specific hash may not be very
> useful all by itself - for instance, if you're trying to collide the hash
> that the PGP signature covers in this message, you *might* be able to find
> a string of bits.  But you won't be able to make it a *plausible*
> signature
> unless your string of bits is *also* a chunk of English text, that reads
> as
> if I wrote it.  So not only do you need to be able to collide a specific
> hash, you need to do so with at least *some* control over the content of
> the text, which is even harder.


Well you could add some garbage at the end of the message. In a text message
would call attention that something is wrong (maybe because is signed and
you would not be able to tell if the key holder signed a text with that
garbage at the end or somewhere else), but not on binary content for example
a driver or an executable image that simply skips the "garbage" that causes
the collision when executed. Although a weakness will be of help to
accomplish this, making the attack to take less time. However if the attack
takes let's say 10 000 years instead of 1000 000 is well... almost the same
thing.

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/