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
|
Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193]
helo=mx.sourceforge.net)
by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <voights@gmail.com>) id 1T40dL-0003jX-Jn
for bitcoin-development@lists.sourceforge.net;
Wed, 22 Aug 2012 02:25:27 +0000
Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.210.47 as permitted sender)
client-ip=209.85.210.47; envelope-from=voights@gmail.com;
helo=mail-pz0-f47.google.com;
Received: from mail-pz0-f47.google.com ([209.85.210.47])
by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1T40dK-0005Vj-QH
for bitcoin-development@lists.sourceforge.net;
Wed, 22 Aug 2012 02:25:27 +0000
Received: by daks35 with SMTP id s35so305940dak.34
for <bitcoin-development@lists.sourceforge.net>;
Tue, 21 Aug 2012 19:25:21 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.66.90.67 with SMTP id bu3mr42397266pab.26.1345602320929; Tue,
21 Aug 2012 19:25:20 -0700 (PDT)
Received: by 10.66.254.97 with HTTP; Tue, 21 Aug 2012 19:25:20 -0700 (PDT)
Date: Tue, 21 Aug 2012 22:25:20 -0400
Message-ID: <CAOCHLotLO8eaLJV2Kkm_YEvbDb80A1VzVGuvujm6NjjGraFEsQ@mail.gmail.com>
From: Forrest Voight <voights@gmail.com>
To: bitcoin-development@lists.sourceforge.net
Content-Type: text/plain; charset=ISO-8859-1
X-Spam-Score: -1.6 (-)
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
(voights[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
author's domain
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: 1T40dK-0005Vj-QH
Subject: [Bitcoin-development] Full Disclosure: CVE-2012-2459 (block merkle
calculation exploit)
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Wed, 22 Aug 2012 02:25:27 -0000
Since at least 80% of the Bitcoin network is now protected against
this attack, I've been given permission to disclose it:
The Merkle hash implementation that Bitcoin uses to calculate the
Merkle root in a block header is flawed in that one can easily
construct multiple lists of hashes that map to the same Merkle root.
For example, merkle_hash([a, b, c]) and merkle_hash([a, b, c, c])
yield the same result. This is because, at every iteration, the Merkle
hash function pads its intermediate list of hashes with the last hash
if the list is of odd length, in order to make it of even length.
And so, the Merkle root function can be effectively preimaged by
changing the input so that one of the intermediate lists is of even
length with the last two elements equal (where originally it was of
odd length with a last element equal to the earlier mentioned two). As
was later noted, this extends to any input length that is not a power
of two: merkle_hash([a, b, c, d, e, f]) == merkle_hash([a, b, c, d, e,
f, e, f]). Note that to maintain the same root hash, the only
flexibility that exists is duplication of elements.
As a result, two blocks can easily be created that have the same block
hash, though one can be valid and the other invalid, by duplicating
one or more of the transactions in a way that maintains the Merkle
root hash. Duplicating any transaction will make the block invalid,
since the block double spends a certain past transaction output.
An unpatched Bitcoin installation can be permanently wedged at its
current highest block using this and the fact that Bitcoin caches
orphan blocks in a disk-backed database. To do so, the attacker must
send it a valid block (that will eventually make it into the
blockchain) made invalid by duplicating one of the transactions in a
way that preserves the Merkle root. The attacker doesn't even need to
mine their own block - instead, they can listen for a block, then
mutate it in this way, and pass it on to their peers.
Once the victim receives this invalid block, they will cache it on
disk, attempt to process it, and reject it as invalid. Re-requesting
the block will not be even attempted since Bitcoin believes that it
already has the block, since it has one with the same hash. Bitcoin
eventually displays the "WARNING: Displayed transactions may not be
correct! You may need to upgrade, or other nodes may need to
upgrade." warning when the blockchain extends further beyond the
received invalid block.
The problem was fixed by Gavin Andresen in Bitcoin commit be8651d [1]
by rejecting blocks with duplicate transactions in CheckBlock,
preventing them from being cached at all.
Cheers,
Forrest Voight
http://forre.st/
[1]: https://github.com/bitcoin/bitcoin/commit/be8651dde7b59e50e8c443da71c706667803d06d
|
