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

["Kaliski, Burt" <[e-mail]>]

Thanks very much for your support, Phill.



As I’ve noted in my previous emails, there are two aspects where CFRG consideration of the draft would be helpful:  (1) guidance on signature modes in general; and (2) the specification of MTL mode in particular.  Phill has enumerated some of the “questions of crypto” that would be involved.



In an addition to my emails to CFRG, I also emailed LAMPS with related questions [1] about signature modes of operation in draft-ietf-lamps-pq-composite-sigs [2].  Mike Ounsworth added my questions to the issues list [3].  Similar questions could be raised with respect to signature modes in other drafts and working groups, hence my interest in a broader discussion within CFRG.



The MTL mode draft was updated this week [4] to align with FIPS 205 (the changes were minor).  In addition, we also recently published design considerations for integrating Merkle Tree Ladder (MTL) Mode signatures into applications [5].



-- Burt

[1] https://mailarchive.ietf.org/arch/msg/spasm/vzomXUHvJOouzIcC82WkMF4DP-g/

[2] https://datatracker.ietf.org/doc/draft-ietf-lamps-pq-composite-sigs/

[3] https://mailarchive.ietf.org/arch/msg/spasm/Xq6PkGkXX4SXudJUnqkVtJ0Mu-U/

[4] https://datatracker.ietf.org/doc/draft-harvey-cfrg-mtl-mode/

[5] https://datatracker.ietf.org/doc/draft-harvey-cfrg-mtl-mode-considerations/







From: Phillip Hallam-Baker <[e-mail]>
Sent: Tuesday, September 10, 2024 1:16 AM
To: Kaliski, Burt <[e-mail]>
Cc: [e-mail]
Subject: [EXTERNAL] Re: [CFRG] Re: Request for adoption: Signature modes guidance / draft-harvey-cfrg-mtl-mode-03



