Subject: [TLS] TLS client puzzles

From: Dmitry Khovratovich <[email-masked]>
Date: Wed, 29 Jun 2016 19:00:17 +0200

Dear all,

together with our colleagues from Akamai, we would like to pursue further
the draft on the TLS client puzzles, the first version of which was aired
in 2015. As before, the client puzzles allow a server to request clients
perform a selected amount of computation prior to the server performing
expensive cryptographic operations such as signature computation.

The distinction of the current version is that it includes, besides the
well-known SHA-2 puzzle, a memory-hard puzzle called Equihash. The latter
is a recent development by our team in Luxembourg, presented at this year
NDSS. It allows cheap and memoryless verification by the server even though
the puzzle solving guaranteely requires dozens of MB of RAM from a client
(time, memory, and client-server asymmetry are tunable parameters).
Equihash has been recently adopted as primary proof-of-work in the
privacy-enhanced cryptocurrency protocol Zcash.

The draft is available at
https://datatracker.ietf.org/doc/draft-nygren-tls-client-puzzles/
and the Equihash paper at
https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf

We would appreciate comments and discussion, and would like to present the
draft at the upcoming IETF meeting in Berlin.

-- 
Best regards,
Dmitry Khovratovich
University of Luxembourg

---

From: Brian Smith <[email-masked]>
Date: Wed, 29 Jun 2016 09:25:44 -1000

Dmitry Khovratovich <[email-masked]> wrote:
> It allows cheap and memoryless verification by the server even though the
> puzzle solving guaranteely requires dozens of MB of RAM from a client

I feel like this is impractical simply because lots of people are
building HTTPS clients that don't even have dozens of MB of RAM total.
I think we should avoid doing anything that requires the client to
have more than ~16KB of memory total to devote to TLS stuff.
Otherwise, we force the internet to have an architecture where all
small devices require a smart proxy to solve these puzzles for them
and do other things.

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Kyle Rose <[email-masked]>
Date: Wed, 29 Jun 2016 17:08:22 -0400

> small devices require a smart proxy to solve these puzzles for them

I think the appropriateness of client puzzles depends on what sorts of
tradeoffs we're willing to accept. Let's say we have a DoS attacker profile
that is not distinguishable from legitimate traffic, since that's the hard
case. Do we want to be able to serve *some* traffic during a DoS attack? If
we can't distinguish between legitimate users and attack traffic, we have
to assume everyone's a potential attacker. It seems what we're left with is
either rationing client requests or raising the cost of requests.

Rationing can be sliced up in any number of ways, but effectively amounts
to randomly denying some percentage of legitimate requests because we're
assuming attack traffic and legitimate traffic have the same profile. (In
reality, outside of NAT scenarios, we may be able to give immediate service
to existing clients and ration new clients; but we're assuming the horse is
a sphere for the sake of argument.)

Raising the cost of requests has a similar problem in that you're punishing
every client, but in doing so you do allow all clients capable of absorbing
the increased cost (e.g., memory, computing power) to get access to the
resources they need if the user is willing to accept that cost (e.g.,
energy, latency).

The problem you pointed out is that of clients that aren't capable of
absorbing the increased cost, such as low-power or memory-constrained
embedded devices. This is a legitimate concern, but I don't think it
universally disqualifies client puzzles. Maybe memory-hard puzzles aren't
appropriate for services that talk to IoT devices, but that doesn't mean
they aren't appropriate for websites that serve primarily to browsers. To
benefit from client puzzles on their websites, providers running IoT REST
services on the same server running their website may want to reconsider
that arrangement. Any client puzzle proposal must of course allow the
server to choose whether and when to issue a client puzzle, which in the
absence of authenticated client identity information should probably be
based on the expected client profile.

Tl;dr: memory-hard client puzzles are not universally appropriate as a DoS
defense, but I don't think that means they are never appropriate.

Kyle

---

From: Christian Huitema <[email-masked]>
Date: Wed, 29 Jun 2016 21:41:10 +0000

On Wednesday, June 29, 2016 2:08 PM, Kyle Rose wrote:
> resources they need if the user is willing to accept that cost (e.g., energy, 
> latency).

