Creating 32768 bit RSA keys for fun and profit

Have you ever wondered how long it would take to create a 32768 bit RSA key with ssh-keygen? Well, I did.

   $ time ssh-keygen -t rsa -b 32768 -f ~/.ssh/tmp32768 -N foobar -q
   real    244m31.259s
   user    244m15.664s
   sys     0m4.736s

In other words, on my test system (AMD X2 CPU with 1.8 GHz per core) it took ca. 4 hours. This is likely very dependent on how much entropy you can get (and how fast), so take the numbers with a grain of salt. A second key with 32767 bits (one less) took 16 hours, for instance.

The resulting tmp32768 (private key) file is ca. 25 KB big, the (public key) file is 5 KB big.

There's likely no noticeable performance hit for ssh or scp AFAICS, as all data transfers are done with a symmetrical session key, not the RSA key itself. Only the initial connection "handshake" will take ca. 40 seconds longer...

And yes, 32768 is the maximum RSA key size you can currently create with OpenSSH, go file a bug report if that's not enough for you ;-) However, as I then noticed, this key will not actually work. When you put it in some authorized_keys file and try to login, the handshake will fail and the server-side will see the following error in /var/log/auth.log:

  sshd[xxxxxx]: error: RSA_public_decrypt failed: error:04067069:lib(4):func(103):reason(105)

I first thought I found an off-by-one error, but the 32767 bit key (one bit less) didn't work either. After looking through the OpenSSH and OpenSSL code as well as the RSA_private_decrypt(3SSL) manpage a bit, I saw that OpenSSH uses the RSA_PKCS1_PADDING parameter. My current theory is thus that some padding is making the key not work. I'm now creating a key with 11 bits less bits than 32768, let's see what happens. For the record, a key with 16384 bits does work just fine.

Anyway, I'll probably report this as "bug" (more a theoretical than a practical problem, though) as ssh-keygen let's you generate RSA keys which will never work in practice...


Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Have you tried using a key

Have you tried using a key of say.. 5003 bits?
ssh-keygen generates this just fine, but iirc it did not work to login using this key..

(and it is a lot faster to generate&test this, than to generate a larger odd-bitlength key)

Finally: if odd-bitlength keys work just fine, why should we stick to powers of 2 at all?

RSA key sizes

Yes, I've tried various key sizes which are not a power of two (and they work), as well as key sizes which are odd numbers (which also work). I don't know any reason not to use "non-standard" key sizes, but it's an interesting question indeed.

I'll do some more investigations and testing, more info later...

Non-standard key sizes

It may be useful to avoid non standard key sizes in case of another vulnerability in the key-generating code. Many people (relatively) quickly generated all the (weak) keys of the standard sizes after the recent fiasco, in order to brute-force unpatched machines. Using a non-standard key size, and a larger key, would help (not prevent) being exploited if something similar happened again.