[spf:guess] Re: DSA and SHA-256 (It works! Or does it?! :))

[Sam Vilain]

Werner Koch wrote:
>> 1. is gpg doing the correct, FIPS-186-3 thing of throwing away the lower
>> bits?
>>     
>
> Yes.
>
> Libgcrypt does not enforce this because FIPS-186-2 does not seem to
> require it.  Libgcrypt is currently in NIST's evaluation queue but the
> project was started far prior to June 2009 when -3 was released.
>   

Right.  Is there an official test suite for that?  Might see if I can't
update Crypt::OpenPGP ... nice library, very accessible being in a HLL
and even fast when you're using it with the C PARI.  Of course most
people are moving towards GPGME but still nice if it was up to date.

>> 2. is this safe?
>>     
>
> We hope so.
>   

See, this is why I worry, from Wang (2005)¹

    Our attack naturally is applied to SHA-0 and all reduced variants
  of SHA-1.  For SHA-0, the attack is so effective that we are able to
  find real collisions of the full SHA-0 with less than 2^39 hash
  operations [16]. We also implemented the attack on SHA-1 reduced to
  58 steps and found real collisions with less than 2^33 hash
  operations. In a way, the 58-step SHA-1 serve as a simpler variant
  of the full 80-step SHA-1 which help us to verify the effectiveness
  of our new techniques.  Furthermore, our analysis shows that the
  collision complexity of SHA-1 reduced to 70 steps is less than 2^50
  hash operations.

Because SHA-256 has fewer rounds than SHA-1, from my very naïve grasp of
the subject, it seems like it could be easier to find a collision by
throwing those bits away, than by using SHA-1.  Taking the approach of
not shortening the hash output, but taking it modulus a very large prime
would seem to lose that information rather than folding it back into the
output via the 'mod q' at the end, where all the extra high bits will
have a very profound and non-linear impact on the output values.

I guess the thing would be to take one of those round/bit grids in the
SHA attack papers, and show which bits through the rounds are
"ignorable", and whether this allows more round tunneling.

Of course I'm so far out of my depth I'll have to make decompression
stops on my way out of this thread.

Sam

*1 "Finding collisions *in the *full SHA*-*1*
<http://www.springerlink.com/index/26vljj3xhc28ux5m.pdf>" X Wang, YL
Yin, H Yu - Lecture Notes in Computer Science, 2005 - Springer