[openpgp] Re: Gap in RFC 9980 regarding 2nd preimage resistance

[Falko Strenzke <[e-mail]>]

Actually RFC 9580 makes the same mistake in its security
considerations:

This means that an adversary carrying out a chosen-message attack will
not be able to control the hash that is being signed and will need to
break second-preimage resistance instead of the simpler collision
resistance to create two messages having the same signature.

Also here, an erratum would be good that at minium replaces "second-
preimage resistance" with "multi-target second-preimage resistance"
(SM-SPR in [HRS16]). Since it  seems to slip our attention too easily,
it might also make sense to mention that under conservative security
parameters with respect to the number of target signatures and message
lengths, also SHA-1 and MD5, both still verifiable according to RFC
9580, are subject to multi-target second-preimage attacks and at the
same time the expandable messages attack from Kelsey and Schneier,
resulting in a potentially drastically lower computational complexity
than 2^n (at increasing memory costs, of course). That might also be
noteworthy. This topic is thus relevant for the correct estimation of
the legacy digest functions generally and at the same time for all
newly introduced signatures schemes that are limited to the v6 format
and thus do not necessarily need to achieve collision resistance.

I am sorry if all that is too cryptic for now, this topic clearly
deserves a writeup for reference, which, however, I won't be able to
produce on short notice. I can offer to give a presentation at the IETF
127 meeting. The errata are minor points and not urgent, but changing
the requirements for the choice of the hash functions in draft-ietf-
openpgp-nist-bp-comp should be addressed rather soon.

[HRS16] A. Hülsing, J. Rijneveld, F. Song, “Mitigating Multi-Target
Attacks in Hash-based Signatures”, PKC 2016.

Falko

