Subject: Re: Suggested changes for DSA2

From: [email-masked] ("Hal Finney")
Date: Sun, 26 Mar 2006 10:02:18 -0800 (PST)

David Shaw writes:
> On Fri, Mar 24, 2006 at 12:21:42PM -0800, "Hal Finney" wrote:
> > Aside from this I think David's wording is a little unclear about "the
> > appropriate number" of leftmost bits.  Maybe we could say:
> > 
> >     DSA signatures MUST use hashes that are equal to or larger than the
> >     size of q, the group generated by the DSA key's generator value.
> >     If the chosen hash is larger than the size of q, the hash result
> >     is truncated to fit by taking a number of leftmost bits equal to
> >     the number of bits in q.  This (possibly truncated) hash function
> >     result is treated as a number and used directly in the DSA signature
> >     algorithm.
> >
> > Note that this truncation (or non-truncation) could still leave the
> > hash as bigger than q, but that is OK as the signature and validation
> > algorithms will either explicitly or implicitly take it mod q as it
> > is used.  So I don't think we have to tell them to take it mod q.
>
> I agree with your suggested change, but I'm not sure I follow this
> comment.  How could the hash still be bigger than q if we're
> explicitly truncating it to be the same size as q?

For example, we have a 1024 bit key with a 160 bit q.  We truncate a
SHA-256 hash to 160 bits.  But q < 2^160, hence the truncated hash can
still be greater than q, i.e.  q < trunc(hash) < 2^160.

I see that my proposed text still has this somewhat ambiguous reference
to "the size of q".  It also refers to the size of the chosen hash when
it should say the output size.  If I fix those two it becomes:

    DSA signatures MUST use hashes whose output size is equal to or larger
    than the number of bits of q, the group generated by the DSA key's
    generator value.  If the output size of the chosen hash is larger
    than the number of bits of q, the hash result is truncated to fit by
    taking a number of leftmost bits equal to the number of bits of q.
    This (possibly truncated) hash function result is treated as a number
    and used directly in the DSA signature algorithm.

Regarding the question of whether to allow intermediate sizes:

> I wasn't so much thinking about which q to use for intermediate p
> sizes, but rather thinking more from the verification end: namely, we
> can't stop people from generating whatever key they like, sensible or
> not.  So rather than defining the set of valid p/q pairs, and
> presumably rejecting any p or q outside the defined set, I was
> thinking of just stepping back and saying, in effect, that this isn't
> our problem to solve.  Give SHOULD guidance on what to generate
> (i.e. the FIPS list), but don't make it a MUST to lock things down to
> that list.  Otherwise, a few years from now, FIPS-186-4 will come out
> and define a p/q pair not on the FIPS-186-3 list and break all of our
> implementations.
>
> The FIPS draft refers such questions to NIST publication SP800-57,
> which actually does mention two larger p/q pairs: p=7680 q=384 and
> p=15360 q=512 (see page 63).  Not that I think that a 15360-bit DSA
> key is useful in practice in 2006, but clearly there is already
> consideration of other key sizes.

It's always a tricky question, how much we should try to enforce
security standards in a data-format document.  We do put minimum length
restrictions on the moduli to try to protect users against making one
kind of mistake, using a too-short key.  In the same way, I don't think
we should allow them to use a 160-bit q for a 3072-bit p.  This is the
spirit behind my suggestion to just allow the NIST sizes.

Allowing the bigger sizes would also be consistent with this proposal
but I don't think everyone would want to support those.

> >      * The DSA algorithm will work with any hash, but it is
> >        sensitive to the quality of the hash algorithm.  An implementation
> >        should take care which hash algorithms are used with DSA.
> >        Verifiers should be aware that even if the signer used a strong
> >        hash, an attacker could have modified a signature to use a
> >        weak one.  Only signatures issued using acceptably strong hash
> >        algorithms should be accepted as valid.

On re-reading this I have two improvements.  The second sentence is
redundant.  And the last sentence cautions verifiers about what hash
was used when the sig was "issued", but the verifier doesn't know this
(that is the point), it only knows what it sees:

     * The DSA algorithm will work with any hash, but it is
       sensitive to the quality of the hash algorithm.  Verifiers
       should be aware that even if the signer used a strong hash,
       an attacker could have modified a signature to use a weak one.
       Only signatures using acceptably strong hash algorithms should
       be accepted as valid.

Hal Finney

---

From: David Shaw <[email-masked]>
Date: Sun, 26 Mar 2006 16:55:31 -0500

> spirit behind my suggestion to just allow the NIST sizes.

I think we more or less agree on this.  My only sticking point is the
idea of allowing people to do something other than the NIST sizes.
How about we make the NIST sizes a SHOULD (like the minimum length
restrictions are SHOULD NOTs), and add a sentence after that to read
something like "Caution should be taken when deviating from the above
parameters which were carefully chosen to balance the strength of the
hash with the strength of the key." ?

