Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id DB33BD97 for ; Tue, 13 Feb 2018 10:06:36 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ot0-f193.google.com (mail-ot0-f193.google.com [74.125.82.193]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 33B9942D for ; Tue, 13 Feb 2018 10:06:36 +0000 (UTC) Received: by mail-ot0-f193.google.com with SMTP id q12so16807364otg.10 for ; Tue, 13 Feb 2018 02:06:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:to:references:from:message-id:date:user-agent:mime-version :in-reply-to:content-transfer-encoding:content-language; bh=3WM/Z1wx7DVr54fJAtuV/L7288JZcBoPjefM0EL11eI=; b=baROAq82wGaIAi0uuCkoHj2vsdDWJFmPm8kGskZH7QzSbwAmvOjOpbOElk4ofxnL/8 ceKg1+XGpnn2lAyHrUUQ/EW02HsobT9H638XhX79mu0EoyWf6JE2bJQ2SBmf/5EhCppy SsIGR4FM2jBG1TET5TPnOJkqsYwzDQksXs4e8XVVZ64Zx+CNPgczR0ZY5XBByGhd/tJq xm44UbNVfCVTlE1A4xnGX4rMLphEViygjJvxHAiO84TDOaA7HLhi9G1io8Mta9XMwDDy Cm1Pub3nCJqI3s96OtelAsL0qhr6Jc4jrXx/e4nBfxub3q/SEQF2fE/9FJpiDFg18rIW U0+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=3WM/Z1wx7DVr54fJAtuV/L7288JZcBoPjefM0EL11eI=; b=Y/4xfPuD7/NXWsBlQvm/4TijKjP3cmd9zuVd7ytU3wdU27XyDNjijCMh8S2SGuwS2C 1K+2KXFH1MsniD8lsVdgzqJkCIM61SasDkLxjznevTJXJPVAIbiB+oNK5SnHAAO8c9ny mo2YkLuhm33QdHUSS0mJuzagTilcvSAFx0r2SvujdTzSux4PfSgAoxZ1j+GBA0RzZ3+3 OHDaM/DgzNoGlR7DcUTXdReAFajpkFJFHVFGZYSttEpZMIdCpkQPkfF4GF4sqw/nswPg LWEX85bFy09GH/FqaYeYXM8iKzBUhZtugmGqW2L7OlJqMaYNfWjR//Xj15avsIpv0Dlm +0ZA== X-Gm-Message-State: APf1xPCrmcbFxS1AACtTyoRXsDobsUNst17x2SKeJwCK0x3lOFdTqCSY Vl6APIQpwBwcRVLvTD1MC03PZ9v9 X-Google-Smtp-Source: AH8x226lIGJ822ZvlviA/A23ZvFE+ezosHhS2IGcdj/rEeyxdLZvTDHiQcu1QvQmWbryZ69Mr96XwQ== X-Received: by 10.157.51.54 with SMTP id f51mr465193otc.145.1518516394859; Tue, 13 Feb 2018 02:06:34 -0800 (PST) Received: from [172.16.19.228] (59-100-254-154.syd.static-ipl.aapt.com.au. [59.100.254.154]) by smtp.gmail.com with ESMTPSA id c34sm6020596otd.16.2018.02.13.02.06.32 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 13 Feb 2018 02:06:33 -0800 (PST) To: bitcoin-dev@lists.linuxfoundation.org References: <1518450650.7829.87.camel@mmci.uni-saarland.de> <1518504374.9878.24.camel@mmci.uni-saarland.de> From: Tristan Hoy Message-ID: <882306fa-3ea0-99bd-61c6-f646d27c2ab6@gmail.com> Date: Tue, 13 Feb 2018 21:06:31 +1100 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.6.0 MIME-Version: 1.0 In-Reply-To: <1518504374.9878.24.camel@mmci.uni-saarland.de> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Content-Language: en-US X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, 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: Tue, 13 Feb 2018 14:05:10 +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: Tue, 13 Feb 2018 10:06:37 -0000 On 13/02/2018 5:46 PM, Tim Ruffing via bitcoin-dev wrote: > On Tue, 2018-02-13 at 08:32 +1100, Tristan Hoy wrote: >> 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. > That's not true. The d(ecommit) transaction, or better let's call it > "decommit step" of a two-step transaction does not specify the effects > (output script). This is what I denote by "tx" in the writeup, and it's > already fixed by the c(ommit) step. > > So yes, if the user finally reveals > d = classic_pk||Sign(classic_sk, tx) > a quantum attacker can indeed forge > d' = classic_pk||Sign(classic_sk, tx') > for tx' != tx of his choice. But that won't help him, because the first > valid c step in the chain is for tx and not for tx'. Thank you for clarifying, I should have caught that. >> 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. > Yep, it needs two entries in the blockchain, and that does not mean > that it doubles the data. It will need some more bytes in the > blockchain but also proper PQ-transactions could need more bytes in the > blockchain, so I don't think that's the major issue. > The worst-case outcome is that ECDSA is broken before PQ addresses are rolled out. There is no reactive response to this - all the existing ECDSA addresses will be compromised. A proactive measure is required, and it should be deployed sooner rather than later. Any two-step approach adopted now as a proactive measure will not only bloat the blockchain, it will also double the effective confirmation time - for all transactions between now and when PQ addresses are rolled out, which seems unlikely to happen in the next 5 years. The bloat will be permanent. Either way, would you mind if I included your approach in the article, with credit? I will seek your review before publishing. >> Regards, >> >> Tristan >> >> On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev > -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-Januar >>> y/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/@tris >>> tanh >>>> 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 >> > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev