Subject: Re: PoW (Re: Attack research on HTTP/2 implementations)

From: Erik Aronesty <[email-masked]>
Date: Thu, 2 Sep 2021 19:59:52 -0400

- Proof of work is a mitigation for an attack... where the server is
obliged to perform cryptographic computations during negotiations that
expend energy... and instead requests that the clients perform an
analogous amount of work in order to mitigate the attack

- Certainly requiring the server to perform all of the computations
isn't more environmentally friendly than requiring the client to do
the same work, right?

- So that's not really an issue here

- Nor should it ever be a concern.  1) Governments, not protocol
developers, should be responsible for improving carbon capture.   2)
We cannot know that the efficiency gained by these mitigation of
attacks isn't greater than the presumed efficiencies lost.  3) Bitcoin
is a good example of a protocol where proof of work clearly saves more
energy than it expends - even though the analysis is not trivial.

On Mon, Aug 9, 2021 at 10:28 PM Erik Nygren <[email-masked]> wrote:
>
> On Mon, Aug 9, 2021 at 8:20 PM Stephen Farrell <[email-masked]> wrote:
>>
>>
>> It probably isn't, but just in case this is a bit of less
>> well known history...
>>
>> On 10/08/2021 01:00, Martin Thomson wrote:
>> > Most of these never went anywhere for a range of reasons.  One of
>> > those being that proof of work is an abomination (and I don't say
>> > that lightly).
>> I think there were also ideas of less onerous proofs that
>> went by the name "client puzzles" but that also fell by the
>> wayside, IIRC due to what's by now likely expired IPR.
>
>
> As an example see:
>
>     https://datatracker.ietf.org/doc/html/draft-nygren-tls-client-puzzles-02
>
> A real challenge is finding a balance that can let a range of legitimate clients
> through while blocking a range of attackers.  (For example, that draft
> has both CPU-hard and memory-hard puzzles.)
>
> To avoid battery-life and environmental / energy impact, these would
> presumably only get employed during attack scenarios, but figuring
> out when that is is a challenge.
>
> The protocol side of this isn't hard, but it adds some real complexity
> and understanding how to use it effectively isn't straight-forward.
>
> In one of the TLS WG interims, a request was for a deeper
> analysis of the scenarios where client puzzles would and wouldn't help,
> which seems like a great academic modeling project for someone
> so-inclined.
>
>     Erik
>
>
>
>
>
>
>
>

---

From: Nick Harper <[email-masked]>
Date: Thu, 2 Sep 2021 17:14:38 -0700

> - So that's not really an issue here

Proof of work requires the client to do additional work for the sake of
doing work. The server still has to do the same amount of work it would
have done had the client not done the proof of work (and in fact needs to
do slightly more work to verify the proof of work). This is not a zero-sum
game where some work is moved from the server to the client; it is a net
increase in the amount of work done.

> energy than it expends - even though the analysis is not trivial.

[citation needed]

---

From: "Charles 'chaals' (McCathie) Nevile" <[email-masked]>
Date: Fri, 03 Sep 2021 12:00:46 +1000

On Fri, 03 Sep 2021 09:59:52 +1000, Erik Aronesty <[email-masked]> wrote:

> 1) Governments, not protocol
> developers, should be responsible for improving carbon capture.

That seems to create a false dichotomy, analogous to suggesting that the  
effort to protect security is misguided because law enforcement should  
solve the problem, not protocol designers.

As someone who works on Ethereum blockchains I concur that PoW is a  
terrible thing. It has served a purpose, but I, like very many in the  
protocol design side am very pleased that the work to get rid of it is  
progressing, and unhappy it took us this long.

Your mileage may vary, which is why rough consensus is important to how we  
make decisions.

Thus far it isn't obvious how the disadvantages of PoW are outweighed by  
the advantages of using it here (noting that for each individual the  
weighting is a somewhat subjective judgement).

cheers

-- 
Using Opera's mail client: http://www.opera.com/mail/

---

