Subject: Re: How to Calculate Signatures?

From: [email-masked] ("Hal Finney")
Date: Mon, 4 Apr 2005 11:08:05 -0700 (PDT)

Ian G wrote:
> >>I'm curious on this point.  Other than the fact that
> >>"it's broken" why is it that you see it important to
> >>repair the DSA in OpenPGP?
> > 
> Hal Finney wrote:
> > I'm not sure if you are asking why we worry about using SHA-1 at all given
> > that the attack is theoretical, or why we don't just abandon DSA keys.

Ian replied:
> I'd say it is an open question, so either or both.
>
> Hal Finney wrote:
> > For the first question, my main concern is that the SHA-1 attack
> > may get worse so that it becomes computationally feasible to find
> > collisions.  If that happens we could be vulnerable to attacks like
> > http://eprint.iacr.org/2005/067 which showed two X.509 certificates
> > with the same hash.  The attacks could become even stronger to where
> > different userids could collide.
>
> I think now I understand this as more an issue for
> WoT than documents - is that right?  (I think I'm
> deriving that from the last sentance above...)  In
> that people who have DSA keys and have lots of sigs
> are faced with losing their 'investment'.

The WoT issue related to the 2nd question about maintaining usability of
DSA keys.  The paragraph above related to the 1st question which was,
why are we worrying about the SHA-1 attack at all, given that it is
purely theoretical and no one has even exhibited a SHA-1 collision.

In the context of that question, it would apply to other situations than
just key signatures.  Ordinary document signatures could be vulnerable.
Alice could prepare a document for Bob to sign, arranging it that there
are two versions.

It could also apply to RSA users who are continuing to use SHA-1.
If the attack worsened, they could be invited to sign someone's key,
and then the data being signed could change.

Again, keep in mind that these paragraphs answer the question, why are
we worried about the attack at all.  Focus on that question in reading
the paragraphs above.

> > For the second, DSA key users do not presently have the options RSA
> > key users do to move to other hashes.  As I argued, the additional risk
> > of giving DSA users more options is not that large.  Letting them use
> > other hashes would allow them to continue to use their existing keys
> > and benefit from the signatures they have acquired on those keys.
>
>
> OK.  In risk terms it might not be that high.  But
> in cost terms, it is significant.  Any changes to
> the way signatures have to be dealt with would have
> to be promulgated through the community, as, if the
> signature verification wasn't standard and acceptable
> to all code bases, it loses its value rapidly.

I agree that if it takes that long for the change to propagate, we are
probably better off waiting for NIST to come up with FIPS 186-3 which
will specify how to use SHA-2 with DSS.

I have a faint hope that they may do something about including a hash
algorithm specifier that would make the standard more robust against
hash breaks.  Even a one octet hash ID similar to what we use in PGP
would greatly improve the flexibility.

The only reason I hold out this hope is that otherwise I don't see what
is taking them so long in releasing this spec.  It's been something like
two years since they announced that it was imminent.  If all they are
going to do is to come up with a few (p, q) size recommendations then
it shouldn't take that long.

If they don't do it, maybe we should think about doing this ourselves,
for next gen DSA keys.  We could include a one byte hash octet ID at
the front of the hash, and make the q size 8 bits bigger.  It would
mean that we are not fully DSS compliant but as Jon points out we are
not quite that way now.

Hal

---

From: David Shaw <[email-masked]>
Date: Mon, 4 Apr 2005 15:24:45 -0400

On Mon, Apr 04, 2005 at 11:08:05AM -0700, "Hal Finney" wrote:

> I agree that if it takes that long for the change to propagate, we
> are probably better off waiting for NIST to come up with FIPS 186-3
> which will specify how to use SHA-2 with DSS.

I think it would take a good long while for the change to propagate.

I don't know about other implementations, but there is no support for
this in GnuPG.  Adding support is trivial, to be sure, but getting
however many GnuPG installations to upgrade (with no compatibility
with many DSA signatures in the meantime) would be a pretty
substantial problem.

David