GnuPG 4096 bit limit

Question

Why is RSA keys in GnuPG limited to 4096 bits?

Would it be illegal for me to modify the source to increase the max size?

ssh-keygen does not have this limitation (e.g., I can create a key that's 32768 bits long). Why is that?

Answer 1

There is pretty sensible explanation (for similar question) by Fire Ant at Security Forums:

http://www.security-forums.com/viewtopic.php?p=317962#317962

All rights reserved there, but fair use citation of short excerpt shouldn't be inappropriate methinks:

Key sizes over 4096 are not currently supported in GPG. The reason for this is that 8192 keys are very slow. If you require a key greater than 4096-bit then you should really thing about what you are using that key for?

Answer 2

At keylength.com there is this:-

To protect a 256-bit symmetric key (e.g. AES-256), you may consider using at the minimum a 17120-bit asymmetric system (e.g. RSA).

The 4096 bit limit can be raised as described in a short article entitled "Generate large keys with GnuPG", reproduced below. This was done for the gnupg package in homebrew to allow for 8192 bit keys: PR 4201. A word of caution about memory allocation for the larger keys: comp.security.pgp.tech.

Generate large keys with GnuPG | David Norman

If you'd like to generate larger keys than 4096 bits with GnuPG, you can compile a new version that increases the upper limit of 4096. You'll probably find yourself generating it as RSA. Download the patch to your un-tared gnupg-1.4.19 directory and apply it with:

usbdrive@sandisk-extreme64:~/gnupg-1.4.19$ patch -p0 < gnupg_1.4.19_large_keygen.patch
patching file g10/keygen.c
usbdrive@sandisk-extreme64:~/gnupg-1.4.19$ ./configure --enable-large-secmem
[...]
checking whether to allocate extra secure memory... yes
[...]
usbdrive@sandisk-extreme64:~/gnupg-1.4.19$ make -j2
usbdrive@sandisk-extreme64:~/gnupg-1.4.19$ make check
usbdrive@sandisk-extreme64:~/gnupg-1.4.19$ sudo make install
usbdrive@sandisk-extreme64:~/gnupg-1.4.19$ gpg --gen-key --enable-large-rsa

Without the --enable-large-rsa flag, the key generation process will automatically downgrade the key to 4096.

To compile on a Mac, you'll need to download Xcode from the App Store first. The patch increases the upper limit of the key size to 15489 bits. Without increasing the secure memory limit, generating a key larger than about 7680-bits will fail because it won't be able to allocate enough memory to the process. Generating keys larger than around 7680-bits (192-bit symmetric equivalent) can also make it impossible to decrypt messages with standard secure memory limits set at compile time because the gpg binary won't be able to allocate enough secure memory to decrypt the message, even small ones.

gnupg_1.4.19_xlarge_key_gen.patch

--- g10/keygen.c    2015-02-26 12:24:21.000000000 -0500
+++ g10/keygen.c    2015-03-02 22:12:09.028419377 -0500
@@ -1041,8 +1041,9 @@
        nbits = 2048;
        log_info(_("keysize invalid; using %u bits\n"), nbits );
     }
-    else if (nbits > 4096) {
-        nbits = 4096;
+    else if (nbits > 15489) {
+        /* fallback to RFC3766 256-bit symmetric equivalency */
+        nbits = 15489;
         log_info(_("keysize invalid; using %u bits\n"), nbits );
     }

@@ -1251,7 +1252,8 @@
     PKT_public_key *pk;
     MPI skey[6];
     MPI *factors;
-    const unsigned maxsize = (opt.flags.large_rsa ? 8192 : 4096);
+    /* New large key limit RFC3766 256-bit symmetric equivalency */
+    const unsigned maxsize = (opt.flags.large_rsa ? 15489 : 4096);

     assert( is_RSA(algo) );

@@ -1578,7 +1580,7 @@
 static unsigned int
 ask_keysize (int algo, unsigned int primary_keysize)
 {
-  unsigned nbits, min, def=2048, max=4096;
+  unsigned nbits, min, def=2048, max=15489;
   int for_subkey = !!primary_keysize;
   int autocomp = 0;

gnupg_1.4.19_xlarge_secmem.patch

--- configure   2015-02-27 03:37:52.000000000 -0500
+++ configure   2015-03-02 22:28:31.488401783 -0500
@@ -5076,7 +5076,7 @@
 { $as_echo "$as_me:${as_lineno-$LINENO}: result: $large_secmem" >&5
 $as_echo "$large_secmem" >&6; }
 if test "$large_secmem" = yes ; then
-   SECMEM_BUFFER_SIZE=65536
+   SECMEM_BUFFER_SIZE=131072
 else
    SECMEM_BUFFER_SIZE=32768
 fi

Article ends. Retrieved on 2016-02-26 from an archived copy of the original.

Answer 3

Why does it not support anything larger? Perhaps at the time of development of GnuPG (and the continued development of RSA for that matter) and the key sizes, computing limits at the time,both for the client side use cases and the potential of government agencies being able to break a 4096 key, developers and cryptographers felt a 4096 key was large enough. Really, 4096 is a really large key and would take a very long time to break with current technology. If a government agency was after you and really wanted to get your messages they would (in the US) get a court order to put a rootkit on your machines to not even worry about breaking encryption.

Now, I haven't looked at the source code specifically, but if you change the key size to anything larger than 4096, you might have problems with other users using your key if their software doesn't support a larger key size. For example, I have a 4096 key, a friend of mine cannot send me messages from an Android device because he cannot find an application that supports anything larger than 3072! Keep that in mind.