Re: [TLS] Comparative cipher suite strengths

["Steven M. Bellovin" <[e-mail]>]

On Thu, 23 Apr 2009 06:40:51 -0700
Eric Rescorla <[e-mail]> wrote:

> How is it that the same government which can't seem to efficiently
> conduct elections or clean up after Hurricane Katrina is suddenly
> infallible when it comes to crypto? Is it just because the message
> comes from Fort Meade or what?

Infallible?  No, of course not.  And no government has ever fielded a
system that they knew the enemy could break -- and of course many
governments have been wrong.  That may include the NSA -- Heath's
master's thesis concludes that the Soviets likely broke NSA's KW-7
encryptor circa 1970.  (She also concluded that the Navy's key-handling
practices were awful.)  Recently declassified documents say that NSA
started having great cryptanalytic success of its own against the
Soviets in the late 1970s.

But -- remember Biham, Biryukov, and Shamir's 2^78 impossible
differential attack on 31-round Skipjack?  2^78 isn't an impressive
result against an 80-bit cipher, and the attack could not be extended
to the full 32 rounds in any case.  But it was interesting that there
was this slight improvement over brute force, so I brought it up in
conversation with a friend who knows a fair amount about the subject.
His comment?  "A 2^78 attack against an 80-bit cipher?  That's not an
attack, that's good engineering."  Maybe NSA really does understand
this stuff that well...

One more point: NSA may or may not be able to speak ex cathedra on
strength; we'll never know.  They have said publicly that they trust
256-bit AES a lot, and a lot more than they trust 128-bit AES.  That
statement is *completely* unprecedented.  The really interesting
question is this: what will NSA ever do, if they ever figure out how to
crack AES-256?  Officially decertify it for TS use, thereby telling the
world they think it's no longer that strong?  Let government agencies
continue to use it, when they know it's breakable?  That would be a
great discussion to listen to....
> 
> In any case, I'm not saying that AES-256 isn't more secure than
> AES-128. It probably is, if only because it has more rounds in
> 256-bit mode. What I'm saying is that there is no practical sense in
> which we can conclude it's 2^{128} times stronger. Either the best
> attack is brute force, in which case there's simply no plausible
> attack on AES-128, or it's not in which case who knows what the
> relative strengths of the algorithms are?
>
Key length certainly isn't everything.  A monoalphabetic substitution
on all 256 byte values has a key length of 256!, or about 1684 bits,
but it is of course trivially crackable. 

That said, there's always Whit Diffie's attitude: having extra key bits
is cheap; why not use them if you can?  Also, remember that many modern
cryptanalytic techniques produce many key bits but not all, requiring a
brute force search for the remainder.  So -- for a situation like that,
more key bits are definitely better, albeit by an imponderable amount.

Final comment: the original poster was not asking if they should use
AES-256; he was saying that they do use it, and should the RSA key size
be increased.  I think we can all agree on that.

		--Steve Bellovin, http://www.cs.columbia.edu/~smb