From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Sun, 02 Nov 2025 05:33:14 -0800 Received: from mail-oa1-f63.google.com ([209.85.160.63]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1vFYCn-0006Cu-BW for bitcoindev@gnusha.org; Sun, 02 Nov 2025 05:33:14 -0800 Received: by mail-oa1-f63.google.com with SMTP id 586e51a60fabf-3c9b84808c1sf7134143fac.0 for ; Sun, 02 Nov 2025 05:33:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1762090387; x=1762695187; 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=shVsZaFdq04HdzBJKQzMMLDZ/z1lLxq68C4aI1MtkHs=; b=bexaPfty73utNtcDacrlhCfDcLN+Vf634FqWRJ8zzwmfyofJS/e+eospI2YCXWYUHP a/uu3dUoOM3SB6EJSrakaVU/EVXGQfKRL+Fi2SWsTv4cL/0gA2XG0cPWPEYkxUrVP1GQ nT7A24JDPILxjbRb05lcCyJoUleLKKtGmrgFnL2p4C0AAEgdYgFW30QRgYgkQoy9j/EZ oummuX+Gp9DoxbYL+BiR3COcLFlRaK6xqN00ZjKQraYj07TkcGLdkUSscIHaTyZu43DR FD/jXrxLns1Z8D1BiiZ0eR8jbGEJh4OGYNRvtKYezGs/YXYbOmSTYMQGe+jELfadho1o s1Tg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762090387; x=1762695187; 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=shVsZaFdq04HdzBJKQzMMLDZ/z1lLxq68C4aI1MtkHs=; b=erdxmdnpiRhhWiB2Btx+mcxQvalVLkkyWwmHQpEIM4oOjWn/yJOxYFp6laDqBu8f3g O5wCefyNNgyhEm3GnC9wW73bTyJpe9oMra+Idl95JiuIv/f5pS1Fev5hJ/53z8uvId/k 6Tit/Wh+SDeJ7pIGTn5vrBWBhi/tIk4ARUWwmdZMZvWxWnpi/3xt0/b3cyDLkjA30yH1 WIgdxx2a66SzeBrKuW608+EgXcJK2XFCA7Kk01QbBq4uhROZ/r8ulDdF083sWx1BHn/o XnOieoEOEAD6r1Ry+CmiRZ9QWTTTdKK/A/jSvF3r0SogoluzFnIf6LFsDqRXZzOKUuRL g1cQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762090387; x=1762695187; 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=shVsZaFdq04HdzBJKQzMMLDZ/z1lLxq68C4aI1MtkHs=; b=PX6FyqG/Oy7dhGR1h7EqfHoY2wiWhaQtORVQtRQffOB14x2VmCzwner7aiuezNzcnk RWq5u1y4nl7VaHY7tA1cSX2I6e6ZoNVh/avNPMTwoB5iDBxIOpS8D9/RN+yh3tdcnnOF EUByaV9xABnWtYWnexAQVu6NuOSVSgDCHtENsCJ+SuPxb3dLA0bRaBISnpx/yEenla9r K6KIBPRteZs95e/opOEQ8V1tLpmlcw8BV8z1uolpFmBpnBWeFlBgqHBmxaXmZtZFBixR c7GkpVUH44O46PSyj3xayZy0TNYK5roipEZQy3IX/r9OpcIpbpcBvzpZDNh2dOhxdgLU FRBg== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCWXZOy3ejKok2xLLjZN5emdrMkcr4//wL1F7pkWBlCP0XYppp6fcbbdSxaQntmtVPVNfShH9rnwHE3y@gnusha.org X-Gm-Message-State: AOJu0YwJdhjrTLe84VWyPAp09/dSd/Mo3p8a10bRfpjPeBnis2lmF5Jb P1svDlpM6Vd8iCyGFVHTWGArTVV48HBwXAnhoddh1jYP87JvcA1+fSWh X-Google-Smtp-Source: AGHT+IH/5AbgkMq7rjq1f5+F7vSRvwx18URphseXcNWTxMmawcPb8i2YOHzjFb9weGiqeBGQiBjBVw== X-Received: by 2002:a05:6871:740f:b0:2ff:d8bb:fc26 with SMTP id 586e51a60fabf-3dacc6d7fcfmr4482199fac.35.1762090386647; Sun, 02 Nov 2025 05:33:06 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h="Ae8XA+bCpMRWbkp1lgX62mVPsXN09PIyd4/m5x176ExwF5htlg==" Received: by 2002:a05:6870:a093:b0:363:4ae7:c37f with SMTP id 586e51a60fabf-3d8b946edfcls2474645fac.0.-pod-prod-05-us; Sun, 02 Nov 2025 05:33:02 -0800 (PST) X-Received: by 2002:a05:6808:2198:b0:44f:6a32:537a with SMTP id 5614622812f47-44f95fda150mr4462393b6e.46.1762090382665; Sun, 02 Nov 2025 05:33:02 -0800 (PST) Received: by 2002:a05:690c:dc1:b0:785:e55d:2dfd with SMTP id 00721157ae682-78649982b58ms7b3; Sun, 2 Nov 2025 05:30:45 -0800 (PST) X-Received: by 2002:a05:690e:4296:10b0:63f:a103:5d3d with SMTP id 956f58d0204a3-63fa1036164mr3672289d50.45.1762090244610; Sun, 02 Nov 2025 05:30:44 -0800 (PST) Date: Sun, 2 Nov 2025 05:30:44 -0800 (PST) From: waxwing/ AdamISZ To: Bitcoin Development Mailing List Message-Id: <31d18bd9-62e0-4035-b04f-f70ff4253257n@googlegroups.com> In-Reply-To: References: <0f6c92cc-e922-4d9f-9fdf-69384dcc4086n@googlegroups.com> <781840dd-b633-4d87-b05d-d389c6374d63n@googlegroups.com> Subject: Re: [bitcoindev] On (in)ability to embed data into Schnorr MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_218048_1944381813.1762090244046" 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_218048_1944381813.1762090244046 Content-Type: multipart/alternative; boundary="----=_Part_218049_2094162489.1762090244046" ------=_Part_218049_2094162489.1762090244046 Content-Type: text/plain; charset="UTF-8" > I already told you, when I said "known plaintext attack". If you want to put random data into private keys or signatures, then things are hard to break. However, if it is something useful for the reader, then usually, that kind of data are non-random. For example: some users store transactions inside OP_RETURNs, and they use ASCII hex representation. If they would use binary encoding, then they would save 50% space. But people simply don't care. > And the similar case is possible here: if you want to store random data, then it is hard to use this method. However, if you want to store ASCII text, where many words can be found in a dictionary, or where the format of the data is known upfront, or can be easily guessed, then the security of the keys, is comparable to the brainwallets. > Which means, that you can just put your data into the private key of the user, and a "signature nonce" (which is nothing else, but yet another private key, placed on secp256k1). And then, if you know, that your data, is for example "ASCII string", then it means, that each and every key, that you produce, simply leaks at least 32 bits per 256-bit key, if not more. Ah, right; I had originally written a response to this idea but then discarded it on the basis that it's kinda "obvious" that we shouldn't think about that, and focused on the more in-the-weeds concept of a lattice attack instead. But it isn't obvious. So let's think of the spectrum here. First, the most trivial nonce to break: one consisting of a single bit (OK technically you can't encode k=0, heh, but, whatever, put it in the second bit of the string). Obviously that is extractable, getting 32 bytes plus one bit. That one extra bit above the 33% is achievable because of "grinding" except here grinding is the most trivial version possible: trying 2 alternatives. This still fits my original claim, which is "33% plus whatever you can get from grinding, and you leak the secret key in the process". Other end of the spectrum: not 1 bit or 5 bytes but say 20 bytes represent an actual message, and let's say the rest of the 256 bit k-string is zero. Now clearly one can't grind that, if it's random. Which brings us to your point about weakness: let's say the 20 bytes of message comes from a space of possible messages, known to all potential readers, whose size is actually 40 bits. Because they can grind 40 bits, they can retrieve the message, but that message is only 40 bits of information. E.g. most crude idea; a table of 2^40 messages, you are picking one .. notice it doesn't matter if the length of each message is 40 bits or 160 bits or 256 bits; you are only conveying 40 bits of *information* if you do this. >From this point of view it's pretty clear that we haven't changed the general conclusion: you only get 33% (say 32 bytes), *plus* whatever you can get from grinding, and since that's exponential work, it's never going to be very big, say 5 bytes or possibly 6? And you leak the key of course. I do agree with you that there could be scenarios where this "mode" of publication/embedding might be the preferable one, because we're gliding over that line between "pure publication" and "publication with sidechannels". As I argued here and elsewhere, if there is a proper, viable, sidechannel, then most of this analysis doesn't apply but a sort of mixup where "if you know information X you can grind out more information Y from the onchain data" is possible. But no, as per the above, you are definitely not conveying 66% (that is to say , 64 bytes out of 96) in the P, R, s tuple using this method. That'd only be true in the sense that if the space of possible messages is "hello world\n\n" and "goodbye world" and then you claimed you were sending 13 bytes because a reader can find the message. Cheers, 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/31d18bd9-62e0-4035-b04f-f70ff4253257n%40googlegroups.com. ------=_Part_218049_2094162489.1762090244046 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable > I already told you, when I said "known plaintext attack". If you want = to put random data into private keys or signatures, then things are hard to= break. However, if it is something useful for the reader, then usually, th= at kind of data are non-random. For example: some users store transactions = inside OP_RETURNs, and they use ASCII hex representation. If they would use= binary encoding, then they would save 50% space. But people simply don't c= are.

> And the similar case is possible here: if you want to = store random data, then it is hard to use this method. However, if you want= to store ASCII text, where many words can be found in a dictionary, or whe= re the format of the data is known upfront, or can be easily guessed, then = the security of the keys, is comparable to the brainwallets.

>= ; Which means, that you can just put your data into the private key of the = user, and a "signature nonce" (which is nothing else, but yet another priva= te key, placed on secp256k1). And then, if you know, that your data, is for= example "ASCII string", then it means, that each and every key, that you p= roduce, simply leaks at least 32 bits per 256-bit key, if not more.
Ah, right; I had originally written a response to this idea b= ut then discarded it on the basis that it's kinda "obvious" that we shouldn= 't think about that, and focused on the more in-the-weeds concept of a latt= ice attack instead.

But it isn't obvious.
<= div>
So let's think of the spectrum here. First, the most t= rivial nonce to break: one consisting of a single bit (OK technically you c= an't encode k=3D0, heh, but, whatever, put it in the second bit of the stri= ng). Obviously that is extractable, getting 32 bytes plus one bit. That one= extra bit above the 33% is achievable because of "grinding" except here gr= inding is the most trivial version possible: trying 2 alternatives. This st= ill fits my original claim, which is "33% plus whatever you can get from gr= inding, and you leak the secret key in the process".

