Long Key Performance

[Anonymous]

Justin Troutman wrote:
>>You don't know that!  This is just a guess based on how far
>>factoring has gotten by now.  It is important not to exaggerate what
>>we know about the mathematics of cryptography.
>
>(nor assume that we should coax or encourage one to use massive key
>sizes above 4096)

It's okay to say "It is my guess that the performance costs of longer
key sizes is not worth the probable improvement in security."

>I'll agree with this to an extent. If you've kept up with
>cryptography and factorization progress, you might notice it hasn't
>advanced as much as many of us thought.

Maybe in the last six months.  Looking at the last three decades,
however, factoring has made tremendous strides.  Even the Great Rivest
got burned by factoring progress with the "squeamish ossifrage"
decryption.  This suggests caution and extreme overengineering is wise
when it comes to factoring.

The same thing was done with steel structures before the properties of
the material and techniques for using it were well understood.  The
Eiffel Tower, for example, is about six times as strong as it needs to
be.  A shame?  Sure, but it was the right design decision at the time.

Attacks on symmetric systems have not had the success comparable to
factoring.  DES has a few weak keys, and some rounds in various
ciphers seem to have suspicious properties, but there haven't been
truly alarming results.

So, it wouldn't be unreasonable for somebody to conclude that
factoring should be treated with great caution, but feel that the
symmetric side of things is in good shape.

Claiming this is unreasonable (or "extremely stupid") is to make
things up.

>However, I will say that with mathematics, it's in good taste to
>assume that a breakthrough could happen on a whim, and surely, with
>math, it is possible that a single advancement could be a tsunami
>against public key systems and factorization.

Right.  There is a chance that an O(1) factoring algorithm is
possible.  We can't do much about that if we are using public key
algorithms.

However, that doesn't mean we can't "buy some insurance" against the
more likely result of a merely improved factoring algorithm.

>The point here though, is that I believe and recommend, in my
>opinion, that 1024 bit keys will still suffice for a while longer,...

The goal is not to be secure for the next 18 months.  The goal is to
keep mail private for all time.

Also, if you think a publicly available fast factoring algorithm could
be available in 5 years, then you should be seriously concerned that
certain private parties may already have it.  (NSA, for example, is
believed to be the world's largest employer of mathematicians.)

>For the computing power, general user, time factor, speeds, et
>cetera, 2048 for a maximum key size is a conservative and good
>choice. If you want 4096 and don't mind any performance slow-downs,
>as well as have the computing power to spare, then so be it.

The performance costs are greatly exaggerated.  Those of us who don't
mind burning some cycles are not well served by tools which somewhat
arbitrarily prevent it.

>Besides the government or any other large corporation with the power
>to even attempt a factorization on a large number such as 1024-bits,
>I think for WinPT's sake, it is safe to say that 2048-bit key sizes
>for the maximum will be just fine,...

But nothing is gained by this limitation!  Gpg generates 4096 bit
keys, so why is WinPT arbitrarily limiting the keys its users can
generate?

>The whole idea being, with current factoring progress, keys <= 4096,
>average recommendation of 2048, would be the most conservative
>choices, in that if the sudden breakthrough would occur, you have
>saved computing power over time and still retained security by using
>these sizes, rather than 16kbit keys that will require massive
>amounts of computer power, as you've quadrupled the maximum key size,
>but will still fall to the factoring breakthrough.

Yes, this *could* happen.  However, there is also some chance (far
larger, based on past experience) that merely somewhat longer keys
will be factored by new attacks.  In this scenario, one would be more
comfortable with a 16 kbit key than a 4096 bit key.

>All in all, I don't think Bernstein's paper has really changed things
>and 2048-4096-bit keys are fine, even 1024, for a while longer, if
>you've kept up with things thus far.

I'm not reacting to Bernstein's paper.  Bernstein's paper validated
something I've been saying for a long time.

>Why go to the trouble? You can save computing time and still retain
>sufficient security at <=4096.

You think so.  But, other people can just as reasonably think
otherwise.  They should be allowed to act on their belief and
tolerance of a few seconds delay while encrypting.

>Going back to my first comments as to how this limit doesn't prohibit
>any security...if you even have the option to choose >4096-bit keys,
>considering the possible scenarios and your computing abilities,
>would it even be necessary?

The cost is not great.  So why not?

>Showing off GPG lies not in the key size, as most people (with a
>decent knowledge of public key crypto) won't ever attempt generating
>a key higher than the maximum even if given the option.

To which "decent knowledge" do you refer?  The truth is: we don't
know!

I challenge you to cite a credible paper which demonstrates that a
4096 bit number is not easy to factor.  Don't bother looking too hard
- it doesn't exist.