headers
Jon Callas | 5 May 2009 19:58
Gravatar

I don't think that collides the way you think it does


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Adi Shamir has pointed out for years now that no one has found *any*  
first or second preimage collision for SHA1. I'll shill for him here.

The new results for 2^52 work, assuming it's actually doable, are  
still for migrating a bitstring into two dependent bitstrings that  
collide. This has significance for people who run CAs with sequential  
serial numbers, or who want to tweak PDFs to project the future, or  
create binary distributions that have and do not have malware. It's  
serious *for* *those* *and* *similar* *cases*.

It does *not* mean that you can get a collision on an existing  
signature, nor on an existing fingerprint, nor on an MDC, etc. We are  
still sitting at *zero* first and second preimage collisions.

I think that we should push through the generic fingerprint proposal.  
I sorta-kinda picked up the ball on that to work with Derek, but if  
there's anyone else who wants it (or who wants to co-author with Derek  
and me), I'm happy to have less work to do.

I also think it's completely reasonable for an implementation to back  
away from SHA1 with all due speed -- but you're supposed to be doing  
that by 2010, anyway!

	Jon

-----BEGIN PGP SIGNATURE-----
(Continue reading)

Permalink | Reply |
headers
Florian Weimer | 8 May 2009 22:47
Picon

Re: I don't think that collides the way you think it does


* Jon Callas:

> The new results for 2^52 work, assuming it's actually doable, are  
> still for migrating a bitstring into two dependent bitstrings that  
> collide. This has significance for people who run CAs with sequential  
> serial numbers, or who want to tweak PDFs to project the future, or  
> create binary distributions that have and do not have malware. It's  
> serious *for* *those* *and* *similar* *cases*.

Unfortunately, signing someone else's key and user ID is a similar
case.  You don't know what you're being asked to sign, and you haven't
created the document yourself.  And a photo ID gives you many bits to
play with.

In the abstract, you do not actually need collision resistance (and
totally keyless hashes) for OpenPGP-like protocols, but current
practice is certainly different.  IMHO, an eventual OpenPGP successor
should prepend salts/IVs in front of signatures.  Of course, this
might be used as a relatively high-bandwidth covert channel, but it
means that the hash function will likely last somewhat longer.
Permalink | Reply |
headers
Daniel Franke | 5 May 2009 21:18
Picon
Favicon

Re: I don't think that collides the way you think it does

Jon Callas <jon <at> callas.org> writes:

> Adi Shamir has pointed out for years now that no one has found *any*  
> first or second preimage collision for SHA1. I'll shill for him here.
>
> The new results for 2^52 work, assuming it's actually doable, are  
> still for migrating a bitstring into two dependent bitstrings that  
> collide. This has significance for people who run CAs with sequential  
> serial numbers, or who want to tweak PDFs to project the future, or  
> create binary distributions that have and do not have malware. It's  
> serious *for* *those* *and* *similar* *cases*.

I think you mean "no one has found any first or second preimage
*attacks* for SHA-1".  To the best of my knowledge, nobody has found any
SHA-1 collisions at all, either chosen or otherwise.  The 2^52 result is
still theoretical, because while 2^52 hash operations is tractable for a
WFO, it's still a formidable amount of work, and Cameron McDonald is not
a WFO.

Preimage attacks are hard.  Even long, long-ago deprecated hash
functions have held up well agaist them.  The one in the worst shape is
MD2, and that attack requires 2^104 operations (vs. 2^128 brute force).
I'm pretty confident that by the time there's a computer that can do
2^104 of anything, nobody is going care about my secrets.

Here's a threat model I suggest for future work on OpenPGP: assume that
the hash function is ideal, but that the adversary has an oracle that
takes as input two messages and pointers to n/2 bits of each message
(where n is the digest length), and outputs colliding messages by
filling in those bits.  In other words, preimage attacks are impossible
(Continue reading)

Permalink | Reply |
headers
Daniel A. Nagy | 6 May 2009 01:00

Re: I don't think that collides the way you think it does

Daniel Franke wrote:
> Jon Callas <jon <at> callas.org> writes:
> 
>> Adi Shamir has pointed out for years now that no one has found *any*  
>> first or second preimage collision for SHA1. I'll shill for him here.
>>
>> The new results for 2^52 work, assuming it's actually doable, are  
>> still for migrating a bitstring into two dependent bitstrings that  
>> collide. This has significance for people who run CAs with sequential  
>> serial numbers, or who want to tweak PDFs to project the future, or  
>> create binary distributions that have and do not have malware. It's  
>> serious *for* *those* *and* *similar* *cases*.
> 
> I think you mean "no one has found any first or second preimage
> *attacks* for SHA-1".  To the best of my knowledge, nobody has found any
> SHA-1 collisions at all, either chosen or otherwise.  The 2^52 result is
> still theoretical, because while 2^52 hash operations is tractable for a
> WFO, it's still a formidable amount of work, and Cameron McDonald is not
> a WFO.

Just to give you some perspective what WFO means at this day and age: my
cryptography lab at the University has just built and tested a DES cracker that
cost us less than €20000 EUR. It iterates through the 56-bit key space in about
one week.

We are considering using it for finding a SHA1 collision using these new
results. But, as noted above, this would be a collision where both pre-images
are carefully chosen by the attacker.

--

--
(Continue reading)

Permalink | Reply |
headers
Jon Callas | 5 May 2009 23:30
Gravatar

Re: I don't think that collides the way you think it does


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On May 5, 2009, at 12:18 PM, Daniel Franke wrote:

> * PGP Signed by an unknown key
>
> Jon Callas <jon <at> callas.org> writes:
>
>> Adi Shamir has pointed out for years now that no one has found *any*
>> first or second preimage collision for SHA1. I'll shill for him here.
>>
>> The new results for 2^52 work, assuming it's actually doable, are
>> still for migrating a bitstring into two dependent bitstrings that
>> collide. This has significance for people who run CAs with sequential
>> serial numbers, or who want to tweak PDFs to project the future, or
>> create binary distributions that have and do not have malware. It's
>> serious *for* *those* *and* *similar* *cases*.
>
> I think you mean "no one has found any first or second preimage
> *attacks* for SHA-1".  To the best of my knowledge, nobody has found  
> any
> SHA-1 collisions at all, either chosen or otherwise.  The 2^52  
> result is
> still theoretical, because while 2^52 hash operations is tractable  
> for a
> WFO, it's still a formidable amount of work, and Cameron McDonald is  
> not
> a WFO.
(Continue reading)

Permalink | Reply |

Gmane