[Cryptography] NSA and cryptanalysis

Jerry Leichter leichter at lrw.com
Mon Sep 2 15:09:31 EDT 2013


On Sep 2, 2013, at 1:25 PM, Perry E. Metzger wrote:

> On Mon, 2 Sep 2013 00:06:21 -0400 Jerry Leichter <leichter at lrw.com>
> wrote:
>> - To let's look at what they want for TOP SECRET.  First off, RSA -
>> accepted for a transition period for SECRET, and then only with
>> 2048 bit moduli, which until the last year or so were almost
>> unknown in commercial settings - is completely out for TOP SECRET.
>> So clearly they're faith in RSA is gone.
> 
> That is a misunderstanding.
> 
> If you look at the way that the NSA specs these things, they try to
> keep all portions of a system of equal security so none is the weak
> point. A 2048 bit RSA key is factored vastly more easily than a 256
> bit AES key is brute forced (that's just public knowledge -- try doing
> the back of the envelope yourself) so that size key would be
> insufficient. However, a sufficiently large RSA key to be "correctly
> sized" for 256 bit AES is totally impractical for performance reasons,
> see:
> 
> http://www.nsa.gov/business/programs/elliptic_curve.shtml
a)  The very reference you give says that to be equivalent to 128 bits symmetric, you'd need a 3072 bit RSA key - but they require a 2048 bit key.  And the same reference says that to be equivalent to 256 bits symmetric, you need a 521 bit ECC key - and yet they recommend 384 bits.  So, no, even by that page, they are not recommending "equivalent" key sizes - and in fact the page says just that.

b)  Those comparisons long ago became essentially meaningless.  On the symmetric size, it's using brute force attack strengths.  But no one is going to brute force a 128-bit key with any known or suggested technology, and brute force attacks against 256-bit keys are way beyond what physics says is even remotely possible.  (I posted on this a long time back:  Any theory even vaguely consistent with what we know about quantum mechanics places a limit on the number of elementary bit flips in a finite volume of space-time.  If you want an answer in 100 years, your computer is at most a sphere in space-time 100 light-years cubed by 100 years in diameter - and that's a gross overestimate.  My quick calculation showed that the quantum limit for that sphere is not far above 128 bits.)

In any real terms, *if you're talking brute force*, 128 bits and 256 bits - and a million bits, if you want to go nuts about it - are indistinguishable.

For the other columns, they don't say where the difficulty estimate comes from. (You could get a meaningless estimate by requiring that the number of primes of the size quoted be equivalent to the number of symmetric keys, but I'm assuming they're being more intelligent about the estimate than that, as a brute force attack on primes makes no sense at all.  What makes more sense - and what they are presumably using - is the number of operations needed by the best known algorithm.  But now we're at point of comparing impossible attacks against 128- and 256-bit symmetric keys with impossible attacks against 3072- or 15360-bit RSA keys - a waste of time.  The relevant point is that attacks against RSA keys have been getting better faster than predicted, while the best publicly known attacks against AES have barely moved the needle from simple brute force.

Given *currently publicly known algorithms*, a 2048 bit RSA key is still secure.  (The same page shows that as equivalent to a 112-bit symmetric key, which is not only beyond any reasonable-term brute force attack, but longer than the keys used - according to some reports, anyway - on some Suite A algorithms.)

> So clearly the purpose of pushing ECC for this application is that
> they want the public key algorithm and its key size to have comparable
> security while both performing reasonably well.
>> (Same for DH and DSA.)
>> It looks as if they are betting that factoring and discrete logs
>> over the integers aren't as hard as people had thought.
And here we actually agree.  Note that I didn't say there was any evidence that NSA was ahead of the public state of the art - even given the public state of the art and the rate that it's advancing, using Z/p as a field is rapidly fading as a realistic alternative.  NSA, looking forward, would be making the recommendation to move to elliptic curves whether or not they could do better than the public at large.  So we can't read much into that aspect of it.  However, note (a) that if NSA does have a theoretical breakthrough, factoring is probably more likely than AES - we know they've hired many people in related fields over many years, and even in public the state of the art has been advancing; (b) most of the Internet is way behind recommendations that are now out there for everyone.  Google recently switched to 2048 bit keys; hardly any other sites have done so, and some older software even has trouble talking to Google as a result.

> Not at all, and the rationale is public and seen above.
> 
> I believe you're incorrectly claiming that we know much less than we
> actually do here.
Just what is it you claim we *know*?

On the asymmetric side, NSA recommends technology that Internet sites *could* have, but in practice mainly don't and for the most part won't for quite some time.  Can NSA break RSA or DH or DSA as most sites on the Internet are using it today?  Damned if I know - but either way is consistent with what we know.

On the symmetric side, I've already agreed that NSA's approval indicated that the considered AES secure 10 years ago, but if they've since learned otherwise but think they are and will remain the only ones with a viable attack for a while, they would be unlikely to admit it by changing their recommendation now.  This isn't evidence that AES is insecure or that NSA has an attack on it, simply a reason why the recommendation is not much in the way of evidence *for* its strength any more either.
                                                        -- Jerry



More information about the cryptography mailing list