From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Wed, 21 May 2025 13:58:07 -0700 Received: from mail-yb1-f187.google.com ([209.85.219.187]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uHqVp-0001bW-Qz for bitcoindev@gnusha.org; Wed, 21 May 2025 13:58:07 -0700 Received: by mail-yb1-f187.google.com with SMTP id 3f1490d57ef6-e7b9115c1b4sf6603133276.2 for ; Wed, 21 May 2025 13:58:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1747861080; x=1748465880; 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=uI4BJSs515Y+zEmO5Oa5cSTLRHcP9wzage+PKjuZnbg=; b=FHUutxMRXDz6jRcoCeg51vKfUHvQIig5R8iwlxVtFXfgXOZUUOD/2U4WnqDj3tw1qY 9c0yy1VnoJYuShMibS6uy940CPyGs8vcwkhZ7+R+C8VxzfWJRW0dxSouIht+AKb+j5Ge PphuvfAfxtp0LJx1JCVAOqMeoCPaire+UcrJEalKUq6y1Djr/7/f58TT9bGDBU6haygw UiBAIL1ycAcp0tlkhlXUuzwZ8Ihgk7c7cFEqsSvrz5r9gfdZt4tCK6ubaqwpZcsljfQo keGc3S9ihcd54E4le71V05ePT7DNa6qF/3Nw/4tWFo+VWDXFaPhRHwBmPldsWXdVEsRP 0cJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1747861080; x=1748465880; 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=uI4BJSs515Y+zEmO5Oa5cSTLRHcP9wzage+PKjuZnbg=; b=AEPZ25+/EdGSsXRUKDvQVkCTCtIRKWDP6ebob+/goDie2HuXwvnqx84rrK2cATYopZ X6HTC8QVmxrOTSzWoln8tc/4qRx9tIMbspqtC94iRdaP9Kx000DKNsYjuA6XO2byDKz0 19+4oGfAGZ0i2xTTtP2tod5bTaIYJYAJviPsAQSWIOIY9+Je8fL6eZAwGrBzTFNWVKfe yXcz8BzWXR17eK+IaIVJI7iYr42kmWndEmRBeCTNER6+2yHoxtMjJKIRHsmmS91Lokvy 0OrIhwMO5dKzvWE8ZbEzYAMgOGCqZmNwPxpU9o//MhrS4WCVaXaIVq0k0ng0DL2GRYzO +pNQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCUvVmEYlKcz57rkzmdSbbOg5O9QgxmwGKJH2KzwUNlxMTKKv3a+xxYCyA09lZhTD/ztQs3tHE4XRx3Q@gnusha.org X-Gm-Message-State: AOJu0Yx8C3ZNlVIASJ7raYY0cuGfTIdYPDAEc/CE1QJwJSwEEIty6TDv McMOsIFjscEkLsolsY+tF7eG5rJ3hc6V9qkKZ81ivclxyPbQE/a+TrXu X-Google-Smtp-Source: AGHT+IHi3fxIJHADn09qMwZ+LtExVa2smxHUHapyKk7VMveEwVA0mnZBUK0euvbK+2DU0+V2VBJQsg== X-Received: by 2002:a05:6902:708:b0:e7b:8529:eb28 with SMTP id 3f1490d57ef6-e7b8529ebd2mr23021813276.0.1747861079938; Wed, 21 May 2025 13:57:59 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBFLOdNiZPHkCr2zqdr40T9m8LhxHhgHE3LJTELtMp2p4w== Received: by 2002:a25:c487:0:b0:e79:3680:7e10 with SMTP id 3f1490d57ef6-e7b4fd690b3ls2621757276.1.-pod-prod-08-us; Wed, 21 May 2025 13:57:55 -0700 (PDT) X-Received: by 2002:a05:690c:3686:b0:708:39f9:ae49 with SMTP id 00721157ae682-70ca7b8b963mr303937177b3.29.1747861075653; Wed, 21 May 2025 13:57:55 -0700 (PDT) Received: by 2002:a05:690c:3107:b0:70d:fff1:fcdd with SMTP id 00721157ae682-70dfff1ffa1ms7b3; Wed, 21 May 2025 13:38:36 -0700 (PDT) X-Received: by 2002:a05:690c:3389:b0:708:3a47:3d2c with SMTP id 00721157ae682-70ca79cb5e9mr335258037b3.13.1747859915764; Wed, 21 May 2025 13:38:35 -0700 (PDT) Date: Wed, 21 May 2025 13:38:35 -0700 (PDT) From: Hunter Beast To: Bitcoin Development Mailing List Message-Id: <8a2c8743-dd0b-422c-85f9-f0350eec1162n@googlegroups.com> In-Reply-To: References: Subject: [bitcoindev] Re: jpeg resistance of various post-quantum signature schemes MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_585740_748976291.1747859915465" X-Original-Sender: hunter@surmount.systems 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: 2.4 (++) ------=_Part_585740_748976291.1747859915465 Content-Type: multipart/alternative; boundary="----=_Part_585741_1535144664.1747859915465" ------=_Part_585741_1535144664.1747859915465 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Thank you for this! It's definitely informing how we approach development= =20 of BIP-360. SLH-DSA is concering, in that 7/8 arbitrary data would make it= =20 about on par with the de facto witness discount. I don't want to sacrifice= =20 SLH-DSA because it's favored due to hash-based signatures having more=20 confidence due to not introducing as many novel security assumptions as are= =20 introduced with lattice cryptography. As a result, BIP-360 will not be able to solve for JPEG resistance, and=20 thus there's no need to use an attestation in order to discount PQC bytes= =20 separately. After conferring with Ethan, he points out that this simplifies= =20 the design of BIP-360 a great deal. We'll be able to lean more on BIP-341,= =20 just disabling keypath spends for P2QRH. Another concern regarding SLH-DSA might be its performance, it's an order= =20 of magnitude more costly to run than FALCON, which itself is an order of=20 magnitude more costly to run than secp256k1 Schnorr... So it could be a bit= =20 of a DoS vector, especially if a discount was increased. But I still think= =20 it's worth including for the reason I just mentioned. It may also be worth= =20 counting QSigOps per block, with secp256k1 being 1, FALCON being 10, and=20 SPHINCS being 100. We'll also be deprecating ML-DSA because it's too similar to FALCON in=20 terms of performance and size. JPEG resistance and scaling will need to be solved through separate means,= =20 perhaps with BitZip, which is what I'm calling Ethan's proposal a couple=20 weeks back for block-wide transaction compression scaling PQC signatures=20 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=E2=80=AFAM UTC-6 Bas Westerbaan wrote= : > Hi all, > > My colleague Ethan asked me the fun question which post-quantum signature= =20 > schemes have the following security property, which he called jpeg=20 > resistance. > > Attacker wins if for a (partially specified) signature and full message,= =20 > they can find a completed signature and public key, such that the complet= ed=20 > signature verifies under the public key. > > A naive hash-based signature is not jpeg resistant. Schoolbook Winternitz= =20 > one-time signatures, forest-of-trees few-time signatures, and Merkle tree= s=20 > all validate signatures (/authentication paths) by recomputing the public= =20 > key (/Merkle tree root) from the signature and the message, and checking= =20 > whether the recomputed public key matches the actual public key. That mea= ns=20 > we can pick anything for the signature, and just set the public key to th= e=20 > recomputed public key. > > The situation is more subtle for actual standardized hash-based=20 > signatures. RFC 8391 XMSS doesn=E2=80=99t sign the message itself, but fi= rst=20 > hashes in (among others) the public key. Basically the best we can do for= =20 > XMSS (except for setting the signature randomizer) is to guess the public= =20 > key. Thus it=E2=80=99s pretty much jpeg resistant. > > The situation is different again for RFC 8391 XMSSMT. XMSSMT is basically= =20 > a certificate chain of XMSS signatures. An XMSSMT public key is an XMSS= =20 > public key. An XMSSMT signature is a chain of XMSS signatures: the XMSSMT= =20 > public key signs another XMSS public key; which signs another public XMSS= =20 > public key; =E2=80=A6; which signs the message. Again the top XMSSMT publ= ic key=20 > is hashed into the message signed, but that only binds the first XMSS=20 > signature. We can=E2=80=99t mess with the first signature, but the other = signatures=20 > we can choose freely, as those roots are not bound. Thus XMSSMT with two= =20 > subtrees is only half jpeg resistant and it gets worse with more subtrees= . > > Similarly SLH-DSA (FIPS 205, n=C3=A9e SPHINCS+) is a certificate chain of= (a=20 > variant of) XMSS signing another XMSS public key, which signs another XMS= S=20 > public key, etc, which signs a FORS public key, which signs the final=20 > message. The SLH-DSA public key is the first XMSS public key. From the=20 > message and the public key it derives the FORS key pair (leaf) in the hyp= er=20 > tree to use to sign, and the message to actually sign. This means we can= =E2=80=99t=20 > mess with the first XMSS keypair. Thus to attack SLH-DSA we honestly=20 > generate the first XMSS keypair. Then given a message, we just pick the= =20 > signature arbitrarily for all but the first XMSS signature. We run the=20 > verification routine to recompute the root to sign by the first XMSS=20 > keypair. Then we sign it honestly. It depends a bit on the parameters, bu= t=20 > basically we get to pick roughly =E2=85=9E of the signature for free. > > ML-DSA (FIPS 204, n=C3=A9e Dilithium) is a Fiat=E2=80=93Shamir transform = of a=20 > (module-)lattice identification scheme. In the identification scheme the= =20 > prover picks a nonce y, and sends the commitment w1 =3D HighBits(A y) to= =20 > the verifier, where A is a matrix that=E2=80=99s part of the public key a= nd=20 > HighBits drops the lower bits (of the coefficients of the polynomials in= =20 > the vector). The verifier responds with a challenge c, to which the prove= r=20 > returns the response z =3D y + c s1, where s1 is part of the private key.= =20 > The verifier checks, among other things, whether HighBits(Az-ct) =3D w1,= =20 > where t =3D As1+s2 is part of the public key. As usual with Fiat=E2=80=93= Shamir, in=20 > ML-DSA the challenge c is the hash of the commitment, message, and public= =20 > key. The scheme has commitment recovery, so the signature itself consists= =20 > of the response z and the challenge c. (There is also a hint h, but that= =E2=80=99s=20 > small and we can ignore it.) If we set s1 to zero, then z=3Dy, which is= =20 > free to choose. So we can freely choose z, which is by far the largest pa= rt=20 > of the signature. Such a public key t is easy to detect, as it has small= =20 > coefficients. Instead we can set s1 to zero on only a few components.=20 > That allows us to choose z arbitrarily for those components, still breaki= ng=20 > jpeg resistance, while being hard to detect. There could well be other=20 > approaches here. > > Falcon. A Falcon private key are small polynomials f,g. Its public key is= =20 > h =3D g f-1. With the private key, for any polynomial c, we can compute= =20 > small s1 and s2 with s1 + s2h =3D c. A Falcon signature is a pair r, s2= =20 > where s1 =3D H(r, m) - s2 h is small. s2 is Guassian distributed, and is= =20 > encoded using an Elias=E2=80=93Fano approach. It=E2=80=99s then padded to= make signatures=20 > fixed-length. Clearly the randomizer r can be set arbitrarily, but it=E2= =80=99s=20 > only 40 bytes. Putting arbitrary bytes in most of the encoding of s2 will= =20 > likely yield a sufficiently small s2. Now, I thought about using this s2= =20 > as a new g and construct a signature that way by finding s=E2=80=991 and = s=E2=80=992 with=20 > s=E2=80=991 + s=E2=80=992s1f-1 =3D H(r,m), but my brother suggested a sim= pler approach. s2=20 > is likely invertible and we can set h =3D H(r, m)/s2. Both approaches wou= ld=20 > be thwarted by using H(H(h), r, m) instead of H(r, m). I do not know if= =20 > there is still another attack. > > Best, > > Bas > > --=20 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 e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= 8a2c8743-dd0b-422c-85f9-f0350eec1162n%40googlegroups.com. ------=_Part_585741_1535144664.1747859915465 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Thank you for this! It's definitely informing how we approach development o= f BIP-360. SLH-DSA is concering, in that 7/8 arbitrary data would make it a= bout on par with the de facto witness discount. I don't want to sacrifice S= LH-DSA because it's favored due to hash-based signatures having more confid= ence due to not introducing as many novel security assumptions as are intro= duced 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 conferr= ing 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 s= pends for P2QRH.

Another concern regarding SLH-D= SA 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 reas= on 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 FAL= CON in terms of performance and size.

JPEG resis= tance and scaling will need to be solved through separate means, perhaps wi= th BitZip, which is what I'm calling Ethan's proposal a couple weeks back f= or 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= =E2=80=AFAM UTC-6 Bas Westerbaan wrote:

Hi all,


My colleagu= e 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 s= pecified) signature and full message, they can find a completed signature a= nd public key, such that the completed signature verifies under the public = key.


