1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
Return-Path: <sergio.d.lerner@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id DE7DABB3
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 14 Aug 2018 15:27:47 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lj1-f170.google.com (mail-lj1-f170.google.com
[209.85.208.170])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 2A33476A
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 14 Aug 2018 15:27:47 +0000 (UTC)
Received: by mail-lj1-f170.google.com with SMTP id s12-v6so15716652ljj.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 14 Aug 2018 08:27:47 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
bh=zbcs4QHuABCJVIVYQ25C8V7RaPLWpREQrlxrryT4r1U=;
b=DIZCnRRmT49nUhg1E6/cBXipHHdqv5pgbXav7u+jpyxKyAHnw9ifYg4DI+0UHe7kUh
FKs6EysgWC7SpLDwoq6gG83THTbbYP5YgtzIbWtCfs7HrPphgiK+CoyfO7KEj+Jve2Dq
CiCxNk/nhfSibR6jRWnebeeKRT/9RMVVpuv8JtKEQrkuVdYRQ0Aj4/bKSxiWgUxUSd4k
tyqYq3PCUuwN/o196EFEJX89FB6coYJ1HZI2VKO9dqRI1NUOvfFo5+thThFhTA9RE8ue
ELca4x/bh7cVbD7wE48BpZhxdh3s6rPf8zdvQQg8/Jf/WBa7j+ZzG9+ZMuNkLz2fcQn+
mC6A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to;
bh=zbcs4QHuABCJVIVYQ25C8V7RaPLWpREQrlxrryT4r1U=;
b=hNoGjQC4DIpgPMAKpgL6mzmmKFnmviC2mOXB1vxusJ0pIxQvexfJgSwdxmJFGFHL/b
Tu4jeEvBHuUQryTS/z1Zt6g0BOXTVbvRjhFE3Fa2ETZw1a6fMeTuVGLM87td9ixSS0st
JQSES46qNBnWazG1kLpcm/Zm17/FuPPH+cxIDXLV0uvWcQjMPXhWIbR91Vjv6pzXY+0J
vQZikisYx9WwZFPZLYCDeolRkNLrfSngZZPIFYv0q/M4P9DSf8U8isSDGqXDGPcfSLVc
bPbUeRdsOmb3o9fV35OVlMil0CwaAmqGjsFz+gL6hpis4OT6BWfExk4Le5kzgU+KiMDL
lwPw==
X-Gm-Message-State: AOUpUlEoEQGJIQ/8FjZ0HCcjoGI8NqRi9PRmRIhlryXUKdBYQTMcN/gh
4hh93tbZCK/0YhC/ywQOOBakFmcfNipWwmO2xPzGxw==
X-Google-Smtp-Source: AA+uWPzu3E6dVrFf5EtbgjdyFrNx+XbC1DtQgwI+vkGYFFE+5Gcz2H/vuTB5JxKSRUCzfl3acBzPrfEC1xL3ebJhGgY=
X-Received: by 2002:a2e:8457:: with SMTP id
u23-v6mr14889846ljh.95.1534260465200;
Tue, 14 Aug 2018 08:27:45 -0700 (PDT)
MIME-Version: 1.0
References: <CAKzdR-oVncNaEA_+WHvdmLoD=SF=0AgpiN6WVXdbvnY6=NtYiA@mail.gmail.com>
In-Reply-To: <CAKzdR-oVncNaEA_+WHvdmLoD=SF=0AgpiN6WVXdbvnY6=NtYiA@mail.gmail.com>
From: Sergio Demian Lerner <sergio.d.lerner@gmail.com>
Date: Tue, 14 Aug 2018 12:26:25 -0300
Message-ID: <CAKzdR-rziKesAJVHSoCOg39Nh3zqst_MB_Q_zCGYorRYFMqhAw@mail.gmail.com>
To: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000057258057366dadc"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Wed, 15 Aug 2018 13:28:40 +0000
Subject: [bitcoin-dev] Fwd: Simple change to the "merkleblock" command to
protect from SPV proof extension attacks
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 14 Aug 2018 15:27:48 -0000
--000000000000057258057366dadc
Content-Type: text/plain; charset="UTF-8"
Hi,
While fixing RSK's SPV bridge I came up with an idea to fix the
MERKLEBLOCK command to prevent rogue peers from attacking SPV peers using
Bitcoin's Merkle tree structure flaws. The most annoying attack is the one
that tries to confuse a victim peer into thinking a transaction is an inner
node, extending such node with a new right-sided branch with a fake
transaction (*) .
The old idea to soft-fork Bitcoin to make invalid 64-byte transactions is
attractive, but also a coordination problem that could be avoided with this
new proposal.
The idea is simple, and it's not a fork, but a network protocol improvement.
Let A be the hash digest that must be combined with the hash digest B, such
that the upper node hash is SHA256(SHA256(A | B)).
Therefore A = SHA256(SHA256(X)) and B = SHA256(SHA256(Y)), and X and Y are
either Bitcoin transactions or other inner nodes.
Instead of storing A, the merkleblock structure should store a pre-image of
A, or SHA256(X).
If the block only has the coinbase, nothing is done.
The pre-image change could be done to both left and right hashes, but it's
enough to do it to all left-side hashes that do not have children in the
partial merkle tree structure (let's call them terminal hahes. to avoid
confusion with leaf hashes).
Verifiers (SPV nodes) would apply a single SHA256() operation to the
left-sided terminal hashes before combining them. The cost to the verifier
is in the worse case only 33% more.
This basically limits the attacker's ability to supply chosen-hash digests
in order to build a transaction. Because the left side contains most of the
previn hash, the attacker would need to bruteforce a huge space (about 208
bits) in order to come up with a pre-image that maps to a owned previn.
Meet-in-the-middle attacks would be expensive as UTXOs are not free.
To implement this change, a new command MERKLEBLOCK2 could be implemented
or the protocol version could be used to differentiate between the two
modes of the MERKLEBLOCK command.
If the idea gets community support, I may write the BIP/code or invite
anyone to do it.
regards
(*)
https://bitslog.wordpress.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/
--000000000000057258057366dadc
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><div class=3D"gmail_quote"><div dir=3D"ltr">Hi,<div>=
=C2=A0While fixing RSK's SPV bridge I came up with an idea to fix the M=
ERKLEBLOCK command to prevent rogue peers from attacking SPV peers using Bi=
tcoin's Merkle tree structure flaws. The most annoying attack is the on=
e that=C2=A0tries to confuse a victim peer into thinking a transaction is a=
n inner node, extending such node with a new right-sided branch with a fake=
transaction (*) .=C2=A0</div><div><br></div><div>The old idea to soft-fork=
Bitcoin to make invalid 64-byte transactions is attractive, but also a coo=
rdination problem that could be avoided with this new proposal.</div><div><=
br></div><div>The idea is simple, and it's not a fork, but a network pr=
otocol improvement.</div><div>Let A be the hash digest that must be combine=
d with the hash digest B, such that the upper node hash is SHA256(SHA256(A =
| B)).</div><div>Therefore A =3D SHA256(SHA256(X)) and B =3D SHA256(SHA256(=
Y)), and X and Y are either Bitcoin transactions or other inner nodes.=C2=
=A0</div><div>Instead of storing A, the merkleblock structure should store =
a pre-image of A, or=C2=A0<span style=3D"font-size:small;background-color:r=
gb(255,255,255);text-decoration-style:initial;text-decoration-color:initial=
;float:none;display:inline">SHA256(X)</span>.</div><div>
<span style=3D"font-size:small;background-color:rgb(255,255,255);text-decor=
ation-style:initial;text-decoration-color:initial;float:none;display:inline=
">If the block only has the coinbase, nothing is done.</span>=C2=A0<br></di=
v><div>The pre-image change could be done to both left and right hashes, bu=
t it's enough to do it to all left-side hashes that do not have childre=
n in the partial merkle tree structure (let's call them terminal hahes.=
to avoid confusion with leaf hashes).</div><div>=C2=A0=C2=A0</div><div>Ver=
ifiers (SPV nodes) would apply a single SHA256() operation to the left-side=
d terminal hashes before combining them. The cost to the verifier is in the=
worse case only 33% more.</div><div><br></div><div>This basically limits t=
he attacker's ability to supply chosen-hash digests in order to build a=
transaction. Because the left side contains most of the previn hash, the a=
ttacker would need to bruteforce a huge space (about 208 bits) in order to =
come up with a pre-image that maps to a owned previn. Meet-in-the-middle at=
tacks would be expensive as UTXOs are not free.</div><div><br></div><div>To=
implement this change, a new command MERKLEBLOCK2 could be implemented or =
the protocol version could be used to differentiate between the two modes o=
f the MERKLEBLOCK command.=C2=A0</div><div><br></div><div>If the idea gets =
community support, I may write the BIP/code or invite anyone to do it.</div=
><div><br></div><div>regards</div><div><br></div><div>=C2=A0(*)=C2=A0<a hre=
f=3D"https://bitslog.wordpress.com/2018/06/09/leaf-node-weakness-in-bitcoin=
-merkle-tree-design/" target=3D"_blank">https://bitslog.wordpress.com/2018/=
06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/</a></div><div><br><=
/div></div>
</div></div>
--000000000000057258057366dadc--
|
