Subject: Re: [TLS] Comparative cipher suite strengths

From: [email-masked]
Date: Wed, 22 Apr 2009 12:16:32 +0100

>>On Wed 22/04/09 11:35 AM , Simon Josefsson [email-masked] sent:
>>> The "key strength" would be limited by the weakest link in the suite
>>> though wouldn't it, which, in this case, is the RSA keys? Or are you
>>> saying that the additional security of the PRF, key derivation
>>> mechanisms, and the entropy in the random data overcomes this?
>>
>> No, I'm saying that talking about trying to match anything to 
>> AES-256 doesn't make sense. We don't know of any situation in
>> which even AES-128 can be attacked.
>
>What we can always do, though, is to compare the amount of work needed
>to break AES-256 with the amount of work needed to break RSA-y using
>state-of-the-art attacks. It's possible that this imply y=15360.
>
>However, I agree that this is looking at things the wrong way. The
>exercise should not have any practical consequences on what key sizes
>you use. One should focus on selecting appropriate security level for
>each algorithm. Today AES-128 and RSA-2048 will probably make
>implementation bugs the weakest link for the majority of users.

Thanks for all the responses. I think the following text is a better way of describing what I meant and why I was asking:

We have a customer that mandated that we utilize AES-256 for the symmetric encryption keys used on our TLS sessions, so we have complied, and this works fine. Looking at implementation details from the customer, I found that they are using static X.509v3 certificates (CA issued), where the public key size is only 1024 bits.

Therefore, in my mind, they are getting a false sense of security from using AES-256 as the underlying strength of the whole TLS session is determined by the weakest point - in this case the 1024 bit RSA keys, which NIST state to be equivalent to "80-bits" [when compared to a symmetric cipher I guess].