The obvious issue with the "proof of work" defense against DDOS is that the bot nets can do more work than many legitimate clients. The puzzle approach will cut off the least capable legitimate clients, such as old phones or IOT devices. It will not cut off the PC enrolled in a bot net. It will merely slow it down a little. But then, you could have the same effect by just delaying the response and enforcing one connection per client.

-- Christian Huitema

---

From: Kyle Rose <[email-masked]>
Date: Wed, 29 Jun 2016 22:00:08 -0400

On Wed, Jun 29, 2016 at 5:41 PM, Christian Huitema <[email-masked]>
wrote:

> energy,
> The obvious issue with the "proof of work" defense against DDOS is that
> the bot nets can do more work than many legitimate clients. The puzzle
> approach will cut off the least capable legitimate clients, such as old
> phones or IOT devices. It will not cut off the PC enrolled in a bot net. It
> will merely slow it down a little. But then, you could have the same effect
> by just delaying the response and enforcing one connection per client.
>

I agree with you that the above seems equivalent in theory, but in practice
it might not be feasible.

The biggest obstacle seems to be enforcing one connection per client. Let's
say rate limiting on a per-client basis doesn't work because many of your
clients are behind a NAT; or because the attacker is using IPv6 and
generates a ton of temporary addresses that make the situation
indistinguishable from many legitimate clients in the same subnet. So you
can either serve one (or a small N) of them at a time, or you drop that
restriction and allow a single client to mount an asymmetric attack.

Alternatively, what if you have lots of geographically-distributed servers
and can't share client rate limiting state among them quickly enough to
detect and blacklist attackers?

It's possible there are additional asymmetric attack vectors I'm not
thinking of, which is why I like this as a general defense against a class
of attacks. I mostly agree it's mostly worthless when you have one server
facing a botnet of 100,000 machines, but frankly that one server is a
sitting duck regardless of countermeasures. OTOH, what if you have 20,000
servers facing such a botnet? Client puzzles effectively become a mechanism
for enforcing distributed rate limiting, and could be used to dramatically
raise the cost of mounting such an attack.

I have to think a lot more about the IoT/resource-constrained client
problem, but I still don't think the existence of clients that would be  by
this scheme

Kyle

---

From: Kyle Rose <[email-masked]>
Date: Wed, 29 Jun 2016 22:01:28 -0400

Let's finish that last sentence:

I have to think a lot more about the IoT/resource-constrained client
problem, but I still don't think the existence of clients that would be
denied service by this scheme renders the concept completely inapplicable.

---

From: Geoffrey Keating <[email-masked]>
Date: 29 Jun 2016 19:36:32 -0700

> denied service by this scheme renders the concept completely inapplicable.

Perhaps for the resource-constrained/IoT situation, what you want is
to mostly be using a pre-shared key, track clients, and only make the
suspicious (too many connections too fast) or new ones solve the
puzzle.

---

From: Christian Huitema <[email-masked]>
Date: Thu, 30 Jun 2016 04:42:02 +0000

> suspicious (too many connections too fast) or new ones solve the

I am also a little worried that this can become a mechanism to DOS the clients. Imagine an adversary capable of redirecting a client request, either by hacking the DNS or hacking a proxy. The hacked server can send the client a puzzle, and force the client into spending some energy. And with the proposed extension, all that happens before the client has a chance to authenticate the server.

-- Christian Huitema

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 30 Jun 2016 09:37:52 +0300

Hi,

you may be also interested in similar work done in ipsecme group:

https://www.ietf.org/id/draft-ietf-ipsecme-ddos-protection-06.txt

The draft describes various defnse methods against (D)DoS attacks in IKEv2
and, in particular, introduces puzzles. We tried to specify using puzzles
in such a way that their negative impact on legitimate (or even unsupporting) initiators
be as small as possible (although of course it cannot be completely avoided).
The draft is in WGLC now.