From: Erik Aronesty <[email-masked]>
Date: Fri, 3 Sep 2021 07:54:53 -0400

> Proof of work requires the client to do additional work for the sake of doing work. The server still has to do the same amount of work it would have done had the client not done the proof of work (and in fact needs to do slightly more work to verify the proof of work). This is not a zero-sum game where some work is moved from the server to the client; it is a net increase in the amount of work done.

yes

assuming the attacker can only afford 10000 (arbitrary fixed number)
computations, before proof of work:

    attacker creates 10000 connections, server performs 10000
cryptographic computations
    total 10000 computations

after proof of work:

    attacker creates 1000 connections, requiring 10 computations per
connection, server performs 1000 cryptographic computations
    total 11000 computations

assuming the attacker has non-infinite resources, a 10x increase in
computation on the client during an attack results in a 10% increase
in overall computation

a very minor proof of work vastly mitigates attacks, while negligibly
increasing the work done by clients

of course companies like google wouldn't like this.... they rely on
machines automatically connecting to billions of sites, so i
understand why you might object against defenses that help mitigate
automation

>> energy than it expends - even though the analysis is not trivial.

really?

if you want, but this is a nascent field - like i said before, the
analysis is not trivial, and it's hard to know what the long term
effects of a bitcoin-integrated society would be.

https://assets.ctfassets.net/2d5q1td6cyxq/2D2BnksJjavw4a6SUvAPwZ/c42a9e3a520b0cc3b230cda3b43eead5/BCEI_White_Paper_.pdf

it's also unrelated to the more important point... that proof of work
is an excellent ddos deterrent

---

From: "Paul Vixie" <[email-masked]>
Date: Fri, 03 Sep 2021 15:41:20 +0000

On Fri Sep 3, 2021 at 11:54 AM UTC, Erik Aronesty wrote:
> > Proof of work ...

i pronounce the acronym PoW differently, "proof of waste". perhaps it's
not as wasteful if the computations are in the goldilocks zone, easy for
actual clients, difficult for malicious or fake clients. but we'd be
arguing matters of degree (how wasteful?) not kind (it's always wasteful.)

> computation on the client during an attack results in a 10% increase

attackers have elastic resources, they'll steal as much as they need. if
we try to stop them with proof of waste, they will use botnets as necessary
to waste as much as we demand. computation is not a rare or valuable asset.
i do not predict a goldilocks zone in the latency requirements for PoW
such that we can distinguish distributed vs. local computation by a client.

consider captcha, which tries to rely on human "computation". attackers
have at various times screen-scraped the captcha demand and shown it to a
user of some "free porn" site they operate, and then copy out the clicks
from that proxy-human, and use them to enter the original protected site.

security engineering is not the same as theory or whiteboarding. at a
minimum, it's necessary to understand the attacker's motives and
alternatives before targeting them for a cost you hope is "too high".

vixie

---

From: Erik Aronesty <[email-masked]>
Date: Fri, 3 Sep 2021 11:53:10 -0400

a flexible, intelligent protocol could make it infeasible for an
attacker to bring down a server, while allowing regular traffic to
proceed virtually unhindered

but i'm arguing with people who have conflicts of interest, so i'm done.

---

From: "Paul Vixie" <[email-masked]>
Date: Fri, 03 Sep 2021 22:43:58 +0000

> proceed virtually unhindered

i think you should google for "low orbit ion cannon" before you decide.

> but i'm arguing with people who have conflicts of interest, so i'm done.

i want to avoid non-beneficial complexity, but that i have no pecuniary
interests in whether such complexity is present in HTTP or not. but,
perhaps you are lumping me in without warrant.

vixie

---

From: Willy Tarreau <[email-masked]>
Date: Sat, 4 Sep 2021 07:40:41 +0200

This whole thread is particularly bizarre, but let me share my experience
here.

> proceed virtually unhindered

This is not true in practice. What matters is not the client-to-server
ratio of work, but the computation delay inflicted to clients so that
the server still has some resources left to work. With something like
PoW, you do not prevent clients from attacking too fast, you only shift
the offset at which the server will have to do lots of work. PoW is only
one tool serving to delay clients, not a solution. It is useful to
protect against small attacks but not against large ones.

Let's say your server can handle 10k connections per second. This means
that regardless of the number of clients, you must make sure the server
does not deal with more than 10k valid connections per second. When you
have 10k clients in front of you, it means you have to inflict on average
one second of work to all of them to keep the incoming rate low. This
can be tolerable to a valid client during an attack. I've personally
gone as high as 0.5s which really feels slow but compared to a dead
server it's not that bad.

But once the number of attackers increases, the ratios are not acceptable
anymore. Say you have 100k clients, you need to inflict them 10s of slow
down. So suddenly you slow down everyone to a level that valid clients
are not willing to accept anymore. And guess what ? The attackers will
not mind waiting for 10s of computation to finally access your site,
because if their goal is to take your site off-line, what matters for
them is not that the servers are down but that clients cannot access
them. With their extra load that results in inflicting very long PoW
to clients, they simply succeed.

This is why I'm saying that it only shifts the offset and does not
solve everything. In other PoW models, you don't care much about the
time it takes to solve the challenge. On the web there is an upper
limit that is the users' acceptance, and it is extremely low (in the
order of one second). And finding sufficient clients to deal with
this from an attacker's perspective is trivial.