A naive hash-based signature is not jpeg resistant. Schoolboo= k 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=E2=80=99t sign the message itself, but first hashes in (among othe= rs) the public key. Basically the best we can do for XMSS (except for setti= ng the signature randomizer) is to guess the public key. Thus it=E2=80=99s = pretty much jpeg resistant.


The situation is different again for R= FC 8391 XMSSMT. XMSSMT is basically a certificate chain of XMSS= signatures. An XMSS= MT public key is an XMSS public key. An XMSSMT signature is a chain of XMSS s= ignatures: the XMSSM= T public key signs another XMSS public key; which signs another pu= blic XMSS public key; =E2=80=A6; which signs the message. Again the top XMS= SMT public = key is hashed into the message signed, but that only binds the first XMSS s= ignature. We can=E2=80=99t mess with the first signature, but the other sig= natures we can choose freely, as those roots are not bound. Thus XMSSMT with two subtr= ees is only half jpeg resistant and it gets worse with more subtrees.


Similarly SLH-DSA (FIPS 205, n=C3=A9e SPHINCS+) is a certifica= te chain of (a variant of) XMSS signing another XMSS public key, which sign= s 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. Fro= m 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=E2=80=99t mess with the first XMSS keypair. Thus to attack SLH-DSA we = honestly generate the first XMSS keypair. Then given a message, we just pic= k the signature arbitrarily for all but the first XMSS signature. We run th= e verification routine to recompute the root to sign by the first XMSS keyp= air. Then we sign it honestly. It depends a bit on the parameters, but basi= cally we get to pick roughly =E2=85=9E of the signature for free.

