Subject: [TLS] TLS Client Puzzles

From: Erik Nygren <[email-masked]>
Date: Thu, 2 Jul 2015 17:40:20 -0400

Following a discussion last year in Denver, I've written up a proposal
for a TLS Client Puzzles extension.  It is specific to TLS 1.3 in that
it is constructed using the HelloRetryRequest request flow (although
it could be adapted to HelloVerifyRequest with prior versions of DTLS).

The puzzles here are placeholders meant as a starting-point for discussion
(and also take in some feedback from discussions on this list last year)
and will likely evolve.

        Erik

---------- Forwarded message ----------
From: <[email-masked]>
Date: Thu, Jul 2, 2015 at 5:30 PM
Subject: New Version Notification for draft-nygren-tls-client-puzzles-00.txt
To: Erik Nygren <[email-masked]>

A new version of I-D, draft-nygren-tls-client-puzzles-00.txt
has been successfully submitted by Erik Nygren and posted to the
IETF repository.

Name:           draft-nygren-tls-client-puzzles
Revision:       00
Title:          TLS Client Puzzles Extension
Document date:  2015-07-02
Group:          Individual Submission
Pages:          12
URL:
https://www.ietf.org/internet-drafts/draft-nygren-tls-client-puzzles-00.txt
Status:
https://datatracker.ietf.org/doc/draft-nygren-tls-client-puzzles/
Htmlized:
https://tools.ietf.org/html/draft-nygren-tls-client-puzzles-00

Abstract:
   Client puzzles allow a TLS server to defend itself against asymmetric
   DDoS attacks.  In particular, it allows a server to request clients
   perform a selected amount of computation prior to the server
   performing expensive cryptographic operations.  This allows servers
   to employ a layered defense that represents an improvement over pure
   rate-limiting strategies.

   Client puzzles are implemented as an extension to TLS 1.3
   [I-D.ietf-tls-tls13] wherein a server can issue a HelloRetryRequest
   containing the puzzle as an extension.  The client must then resend
   its ClientHello with the puzzle results in the extension.

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

The IETF Secretariat

---

From: Yoav Nir <[email-masked]>
Date: Fri, 3 Jul 2015 01:23:43 +0300

Hi, Erik

You might be interested in the similar work we’re doing at IPsecME:
https://tools.ietf.org/html/draft-ietf-ipsecme-ddos-protection-01#section-3 <https://tools.ietf.org/html/draft-ietf-ipsecme-ddos-protection-01#section-3>

After discussing multiple puzzle schemes, we (for now) settled on a puzzle that uses a MAC function such as HMAC-SHA256.

The server sets the puzzle level to n and generates a calculable challenge (for TLS it could be random). The client finds a key k for the MAC function such the result of MAC(k,challenge) has at least n trailing zero bits.

The expected time to solve such a puzzle is 2^n invocations of the MAC function. There are two issues:
  1. The time it takes to find a key that works varies a lot. A puzzle that takes on average 1 second to solve could take an unlucky client half a minute.
  2. Clients are diverse. Mobile phones and embedded devices are far weaker than desktop computers. What’s hard enough for one machine is too hard for another.

We can solve #1 by increasing the number or required distinct solutions while reducing the number of zero bits:
http://www.ietf.org/mail-archive/web/ipsec/current/msg09844.html <http://www.ietf.org/mail-archive/web/ipsec/current/msg09844.html>

We don’t know how to solve #2.

Yoav

> On Jul 3, 2015, at 12:40 AM, Erik Nygren <[email-masked]> wrote:
> 
> From: <[email-masked] <mailto:[email-masked]>>
> To: Erik Nygren <[email-masked] <mailto:[email-masked]>>
> 
> 
> 
> URL:            https://www.ietf.org/internet-drafts/draft-nygren-tls-client-puzzles-00.txt <https://www.ietf.org/internet-drafts/draft-nygren-tls-client-puzzles-00.txt>
> Status:         https://datatracker.ietf.org/doc/draft-nygren-tls-client-puzzles/ <https://datatracker.ietf.org/doc/draft-nygren-tls-client-puzzles/>
> Htmlized:       https://tools.ietf.org/html/draft-nygren-tls-client-puzzles-00 <https://tools.ietf.org/html/draft-nygren-tls-client-puzzles-00>
> 
> 
> Abstract:
> until the htmlized version and diff are available at tools.ietf.org <http://tools.ietf.org/>.
> 
> The IETF Secretariat
> 
> 
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Erik Nygren <[email-masked]>
Date: Thu, 2 Jul 2015 18:33:52 -0400

Hi, Yoav.  Brandon Williams pointed that IPsecME doc out to me earlier today
and it's linked from later on in the draft.

I was proposing something very similar using a SHA256 or HMAC-SHA256 as a
starting point.
Based on discussion here last year, I let the puzzle level parameter be
specified directly
(rather than as an exponent) as that allows servers to scale difficulty
more linearly.
I believe that for this proposed puzzle, the average solution time should
be
half the worst-case time for a given client (but the best case could be
better).

Incorporating a puzzle with a memory-hard component (I give one poor example
where that component is symmetric) may be an option for mobile clients who
are more CPU constrained than memory-bandwidth constrained.  We have
some other ideas here we're still exploring.

Thanks, Erik

On Thu, Jul 2, 2015 at 6:23 PM, Yoav Nir <[email-masked]> wrote:

> https://tools.ietf.org/html/draft-ietf-ipsecme-ddos-protection-01#section-3
>
> After discussing multiple puzzle schemes, we (for now) settled on a puzzle
> that uses a MAC function such as HMAC-SHA256.
>
> The server sets the puzzle level to n and generates a calculable challenge
> (for TLS it could be random). The client finds a key k for the MAC function
> such the result of MAC(k,challenge) has at least n trailing zero bits.
>
>   1. The time it takes to find a key that works varies a lot. A puzzle
> that takes on average 1 second to solve could take an unlucky client half a
> minute.
>   2. Clients are diverse. Mobile phones and embedded devices are far
> weaker than desktop computers. What’s hard enough for one machine is too
> hard for another.
>
> http://www.ietf.org/mail-archive/web/ipsec/current/msg09844.html
>

---

From: Douglas Stebila <[email-masked]>
Date: Fri, 3 Jul 2015 07:04:31 +0000

My research group did some experimental work a few years ago involving client puzzles in TLS; some of the results might be of interest, though not all:  we focused on RSA key transport ciphersuites (rather than ECDHE) and also considered a new signature algorithm for client authentication based on a design of Bernstein.

In our modifications to TLS, the client advertised "PuzzlesSupported" in a ClientHello extension, and the server responded with a Puzzle in a ServerHello extension.  The client turned the solution in a new message coming in the same flight as the ClientKeyExchange.  Our design focused only on RSA key transport-based ciphersuites, so this was sufficient to save the server from doing computationally expensive cryptographic operations before checking the puzzle solution.

Our puzzle was based on SHA-1, and involved finding an input that when hashed started with at least 12 zeros.

We did some experiments to determine performance impact and benefit.  The ciphersuite was RSA key transport with server-only authentication, 1024-bit keys; AES-128 in CBC mode for bulk encryption and SHA-1 for the hash function.  In the face of legitimate requests, this verification procedure reduced the number of supported connections by 0.6%, from 1924 connections/second to 1911 connections/second.  In the face of a flood of garbage requests, the server could discard 5109 requests/second.

The paper can be found here:
	http://www.douglas.stebila.ca/research/papers/RSBG11
As I mentioned we were investigating another signature scheme as well, so those portions of the paper would not be relevant to this proposal.

Douglas

> On Jul 3, 2015, at 07:40, Erik Nygren <[email-masked]> wrote:
> 
> URL:            https://www.ietf.org/internet-drafts/draft-nygren-tls-client-puzzles-00.txt
> Status:         https://datatracker.ietf.org/doc/draft-nygren-tls-client-puzzles/
> Htmlized:       https://tools.ietf.org/html/draft-nygren-tls-client-puzzles-00
> 
> 
> Abstract:

---

From: Jeffrey Walton <[email-masked]>
Date: Fri, 3 Jul 2015 18:26:29 -0400

Hi Douglas,

> My research group did some experimental work a few years ago involving client puzzles in TLS; some of the results might be of interest, though not all:  we focused on RSA key transport ciphersuites…

Are you aware of any papers or results that callout puzzles as a
successful remediation to DoS and DDoS? (Vanilla TCP and SSL/TLS would
both be useful).

Jeff

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 6 Jul 2015 18:51:11 -0700

On Thu, Jul 2, 2015 at 2:40 PM, Erik Nygren <[email-masked]> wrote:

> for a TLS Client Puzzles extension.
>

I'm sorry, but I think this is the wrong approach.

