Subject: Proposal and intent to implement "dsa-sha2-256" SSH key algorithm

From: denis bider <[email-masked]>
Date: Tue, 27 Oct 2015 22:50:09 +0000

Hey everyone,

so, over the past several years, it looks like everyone has proverbially screwed the pooch with regard to plain old DSA key sizes larger than 1024 bits.

OpenSSH is now going so far as to have dropped ssh-dss in its default  configuration, which is reasonable, given that this algorithm is now only useful  for 1024-bit DSA.

Everyone is migrating now to ECDSA over NIST curves or Ed25559,  which is all nice and well - these appear to be strong algorithms,  according to information available at this time.

Still, I think it's a pity for larger DSA keys to never have had a chance; but more than sentimentalism, I think we're losing out on heterogeneity and backup options in case something, anything, turns out to be wrong in Elliptic Curve territory.

Now, if we want to agree on some way to implement large DSA keys, the "ssh-dss" algorithm name is tainted for use with larger key sizes, because there are implementations out there that implement them in incompatible ways:

- There were older versions of OpenSSL and OpenSSH that implemented 2048-bit modulus, but kept 160-bit subgroup. This did not effectively increase the security of the scheme, compared to 1024-bit modulus.

- Our (Bitvise) implementation predates FIPS 186-3 by a year. It supports a larger modulus, and appropriately larger subgroups, BUT continues to use SHA-1 as the hash function. After FIPS 186-3, other implementations of larger DSA keys, such as Windows CNG, support the larger DSA keys in conjunction with SHA-2.

- A majority of other "ssh-dss" implementations support only 1024-bit key sizes, and can't verify signatures with larger DSA keys under that scheme.

Larger DSA keys need a new scheme name for compatibility reasons.

I therefore suggest a new SSH key algorithm, dsa-sha2-256, which cherry-picks from FIPS 186-3 the following two options:

L = 2048, N = 256
L = 3072, N = 256

In other words:
- modulus size is either 2048 or 3072
- subgroup size is 256 bits
- hash function is SHA2-256

I choose the name "dsa-sha2-256", rather than a suffixed name ("[email-masked]") for the following reasons:

- Suffixed names are overly long and clumsy. If I were to choose a suffixed name instead, I would go with just "...@bv".

- Suffixed names complicate standardization. If a suffixed algorithm is commonly implemented, there's pressure to have a version with a non-suffixed name, and now we have multiple names for the same thing.

- I don't see many ways for "dsa-sha2-256" to be implemented incorrectly or incompatibly by a reasonable implementor. There's really only one DSA, the one specified in FIPS 186. This has four variants. The suffix -sha2-256 explicitly specifies which hash function to use, and strongly suggests use of the 256-bit subgroup sizes.

Unless someone has a strong and reasonable objection, I intend to  implement this for Bitvise SSH Client and Server 7.xx as described above.

Comments welcome.

---

From: [email-masked] (Niels Möller)
Date: Wed, 28 Oct 2015 14:47:47 +0100

denis bider <[email-masked]> writes:

> I therefore suggest a new SSH key algorithm, dsa-sha2-256, which
> cherry-picks from FIPS 186-3 the following two options:
>
> L = 2048, N = 256
> L = 3072, N = 256
>
> In other words:

Makes sense to me. 

Last time I looked at doing larger DSA, I had trouble finding any test
vectors. Does FIPS-186 include any now?

> I choose the name "dsa-sha2-256", rather than a suffixed name
> ("[email-masked]") for the following reasons:

I don't quite agree, but I don't have any strong objection either.

I think it would be nice with an (informational?) RFC spelling out those
details, and providing a few test vectors. Any then a non-suffixed name
is fully appropriate (and as far as I remember, the ietf requirements
for a new ssh algorithm name are pretty weak).

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

---

From: "Mark D. Baushke" <[email-masked]>
Date: Wed, 28 Oct 2015 07:06:04 -0700

Hi denis,

denis bider <[email-masked]> writes:

> Now, if we want to agree on some way to implement large DSA keys, the
> "ssh-dss" algorithm name is tainted for use with larger key sizes,
> because there are implementations out there that implement them in
> incompatible ways:
> 
> - There were older versions of OpenSSL and OpenSSH that implemented
>   2048-bit modulus, but kept 160-bit subgroup. This did not
>   effectively increase the security of the scheme, compared to
>   1024-bit modulus.
> 
> - Our (Bitvise) implementation predates FIPS 186-3 by a year. It
>   supports a larger modulus, and appropriately larger subgroups, BUT
>   continues to use SHA-1 as the hash function. After FIPS 186-3, other
>   implementations of larger DSA keys, such as Windows CNG, support the
>   larger DSA keys in conjunction with SHA-2.

If you are going to go there, you will want to write another RFC and
probably use FIPS 186-4 Section 4 "The Digital Signature Algorithm
(DSA)" as the normative reference.

