From: waxwing/ AdamISZ <ekaggata@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] On (in)ability to embed data into Schnorr
Date: Sun, 2 Nov 2025 05:30:44 -0800 (PST) [thread overview]
Message-ID: <31d18bd9-62e0-4035-b04f-f70ff4253257n@googlegroups.com> (raw)
In-Reply-To: <CAN7kyNgyoA5rb8hYuxai6bSaPdon=y=9Z+dAfqP6Mf=PyniJLw@mail.gmail.com>
[-- Attachment #1.1: Type: text/plain, Size: 4249 bytes --]
> 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.
[-- Attachment #1.2: Type: text/html, Size: 4720 bytes --]
prev parent reply other threads:[~2025-11-02 13:33 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-10-01 14:24 waxwing/ AdamISZ
2025-10-01 22:10 ` Greg Maxwell
2025-10-01 23:11 ` Andrew Poelstra
2025-10-02 0:25 ` waxwing/ AdamISZ
2025-10-02 15:56 ` waxwing/ AdamISZ
2025-10-02 19:49 ` Greg Maxwell
2025-10-06 13:04 ` waxwing/ AdamISZ
2025-10-03 13:24 ` Peter Todd
2025-10-04 2:39 ` waxwing/ AdamISZ
2025-10-07 8:22 ` Anthony Towns
2025-10-07 12:05 ` waxwing/ AdamISZ
2025-10-08 5:12 ` Anthony Towns
2025-10-08 12:55 ` waxwing/ AdamISZ
2025-10-31 9:10 ` Tim Ruffing
2025-10-31 13:09 ` waxwing/ AdamISZ
2025-10-31 13:19 ` Garlo Nicon
2025-11-01 14:49 ` waxwing/ AdamISZ
2025-11-02 9:11 ` Garlo Nicon
2025-11-02 13:30 ` waxwing/ AdamISZ [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=31d18bd9-62e0-4035-b04f-f70ff4253257n@googlegroups.com \
--to=ekaggata@gmail.com \
--cc=bitcoindev@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox