Subject: Re: Suggested changes for DSA2

From: [email-masked] ("Hal Finney")
Date: Mon, 27 Mar 2006 15:22:15 -0800 (PST)

David writes:
> For implementation of signature verification you can just take p and q
> straight from the public key.  You don't need to guess since the key
> has all the information you need.

With signatures, it is the verifier more than the signer who is vulnerable
and who needs to be protected.  The problem is that as the verifying
software it is my responsibility to provide some level of assurance to
the user about how strong this signature is.

Right now at best we only report the key size.  I'd like to make sure that
q is as strong as p.  Otherwise we might see a 4096 bit key with a 160 bit
q, so it is really no stronger than a 1024 bit key.  It is hard to report
to the user how strong a signature by that key should be considered to be.

This problem goes away if we standardize on the q sizes that go with
certain p sizes.  That's what I'd like to do.  Any keys that break the
rules would be considered invalid.  Maybe we don't have to just do the
FIPS ones but could extend them somewhat.

Hal

---

From: David Shaw <[email-masked]>
Date: Mon, 27 Mar 2006 21:02:15 -0500

> FIPS ones but could extend them somewhat.

Forgetting DSA2 for a moment, this isn't a new problem.  We have this
same key size / hash size mismatch possibility today with DSA1 (since
DSA in 2440 could be 768-1024 bits), and again with RSA (which can use
any hash, regardless of the key size).  Fixing the q sizes for DSA2
doesn't really solve this.

I do agree there is an issue here, but I have trouble seeing it in
terms of something that can be fixed in the standard, especially in a
reasonably future-proofed way.  It just feels a bit like pushing a
user or UI problem into the data specification.

Implementations are free to use whatever guidelines they like in
presenting signature information to the user.  It would be very
reasonable for a program to pop up some sort of "Warning: the hash
used in this signature is weaker than the key", or "this signature has
xxxx bits of assurance" or whatever sort of message is deemed most
understandable.  I just think that the onus is on the implementation
to do this, and not the standard.

That said, I would support language (perhaps in the Security
Considerations or signature sections) that read something like this:

   When verifying a signature, it may be noted that the strength of
   the signing key and the strength of the hash used are not similar.
   In such cases, implementations MAY/SHOULD warn the user that the
   overall signature strength is limited by the weakest part.  In
   extreme cases, the implementation may wish to consider the
   signature to be in error.  While conventional wisdom may change
   over time as to the strength of algorithms, at publication time,
   one such set of guidelines is [SP800].

And add a cite for [SP800] to the NIST key length / hash length guide.

David

---

From: [email-masked] (Daniel A. Nagy)
Date: Tue, 28 Mar 2006 10:46:21 +0200

> the user about how strong this signature is.

Right, but it still boils down to whether or not the verifier trusts a
certain public key. Thus, the decision needs to be made on a per-key, rather
than per-signature basis. I am not arguing here; it is just a remark.
 
> q, so it is really no stronger than a 1024 bit key.

That is not quite precise, either. Increasing the size of q and the size of p
protect against two different attacks. Large q's protect against (optimized)
brute-force or random guessing of the discrete logarithm, while large p's
protect against sieve methods. The relative strength of the two attacks is
not easily assessed. Sieve methods are getting better and better. Thus, in
the future it may very well happen that the balanced choice will be 4096
bits for p and 160 bits for q.

As desirable as describing strength in some one-dimensional quantity is, it
is hardly possible. NIST's choice of matching modulus sizes and group orders
reflect the balancing of time costs of state-of-the-art attacks with no
regard to memory costs. (by the way, this same approach is reflected in
declaring 3DES as strong as a 112-bit cipher -- as if 2^62 bits of memory
were free) This is a long-standing tradition in the main-steam crypto
community, but there is no universal consensus about this.

> It is hard to report

Yes, it is. That is one reason not to reflect _our_ judgement (even if we
could ever come to an agreement) about it in the standard.

> rules would be considered invalid. 

No, it won't go away. Moreoever, why would you declare |p|=1024 |q|=160
valid, while |p|=4096 |q|=160 invalid, while the second choice is clearly no
weaker than the first one?

Putting lower limits on both the modulus size and the group order makes more
sense, but that also does not merit more than a passing remark in the
standard. IMHO, of course.

-- 
Daniel