[CFRG] Re: Request for adoption: Signature modes guidance / draft-harvey-cfrg-mtl-mode-03

[Phillip Hallam-Baker <[e-mail]>]

I support this work having worked on developing similar structures for the
purpose of validating notary entries.

>From an implementation point of view, it fits in the signature slot.

There are actually quite a few degrees of freedom here and implementation
actually requires rather a lot of thought. Working out how to balance the
tree is one thing, gathering up the minimum necessary data to create a
proof is another.

Sure, it all looks easy *after the code is written* but so did Diffie
Hellman and Martin Hellman reports that it actually took him quite a while
puzzling over how to put the things together because what seems obvious
once you see the answer is not when you are trying to find it.

And there are real questions of crypto here. For example, what hash size do
we need for a given work factor? Digests typically require double the bit
size on account of the birthday thing. But is that the case here? Can we
get a work factor of 2^256 with 256 bit digests? That halves the size of
the tree at a stroke.


Right now I am using binary trees but that has the problem that
32*log2(bignumber) gets big fast. So I have been playing with increasing
the degree of the graph as it expands. So you start off with binary, shift
to order 3, shift up to 4, 5, etc. as the log expands so that you get a
tradeoff between the node size and path length.




On Fri, Aug 9, 2024 at 11:23 AM Kaliski, Burt <bkaliski=
[e-mail]> wrote:

