Draft of nine new FAQ questions

[Robert J. Hansen]

On 5/25/12 6:41 AM, Nicholas Cole wrote:
> ***In terms of current scientific understandings, the symmetric
> ciphers used in GnuPG are utterly***
> The symmetric ciphers used in GnuPG are utterly immune to
> brute forcing.  The Second Law of Thermodynamics places strict

I'm comfortable with things as they are.  If and when Heisenberg and/or
the Second Law stop being accurate descriptions of the universe, I'll
have much bigger things to worry about than the FAQ.  :)

> There's a slight confusion in these answers that I think it would be
> really helpful to address in an FAQ.

Yes, there is.  Unfortunately, the answer is kind of messy.

NIST believes a 112-bit *keyspace* ("bits of security") will be
sufficient until at least 2030, but NIST never gives their reasons why.
 I suspect that's because the committee wasn't able to reach an
agreement on why: one person believed X was the biggest threat and would
come to pass no sooner than 2030, another person believed Y and it would
come to pass no sooner than 2030, another person believed Z.  They all
agreed "safe until 2030," so that's what got put down as a
recommendation -- but NIST reached no consensus on what particular
threat they were worried about.

NIST also believes a 2048-bit key provides a 112-bit keyspace.  There's
a lot of conjecture going on there.  Sure, there may be approximately
2**112 primes that would have to be checked in order to do a brute-force
factoring, but there's some evidence that RSA can be broken *without
needing to factor anything* (!!).  We have no idea how to do it and no
idea how much easier this would be than brute-force factoring.  (In
fact, for all we know it might be harder, although that's considered
unlikely.)  Dan Boneh showed breaking RSA without factoring anything was
probably possible, but it was a nonconstructive demonstration -- we have
no idea where to begin.

So on the one hand, it's possible that brute-force factoring will have
some sort of breakthrough by 2030 (Shor's algorithm, maybe?) that will
end the useful lifespan of 2048-bit keys.  And on the other hand, it's
possible that Boneh's work will have some sort of breakthrough by 2030
that will blow RSA out of the water.  We don't know.  It's kind of
frustrating.  It's this sort of complexity that causes our crystal balls
to be all murky.

Remember, too, that we're talking about predictions *18 years out*.
That's a long, long ways.  I'll be getting senior citizen's discounts at
restaurants by then.  I imagine a lot of the NISTers just didn't feel
comfortable making pronouncements past 2030.

> To put the question in the form that sometimes comes up on this list -
> what if one wants security until 2040?  Would a 3072 key make sense in
> that case or not?

Then you're probably best-served going hog-wild on a 4096-bit key, with
the strong caveat that nobody really has any idea whether even a 4k key
will survive until 2040.