Subject: Re: [Uta] Remarks on bcp-tls-sheffer-01

From: Yaron Sheffer <[email-masked]>
Date: Wed, 01 Jan 2014 22:58:32 +0200

Hi Watson,

Thanks for your comments. Please see below.

	Yaron

On 12/31/2013 04:57 PM, Watson Ladd wrote:
> This draft has some issues.
> First, its main recommendation involves adoption of TLS 1.2. For servers and
> clients that cannot do this we have a problem, but I don't think the
> draft should be
> silent on this issue. It should strongly urge adoption and explain why TLS 1.0
> doesn't work out. 22.5% percent of websites use TLS 1.2 according to sslpulse.
>

I would like to see more WG discussion of this point. The goal of the 
draft is to move the industry forward but yes, much of the installed 
base will remain on earlier versions.

> Secondly, it recommends brainpool over P256. Yes, there is a question about P256
> parameters, but brainpool constant time implementations are not known to exist.
>

Brainpool is less widely deployed, of course. Is there anything in 
principle that precludes constant time implementations, or can we expect 
such implementations to become available over time?

> Section 6.2 is factually incorrect: DDH is not equivalent to the DLP.
> (I could insert
> a long story about weak reductions here, but they don't matter for
> practical use)

Yes. Thanks.

>
> Thirdly, I don't quite get the RSA over ECDSA recommendation. Some
> implementations (IE on a windows version I don't recall) only support
> ECDHE in the Suite B configuration, with all certificates ECDSA. Is
> this because of legacy certificates?

Of course. "Legacy" certificates are probably >99% of the existing 
certificates (with the last 1% being US Federal). Ralph might have 
better numbers.

>
> Fourth, if a browser doesn't support TLS 1.2 and ECDSA there will be a
> fallback. What should that fallback be, and how should various
> fallbacks be ordered?

I believe you meant, "Server doesn't support TLS 1.2 and ECDSA". 
Currently we only mandate "no fallback to SSLv3". I strongly suspect 
that any recommendation we make here will not be heeded anyway. 
Fallbacks are a browser-specific black art.

>
> Sincerely,
> Watson Ladd
> _______________________________________________
> Uta mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/uta
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 2 Jan 2014 00:28:26 +0200

On Wed, Jan 01, 2014 at 10:58:32PM +0200, Yaron Sheffer wrote:
> principle that precludes constant time implementations, or can we
> expect such implementations to become available over time?

Of couse, it is _possible_ to implement Brainpool in constant time,
but unfortunately, Brainpool curves are not of special form that
has fast constant-time arithmetic.

Thus either Brainpool implementations are not constant-time or those
are slow.

Furthermore, the random primes are quite annoying to work with.
 
The most important special classes (there are some others as well) of
prime-order curves with fast constant-time arithmetic are complete
Montgomery/Edwards curves.

BTW: Some cryptographers took the generation process of Curve25519
and Curve1174 (which is of Edwards type) and extended it to 224/384/512-
bit level.

All these curves (except E-521 which aren't listed for some reason)
pass everything in safecurves.

Reference:
Diego F. Aranha, Paulo S. L. M. Barreto, Geovandro C. C. F. Pereira,
Jefferson Ricardini. "A note on high-security general-purpose elliptic
curves." 2013. http://eprint.iacr.org/2013/647

> Fallbacks are a browser-specific black art.

Fallbacks are always due to one of:
1) Buggy server.
2) Buggy client.
3) Something on the path between interfering with TLS[1].
4) Transistent network errors causing inapporiate fallback[2].

Fallbacks are not the same as version negotiation. TLS 1.2
client vs. TLS 1.1 server (or vice versa) selecting TLS 1.1
on the first try is not a fallback.

And unfortunately I think there still are severly buggy stuff
that requires fallbacks to SSL 3.0 w/o extensions.[3][4]

Some of that might be EOL'd local-use stuff that will contine
to be run for years and years... And I think there are a
bunch of public webservers as well...

Blech, what a mess, especially considering we are dealing
with a security vulernability.

[1] Sometimes security programs installed on the client do
this!

[2] Retry with the same version would have worked.

[3] Blech. Die, die, die.

[4] And then there's unfortunately also non-renego-patched
stuff there...

-Ilari

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 01 Jan 2014 23:45:13 +0000

On 31/12/2013 10:26, Yaron Sheffer wrote:

> The idea was to recommend only things that are currently
> standardized, and already widely (though definitely not
> universally) implemented.

Noted. See below.

> But it means that with a bit of industry push, the RFC will be
> usable by *implementors* within 6-12 months.

I would prefer a little faster than that, if we can.

This is intended to be, at first blush (and my interpretation):
• A standard of Best Current Practice on Secure TLS Configuration
• To advise people how to _properly_ securely configure
• TLS implementations they've _already got_
• Based on what we know _right now_
• Which we will update
  - as new threats arise; and,
  - as new standards (and implementations) arise out of drafts
    · i.e. agl's [1.2] and Nikos' [1.1 & 1.0] ChaCha20, etc
• Which we can point other people (and organisations) to and say
  - If you don't do it like this, you're insecure!
  - Here is _why_ that other advice you got and/or gave was wrong
  - And why you need to change this _right now_ to be secure

I think that's what it's going to take to overcome the inertia of
existing bad practice.

                                 -oOo-

So, that said, my own rather disorganised (sorry!) comments on this
early draft:

> [TLS 1.2]

On 31/12/2013 14:57, Watson Ladd wrote:
> It should strongly urge adoption and explain why TLS 1.0 doesn't
> work out.

I'd go further. As a document hopefully intended to codify Best
Current Practice, it should not merely strongly urge, it should have
TLS 1.2 support as an absolute unconditional MUST.

