Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id D5CA6EAF for ; Mon, 12 Feb 2018 21:32:38 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-lf0-f50.google.com (mail-lf0-f50.google.com [209.85.215.50]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D59D7165 for ; Mon, 12 Feb 2018 21:32:37 +0000 (UTC) Received: by mail-lf0-f50.google.com with SMTP id k19so22374825lfj.1 for ; Mon, 12 Feb 2018 13:32:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=oD5vlXPcmLUJsWEXzKKSVPAV9aQxct7f/XhVzfY7DzI=; b=k1+lIGqpyt8nCF6tL3si5WmP2f0MxLqJhWsvhX6RjeMRtMol7CnTLFssGvhpPXDUWa aYpley8qWTE0OlhXb88UUtY/Ha8vOVJbQmMuhz242w55tRb2cxGJXRmpTQnGikIXESxk /PA3nxSBExtlPrZqJVv0b5PfRyvQogdgzxCQCkhzP0kOOAAdVkM46eJjN+5XIVX1NH8Z qKCbxJHZY1I4lvaiKAGWtgh0A22Opw8HtIWqjV2TuDaXOcz9yzOim2ZoWQa0aE8N3+8U WWgWk17fSGYj5OvlPtyfUasyDH6OkvoaTwFP5c6gTRJsA47ShuoFvojT2SG9Ac02lv/v KQdA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=oD5vlXPcmLUJsWEXzKKSVPAV9aQxct7f/XhVzfY7DzI=; b=piygfXestexrd7Xw/MumLD3hbsDKcIjvCufKmwvPkKe7ipb4DcYfYiJUV7dMdmVPLu CIp33FJyd/BD/Db9Oq+U5cHqbIRISAMDqUhQNBoXpsI2Q/eOKtnHm7E18J265NtqVABc 3tWouGXcbl265/JFWAInakJ/0zUcXtzpou/Bz/Dy3nrTFhCBzVF3pAD0SpsP5J0MVkpm 1I+BwisOz5J8vtlxONTQ3B8W7pl8ybhQbjFulAPe7tBQ8O0I2tXGcpD92pi5HepH/lLl k3F3xxhgPotHFlBYFsC/CJs/tdmmUiQnbA8uacw+wv098B6xqSJSYiN1ksGraI9dWTR4 ClDA== X-Gm-Message-State: APf1xPA3OJVrUrBoAHiX6Lu3Or3SFBzIFhpjhQpXzE22SRt4uhEH3YzC jfcJXs2/PEmCc9Jtc+YRIzeh6O0EXrq6mJqEETU= X-Google-Smtp-Source: AH8x227pUdcOZxA596y+BsfpieWApeW46KucGj3zoXcdRk+4DybHr26wNaexFoJq4my+K24YQUbizM41UymL6bU1DHg= X-Received: by 10.25.153.213 with SMTP id b204mr206702lfe.144.1518471156007; Mon, 12 Feb 2018 13:32:36 -0800 (PST) MIME-Version: 1.0 Received: by 10.25.89.140 with HTTP; Mon, 12 Feb 2018 13:32:35 -0800 (PST) In-Reply-To: <1518450650.7829.87.camel@mmci.uni-saarland.de> References: <1518450650.7829.87.camel@mmci.uni-saarland.de> From: Tristan Hoy Date: Tue, 13 Feb 2018 08:32:35 +1100 Message-ID: To: Tim Ruffing , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="001a11401934db0d8605650a9d95" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE 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: Mon, 12 Feb 2018 22:55:21 +0000 Subject: Re: [bitcoin-dev] Transition to post-quantum X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 12 Feb 2018 21:32:38 -0000 --001a11401934db0d8605650a9d95 Content-Type: text/plain; charset="UTF-8" Hi Tim, Just read through your post, thanks for the heads up - I only just joined this mailing list. In a post-quantum world, your second "d" type transaction is completely forgeable, which means it is vulnerable to front-running. An adversary capable of breaking ECDSA needs only listen for these transactions, obtain "classic_sk" and then use a higher fee (or relationship with a miner) to effectively turn your original "d" transaction into a double-spend, with the forged transaction sending all your funds to the adversary. I'm pretty confident that a PQ DSA is required to prevent front-running, and that no "commit-reveal" scheme will be secure without one. The other issue with your approach is that if it is rolled out today, it will effectively double transaction volumes - this is what I tried to solve in solutions 2 and 3 in my article by instead modifying the address generation process. Regards, Tristan On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Hi Tristan, > > Regarding the "Post-Quantum Address Recovery" part (I haven't read the > other parts), you may be interested in my message to the list from last > month and the rest of the thread: > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/ > 2018-January/015659.html > > This is an approach which aims to avoid the issues that you've > mentioned in your blog post. > > Best, > Tim > > On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev wrote: > > Hi all, > > > > Recently I've been exploring what a post-quantum attack on Bitcoin > > would actually look like, and what options exist for mitigating it. > > > > I've put up a draft of my research here: https://medium.com/@tristanh > > oy/11271f430c41 > > > > In summary: > > 1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are > > scalable > > 2) This is a rapidly advancing space and committment to a specific > > post-quantum DSA now would be premature > > 3) I've identified a strategy (solution 3 in the draft) that > > mitigates against the worst case scenario (unexpectedly early attack > > on ECDSA) without requiring any changes to the Bitcoin protocol or > > total committment to a specific post-quantum DSA that will likely be > > superseded in the next 3-5 years > > 4) This strategy also serves as a secure means of transferring > > balances into a post-quantum DSA address space, even in the event > > that ECDSA is fully compromised and the transition is reactionary > > > > The proposal is a change to key generation only and will be > > implemented by wallet providers. > > > > Feedback would be most appreciated. > > > > Regards, > > > > Tristan > > _______________________________________________ > > bitcoin-dev mailing list > > bitcoin-dev@lists.linuxfoundation.org > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --001a11401934db0d8605650a9d95 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Tim,

