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
|
Return-Path: <tier.nolan@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 64355AC8
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 11 Jan 2016 23:58:00 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ig0-f173.google.com (mail-ig0-f173.google.com
[209.85.213.173])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id DB02ECC
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 11 Jan 2016 23:57:59 +0000 (UTC)
Received: by mail-ig0-f173.google.com with SMTP id ik10so135021905igb.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 11 Jan 2016 15:57:59 -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:cc
:content-type; bh=DflXMDSnTypouvEzlKVJ+poLjf5QBhsV3uFFl/xuBEk=;
b=S+k2fuU22o0SqvTL+6p69+8GvuyuEruct/GTaL67CjMXo5zCFO96m9cmdQ4AtyAHl+
LLqP9i1ArvUPWHvCEvtUf0VXkAe0cZpHPlhlU5jfYgmJWeIiACJtig/wwj0Vnf2zJz7B
JWGth+9f6Dvqn0hfLRI4ckXZJxPR3cbL4rMIMUOR49RvHXKaLIH0+jvVXQQCkKAYeGNC
ROQYndpA/tu2Z/ci/SqPG4TJsS+DBQdVhMn3QG7+7y+AbrysSmWg8xBvYaaiT+Qx5do8
tWnYSITBHFcxzxqeLI9zjsNDkVQ8En2Jtr3l3s7JlfnY2TbmJHU1ruzD795MDjzFdaM0
33wg==
MIME-Version: 1.0
X-Received: by 10.50.119.105 with SMTP id kt9mr3953286igb.26.1452556679318;
Mon, 11 Jan 2016 15:57:59 -0800 (PST)
Received: by 10.79.77.75 with HTTP; Mon, 11 Jan 2016 15:57:59 -0800 (PST)
In-Reply-To: <CABsx9T3MfndREm9icE-TUF58zsRZ5YsBMvUAMy4E-MmYWxWV=A@mail.gmail.com>
References: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com>
<CAPg+sBhH0MODjjp8Avx+Fy_UGqzMjUq_jn3vT3oH=u3711tsSA@mail.gmail.com>
<8760z4rbng.fsf@rustcorp.com.au>
<C4B5B9F1-9C53-45BC-9B30-F572C78096E3@mattcorallo.com>
<8737u8qnye.fsf@rustcorp.com.au>
<CABsx9T1gmz=sr_sEEuy8BQU6SXdmi58O30rzRWNW=0Ej98fi4A@mail.gmail.com>
<20160108153329.GA15731@sapphire.erisian.com.au>
<CABsx9T3MfndREm9icE-TUF58zsRZ5YsBMvUAMy4E-MmYWxWV=A@mail.gmail.com>
Date: Mon, 11 Jan 2016 23:57:59 +0000
Message-ID: <CAE-z3OUMRivWPVA+3BgC_95MGYBHN34+hoo6xfCu_gNeLFVknA@mail.gmail.com>
From: Tier Nolan <tier.nolan@gmail.com>
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=089e0111c26ae312e1052917b4d0
X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,MISSING_HEADERS,
RCVD_IN_DNSWL_LOW autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.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: Mon, 11 Jan 2016 23:58:00 -0000
--089e0111c26ae312e1052917b4d0
Content-Type: text/plain; charset=UTF-8
On Fri, Jan 8, 2016 at 3:46 PM, Gavin Andresen via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> How many years until we think a 2^84 attack where the work is an ECDSA
> private->public key derivation will take a reasonable amount of time?
>
I think the EC multiply is not actually required. With compressed public
keys, the script selection rule can just be a sha256 call instead.
V is the public key of the victim, and const_pub_key is the attacker's
public key.
if prev_hash % 2 == 0:
script = "2 V 0x02%s 2 CHECKMULTISIG" % (sha256(prev_hash)))
else:
script = "CHECKSIG %s OP_DROP" % (prev_hash, const_pub_key)
next_hash = ripemd160(sha256(script))
If a collision is found, there is a 50% chance that the two scripts have
different parity and there is a 50% chance that a compressed key is a valid
key.
This means that you need to run the algorithm 4 times instead of 2.
The advantage is that each step is 2 sha256 calls and a ripemd160 call. No
EC multiply is required.
--089e0111c26ae312e1052917b4d0
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On F=
ri, Jan 8, 2016 at 3:46 PM, Gavin Andresen via bitcoin-dev <span dir=3D"ltr=
"><<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_b=
lank">bitcoin-dev@lists.linuxfoundation.org</a>></span> wrote:<br><block=
quote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1=
px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div>How many =
years until we think a 2^84 attack where the work is an ECDSA private->p=
ublic key derivation will take a reasonable amount of time?<br></div></div>=
</blockquote><div><br></div><div>I think the EC multiply is not actually re=
quired.=C2=A0 With compressed public keys, the script selection rule can ju=
st be a sha256 call instead.<br><br></div><div>V is the public key of the v=
ictim, and const_pub_key is the attacker's public key.<br></div><div></=
div><div><br></div><div>=C2=A0=C2=A0=C2=A0=C2=A0 if prev_hash % 2 =3D=3D 0:=
<br></div><div></div><div>
=C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 script =3D "2 V 0x02%s 2 CHECKMU=
LTISIG" % (sha256(prev_hash)))<br>=C2=A0=C2=A0=C2=A0 else:<br>
=C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 script =3D "CHECKSIG %s OP_DROP&=
quot; % (prev_hash, const_pub_key)<br><br>=C2=A0=C2=A0=C2=A0 next_hash =3D =
ripemd160(sha256(script))</div><div><br></div><div>If a collision is found,=
there is a 50% chance that the two scripts have different parity and there=
is a 50% chance that a compressed key is a valid key.<br><br></div><div>Th=
is means that you need to run the algorithm 4 times instead of 2.=C2=A0 <br=
><br>The advantage is that each step is 2 sha256 calls and a ripemd160 call=
.=C2=A0 No EC multiply is required.<br></div></div></div></div>
--089e0111c26ae312e1052917b4d0--
|