ML-DSA (FIPS 204, n=C3=A9e Dilithium) is a Fiat=E2=80=93S= hamir transform of a (module-)lattice identification scheme. In the identif= ication scheme the prover picks a nonce y, and sends the commitment w1 =3D HighBits(A = y) to the verifier, where A is a matrix that=E2=80=99s part of the public k= ey and HighBits drops the lower bits (of the coefficients of the polynomial= s in the vector). The verifier responds with a challenge c, to which the pr= over returns the response z =3D y + c s1, where s1 is part of the private key. The verifier checks, a= mong other things, whether HighBits(Az-ct) =3D w1, where t =3D As1+s2 is part of the public key. As usual with Fia= t=E2=80=93Shamir, in ML-DSA the challenge c is the hash of the commitment, = message, and public key. The scheme has commitment recovery, so the signatu= re itself consists of the response z and the challenge c. (There is also a = hint h, but that=E2=80=99s small and we can ignore it.) If we set s<= span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);= background-color:transparent;font-variant-numeric:normal;font-variant-east-= asian:normal;font-variant-alternates:normal;vertical-align:baseline">1 to zero, then z=3Dy= , which is free to choose. So we can freely choose z, which is by far the l= argest 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 all= ows us to choose z arbitrarily for those components, still breaking jpeg re= sistance, while being hard to detect. There could well be other approaches = here.