> Thanks all for the thoughtful feedback to my request.
>
> I've included responses to the technical comments below.
>
> Note that although draft-harvey-cfrg-mtl-mode-03 is the document under
> discussion, the proposal I'm making is broader. I am asking that CFRG
> provide guidance to protocol designers on signature modes of operation more
> generally.  In particular, how to combine hash functions and other
> techniques with an underlying signature algorithm to obtain additional
> security and operational properties.
>
> > [Watson Ladd] I don't understand why this is in the CFRG: it seems to be
> squarely in the line of decisions WGs have made outside CFRG such as
> keytrans or CT.
>
> WGs have made decisions on using pre-hashing and Merkle tree constructions
> in various ways, and they could continue to do so for MTL mode and other
> techniques. However, while WGs may have built on one another's experiences
> in deciding on their cryptographic constructions, the specifications of
> these constructions have generally been made within the applications
> themselves.
>
> Having common specifications for these kinds of constructions would be
> helpful not only for interoperability but also for addressing security
> questions such as:
>
> (a) which hash functions to use in combination with particular signature
> algorithms (discussions along these lines are underway in LAMPS for
> composite signatures);
> (b) how to handle the case that an application uses the same key pair in
> two different modes (e.g. "pure" and "pre-hashing" -- should there be a
> "domain separator");
> (c) whether and when to include other inputs to the hash functions
> (randomizer, public key, etc.) to achieve additional security properties;
> (d) how to model interactions between the use of hash and other functions
> in the construction, and in the underlying signature algorithms, as they
> mayaffect security proofs.
>
> Questions like these are more squarely in the line of CFRG than in the WGs
> integrating the constructions into their applications.
>
> > [Watson Ladd] Separately while I think the idea is interesting, there's
> a lot of operational and structural questions to actually apply it very
> closely ingrained with application and protocol level considerations. CFRG
> isn't really suited to determine if this will work. This is not to say it
> shouldn't be pursued, but I just have a lot of questions about how it would
> work fro DNSSEC for instance.
>
> Agreed. We expect that specifications for integrating MTL mode into a
> given application, e.g., DNSSEC (see
> draft-fregly-dnsop-slh-dsa-mtl-dnssec-02) will give further detail specific
> to the application. The focus for CFRG would be the cryptographic
> constructions.
>
> > [Richard Barnes] I tend to agree with Watson here. It's not clear to me
> why this is a new signing mode vs. just another data structure that gets
> signed.  Plenty of other signed hash-based data structures have been
> defined by Certificate Transparency, the various flavors of Key
> Transparency, and others. As Watson says, and as these examples illustrate,
> the details of these data structures tend to be pretty
> application-specific. So it seems like this work might be better done in a
> venue with more DNSSEC expertise, even if it might be reusable elsewhere.
>
> As noted, the focus for CFRG would be on the cryptographic constructions.
> These reusable parts would benefit from CFRG expertise on the state of the
> art in cryptographic design. For example, draft-harvey-cfrg-mtl-mode-03
> adopts techniques from SPHINCS+ to reduce the size of the internal hash
> values and to move to security properties such as multi-function,
> multi-target second-preimage resistance. These kinds of changes are much
> more within CFRG expertise than DNSSEC.
>
> > [Mike Ounsworth] But CT doesn't externalize data needed to validate the
> signature into the CT data. I think that's what makes it a "signature mode"
> rather than a "protocol".
>
> > I also think that the authors are trying to get cryptographic review of
> the crypto and show that this mode could be used beyond DNSSEC, hence
> bringing it to CFRG.
>
> Yes, in MTL mode, signatures can be distributed in two parts, a short
> "condensed signature" for a specific message, and a longer "signed ladder"
> that can authenticate multiple messages. The two parts of the signature for
> a given message can also vary over time as additional messages are signed.
> We see this approach as a signature mode because the parts are
> cryptographic constructions and agree that it could be used beyond DNSSEC.
>
> -- Burt
>
> (Note:  Reference [10] in my initial email refers to
> draft-ietf-lamps-pq-composite-kem-04.  It should have referred to
> draft-ietf-lamps-pq-composite-sigs-02.)
>
>
> -----Original Message-----
> From: Kaliski, Burt
> Sent: Monday, August 5, 2024 9:43 AM
> To: '[e-mail]' <[e-mail]>
> Cc: Fregly, Andrew <[e-mail]>; Harvey, Joseph
> <[e-mail]>; Sheth, Swapneel <[e-mail]>
> Subject: Request for adoption: Signature modes guidance /
> draft-harvey-cfrg-mtl-mode-03
>
> CFRG,
>
> Following up on my presentation at IETF 120, I would like to request that
> CFRG adopt draft-harvey-cfrg-mtl-mode-03 [1] as part of a broader research
> effort to provide guidance on modes of operation for digital signature
> schemes in applications.  The authors' rationale is as follows:
>
> * NIST is in the process of standardizing what are effectively two modes of
> operation for FIPS 204 and 205 - "pure signing" where the message is signed
> directly with the underlying signature scheme and "pre-hash signing" where
> the hash of the message is signed.  NIST has also introduced a "domain
> separator" format to distinguish the two modes [2].
> (draft-harvey-cfrg-mtl-mode-03 adopts the domain separator format to
> distinguish MTL mode from others.)
>
> * There are discussions underway on these topics on NIST's pqc-forum
> mailing
> list [3].  It seems prudent that CFRG advance guidance to applications on
> how and when to use pure signing vs. pre-hash signing, how to use domain
> separators and context strings in inputs to signature schemes, and how to
> approach other modes of operation.
>
> * The initial use case for MTL mode is DNSSEC, as described in
> draft-fregly-dnsop-slh-dsa-mtl-dnssec-02 [4].  The current draft includes
> an
> example zone file signed with SPHINCS+ (SLH-DSA) in MTL mode.  The authors
> hosted a hackathon session [5] on the draft at IETF 120 and also presented
> [6] at HotRFC.  In addition, following the PQ DNSSEC side meeting [7], a
> new
> non-WG mailing list, pq-dnssec [8], was formed in the Security Area.  The
> mailing list will be used for discussions of
> draft-fregly-research-agenda-for-pqc-dnssec-01 [9].  MTL mode is one of
> several approaches for reducing the operational impact of post-quantum
> signatures identified in the draft.
>
> * Another example of a signature mode where CFRG guidance would be helpful
> is composite signatures [10].  For instance, if the composite signature
> construction is applied to FIPS 204/205, does this mean that FIPS 204/205
> is
> operated in "pure" mode (because the pre-hashing has already been done)?
> And how should an application use the optional context string provided by
> FIPS 204/205 in a composite construction?
>
> * Verisign announced a public, royalty-free license to certain intellectual
> property related to draft-harvey-cfrg-mtl-mode-03.  IPR declarations
> 6174-6176 [11] give the official language.
>
> Thanks -- Burt
>
> [1] J. Harvey, B. Kaliski, A. Fregly, S. Sheth.  Merkle Tree Ladder (MTL)
> Mode Signatures.  draft-harvey-cfrg-mtl-mode-03, June 12, 2024,
> https://datatracker.ietf.org/doc/draft-harvey-cfrg-mtl-mode/03/
> [2] D. Moody. Updates on pre-hash for FIPS 204 and 205.
> [e-mail] mailing list, April 19, 2024,
>
> https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/JKMh0D0pa30/m/vbflXo
> lxAQAJ.
> [3] pqc-forum mailing list,
> https://groups.google.com/a/list.nist.gov/g/pqc-forum
> [4] A.M. Fregly, B. Kaliski. J. Harvey, D. Wessels.  Stateless Hash-Based
> Signatures in Merkle Tree Ladder Mode (SLH-DSA-MTL) for DNSSEC.
> draft-fregly-dnsop-slh-dsa-mtl-dnssec-02, July 8, 2024,
> https://datatracker.ietf.org/doc/draft-fregly-dnsop-slh-dsa-mtl-dnssec/02/
> [5] Exploring Implementation Approaches for Merkle Tree Ladder Mode
> Signatures for DNSSEC, IETF 120 Hackathon,
> https://wiki.ietf.org/en/meeting/120/hackathon
> [6] A. Fregly, Stateless Hash-Based Signatures in Merkle Tree Ladder Mode
> (SLH-DSA-MTL) for DNSSEC, IETF 120 HotRFC,
>
> https://datatracker.ietf.org/meeting/120/materials/slides-120-hotrfc-sessa-0
> 4-stateless-hash-based-signatures-in-merkle-tree-ladder-mode-01
> <https://datatracker.ietf.org/meeting/120/materials/slides-120-hotrfc-sessa-04-stateless-hash-based-signatures-in-merkle-tree-ladder-mode-01>
> [7] Side Meetings at IETF 120,
> https://wiki.ietf.org/en/meeting/120/sidemeetings
> [8] pq-dnssec mailing list,
> https://mailarchive.ietf.org/arch/browse/pq-dnssec/
> [9] A.M. Fregly et al., Research Agenda for a Post-Quantum DNSSEC.
> draft-fregly-research-agenda-for-pqc-dnssec-01, June 26, 2024,
>
> https://datatracker.ietf.org/doc/draft-fregly-research-agenda-for-pqc-dnssec
> /01/
> <https://datatracker.ietf.org/doc/draft-fregly-research-agenda-for-pqc-dnssec/01/>
> [10] M. Ounsworth et al., Composite ML-KEM for Use in the Internet X.509
> Public Key Infrastructure and CMS.  draft-ietf-lamps-pq-composite-kem-04,
> July 8, 2024,
> https://datatracker.ietf.org/doc/draft-ietf-lamps-pq-composite-kem/04/
> [11]
>
> https://datatracker.ietf.org/ipr/search/?draft=draft-harvey-cfrg-mtl-mode&rf
> c=&doctitle=&group=&holder=VeriSign%2C+Inc.&iprtitle=&patent=&submit=draft
> <https://datatracker.ietf.org/ipr/search/?draft=draft-harvey-cfrg-mtl-mode&rfc=&doctitle=&group=&holder=VeriSign%2C+Inc.&iprtitle=&patent=&submit=draft>
>
> _______________________________________________
> CFRG mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>