Subject: [TLS] Channel ID and server load: comment on draft-balfanz-tls-channelid-00

From: Watson Ladd <[email-masked]>
Date: Mon, 21 Oct 2013 18:11:13 -0700

Channel ID requires 2 modular exponentiations every handshake on the
server, even when sessions are resumed. The claimed argument for this
necessity is that resumption tickets could get stolen from the client.
Why could Channel ID identifiers not get stolen when the resumption
tickets are? Is there a reasonable threat model in which a client so
compromised as to lose resumption tickets has a meaningful benefit
from Channel ID?

Why P256 and ECDSA? These choices prevent batch verification on the
server, increasing the workload significantly. They do not have major
security advantages, or performance advantages over Ed25519.

When browsers implement Channel ID, what separations between different
websites are required? Cross-site request forgery has long been the
bane of web authentication technologies: does Channel ID provide
additional benefits here?
Sincerely,
Watson Ladd

---

From: Adam Langley <[email-masked]>
Date: Tue, 22 Oct 2013 11:14:27 -0400

> compromised as to lose resumption tickets has a meaningful benefit

Because ChannelIDs have a public and private part, the private part
can be much better protected. For example, by moving it out of the
browser process completely, even on standard machines, and even under
hardware-protection, where such capability exists.

> security advantages, or performance advantages over Ed25519.

Why can't one batch verify ECDSA signatures?

The major issue with batch verification is latency: in order to build
a batch one has to wait for enough ChannelID connections (64 for the
batch speeds advertised for Ed25519) to be in the handshake stage. But
for HTTPS, latency is very important and we can't delay connections
for that long in normal processing.

That's not to say that batch processing is useless in all situations,
but it not always applicable.

The goal of wanting to put the private key into hardware protection
also motivated the choice of signing primitive since we get what we're
given with hardware. I did come close to adding signature primitive
negotiation to ChannelID recently but, due to bugs in old F5
firmwares, we cannot currently afford any extra bytes in the
ClientHello until we have workarounds in place. It may still appear in
the future.

> additional benefits here?

Dirk deals with the higher levels of the stack, so I'll pass on that question.

Cheers

AGL

---

From: Watson Ladd <[email-masked]>
Date: Tue, 22 Oct 2013 10:52:11 -0700

> hardware-protection, where such capability exists.
Completely spurious: hardware (or a separate process) does not know
whether it is being asked to provide
the ChannelID for a request that is genuine or one that the attacker
provided after subverting the browser process.
There also is a replay attack: a signature of a static string provides
no liveness, contrary to assumptions made here.
As a result disclosure of a ChannelID for a web server provides the
ability to falsely authenticate a connection.
> Why can't one batch verify ECDSA signatures?
Because of a stupid missing bit, you don't know which of two points
lead to the r value. If you did know this bit, you could
make the verification equation an identity in the curve and apply the
Bos-Coster trick Ed25519 does. I've not come up with
a way around this issue. Guess and check isn't worth it: it ends up
costing more than verifying one at a time.
> but it not always applicable.
Fair enough: I assume P256 is performant enough for the applications
being imagined, but given
the constant kvetching about performance, I'm not sure everyone shares
that. (Then again, they
kvetch while using interpreted languages...)

The argument for batch signatures to reduce latency is as follows: so
long as connections are coming in at a rate slow enough for us to deal
with them, all is good. But when connections come in faster than we
can process, we can grind through the queue faster.

I personally think TLS 1.3 should use a client key and server key to
derive a forward-secure channel, and then carry out whatever proofs or
verifications (certificate presentations, etc) are required within it.
Done right this can be fast in latency and CPU terms. Done wrong we
have what we have now.
> ClientHello until we have workarounds in place. It may still appear in
Options have burned us in the past: there was a recent email
describing a case of deployments with incompatible cipher suites
leading
to interesting results.

Sincerely,
Watson Ladd

---

From: Trevor Perrin <[email-masked]>
Date: Tue, 22 Oct 2013 11:32:48 -0700

> no liveness, contrary to assumptions made here.

Hi Watson,

I think you're misreading the draft: ChannelID signs hashes of
handshake messages, not a "static string".

I do think ChannelID needs to explain the value of storing private
keys in a "secure element" further, and why storing ECDSA private keys
is better than, say, HMAC keys.

Trevor

---

From: Adam Langley <[email-masked]>
Date: Wed, 23 Oct 2013 11:21:03 -0400

> provided after subverting the browser process.

Certainly that's true. However, it limits the attacker to an online
attack: closing the laptop etc stops them. That's a lot better than
the current situation where cookie theft is a significant problem.

Additionally, ChannelID can be extended to an "ignition key" model
where connections need to reprove the presence of the ChannelID every
$n minutes. (That might get the verification load to the point where
batching is useful :)

> no liveness

ChannelID signs the handshake which includes an nonce from the server.

> costing more than verifying one at a time.