That is, a server or client which does not implement TLS 1.2 at all is
incompliant; and any server or client which cannot talk to TLS 1.2 is
incompliant.

Then it should explain, specifically, why that is. (But see below, for
backwards-compatibility.)

> [curve choice]

Sorry, I can't agree with that one: brainpoolP256r1 unfortunately has
a weak twist¹.

Also, as Watson points out, where you have non-hardcoded ECDHE
implementations deployed which are capable of working on arbitrary
curves (and actually very few of them are), they're not constant-time.
That is also a Problem.

As it stands, despite our misgivings - as all NIST can do is state the
seeds are pseudo-random, but for now, can't prove there was nothing up
the sleeve of the generators, and people certainly have real questions
about that - we don't have anything concrete right now to suggest the
widely-deployed (and, often, only supported) secp256r1 (aka
prime256v1) is necessarily particularly weak.

We know it's hard to implement in constant-time, as we want (but such
implementations _do_ exist for it in some common libraries, unlike
brainpool).

If we've gotta have a curve for ECDHE, and it's got to be what's out
there right now, it's pretty much got to be secp256r1 - but we
definitely want to replace that with a SafeCurve when we can, and it
MUST be a constant-time implementation.

> [RSA vs ECDSA]

ECDSA certificates are still pretty rare, as are ECDSA CAs.

I feel secure use of ECDSA requires RFC6979. I think that _if_ you do
that, and you MUST do that, and if you use a strong curve, and a good
implementation (as above), it is probably secure.

I'd definitely be more comfortable with EdDSA_Ed25519, or
EdDSA_Curve3617, but that's something for the future, and this is a
recommendation for the immediate present while we work on fixes.

> [Ciphers]

Might we prefer AES-128 and not AES-256? Specifically, from my
understanding, AES-128 is faster, but from what we know at the moment
(the meet-in-the-middle attack), I'm not sure if either AES-192 nor
AES-256 are technically better - that's my understanding anyway,
_please_ feel free to correct me, as I know it's a time-space tradeoff.

However, none of the attacks on AES of any form are practical, or are
expected to be in the short- or medium-term.

If you wanted better, you'll have to wait, maybe for ChaCha20_Poly1305
(when it comes out of draft).

We have to consider this carefully in light of fallbacks and what
known clients in-the-wild will negotiate.

> [Fallbacks]

We have got to have something in there for fallbacks, and we should
specify exactly what that should be, for exactly which clients, and
exactly why, and the security impact of having them.

We probably can't get great security (particularly not forward
security) with every client people want their servers to talk to, and
definitely not with every server people want their client to talk to.

They will want backwards-compatibility, and we definitely need to
provide guidance as to the whole list to use.

Notably, many clients out there, even current ones, still use TLS 1.0,
as do many servers. It needs to be made clear that this is incompliant
and they need to fix that. But servers will want to talk to clients,
and clients will want to talk to servers, and we should make sure they
do the best they can.

Admittedly, that happens in the presence of absolutely no downgrade
protection fielded at the moment. That demands that anything we know
to be insecure MUST NOT appear in the list. We just can't have it
there; if it's there, an attacker can force it to be chosen. So we
have kind of a problem.

It depends how far back people want to go, and the relative
difficulties posed by each known, and theorised, attack. We need
advice about that.

RC4 has got to go. It does not appear in the list - period. Nor should
MD5. I'd rather see DES_CBC3_SHA in there, at the end, supported by a
server for rusty old clients, than RC4_SHA or RC4_MD5.

DHE_RSA_AES128_SHA would be better - but the DH group MUST NOT be 1024
bits - that is not good enough. That poses a problem to Java's crypto
library, which can't negotiate DHE with secure key sizes.

> [And so...]

My tentative suggestion, and I'm not sure I particularly like it - in
fact, I absolutely hate it, and welcome input from others to get it to
something I hate less, particularly with regard to which clients will
connect to what with what, which is probably the important bit.

• ECDHE and ECDSA should use secp256r1 [23], for now. (Ugh. Sigh.)
  - They MAY use secp384r1 or secp521r1, on the strict condition they
    have constant-time implementations of those. If not: take them out.
• You MUST have a constant-time implementation of secp256r1 for ECDSA
  and ECDHE.
  - If that is not the case, or you're not sure, remove those suites.
  - Problem: You need this to support connections from or to Java.
    (Oh, god, Java. <headdesk>)
    Otherwise it'll fall through to 2048-bit DHE and break. Sorry.
• ECDSA MUST NOT be used unless RFC6979 is implemented in your library.
  - If that is not the case, or you're not sure, remove those suites.
• You MUST NOT use DSS certificates. (God, does anyone? I hope not.)
• All RSA certificates MUST have at least 2048 bits.
• Certificates MUST use at least SHA-1 (and MUST NOT use MD2 or MD5).
• Certificates SHOULD use SHA-256 - this is preferable, if your clients
  support this.
  - Insert notes on which ones do and don't? Is this still a problem?
  - If not, make SHA-256 a MUST.
• DHE, where used, MUST use DH parameters of 2048 bits.
  - Do we have recommendations about generating your own vs. pre-baked?
  - I don't support 1024-bit DHE. It's just too damn weak. I know that
    poses a problem to Java in particular, but I'm not convinced using
    weak keys is worth FS to a bad client.
• This is conditional on the basis that AES-256 is no better than
  AES-128: accordingly I favoured that on the basis that 128 is faster.
  Others should weigh in on that.
• Any GCM, CCM or CBC implementation MUST be constant-time.
  Else, consider falling back.
• You MUST have server-side countermeasures to the BEAST attack.
• You MUST NOT support TLS compression.

• TLS 1.2, allowing TLS 1.1 or TLS 1.0; you SHOULD NOT support SSLv3
  and MUST NOT support SSLV2.

This is what I'd sort of consider given that. I'm... not loving this,
however. It has multiple issues, chief among them, of course, how this
would survive contact with the real world.

(----Time Travelling TLS 1.2 Top Tier----)
[cc14] TLS_ECDHE_ECDSA_WITH_CHACHA20_POLY1305_SHA256 #
[cc13] TLS_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256 #
[cc15] TLS_DHE_RSA_WITH_CHACHA20_POLY1305_SHA256 #
(----Time Travelling TLS 1.1 and 1.0 High Tier----)
[e502] TLS_ECDHE_ECDSA_WITH_CHACHA_SHA1 &
[e501] TLS_ECDHE_RSA_WITH_CHACHA_SHA1 &
[e507] TLS_DHE_RSA_WITH_CHACHA_SHA1 &
(----High Tier: AEAD with Forward Security----)
[c02b] TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 *†
[c02f] TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 *
[c02c] TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384 *†
[c030] TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 *
[009e] TLS_DHE_RSA_WITH_AES_128_GCM_SHA256
[009f] TLS_DHE_RSA_WITH_AES_256_GCM_SHA384
[c09e] TLS_DHE_RSA_WITH_AES_128_CCM ‡
[c09f] TLS_DHE_RSA_WITH_AES_256_CCM ‡
(----Medium Tier: Forward Security, but potentially BEASTly----)
[c023] TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA256 *†
[c024] TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA384 *†
[c027] TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256 *
[c028] TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384 *
[c009] TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA *†
[c00a] TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA *†
[c013] TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA *
[c014] TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA *
[0067] TLS_DHE_RSA_WITH_AES_128_CBC_SHA256
[006b] TLS_DHE_RSA_WITH_AES_256_CBC_SHA256
[0033] TLS_DHE_RSA_WITH_AES_128_CBC_SHA
[0039] TLS_DHE_RSA_WITH_AES_256_CBC_SHA
(----Low Tier: Anything below this line has no Forward Security----)
[e500] TLS_RSA_WITH_CHACHA_SHA1 &
[009c] TLS_RSA_WITH_AES_128_GCM_SHA256
[009d] TLS_RSA_WITH_AES_256_GCM_SHA384
[c09c] TLS_RSA_WITH_AES_128_CCM ‡
[c09d] TLS_RSA_WITH_AES_256_CCM ‡
(----Crud Tier: No Forward Security; no AEAD; potentially BEASTly----)
[003c] TLS_RSA_WITH_AES_128_CBC_SHA256
[003d] TLS_RSA_WITH_AES_256_CBC_SHA256
[002f] TLS_RSA_WITH_AES_128_CBC_SHA
[0035] TLS_RSA_WITH_AES_256_CBC_SHA
(----Hell Tier: Abandon Hope All Ye Legacy Clients Who Enter Here----)
[000a] TLS_RSA_3DES_EDE_CBC_SHA §

# This is still a draft, and thus not widely deployed at all. Included
  in here for references' sake; definitely won't make it to BCP until
  it's standardised.
  { draft-agl-tls-chacha20poly1305-04 }
& For use in TLS 1.1 and TLS 1.0 only. Still a draft, and thus not
  widely deployed at all. Included in here for references' sake;
  definitely won't make it to BCP until it's standardised.
  { draft-mavrogiannopoulos-chacha20-tls }
* Requires a constant-time secp256r1/prime256v1 implementation.
† Requires RFC6979 support from server (and client if client
  certificates used)
‡ This is, although standard, not widely deployed.
§ This should only be included if you REALLY NEED it there.

Note: RC4 is deliberately NOT in this list. It languishes deep in
      Hades, below 3DES, in the realms of 40-bit EXP ciphers, MD5, MD2,
      and NULL.

      The whole reason for us doing this is to get it out of the list.

      If we have it in the list for any reason, peers which prefer it
      based on earlier, bad advice, will (unfortunately) pick it.

I'm not sure this doesn't have more problems than the draft! Ugh.
(Oh well, I've spent two hours drafting this: shoot it out, see what
 people say - hopefully the discussion will at least be helpful...)

___
1. In fact, at 2^44.5, brainpoolP256r1 has the weakest twist (t1) of
   any curve so far analysed by SafeCurves.
   <http://safecurves.cr.yp.to/twist.html>

- -- 
/akr

---

From: Watson Ladd <[email-masked]>
Date: Wed, 1 Jan 2014 18:55:17 -0500

> has fast constant-time arithmetic.

So I originally asked this question, but I think that if you use
Montgomery reduction
it might be possible to eek out acceptable performance. The question of what is
"acceptable" rears its ugly head at this point.

> Montgomery/Edwards curves.

Well, there are two issues. The first is the speed of the prime, the
second is the
speed of the curve in field operations. Short Weierstrass form hurts the second,
but the brainpool curves hurt the first badly.

> 4) Transistent network errors causing inapporiate fallback[2].

So I said fallback, I meant server not supporting the recommended
ciphersuite or negotiating
a version for which it is not defined. Ideally the BCP would make a
decision between the various
TLS 1.0 and 1.1 ciphersuites as well as picking a TLS 1.2 ciphersuite,
and this decision would be
a recommended total ordering.

For instance, we have to pick between PFS and sufficiently long key
lengths due to the JSSE implementation
falling down on DHE parameters that are over a certain length.

While I was writing this email Alyssa Rowan sent an email covering
similar ground: I'll respond to that one in a bit.
Sincereley,
Watson Ladd
-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 1 Jan 2014 19:33:27 -0800

On Dec 31, 2013, at 6:57 AM, Watson Ladd <[email-masked]> wrote:

> Yes, there is a question about P256
> parameters

What question is that? I have seen even the most anti-NSA folks saying that they don't think there is a problem, but there might be questions I missed. I think it is important for this discussion.

