[Cryptography] NSA and cryptanalysis

[Perry E. Metzger]

On Mon, 2 Sep 2013 15:09:31 -0400 Jerry Leichter <leichter at lrw.com>
wrote:
> 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.

Only as a legacy "you can do this for a while but please switch."

> 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.

I'd say they're judging a balance between security and performance
while attempting not to leave particularly bad holes.

> 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 believe that is indeed a factor here, and is probably part of why
the asymmetric key lengths aren't a bit longer. It is also possible
they've been selected based on knowledge that AES keys are slightly
weaker than we expect, but not radically so.

As an aside, I'm reminded of the fact that there were certificational
weaknesses in Skipjack that meant it was only more or less as
potentially secure as the number of bits available in they key
length. When this was pointed out to someone in the know, the mumble
back I remember was "in other words, they did the engineering
correctly."

Anyway, as I've said, I'm paranoid, but I operate under the
assumption the counterparty is a reasonably rational actor that
understands the very limited duration of secrets.

Perry
-- 
Perry E. Metzger		perry at piermont.com