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
172
173
174
|
Return-Path: <eth3rs@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id C7CABC95
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Jan 2016 22:56:40 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f53.google.com (mail-wm0-f53.google.com [74.125.82.53])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id F1A0616B
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Jan 2016 22:56:39 +0000 (UTC)
Received: by mail-wm0-f53.google.com with SMTP id l65so115308100wmf.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 07 Jan 2016 14:56:39 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:cc:content-type:content-transfer-encoding;
bh=IG/J3iTCC14s9sQWSnFZNbGuI4dPplBd0QC/tHfE74A=;
b=u5XWwpM50b4GNIXqkjCBCqJPorwCHSgJCFoYDLTib+z2ECMjP1PGIerPeqisjx/pSR
hXjBwO+j6X5a8El7dsje0ImZ8A6zD2cX+tsUACNw+rm+9sDBCxfxYZ18BU6roE0PwEhQ
I1HmGOsa1+AblSB0md99RP2M1WJzUBWBW/t6vTgJeztJfOVfmBoKkupPIZx6f8zaGgiF
VyAzxP+uD+vyd+kjKHUy0aQ55LE+nxIffmpI4YC7VVP9DjlwmqIVrBI9brMGz6F63EbQ
bblbWF2yhg4NqelyluYdcHdYY23vHpinQYB12Y0+jcefq4PL8oRE9F0NCOtpAsvUI3OE
Z7jw==
MIME-Version: 1.0
X-Received: by 10.28.158.194 with SMTP id h185mr20498052wme.48.1452207398792;
Thu, 07 Jan 2016 14:56:38 -0800 (PST)
Received: by 10.27.217.12 with HTTP; Thu, 7 Jan 2016 14:56:38 -0800 (PST)
In-Reply-To: <CABsx9T0JX41bOQxjPg7QFUKGEwgFaCGFzR3ySbaqFwy4i28Hbg@mail.gmail.com>
References: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com>
<CALqxMTHjvFT2aCBYDEiG-6F5qvsXK57_LR6ttpPb3xUG2i443w@mail.gmail.com>
<CAGLBAhczEceqDp6XPSVLJ0FuTcmZgYkVnUE4rspb3JdeHnZJUg@mail.gmail.com>
<CABsx9T0JX41bOQxjPg7QFUKGEwgFaCGFzR3ySbaqFwy4i28Hbg@mail.gmail.com>
Date: Thu, 7 Jan 2016 17:56:38 -0500
Message-ID: <CAEM=y+VAmT5wRsDhUufPCDPB=U+h-MQ1+xY5uJqAAO8Xt6SaxA@mail.gmail.com>
From: Ethan Heilman <eth3rs@gmail.com>
To: Gavin Andresen <gavinandresen@gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM,
RCVD_IN_DNSWL_LOW 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: Thu, 07 Jan 2016 23:09:27 +0000
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or
not?
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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: Thu, 07 Jan 2016 22:56:40 -0000
>Ethan: your algorithm will find two arbitrary values that collide. That i=
sn't useful as an attack in the context we're talking about here (both of t=
hose values will be useless as coin destinations with overwhelming probabil=
ity).
I'm not sure exactly the properties you want here and determining
these properties is not an easy task, but the case is far worse than
just two random values. For instance: (a). with a small modification
my algorithm can also find collisions containing targeted substrings,
(b). length extension attacks are possible with RIPEMD160.
(a). targeted cycles:
target1 =3D "str to prepend"
target2 =3D "str to end with"
seed =3D {0,1}^160
x =3D hash(seed)
for i in 2^80:
....x =3D hash(target1||x||target2)
x_final =3D x
y =3D hash(tartget1||x_final||target2)
for j in 2^80:
....if y =3D=3D x_final:
........print "cycle len: "+j
........break
....y =3D hash(target1||y||target2)
If a collision is found, the two colliding inputs must both start with
"str to prepend" and end with the phrase "str to end with". As before
this only requires 2^81.5 computations and no real memory. For an
additional 2**80 an adversary has an good change of finding two
different targeted substrings which collide. Consider the case where
the attacker mixes the targeted strings with the hash output:
hash("my name is=3D0x329482039483204324423"+x[1]+", my favorite number
is=3D"+x) where x[1] is the first bit of x.
(b). length extension attacks
Even if all the adversary can do is create two random values that
collide, you can append substrings to the input and get collisions.
Once you find two random values hash(x) =3D hash(y), you could use a
length extension attack on RIPEMD-160 to find hash(x||z) =3D hash(y||z).
Now the bitcoin wiki says:
"The padding scheme is identical to MD4 using Merkle=E2=80=93Damg=C3=A5rd
strengthening to prevent length extension attacks."[1]
Which is confusing to me because:
1. MD4 is vulnerable to length extension attacks
2. Merkle=E2=80=93Damg=C3=A5rd strengthening does not protect against lengt=
h
extension: "Indeed, we already pointed out that none of the 64
variants above can withstand the 'extension' attack on the MAC
application, even with the Merkle-Damgard strengthening" [2]
3. RIPEMD-160 is vulnerable to length extension attacks, is Bitcoin
using a non-standard version of RIPEMD-160.
RIPEMD160(SHA256()) does not protect against length extension attacks
on SHA256, but should protect RIPEMD-160 against length extension
attacks as RIPEMD-160 uses 512-bit message blocks. That being said we
should be very careful here. Research has been done that shows that
cascading the same hash function twice is weaker than using HMAC[3]. I
can't find results on cascading RIPEMD160(SHA256()).
RIPEMD160(SHA256()) seems better than RIPEMD160() though, but security
should not rest on the notion that an attacker requires 2**80 memory,
many targeted collision attacks can work without much memory.
[1]: https://en.bitcoin.it/wiki/RIPEMD-160
[2]: "Merkle-Damgard Revisited: How to Construct a Hash Function"
https://www.cs.nyu.edu/~puniya/papers/merkle.pdf
[3]: https://www.cs.nyu.edu/~dodis/ps/h-of-h.pdf
On Thu, Jan 7, 2016 at 4:06 PM, Gavin Andresen via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> Maybe I'm asking this question on the wrong mailing list:
>
> Matt/Adam: do you have some reason to think that RIPEMD160 will be broken
> before SHA256?
> And do you have some reason to think that they will be so broken that the
> nested hash construction RIPEMD160(SHA256()) will be vulnerable?
>
> Adam: re: "where to stop" : I'm suggesting we stop exactly at the curre=
nt
> status quo, where we use RIPEMD160 for P2SH and P2PKH.
>
> Ethan: your algorithm will find two arbitrary values that collide. That
> isn't useful as an attack in the context we're talking about here (both o=
f
> those values will be useless as coin destinations with overwhelming
> probability).
>
> Dave: you described a first preimage attack, which is 2**160 cpu time and=
no
> storage.
>
>
> --
> --
> Gavin Andresen
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
|
