From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ; 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 To: Bitcoin Development Mailing List Message-Id: <5fcbe15c-2793-44a7-88d1-e708c224f2fdn@googlegroups.com> In-Reply-To: References: 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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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:

> 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 validate= s
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 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.

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!

Regards,
AdamISZ/waxwing
=C2=A0

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/5fcbe15c-2793-44a7-88d1-e708c224f2fdn%40googlegroups.com.
------=_Part_99303_1229769954.1737736727642-- ------=_Part_99302_519076367.1737736727642--