I assume you're trying to solve the asymmetrical computation requirements
of RSA, a.k.a. the "THC DoS attack"

If you're using RSA for key exchange, don't. It's very broken in more ways
than DoS.
If you're using RSA for signatures, it should be deprecated and phased out.

Trying to solve the latter problem by complecting TLS is likewise something
I oppose.

Moving to ECC-based signatures (ECDSA or EdDSA or
CFRG-yet-to-be-standardized-signatures) would obviate this problem without
complecting the TLS protocol. ECC punts the computational burden to the
client, elegantly solving this problem by using the algorithms we want to
move to anyway.

Complexity is the enemy of security.

I prefer simplicity. To solve this same problem, I would prefer RSA
diediedie. I know that's a stretch, but I would prefer TLS gravitate
towards simple solutions than adding complex band-aids.

-- 
Tony Arcieri

---

From: Erik Nygren <[email-masked]>
Date: Mon, 6 Jul 2015 22:39:44 -0400

Sadly, even the ECDSA schemes and ECDHE key exchange still require the
server
to do significant work without the client needing to do any work.  For
example on a
sample modern processor (per core):

- RSA 2048 signs       = 1,070 per second
- ECDSA P-256 signs = 10,515 per second
- ECDHE P-256 ops    = 6,070 per second
- SHA-256 of 64 byte blocks = 2,136,484 per second

So even if you can ditch RSA signatures and do one ECDSA signature
and one ECDHE op for key exchange, you're doing 3848 per core (so 3.8x over
RSA
which is a big boost, but not orders of magnitude of improvement).
This helps a bunch, but there's no need for a client to do any work to get
you to do that work.

With a client puzzle and when under attack, you do some small number of
SHA-256 ops
and then the client will have to do some amount of work of your choosing.
For example, giving the client ~500 SHA-256 rounds to do before you do an
ECDSA
signature will put the server at-parity with the client with respect to
amount of crypto work.

I'm all for simple solutions here, which is part of why anything here would
ideally
share as much in common with what's needed for DTLS cookies as well as use
crypto routines already in-use in TLS as much as possible...

         Erik

On Mon, Jul 6, 2015 at 9:51 PM, Tony Arcieri <[email-masked]> wrote:

> Trying to solve the latter problem by complecting TLS is likewise
> something I oppose.
>

---

From: Watson Ladd <[email-masked]>
Date: Mon, 6 Jul 2015 20:16:03 -0700

> - SHA-256 of 64 byte blocks = 2,136,484 per second

These numbers are far below what faster cryptography can deliver: I
have nearly a million gls254 computations per second, and 50,000 key
agreements per second on a kummer surface. Changing TLS to not require
online signing would realize this degree of performance.

At these rates you saturate gigabit ethernet connections, which
puzzles will not help with. In fact, they will make the problem worse.

> crypto routines already in-use in TLS as much as possible...

What about improving performance? That avoids any protocol changes,
and brings about the benefits you seem to want.

>> diediedie. I know that's a stretch, but I would prefer TLS gravitate towards
>> simple solutions than adding complex band-aids.
>>
>> --
>> Tony Arcieri
>
>
>

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Brian Sniffen <[email-masked]>
Date: Tue, 7 Jul 2015 11:18:10 -0400

> puzzles will not help with. In fact, they will make the problem worse.

It's now normal to deploy one 10GbE NIC per CPU.  CPU load is definitely
still the bottleneck.

> and brings about the benefits you seem to want.

By all means!  But it'll take 10-20 years to get those performance
benefits out to the ends of the Earth.  I hope we can have some
conversations using that technology in 2-5 years, but we should expect
to be supporting RSA-2048 at least through 2025 (or a few years after
it's discovered to be broken), and NIST curves through 2030.

I'm not happy (or sad) about those dates, but if we think we're going to
go faster than final death of SSLv2, MD5, and similar, we should be able
to explain why that would be.

-Brian

---

From: Watson Ladd <[email-masked]>
Date: Wed, 8 Jul 2015 20:25:05 -0700

> It's now normal to deploy one 10GbE NIC per CPU.  CPU load is definitely

There is still going to be a bottleneck somewhere. The only question is can
you serve more clients than an attacker can muster: plenty of zombies can
solve puzzles.

> it's discovered to be broken), and NIST curves through 2030.

Why is deploying puzzles more likely to happen then faster crypto?

---

From: Brian Sniffen <[email-masked]>
Date: Thu, 9 Jul 2015 12:38:45 -0400

> you serve more clients than an attacker can muster: plenty of zombies can

Not quite!  Under a sufficiently big attack, we'll have to take *some*
damage.  But we can use puzzles---in particular in combination with
resumption/PSK modes---to make some choices about where we take
that damage.  For example, mobile clients probably can't keep up with
puzzles---but desktop browsers ought to be able to succeed at puzzles
enough to justify asymmetric crypto once, then continue on.

> Why is deploying puzzles more likely to happen then faster crypto?

We get the benefit of puzzles when they hit the computationally powerful
systems; those are mostly desktop browsers with a tight deployment loop.
I don't think we get the benefit of faster crypto when they hit ~all the
clients, and we can reasonably turn off slow crypto.

I'd like both.

-Brian

---

From: Watson Ladd <[email-masked]>
Date: Thu, 9 Jul 2015 12:31:43 -0700

> enough to justify asymmetric crypto once, then continue on.

Let's assume you can handle X connections before dropping some. An attacker
who can muster the resources to take up X connections wins. It doesn't
matter which resource is limiting.

> clients, and we can reasonably turn off slow crypto.

So now when puzzles turn on you start dropping mobile clients instead of
randomly selected ones. Where is the win here?

---

From: Dave Garrett <[email-masked]>
Date: Thu, 9 Jul 2015 15:39:25 -0400

I'm personally not a fan of the idea of raw processing puzzles. Has anyone investigated network puzzles of some sort, like requiring clients to retrieve a key/signature from a 3rd party? For example: a DDoS vulnerable server requests clients first get some token signed by a trusted 3rd party capable of handling heavy load & filtering DDoSes better, then can use that signed token to connect to desired server.

Dave

---

From: Brian Sniffen <[email-masked]>
Date: Fri, 10 Jul 2015 12:52:17 -0400

>>> There is still going to be a bottleneck somewhere. The only question
>>> is can you serve more clients than an attacker can muster: plenty of
>>> zombies can solve puzzles.
>>
>> resumption/PSK modes---to make some choices about where we take that
>> damage. For example, mobile clients probably can't keep up with
> Let's assume you can handle X connections before dropping some. An
> attacker who can muster the resources to take up X connections wins.
> It doesn't matter which resource is limiting.

1:1?  I think the adversary-win threshold is much higher---more like 5X:

I think the steady state depends on the following rates:

Lp, New legitimate connections that show up for handshake per second,
Ln, Legitimate Connections that die off per second,
Rp, resumptions that show up per second per "open" legitimate connection
An, Adversary connections that show up per second,
X, Number of new handshakes that can be done per second,
R, Number of resumptions that can be done per second. >>X

If the number of new legitimate + adversary handshakes exceeds handshake
capacity, some handshakes will fail, in proportion to the ratio of
legitimate to adversary handshakes. If the elements of the adversary and
legitimate populations are identical, an adversary with An=Lp only takes
half the available capacity.  Users hit "retry," half of them make it
through, and over time the good people accumulate on the right side of
the asymmetric crypto barrier.

> So now when puzzles turn on you start dropping mobile clients instead
> of randomly selected ones. Where is the win here?

Predictability. Secondarily, the ability of clients (say, a proxy with a
lot of users behind it) to invest in being able to make it through a
pile-up.

-Brian

---

From: Martin Thomson <[email-masked]>
Date: Fri, 10 Jul 2015 09:57:56 -0700

On 9 July 2015 at 12:39, Dave Garrett <[email-masked]> wrote:
> I'm personally not a fan of the idea of raw processing puzzles. Has anyone investigated network puzzles of some sort, like requiring clients to retrieve a key/signature from a 3rd party?

Computational puzzles can be reduced to that.  If a mobile device
can't solve a (small) bitcoin puzzle, it can contact a server that
can.

---

From: Jeffrey Walton <[email-masked]>
Date: Fri, 10 Jul 2015 21:06:48 -0400

> can't solve a (small) bitcoin puzzle, it can contact a server that

Doesn't that sort of delegation open another attack surface?

Jeff

---

From: Martin Thomson <[email-masked]>
Date: Fri, 10 Jul 2015 19:33:25 -0700

> Doesn't that sort of delegation open another attack surface?

Not if you consider that the mobile device is known to the server it
contacts at the time it makes the request.  The problem puzzles
address is one where the client identity is unknown until the server
commits the work.