1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
|
Return-Path: <tim.ruffing@mmci.uni-saarland.de>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 82865FE4
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 26 Jan 2018 13:14:21 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from juno.mpi-klsb.mpg.de (srv-40-62.mpi-klsb.mpg.de [139.19.86.40])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 45CB2E2
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 26 Jan 2018 13:14:19 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed;
d=mmci.uni-saarland.de; s=mail200803;
h=Content-Transfer-Encoding:Mime-Version:Content-Type:References:In-Reply-To:Date:To:From:Subject:Message-ID;
bh=O/gtiFzdInoEsDSD2tBRfWZ5IuvlF8mUQxPyXitOXiQ=;
b=pccJOsy17YcQpU9kDKegncQqkxo/un6QampxzJq3HYb2A9kDjTytcwXTg+VmdBevARnUx+U4Jl7u7PZgNdVg15a3U6wH9n83FDHBAB9XNf7Alfrp6UacaVb0yGJcyTjP3l2Tl1yz7sx0aLtLvD4+sdscqMci3VSrZE4AEJCTHKY=;
Received: from sam.mpi-klsb.mpg.de ([139.19.86.26]:40002)
by juno.mpi-klsb.mpg.de (envelope-from
<tim.ruffing@mmci.uni-saarland.de>)
with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128)
(Exim 4.84_2) id 1ef3pg-0008J8-2C
for bitcoin-dev@lists.linuxfoundation.org;
Fri, 26 Jan 2018 14:14:18 +0100
Received: from port-92-203-194-168.dynamic.qsc.de ([92.203.194.168]:48588
helo=tonno.fritz.box) by sam.mpi-klsb.mpg.de (envelope-from
<tim.ruffing@mmci.uni-saarland.de>)
with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.84_2) id 1ef3pf-0006Ip-Lh
for bitcoin-dev@lists.linuxfoundation.org;
Fri, 26 Jan 2018 14:14:15 +0100
Message-ID: <1516972454.3107.67.camel@mmci.uni-saarland.de>
From: Tim Ruffing <tim.ruffing@mmci.uni-saarland.de>
To: bitcoin-dev@lists.linuxfoundation.org
Date: Fri, 26 Jan 2018 14:14:14 +0100
In-Reply-To: <CAAt2M19UObuaaODHXb+iW9bWMj53wGHAdjVzZgWBi-ZCCUi4Mg@mail.gmail.com>
References: <CAAS2fgTXg5kk6TyUM9dS=tf5N0_Z-GKVmzMLwTW1HxUgrqdo+Q@mail.gmail.com>
<20180123064419.GA1296@erisian.com.au>
<CAAS2fgSy8qg71M6ZOr=xj=W6y2Jbz8hwygZOUYv-Brkt0JwVaQ@mail.gmail.com>
<20180123222229.GA3801@erisian.com.au>
<CAAS2fgTNcCB2mfvCBhC_AhgxX=g8feYguGHN_VPWW0EoOOxMyA@mail.gmail.com>
<CAAt2M1-oh=_Ro6+Srit0XYburK_abQgJiW0Jx=nmNyeToA2rSA@mail.gmail.com>
<1516808291.4277.25.camel@mmci.uni-saarland.de>
<CAAt2M19csW3eTW_rrS+8+OuaG18EhqajWgLFotCrcVfSeVmrrQ@mail.gmail.com>
<1516836125.5969.11.camel@mmci.uni-saarland.de>
<CAAt2M19UObuaaODHXb+iW9bWMj53wGHAdjVzZgWBi-ZCCUi4Mg@mail.gmail.com>
Content-Type: text/plain; charset="UTF-8"
X-Mailer: Evolution 3.26.4
Mime-Version: 1.0
Content-Transfer-Encoding: 7bit
X-MPI-Local-Sender: true
X-Spam-Status: No, score=-4.3 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: [bitcoin-dev] Recovery of old UTXOs in a post-quantum world
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 26 Jan 2018 13:14:21 -0000
(changing the subject... ;))
My proposal does not include any form of expiration, so I don't see how
it should be vulnerable to the described attack.
To make this a little bit more detailed:
The user has one or more single standard UTXOs all with ECDSA public
key classic_pk and thus address SHA256(RIPEMD160((classic_pk)). The
corresponding secret key is classic_sk. Let MAC be a quantum-secure
message-authentication code, e.g., MAC(k,x)=H(k||x) for a suitable hash
function, e.g, BLAKE2 or SHA3.
The idea is to (ab)use the public key classic_pk as a key for the MAC.
To spend an UTXO with a transaction tx, the user does the following:
1. Create and publish a "transaction" c that references the address
SHA256(RIPEMD160((classic_pk)) and contains the following data:
MAC(classic_pk,tx))||tx
2. Wait until c is confirmed. (If it does not confirm, send it again as
usual).
3. Create and publish a "transaction" d with the following data:
classic_pk||Sign(classic_sk, tx)
Consensus rules:
A transaction d=classic_pk||sig spends all UTXOs with
address SHA256(RIPEMD160(classic_pk)), applying the effects of tx, if
there exists a transaction c=mac||tx in the blockchain such that
1. c is the first transaction (among all referencing the address) in
the blockchain where mac is a valid MAC for message tx under correct
key classic_pk
2. sig is valid ECDSA signature over tx under public key classic_pk
c-transactions never expire.
If the user has not published classic_pk before, this should be secure
against quantum attackers:
Before step 2, the MAC key k=classic_pk is only known to the user. So
the only valid c that the attacker can produce has the real transaction
tx, because a different transaction tx' requires the attacker to forge
the MAC. Since the user waits for confirmation, the first c in the
blockchain fulfilling conditions 1 and 2 has been created by the user.
Even if classic_pk is known, this is no less secure than "classic
spending", because we require an ECDSA signature on tx.
I'm pretty confident that I'm not overlooking an obvious attack. If I'm
wrong then please describe exactly the steps of the user and the
attacker.
Best,
Tim
On Thu, 2018-01-25 at 01:09 +0100, Natanael wrote:
>
> Den 25 jan. 2018 00:22 skrev "Tim Ruffing via bitcoin-dev" <bitcoin-d
> ev@lists.linuxfoundation.org>:
> > I think you misread my second proposal. The first step is not only
> > to
> > publish the hash but to publish a *pair* consisting of the hash and
> > the
> > transaction.
> >
> > If the attacker changes the transaction on the wire, the user does
> > not
> > care and will try again.
>
> I guess I assumed you meant it otherwise because I didn't assume you
> intended a commitment to the full transaction just without the
> asymmetric key material.
>
> You could treat it the same way as in my suggestion, let it expire
> and prune it if the key material isn't published in time.
>
> However... A sufficiently powerful attacker can deploy as soon as he
> sees your published signature and key, delay its propagation to the
> miners, force expiration and then *still* repeat the attack with his
> own forgery.
>
> Honestly, as long as we need to allow any form of expiry + relying on
> publication of the vulnerable algorithms result for verification, I
> think the weakness will remain.
>
> No expiration hurts in multiple ways like via DoS, or by locking in
> potentially wrong (or straight up malicious) transactions.
>
> ---
>
> There's one way out, I believe, which is quantum safe Zero-knowledge
> proofs. Currently STARK:s are one variant presumed quantum safe. It
> would be used to completely substitute the publication of the public
> key and signatures, and this way we don't even need two-step
> commitments.
>
> It does however likely require a hardfork to apply to old
> transactions. (I can imagine an extension block type softfork method,
> in which case old UTXO:s get locked on the mainchain to create
> equivalent valued extension block funds.)
>
> Without practical ZKP, and presuming no powerful QC attackers with
> the ability to control the network (basically NSA level attackers), I
> do think the Fawkes signature scheme is sufficient. Quantum attacks
> are likely to be very expensive anyway, for the foreseeable future.
|
