Understanding Problem with rsa min key length 1024

[Mark D. Baushke]

Hi Daniel,

I agree with your points and I also agree that a default of 2048 now and
3072 bits in a few years for OpenSSH may be desirable.

There was a bug in some SSHv2 implementatons where 1023 bit keys were
generated when 1024 bit keys were asked.

  https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=661152

  https://bugzilla.mozilla.org/show_bug.cgi?id=360126

Regarding strength, see also this article:
  
  https://en.wikipedia.org/wiki/Key_size

which has a reference to this letter on RSA Key Size:

  https://web.archive.org/web/20170417095741/https://www.emc.com/emc-plus/rsa-labs/historical/twirl-and-rsa-key-size.htm


    Executive Summary

    The popular 1024-bit key size for RSA keys is becoming the next
    horizon for researchers in integer factorization, as demonstrated by
    the innovative “TWIRL” design recently proposed by Adi Shamir and
    Eran Tromer. The design confirms that the traditional assumption
    that a 1024-bit RSA key provides comparable strength to an 80-bit
    symmetric key has been a reasonable one. Thus, if the 80-bit
    security level is appropriate for a given application, then TWIRL
    itself has no immediate effect. Many details remain to be worked
    out, however, and the cost estimates are inconclusive. TWIRL
    provides an opportunity for review of key sizes in practice; RSA
    Laboratories’ revised recommendations are given in Table 1 below.

... elided ...

    The 112-bit security level is somewhat higher than needed now, but
    it is convenient since triple-DES is already widely implemented, and
    the 2048-bit RSA key size key size is convenient as it is already
    supported for root keys. In the recent NESSIE recommendations
    [NESSIE03], a minimum of 1536 bits is suggested for RSA signature
    keys. This may be an appropriate interim measure, but due to the
    lengthy process of upgrading key sizes, 2048 bits is a better goal.
    Based on these considerations, RSA Laboratories offers the following
    recommendations for key sizes:

    +-------------------------+-----------------+-------------+
    | Protection Lifetime     | Minimum         | Minimum RSA |
    | of Data                 | symmetric       | key size    |
    |                         | security level  |             |
    +-------------------------+-----------------+-------------+
    | 2003 – 2010             | 80 bits         | 1024 bits   |
    +-------------------------+-----------------+-------------+
    | 2003 – 2030             | 112 bits        | 2048 bits   |
    +-------------------------+-----------------+-------------+
    | 2003 – 2031 and Beyond  | 128 bits        | 3072 bits   |
    +-------------------------+-----------------+-------------+

    Table 1. Recommended minimum symmetric security levels and RSA key
    sizes based on protection lifetime. [I pivoted the table for easier
    reading in email]

The United States National Institute of Standards and Technology (NIST)
also has a letter on key strengths:

  https://csrc.nist.gov/csrc/media/projects/key-management/documents/transitions/transitioning_cryptoalgos_070209.pdf

as well as a Special Publication which recomments RSA 2048-bit keys for now.

  https://nvlpubs.nist.gov/nistpubs/specialpublications/nist.sp.800-57pt3r1.pdf

as well as this document:

  NIST Special Publication 800-131A Revision 2
  Transitioning the Use of Cryptographic Algorithms and Key Lengths
  https://doi.org/10.6028/NIST.SP.800-131Ar2

	Enjoy!
	-- Mark