📅 Original date posted:2018-02-13
📝 Original message: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 <bitcoin
>> -dev at 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 at lists.linuxfoundation.org
>>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitcoin-dev at lists.linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Tristan Hoy [ARCHIVE] /
npub1ep…fu796
2023-06-07 18:10:37
in reply to nevent1q…wgxe
Author Public Key
npub1ep2e4afh7kpasqeed62j0x4hfda7junmaumuhtfrz48qlg7d8qys4fu796Seen on
wss://relay.noswhere.comPublished at
2023-06-07 18:10:37Event JSON
{
"id": "9990f13629c151fe4d24710720c0107aeb7d87fbdcc7e2a89c0944fce2d64254",
"pubkey": "c8559af537f583d803396e95279ab74b7be9727bef37cbad23154e0fa3cd3809",
"created_at": 1686161437,
"kind": 1,
"tags": [
[
"e",
"74cac95639ddcdb0a3025aa02802000639d0d8a449d57b4ca47e5dcff3c843f3",
"",
"root"
],
[
"e",
"85a6ed5157417b24bb8eadd81257147563989ab87857f173a6f4651708f0e789",
"",
"reply"
],
[
"p",
"c6d7a400897460d9a2c07bbad58731b6d04267edd75af42af45f471b04581ec2"
]
],
"content": "📅 Original date posted:2018-02-13\n📝 Original message:On 13/02/2018 5:46 PM, Tim Ruffing via bitcoin-dev wrote:\n\u003e On Tue, 2018-02-13 at 08:32 +1100, Tristan Hoy wrote:\n\u003e\u003e In a post-quantum world, your second \"d\" type transaction is\n\u003e\u003e completely forgeable, which means it is vulnerable to front-running.\n\u003e\u003e An adversary capable of breaking ECDSA needs only listen for these\n\u003e\u003e transactions, obtain \"classic_sk\" and then use a higher fee (or\n\u003e\u003e relationship with a miner) to effectively turn your original \"d\"\n\u003e\u003e transaction into a double-spend, with the forged transaction sending\n\u003e\u003e all your funds to the adversary.\n\u003e That's not true. The d(ecommit) transaction, or better let's call it\n\u003e \"decommit step\" of a two-step transaction does not specify the effects\n\u003e (output script). This is what I denote by \"tx\" in the writeup, and it's\n\u003e already fixed by the c(ommit) step.\n\u003e\n\u003e So yes, if the user finally reveals\n\u003e d = classic_pk||Sign(classic_sk, tx)\n\u003e a quantum attacker can indeed forge\n\u003e d' = classic_pk||Sign(classic_sk, tx')\n\u003e for tx' != tx of his choice. But that won't help him, because the first\n\u003e valid c step in the chain is for tx and not for tx'.\nThank you for clarifying, I should have caught that.\n\n\u003e\u003e The other issue with your approach is that if it is rolled out today,\n\u003e\u003e it will effectively double transaction volumes - this is what I tried\n\u003e\u003e to solve in solutions 2 and 3 in my article by instead modifying the\n\u003e\u003e address generation process.\n\u003e Yep, it needs two entries in the blockchain, and that does not mean\n\u003e that it doubles the data. It will need some more bytes in the\n\u003e blockchain but also proper PQ-transactions could need more bytes in the\n\u003e blockchain, so I don't think that's the major issue.\n\u003e\nThe worst-case outcome is that ECDSA is broken before PQ addresses are \nrolled out. There is no reactive response to this - all the existing \nECDSA addresses will be compromised. A proactive measure is required, \nand it should be deployed sooner rather than later.\n\nAny two-step approach adopted now as a proactive measure will not only \nbloat the blockchain, it will also double the effective confirmation \ntime - for all transactions between now and when PQ addresses are rolled \nout, which seems unlikely to happen in the next 5 years. The bloat will \nbe permanent.\n\nEither way, would you mind if I included your approach in the article, \nwith credit? I will seek your review before publishing.\n\n\u003e\u003e Regards,\n\u003e\u003e\n\u003e\u003e Tristan\n\u003e\u003e\n\u003e\u003e On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev \u003cbitcoin\n\u003e\u003e -dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\u003e\u003e Hi Tristan,\n\u003e\u003e\u003e\n\u003e\u003e\u003e Regarding the \"Post-Quantum Address Recovery\" part (I haven't read\n\u003e\u003e\u003e the\n\u003e\u003e\u003e other parts), you may be interested in my message to the list from\n\u003e\u003e\u003e last\n\u003e\u003e\u003e month and the rest of the thread:\n\u003e\u003e\u003e https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Januar\n\u003e\u003e\u003e y/015659.html\n\u003e\u003e\u003e\n\u003e\u003e\u003e This is an approach which aims to avoid the issues that you've\n\u003e\u003e\u003e mentioned in your blog post.\n\u003e\u003e\u003e\n\u003e\u003e\u003e Best,\n\u003e\u003e\u003e Tim\n\u003e\u003e\u003e\n\u003e\u003e\u003e On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev\n\u003e\u003e\u003e wrote:\n\u003e\u003e\u003e\u003e Hi all,\n\u003e\u003e\u003e\u003e\n\u003e\u003e\u003e\u003e Recently I've been exploring what a post-quantum attack on\n\u003e\u003e\u003e Bitcoin\n\u003e\u003e\u003e\u003e would actually look like, and what options exist for mitigating\n\u003e\u003e\u003e it.\n\u003e\u003e\u003e\u003e I've put up a draft of my research here: https://medium.com/@tris\n\u003e\u003e\u003e tanh\n\u003e\u003e\u003e\u003e oy/11271f430c41\n\u003e\u003e\u003e\u003e\n\u003e\u003e\u003e\u003e In summary:\n\u003e\u003e\u003e\u003e 1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are\n\u003e\u003e\u003e\u003e scalable\n\u003e\u003e\u003e\u003e 2) This is a rapidly advancing space and committment to a\n\u003e\u003e\u003e specific\n\u003e\u003e\u003e\u003e post-quantum DSA now would be premature\n\u003e\u003e\u003e\u003e 3) I've identified a strategy (solution 3 in the draft) that\n\u003e\u003e\u003e\u003e mitigates against the worst case scenario (unexpectedly early\n\u003e\u003e\u003e attack\n\u003e\u003e\u003e\u003e on ECDSA) without requiring any changes to the Bitcoin protocol\n\u003e\u003e\u003e or\n\u003e\u003e\u003e\u003e total committment to a specific post-quantum DSA that will likely\n\u003e\u003e\u003e be\n\u003e\u003e\u003e\u003e superseded in the next 3-5 years\n\u003e\u003e\u003e\u003e 4) This strategy also serves as a secure means of transferring\n\u003e\u003e\u003e\u003e balances into a post-quantum DSA address space, even in the event\n\u003e\u003e\u003e\u003e that ECDSA is fully compromised and the transition is reactionary\n\u003e\u003e\u003e\u003e\n\u003e\u003e\u003e\u003e The proposal is a change to key generation only and will be\n\u003e\u003e\u003e\u003e implemented by wallet providers.\n\u003e\u003e\u003e\u003e\n\u003e\u003e\u003e\u003e Feedback would be most appreciated.\n\u003e\u003e\u003e\u003e\n\u003e\u003e\u003e\u003e Regards,\n\u003e\u003e\u003e\u003e\n\u003e\u003e\u003e\u003e Tristan\n\u003e\u003e\u003e\u003e _______________________________________________\n\u003e\u003e\u003e\u003e bitcoin-dev mailing list\n\u003e\u003e\u003e\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e\u003e\u003e\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\u003e\u003e _______________________________________________\n\u003e\u003e\u003e bitcoin-dev mailing list\n\u003e\u003e\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e\u003e\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\u003e\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev",
"sig": "9a976c47a43804ef261688fa112077aef3940ff760eeacef1c032ba98116bcb11cc49324fb2cfd7a220fdce8b97a1eb996259a988370909de7da7c7c8d69635f"
}