Falcon. A Falcon private key are small pol= ynomials f,g. Its public key is h =3D g f-1. With the private key, for any polynomial = c, we can compute small s1 and s2 with s1= + s2<= span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);= background-color:transparent;font-variant-numeric:normal;font-variant-east-= asian:normal;font-variant-alternates:normal;vertical-align:baseline">h =3D = c. A Falcon signature is a pair r, s2 where s1 =3D H(r, m) - s2 h is small. s2 is Guassian distributed, and is encoded using an= Elias=E2=80=93Fano approach. It=E2=80=99s then padded to make signatures f= ixed-length. Clearly the randomizer r can be set arbitrarily, but it=E2=80= =99s only 40 bytes. Putting arbitrary bytes in most of the encoding of s<= span style=3D"font-size:0.6em;vertical-align:sub">2 will likely yi= eld a sufficiently small s2. Now, I thought about using this s2 as a new g and construct a signature = that way by finding s=E2=80=991 and s=E2=80=992 with s=E2=80=991 + s=E2=80=992s1f-1 =3D H(r,m), but my brother suggested a simpler approach. s2 is likely invertible= and we can set h =3D 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,


=C2=A0Bas


--
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/8a2c8743-dd0b-422c-85f9-f0350eec1162n%40googlegroups.com.
------=_Part_585741_1535144664.1747859915465-- ------=_Part_585740_748976291.1747859915465--