=
Other end of the spectrum: not 1 bit or 5 bytes but say 20 bytes repre= sent an actual message, and let's say the rest of the 256 bit k-string is z= ero. Now clearly one can't grind that, if it's random. Which brings us to y= our point about weakness: let's say the 20 bytes of message comes from a sp= ace of possible messages, known to all potential readers, whose size is act= ually 40 bits. Because they can grind 40 bits, they can retrieve the messag= e, but that message is only 40 bits of information. E.g. most crude idea; a= table of 2^40 messages, you are picking one .. notice it doesn't matter if= the length of each message is 40 bits or 160 bits or 256 bits; you are onl= y conveying 40 bits of *information* if you do this.

=
From this point of view it's pretty clear that we haven't changed the = general conclusion: you only get 33% (say 32 bytes), *plus* whatever you ca= n get from grinding, and since that's exponential work, it's never going to= be very big, say 5 bytes or possibly 6? And you leak the key of course.

I do agree with you that there could be scenarios = where this "mode" of publication/embedding might be the preferable one, bec= ause we're gliding over that line between "pure publication" and "publicati= on with sidechannels". As I argued here and elsewhere, if there is a proper= , viable, sidechannel, then most of this analysis doesn't apply but a sort = of mixup where "if you know information X you can grind out more informatio= n Y from the onchain data" is possible.

But no, = as per the above, you are definitely not conveying 66% (that is to say , 64= bytes out of 96) in the P, R, s tuple using this method. That'd only be tr= ue in the sense that if the space of possible messages is "hello world\n\n"= and "goodbye world" and then you claimed you were sending 13 bytes because= a reader can find the message.

Cheers,
Ada= mISZ/waxwing

--
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/31d18bd9-62e0-4035-b04f-f70ff4253257n%40googlegroups.com.
------=_Part_218049_2094162489.1762090244046-- ------=_Part_218048_1944381813.1762090244046--