Subject: [TLS] Re-thinking OPTLS

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 21 Nov 2014 16:55:31 -0500

>From information I received regarding the meeting in Honolulu (which I did
not
attend and whose minutes are still unpublished) I gather that there was not
enough support to continue consideration of the OPTLS proposal. This lack of
support was based on three objections:

- It is a "last minute" proposal that will delay the publication of TLS 1.3.

- The "delegation" issue: An attacker that can gain access to the server's
  signing box, without necessarily learning the signing key, can obtain a
  signature on a static DH key and use it to impersonate the server.

- The performance advantage of OPTLS relative to RSA signing is diminished
  when comparing to (current) TLS 1.3 with ECDSA signatures.

I think these are important points but I feel that they were not given
proper
consideration, in particular, since there was not enough time to digest the
proposal before the Honolulu meeting. I believe that OPTLS offers
significant
security and functional advantages over the current TLS 1.3 proposal and
should not be dismissed without a more focused discussion.  This is
particularly so if we can clear the issue of delegation that was the main
trigger to the change of sentiment on OPTLS from positive to "hesitating".

In this note, I will address the three issues. The arguments are incomplete
in
the interest of not making this long email even longer. I will be happy to
hear your feedback and expand on any issues that need further
clarifications.

*** The "last minute" objection ***

This proposal is indeed coming at a late point in the process of specifying
TLS 1.3. However, we are planning for a protocol that we hope will serve us
for many years; a possible delay of a few weeks should not be a determining
consideration. We must approach the design of TLS 1.3 with a
*forward-looking*
approach that considers evolving crypto technology, addresses a set of core
requirements and leaves some flexibility for future functionality.
TLS history shows that the protocol should be based on sound cryptographic
design requiring as little crypto machinery as possible, and providing a
consistent logic for the different modes of the protocol. OPTLS is rooted in
this approach, building fully on a single underlying mechanism -
Diffie-Hellman for both forward secrecy and authentication - and extending
naturally to other authentication settings such as 0-RTT, pre-shared key and
session resumption. Many of the benefits of OPTLS have been discussed in the
original thread in this list and will not be reiterated here in detail.
Please refer to these messages for more background:

https://www.ietf.org/mail-archive/web/tls/current/msg14385.html
https://www.ietf.org/mail-archive/web/tls/current/msg14592.html
https://www.ietf.org/mail-archive/web/tls/current/msg14601.html

*** The delegation issue ***

I would now like to address the very valid concerns with using the server's
existing signature key to sign static DH keys (a signature I refer to as a
"subcert"). This has been the only technical objection to the protocol
raised
in this list and therefore I see its resolution as a necessary (and
hopefully
sufficient) condition for the adoption of the protocol. For some previous
discussion on this issue see above cited messages, particularly the last
one.
Essentially, the problem is that the server's signature key becomes a
"certifying key" for static DH keys and therefore its unauthorized usage can
lead to adversarially-chosen static DH keys that allow the attacker to fully
impersonate the server. This is not worse than an attacker stealing the
signature key and using it to impersonate the server in current TLS.
However, in the non-typical, but possible, scenario where an attacker can
gain
access to the signing functionality as a black-box (i.e., without learning
the
signing key) and obtain a signature on a message of its choice, this becomes
a serious vulnerability. A particularly "ugly" case is that of a server that
hasn't even upgraded to TLS 1.3 but that can be impersonated as a TLS 1.3
server if the attacker gets a signature of the server on a static DH key of
the attacker's choice.

One clean solution to the problem is to equip servers with new certificates
that indicate use of the certified key for TLS 1.3. These can be either ECDH
certificates or signature certificates (RSA, ECDSA or your favorite
signature
algorithm). In the case of ECDH certificates, no subcert or any form of
signature is needed to run OPTLS. If the server's certificate is for a
signing
key then the server needs to send to the client a subcert with a signature
on
its static DH key. However, in this case, the certified key will only be
used
to sign subcerts - never as an online signature, hence can be afforded
better
protection. Indeed, the key can be stored offline and used only when new
subcerts (for new static DH keys) are needed, or it can be protected even
better by using it to to produce multiple subcerts (for multiple validity
periods and/or multiple EC groups) and then be destroyed. For those who
still
feel this is not secure enough, the choice is simple: Use ECDH certificates
and avoid the whole delegation issue. Note that ECDH certificates would be
the
simplest way of supporting a protocol like OPTLS. There is, however, one
issue
with ECDH certificates, namely, a server will need multiple certificates to
support different groups. This is where server-signed subcerts are
convenient.
Note, however, that this is an advantage only when using RSA signatures.
When the signature is ECDSA, we are back to the problem of requiring
multiple
ECDSA certificates for multiple groups. In this case, there seems to be no
advantage on having signature certificates. Fortunately, OPTLS can work with
any of these certificate types, leaving these choices to individual servers
and accommodating any future (possibly unforeseeable) preferences.

The bottom line is that the potential delegation vulnerabilities are
addressed
by servers obtaining new certificates for use with TLS 1.3. However, what
about a server that is interested to upgrade to 1.3 (e.g. for providing PFS)
but wants to keep using his TLS 1.2 signature key also with 1.3?
For this case, I proposed (see third message above) a small tweak to the
original OPTLS in which the server signs the static DH key together with the
client's nonce, hence preventing any form of delegation attack. This forgoes
the performance advantage of OPTLS relative to current TLS 1.3, but it
facilitates a transition period until a server acquires a new certificate
for
use in TLS 1.3. The nice thing about this tweak is that the only change in
the
protocol's spec is replacing the validity period in the subcert with the
client's nonce.  *Everything* else in the protocol stays the same; in
particular, it preserves all of the non-performance OPTLS advantages
(including optional 0-RTT support at no extra cost and a single logic for
all
the protocol modes). It also presents a real incentive for servers to
upgrade
to TLS 1.3 (and TLS 1.3 certificates) as it saves the cost of RSA decryption
in each session. As we know, performance gains are a better motivator than
just added security.

*** OPTLS vs ECDSA ***

The argument was made that when people will start running TLS 1.3 (as
currently specified) with ECDSA, the dramatic performance advantage of OPTLS
relative to RSA signatures will diminish. That is true. But the OPTLS
advantages are well beyond performance. In particular, as said above, OPTLS
uses a single cryptographic mechanism, Diffie-Hellman, for all its
functionality and does not depend on signatures (except for certification).
Current TLS 1.3 depends on both DH and signatures, hence reducing its
security
to the weaker of the two.  In addition, 0-RTT cannot be supported with a
server's signature key and it requires adding a static DH key (or other PK
encryption keys) to the server's public keys. Hence the signature is
duplicating a functionality that can be provided by the static DH key only
(as
OPTLS does). There are also specific problematic aspects with ECDSA. For
one,
there is the issue of supporting multiple groups, hence necessitating
multiple
certificates (for the same "price", one can run OPTLS with ECDH
certificates,
avoiding signatures, subcerts, and their associated complexities and costs,
including bandwidth).  ECDSA requires deployment at servers and clients (in
addition to ECDH that's needed for forward secrecy anyway), and presents
non-trivial implementation issues for performance and to resist side-channel
attacks (these implementation  problems are specific to ECDSA signing and do
not apply to ECDSA verification as may be needed for verifying
certificates).
OPTLS avoids these obstacles by solely building on the necessary and
simpler-to-implement ECDH mechanism. Finally, ECDSA is vulnerable to the
full
compromise of the signing key upon the leakage of a single ephemeral
quantity.
OPTLS does not suffer of this problem and actually increases security over
the
ephemeral DH key computed in TLS 1.3 by feeding g^{xs} into the KDF that
produces application keys.

I respectfully ask for the re-consideration of OPTLS by the WG as a possible
enhancement of TLS 1.3 design.

Thanks,

Hugo

---

From: Martin Thomson <[email-masked]>
Date: Fri, 21 Nov 2014 15:24:57 -1000

> - It is a "last minute" proposal that will delay the publication of TLS 1.3.

I don't think that this is at all the concern.  Far from it.  Not only
did this not come up to my recollection, my impression that the
participants in the conversation were seriously considering the
proposal without regard to this particular cost.

The most trite argument leveled against your proposal was the
complexity one, but even that was recognized as being manageable.

---

From: Hugo Krawczyk <[email-masked]>
Date: Sat, 22 Nov 2014 00:29:30 -0500

> proposal without regard to this particular cost.

​I'm glad to hear that the "last minute" objection that was communicated to
me is not a real concern and that people are willing to seriously consider
the proposal.
​

> complexity one, but even that was recognized as being manageable.

​I am glad to hear this too. Please let me know what the sources of
perceived complexity are.
I might have addressed some of these in my recent posts, particularly the
issue of delegation and certificates, but there is probably more to be
cleared.
In particular, I am not expert in the realities of the certification world
- I do hope these realities will not mean a show stopper for the proposal.
After all, the same certification issues will arise with any protocol that
uses ECDH or ECDSA keys. Such protocol will either need per-group
certificates or will have to accommodate some form of "delegation" (what I
call subcerts) for signing keys in different groups.
 ​

​Another possible source of ​perceived complexity is the support of 0-RTT
as part of the protocol. Note, however, that while this feature is built-in
into the protocol, its use is optional and it has no extra cost for those
who do not use it. Its inclusion is simple to specify and it may avoid the
need for a future revision/extension of the protocol.

Hugo

---

From: Martin Thomson <[email-masked]>
Date: Fri, 21 Nov 2014 20:14:55 -1000

On 21 November 2014 19:29, Hugo Krawczyk <[email-masked]> wrote:
> I am glad to hear this too. Please let me know what the sources of perceived
> complexity are.

The only items of note were:
 - the second update to the handshake protection under g^{xs}+g^{xy}.
We all realized that this was trivially addressed (ekr had a slide at
the meeting that showed an easy simplification, which should be in the
meeting materials).
 - the delegation scheme itself

I don't think that you can underestimate the costs involved with
creating an external dependency of any sort - for any project. The
reliance on PKIX updates could be problematic.  That said, I'm not
entirely sure that this is as straightforward a win as you suggest.
If such a flag existed, using it would create the delegation problem
we were most concerned about.

I'll let others explain more of the thinking behind the delegation
problem.  I think that it's the only real issue with your proposal
that you need to worry about.  The performance characteristics are
probably manageable.

---

From: Watson Ladd <[email-masked]>
Date: Fri, 21 Nov 2014 23:23:35 -0800

> the meeting that showed an easy simplification, which should be in the

Both variants were in fact in Hugo's email. However, if you have
computed [xy]g, there are no savings from computing
[xy]g+[xs]g vs [xs]g. I'm not sure the "variant of Hugo's proposal" in
the slides is worthwhile at all: the original reason to use
[xy]g+[xs]g was for a 1-RTT round trip with forward secrecy, and it
was mentioned that this would require other changes.

In fact the scheme presented on the slides as a "variant" is insecure,
in addition to having no efficiency gains. Did anyone catch the
mistake?

(For the correct variants, as well as description of the attack on
this variant see
https://www.infsec.cs.uni-saarland.de/~mohammadi/paper/owake.pdf,
following http://cacr.uwaterloo.ca/techreports/2011/cacr2011-11.pdf)

> we were most concerned about.

I understood the delegation problem as one concerned with the
following scenario: someone owns a box with an HSM attached, signs a
delegation, uses it surreptitiously. So long as TLS 1.3 could work for
a cert issues not for it, this was a problem: certain security
guarantees would be broken.

But if TLS 1.3 is opt-in how is this a problem? The HSM could execute
the ECDH related operations itself, and return only the keys, and a
server requiring this level of security without such an HSM could
continue using TLS 1.2. Or is the issue one that any protocol not
requiring online signatures would run into?

Moreover, even if people don't want delegation, OTLS is still a good
idea. Many of the areas like client authentication and 0-RTT that are
labeled "very sketchy" or "TODO" in the EKR draft are solved by OTLS.
As far as I know, we've not had anyone look at the TLS 1.3 draft and
say they could prove it secure. That said, with renegotiation dead, it
should be a lot easier. But I'm not an expert in this area: it may be
the current draft is comparable to OPTLS in terms of provability.

> that you need to worry about.  The performance characteristics are

Not requiring online signatures is a win for performance for users
with RSA certificates. The current draft has very similar performance.

Sincerely,
Watson

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

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: "Salz, Rich" <[email-masked]>
Date: Sat, 22 Nov 2014 11:54:40 -0500

> I don't think that this is at all the concern.

Some of us have this concern, and discussed it off-list with WG "management" who didn't disagree.

But if the consensus is that this is not an issue, then not only am I okay with it, I think that this is very good news.

---

From: Adam Langley <[email-masked]>
Date: Sat, 22 Nov 2014 09:19:04 -0800

> with RSA certificates. The current draft has very similar performance.

There is at least one data-point when it comes to "delegation"
signatures: it's what QUIC does[1] (with its own message format and
embedded expiry) and Google is perfectly happy with deploying QUIC.

[1] https://docs.google.com/document/d/1g5nIXAIkN_Y-7XJW5K45IblHd_L2f5LTaDUDwvZ5L6g/edit#heading=h.bzxklo2i5w6k

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Hugo Krawczyk <[email-masked]>
Date: Sat, 22 Nov 2014 18:03:40 -0500

Martin, one does not have to resort to delegation for using OPTLS, you can
use
ECDH certificates, except that you may need a certificate for each group you
support. The *same* goes for using ECDSA in current TLS. That is, if you
want
to be able to sign in TLS with different groups (I think this will be
needed),
then you need one certificate for each group that you want to support or
else
you need delegation (for signing subcerts for mutliple ECDSA keys).

Let me parse all the options we have.

If you don't want delegation you have three options: RSA certificates (and
pay
for per-session RSA signing performance cost), per-group ECDSA certificate
(requiring per-session signature), or per-group ECDH certificates (requires
no
signing at all and no delegation). All other cases require delegation.

So, if you don't care about per-session RSA cost AND do not care about the
added value/functionality of OPTLS, then you can keep current TLS 1.3.

Otherwise, you are left with essentially two choices.

- If you are willing to live with multiple certificates, one per-group, then
  run OPTLS with ECDH certificates: It gives the best
  security-functionality-performance return (and no delegation).

- If you don't want per-group certificates then you must resort to
delegation
  (this is the case whether you use current TLS 1.3 with ECDSA or use
OPTLS).
  But if you are going to live with delegation then there is no advantage
to
  TLS 1.3 over OPTLS.

The interesting thing about OPTLS (with the optional online signature tweak)
is that it can accommodate all of the above options in one compact protocol:

- you don't want delegation or per-group keys, use OPTLS with Online RSA
  signature (the subcert signs the client nonce)

- you don't want delegation but accept per-group keys, use OPTLS with ECDH
  certificates (no signatures, no subcert/delegation)

- you don't like the above options (hence forced to live with delegation),
  use OPTLS with offline-signed subcerts for ECDH keys.

The above, I think, is nice and provides a strong justification for OPTLS.
However, if you want the protocol to support delegation and are concerned
about the
"HSM attacks" discussed here, then you need to require servers to obtain new
certificates (ECDH, ECDSA or RSA). The point is that you don't want servers
to
use their TLS 1.2 (or earlier) keys to also sign subcerts.