> - A majority of other "ssh-dss" implementations support only 1024-bit
>   key sizes, and can't verify signatures with larger DSA keys under
>   that scheme.
> 
> - Suffixed names are overly long and clumsy. If I were to choose a
>   suffixed name instead, I would go with just "...@bv".
> 
> - Suffixed names complicate standardization. If a suffixed algorithm
>   is commonly implemented, there's pressure to have a version with a
>   non-suffixed name, and now we have multiple names for the same
>   thing.
> 
> - I don't see many ways for "dsa-sha2-256" to be implemented
>   incorrectly or incompatibly by a reasonable implementor. There's
>   really only one DSA, the one specified in FIPS 186. This has four
>   variants. The suffix -sha2-256 explicitly specifies which hash
>   function to use, and strongly suggests use of the 256-bit subgroup
>   sizes.
> 
> Unless someone has a strong and reasonable objection, I intend to
> implement this for Bitvise SSH Client and Server 7.xx as described
> above.
> 
> Comments welcome.

You have already been through co-authoring RFC 6668, so writing another
RFC for dsa-sha2-256 should not be that hard of a thing for you to do.

Information on test vectors for DSA may be found here:

  http://csrc.nist.gov/groups/STM/cavp/documents/dss2/dsa2vs.pdf

The test vectors for DSA2 are here

  http://csrc.nist.gov/groups/STM/cavp/documents/dss/186-3dsatestvectors.zip

(Yes, they are still the same as FIPS 186-3.)

	-- Mark

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 28 Oct 2015 13:52:33 +0000

If proceeding with this, it'd be good to pass it by the
CFRG [1] list for comment.

For example, in discussion of signature schemes based on
new curves, CFRG recently preferred deterministic signatures,
I'm not sure whether this proposal is the same i that respect
or not.

Cheers,
S.

[1] https://irtf.org/cfrg

---

From: [email-masked] (Niels Möller)
Date: Thu, 29 Oct 2015 05:01:28 +0100

> new curves, CFRG recently preferred deterministic signatures,

A standard (including test vectors) on how to do deterministic DSA would
be nice. But independent of the ssh protocol.

Regards,
/Niels

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Wed, 28 Oct 2015 17:31:57 -0400

> ("[email-masked]") for the following reasons:

Please don't do that, unless you are going to write and publish an IETF
consensus RFC and register the name properly.  Just making up names
leads to collisions and resulting interop problems, which is a very real
possibility if someone else is thinking the same as you but isn't active
on this list.

Also, with no registration, someone seeing this and wanting to
interoperate has no idea where to look for a specification.

> suffixed name instead, I would go with just "...@bv".

Please don't do that either.  Besides being non-compliant, it again
leaves anyone wanting to interoperate with no idea how to find a spec.

> - Suffixed names complicate standardization. If a suffixed algorithm is
> commonly implemented, there's pressure to have a version with a
> non-suffixed name, and now we have multiple names for the same thing.

Yes, that's an issue, if the thing actually gets standardized.  The
right answer is to keep using the original name, rather than inventing a
new one, unless the algorithm has actually changed during the
standardization process.

> incorrectly or incompatibly by a reasonable implementor. There's really
> only one DSA, the one specified in FIPS 186. This has four variants.
> The suffix -sha2-256 explicitly specifies which hash function to use,
> and strongly suggests use of the 256-bit subgroup sizes.

Well, someone could decide to implement only one of the two modulus
sizes available with 256-bit subgroups.  Or, they could decide that all
four options are permissible, as long as the hash is SHA-256.  I think
it would be desirable to publish an RFC to nail these sorts of things
down.

-- Jeff

---

From: Jon Bright <[email-masked]>
Date: Wed, 28 Oct 2015 11:10:28 +0100

The algorithm/idea itself sounds reasonable, but why not write this up as a
short RFC and get IANA to actually assign the name?

On 27 October 2015 at 23:50, denis bider <[email-masked]> wrote:

> Hey everyone,
>
> so, over the past several years, it looks like everyone has proverbially
> screwed the pooch with regard to plain old DSA key sizes larger than 1024
> bits.
>
> OpenSSH is now going so far as to have dropped ssh-dss in its default
> configuration, which is reasonable, given that this algorithm is now only
> useful for 1024-bit DSA.
>
> Everyone is migrating now to ECDSA over NIST curves or Ed25559, which is
> all nice and well - these appear to be strong algorithms, according to
> information available at this time.
>
> Still, I think it's a pity for larger DSA keys to never have had a chance;
> but more than sentimentalism, I think we're losing out on heterogeneity and
> backup options in case something, anything, turns out to be wrong in
> Elliptic Curve territory.
>
> "ssh-dss" algorithm name is tainted for use with larger key sizes, because
> there are implementations out there that implement them in incompatible
> ways:
>
> 2048-bit modulus, but kept 160-bit subgroup. This did not effectively
> increase the security of the scheme, compared to 1024-bit modulus.
>
> - Our (Bitvise) implementation predates FIPS 186-3 by a year. It supports
> a larger modulus, and appropriately larger subgroups, BUT continues to use
> SHA-1 as the hash function. After FIPS 186-3, other implementations of
> larger DSA keys, such as Windows CNG, support the larger DSA keys in
> conjunction with SHA-2.
>
> - A majority of other "ssh-dss" implementations support only 1024-bit key
> sizes, and can't verify signatures with larger DSA keys under that scheme.
>
> - I don't see many ways for "dsa-sha2-256" to be implemented incorrectly
> or incompatibly by a reasonable implementor. There's really only one DSA,
> the one specified in FIPS 186. This has four variants. The suffix -sha2-256
> explicitly specifies which hash function to use, and strongly suggests use
> of the 256-bit subgroup sizes.
>
> implement this for Bitvise SSH Client and Server 7.xx as described above.
>
> Comments welcome.
>
>