does gpg cope with very large key sizes

[Philippe Cerfon]

Hi list and GnuPG developers!


Let me introduce myself,... I'm Philippe Cerfon and I'm currently taking some crypto-lectures... including all that fancy algorithms and so on ;-)
Out of curiosity I was starting some test series on how key creation time and encryption/signing time relates to key sizes.
I soon found out that gpg puts a limit on keys at 4096 bits which is surely reasonable for real world but somewhat disturbing my test.

I was looking into the gnupg mailing list archives and found out that gpg is said to be able to work with larger keys. I've also seen that this topic is well somewhat critical, so to say it in advance,.. this only for trying and playing :)

So I grepped the sources (for both version 1.x and 2.x) and found that the limit is enfored here:
g10/keygen.c:  unsigned nbits, min, def=2048, max=4096;

With version 2.x probably in some other places, too:
g10/app-openpgp.c:      max_length = 4096;
scd/app-openpgp.c:      max_length = 4096;
scd/command.c:#define MAXLEN_KEYDATA 4096
tools/gpgkey2ssh.c:      max_length = 4096;
tools/gpgconf-comp.c:#define BUF_LEN 4096
but I think they're unrelated to key creation/use.

So all I must to is e.g. set max = 65536 or even something higher ;-)
Right so far?

I've seen many other places where some buffers or other this are set to 4096 (see attachments):
So my questions now are:
- Is it done with changing the max or would I have to change some other places too in order to make everything work correctly (e.g. these max_length's or so)?
- Are the generated keys (or their signatures) actually sane? I mean I could imagine that at some point randomness gets just worse, or some buffers cap the key entropy or whatever.
- Or is in everything ok,.. and there's just this max=something in g10/keygen.c where you save users from shooting into their feets by creating to large keys but nothing else?

You know, my time measurements might be simply bogus as gpg stops producing valuable key bits after some limit,.. or the measurements might be useless as these keys were no longer secure (even less than normal keys) anyway...

Thanks and au revoir,
Philippe.

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@...
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[David Shaw]

On Sep 9, 2009, at 6:43 PM, Philippe Cerfon wrote:

> Hi list and GnuPG developers!
>
>
> Let me introduce myself,... I'm Philippe Cerfon and I'm currently  
> taking some crypto-lectures... including all that fancy algorithms  
> and so on ;-)
> Out of curiosity I was starting some test series on how key creation  
> time and encryption/signing time relates to key sizes.
> I soon found out that gpg puts a limit on keys at 4096 bits which is  
> surely reasonable for real world but somewhat disturbing my test.
>
> I was looking into the gnupg mailing list archives and found out  
> that gpg is said to be able to work with larger keys. I've also seen  
> that this topic is well somewhat critical, so to say it in  
> advance,.. this only for trying and playing :)
>
> So I grepped the sources (for both version 1.x and 2.x) and found  
> that the limit is enfored here:
> g10/keygen.c:  unsigned nbits, min, def=2048, max=4096;

Yes.

> So all I must to is e.g. set max = 65536 or even something higher ;-)
> Right so far?

Right, but you may be surprised how long it takes to generate a really  
massive key.  The key generation code is single-threaded, and  
generally not optimized for really big keys.

> So my questions now are:
> - Is it done with changing the max or would I have to change some  
> other places too in order to make everything work correctly (e.g.  
> these max_length's or so)?

You should be okay with changing the ones in keygen.c.

> - Or is in everything ok,.. and there's just this max=something in  
> g10/keygen.c where you save users from shooting into their feets by  
> creating to large keys but nothing else?

Pretty much true if your goal is to just do performance testing with  
different sizes.  I certainly wouldn't actually use such a key in the  
real world, though.

David


_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@...
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[Philippe Cerfon]

Hi David.


On Thu, Sep 10, 2009 at 5:09 AM, David Shaw <dshaw@...> wrote:
>> So I grepped the sources (for both version 1.x and 2.x) and found that the limit is enfored here:
>> g10/keygen.c:  unsigned nbits, min, def=2048, max=4096;
> Yes.

Wow,.. I alawys knew I'd be a gpg-code guru *laughs* ;-)


>> So all I must to is e.g. set max = 65536 or even something higher ;-)
>> Right so far?
> Right, but you may be surprised how long it takes to generate a really massive key.  The key generation code is single-threaded, and generally not optimized for really big keys.

That's just what I want to find out,... ok actually,.. I think the
times required to sign/encrypt with such a key are more interesting,..
but creation time is somewhat interesting, too.


> You should be okay with changing the ones in keygen.c.

>> - Or is in everything ok,.. and there's just this max=something in g10/keygen.c where you save users from shooting into their feets by creating to large keys but nothing else?
> Pretty much true if your goal is to just do performance testing with different sizes.  I certainly wouldn't actually use such a key in the real world, though.