Regards,
Valery Smyslov.

  On Wed, Jun 29, 2016 at 5:41 PM, Christian Huitema <[email-masked]> wrote:

  I agree with you that the above seems equivalent in theory, but in practice it might not be feasible.

  The biggest obstacle seems to be enforcing one connection per client. Let's say rate limiting on a per-client basis doesn't work because many of your clients are behind a NAT; or because the attacker is using IPv6 and generates a ton of temporary addresses that make the situation indistinguishable from many legitimate clients in the same subnet. So you can either serve one (or a small N) of them at a time, or you drop that restriction and allow a single client to mount an asymmetric attack.

  Alternatively, what if you have lots of geographically-distributed servers and can't share client rate limiting state among them quickly enough to detect and blacklist attackers?

  It's possible there are additional asymmetric attack vectors I'm not thinking of, which is why I like this as a general defense against a class of attacks. I mostly agree it's mostly worthless when you have one server facing a botnet of 100,000 machines, but frankly that one server is a sitting duck regardless of countermeasures. OTOH, what if you have 20,000 servers facing such a botnet? Client puzzles effectively become a mechanism for enforcing distributed rate limiting, and could be used to dramatically raise the cost of mounting such an attack.

  I have to think a lot more about the IoT/resource-constrained client problem, but I still don't think the existence of clients that would be  by this scheme

  Kyle

------------------------------------------------------------------------------

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

---

From: Yoav Nir <[email-masked]>
Date: Thu, 30 Jun 2016 11:23:47 +0300

> On 29 Jun 2016, at 10:25 PM, Brian Smith <[email-masked]> wrote:
> 

Hi, Brian.

Having clients commit resources to solve puzzles is always a balancing act between the capabilities of legitimate clients and those of the attackers. With CPU-intensive puzzles the attackers tend to be fast desktops and servers, while the legitimate clients could be as weak as a smart-object or as powerful as a server. It’s hard to find good parameters that will allow the oldest phone in while slowing the attacker down significantly. The same, as you pointed out, is true for RAM-intensive puzzles.

For the web the legitimate clients fall into two categories: Desktops and laptops on the one hand, and mobile phones on the other. For CPU-intensive puzzles their capabilities are far apart, so you’d have to tune the puzzle to the capabilities of the weakest phone, or else accept that phones are cut off during a severe DDoS attack.  With RAM, however, the differences are less pronounced. Both kinds of legitimate clients can afford to devote dozens of MB of RAM. The same is not true for IoT, but I’m talking about the real web here, not data services over HTTPS.

I think for this particular case RAM-intensive puzzles make sense.

Yoav

---

From: Bill Cox <[email-masked]>
Date: Thu, 30 Jun 2016 08:07:56 -0700

Equihash looks like a nice advance, so kudos to Dmitry's team.  So long as
we're on this topic, I'll mention an alternative that addresses some of
your concerns.  I do not recommend making it an official part of TLS, as I
feel that TLS is already vastly too complex.  However, this algorithm is
very cool:

Makwa <http://password-hashing.net/wiki/doku.php/makwa> is a "recommended"
algorithm from the password-hashing contest.  It is a proof-of-work
algorithm with fast verification, but is not memory-hard.  However, that
seems OK, since Makwa supports "delegation".  An IoT device can ask any
Makwa hashing provider on the Internet to do the proof of work for it, and
the result is as secure as if the IoT device had done it.  This solves the
concern about leaving under-powered devices behind, while aiding in DDoS
defense.

If widely adopted, with ASIC implementations, it would also defeat
botnets.  ASICs would many times more efficient than CPUs at Makwa, IIRC,
about 4000X in my last analysis.  Even botnets would have difficulty
competing with a legit ASIC Makwa provider.

My own dumb-idea related to Makwa is to use it as a PoW in a block-chain
based crypto-coin.  If miners are going to waste crazy amounts of
electricity mining anyway, at least they could help defeat DDoS attacks
while they are at it.  This might also create a method for IoT devices to
pay for the PoW service in nano transactions.

No way would I ever want such a beast bolted into TLS :>  Maybe as a DDoS
extension API in OpenSSL?

Bill

---

From: David Adrian <[email-masked]>
Date: Thu, 30 Jun 2016 23:25:06 +0000

> small devices require a smart proxy to solve these puzzles for them
I have to second Brian's opinion---it's difficult enough to get embedded
devices to use HTTPS already. Requiring dozens of megabytes of memory will
make HTTPS impossible for these devices in many cases.