Re: Non-SHA-1 fingerprints

On 05/04/2009 06:04 PM, Daniel A. Nagy wrote:
> For fingerprints, MDC and self-signatures, collision-resistance does not 
> matter,
> only the one-way property. So I think it is totally safe to postpone 
> discussion
> until SHA3 is selected.
The more that i consider this, the more important it seems.  Thank you
for emphasizing it, Daniel.

If i understand you correctly, your point is that fingerprints and
self-signatures use hashes over data that is provided entirely by the
signer, covering nothing that is supplied by an outside party.

Since "birthday" attacks rely on the attacker generating an arbitrary
collision, providing one side of it for signing by the victim, and then
transferring the signature onto the other side of the discovered
collision, they do not work against material under full control of the
signer (like fingerprints and self-sigs).

Even if the recent claims of O(2^52) (instead of the
theoretically-optimal 2^80) operations to generate a colliding pair were
to scale proportionally to attacks against the one-wayness of SHA-1,
that would mean O(2^104) (instead of 2^160) operations to find a message
that hashes to a given value.  i have no idea if these sort of results
can actually scale this way, but i  imagine we'd hear a much larger
hullabaloo if someone had announced an  attack against the one-wayness
of SHA-1 with less than O(2^104) operations.

Anyway, since 2^104 is still outside the capabilities of well-funded
organizations, we have breathing room on these parts of the
specification that only rely on collision-resistance.

Did i get anything wrong above?  I apologize if this is elementary for
everyone else, i'm just trying to make sure i understand the ideas involved.

        --dkg

signature.asc
Description: OpenPGP digital signature