That would seem to be the best of all worlds: we strongly advise
people to use the NIST sizes, tell them why we want them to use the
NIST sizes, but don't lock them down.

David

---

From: Ian G <[email-masked]>
Date: Mon, 27 Mar 2006 15:19:54 +0200

> NIST sizes, but don't lock them down.

The question is more whether a receiving implementation
should / may read non-preferred sizes.  My inclination
is to reduce them wherever possible.  I've yet to see a
real case where it has been useful to have non-standard
sizes, and I've seen many cases where incompatibilities
have sprung from overly broad readings of what was allowed.

There's also no need for the standard to say this at all.
If there was a need for a variant, then the various
implementations can try it out and implement it as a non-
standard variant.

I would vote for just allowing a subset of the NIST sizes.
That is, something like an implementation MUST accept the
NIST set, and SHOULD reject all others.  If a need for a
variant comes up, the developers have to battle it out and
justify going up against the SHOULD.  If there is a clear
need, then they'll work it out.

iang

PS:  was it Bernstein who said, be precise in what you
output, and be precise in what you accept for input?

---

From: David Shaw <[email-masked]>
Date: Mon, 27 Mar 2006 10:01:20 -0500

> need, then they'll work it out.

It is not the place of a data format standard to hold people's hands
to that extent.  We (correctly) don't tell people to reject signatures
from a 512-bit RSA key.  That's not our job in the standard.  If an
*implementation* wants to do that, that's just fine, but it does not
need permission from the standard to do it.

David

---

From: David Shaw <[email-masked]>
Date: Mon, 27 Mar 2006 10:23:54 -0500

>        Only signatures using acceptably strong hash algorithms should

Yes, I made a similar change in the "round 2" changes for the same
reason.  I've fixed the redundant second sentence for round 3.

David

---

From: [email-masked] (Daniel A. Nagy)
Date: Mon, 27 Mar 2006 17:44:27 +0200

> need permission from the standard to do it.

I agree with David here. The standard's purpose is to ensure
interoperability. It should tell us the sematics behind sequences of bytes.
It is up to the implementation to make decisions based on these semantics.
Valid reasons to exclude certain combinations from the standard include
ambiguity of interpretation, inherent insecurity or a wide installed base of
incompatible implementations, but not the possibility of weird uses, IMHO.

Regards,

-- 
Daniel

---

From: Jon Callas <[email-masked]>
Date: Mon, 27 Mar 2006 13:25:38 -0800

> incompatible implementations, but not the possibility of weird  

I agree as well with both Davids.

As an observation, in 2440 one of the things we allowed was deviation  
from DSS because the rough consensus had a certain amount of  
grumpiness with the US Government. In practice, hardly anyone did  
anything different with DSA than DSS. We even removed hash functions.

Many things have changed in the last decade, but toeing the exact  
NIST line or even being like them only moreso is going a bit too far.  
In the next decade, we're going to see a lot of advancement in hash  
functions. Someone is going to want to use those new hash functions  
with DSA, and it would be nice to be able to move faster than NIST.

Let's suppose someone comes up with a new hash function that is 251  
bits. (I picked 251 because it's prime and less than 256.) We don't  
want a constitutional crisis over using it. We want to be flexible  
enough that it's pretty obvious how to extend OpenPGP to use new hash  
functions with DSA.

	Jon

---

From: Ian G <[email-masked]>
Date: Thu, 30 Mar 2006 15:57:16 +0200

> I agree as well with both Davids.

Well, I can see I've lost the consensus battle on
this one - but I would propose that the purpose of
the ID is security, over and above interoperability,
and that is an entirely valid reason to exclude
"Weird Uses."

In general, with security, the less choice the better.

> from DSS because the rough consensus had a certain amount of  grumpiness 
> with the US Government. In practice, hardly anyone did  anything 
> different with DSA than DSS. We even removed hash functions.
> 
> Many things have changed in the last decade, but toeing the exact  NIST 
> line or even being like them only moreso is going a bit too far.  In the 
> next decade, we're going to see a lot of advancement in hash  functions. 
> Someone is going to want to use those new hash functions  with DSA, and 
> it would be nice to be able to move faster than NIST.

As to the political circumstances of the past, it is
true that the community did certain daft things that
reduced security in response to the USG's own set of
daft things that reduced security.  It's definately
not good to follow either lead...

> enough that it's pretty obvious how to extend OpenPGP to use new hash  

It seems that PGP's design bends over backwards
to be flexible.  It's a lot of fun for crypto-
plumbers;  in fact it looks like it has been
designed as a toykit for programmers to muck
around with algorithms.

In practice, though, this flexibility seems to
rarely be used in any sensible way.

And, again, in practice, this flexibility causes
endless discussions on this mailgroup - as seen
this week - and other places where implementors
and users try and figure what goes with what.

It all takes up time from other important things.

So I guess what I'm saying is ... all this
flexibility ... how many times has it been used
to advantage, and how many times to disadvantage?

What's the cost-benefit analysis here?

iang