* [bitcoindev] jpeg resistance of various post-quantum signature schemes
@ 2025-05-21 10:32 'Bas Westerbaan' via Bitcoin Development Mailing List
2025-05-21 20:38 ` [bitcoindev] " Hunter Beast
0 siblings, 1 reply; 3+ messages in thread
From: 'Bas Westerbaan' via Bitcoin Development Mailing List @ 2025-05-21 10:32 UTC (permalink / raw)
To: bitcoindev
[-- Attachment #1: Type: text/plain, Size: 5422 bytes --]
Hi all,
My colleague Ethan asked me the fun question which post-quantum signature
schemes have the following security property, which he called jpeg
resistance.
Attacker wins if for a (partially specified) signature and full message,
they can find a completed signature and public key, such that the completed
signature verifies under the public key.
A naive hash-based signature is not jpeg resistant. Schoolbook Winternitz
one-time signatures, forest-of-trees few-time signatures, and Merkle trees
all validate signatures (/authentication paths) by recomputing the public
key (/Merkle tree root) from the signature and the message, and checking
whether the recomputed public key matches the actual public key. That means
we can pick anything for the signature, and just set the public key to the
recomputed public key.
The situation is more subtle for actual standardized hash-based signatures.
RFC 8391 XMSS doesn’t sign the message itself, but first hashes in (among
others) the public key. Basically the best we can do for XMSS (except for
setting the signature randomizer) is to guess the public key. Thus it’s
pretty much jpeg resistant.
The situation is different again for RFC 8391 XMSSMT. XMSSMT is basically a
certificate chain of XMSS signatures. An XMSSMT public key is an XMSS
public key. An XMSSMT signature is a chain of XMSS signatures: the XMSSMT
public key signs another XMSS public key; which signs another public XMSS
public key; …; which signs the message. Again the top XMSSMT public key is
hashed into the message signed, but that only binds the first XMSS
signature. We can’t mess with the first signature, but the other signatures
we can choose freely, as those roots are not bound. Thus XMSSMT with two
subtrees is only half jpeg resistant and it gets worse with more subtrees.
Similarly SLH-DSA (FIPS 205, née SPHINCS+) is a certificate chain of (a
variant of) XMSS signing another XMSS public key, which signs another XMSS
public key, etc, which signs a FORS public key, which signs the final
message. The SLH-DSA public key is the first XMSS public key. From the
message and the public key it derives the FORS key pair (leaf) in the hyper
tree to use to sign, and the message to actually sign. This means we can’t
mess with the first XMSS keypair. Thus to attack SLH-DSA we honestly
generate the first XMSS keypair. Then given a message, we just pick the
signature arbitrarily for all but the first XMSS signature. We run the
verification routine to recompute the root to sign by the first XMSS
keypair. Then we sign it honestly. It depends a bit on the parameters, but
basically we get to pick roughly ⅞ of the signature for free.
ML-DSA (FIPS 204, née Dilithium) is a Fiat–Shamir transform of a
(module-)lattice identification scheme. In the identification scheme the
prover picks a nonce y, and sends the commitment w1 = HighBits(A y) to the
verifier, where A is a matrix that’s part of the public key and HighBits
drops the lower bits (of the coefficients of the polynomials in the
vector). The verifier responds with a challenge c, to which the prover
returns the response z = y + c s1, where s1 is part of the private key. The
verifier checks, among other things, whether HighBits(Az-ct) = w1, where t
= As1+s2 is part of the public key. As usual with Fiat–Shamir, in ML-DSA
the challenge c is the hash of the commitment, message, and public key. The
scheme has commitment recovery, so the signature itself consists of the
response z and the challenge c. (There is also a hint h, but that’s small
and we can ignore it.) If we set s1 to zero, then z=y, which is free to
choose. So we can freely choose z, which is by far the largest part of the
signature. Such a public key t is easy to detect, as it has small
coefficients. Instead we can set s1 to zero on only a few components. That
allows us to choose z arbitrarily for those components, still breaking jpeg
resistance, while being hard to detect. There could well be other
approaches here.
Falcon. A Falcon private key are small polynomials f,g. Its public key is h
= g f-1. With the private key, for any polynomial c, we can compute small s1
and s2 with s1 + s2h = c. A Falcon signature is a pair r, s2 where s1 =
H(r, m) - s2 h is small. s2 is Guassian distributed, and is encoded using
an Elias–Fano approach. It’s then padded to make signatures fixed-length.
Clearly the randomizer r can be set arbitrarily, but it’s only 40 bytes.
Putting arbitrary bytes in most of the encoding of s2 will likely yield a
sufficiently small s2. Now, I thought about using this s2 as a new g and
construct a signature that way by finding s’1 and s’2 with s’1 + s’2s1f-1 =
H(r,m), but my brother suggested a simpler approach. s2 is likely
invertible and we can set h = H(r, m)/s2. Both approaches would be thwarted
by using H(H(h), r, m) instead of H(r, m). I do not know if there is still
another attack.
Best,
Bas
--
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/CAMjbhoU%3DPCUwbhWFbqCbOdZc%2BybmREJmmt1K1TuHrCTncKH6VA%40mail.gmail.com.
[-- Attachment #2: Type: text/html, Size: 29470 bytes --]
^ permalink raw reply [flat|nested] 3+ messages in thread
* [bitcoindev] Re: jpeg resistance of various post-quantum signature schemes
2025-05-21 10:32 [bitcoindev] jpeg resistance of various post-quantum signature schemes 'Bas Westerbaan' via Bitcoin Development Mailing List
@ 2025-05-21 20:38 ` Hunter Beast
2025-05-22 12:57 ` 'Bas Westerbaan' via Bitcoin Development Mailing List
0 siblings, 1 reply; 3+ messages in thread
From: Hunter Beast @ 2025-05-21 20:38 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 7393 bytes --]
Thank you for this! It's definitely informing how we approach development
of BIP-360. SLH-DSA is concering, in that 7/8 arbitrary data would make it
about on par with the de facto witness discount. I don't want to sacrifice
SLH-DSA because it's favored due to hash-based signatures having more
confidence due to not introducing as many novel security assumptions as are
introduced with lattice cryptography.
As a result, BIP-360 will not be able to solve for JPEG resistance, and
thus there's no need to use an attestation in order to discount PQC bytes
separately. After conferring with Ethan, he points out that this simplifies
the design of BIP-360 a great deal. We'll be able to lean more on BIP-341,
just disabling keypath spends for P2QRH.
Another concern regarding SLH-DSA might be its performance, it's an order
of magnitude more costly to run than FALCON, which itself is an order of
magnitude more costly to run than secp256k1 Schnorr... So it could be a bit
of a DoS vector, especially if a discount was increased. But I still think
it's worth including for the reason I just mentioned. It may also be worth
counting QSigOps per block, with secp256k1 being 1, FALCON being 10, and
SPHINCS being 100.
We'll also be deprecating ML-DSA because it's too similar to FALCON in
terms of performance and size.
JPEG resistance and scaling will need to be solved through separate means,
perhaps with BitZip, which is what I'm calling Ethan's proposal a couple
weeks back for block-wide transaction compression scaling PQC signatures
through STARK proofs.
Will be making those changes to the BIP soon. Feedback is always welcome!
On Wednesday, May 21, 2025 at 5:20:02 AM UTC-6 Bas Westerbaan wrote:
> Hi all,
>
> My colleague Ethan asked me the fun question which post-quantum signature
> schemes have the following security property, which he called jpeg
> resistance.
>
> Attacker wins if for a (partially specified) signature and full message,
> they can find a completed signature and public key, such that the completed
> signature verifies under the public key.
>
> A naive hash-based signature is not jpeg resistant. Schoolbook Winternitz
> one-time signatures, forest-of-trees few-time signatures, and Merkle trees
> all validate signatures (/authentication paths) by recomputing the public
> key (/Merkle tree root) from the signature and the message, and checking
> whether the recomputed public key matches the actual public key. That means
> we can pick anything for the signature, and just set the public key to the
> recomputed public key.
>
> The situation is more subtle for actual standardized hash-based
> signatures. RFC 8391 XMSS doesn’t sign the message itself, but first
> hashes in (among others) the public key. Basically the best we can do for
> XMSS (except for setting the signature randomizer) is to guess the public
> key. Thus it’s pretty much jpeg resistant.
>
> The situation is different again for RFC 8391 XMSSMT. XMSSMT is basically
> a certificate chain of XMSS signatures. An XMSSMT public key is an XMSS
> public key. An XMSSMT signature is a chain of XMSS signatures: the XMSSMT
> public key signs another XMSS public key; which signs another public XMSS
> public key; …; which signs the message. Again the top XMSSMT public key
> is hashed into the message signed, but that only binds the first XMSS
> signature. We can’t mess with the first signature, but the other signatures
> we can choose freely, as those roots are not bound. Thus XMSSMT with two
> subtrees is only half jpeg resistant and it gets worse with more subtrees.
>
> Similarly SLH-DSA (FIPS 205, née SPHINCS+) is a certificate chain of (a
> variant of) XMSS signing another XMSS public key, which signs another XMSS
> public key, etc, which signs a FORS public key, which signs the final
> message. The SLH-DSA public key is the first XMSS public key. From the
> message and the public key it derives the FORS key pair (leaf) in the hyper
> tree to use to sign, and the message to actually sign. This means we can’t
> mess with the first XMSS keypair. Thus to attack SLH-DSA we honestly
> generate the first XMSS keypair. Then given a message, we just pick the
> signature arbitrarily for all but the first XMSS signature. We run the
> verification routine to recompute the root to sign by the first XMSS
> keypair. Then we sign it honestly. It depends a bit on the parameters, but
> basically we get to pick roughly ⅞ of the signature for free.
>
> ML-DSA (FIPS 204, née Dilithium) is a Fiat–Shamir transform of a
> (module-)lattice identification scheme. In the identification scheme the
> prover picks a nonce y, and sends the commitment w1 = HighBits(A y) to
> the verifier, where A is a matrix that’s part of the public key and
> HighBits drops the lower bits (of the coefficients of the polynomials in
> the vector). The verifier responds with a challenge c, to which the prover
> returns the response z = y + c s1, where s1 is part of the private key.
> The verifier checks, among other things, whether HighBits(Az-ct) = w1,
> where t = As1+s2 is part of the public key. As usual with Fiat–Shamir, in
> ML-DSA the challenge c is the hash of the commitment, message, and public
> key. The scheme has commitment recovery, so the signature itself consists
> of the response z and the challenge c. (There is also a hint h, but that’s
> small and we can ignore it.) If we set s1 to zero, then z=y, which is
> free to choose. So we can freely choose z, which is by far the largest part
> of the signature. Such a public key t is easy to detect, as it has small
> coefficients. Instead we can set s1 to zero on only a few components.
> That allows us to choose z arbitrarily for those components, still breaking
> jpeg resistance, while being hard to detect. There could well be other
> approaches here.
>
> Falcon. A Falcon private key are small polynomials f,g. Its public key is
> h = g f-1. With the private key, for any polynomial c, we can compute
> small s1 and s2 with s1 + s2h = c. A Falcon signature is a pair r, s2
> where s1 = H(r, m) - s2 h is small. s2 is Guassian distributed, and is
> encoded using an Elias–Fano approach. It’s then padded to make signatures
> fixed-length. Clearly the randomizer r can be set arbitrarily, but it’s
> only 40 bytes. Putting arbitrary bytes in most of the encoding of s2 will
> likely yield a sufficiently small s2. Now, I thought about using this s2
> as a new g and construct a signature that way by finding s’1 and s’2 with
> s’1 + s’2s1f-1 = H(r,m), but my brother suggested a simpler approach. s2
> is likely invertible and we can set h = H(r, m)/s2. Both approaches would
> be thwarted by using H(H(h), r, m) instead of H(r, m). I do not know if
> there is still another attack.
>
> Best,
>
> Bas
>
>
--
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/8a2c8743-dd0b-422c-85f9-f0350eec1162n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 31386 bytes --]
^ permalink raw reply [flat|nested] 3+ messages in thread
* [bitcoindev] Re: jpeg resistance of various post-quantum signature schemes
2025-05-21 20:38 ` [bitcoindev] " Hunter Beast
@ 2025-05-22 12:57 ` 'Bas Westerbaan' via Bitcoin Development Mailing List
0 siblings, 0 replies; 3+ messages in thread
From: 'Bas Westerbaan' via Bitcoin Development Mailing List @ 2025-05-22 12:57 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 8985 bytes --]
On Wednesday, May 21, 2025 at 10:58:00 PM UTC+2 Hunter Beast wrote:
Thank you for this! It's definitely informing how we approach development
of BIP-360. SLH-DSA is concering, in that 7/8 arbitrary data would make it
about on par with the de facto witness discount. I don't want to sacrifice
SLH-DSA because it's favored due to hash-based signatures having more
confidence due to not introducing as many novel security assumptions as are
introduced with lattice cryptography.
At present, lattices are the only viable approach to post-quantum key
agreement in TLS. If come Q-day they're broken, then it's not just Bitcoin
that's in big trouble. If you do want the certainty of hashes, you might
want to consider XMSS: that's JPEG resistant. With parameters n=16, h=20,
d=1, w=16 it has 32 byte public key and 880 byte signature can sign a
million messages, and only requires 3,000 hashes for verification [1]
(which can actually be reduced threefold.) The big downside is that if you
use the same OTS leaf twice, probably anyone can forge another signature on
that leaf. In this case you might make this mistake harder by keeping track
of the last leaf that was used for each public key. If you see a public key
sign using the same leaf a second time, you simply ignore the second
signature. This helps against an oopsie that's at least a few hours apart,
but not if you're using the same leaf twice in short succession.
Another concern regarding SLH-DSA might be its performance, it's an order
of magnitude more costly to run than FALCON, which itself is an order of
magnitude more costly to run than secp256k1 Schnorr...
I assume you're talking about signature size? Falcon-512 requires fewer
cycles to verify than secp256k1. SLH-DSA's verification is a bit slower.
There is some flexibility: SLH-DSA today assumes that a signer will make
2^64 signatures. If you drop that to say one million, then you can get
smaller parameters. You can also vary parameters to smoothly vary signature
size, verification time, and signing time. There is some momentum between
standardising new variants of SLH-DSA. See also this paper [2]. If XMSS is
too scary, you might want to consider a Bitcoin tailored variant of SLH-DSA.
We'll also be deprecating ML-DSA because it's too similar to FALCON in
terms of performance and size.
Falcon has great signature size and verification performance. Its
verification routine is also simple to implement. I do have to warn about
it's signing routine: it's quite complicated and tricky to implement
securily, especially if you want it to be fast. I don't think speed is
critical here, so I would stay away from implementations that use
floating-point accelerators. Another thing to note is that if lattice
cryptanalysis improves, the first step above Falcon-512 is Falcon-1024. A
Falcon-768 is possible (and used to be specified), but it's quite a bit
more complex.
Best,
Bas
JPEG resistance and scaling will need to be solved through separate means,
perhaps with BitZip, which is what I'm calling Ethan's proposal a couple
weeks back for block-wide transaction compression scaling PQC signatures
through STARK proofs.
Will be making those changes to the BIP soon. Feedback is always welcome!
On Wednesday, May 21, 2025 at 5:20:02 AM UTC-6 Bas Westerbaan wrote:
Hi all,
My colleague Ethan asked me the fun question which post-quantum signature
schemes have the following security property, which he called jpeg
resistance.
Attacker wins if for a (partially specified) signature and full message,
they can find a completed signature and public key, such that the completed
signature verifies under the public key.
A naive hash-based signature is not jpeg resistant. Schoolbook Winternitz
one-time signatures, forest-of-trees few-time signatures, and Merkle trees
all validate signatures (/authentication paths) by recomputing the public
key (/Merkle tree root) from the signature and the message, and checking
whether the recomputed public key matches the actual public key. That means
we can pick anything for the signature, and just set the public key to the
recomputed public key.
The situation is more subtle for actual standardized hash-based signatures.
RFC 8391 XMSS doesn’t sign the message itself, but first hashes in (among
others) the public key. Basically the best we can do for XMSS (except for
setting the signature randomizer) is to guess the public key. Thus it’s
pretty much jpeg resistant.
The situation is different again for RFC 8391 XMSSMT. XMSSMT is basically a
certificate chain of XMSS signatures. An XMSSMT public key is an XMSS
public key. An XMSSMT signature is a chain of XMSS signatures: the XMSSMT
public key signs another XMSS public key; which signs another public XMSS
public key; …; which signs the message. Again the top XMSSMT public key is
hashed into the message signed, but that only binds the first XMSS
signature. We can’t mess with the first signature, but the other signatures
we can choose freely, as those roots are not bound. Thus XMSSMT with two
subtrees is only half jpeg resistant and it gets worse with more subtrees.
Similarly SLH-DSA (FIPS 205, née SPHINCS+) is a certificate chain of (a
variant of) XMSS signing another XMSS public key, which signs another XMSS
public key, etc, which signs a FORS public key, which signs the final
message. The SLH-DSA public key is the first XMSS public key. From the
message and the public key it derives the FORS key pair (leaf) in the hyper
tree to use to sign, and the message to actually sign. This means we can’t
mess with the first XMSS keypair. Thus to attack SLH-DSA we honestly
generate the first XMSS keypair. Then given a message, we just pick the
signature arbitrarily for all but the first XMSS signature. We run the
verification routine to recompute the root to sign by the first XMSS
keypair. Then we sign it honestly. It depends a bit on the parameters, but
basically we get to pick roughly ⅞ of the signature for free.
ML-DSA (FIPS 204, née Dilithium) is a Fiat–Shamir transform of a
(module-)lattice identification scheme. In the identification scheme the
prover picks a nonce y, and sends the commitment w1 = HighBits(A y) to the
verifier, where A is a matrix that’s part of the public key and HighBits
drops the lower bits (of the coefficients of the polynomials in the
vector). The verifier responds with a challenge c, to which the prover
returns the response z = y + c s1, where s1 is part of the private key. The
verifier checks, among other things, whether HighBits(Az-ct) = w1, where t
= As1+s2 is part of the public key. As usual with Fiat–Shamir, in ML-DSA
the challenge c is the hash of the commitment, message, and public key. The
scheme has commitment recovery, so the signature itself consists of the
response z and the challenge c. (There is also a hint h, but that’s small
and we can ignore it.) If we set s1 to zero, then z=y, which is free to
choose. So we can freely choose z, which is by far the largest part of the
signature. Such a public key t is easy to detect, as it has small
coefficients. Instead we can set s1 to zero on only a few components. That
allows us to choose z arbitrarily for those components, still breaking jpeg
resistance, while being hard to detect. There could well be other
approaches here.
Falcon. A Falcon private key are small polynomials f,g. Its public key is h
= g f-1. With the private key, for any polynomial c, we can compute small s1
and s2 with s1 + s2h = c. A Falcon signature is a pair r, s2 where s1 =
H(r, m) - s2 h is small. s2 is Guassian distributed, and is encoded using
an Elias–Fano approach. It’s then padded to make signatures fixed-length.
Clearly the randomizer r can be set arbitrarily, but it’s only 40 bytes.
Putting arbitrary bytes in most of the encoding of s2 will likely yield a
sufficiently small s2. Now, I thought about using this s2 as a new g and
construct a signature that way by finding s’1 and s’2 with s’1 + s’2s1f-1 =
H(r,m), but my brother suggested a simpler approach. s2 is likely
invertible and we can set h = H(r, m)/s2. Both approaches would be thwarted
by using H(H(h), r, m) instead of H(r, m). I do not know if there is still
another attack.
Best,
Bas
[1] https://westerbaan.name/~bas/hashcalc/
[2] https://eprint.iacr.org/2024/018.pdf
--
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/e812604c-94a5-4f5f-87e8-71d178963d62n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 35690 bytes --]
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2025-05-22 13:01 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2025-05-21 10:32 [bitcoindev] jpeg resistance of various post-quantum signature schemes 'Bas Westerbaan' via Bitcoin Development Mailing List
2025-05-21 20:38 ` [bitcoindev] " Hunter Beast
2025-05-22 12:57 ` 'Bas Westerbaan' via Bitcoin Development Mailing List
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox