MIME-Version: 1.0
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
Subject: Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or
	not?
Precedence: list

--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=
">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_b=
lank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</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-&gt;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&#39;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 &quot;2 V 0x02%s 2 CHECKMU=
LTISIG&quot; % (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 &quot;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--