So, I would want to recommend to the customer that if they want a more secure TLS session, then they need to increase the RSA key sizes to "match" the symmetric key strength, as the overall security 'strength' of their TLS sessions comes down to their RSA key size [as it's lower comparably to AES-256].

Does this seem reasonable and make more sense than my original question?

Regards,

Carl

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Wed, 22 Apr 2009 07:38:10 -0400

On Wed, 22 Apr 2009 12:16:32 +0100
[email-masked] wrote:

> >>> The "key strength" would be limited by the weakest link in the
> >>> suite though wouldn't it, which, in this case, is the RSA keys?
> >>> Or are you saying that the additional security of the PRF, key
> >>> derivation mechanisms, and the entropy in the random data
> >>> overcomes this?
> >>
> >What we can always do, though, is to compare the amount of work
> >needed to break AES-256 with the amount of work needed to break
> >RSA-y using state-of-the-art attacks. It's possible that this imply
> >y=15360.
> >
> Thanks for all the responses. I think the following text is a better
> way of describing what I meant and why I was asking:
> 
> We have a customer that mandated that we utilize AES-256 for the
> symmetric encryption keys used on our TLS sessions, so we have
> complied, and this works fine. Looking at implementation details from
> the customer, I found that they are using static X.509v3 certificates
> (CA issued), where the public key size is only 1024 bits.
> 
> Therefore, in my mind, they are getting a false sense of security
> from using AES-256 as the underlying strength of the whole TLS
> session is determined by the weakest point - in this case the 1024
> bit RSA keys, which NIST state to be equivalent to "80-bits" [when
> compared to a symmetric cipher I guess].
> 
> So, I would want to recommend to the customer that if they want a
> more secure TLS session, then they need to increase the RSA key sizes
> to "match" the symmetric key strength, as the overall security
> 'strength' of their TLS sessions comes down to their RSA key size [as
> it's lower comparably to AES-256].
> 
Yes -- see RFC 3766.  NIST also has some recommendations, but I don't
happen to know the publication number offhand.

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

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 22 Apr 2009 05:42:15 -0700

At Wed, 22 Apr 2009 12:16:32 +0100,
[email-masked] wrote:
> complied, and this works fine. Looking at implementation details
> from the customer, I found that they are using static X.509v3
> certificates (CA issued), where the public key size is only 1024
> bits.
> 

Sure, but they're getting a false sense of security from AES-256
as well. Let's say for the sake of argument that you had
a system that used static, randomly generated 256-bit AES
keys. Do you really think that's 2^{128} times more secure
than one that uses 128-bit AES?

> more secure TLS session, then they need to increase the RSA key
> sizes to "match" the symmetric key strength, as the overall security
> 'strength' of their TLS sessions comes down to their RSA key size
> [as it's lower comparably to AES-256].
> 

It makes more sense to say you need a bigger RSA key, but IMO
the "match" thing is the wrong way to look at it. Rather, you
should decide on your minimum security level and choose algorithms
that support that. I don't think having them match is particularly
interesting once we're at the point where there is no plausible
non-analytic attack on the algorithm.

-Ekr

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 22 Apr 2009 11:42:26 -0500

> (CA issued), where the public key size is only 1024 bits.

As you surmise the weak link in the chain then is the RSA key size.
There's always going to be a weak link, but there's no sense in making
the other links stronger so far out of proportion to the weakest link.

Either the customer should revise their requirement that AES-256 be used
or they should deploy larger RSA keys.  But even so, going whole hog to
15kbit key lengths is not really practical.  Therefore I'd recommend
raising the RSA key size to 2048.

> So, I would want to recommend to the customer that if they want a more
> secure TLS session, then they need to increase the RSA key sizes to
> "match" the symmetric key strength, as the overall security 'strength'
> of their TLS sessions comes down to their RSA key size [as it's lower
> comparably to AES-256].
> 

Yes, but by my experience your customer's security policy people are not
likely to agree or will be averse to any change.  Here's how this sort
of thing goes:

SECURITY: the policy is <fill in the blank> (and "it's needed for SOX
compliance")
INTERNAL AUDIT: you're not doing what the policy requires
YOU: the policy is stupid^H^H^H^H^H^Hbroken, here's why
SECURITY: <crickets>

If you get past that you then run into other walls.  E.g., say you
convince the policy ppl that they should raise the RSA key size, but
then the business people complain that performance sucks, or that
deploying new certs will cost too much, so they ask their regulators for
a waiver -- and then you're back at square one (the policy has changed
but reality hasn't).

See also Dilbert.

Nico
--

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 23 Apr 2009 19:06:10 +1200

[email-masked] writes:

>Therefore, in my mind, they are getting a false sense of security from using
>AES-256 as the underlying strength of the whole TLS session is determined by
>the weakest point - in this case the 1024 bit RSA keys, which NIST state to
>be equivalent to "80-bits" [when compared to a symmetric cipher I guess].

They're not getting any sense of security at all.  They initially wanted a
cipher with 128-bit encryption, because everyone knows that you have to have
128 bits to be Good.  AES encryption has the required 128 thingies, so they
went with that.

Then someone pointed out that there's a version of AES with 256 thingies
instead of 128, and if 128 is Good then 256 must be even Gooder.  So the
requirement was changed to use AES with 256 thingies.

If there was an AES with 397 thingies they'd go with that instead, because
it's obvious that that one's ever Gooderer than the one with 256 thingies.

>So, I would want to recommend to the customer that if they want a more secure
>TLS session,

They don't want a more secure TLS session, they want bigger numbers after
their algorithm name.  So the optimal approach here would be to write a draft
for a new TLS cipher suite using the McEliece cryptosystem, because then you
can use numbers bigger than anyone else.

Peter.

---

From: "Blumenthal, Uri" <[email-masked]>
Date: Thu, 23 Apr 2009 07:57:58 -0400

How about this: US Government (yes, the one you seem to like rather less than the other governments) has declared that AES-128 can be used to protect information up to SECRET level, and for TOP SECRET one must use AES-256. Apparently they weren't aware of Eric's views regarding the unnecessariness of 256 bits when you have a perfectly good 128-bit key-space, and can't truly-really guarantee the algorithm strength anyway.

They did not mandate (nor even define) AES-397 or 398 as of yet, obviously because crypto scientists who work for them are not as smart or sarcastic as we are here.

So the optimal approach here would be to find out the real need of the customer - for what purpose he's trying to go to a higher-level encryption standard - and address it in practical matter (i.e. 15K RSA keys, while theoretically matching, are hardly usable in practice - so something bigger than 1K or 2K, but still wield-able; or follow Suite B and use ECC - in that case you can achieve the ballpark key size match between the algorithms).

Though where that customer is going to get a reasonably bug-free implementation is beyond me. I concede this point.

You can also point out to your customer that AES-128 is indeed considered "good enough" for most of the "normal" applications. But if he's already set his encryption policy, you probably won't get very far.
--
Regards,
Uri
<Disclaimer>

On 4/23/09  03:06 , "Peter Gutmann" <[email-masked]> wrote:

Peter.

_______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 23 Apr 2009 06:40:51 -0700

At Thu, 23 Apr 2009 07:57:58 -0400,
Blumenthal, Uri wrote:
> 
> [1  <multipart/alternative (7bit)>]
> [1.1  <text/plain; iso-8859-1 (quoted-printable)>]
> How about this: US Government (yes, the one you seem to like rather
> less than the other governments) has declared that AES-128 can be
> used to protect information up to SECRET level, and for TOP SECRET
> one must use AES-256. Apparently they weren't aware of Eric's views
> regarding the unnecessariness of 256 bits when you have a perfectly
> good 128-bit key-space, and can't truly-really guarantee the
> algorithm strength anyway.
> 
> They did not mandate (nor even define) AES-397 or 398 as of yet,
> obviously because crypto scientists who work for them are not as
> smart or sarcastic as we are here.

I'm finding this argument from authority really pretty unconvincing.

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?

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?

-Ekr

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Thu, 23 Apr 2009 15:05:15 -0400

On Thu, 23 Apr 2009 06:40:51 -0700

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

---

From: Dean Anderson <[email-masked]>
Date: Thu, 23 Apr 2009 16:24:35 -0400 (EDT)

On Thu, 23 Apr 2009, Steven M. Bellovin wrote:

> statement is *completely* unprecedented.

What's classified top secret is itself classified; and as I understand
it, so is the storage and handling of top secret materials, so I think
they shouldn't disclosed that AES256 is suitable for top secret because
that fact should be a secret that should only be known to people with
top secret clearance who handled top secret data.  Identifying the
cipher in use is part of the cryptanalysis problem, and they shouldn't
make that any easier; someone wasn't thinking.

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

Easy, they can tell the top secret world that they have a better cipher,
which doesn't mean AES-256 is insecure, but only that the new cipher is
stronger.

		--Dean

-- 
Av8 Internet   Prepared to pay a premium for better service?
www.av8.net         faster, more reliable, better service
617 344 9000

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 23 Apr 2009 13:40:19 -0700

At Thu, 23 Apr 2009 15:05:15 -0400,
> more key bits are definitely better, albeit by an imponderable amount.

So, this is true for symmetric ciphers but not asymmetric ciphers.

> be increased.  I think we can all agree on that.

I actually don't necessarily agree. If he's using AES-256 because
he has data that needs to be kept *really secure*, then yes, he
should use RSA > 1024. If he's using AES-256 because it's got
a cool sounding name, then maybe not so much.

-Ekr

---

From: Robert Relyea <[email-masked]>
Date: Fri, 24 Apr 2009 11:33:42 -0700

> it's obvious that that one's ever Gooderer than the one with 256 thingies.
So there is a method behind the AES-256 bit madness, and can see it in 
the cipher suites that NIST specifies.

As Carl has found (and most on this list is familiar with), NIST has 
standardized it's 'strength' specification in terms of symmetric key 
algorithm, which is why he matched AES-256 with a 15K bit RSA key.

NIST also defines strengths for various security levels. 128 bits is the 
minimum for Secret, 192 is the minimum for Top Secret. These numbers are 
both chosen to be more than known foreign governments and agencies are 
likely to be able to crack (presumably including a generous safety factor).

In addition to security levels, NIST also defines a set of cipher suites 
for these levels:

Secret: AES-128, ECC-256 prime, SHA-256
Top Secret: AES-256, ECC 384 prime, SHA-384

Note that AES-256 has a bigger key than required.  NIST specified 
AES-256 because it was already the same speed as AES-192. I don't know 
why they didn't specify SHA-512 over SHA-384 (which has the same 
characteristics).

The upshot is even NIST, using top secret doesn't need 256 bits. It's 
just the easiest way to meet their 192 bit requirement. Also not that 
AES-128 is considered sufficient for the US government to encode  Secret 
information. For practical and commercial use, it's still overkill. 80- 
100 bits is still sufficient for now (though moving toward 100 bits is 
probably prudent).

So you need to go back to your customer and find out what their real key 
strength need is. If your customer needs 192 bits, you probably want to 
move toward ECC ciphers (If you customer's AES-256 is coming from a NIST 
Suite-B requirement, then you'll need to move there anyway). Otherwise 
you are looking at a 7K bit RSA key to meet that requirement.

If you aren't talking to a Suite-B customer, then the info you are 
getting from this list is probably correct "AES-256 sounds strong, might 
as well go there" ignoring the fact that even at AES-128 your weak link 
is RSA (unless you use a 3K key).

bob