--Paul Hoffman

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 02 Jan 2014 07:36:40 +0000

On 02/01/2014 03:33, Paul Hoffman wrote:

>> Yes, there is a question about P256 parameters
> What question is that? I have seen even the most anti-NSA folks 
> saying that they don't think there is a problem, but there might
> be questions I missed. I think it is important for this
> discussion.

To summarise (I'll use SafeCurves' terminology):

• The NIST/SEC curves lack "rigidity"; they are "manipulatable"¹.

• The concern is that the NSA may have manipulated the parameters in a
  way that weakens them.
  - The parameters were generated from SHA-1 "seeds".
  - The NIST/SEC documents spend time explaining how to prove the
    parameters came from these seeds.
  - However: the NIST/SEC documents seem to _very carefully_ omit
    details of where the seeds _came_ from - no-one knows!
    · No "nothing-up-my-sleeve" numbers present
  - This is of particular concern, because that's exactly the kind of
    thing that happened with Dual_EC_DRBG
    · Which, courtesy of NSA, had an enormous backdoor in it because
      they picked, essentially, the public key
    · That was noticed straight away
  - The congruity between this and the opacity of the NIST/SEC curve
    generation process was only really raised recently
    · SafeCurves
  - but it's not the first time it was raised
    · Brainpool, for example
  - How could they have done this if they couldn't reverse SHA-1?
    · Easy: repeatedly try seeds until they get one with the right
      characteristics
    · I think we can assume the NSA have always had enough computer
      power to do something like that; any of us probably have!

• Here's the problem: we don't know if they _did_, specifically,
  backdoor these curves.

• But here's what we _do_ know, thanks to Edward Snowden:
  - Quoting nsa-sigint-enabling-propublica-13-0905.pdf²

                    "(U) COMPUTER NETWORK OPERATIONS"
                          "(U) SIGINT ENABLING"
    · This is their big "backdoor project"

    "(S//NF)" [a table with their budget from 2011-2013]
    · Funded to the tune of ≈$250-$300 million each year
    · ≈141-144 employees, full time, all civilians, at that time
    · We know they exist today, and we know they existed before 2011
    · They have clearly existed for a _long time_
    · We don't know how long exactly
    · Some overt & covert malign influence from NSA seems to predate
      20131109
    · But they got way more active afterwards

      Here's their mission statement:

    "(TS//SI//NF) The SIGINT Enabling Project actively engages the US
     and foreign IT industries to covertly influence and/or overtly
     leverage their commercial products' designs. These design
     changes make the systems in question exploitable through SIGINT
     collection (e.g., Endpoint, MidPoint, etc) with foreknowledge of
     the modification. To the consumer and other adversaries, however,
     the systems' security remains intact. In this way, the SIGINT
     Enabling approach uses commercial technology and insight to
     manage the increasing cost and technical challenges of
     discovering and successfully exploiting systems of interest
     within the ever-more integrated and security-focused global
     communications environment."
    · Translation: This NSA unit secretly backdoors commercial
      (civilian: this is positively known to even include NIST)
      technologies, so we can break them, because we know what we
      did, but if you don't know what we did, you won't know that we
      weakened them, that we can break them, or how

    "(TS//SI//REL TO USA, FVEY) This Project supports the
     Comprehensive National Cybersecurity Initiative (CNCI) by
     investing in corporate partnerships and providing new access to
     intelligence sources, reducing collection and exploitation costs
     of existing sources', and enabling expanded network operation
     and intelligence exploitation to support network defense and
     cyber situational awareness. This Project contains the SIGINT
     Enabling Sub-project."
    · Translation: They mostly do this by bribing/subverting people

    "(U) Base resources in this project are used to:"
    "(TS//SI//REL TO USA, FVEY) Insert vulnerabilities into
     commercial encryption systems, IT systems, networks, and
     endpoint communications devices used by targets."
    · Translation: They backdoor things.

     [...skipping ahead a little...]
    "(TS//SI//REL TO USA, FVEY) Influence policies, standards and
     specification for commercial public key technologies."
    · Translation: Oh, crap. We may have a problem here.

    [...]
    "(TS//SI/NF) Shape the worldwide commercial cryptography
     marketplace to make it more tractable to advanced
     cryptanalytic capabilities being developed by NSA/CSS.
     [CCP_00090]"
    · Translation: In 2013, we plan to make it even easier for us
      to crack crypto!

  - Specific, infamous examples of what they've done:
    · Dual_EC_DRBG - the only _obvious_ covert backdoor to date
    · And they paid RSA Security $10m to use it
  - Less specific
    · Wireless: phone crypto? - "specific and aggressive"
    · Wireless: satellite crypto - "a commercial satellite provider"
    · They prefer being more subtle in their weaknesses
    · Fragile crypto which makes it easier to backdoor
    · High RNG reliance (which explains the RNG backdoors)

• We have a problem, then.
  - We know they have been doing, and do, this kind of thing
  - It even appears as a specific line-item in their budget!
  - But we don't know specifically WHAT they've influenced
  - Or how

• Right now, the only vulnerabilities we can positively identify
  are¹:
  - secp224r1: Insecure twist - 2^58.4
  - secp256k1: CM field discriminant D = -3 (≈2^1.6)

• We don't know of any other vulnerabilities right now
  - And we don't know if those were deliberate, either
  - But given all of the above, we're pretty damn concerned there
    may well be others we don't know about specifically yet
  - The NSA have a huge head-start on ECC, and were using it
    secretly even before their deal with Certicom
  - By the way, they had a deal with Certicom
    · We don't know if that was just to use their encryption, or
      to backdoor it - possibly just use
    · But you should probably look at Dan Brown's message
    · He didn't work there at the relevant time, but they did
      have a partnership with them back then

