Mailing List Archive

Understanding Problem with rsa min key length 1024
Hello,


Sometime ago min rsa key length was increased to 1024 bit and i have a
little understanding problem with this.
I hope somebody with some crypto-experience can enlighten me. To make
that clear, that is not about allowing lower keys in general.
Personally i would tend to use even longer keys(2048bit+).
However Due nature of RSA-algorithm in case of 1024bit this might result
in a key length of 1023 or 1024 bit.

By default with a RSA Min Key length of 1024 this means all 1023bit
length keys are rejected, while there is no real advantage regarding the
complexity of the key when enforcing 1024bit length only.

So here my question, would rejecting the 1023 bit keys not simply limit
the range of possible keys and therefore lower security of the
encryption?
So shouldn't be the min key length 1023bit to ensure that the whole
range of keys can be used?

Sorry for the stupid questions, just trying to understand(i'm no
cryptographer).

Have a nice day.

regards,
Daniel
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@mindrot.org
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
Re: Understanding Problem with rsa min key length 1024 [ In reply to ]
On Thu 2019-04-11 15:56:50 +0200, schlifka@geekpit.org wrote:

> Sometime ago min rsa key length was increased to 1024 bit and i have a
> little understanding problem with this.
> I hope somebody with some crypto-experience can enlighten me. To make
> that clear, that is not about allowing lower keys in general.
> Personally i would tend to use even longer keys(2048bit+).
> However Due nature of RSA-algorithm in case of 1024bit this might result
> in a key length of 1023 or 1024 bit.

if some RSA key generation algorithm is generating a 1023-bit key when
it is asked for a 1024-bit key, that implementation sounds buggy.

The generally-accepted understanding of a 1024-bit RSA key is one where
bit 1023 is set to 1 (and all higher bits are set to 0). (i'm assuming
that the LSB is "bit 0", so "bit 1023" is the 1024th bit)

a 1023-bit RSA key is one where bit 1022 is 1 and bit 1023 (and all
higher bits) are set to 0.

> By default with a RSA Min Key length of 1024 this means all 1023bit
> length keys are rejected, while there is no real advantage regarding the
> complexity of the key when enforcing 1024bit length only.

I think this is a "slippery slope" line of reasoning, which can be
extended against making any sort of cutoff -- clearly a bad outcome,
because we'd like to draw the line someplace. For example, 17-bit RSA
keys are clearly inappropriate for use on the public Internet.

1024-bit RSA keys are obsolescent at best today -- arguably we should
have a higher limit than 1024 itself (i wouldn't object to a 2048-bit
RSA cutoff by default, it's 2019!). And a "would-be 1024-bit" RSA keys
generated by a buggy implementation is probably below the threshhold of
what we want to tolerate.

does that make sense?

--dkg
Re: Understanding Problem with rsa min key length 1024 [ In reply to ]
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
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@mindrot.org
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
Re: Understanding Problem with rsa min key length 1024 [ In reply to ]
On Thu 2019-04-11 09:48:01 -0700, Mark D. Baushke wrote:
> 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

right, this is a 7-year-old bug in putty. i don't mind asking people
who still use material from that era to upgrade. :)

--dkg
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@mindrot.org
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
Re: Understanding Problem with rsa min key length 1024 [ In reply to ]
On Fri, 12 Apr 2019 at 02:53, Mark D. Baushke <mdb@juniper.net> wrote:
[...]
>
> 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.

The soon-to-be-released 8.0 will increase the default RSA key size to
3kbit for pretty much the reasons you cite.

http://anongit.mindrot.org/openssh.git/commit/?id=f47269ea67eb4ff87454bf0d2a03e55532786482
http://anongit.mindrot.org/openssh.git/commit/?id=26e0cef07b04479537c971dec898741df1290fe5

