Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1USl9D-0002HY-GT for bitcoin-development@lists.sourceforge.net; Thu, 18 Apr 2013 09:28:55 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.219.54 as permitted sender) client-ip=209.85.219.54; envelope-from=mh.in.england@gmail.com; helo=mail-oa0-f54.google.com; Received: from mail-oa0-f54.google.com ([209.85.219.54]) by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1USl9C-0003v8-Ch for bitcoin-development@lists.sourceforge.net; Thu, 18 Apr 2013 09:28:55 +0000 Received: by mail-oa0-f54.google.com with SMTP id l20so2506747oag.41 for ; Thu, 18 Apr 2013 02:28:49 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.60.56.36 with SMTP id x4mr4925849oep.25.1366277329007; Thu, 18 Apr 2013 02:28:49 -0700 (PDT) Sender: mh.in.england@gmail.com Received: by 10.76.167.169 with HTTP; Thu, 18 Apr 2013 02:28:48 -0700 (PDT) In-Reply-To: <20130418090444.GA30995@savin> References: <453bfc69-b2ab-4992-9807-55270fbda0db@email.android.com> <20130418090444.GA30995@savin> Date: Thu, 18 Apr 2013 11:28:48 +0200 X-Google-Sender-Auth: -pysRLkyKvIMSsBZUPvozLAeBK8 Message-ID: From: Mike Hearn To: Peter Todd Content-Type: multipart/alternative; boundary=001a11c249f6dc3cd504da9f3a86 X-Spam-Score: -0.5 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (mh.in.england[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 1.0 HTML_MESSAGE BODY: HTML included in message 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1USl9C-0003v8-Ch Cc: Bitcoin Dev Subject: Re: [Bitcoin-development] Anti DoS for tx replacement X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 18 Apr 2013 09:28:55 -0000 --001a11c249f6dc3cd504da9f3a86 Content-Type: text/plain; charset=UTF-8 > An attack still shuts down useful tx replacement though. For instance in > the adjusting payments example an attacker sets up a legit adjusting > payment channel, does a bunch of adjustments, and then launches their > attack. They broadcast enough adjustments that their adjustment session > looks like part of an attack, and then don't have to pay for the full > adjusted amount. > It's possible, but let's do some back of the envelope calculations to look at how quickly such an attack can exhaust itself. Consider a contract that has a time window of 12 hours and is adjusted once per second for that duration. That's 43,200 adjustments. It sounds sort of ballpark-ish for micropayments. If you end up losing 1 seconds worth of service, well, probably that's no big deal. As the contract reaches its nLockTime, the attacker starts broadcasting all of the adjustments in sequence in the hope that an earlier version will be being processed as the lock time expires and a block is solved, so the latest version (the one that gives him the least money) ends up not being included in the chain. The input is a multi-signature transaction, so to process every single adjustment created would take 86,400 signature verifications. With the sipaspeed patches it seems ECDSA can be processed on modern cores at something like 20,000 signatures per second. So it'd take a bit over 4 seconds to process all of them (cpu time). That gives the attacker a less than 4 second window in which to try and roll back the contract to an earlier time before he reaches the last version and things are as they should be. Given that a block is solved on average every 10 minutes, you'd have to get very lucky indeed to succeed with such an attack. It's probably easier to try and find a corrupt miner who is willing to bend the rules for you. Let's include bandwidth. Say the contract (multi-sig input + the outputs) is about 700 bytes. 43,200 transactions is then about 29 megabytes of data. On a fairly normal 10mbit connection that would take about 23 seconds to transfer. Of course the real number is a bit higher because of latency introduced by the inv/tx round-tripping. So the time window of the attack is dominated by bandwidth but it's still quite small compared to the block solving window. It's *easily* DoSable, not trivially. > What I meant is - find some open DNS resolvers, start firing packets at testnet nodes, done. You don't have to do protocol level attacks to just render nodes useless. > You would need some way of determining which input was responsible for a > replacement though - I can't think of an obvious way to within the > current transaction format, but I haven't thought hard about it yet. > Ah, I think it actually is possible and this is an intriguing idea. Each input has its own sequence number. Look at the definition of IsNewerThan() - to make a newer version you increment your inputs sequence number in a particular manner whilst leaving the others alone. Having a single multi-sig input means you can't do that because both parties co-operate to update the single input, but schemes that use multiple inputs do seem posible. > How exactly do you envision replacement working with non-final == > non-standard anyway? > As I said at the bottom of my second mail, it means making non-final transactions relayable again, but only to nodes that advertise a high enough version number. Those nodes are expected to do something intelligent with them, like just not put them in the wallet (unless the user has opted in and ticked the "i know what i'm doing" box, perhaps). > If he's reasonable about the scope, IE just a initial implementation for > further evaluation, I figure it's about two days work. Well, it depends on your use case - you need to cast the (fixed) algorithm into a network protocol, manage the interactions between the parties, monitor the network for malicious broadcasts so you can replace them, fix the code so the wallets don't accept non-final transactions except when taking part in your contract, etc. If you do it all with Bitcoin-Qt it's easier but then your app can't easily run in places that can't afford a few hundred megs of ram (like wifi hotspots). The devil is in the details. --001a11c249f6dc3cd504da9f3a86 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

=
An attack still shuts down useful tx replacement though. For instance in the adjusting payments example an attacker sets up a legit adjusting
payment channel, does a bunch of adjustments, and then launches their
attack. They broadcast enough adjustments that their adjustment session
looks like part of an attack, and then don't have to pay for the full adjusted amount.

It's possibl= e, but let's do some back of the envelope calculations to look at how q= uickly such an attack can exhaust itself.

Consider a contract that has a time window of 12 hours and is adjusted once= per second for that duration. That's 43,200 adjustments. It sounds sor= t of ballpark-ish for micropayments. If you end up losing 1 seconds worth o= f service, well, probably that's no big deal. As the contract reaches i= ts nLockTime, the attacker starts broadcasting all of the adjustments in se= quence in the hope that an earlier version will be being processed as the l= ock time expires and a block is solved, so the latest version (the one that= gives him the least money) ends up not being included in the chain.

The input is a multi-signature transaction,= so to process every single adjustment created would take 86,400 signature = verifications. With the sipaspeed patches it seems ECDSA can be processed o= n modern cores at something like 20,000 signatures per second. So it'd = take a bit over 4 seconds to process all of them (cpu time).

That gives the attacker a less than 4 secon= d window in which to try and roll back the contract to an earlier time befo= re he reaches the last version and things are as they should be. Given that= a block is solved on average every 10 minutes, you'd have to get very = lucky indeed to succeed with such an attack. It's probably easier to tr= y and find a corrupt miner who is willing to bend the rules for you.

Let's include bandwidth. Say the contra= ct (multi-sig input + the outputs) is about 700 bytes. 43,200 transactions = is then about 29 megabytes of data. On a fairly normal 10mbit connection th= at would take about 23 seconds to transfer. Of course the real number is a = bit higher because of latency introduced by the inv/tx round-tripping. So t= he time window of the attack is dominated by bandwidth but it's still q= uite small compared to the block solving window.

It's *easily* DoSable, not trivially.

What I meant is - find some op= en DNS resolvers, start firing packets at testnet nodes, done. You don'= t have to do protocol level attacks to just render nodes useless.
=C2=A0
You would need some w= ay of determining which input was responsible for a
replacement though - I can't think of an obvious way to within the
current transaction format, but I haven't thought hard about it yet.

Ah, I think it actually is possible= and this is an intriguing idea. Each input has its own sequence number. Lo= ok at the definition of IsNewerThan() - to make a newer version you increme= nt your inputs sequence number in a particular manner whilst leaving the ot= hers alone.

Having a single multi-sig input means you c= an't do that because both parties co-operate to update the single input= , but schemes that use multiple inputs do seem posible.
=C2=A0
How exactly do you envision replacement work= ing with non-final =3D=3D
non-standard anyway?

As I said at= the bottom of my second mail, it means making non-final transactions relay= able again, but only to nodes that advertise a high enough version number. = Those nodes are expected to do something intelligent with them, like just n= ot put them in the wallet (unless the user has opted in and ticked the &quo= t;i know what i'm doing" box, perhaps).
=C2=A0
If he's reasonabl= e about the scope, IE just a initial implementation for
further evaluation, I figure it's about two days work.

Well, it depends on your use case - you need to cast = the (fixed) algorithm into a network protocol, manage the interactions betw= een the parties, monitor the network for malicious broadcasts so you can re= place them, fix the code so the wallets don't accept non-final transact= ions except when taking part in your contract, etc. If you do it all with B= itcoin-Qt it's easier but then your app can't easily run in places = that can't afford a few hundred megs of ram (like wifi hotspots). The d= evil is in the details.
--001a11c249f6dc3cd504da9f3a86--