• Basically, there's a whole lot we don't know, but many things that
  tend to make us highly uncomfortable about secp256r1. Its immediate
  peers are weak, we don't specifically know how the seeds were
  generated, and there's massive concern they were backdoored -
  somehow - by the NSA, who have influencing public-key technologies
  in a negative way in their top secret line-item budget.

I await private communication which _might_ serve to clarify the
matter a little, depending on what I hear, and I will update if I
am able to do so (or they will, directly): that doesn't change the
facts that we know, only the confidence of what we derive out of them.

The upshot is, we need to switch to new things with no NSA influence,
because we suspect secp256r1 has had negative NSA influence.

The downside is, the SECP curves are the only ones in TLS with mature
constant-time implementations. We plan to add others, probably the
SafeCurves, soon, in either TLS 1.2 (if possible) or TLS 1.3.

I hope that helps summarise. Please correct me if I've got anything wrong.

___
1. <http://safecurves.cr.yp.to/>
2.
<http://cryptome.org/2013/09/nsa-sigint-enabling-propublica-13-0905.pdf>

- -- 
/akr

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 02 Jan 2014 07:39:05 +0000

On 02/01/2014 07:36, Alyssa Rowan wrote: (Sorry for the double-post!)

> · Some overt & covert malign influence from NSA seems to predate 

Oops, obvious correction: 20011109 i.e. "9/11"!

> The upshot is, we need to switch to new things with no NSA
> influence, because we suspect secp256r1 has had negative NSA
> influence.

> The downside is, the SECP curves are the only ones in TLS with
> mature constant-time implementations. We plan to add others,
> probably the SafeCurves, soon, in either TLS 1.2 (if possible) or
> TLS 1.3.

Our really big concern, for this BCP right now, is how to balance
these two.

- -- 
/akr

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 2 Jan 2014 07:31:51 -0800

On Jan 1, 2014, at 11:36 PM, Alyssa Rowan <[email-masked]> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
> 

To summarize your concerns, only Dan Bernstein's curve would be acceptable for a 128-bit security level because all other commonly-deployed curves fail his design criteria. Further, nowhere on the SafeCurves page does Dan question the P256 parameters. Instead, he has a design where those parameters are not needed.

Let me be a bit more specific: can you reference sites where P256's parameters are questioned more than the parameters of other widely-deployed elliptic curve?

It's fine if this WG wants to abandon every widely-deployed elliptic curve other than Curve25519 and its cohorts, but if the WG does that, it needs to do it explicitly.

--Paul Hoffman

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 2 Jan 2014 19:21:08 +0200

>     (Oh, god, Java. <headdesk>)