Pretty much? What do you mean by that? The time/performance issues?
Out of curiosity: As far as I know the suggested key sizes will always
rather raise, right (expect one moves perhaps away from RSA, but are
there any alternatives than DSA?)? So maybe in 20 or 30 years 32k bit
keys will be necessary,... would be bad if those keys weren't usable
in the real world :-/


Cheers,
Philippe.

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@...
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[David Shaw]

On Sep 10, 2009, at 7:40 AM, Philippe Cerfon wrote:

>>> - Or is in everything ok,.. and there's just this max=something in  
>>> g10/keygen.c where you save users from shooting into their feets  
>>> by creating to large keys but nothing else?
>> Pretty much true if your goal is to just do performance testing  
>> with different sizes.  I certainly wouldn't actually use such a key  
>> in the real world, though.
>
> Pretty much? What do you mean by that? The time/performance issues?

Yes, but also that it's a silly keysize in the real world.  For most  
people (doing regular-people things like using computers connected to  
the internet, presumably in a house or apartment with a front door),  
the key would be so vastly stronger than the rest of the environment  
that an attacker wouldn't bother to attack it.  Rather they'd go  
against that front door, or other attacks against you and/or your  
environment.

It's a bit like this: http://failblog.org/2009/05/22/security-fail-5/

> Out of curiosity: As far as I know the suggested key sizes will always
> rather raise, right (expect one moves perhaps away from RSA, but are
> there any alternatives than DSA?)? So maybe in 20 or 30 years 32k bit
> keys will be necessary,... would be bad if those keys weren't usable
> in the real world :-/

I don't forsee we'll ever end up with keys that large.  They're just  
too big to conveniently use.  Rather, we'll switch over to algorithms  
like Elliptic Curve that are stronger per-bit than RSA or DSA.

David


_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@...
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[Sebastian Wiesinger-9]

* Philippe Cerfon <philcerf@...> [2009-09-10 01:43]:
> Hi list and GnuPG developers!
>
>
> Let me introduce myself,... I'm Philippe Cerfon and I'm currently taking
> some crypto-lectures... including all that fancy algorithms and so on ;-)
> Out of curiosity I was starting some test series on how key creation time
> and encryption/signing time relates to key sizes.
> I soon found out that gpg puts a limit on keys at 4096 bits which is surely
> reasonable for real world but somewhat disturbing my test.

Hi,

regarding this, the Simtec Entropy Key http://www.entropykey.co.uk/ is
available for sale online since a few days ago. This is an USB
hardware entropy generator. Perhaps this would be something to
consider in your tests regarding quality and speed of entropy
generation.

Regards,

Sebastian

--
New GPG Key: 0x93A0B9CE (F4F6 B1A3 866B 26E9 450A  9D82 58A2 D94A 93A0 B9CE)
Old GPG Key-ID: 0x76B79F20 (0x1B6034F476B79F20)
'Are you Death?' ... IT'S THE SCYTHE, ISN'T IT? PEOPLE ALWAYS NOTICE THE SCYTHE.
            -- Terry Pratchett, The Fifth Elephant


_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@...
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[Philippe Cerfon]

Hi David.



On Thu, Sep 10, 2009 at 6:07 PM, David Shaw <dshaw@...> wrote:
>> Pretty much? What do you mean by that? The time/performance issues?
> Yes, but also that it's a silly keysize in the real world.  For most people
> (doing regular-people things like using computers connected to the internet,
> presumably in a house or apartment with a front door), the key would be so
> vastly stronger than the rest of the environment that an attacker wouldn't
> bother to attack it.  Rather they'd go against that front door, or other
> attacks against you and/or your environment.

Of course,... I was aware on this :)
If CIA|NSA|etc. want my secrets (not that my life would be so
interesting ^^), they probably woulnd't try to hack my keys at all,..
but simply beat me until I happly give them everything plus
confessions to anything they want ;)

When I asked you before,.. I just ment if these oversized keys would
still be ok and "secure", in a hypothetical scenario, where everything
else is also perfectly secure (e.g. having a steel door with Superman
guarding it ;-) )


> I don't forsee we'll ever end up with keys that large.  They're just too big
> to conveniently use.  Rather, we'll switch over to algorithms like Elliptic
> Curve

*looked it up*
Ah,.. interesting...
So will this "replace" RSA/DSA? Perhaps also with an OpenPGP without
the strict bindings to SHA1 you mentioned before?
Is it already working (for gpg)? Or when could one expect this being
usable for production?


Cheers,
Philippe.

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@...
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[David Shaw]

On Sep 10, 2009, at 5:29 PM, Philippe Cerfon wrote:

> When I asked you before,.. I just ment if these oversized keys would
> still be ok and "secure", in a hypothetical scenario, where everything
> else is also perfectly secure (e.g. having a steel door with Superman
> guarding it ;-) )