In addition, the simple act of delivering the challenge to the client
requires some work, and this work is a non-negligible ratio of the
TLS calculation (typically 1/10 to 1/100), so that it remains very
easy to take down a server by forcing it to just deliver many
challenges. And in this case the client-to-server work ratio comes back
to 1:1 approximately. This is even why attacks such as SYN floods, ICMP
floods or UDP floods remain so popular these days.

When you only want to deal with low-capacity attacks (those that PoW
can help against), there are other, much simpler approaches, which
already offset the client-to-server work. Just use ECDSA certificates.
>From what I've seen in field, they require about 5 times less work on
the server while at the same time the client requires roughly 15 times
more than the server. This simply allows to significantly raise the
server's limits and bring them closer to other subsystems that are
involved (e.g. the TCP stack and/or stateful firewalls).

> but i'm arguing with people who have conflicts of interest, so i'm done.

This assertion is particularly strange considering that all of us here
have for interest to keep our respective components interoperable around
the same protocol definition in order to minimize our bug reports and
keep users happy.

However, keep in mind that your approach of PoW would only be effective
for very large operators, those that can deploy 100s to 1000s of servers
to absorb moderately large botnets, and would not help single-server
sites that remain trivial to knock down. I personally don't think we
should encourage all internet hosting to be brought to ultra-large
companies who could afford to protect it, and that's what your approach
would inevitably result in because it is the only one that can be
demonstrably effective there. It is not internet I'm dreaming of,
personnally.

Regards,
Willy

---

From: Stefan Eissing <[email-masked]>
Date: Sat, 4 Sep 2021 08:09:58 +0200

Thanks Willy, well stated.

The way out of the medieval internet is not for everyone to move behind the largest city walls. ;-)

- Stefan

> Am 04.09.2021 um 07:44 schrieb Willy Tarreau <[email-masked]>:
>

---

From: Erik Aronesty <[email-masked]>
Date: Mon, 6 Sep 2021 10:25:13 -0400

Pow is only one tool serving to delay clients, not a solution. It is useful
> to

Correct.

A useful tool, that allows smaller companies to host with fewer resources.

I can imagine large hosting companies might like the profligate waste that
people purchase in order to defend themselves these days.

But I think most smaller companies would prefer this.

The act of delivering the challenge can be simply a bit flipped in a header
packet.  The challenge itself can be a hash of some of the initial stuff
that's sent anyway.  I was thinking about a way to make sure that the
entire proposal consisted of a single bit.

Correct it only shifts the offset.  At most it improves things about a
hundred to one.  After that the attacker wins unless you have other tools.