Also, MUST check that the received points are valid, unless one does
one-coordinate ladder on twist-secure curve (a'la Curve25519).

This holds even if point compression is used (one can still do twist
attacks otherwise).

If one doesn't, that leads to invalid curve or twist attacks.

>   - If that is not the case, or you're not sure, remove those suites.

RFC6979 seems to have undesirable properties timing-wise.

When used with something-equivalent-to-Curve25519[1], it fails especially
bad[2].

The idea of RFC6979 (deterministic signing) is a good one tho.

> • You MUST NOT use DSS certificates. (God, does anyone? I hope not.)

I think only a few have been seen in the wild.

>   Else, consider falling back.

AFAIK, there is no current non-NULL ciphersuite in registry that can
be implemented:
- With good performance (relative to non-protected implementation)
- Without hardware support
- In perfect constant time.

So this would pretty much need the Chacha ciphers.

[1] In theory, Curve25519 works directly with ECDSA. However,
in practice this is a bad idea (suboptimal performance[3],
implementation difficulties[4]).

[2] Failure chance per round is ~1/2. Even NIST P-256 has ~1/2^32
chance.

[3] Way suboptimal compared to what can be done at equivalent
security, not necressarily slow in absolute terms.

[4] Complete with one nasty surprise[5] that will totally break
security if you hit it...

[5] Clamping the private key. Some implementations do that internally!

-Ilari

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 02 Jan 2014 19:20:56 +0000

On 02/01/2014 15:31, Paul Hoffman wrote:

>>> What question is that? [...] I think it is important for this 
>>> discussion.
>> [...admittedly long summary...]
> To summarize your concerns, only Dan Bernstein's curve would be 
> acceptable for a 128-bit security level because all other 
> commonly-deployed curves fail his design criteria.

I feel you may be mischaracterising my summary somewhat.

I didn't evaluate the "SafeCurves" as part of that summary.

I was simply, independently, stating the reasons why trust in the
NIST/SEC curves in general has been undermined; and covering (I hope
in a calm and balanced way) what we know, what has been disclosed, and
what we don't know.

Any decision that we take should, I feel, be taken with the fullest
knowledge of the situation that we can have - including knowledge of
the widely-expressed doubts and the reasons behind them, but also
knowledge of the very real gaps in what we know that lay behind those
doubts, so that we can make a fair assessment.

And, of course, foremost in our mind, the question of what is
available right now - because those are the choices we have to make
right now. Choices that a hell of a lot of internet security is
probably going to rely on.

> Further, nowhere on the SafeCurves page does Dan question the P256
>  parameters.

That is incorrect. The SafeCurves page (which is joint work between
djb and Tanja Lange, incidentally) states¹ that the parameters were
generated from seeds whose source were unexplained, and therefore they
are manipulatable - there are no 'nothing-up-my-sleeve' numbers.

I have already independently covered why that assessment is correct,
and the reasons behind why that raises a concern, in my previous
message; which, with the greatest respect, I feel you may not have fully
digested.

> It's fine if this WG wants to abandon every widely-deployed 
> elliptic curve other than Curve25519 and its cohorts, but if the WG
> does that, it needs to do it explicitly.

You misunderstand. None of the "SafeCurves" are at this time specified
for use in TLS. That is, as yet, an unwritten draft (although one that,
if drafted, would certainly be promising for TLS 1.3, or even TLS
1.2). Although they have been used in other areas, they are certainly
not widely-deployed for TLS.

As Montgomery and Edwards curves, they are not really suitable for
feeding as-is as arbitary curves directly into short-Weierstrass
ECDHE/ECDSA routines; to do so invites a few practical problems (as
Ilari has raised). They are designed more for use with something like
EdDSA - which is also, as yet, an unwritten (but potentially-
promising) draft.

Newer crypto is often better than older crypto. That's how we move
forward. It also takes time to standardise and deploy. That's normal.

Therefore, although they would be nice, as would ChaCha20_Poly1305,
I think that falls outside the scope of what we can recommend in this
revision of the BCP. Pity. We should revisit that at a later date.

> Let me be a bit more specific: can you reference sites where P256's
> parameters are questioned more than the parameters of other 
> widely-deployed elliptic curve?

As I hope my summary makes clear, there has been a question mark over
the progeny of all of the NIST/SEC curves for some time. In
particular, this was the _reason_ for Brainpool (although, as I have
stated, I do not feel brainpoolP256r1 would be a suitable in-situ
replacement due to its weak twist, even relative to secp256r1; perhaps
brainpoolP384r1 would, however, but see below re: my notes on
availability).

The NIST/SEC curves proliferated, despite some caution on their 'magic',
largely on the basis that it was believed at the time NSA (who worked
with Certicom and had aggressively promoted them, whether they had a
hand in their generation or otherwise) had a vital interest in
assuring the availability of strong cryptography as part of their
"Information Assurance" mission, and would not therefore seek to
further their SIGINT (spying) mission by subverting public standards
they themselves sought to use.

In fact, that belief proved to be clearly incorrect, as NSA actually
proved willing to backdoor NIST standards in practice (Dual_EC_DRBG) and
then manipulated commercial vendors into actually using those
backdoored standards (RSA).

That it has been disclosed that they have a line-item in their
'backdoor budget' _specifically_ for manipulation of public-key
standards has brought the doubt regarding the NIST/SEC curves into
particularly sharp focus recently.

We do not know whether the NIST/SEC curves are backdoored. They may
be. They may not be. We do know that those behind them have been party
to similar backdoored standards. We do know they have a budget to
backdoor public-key standards, which is what the curves are. And we
still do not have a concrete assurance that they are _not_ backdoored,
where we would normally expect and demand to have such an assurance
(as with any unexplained 'magic numbers' in a crypto standard).

On the other hand, we do not know of a current public attack that
breaks the NIST/SEC curves in use when they are properly implemented.
Unless Snowden has a huge bombshell for us, we simply do not know the
full extent of what nation state adversaries have on the table². And
it may be that any weakness, if it is present, is quite simply the
"properly implemented" part, and to any useful extent has already been
independently rediscovered and addressed. Again: we don't know.

I've raised all that in my previous message.

But here, in this WG, for the Best Current Practice, we're faced with
the question of what is best right now, in the short-term; to make
recommendations not for tomorrow, but for today.

You mention widely-deployed elliptic curves, and indeed, that's
probably the relevant point for us to consider now. We need to weigh
this, publicly and openly, as a group, against the concerns and make a
considered judgment.

My take:

Here's what's on the table right now; these are the widely-deployed
elliptic curves available in most of the common libraries that support
ECDHE and/or ECDSA:
• secp192r1 (aka prime192v1)
• secp224r1
• secp256r1 (aka prime256v1)
• secp384r1
• secp521r1

That is quite a short list; and they are all NIST/SEC curves. It gets
shorter. Here are the universally-deployed elliptic curves, available
in all of the common libraries that support ECDHE and/or ECDSA:
• secp192r1 (aka prime192v1)
• secp256r1 (aka prime256v1)
• secp521r1

The brainpool curves have been standardised, but are only actually
available as named curves in Botan and PolarSSL. Arbitary curve
support seems only to be implemented as available in OpenSSL (and
isn't constant-time).

Only secp256r1 and secp384r1 has constant-time routines available and
at least somewhat frequently deployed in the wild. And secp384r1 isn't
implemented in all the libraries.

I therefore essentially feel, despite widely-expressed misgivings
about the continued medium-term and long-term use of the NIST/SEC
curves, for short-term curve recommendations, we're selecting (via a
process of elimination) from a slate of one candidate:
• secp256r1 (aka prime256v1)

It is not ideal. Doubts have been raised over it that remain
unanswered. There is quite a lot of scope for improvement in the
future: the SafeCurves appear a fruitful source for that improvement.

But as for recommendations for now, we're probably stuck with
secp256r1 if we want to use elliptic curves usefully at all in this
revision of the BCP.

Such is the nature of practical compromise. Oh well.

If the murkiness surrounding the NIST/SEC curves made us too jumpy and
we took the decision to remove ECDHE entirely for now, we have the
unfortunate practical problem that the DHE modes, the other (far more
traditional) forward-secure modes, have a serious interoperability
problem with Java with keys of a size considered reasonable today
(2048-bit); it just doesn't work. (Unlike curves, we don't have a way
to negotiate DHE parameter size support.)

DHE's also fairly slow by comparison, to the extent that many people
were turning it off for performance reasons - because, hey, who'd
steal your RSA key? (Of course, that too turned out to be a problem.)

And, of course, those are our only two choices which yield
forward-security, which as we now know is a pretty vital property we
can't afford to ignore.

That's why I think, even despite misgivings that I support and fully
understand, I think secp256r1 is probably the right choice for curve
support in TLS, on balance, right now: and why for tomorrow's TLS, I
think we should definitely be looking at better choices.

Of course, I'm very interested in the input of others, who no doubt
have far more to say than I, and hopefully far more practical data
about server and client support.

I hope together we can come up with some really good advice. And -
more importantly - I hope together we can convince people to actually
take it!

___
1. <http://safecurves.cr.yp.to/rigid.html>

2. From what has been disclosed so far, and a little dash of common-
   sense: to a nation state adversary, stealing keys, compromising
   endpoints, tapping networks behind frontends, or impersonating
   certificates via rogue/compromised CAs is probably much easier than
   cracking them (unless a backdoor, if present, is _really_
   phenomenal).

- -- 
/akr

---

From: Watson Ladd <[email-masked]>
Date: Thu, 2 Jan 2014 17:35:16 -0500

> If one doesn't, that leads to invalid curve or twist attacks.

And you have to ensure all sorts of things in an implementation.
> The idea of RFC6979 (deterministic signing) is a good one tho.

Please understand the way Ed25519 works. E(F_p) is the direct sum of
two groups, one order 8 and the other order q. When using with ECDSA
you only use
the group of order q. I leave it as an easy exercise to figure out why
this renders it
no worse than with prime order curves. The failure chance doing this
is 1/2^(127),
which is better than P256.

The timing issue might be more of an issue with brainpool: it depends
on the gap between
q and 2^{ceil(log(q)/log(2))}. I've not done the calculations yet.

ECDSA has an inversion modulo the group order which costs a lot
relative to group operations.

I'm curious what you have that is faster than Ed25519/ECDSA. SUPERCOP
has RSA verification
being faster, but for signing very little is faster at equivalent
security. Signing is the bottleneck: verification happens on lots
of clients as opposed to a few servers.

> So this would pretty much need the Chacha ciphers.

Performance should be absolute of protected implementations. Why
should a cipher lose out
because an unprotected version can be heavily optimized?

Sincerely,
Watson Ladd

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 3 Jan 2014 02:14:40 +0200

> which is better than P256.

I was referring to failure chance if generated according to RFC6979.

I get that the failure chance per round is approximately 0.5 (the
corrections to that number are insignificant).

This is because RFC6979 uses 253 bit input if used with something-
equivalent-to-Curve25519 (because q doesn't fit in 252 bits) and q
is barely any larger than 2^252.

Ed25519 does not generate k according to RFC6979. It internally generates
512-bit pseudorandom number and does modular reduction (no chance
of failure).

It is fairly easy to take a 377-bit number and reduce it modulo
Curve25519 group order minus one. Don't know if 125 extra bits
are enough (NIST specs say 64 is enough, but those are NIST
specs...)

> relative to group operations.

Yeah, there are probably over 250 squares and dozens of mults mod q
(I haven't worked out or seen the optimal chains, so I don't
know the exact counts).
 
> I'm curious what you have that is faster than Ed25519/ECDSA. 

Nothing really. Ed25519 uses Edwards curve that is equivalent
to Curve25519.

I was talking about using Curve25519 directly (ECDSA and GOST need
just the X coordinate which is computed by Curve25519!)

Of course, this leads into implementation troubles with verification
(there's a point addition in there, which is not compatible with
X-only!).

> because an unprotected version can be heavily optimized?

There are AES implementations that are nearly constant time and
run with good performance (but doing such implementation is Hard).

But these implementations are not perfect constant time. Even
the naivest implementations of SHA-2, Salsa20, Chacha, Threefish,
etc... are. Also, main implementations of Curve25519 are also
perfect constant time (and I have also written such myself).

-Ilari

---

From: Rob Stradling <[email-masked]>
Date: Fri, 03 Jan 2014 11:52:35 +0000

On 02/01/14 19:20, Alyssa Rowan wrote:
<snip>
> • secp256r1 (aka prime256v1)

secp192r1 is not universally supported.  MS CryptoAPI only supports 
secp256r1, secp384r1 and secp521r1.

> implemented in all the libraries.

What libraries don't support secp384r1?

http://en.wikipedia.org/wiki/Comparison_of_TLS_implementations claims 
that SecureTransport doesn't support secp384r1, but I suspect this claim 
is incorrect.

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 03 Jan 2014 13:20:49 +0100

> secp256r1, secp384r1 and secp521r1.

RedHat/Fedora systems are also confined to support only these three
curves.

regards,
Nikos

---

From: Ivan Ristic <[email-masked]>
Date: Fri, 03 Jan 2014 12:32:39 +0000

> secp256r1, secp384r1 and secp521r1.

Further, Internet Explorer appears to offer only secp256r1 and secp384r1:

https://www.ssllabs.com/ssltest/viewClient.html?name=IE&version=11&platform=Win%208.1

IE 7 on Vista offers secp521r1, but other versions don't.

To see what major browsers/clients do offer (I have a good selection of 
22 clients on various platforms), go to any SSL Labs result page, scroll 
to the Handshake Simulator section, and click on each client name:

https://www.ssllabs.com/ssltest/analyze.html?d=www.ssllabs.com

-- 
Ivan

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 03 Jan 2014 13:03:35 +0000

>https://www.ssllabs.com/ssltest/analyze.html?d=www.ssllabs.com

Thank you all for the corrections and further information: that's especially helpful, Ivan. The bigger challenge is likely to be some of the more obscure clients (and of course Java, with its ever-helpful 1024-bit cap on DHE).

It did seem odd to me that Secure Channel apparently didn't support secp384r1, as secp256r1 and secp384r1 are the curves NSA specified for "Suite B" for 128-bit and 192-bit security, and I'd have expected US Government use to have encouraged the adoption of both of those. More likely to be a mistake: I'll try and check and hunt down a few more.

(Oddly, I can't see them actually using secp521r1 in anything - the "256-bit" application profile is curiously absent from several "Suite Beatifications", as Kevin Igoe put it. Maybe it didn't meet their needs for those applications? For what reason, I wonder?)

I'll take a look at those and see if any particularly useful intersections pop out.

- --
/akr

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 03 Jan 2014 15:12:24 +0200

Hi Alyssa,

I just got around to reading the recent flurry of emails on this list, 
sorry for the delay.

Thanks a lot for injecting more crypto clue into this discussion.

I 100% agree with your characterization of the goals of the BCP, below. 
And the following should be taken with that in mind.

You are using the term "compliant". The word is generally shunned in the 
IETF, and in particular I don't think it ever applies to a BCP. We are 
making recommendations. People are free to use all, some or none of them.

Fallback behavior by clients (specifically, when to restart negotiation 
with a lower version number that the original) is specific to each 
browser and the assumptions it makes on clients, servers and 
middleboxes. And if by fallback we mean "advise the user to only enable 
TLS 1.2 on their browser, and forbid TLS 1.0+1.1", I don't think any sys 
admin will accept such a recommendation in the near-to-middle term.

Re: curves, I agree to your reasoning. Maybe we should drop the 
Brainpool recommendation and wait for something better to appear.

Re: constant time implementation, this is not something that a deployer 
can do anything with. If I'm using Apache with mod_ssl or mod_gnutls, I 
have absolutely no idea which if any of their ciphers are implemented in 
constant time. So none of this belongs in the BCP. OTOH *we* should use 
our familiarity with existing implementations when making our 
recommendations.

RC4: bashing RC4 is good fun... But if the "fallback" when we drop RC4 
from the list is for the connection to fail, and maybe manually 
restarted with no TLS at all, is this really better than keeping RC4 on 
the list? I can accept this is so for Export cipher suites (which, mind 
you, still appear by default on some server lists), but I'm less sure 
about RC4.

As a side note, much of the recent discussion (ECDSA, SafeCurves) is 
very future looking, and so has nothing to do with the BCP, and actually 
belongs on either the TLS or CFRG mailing lists.

Thanks,
	Yaron

---

From: Ivan Ristic <[email-masked]>
Date: Fri, 03 Jan 2014 13:33:09 +0000

On 03/01/2014 13:03, Alyssa Rowan wrote:
>
> ...
>
> The bigger challenge is likely to be some of the more obscure clients
> (and of course Java, with its ever-helpful 1024-bit cap on DHE).

Speaking of Java, that restriction is likely to go away in Java 8, due 
for release in March. Further, Java 7 supports ECDHE suites, which means 
that a properly configured server should never need to negotiate DHE 
suites with a Java 7 client.

Java 6 clients do remain a potential issue for DHE > 1024. But, Apache 
2.4.7 has already adopted DHE of min. 2048 bits, so I think that battle 
has been won.

-- 
Ivan

---

From: Watson Ladd <[email-masked]>
Date: Fri, 3 Jan 2014 08:39:57 -0500

On Fri, Jan 3, 2014 at 8:12 AM, Yaron Sheffer <[email-masked]> wrote:
> Hi Alyssa,
>
> I just got around to reading the recent flurry of emails on this list, sorry
> for the delay.
>
> I 100% agree with your characterization of the goals of the BCP, below. And
> the following should be taken with that in mind.
>
> Fallback behavior by clients (specifically, when to restart negotiation with
> a lower version number that the original) is specific to each browser and
> the assumptions it makes on clients, servers and middleboxes. And if by
> fallback we mean "advise the user to only enable TLS 1.2 on their browser,
> and forbid TLS 1.0+1.1", I don't think any sys admin will accept such a
> recommendation in the near-to-middle term.
>
> Re: curves, I agree to your reasoning. Maybe we should drop the Brainpool
> recommendation and wait for something better to appear.
>
> Re: constant time implementation, this is not something that a deployer can
> do anything with. If I'm using Apache with mod_ssl or mod_gnutls, I have
> absolutely no idea which if any of their ciphers are implemented in constant
> time. So none of this belongs in the BCP. OTOH *we* should use our
> familiarity with existing implementations when making our recommendations.

Learn! If you are a sysadmin, RTFM. The short answer is that P256 is
constant time,
and RSA is blinded. If you don't think they should have to worry about
this, than you shouldn't
have given them the option in the first place. The BCP is not just for
deployers, but
also developers. They should know this already, but for some reason don't.
 Anyway, I think the bottom line recommendation of this draft is good.
The question I have is how many servers is this just a configuration
change for, and how many
will need new code/deployment? That's fundamentally going to make or
break adoption here.

>
> RC4: bashing RC4 is good fun... But if the "fallback" when we drop RC4 from
> the list is for the connection to fail, and maybe manually restarted with no
> TLS at all, is this really better than keeping RC4 on the list? I can accept
> this is so for Export cipher suites (which, mind you, still appear by
> default on some server lists), but I'm less sure about RC4.

This is 100% unclear. I've heard a lot about RC4 only implementations, but
no one has given me an example. The IE6 one I've said we should throw to
the wolves: TLS_3DES_EDE_HMAC works if in constant time, and given that in
April it is EOL, either microsoft patches it, or we can feel fine
being mean to them.

Also, the little lock has to mean something. If there isn't one, I
don't type my credit
card number in. If there is one, I used to assume it was safe. I don't
think that weak crypto
is better than no crypto: one can always avoid no crypto, but weak
crypto is hidden and
bites.

>
> As a side note, much of the recent discussion (ECDSA, SafeCurves) is very
> future looking, and so has nothing to do with the BCP, and actually belongs
> on either the TLS or CFRG mailing lists.

I think TLS: we all know ECC on Safe Curve is nice.

Sincerely,
Watson