​Hugo​

PS: ​I will answer the issue of key derivation separately.​

---

From: Hugo Krawczyk <[email-masked]>
Date: Sat, 22 Nov 2014 18:09:17 -0500

See below on the issue of key derivation

On Sat, Nov 22, 2014 at 1:14 AM, Martin Thomson <[email-masked]>
wrote:

> ​​

​I haven't seen these slides and didn't know about them.
The derivation of keys based on g^{xs} and g^{xy} does NOT use a sum or any
other algebraic combination (although some combinations are secure, most are
not, and identifying the good ones is non-trivial). Anyway, I have left the
details of key derivation unspecified, not because they are not important
for
security (they are!), but because optimizing the derivation depends on the
functionality and properties one wants from the protocol and I wanted to
learn
more about them from these discussions. For the moment just think that a key
derived from the above two quantities will be computed by hashing the two
values
together (with some additional information) and we will model the hash as a
random
oracle in the cryptographic analysis. The actual derivation will be a bit
more
involved for the sake of better provability but not significantly different
from an implementation point of view.

Hugo
​

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 22 Nov 2014 15:29:28 -0800

On Sat, Nov 22, 2014 at 3:09 PM, Hugo Krawczyk <[email-masked]>
wrote:

> not, and identifying the good ones is non-trivial).
>

Note, I didn't intend addition (and I suspect Martin didn't either). I was
just using
'+' as shorthand for "both" and being vague about the details of the
key derivation (as you suggest below). Sorry about the confusion.

-Ekr

---

From: Hugo Krawczyk <[email-masked]>
Date: Sat, 22 Nov 2014 20:02:35 -0500

I thought that was what you meant but at least Watson seemed to be
interpreting in the arithmetic sense and he was right to point out that it
would be insecure to do so.

On Sat, Nov 22, 2014 at 6:29 PM, Eric Rescorla <[email-masked]> wrote:

>> On Sat, Nov 22, 2014 at 1:14 AM, Martin Thomson <[email-masked]
>> > wrote:
>>

---

From: Nico Williams <[email-masked]>
Date: Mon, 24 Nov 2014 00:33:06 -0600

I'm in favor of using static server (EC)DH keys for server
authentication and possible 0-RTT, particularly in connection
with DANE.

I *don't* think that OPTLS is worthwhile without connection to DANE, but
only because OPTLS is just an optimization with roughly the same
applicability as an existing optimization that is much faster: session
resumption [with encrypted session state tickets].

But since I think sprinkling DANE on is the obvious thing to do given
OPTLS as part of the protocol, I'm in favor.

Security-wise the use of static (EC)DH keys is well-understood (as well
understood as (EC)DH is in general).

The g^xs plus (not the arithmetic operator) g^xy method of obtaining PFS
is also OK, and heck, if need be the client could use two different x's,
and the protocol ought to allow it (not least because the client might
want to use different groups/ curves for PFS key agreement than for
authentication key agreement).

Nico
--

---

From: Hugo Krawczyk <[email-masked]>
Date: Mon, 24 Nov 2014 19:03:34 -0500

On Sat, Nov 22, 2014 at 12:19 PM, Adam Langley <[email-masked]>
wrote:

> [1]
> https://docs.google.com/document/d/1g5nIXAIkN_Y-7XJW5K45IblHd_L2f5LTaDUDwvZ5L6g/edit#heading=h.bzxklo2i5w6k
>
>
>
​QUIC was indeed a main motivation to build 0-RTT into OPTLS.
I am glad to hear that the "delegation" approach works for you.

​

---

From: Hugo Krawczyk <[email-masked]>
Date: Mon, 24 Nov 2014 19:06:18 -0500

> resumption [with encrypted session state tickets].

​Session resumption is indeed faster if you don't do PFS - otherwise it is
still faster but not by much.
And of course, as I'm sure you agree, there are 0-RTT scenarios that cannot
be  reduced to session resumption as in the QUIC case mentioned by AGL or
any setting where keeping a shared secret state at the client is not
practical.

Hugo
​

---

From: Nico Williams <[email-masked]>
Date: Mon, 24 Nov 2014 21:49:17 -0600

On Mon, Nov 24, 2014 at 07:06:18PM -0500, Hugo Krawczyk wrote:
> Session resumption is indeed faster if you don't do PFS - otherwise it is

If one wants half-PFS (foward security relative only to client
compromise) including for 0-RTT data then OPTLS wins every time.

> any setting where keeping a shared secret state at the client is not

Hmm, a client that can't keep a shared secret around probably can't keep
a server sub-cert either...  Nor reuse its ECDH keys (which the QUIC doc
linked by AGL talks about in conjunction with caches of shared keys,
which then is a lot like resumption).  A client that can't keep state
could use DANE though, and thus get 0-RTT with half-PFS every time.

Of course, it's all about relative numbers: how long a client is willing
to go without using new keys for PFS (relative to client compromise),
how frequently it connects to the same server, and how long the server
is willing to go without using new keys for PFS (relative to server
compromise).  That the client is more sensitive about PFS than the
server makes some sense.

(Shouldn't we really speak of PFS relative to compromise of each peer?
After all, they can't really prove that the other peer isn't reusing
PKs, not spending without extra effort monitoring for reuse.)

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Tue, 25 Nov 2014 19:51:36 -0600

On Wed, Nov 26, 2014 at 12:54:07AM +0100, Hoeteck Wee wrote:
> > a server sub-cert either...
> 
> I don't think that is correct. If an adversary learns the shared
> secret held by the client in resumption, then the session gets
> compromised and the adversary can decrypt all of the data that gets
> sent later. If an adversary learns the server sub-cert g^s held by the
> client, no security is lost.

That is quite true, and I conceded that clients can have different
tolerance for sub-cert freshness than resumption state lifetime,
but I thought the meaning of "can't" wasn't "because of policy" but
"because of lack of storage".

---

From: Hoeteck Wee <[email-masked]>
Date: Wed, 26 Nov 2014 00:54:07 +0100

A sub-cert g^s is essentially like a public key in a public-key
encryption scheme, whereas the shared secret in resumption is like a
secret key in a secret-key encryption scheme. Learning the public key
in public-key encryption does not compromise the security of the
encryption scheme; learning the secret key in a secret-key encryption
scheme does.

Hoeteck