ECDSA certs are a poor proof of work.  The best ratio you get is three to
one.  You're requiring a small amount of additional work for the client but
also for the server and it's quite significant what the server has to do.

Also you're making it so that you cannot serve your site to the public.
Which is not useful in many circumstances.

Your assertion about hosting providers is strange to me.

If POW gives small hosts  a 100/1 advantage over not having POW, protecting
them from all but the largest attacks, this clearly allows smaller hosting
providers to compete with larger ones in situations where they currently
cannot.

Obviously it can only be one tool.  But it's still an effective one in many
scenarios.

I run a relay network where we use this technique after https is
established on a websocket.  I can tell you that it is defended our network
admirably against more targeted/smaller attacks dozens of times this year
alone.

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 6 Sep 2021 18:27:42 +0200

> providers to compete with larger ones in situations where they currently

What you seem to refuse to understand is that it's not just the ratio but
the *limits*, and that if your servers are taken down by small attacks, it
doesn't mean at all that larger attacks are not possible for the attacker,
only that the attacker is sending what's necessary to take your site down.
If you're seeing your server going down with only 10000 connections per
second, you naturally think "ah if I could sustain more that would be
great", except that the client limits itself to your server's
responsiveness, and is barely working above 1%. Even if you would enforce
a 100:1 work ratio it would still be feasible for the client to take your
server down, by giving up on the challenge and trying again.

At the TCP layer, both the attacker and the victim face the very same
limits (in fact slightly less for the attacker who does not need to be
firewalled). This is why I explained that ratios are one thing but they
only apply an offset until the next limit is reached (connection rate
and/or connection count). Without seeking long, I can easily find hosted
machines offering 250 Mbps guaranteed public traffic for $0.07/hr. At
250 Mbps you can set up 186000 TCP connections per second. Good luck
finding a machine accessible to a small company that's able to deal with
such a high connection rate and to deliver TLS PoW challenges! Most of
them will be constrained by their link speed! And I'm not even talking
about the hundreds of thousands or even million concurrent connections
you'll need to sustain just to grant a few seconds timeout before your
regular clients can send their valid requests! And for half a dollar per
hour, that's 750k connections per second that you can send. Some can
even do that from their home fibre connection. I'm not kidding, this
PoW doesn't serve anymore at the packet rates we have to deal with
nowadays.

Another point worth adding, lots of DoS nowadays also involve application
servers. Once the attacker validates the PoW challenge, they can send
countless harmful requests there, that very often thanks to todays lazy
technologies cost way more CPU than the poor 1 ms it takes for an RSA
handshake and cause much more harm. Hint: just loop over the search link
of plenty of sites when it's self-hosted and you'll see that it can takes
*seconds* of CPU, not 1 ms.

As sad as it is, all self-hosted sites nowadays are trivial to instantly
knock down, and it's not due to $bigcorp creating protocols for their own
good but because link speeds increase faster than the processing capacity.
I'm not saying it's not worth defending oneself a little bit, quite the
opposite. All I'm saying is that modifying protocols to include this will
only result in the small ones that cannot update that often to become
harmed even more as attacks will instantly increase 100-fold.

> Obviously it can only be one tool.  But it's still an effective one in many

It would be effective if it prevented the packets from reaching the server's
external link in the first place.

> established on a websocket.

I'm not sure what you mean by "https is established on a websocket". If
you have to setup a websocket connection over HTTPS, the harm was already
done.

> I can tell you that it is defended our network

It's only effective for you because most users do not do this by default
and attackers do not waste resources dealing with your specific case. Once
a protection mechanism becomes standard, it's regularly attacked. Look at
SYN floods. A long time ago, SYN cookies were invented to deal with exactly
this. A few years later the protection had been adopted so quickly that
SYN flood rates have reached levels that can barely be handled by dedicated
software or even hardware since their goal has now changed and is now to
saturate links with packets that can difficultly be filtered out.

The best I hope for you if you're using a not-so-common mechanism that
works well for you is that it remains little spread so that it doesn't
become a standard target and continues to work well for you.

Willy