Just read through your post, th= anks for the heads up - I only just joined this mailing list.
In a post-quantum world, your second "d" type transac= tion is completely forgeable, which means it is vulnerable to front-running= . An adversary capable of breaking ECDSA needs only listen for these transa= ctions, obtain "classic_sk" and then use a higher fee (or relatio= nship with a miner) to effectively turn your original "d" transac= tion into a double-spend, with the forged transaction sending all your fund= s to the adversary.

I'm pretty confident that = a PQ DSA is required to prevent front-running, and that no "commit-rev= eal" scheme will be secure without one.

The o= ther issue with your approach is that if it is rolled out today, it will ef= fectively double transaction volumes - this is what I tried to solve in sol= utions 2 and 3 in my article by instead modifying the address generation pr= ocess.

Regards,

Tris= tan

On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
Hi Tristan,

Regarding the "Post-Quantum Address Recovery" part (I haven't= read the
other parts), you may be interested in my message to the list from last
month and the rest of the thread:
https://lists.linuxf= oundation.org/pipermail/bitcoin-dev/2018-January/015659.html<= br>
This is an approach which aims to avoid the issues that you've
mentioned in your blog post.

Best,
Tim

On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev wrote:
> Hi all,
>
> Recently I've been exploring what a post-quantum attack on Bitcoin=
> would actually look like, and what options exist for mitigating it. >
> I've put up a draft of my research here: https://medium.com/@tr= istanh
> oy/11271f430c41
>
> In summary:
> 1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are
> scalable
> 2) This is a rapidly advancing space and committment to a specific
> post-quantum DSA now would be premature
> 3) I've identified a strategy (solution 3 in the draft) that
> mitigates against the worst case scenario (unexpectedly early attack > on ECDSA) without requiring any changes to the Bitcoin protocol or
> total committment to a specific post-quantum DSA that will likely be > superseded in the next 3-5 years
> 4) This strategy also serves as a secure means of transferring
> balances into a post-quantum DSA address space, even in the event
> that ECDSA is fully compromised and the transition is reactionary
>
> The proposal is a change to key generation only and will be
> implemented by wallet providers.
>
> Feedback would be most appreciated.
>
> Regards,
>
> Tristan
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@l= ists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev

--001a11401934db0d8605650a9d95--