From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 64355AC8 for ; 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 ; Mon, 11 Jan 2016 23:57:59 +0000 (UTC) Received: by mail-ig0-f173.google.com with SMTP id ik10so135021905igb.1 for ; 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: References: <8760z4rbng.fsf@rustcorp.com.au> <8737u8qnye.fsf@rustcorp.com.au> <20160108153329.GA15731@sapphire.erisian.com.au> Date: Mon, 11 Jan 2016 23:57:59 +0000 Message-ID: From: Tier Nolan Cc: Bitcoin Dev 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
On F= ri, 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->p= ublic key derivation will take a reasonable amount of time?
=

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.

V is the public key of the v= ictim, and const_pub_key is the attacker's public key.

=C2=A0=C2=A0=C2=A0=C2=A0 if prev_hash % 2 =3D=3D 0:=
=C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 script =3D "2 V 0x02%s 2 CHECKMU= LTISIG" % (sha256(prev_hash)))
=C2=A0=C2=A0=C2=A0 else:
=C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 script =3D "CHECKSIG %s OP_DROP&= quot; % (prev_hash, const_pub_key)

=C2=A0=C2=A0=C2=A0 next_hash =3D = 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.

Th= is means that you need to run the algorithm 4 times instead of 2.=C2=A0
The advantage is that each step is 2 sha256 calls and a ripemd160 call= .=C2=A0 No EC multiply is required.
--089e0111c26ae312e1052917b4d0--