I have not looked into batching ECDSA verifies but [1] seems quite
clear that it's dealing with unmodified ECDSA signatures (paywalled
I'm afraid, but the first two pages are free). They report a speedup
of 2x for batches with multiple signers, which is roughly equal to the
reported speedup for Ed25519 (273K -> 134K cycles).

[1] http://rd.springer.com/chapter/10.1007%2F978-3-642-31410-0_1

> kvetch while using interpreted languages...)

I am not terribly happy with the performance implications of ChannelID
either, but we're still exploring our options.

Cheers

AGL

---

From: Adam Langley <[email-masked]>
Date: Wed, 23 Oct 2013 11:25:09 -0400

> is better than, say, HMAC keys.

I agree that HMAC would, of course, be much faster but I believe that
public/private is needed for some of the higher level capabilities:
http://www.browserauth.net/proof-key-federation-protocols

Cheers

AGL

---

From: Adam Langley <[email-masked]>
Date: Wed, 23 Oct 2013 14:15:59 -0400

> [1] http://rd.springer.com/chapter/10.1007%2F978-3-642-31410-0_1

It's been pointed out to me that the technique described in that paper
is broken in [2] (see section 2). So it may well be that ECDSA batch
verification is infeasible.

[2] http://cr.yp.to/badbatch/badbatch-20120919.pdf

Cheers

AGL

---

From: Trevor Perrin <[email-masked]>
Date: Wed, 23 Oct 2013 18:40:54 -0700

> http://www.browserauth.net/proof-key-federation-protocols

For binding cookies to a browser you could get by with symmetric
crypto.  There's proposals from websec on this (eg "Smart Cookies"
[1]).

For binding a token sent from an IdP to an RP, I wonder if there might
be a symmetric-key analogue to "Proof-key federation":

AIUI, the goals are:
 1) IdP receives some sort of proof that the same browser sharing
channel key Ki with the IdP is also sharing channel key Kr with some
RP.
 - IdP signs an assertion that is only useable by a browser with channel key Kr.

"Proof-key federation"/ChannelID achieves this by:
 1) A Javascript API where a browser signs cross-certificates between
the ECDSA keys Ki and Kr
 2) The IdP refers to Kr in its signed assertion

Imagine instead if Ki and Kr were HMAC "cookie keys" associated with
smart cookies between the (browser, IdP) and (browser, RP).  A
javascript API could be used to produce the triple:
  (nonce, HMAC(Ki, nonce), HMAC(Kr, nonce))

The triple would be forwarded to the IdP who would check HMAC(Ki,
nonce), then include the triple in the signed assertion.  The RP would
check HMAC(Kr, nonce).  The assertion is thus only usable to a browser
that know Kr, and is only issued to a browser that knows Ki.

Anyways, dunno if this is better than ChannelID or if I'm missing
something (probably).  But I'd like to see more analysis of why
public-key was chosen for ChannelID, in light of computation costs.

Trevor

[1] http://www.ietf.org/mail-archive/web/websec/current/msg01729.html

---

From: Watson Ladd <[email-masked]>
Date: Thu, 24 Oct 2013 12:52:30 -0700

> the current situation where cookie theft is a significant problem.
Nope: the attacker could provide their own ChannelID and force the
user to reauthenticate,
thus causing their secret key to be trusted.
They could disable ChannelID entirely and force fallback to cookies,
which they then steal.
Online attack cleans
out a bank account just as quickly as offline.

ChannelID provides a benefit only if the user interaction authorizing
access to the ID generator
can be secured from malware interference, in which case we could just
use a cookie there instead.
> $n minutes. (That might get the verification load to the point where
Steal a resumption ticket and you have the same attacker issue for $n minutes.
> ChannelID signs the handshake which includes an nonce from the server.
Yes, I stand corrected on this point.

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

---

From: Adam Langley <[email-masked]>
Date: Fri, 25 Oct 2013 10:59:44 -0400

> They could disable ChannelID entirely and force fallback to cookies,

Likewise, someone could undermine the confidentiality of TLS by
failing to set the secure flag on a cookie.

Just because you could design a system that uses ChannelID and has
these drawbacks isn't terribly meaningful.

> out a bank account just as quickly as offline.

That is rarely true in my experience. Rate limiting of transfers seems
to be common practice.

> Steal a resumption ticket and you have the same attacker issue for $n minutes.

Session resumption tickets do not carry the authority of the
ChannelID. The (hypothetical) reauthorisation idea prevented an
attacker from taking over a connection, perhaps because the computer
continues to run even though the user has stepped away.

Cheers

AGL

---

From: Adam Langley <[email-masked]>
Date: Fri, 25 Oct 2013 11:02:01 -0400

On Wed, Oct 23, 2013 at 9:40 PM, Trevor Perrin <[email-masked]> wrote:
> But I'd like to see more analysis of why

That sounds very reasonable, but I fear that I only have insight into
a small part of the design here and can't usefully talk on this point.
I'll see if I can pin Dirk down on it.

Cheers

AGL