On Thu, 2026-10-15 at 14:49 +0200, Falko Strenzke wrote:
> One detail needs correction: I present it below as if T is the number
> of messages one key of one user has signed. Actually, if the attacker
> can benefit from a forged message signed by a larger set of keys from
> potentially different users, his search is among the whole set and
> thus T is the number of all messages of the relevant keys and users
> combined. The attacker chooses the public key after the match. But
> that is not really changing the order of magnitude I have given
> below.
> 
> On Thu, 2026-10-15 at 14:14 +0200, Falko Strenzke wrote:
> > The observation and proposals regarding RFC 9980 and draft-ietf-
> > openpgp-nist-bp-comp that follow has so far been discussed among
> > Stavros, Stephan, and me. Before the authors agree on and work out
> > their proposal in detail, it makes sense to get feedback from the
> > chairs and the working group first.
> > 
> > It turns out the requirements for the message digest choice as
> > prescribed in RFC 9980 have a gap. It specifies at minimum a 256-
> > bit digest size as “MUST”. In the security considerations, it is
> > argued that this is sufficient for all levels since, due to the
> > random salt prefixed to v6 signatures, hash collisions do not have
> > to be considered, but only 2nd preimage resistance. So far, this is
> > correct, but the conclusion that is then drawn, namely that 256-bit
> > digests are enough to achieve 2nd pre-image resistance, is wrong:
> > As soon as the attacker has recorded T=2cT = 2^{c} signed messages,
> > he can match each digest of his crafted trial messages
> > to TT digests to find a valid signature. The attack cost is thus,
> > in a cost model that considers only computational effort and
> > ignores memory-related costs, reduced to 2256−c2^{256 - c}. The
> > effect is present already after two signed messages. With about 1
> > million signed messages, the security is degraded by 20 bits
> > to 22362^{236}.
> >  
> > The attack technique from [1] provides a further potential speedup
> > against SHA-256. This attack, however, has a considerable
> > computational overhead and thus only applies when the combined size
> > of the recorded messages becomes very large.
> >  
> > It is important to be aware that this does not mean that there is
> > any real threat to the security of messages signed according to the
> > current specifications in RFC 9580. This is for the following
> > reasons:
> >  
> >  * The security level of 256-bit for signatures has a vast security
> >    margin. There is basically no application context that requires this
> >    security level. 256-bit security is the highest level that we have
> >    in algorithm parameter specifications and is – if at all – used for
> >    encryption of the most sensitive data with an (indeterminate) long-
> >    term security requirement.
> >  * For a substantial degradation of the security level, the attacker
> >    needs many messages. The assumption of 2⁶⁴ messages, that NIST is
> >    using, makes sense for a bound that covers all conceivable usage
> >    scenarios, but is not generally realistic. For the typical OpenPGP
> >    use case, the degradation by 20 bits given in the example above is
> >    probably a much better orientation.
> >  * These preimage attacks aim at the message hash do not interact with
> >    potential degradations through improved attacks against the
> >    primitives of the underlying signature algorithms. In other words,
> >    the degradations of these two different attack classes would not add
> >    up to a combined degradation.
> >  
> > However, as a consequence, we propose two things:
> >  
> >  * Correct RFC 9980 with an erratum. The proposal is detailed below.
> >    The open question here is whether an erratum can introduce a change
> >    to the normative requirements of the specification, if it does not
> >    introduce a wire-format-breaking change.
> >  * Correct draft-ietf-openpgp-nist-bp-comp by requiring 512-bit digest
> >    sizes for all parameters. This will also require an update of the
> >    test vectors. The question here is whether this can be done without
> >    formally returning the draft to the WG.
> >  
> > The following is our proposed correction as a working draft:
> >  
> > RFC 9980 currently says:
> >  
> > A composite ML-DSA + EdDSA signature MUST use a hash algorithm with
> > a digest size of at least 256 bits for the computation of the
> > message digest. A verifying implementation MUST reject any
> > composite ML-DSA + EdDSA signature that uses a hash algorithm with
> > a smaller digest size.
> >  
> > and has the equivalent statement for SLH-DSA. In an erratum, we
> > would add a sentence after the above one: “For ML-DSA+EdDSA
> > composite signatures, the signer SHOULD use a hash algorithm with a
> > digest size of at least 512 bits for the computation of the message
> > digest in order to achieve adequate second preimage resistance in
> > all usage scenarios. See Section 9.4 in the security considerations
> > for the rationale.”
> >  
> > And for SLH-DSA, we would add after the corresponding sentence:
> >  
> > “For SLH-DSA-SHAKE-256s, the signer SHOULD use a hash algorithm
> > with a digest size of at least 512 bits for the computation of the
> > message digest in order to achieve adequate second preimage
> > resistance in all usage scenarios. See Section 9.4 in the security
> > considerations for the rationale.”
> >  
> > This is a change of the normative requirements, but lets messages
> > signed according to the published version remain valid.
> >  
> > The following should replace the currently present invalid
> > justification of the 256-bit digests in the security
> > considerations:
> >  
> > > The leading random salt does not by itself establish that a 256-
> > > bit message digest matches every targeted security level. In this
> > > construction, the salt is authenticated through the message
> > > digest. An attacker who produces a different admissible input
> > > with the same digest can reuse the corresponding signature value,
> > > including both components of a composite signature.
> > > Given T=2ᶜ distinct target digests from signatures under one key,
> > > generic multi-target digest matching requires approximately
> > > 2²⁵⁶/T=2²⁵⁶⁻ᶜ hash evaluations, assuming sufficient storage and
> > > efficient target lookup. NIST’s signature evaluation model
> > > considers attackers with access to up to 2⁶⁴ signatures. At that
> > > reference point, the search cost is approximately 2¹⁹² hash
> > > evaluations. This is an attack-cost estimate under the stated
> > > assumptions, not a proof of an achieved NIST security category,
> > > and it falls below the classical 2²⁵⁶ reference work factor
> > > associated with category 5.
> > > For SHA2-256, expandable-message techniques [1] can additionally
> > > exploit intermediate chaining states of signed messages. In the
> > > multi-target application, the bridge-search cost is approximately
> > > 2²⁵⁶/N, where N counts distinct eligible target states. For a
> > > realistic cost estimate, expandable-message construction, target
> > > preprocessing, and storage must also be accounted for. For
> > > sufficiently large target sets and suitable message lengths, this
> > > can yield an attack below the classical 2¹⁹² reference work
> > > factor relevant to ML-DSA-65 + Ed25519. The same construction
> > > does not apply to SHA3-256.
> > > To provide a conservative margin against these attacks, this
> > > specification recommends message digests of at least 512 bits for
> > > both composite signature algorithms and for SLH-DSA-SHAKE-256s.
> >  
> > In draft-ietf-openpgp-nist-bp-comp we suggest explicitly stating
> > the MUST requirement for 512-bit digests with no exceptions. That
> > requires an update of the test vectors which are currently
> > conflicting with this [2]. In the security considerations we would
> > not refer to RFC 9980 regarding this point, since the discussion
> > about the erratum might take some time. We suggest including here
> > the same text that we propose above as the correction to RFC 9980.
> >  
> > [1] John Kelsey and Bruce Schneier. Second preimages on n-bit hash
> > functions for much less than 2n2^{n} work. In Advances in
> > Cryptology – EUROCRYPT 2005, volume 3494 of LNCS, pages 474–490.
> > Springer, 2005. doi: 10.1007/11426639_28.
> >  
> > [2]
> >  
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > Vector setAlg IDKey self-sigs (direct-key 0x1f, cert 0x13, subkey
> > binding 0x18)Detached signature (0x00)
> > 
> > 
> > 
> > 
> > A.1 ML-DSA-65 + ECDSA-NIST-P-38441SHA3-256SHA-256
> > 
> > 
> > A.2 ML-DSA-87 + ECDSA-NIST-P-52142SHA3-512SHA3-512
> > 
> > 
> > A.3 ML-DSA-65 + ECDSA-brainpoolP384r143SHA3-256SHA-256
> > 
> > 
> > A.4 ML-DSA-87 + ECDSA-brainpoolP512r144SHA3-512SHA3-512
> > 
> > 
> > 
> > 
> 

-- 
MTG AG
Dr. Falko Strenzke

Phone: [phone]
E-Mail: [e-mail]
Web: mtg.de

MTG AG - Dolivostr. 11 - 64293 Darmstadt, Germany
Commercial register: HRB 8901
Register Court: Amtsgericht Darmstadt
Management Board: Jürgen Ruf (CEO), Tamer Kemeröz
Chairman of the Supervisory Board: Dr. Thomas Milde

This email may contain confidential and/or privileged information. If
you are not the correct recipient or have received this email in error,
please inform the sender immediately and delete this email.Unauthorised
copying or distribution of this email is not permitted.

Data protection information: Privacy policy