Caution: This email originated from outside the organization. Do not click links or open attachments unless you recognize the sender and know the content is safe.

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]<mailto:[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]<mailto:[e-mail]>' <[e-mail]<mailto:[e-mail]>>
   Cc: Fregly, Andrew <[e-mail]<mailto:[e-mail]>>; Harvey, Joseph
   <[e-mail]<mailto:[e-mail]>>; Sheth, Swapneel <[e-mail]<mailto:[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/<https://secure-web.cisco.com/1d4-qYj01_2aEClhnq-gkCWrwp76cXNq5vtNdEYffGieqYxp3MbqS_wDNFwAf6260jKu663MZAlHpQmTjmOExMx0vcWGx6oAh-2Mo1b79B-7qPhL5Mgznnl64_GFKqLHtnhd05sECLMQXKB_QsKAFHXy-og43avdeQYgaKvfDha80BXeJerND_5R7gef86eJRcIhit1FaTV3HFLWd6BAR4eQ8Mi3Ucn73uqbY8cj2upYiFadobObLMdaFyQSGZRod6RrzEmRlsVnwoRmT_3vh4UDtIa51V9cDe1nIxYLg4Ak/https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fdraft-harvey-cfrg-mtl-mode%2F03%2F>
   [2] D. Moody. Updates on pre-hash for FIPS 204 and 205.
   [e-mail]<mailto:[e-mail]> mailing list, April 19, 2024,
   https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/JKMh0D0pa30/m/vbflXo<https://secure-web.cisco.com/18xmBY03DFm0s3hPhlUVcz6qFKWrbe9oMzaM4x96n0UqrO593MlkKusXtkAWLACdX_Hy8Wo8bjpDlL50NRE4RqPvuZ1oTAwA5NaBPeeI352BLrFC5zRVXNKcS6Q31JG_u4wXqxmrsJIjWERQsRjDeVfg0qmuCrJvTTtNK3xA1qVAWhGUB0ZbknCl5jOkeaeHpK1q2lk06E7t2GI_2erzjBra3nfV01Toi9uOJZtZvtBybI2x4_SQolFw_oN2OZPk4ZC3TPxs0uQHMPRt-N_8XGeZW6fXQj3wDJ7lAgqYT_qk/https%3A%2F%2Fgroups.google.com%2Fa%2Flist.nist.gov%2Fg%2Fpqc-forum%2Fc%2FJKMh0D0pa30%2Fm%2FvbflXo>
   lxAQAJ.
   [3] pqc-forum mailing list,
   https://groups.google.com/a/list.nist.gov/g/pqc-forum<https://secure-web.cisco.com/1oTBi10uimVxvWdXt5M2MDFLG9ah0UCgUnm1KqGrp7MkzbLNli_lypsKWpWH4NChQ6a-tbsLP7BldmdqP3uxiqHVA5K4WulwZ8Xo_SwV9sQ8w8Pv2wRxQ2854OV1dephE74b0j3yf98FbvN3IMmidB3ZLWNFyC1rqPyaiMTjzeQ5LD0xfXoHRjRcttdagenan_XGaLxkb_i35K4LN5d_3Q1Ycj37Wk6c1jahC9JGZCXzVR3JCRAUeNKli4_xHRM3g9YUaJ94DKaGrP_cCwEGVGKf12vd6g67FCH33M2ypyyc/https%3A%2F%2Fgroups.google.com%2Fa%2Flist.nist.gov%2Fg%2Fpqc-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/<https://secure-web.cisco.com/1NRQ9IsfVhHkH5ZodHWJShguYTuBnkCC61LERYiiJfrrpWJCQqCCm2Adtjyk9zsNZv4g8fH4u1kPo4UbO_eHBTHW7FcSAWYPC_iM8Y14Savrl-y7OAuWtFjEC6oreE2qpuUpY7rY2dQ5wiGb4tdxHGZC88-KyXakU9UXh98UbJJ9PbXBGHL8wO7KsMbJwCiinpOj4jsWwHhmG7kzgf4o0M7bNf6rposDeoqgA5Su4C0_Zdi0wZHjufre_Zt8bhUajyeBtTm8aST0XavPCgHIZ_U87wEeXvgfvvrCcfetoILc/https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fdraft-fregly-dnsop-slh-dsa-mtl-dnssec%2F02%2F>
   [5] Exploring Implementation Approaches for Merkle Tree Ladder Mode
   Signatures for DNSSEC, IETF 120 Hackathon,
   https://wiki.ietf.org/en/meeting/120/hackathon<https://secure-web.cisco.com/1DYTsFHDt7e1QDQ_KwQRlMAKfIUaUkW2GnPMrBxU7veXxhxmnXiQdr1KtsYyKz8Ti4j6gY2KJq6cjZFv43FH-IL-7rzSQ_XJBuzzqdlfhPA3IXGOfyzuwuKtkvj4r9MsqkQvsYuabPT7mKC5LBjQ2yb2tBUAPDiITSnYThfIhsZ41-sZb5rWhH562jKPQwHRDlr5hsDbxmWaQCTggoZoAiPobTM0pozY2YQHVFw1SU6gr8JWgmhdDz5GwOh0m30OzgKRsZccJ67xFogpVV6zZ7eSRsk3PSffscJ7L0XNPYSo/https%3A%2F%2Fwiki.ietf.org%2Fen%2Fmeeting%2F120%2Fhackathon>
   [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://secure-web.cisco.com/1-MfRdMuoQLMog4-WY2pUPpzgwJmmVI2lhVETlEmxUyKLZIhAoMW4ptNEptz7MuHDWT-gJ_-IU4rnE-N7Pq6e7oAMy4oEnvacYWDgLYDDtgn56JFBF4IjkCheNdtVynTI8nUY4MwNXzRfb1rokZskbxSecLRE28BXlMJFd_QZmU7L0DRmZRkOrORI0GaKBDzzFIHBMyFOo9zKP8sJtwti4-btLmYVG7D1Bkn5lq6m4aboFghSI-NfQOom98_9URVkatDAg5t7Gpt8MT1CuqPZbVhJsfRSp7mIIkEnshS31Yw/https%3A%2F%2Fdatatracker.ietf.org%2Fmeeting%2F120%2Fmaterials%2Fslides-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<https://secure-web.cisco.com/1S9yIiT5sFDdVYn2nGpCwtMwSIbsVoaUPSEciDfEh9Up_EKWRB6F0o_4bNtb8agn3QX8CipL4hiTBWZ1MVFYBGlIlwzxR1ypenQ1WK2sJUz2AcBN_0zDpT7t3jE8G1z7cbRozB4Bz-4xXZ9EqDZVmZLhorbNXxZhOIRThqbj60uNYOdISWsv6qGlIDiCbYAdQ3udsBzRItnjA47v0zVSxscrD2ZGUdRKqqheo43t8Fa4HitD8SPf35JjuDKZ0-XOi4i1LVn8hDT7oT4FP4g3uDPHdi4iYsDFqUMKEilIPsJU/https%3A%2F%2Fwiki.ietf.org%2Fen%2Fmeeting%2F120%2Fsidemeetings>
   [8] pq-dnssec mailing list,
   https://mailarchive.ietf.org/arch/browse/pq-dnssec/<https://secure-web.cisco.com/1Z-I8CcbG2ec6kA1K6ghmh1S_CYPS3srle6Kd35Onnvgbqf5rXjY49OvcGxwOeTHksT8_VIxWKUpIWOldZN4uyGR03YuktldXx52Pj057ZXkYhpVCx4HqNjjUb16R5_HFz9qf0G1KDPOaGeBnT6KYNjfECO9qQkrYTkoIDcXF8Ora0yKrPouC6PUgNrKh85gUpYb0_ENZw1lzn8AgBF4IYbWs6eSD-jofkA6dwUVSWoJt7Hx5xnE-K-Q0t20zY_q798UyiQquy_LBnKQ7I3PgB0fpPXP10n-xceB7-mvgzKk/https%3A%2F%2Fmailarchive.ietf.org%2Farch%2Fbrowse%2Fpq-dnssec%2F>
   [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://secure-web.cisco.com/1qj5gDY1YVtQKEbmfKQlJ_5Ti14D9LnJYbjrrD5r264QRjzD_ciC1w4TtaR3tBrKjJdtWvrwnP_DDvzFnTki7zHpYFR3rxFd9k7q7-siArvEGo2ObuKHX1RgUY_FbmgHS_Gn4DV803R5g7wKAZUC7SLS7A1ByHBQfP6qGc7Td_9mZ75-vAzK0Q5AwelsoWPxI0AU-O1nnoHXUWglhhcp3YKHGiv-xtjZKd9hS6nGadX_O5S8V_8jauBzE4Cg-MEt-wNemtgU2Pv79JlqVmpIylLQa-PAnQPK6kLiG0aaLQ8Y/https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fdraft-fregly-research-agenda-for-pqc-dnssec%2F01%2F>
   [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/<https://secure-web.cisco.com/1GDKK7pNi3_W2yc3KLslkc90t1AgLHRQz9XzadBY1dT75qewnKjBboGSPvU70Pauroz03pZ4N-KjFNomTiLgQC7vMUsw19mc-u8-QMV-ACM7wvn5LPdhFIm2ldm0s4SSmiYmWhBT_AWRS44bz96fdzTDSOUxuEW_C-B0CdIapCVt166L4-qrPpjz1DSGRQBVz9jkJ1TFyh4pKApWk_33pu1_6bDWrEW5oorGILHCLceRYvmR3QzN6856eB1MdFJA-a2Q4wcd3xGNkcZB1D42KiuWzrgKo3EDmlSVqyRcjv9E/https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fdraft-ietf-lamps-pq-composite-kem%2F04%2F>
   [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://secure-web.cisco.com/1oMoP2kEIYKPT56CXe5iru2wfKXIzg9AKUV6dkRslxUSA_3AlIz-agQ04DkrfDe7QAX8_ctvh6l5WXfRvMhkCPHSiZSzK8ax9RiMpL7NvfbckaEqA6lsTu_QAMsWN4zlFMG7CqplIRGtYhachT-UD5uB4wHBadcj5cF4-qEwOluiWjSR0OG_E_y2F0cbag4ELZfwAqV2Lr4PpYswKZo7e98f5YuLh5kKjuCl9RL8UR6HjCESZ9IHlYQwgBCI1f7NL0Qc-IXz3uxTWlm-JquDkzl7o1miw8Jsd8E8LfhgMcp8/https%3A%2F%2Fdatatracker.ietf.org%2Fipr%2Fsearch%2F%3Fdraft%3Ddraft-harvey-cfrg-mtl-mode%26rfc%3D%26doctitle%3D%26group%3D%26holder%3DVeriSign%252C%2BInc.%26iprtitle%3D%26patent%3D%26submit%3Ddraft>

   _______________________________________________
   CFRG mailing list -- [e-mail]<mailto:[e-mail]>
   To unsubscribe send an email to [e-mail]<mailto:[e-mail]>