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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
Delivery-date: Fri, 24 Jan 2025 09:06:36 -0800
Received: from mail-yb1-f183.google.com ([209.85.219.183])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBDI23FE35EIBBEURZ66AMGQEHUSGAWI@googlegroups.com>)
id 1tbN8d-0003By-5A
for bitcoindev@gnusha.org; Fri, 24 Jan 2025 09:06:36 -0800
Received: by mail-yb1-f183.google.com with SMTP id 3f1490d57ef6-e398cb73918sf541590276.3
for <bitcoindev@gnusha.org>; Fri, 24 Jan 2025 09:06:35 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1737738389; x=1738343189; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:references:in-reply-to:message-id:to:from:date:sender:from
:to:cc:subject:date:message-id:reply-to;
bh=bkU1IrvrKp0ABzotJAshG0ivBjb54awy1Jux5XAx2UA=;
b=wD/PRNZDxEfo5FVhbyai6KCtql1eYStMliVMg3qIy5FsC+U4wThJ3J0m6Irky8yic2
hL9XCal7RtH6NOKbBL5cqUqQJZtyLONS3AHd1zk3N4QoDdhknCuCxz26fPZwF+q4XtoM
PVgotFR8mVpZ+Y7OxWHEhOD2gdOjl6FE9denqFx6PCrVCk3RitQJLpgF3HDE9YE1aB6/
nzoXTHY8IDDlsTBKienD+vKQKp+L276quxyy014/C5D7A+T3PnZ3cboCMkZPeUN+6uE0
ei2B4kjdZ0PNbji7EoHfBxOQCVBLBskuvZB+MTT3dMyY6o0AlYumXc23vArcWZB2UeZE
F+VQ==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1737738389; x=1738343189; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:references:in-reply-to:message-id:to:from:date:from:to:cc
:subject:date:message-id:reply-to;
bh=bkU1IrvrKp0ABzotJAshG0ivBjb54awy1Jux5XAx2UA=;
b=KNHexqgVG0qmoYJSXVfqSnBkdeUIKYbV9E1eTBjcDGP8v9VkOrNMfmAEOeTrWMtewP
1iSoF4rsUsd/OoVx3CgrheO0ObsRP7y8oFKkS0iwPGS2Ujp3Q2rcgb8u5HmgT6pyL0cF
lYj3DCYnHIVmJn8M4kk/LjwSCKLe0k47EgY9xMrK4bXp54ycsZ+ySsS2qr8kEVAJDEQ8
u2UMvK0gUTJc+PA/RKz0xEMDLwfBOAMSrmdW9XvXLZ6k7Y+R+l5PSclNkGSuN5VVY3a1
8o55qkdW5R7QOcqbZ8TirOWGZc9NzJQoTVODZxnkmyzE8HsL6BfwnEcq7Yj8kDXpRiNY
hMlw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1737738389; x=1738343189;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:references:in-reply-to:message-id:to:from:date:x-beenthere
:x-gm-message-state:sender:from:to:cc:subject:date:message-id
:reply-to;
bh=bkU1IrvrKp0ABzotJAshG0ivBjb54awy1Jux5XAx2UA=;
b=BbW64w9noDhHS0Y2S8XEHRd61waBC/I/AfmSteRQLHiLbzPWOM/5wmnRGnSqUCEzPT
kwTno7ea0kVnDUzOsQF9eS7IYl4xZO+Ud9fJHJQEXBUx4FbkytDl4UWinFiVOXfcWRf+
H5P4vfXEI5U1yX/GNGAUBVyDbgJyTyobPd3G6QVqF5dj94AEbdkeXL7Oo40vN2gb1Cia
CSbwlelvX63Yr6LuuwjWTxznNugnOnAREta312t2yeh67fkdzUsN38FHC7Lgpjp9qVmO
Cglei9t7mlrDCkA2qlLS2B1y3ugWsJflFoqVLQ+ufChNDDVOm1uf/Yz/OoR7m5aM5CbN
+Ggw==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCWz625O+KBFIw+BjvlUCVvtSaO72D9iuvuWcknYhwjEiYs+NJ/QwVwTGNxVPjnEenQ4/GUwzB4PgZos@gnusha.org
X-Gm-Message-State: AOJu0Yw8MNtoSDDx8ukYQxRXXgJ3c0pcHW7rQnoAPObGKnCY5bTz1f7k
ZloDwmbfMu0XwM5BKFcnQQP687iTD+4k2uSWj0J1J6V9R1H2/f+a
X-Google-Smtp-Source: AGHT+IFRBX8cb9xncK6VeNiFYcJfgArbhjhY+dtr4S+mH12pCkZi3LuhXwXFLC/z7jGUT7NtOsl3hQ==
X-Received: by 2002:a05:6902:138e:b0:e57:902a:66ea with SMTP id 3f1490d57ef6-e57b132653bmr10644603276.5.1737738389099;
Fri, 24 Jan 2025 09:06:29 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a25:d8c4:0:b0:e58:31ee:56ca with SMTP id 3f1490d57ef6-e584d432fc6ls201638276.1.-pod-prod-02-us;
Fri, 24 Jan 2025 09:06:25 -0800 (PST)
X-Received: by 2002:a05:690c:6406:b0:6ef:4696:f1cc with SMTP id 00721157ae682-6f6eb6b288cmr253021857b3.22.1737738385802;
Fri, 24 Jan 2025 09:06:25 -0800 (PST)
Received: by 2002:a0d:e5c3:0:b0:6f6:cfb8:3ae3 with SMTP id 00721157ae682-6f7588be4aems7b3;
Fri, 24 Jan 2025 08:38:49 -0800 (PST)
X-Received: by 2002:a05:690c:201d:b0:6f7:409c:f647 with SMTP id 00721157ae682-6f7409cfd18mr72186837b3.3.1737736728155;
Fri, 24 Jan 2025 08:38:48 -0800 (PST)
Date: Fri, 24 Jan 2025 08:38:47 -0800 (PST)
From: waxwing/ AdamISZ <ekaggata@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <5fcbe15c-2793-44a7-88d1-e708c224f2fdn@googlegroups.com>
In-Reply-To: <Z5JtilN2k7HwRRXt@petertodd.org>
References: <CAAQdECCdRVV+3ZoJhOotKEvmUV4yrV7EYWE8SOWCE1CF9tZ6Yg@mail.gmail.com>
<Z5JtilN2k7HwRRXt@petertodd.org>
Subject: Re: [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai)
deanonymization attacks
MIME-Version: 1.0
Content-Type: multipart/mixed;
boundary="----=_Part_99302_519076367.1737736727642"
X-Original-Sender: ekaggata@gmail.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
<https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.5 (/)
------=_Part_99302_519076367.1737736727642
Content-Type: multipart/alternative;
boundary="----=_Part_99303_1229769954.1737736727642"
------=_Part_99303_1229769954.1737736727642
Content-Type: text/plain; charset="UTF-8"
> The only question left for this technique is a cryptography one:
> Is it possible to create an alternate pubkey p', that such that a valid
signature s signed by arbitrary pubkey p for message m, also validates
for p' for signature s and message m? I believe the answer is no for
schnorr. But I'm not a cryptography expert, and I may have missed
something.
I've been thinking about this (to some extent digging up old analyses from
a few years back). I'm pretty sure that because of Schnorr's key-prefixing,
it is indeed not possible to do this: (specifically: given a tuple (m,
(R,s), P) that exists and for which the signature is valid, create a *new*
pubkey P2 s.t. (m, (R, s), P2) is valid. Notice this is not quite the same
as the definition of strong unforgeability (in which we analyze a specific
given key), which is an established property of Schnorr under the ROM.
Still, my argument would be that: a new P2 for which this is valid
satisfies: sG = R + e' P2, where e'=H(R,P2,m) and we previously had sG = R
+ eP, so that we require P2 = e/e' * P, but e' = H(R,P2,m) so that this
equation is insoluble under the preimage resistance of the hash function.
Does this same argument apply to ECDSA? No, definitely not because ECDSA
does not fix the pubkey into the hashing (which is of course why pubkey
recovery is possible in ECDSA, for example). From just looking at the
verification equation sR = H(m)G + R_x P, though, I guess that we cannot
actually create a new P2 for the same (R,s),m tuple, but for different
reasons: while a negation of s is still valid, that is not the issue. If we
cannot change R or s or m, we cannot change P. Apparently it's debatable
how important the ECDSA case will be, but, it's for sure interesting!
Regards,
AdamISZ/waxwing
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/5fcbe15c-2793-44a7-88d1-e708c224f2fdn%40googlegroups.com.
------=_Part_99303_1229769954.1737736727642
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
> The only question left for this technique is a cryptography one:
<br />
<br />> Is it possible to create an alternate pubkey p', that such that =
a valid
<br />signature s signed by arbitrary pubkey p for message m, also validate=
s
<br />for p' for signature s and message m? I believe the answer is no for
<br />schnorr. But I'm not a cryptography expert, and I may have missed
<br /><div>something. <br /></div><div><br /></div><div>I've been thinking =
about this (to some extent digging up old analyses from a few years back). =
I'm pretty sure that because of Schnorr's key-prefixing, it is indeed not p=
ossible to do this: (specifically: given a tuple (m, (R,s), P) that exists =
and for which the signature is valid, create a *new* pubkey P2 s.t. (m, (R,=
s), P2) is valid. Notice this is not quite the same as the definition of s=
trong unforgeability (in which we analyze a specific given key), which is a=
n established property of Schnorr under the ROM. Still, my argument would b=
e that: a new P2 for which this is valid satisfies: sG =3D R + e' P2, where=
e'=3DH(R,P2,m) and we previously had sG =3D R + eP, so that we require P2 =
=3D e/e' * P, but e' =3D H(R,P2,m) so that this equation is insoluble under=
the preimage resistance of the hash function.</div><div><br /></div><div>D=
oes this same argument apply to ECDSA? No, definitely not=C2=A0 because ECD=
SA does not fix the pubkey into the hashing (which is of course why pubkey =
recovery is possible in ECDSA, for example). From just looking at the verif=
ication equation sR =3D H(m)G + R_x P, though, I guess that we cannot actua=
lly create a new P2 for the same (R,s),m tuple, but for different reasons: =
while a negation of s is still valid, that is not the issue. If we cannot c=
hange R or s or m, we cannot change P. Apparently it's debatable how import=
ant the ECDSA case will be, but, it's for sure interesting!</div><div><br /=
></div><div>Regards,<br />AdamISZ/waxwing<br /><blockquote style=3D"margin:=
0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left=
: 1ex;">=C2=A0<br /></blockquote></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/5fcbe15c-2793-44a7-88d1-e708c224f2fdn%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/5fcbe15c-2793-44a7-88d1-e708c224f2fdn%40googlegroups.com</a>.<br />
------=_Part_99303_1229769954.1737736727642--
------=_Part_99302_519076367.1737736727642--
|
