Subject: Re: [TLS] Comparative cipher suite strengths

From: "Blumenthal, Uri" <[email-masked]>
Date: Wed, 22 Apr 2009 09:24:26 -0400

Eric,

I disagree. You're mixing together two orthogonal issues: security of algorithms and security of implementation.

NIST recommends that algorithms in a cipher suite are of comparable strength. That includes relative key length.

The fact that despite of using secure algorithms your implementation still can have exploitable bugs (that nullify the benefits of cryptography) is 100% irrelevant to the issue of selecting algorithms and their parameters.

Why didn't NIST say "your implementations will suck anyway, therefore there's no need to define AES with more than 128-bit keys - you'll be attacked via code not AES weaknesses"?

It might even be possible that Carl's customer is also aware of implementation issues and is taking care of them, however unlikely it may sound.

----- Original Message -----
From: [email-masked] <[email-masked]>
To: [email-masked] <[email-masked]>
Cc: TLS <[email-masked]>
Sent: Wed Apr 22 08:42:15 2009
Subject: Re: [TLS] Comparative cipher suite strengths

At Wed, 22 Apr 2009 12:16:32 +0100,
[email-masked] wrote:
> 
> 
> >>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].

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?

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

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
_______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 22 Apr 2009 06:46:27 -0700

At Wed, 22 Apr 2009 09:24:26 -0400,
Blumenthal, Uri wrote:
> 
> Eric,
> 
> I disagree. You're mixing together two orthogonal issues: security
> of algorithms and security of implementation.
> 
> NIST recommends that algorithms in a cipher suite are of comparable
> strength. That includes relative key length.

I appreciate that NIST recommends this. I think it's silly.
It doesn't get any less silly because it's typeset in cool
FIPS formatting.

> The fact that despite of using secure algorithms your implementation
> still can have exploitable bugs (that nullify the benefits of
> cryptography) is 100% irrelevant to the issue of selecting
> algorithms and their parameters.

I don't agree that that's true, but in any case it's not what I'm saying.

The amount of computational power required to break a 128-bit AES
key with current is so outlandishly large that there is plausible
scenario that such a key will be broken by brute force. The 
only plausible situations in which 128-bit AES keys are breakable,
then, are non-brute-force attacks such as attacks on the implementation
or an analytic attack. In neither case does 2^{128} represent
an accurate estimate of the security of the algorithm, nor is
there any reason to believe that AES-256 is 2^{128} times more
secure under such attacks. Thus, the inference that one ought to
use an RSA key that is 2^{128} times stronger with AES-256 than
AES-128 also does not follow.

-Ekr

---

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

On Wed, 22 Apr 2009 06:46:27 -0700
Eric Rescorla <[email-masked]> wrote:

> then, are non-brute-force attacks such as attacks on the
> implementation or an analytic attack. In neither case does 2^{128}
> represent an accurate estimate of the security of the algorithm, nor
> is there any reason to believe that AES-256 is 2^{128} times more
Two points...  First, it may be a question of future-proofing: will
someone find a new cryptanalytic attack on AES-128 in the next, say, 20
years?  (You have, I assume, arranged for remote deletion of all of the
surreptitious copies of your DES-protected conversations from 20 years
ago, right?)

Second, 1024-bit RSA is a much weaker link than 128-bit AES *today* --
they should switch to 2048- or 3072-bit RSA even if they stick with
128-bit AES.

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

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 22 Apr 2009 07:14:11 -0700

At Wed, 22 Apr 2009 10:01:23 -0400,
> surreptitious copies of your DES-protected conversations from 20 years

I agree with this claim. But I don't think it supports the
"matching" argument particularly well. I.e., we don't really have
any idea of how relatively strong AES-256 and ECC-512 (for instance)
will be under some new analytic method.

> they should switch to 2048- or 3072-bit RSA even if they stick with

This I only sort of agree with: symmetric algorithms come in
relatively rough granularity. If I was happy with 80 bits of
security (which is apparently what NIST claims for RSA-1024,
though I've also heard 72), then there's no good reason
to make my PK much slower just b/c NIST has declined to
give me an 80-bit algorithm.

-Ekr

---

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

On Wed, 22 Apr 2009 07:14:11 -0700
Eric Rescorla <[email-masked]> wrote:

> > Second, 1024-bit RSA is a much weaker link than 128-bit AES *today*
> > -- they should switch to 2048- or 3072-bit RSA even if they stick
> > with 128-bit AES.
> 
Assuming, of course, that people realized how weak 1024-bit RSA is,
you're right.  Did people realize that?  *Do* people realize it?  When
I look at the number of CA certs in my browser that use 1024-bit keys,
I worry...

---

From: <[email-masked]>
Date: Wed, 22 Apr 2009 16:44:06 +0200

Just FYI, in IEEE 802 there was a lengthy discussion to try and reach a shorthand way of expressing the relative strength of each suite as expressed in the NIST lists. The shorthand was to be used in a network information IE, and in mobile device policy when evaluating which networks to attach to. No conclusion on how to do it was reached, so that approach was abandoned.

Kind Regards,
Michael

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of ext Steven M. Bellovin
Sent: 22 April, 2009 07:23
To: Eric Rescorla
Cc: [email-masked]'
Subject: Re: [TLS] Comparative cipher suite strengths

On Wed, 22 Apr 2009 07:14:11 -0700
Eric Rescorla <[email-masked]> wrote:

> relatively rough granularity. If I was happy with 80 bits of security 
> (which is apparently what NIST claims for RSA-1024, though I've also 
> heard 72), then there's no good reason to make my PK much slower just 
> b/c NIST has declined to give me an 80-bit algorithm.
> 
Assuming, of course, that people realized how weak 1024-bit RSA is, you're right.  Did people realize that?  *Do* people realize it?  When I look at the number of CA certs in my browser that use 1024-bit keys, I worry...

		--Steve Bellovin, http://www.cs.columbia.edu/~smb _______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls

---

From: "Blumenthal, Uri" <[email-masked]>
Date: Wed, 22 Apr 2009 10:58:07 -0400

> It doesn't get any less silly because it's typeset in cool

And  I think it makes a perfect sense. It lowers the likelihood of people building tents with steel doors.

We both are entitled to our opinions - but the way cryptographers in all the places (academy, industry, etc) go suggests more weight on my side of the argument. (I know you're going to say that in my analogy the implementation quality is that tent - so see below.)

>From cryptography point of view it is true to a very large extent. The fact that there are attacks directed against implementations (DFA, etc) does not reduce the importance of "pure math" algorithm study. But see below.

> key with current is so outlandishly large that there is no plausible
> or an analytic attack.

Yes, so? Until we learned about differential cryptanalysis we assumed that DES was 2^56 strong. Once we learned of that attack, we dropped our estimated strength to 2^47, then to 2^42... And then 2^56 became breakable by brute force. So...? For now AES-128 is 2^128 strong - feel free to prove otherwise.

> In neither case does 2^{128} represent

The above is cryptographically incorrect. True, we can't know for sure that AES-128 has 2^128 strength against analytical attack, though at this time it appears so (as implementation attacks are out of scope for this discussion). We don't know for sure that AES-256 is 2^128 stronger than AES-128 either. It is simply impossible to prove (given the current state of the science), as you well know. (Needless to say you can't prove at this time that it is less strong either.)

But until there are tangible reasons to assume otherwise - we go by the existing evidence that suggests 2^128 strength for AES-128, and 2^256 for AES-256 correspondingly. So the inference follows directly that we use equivalent (ballpark!) key strength for RSA and ECC.

The practical question becomes - what peer algorithms to choose for the suite based on AES-256. I say use NIST guidelines - and at the very least you won't get sued for negligence (in that area :-).

Also, keep in mind that there is no exact matching of the key strength - only the ballpark.
--
Regards,
Uri
<Disclaimer>

---

From: Daniel Brown <[email-masked]>
Date: Wed, 22 Apr 2009 11:51:10 -0400

Eric,

Are you saying that 2^128 computations will never be feasible, and therefore, that Moore's law will stop?

Best regards,

	Dan

---

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

At Wed, 22 Apr 2009 11:51:10 -0400,
> therefore, that Moore's law will stop?

I wasn't aware that that was a particularly controversial observation.

Current computers, with feature sizes of about 50 nm (50 * 10^{-9} m)
are just about fast enough to brute force a 64-bit key. So, in order
for Moore's law (which, remember, is about feature size) to get us to
128-bit keys, the feature sizes would need to shrink to 50 * 10^{-9} *
2^{-64} ~= 50 * 10^{-28}. Given that hydrogen atoms are on the order
of 10^{-10} m large, I don't think it's particularly safe to do a
straight line extrapolation of Moore's law through 18 more orders of
magnitude. Obviously, it's possible we'll learn how to construct
computers with some entirely different technology (quarks!), but
it's not like it's just a matter of giving Intel more money.

-Ekr

---

From: Daniel Brown <[email-masked]>
Date: Thu, 23 Apr 2009 13:13:13 -0400

NIST SP 800-57, Table 2, provides a list of comparable strengths, and Table 4, provides a list of algorithm security lifetimes, which I liberally interpret as saying 2^80 computations may be feasible for a concerted adversary, in 2010 and perhaps 2^112 operations may be feasible by 2030.  

Note that Table 4 does not differentiate the lifetimes 128, 192, or 256 security, in loose agreement with, and perhaps for similar reasons to, Eric's argument that searching 2^128 keys will never be feasible.

Furthermore, adapting Eric's calculations below, to brute force 112-bit keys, assuming 80-bit keys are brute forcible today (let's just say with massive distributed computing for the sake of example), feature sizes would need to shrink to 50 * 10^{-9} * 2^{-32} =~ 1.16 * 10^{-17}, still smaller than a Hydrogen atom, but perhaps NIST was accounting for the possibility of some future technical developments leading to continued or even accelerated increase in processing power, or perhaps NIST was also accounting for some degradation in the security of the TDEA aglorithm below that of a generic block cipher, or perhaps NIST is just encouraging migration to AES. 

That all said, personally, I'm still much more reluctant to predict a decrease in the growth of processing power that has been going fairly steady (?) for some time.  Therefore, data needing long term protection, say medical information, is worth encrypting at a potentially higher security level, assuming one has the processing power and a well-established encryption algorithm to do so.  If Moore's law (liberally applied to processing power, not just feature size) stops soon enough, then using the larger keys was at worst a waste of processing power, or at best, insurance.

Best regards,

	Dan

-----Original Message-----
From: Eric Rescorla [mailto:[email-masked]] 
Sent: Thursday, April 23, 2009 9:57 AM
To: Daniel Brown
Cc: Eric Rescorla; Blumenthal, Uri; [email-masked]'
Subject: Re: [TLS] Comparative cipher suite strengths

-Ekr

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 23 Apr 2009 11:00:20 -0700

At 1:13 PM -0400 4/23/09, Daniel Brown wrote:
>Table 4, provides a list of algorithm security lifetimes,

That's your interpretation. NIST labels the table "Recommended algorithms and minimum key sizes", and precedes it with "Table 4 provides recommendations that may be used to select an appropriate suite of algorithms and key sizes for Federal Government unclassified applications." If you want to ignore that and call it "a list of algorithm security lifetimes", that's fine, but maybe don't attribute that interpretation to NIST without further backup.
>
>which I liberally interpret as saying 2^80 computations may be feasible for a concerted adversary, in 2010 and perhaps 2^112 operations may be feasible by 2030.

See above.

>... but perhaps NIST was ... or perhaps NIST was ... or perhaps NIST is ...

Another possibility is to take NIST's words as what they intended to say.

--Paul Hoffman, Director
--VPN Consortium

---

From: Daniel Brown <[email-masked]>
Date: Thu, 23 Apr 2009 14:39:12 -0400

Paul,

Yes, I certainly ignored many parts of SP 800-57.  I'm sorry about that.

But I don't want to also ignore other parts of SP 800-57 (Revision, March 2007) such as Table 4 column heading: "Algorithm security lifetime", which also appears in the Glossary defined as "The estimated time period during which data protected by a specific algorithm remains secure".  Further on, SP 800-57 makes requirements based on Table 4, "Algorithms or key sizes not indicated for a given range of years shall not be used to protect information during that time period."  (My personal interpretation of this is that 2048-bit FFC is not to be used for data needing protection beyond 2030 under SP 800-56 compliance, but I could be completely wrong, and I have not found a more direct quote to support this.)

SP 800-57 does not provide rationale for this requirement, does it?  Is it unreasonable to speculate NIST's rationale, if only as a less dry way to discuss purely objective arguments, such as Eric's, about recommendations such as Table 4, and their wider applicability to TLS users and people not bound by SP 800-57 but who might appreciate following its guidance, especially given the question about incomparable algorithm security levels over which this thread began?

Best regards,

	Dan

-----Original Message-----
From: Paul Hoffman [mailto:[email-masked]] 
Sent: Thursday, April 23, 2009 2:00 PM
To: Daniel Brown; Eric Rescorla
Cc: [email-masked]'
Subject: Re: [TLS] Comparative cipher suite strengths

See above.

--Paul Hoffman, Director
--VPN Consortium

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 23 Apr 2009 12:05:18 -0700

At 2:39 PM -0400 4/23/09, Daniel Brown wrote:
>SP 800-57 does not provide rationale for this requirement, does it? 

Correct: it does not. It dances around the rationale in a few places, but does not give a specific rationale.

>Is it unreasonable to speculate NIST's rationale, if only as a less dry way to discuss purely objective arguments, such as Eric's, about recommendations such as Table 4, and their wider applicability to TLS users and people not bound by SP 800-57 but who might appreciate following its guidance, especially given the question about incomparable algorithm security levels over which this thread began?

I believe it is unreasonable, yes. NIST is a government bureaucracy with thousands of employees and an ever-changing management above them (and I say that in both the positive and negative senses). Attributing meaning to what they do beyond what they say their own stated reasoning means that you understand the bureaucracy and requirements they work under better than they do.

--Paul Hoffman, Director
--VPN Consortium

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 23 Apr 2009 13:55:50 -0500

On Thu, Apr 23, 2009 at 01:13:13PM -0400, Daniel Brown wrote:
> Furthermore, adapting Eric's calculations below, to brute force
> 112-bit keys, assuming 80-bit keys are brute forcible today (let's

112-bit keys...  Ah, you must be thinking 3DES.  It's worth noting that
one of the major cryptographic improvements in AES over 3DES is the
block size.  The block size has a major impact on things like re-keying
considerations.  So even assuming equal strength of 3DES and AES and
that 112-bit keys are impossible to brute force now and forever, it'd
still be worthwhile to switch from 3DES to to AES-128.

> just say with massive distributed computing for the sake of example),
> feature sizes would need to shrink to 50 * 10^{-9} * 2^{-32} =~ 1.16 *
> 10^{-17}, still smaller than a Hydrogen atom, but perhaps NIST was
> accounting for the possibility of some future technical developments
> leading to continued or even accelerated increase in processing power,
> or perhaps NIST was also accounting for some degradation in the
> security of the TDEA aglorithm below that of a generic block cipher,
> or perhaps NIST is just encouraging migration to AES. 

If that were quantum computing then all sorts of assumptions go out the
window.  The more likely explanation is that *some* imaginable
cryptanalytic advances could reduce the effective strength of AES in
such a way that longer keys remain more secure than shorter keys.
Imagine an attack that reduces the effective strength of AES so that
breaking it is equivalent to brute-forcing a 2^{key size - 48} key
space.

As EKR points out, there could be cryptanalytic advances that reduce the
strength of AES regardless of the key size used.  But going by past
advances I think it's likely that any cryptanalysis of AES will leave
AES-256 stronger than AES-192, and in turn AES-192 stronger than
AES-128.  Or at least it's likely that NIST and others thing that :)

> That all said, personally, I'm still much more reluctant to predict a
> decrease in the growth of processing power that has been going fairly

Sadly it must come.  We can't reduce feature size too much more than a
few atoms, really (ignoring entangled electrons), and we can't have more
features than we can pack into a reasonable volume.  2^128 ~= 10^38,
which would be only about 10^11 times smaller than Earth.  So you'd need
1/10,000th the amount of matter on Earth in order to make a machine that
has 2^128 features the size of atoms.  Scale that down to something
reasonable (and scale up feature size a bit) and you have a rather small
computer relative to 128-bit key sizes (but still big enough that
distances between components get large enough to be huge headaches).

Short of quantum computing and sci-fi tech such as using black holes as
computers, I really doubt we'll ever brute force 128-bit keys.  It's
cryptanalysis or bust :)

Nico
--

---

From: Martin Rex <[email-masked]>
Date: Thu, 23 Apr 2009 22:02:05 +0200 (MEST)

> still be worthwhile to switch from 3DES to to AES-128.

A few minor comments.

The bit-size is probably about "comparable symmetric cipher strength"
rather than actual key length.

A 3DES with 112-bit keys would be a two-key-triple-DES,
and it is IMHO from the 80-bit comparable symmetric strength ballpark.

In common use is 3-key-triple-DES (usually as 3DES-EDE-CBC),
which means a 168-bit key (when ignoring the parity bits)
and 112-bit comparable symmetric strength.

AES-128 is probably much faster in Software on common 32-bit
and 64-bit CPUs than 3DES (but I don't know about the modern CPUs
from the UltraSparc and Power architectures that have crypto support
built-in).

There is also a difference in the IV size (matching the cipher blocksize)
between 3DES and AES-128.

With 3DES you have additonal problems creating keys compared
to AES-128: none of the 3 subkeys of 3DES must have the same
value, and none of the subkeys should be one of the known
DES weak keys.

And as long as you don't reuse the same symmetric key all
the time, there probably is a difference in the "attributed
algorithm strength" based on the best-known attacks and the
effective protection strength of a moderately sized archived
piece of encrypted data.

In case the encryption key is based on a human-memorized
password (aka password-based encryption) rather than a strong
random session key (as in normal TLS ciphersuites),
then the effective strength of the protection might be *much*
smaller than what the chosen symmetric algorithm can
theoretically provide.

-Martin

---

From: Michael D'Errico <[email-masked]>
Date: Thu, 23 Apr 2009 18:42:34 -0700

> Furthermore, adapting Eric's calculations below, to brute
> force 112-bit keys, assuming 80-bit keys are brute forcible
> today (let's just say with massive distributed computing for
> the sake of example), feature sizes would need to shrink to
> 50 * 10^{-9} * 2^{-32} =~ 1.16 * 10^{-17}, still smaller than
> a Hydrogen atom....

There is a problem with this math (and the original).  Feature
size is a linear measure; the number of features increases as
the square of the feature size reduction.  If you need 2^32
times as many features, then feature size needs to shrink by
"only" 2^(-16).

Mike

---

From: Bill Frantz <[email-masked]>
Date: Thu, 30 Apr 2009 18:56:35 -0700

[email-masked] (Nicolas Williams) on Thursday, April 23, 2009 wrote:

>The more likely explanation is that *some* imaginable

When I think of the reasons that NSA/DOD could have for requiring AES-128
for secret and AES-192 for top secret, I think they may be looking at the
whole cryptographic system. While symmetric cyphers have some solid math
behind them, other parts of the system, such as generating random numbers
for the keys are frequently more akin to black magic.

If my random numbers were only 75% random against some attack, with AES-192
I would still have 128 bits of strength against a brute force attack. With
AES-128, I'd only have 96 bits, and I would be quite concerned when
protecting top secret data.

Cheers - Bill

---------------------------------------------------------------------------
Bill Frantz        |"After all, if the conventional wisdom was working, the
408-356-8506       | rate of systems being compromised would be going down,
www.periwinkle.com | wouldn't it?" -- Marcus Ranum

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 30 Apr 2009 22:50:08 -0700

At Thu, 30 Apr 2009 18:56:35 -0700,
> protecting top secret data.

I don't think this lines up particularly well with how CSPRNGs
work. You start with some random seed information S which you
use to seed the CSPRNG. That seed has some number of bits of
entropy. Call it E. You then generate your cryptographic key.
No matter how long that key is, the total strength of the system
is the cost of brute-forcing S, i.e., 2^E operations. This is true
whether the symmetric cipher is 128 bits or 256 bits.

-Ekr