So far as I know, they should be fine and still secure - just very  
large.  Of course, we don't test beyond 4096 bits, but I don't know of  
any particular gotchas in there for keys beyond 4096.

>> I don't forsee we'll ever end up with keys that large.  They're  
>> just too big
>> to conveniently use.  Rather, we'll switch over to algorithms like  
>> Elliptic
>> Curve
>
> *looked it up*
> Ah,.. interesting...
> So will this "replace" RSA/DSA? Perhaps also with an OpenPGP without
> the strict bindings to SHA1 you mentioned before?
> Is it already working (for gpg)? Or when could one expect this being
> usable for production?

Not very soon.  The first step is to get ECC as an update to the  
OpenPGP spec.  The next step (really concurrent with the first step)  
would be get more than one implementation (GPG, PGP, OpenPGP:SDK, etc)  
to support it and prove interoperability.  Finally there is the rather  
slow ramp-up as people slowly adopt the new ability.  This is the part  
that takes the longest as people don't upgrade very quickly or often,  
there is reluctance to make new keys, etc.

There is currently a proposal for OpenPGP ECC.  See http://brainhub.googlepages.com/pgp

Note that ECC and a no-SHA1 OpenPGP aren't necessarily related.  As  
specified in the draft, ECC ends up being two new algorithm types like  
RSA or DSA.  You could have a (for example) a ECDSA subkey on your RSA  
primary key and so on.  A no-SHA1 OpenPGP is a different sort of  
problem, and pretty much implies a new key packet type, as I see it.

Even in an ideal world, widespread ECC use is years away.  (Which  
doesn't mean we shouldn't start - if we want it used years from now,  
we have to start on it).

If you're interested in ECC, I suggest you check out the ietf-openpgp  
list.  This is where changes to the OpenPGP spec are discussed.  See http://www.imc.org/ietf-openpgp/

David


_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@...
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[Philippe Cerfon]

Thanks for your infos and the pointer to that mailing list :-)


Greetings,
Philippe

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@...
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[Philippe Cerfon]

Hi.

For those wo are interested,... ;)

I've aborted trying to create a 65536 bit RSA key. Took just too long
and I don't know enough on key generation to make an estimation ;)


Anyway,.. when trying to create 32768 bit RSA key I've got the following error:
We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.
.......................+++++
.........................................................................+++++
gpg: out of secure memory while allocating 4096 bytes
gpg: (this may be caused by too many secret keys used simultaneously
or due to excessive large key sizes)

Is this a bug? Or is there anything I can do to get more "secure memory"?


Thanks,
Philippe

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@...
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[David Shaw]

On Sep 13, 2009, at 1:07 PM, Philippe Cerfon wrote:

> Hi.
>
> For those wo are interested,... ;)
>
> I've aborted trying to create a 65536 bit RSA key. Took just too long
> and I don't know enough on key generation to make an estimation ;)
>
>
> Anyway,.. when trying to create 32768 bit RSA key I've got the  
> following error:
> We need to generate a lot of random bytes. It is a good idea to  
> perform
> some other action (type on the keyboard, move the mouse, utilize the
> disks) during the prime generation; this gives the random number
> generator a better chance to gain enough entropy.
> .......................+++++
> .........................................................................+
> ++++
> gpg: out of secure memory while allocating 4096 bytes
> gpg: (this may be caused by too many secret keys used simultaneously
> or due to excessive large key sizes)
>
> Is this a bug? Or is there anything I can do to get more "secure  
> memory"?

No, it's not a bug.  You're hacking the code to get it to do something  
the developers explicitly don't permit doing.  You can't file a bug  
against a car for not driving straight after you removed a wheel.  The  
rules of this game are: if you break it, you get to keep the pieces.

You can get more secure memory by changing the call to secmem_init in  
gpg.c.

David


_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@...
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[Philippe Cerfon]

On Sun, Sep 13, 2009 at 8:13 PM, David Shaw <dshaw@...> wrote:
> You can get more secure memory by changing the call to secmem_init in gpg.c.

btw: For my tests, ... would it also work to just set --no-require-secmem ?

Cheers,
Philippe.

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@...
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

[David Shaw]

On Sep 13, 2009, at 4:22 PM, Philippe Cerfon wrote:

> On Sun, Sep 13, 2009 at 8:13 PM, David Shaw <dshaw@...>  
> wrote:
>> You can get more secure memory by changing the call to secmem_init  
>> in gpg.c.
>
> btw: For my tests, ... would it also work to just set --no-require-
> secmem ?

No, that has nothing to do with the amount of secure memory.

David


_______________________________________________
Gnupg-devel mailing list
Gnupg-devel@...
http://lists.gnupg.org/mailman/listinfo/gnupg-devel