--
Darren Tucker (dtucker at dtucker.net)
GPG key 11EAA6FA / A86E 3E07 5B19 5880 E860 37F4 9357 ECEF 11EA A6FA (new)
Good judgement comes with experience. Unfortunately, the experience
usually comes from bad judgement.
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@mindrot.org
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
Re: Understanding Problem with rsa min key length 1024 [ In reply to ]
On 11/4/19 11:26 pm, schlifka@geekpit.org wrote:
> However Due nature of RSA-algorithm in case of 1024bit this might
> result in a key length of 1023 or 1024 bit.

I've been confused by this and am astounded by the information I've
found.  For example,

Q: I am receiving warning messages regarding key lengths.  What do
these messages mean, and how can I prevent them?

A: The key-length warning messages you are seeing are sent by
OpenSSH when it encounters certain defective RSA or DSA keys that
are sometimes generated by a bug in the ssh-keygen program (in
commercial SSH).  These defective keys are Pubkey Authentication
keys whose Most Significant Bit (MSB) is not set.  Thus, these keys
ar efrequently half as long as advertised (they advertise as full
length.) ...

Next Generation SSH2 Implementation: Securing Data in Moption,
Chapter 6, Dale Liu

The problem with this answer is that a random key can have MSB zero or
one.  If MSB is known to be one, then the key is 1023-bits prefixed with
a constant one.

When picking random prime 512-bit numbers, the number 2 is a valid
choice.  If you disallow that choice then you're not picking from the
full 512-bit space.

Tragically, as I understand, the logic that Dale espouses is entrenched
and we have only half the key space that's advertised. (The key space is
the upper-half of the 1024-bit range.)

In RSA keys, the key is the product of two 512-bit prime numbers.  If
those numbers are selected on the basis that both have their MSB set,
then the key space is only 1022 bits.

_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@mindrot.org
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
Re: Understanding Problem with rsa min key length 1024 [ In reply to ]
On Fri 2019-04-12 16:11:48 +0930, David Newall wrote:
> When picking random prime 512-bit numbers, the number 2 is a valid
> choice.  If you disallow that choice then you're not picking from the
> full 512-bit space.

that's correct. However, most people and most attack machinery already
know about 2 being a prime number and have very cheap ways of testing
for whether 2 is one of your supposedly secret primes. If you use 2 as
one of your factors in an RSA key, it will be immediately cracked,
despite it being a valid "4096-bit prime" according to the definition
you're using here.

Ensuring that the MSB is set is a way of ensuring that the most
commonly-known primes are not used in the generation of RSA keys.

> In RSA keys, the key is the product of two 512-bit prime numbers.  If
> those numbers are selected on the basis that both have their MSB set,
> then the key space is only 1022 bits.

It's even worse than that, because primes are sparse! so the actual
space being searched (all primes of a given length) is *much* smaller
than 1022 bits once we weed out all the composite numbers ;)

But even taking the labeling of the "key space" as you've given it, if
your concern is that 1022 bits is too small of a key space (and it is,
given how sparse primes are!), then the right approach in 2019 is to use
3072-bit keys (which you rightly point out are "only" choosing from a
3070-bit "key space"), not to quibble about whether it ought to be OK to
select 2 as one of the factors.

All the best,

--dkg
Re: Understanding Problem with rsa min key length 1024 [ In reply to ]
On Fri, Apr 12, 2019 at 08:39:49AM -0400, Daniel Kahn Gillmor wrote:
> But even taking the labeling of the "key space" as you've given it, if
> your concern is that 1022 bits is too small of a key space (and it is,
> given how sparse primes are!), then the right approach in 2019 is to use
> 3072-bit keys (which you rightly point out are "only" choosing from a
> 3070-bit "key space"), not to quibble about whether it ought to be OK to
> select 2 as one of the factors.

FWIW, RSA 1024bit keys have approximately 80bits of strength. RSA2048 is
112 bits (and is the minimum NIST requirement). RSA3072 is 128bit.


--

rgds
Stephen
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@mindrot.org
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev