LAMPS Y. Nir Internet-Draft Dell Technologies Intended status: Standards Track 19 June 2023 Expires: 21 December 2023 A Hybrid Signature Method with Strong Non-Separability draft-nir-lamps-altcompsigs-00 Abstract This document presents an alternative scheme of composing classic and post-quantum signature algorithms with different security properties. This scheme produces signatures with strong non-separability (SNS) at the cost of breaking backward compatibility with legacy cryptographic hardware. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on 21 December 2023. Copyright Notice Copyright (c) 2023 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/ license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Nir Expires 21 December 2023 [Page 1] Internet-Draft AltCompSig June 2023 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1. Controversy in the LAMPS Working Group . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1. Requirement Keywords . . . . . . . . . . . . . . . . . . 4 2.2. Non-Separability . . . . . . . . . . . . . . . . . . . . 4 2.3. Backward Compatibility . . . . . . . . . . . . . . . . . 5 3. Hybrid Schemes . . . . . . . . . . . . . . . . . . . . . . . 5 3.1. Fiat-Shamir and Fiat-Shamir . . . . . . . . . . . . . . . 5 3.1.1. Key Generation . . . . . . . . . . . . . . . . . . . 5 3.1.2. Signing . . . . . . . . . . . . . . . . . . . . . . . 5 3.1.3. Encoding . . . . . . . . . . . . . . . . . . . . . . 7 3.1.4. Example . . . . . . . . . . . . . . . . . . . . . . . 7 3.2. Fiat-Shamir and RSA . . . . . . . . . . . . . . . . . . . 7 3.3. Fiat-Shamir and Falcon . . . . . . . . . . . . . . . . . 7 3.4. RSA and Falcon . . . . . . . . . . . . . . . . . . . . . 7 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7 5. Comparison with Other Proposals . . . . . . . . . . . . . . . 7 6. Security Considerations . . . . . . . . . . . . . . . . . . . 7 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 7.1. Normative References . . . . . . . . . . . . . . . . . . 8 7.2. Informative References . . . . . . . . . . . . . . . . . 8 Appendix A. Change Log . . . . . . . . . . . . . . . . . . . . . 9 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 9 1. Introduction In the past few years, there has been great progress in the development of quantum-computing. Today, most of the cryptographic algorithms are based on the difficulty of integer factorization and discrete logarithm over finite fields or elliptic curves. Yet in the upcoming years, with the potential of building a strong enough quantum-computer capable of computing Shor's algorithm - a so-called cryptographically relevant quantum computer (CRQC) - these algorithms may no longer be secure enough to rely upon. With the looming threat of CRQCs breaking existing public key constructs such as digital signatures, the world in general and the IETF in particular are looking to transition to so-called post- quantum algorithms, algorithms that are thought to be secure against a cryptanalytic attack by a quantum computer. The National Institute of Standards and Technology (NIST) has been running a project for selecting such post-quantum algorithms since 2016 ([NIST-PQC]). This project is not complete at the time of this writing. It has produced several finalists including Crystals- Dilithium ([Dilithium]), Falcon, and more. Nir Expires 21 December 2023 [Page 2] Internet-Draft AltCompSig June 2023 There is, however, concern about deploying these new algorithms as full replacements for the existing (or "classic") algorithms. On the one hand, there is the fear that researchers or nation-state adversaries will produce a CRQC that will allow them to break the classic algorithms such as RSA, ECDSA, and EdDSA. On the other hand, there is still doubt about the security of the new algorithms. This doubt is well-founded: One of the candidate algorithms, SIKE, was broken in late stages of the competition ([SIKE-BREAK]). To minimize the risks or relying on a single algorithm, there are some proposals for combining two or more algorithms, typically a classic algorithm and a post-quantum algorithm, such that all of the algorithms are used to create the signature, and some or all of them are used to verify the signature. This has the advantage that unless the adversary is able to break all of the algorithms, a verifier who uses all of the algorithms will not be fooled. One such proposal is [I-D.ounsworth-pq-composite-sigs]. Most such proposals, including the above-mentioned draft, involve independently signing with the several algorithms, each having their own private/public key pair. With these schemes the private key is a concatenation or a vector of the private keys of the several algorithms, and similarly the public key is a vector of the public keys, and the signature is a vector of independent signatures. A signature like that is said to be parallel and separable, as there is no dependency between the signatures involved. This draft proposes alternate schemes where specific algorithms are combined to create signatures that are non-separable, meaning that it is not possible to verify the signature using just one algorithm. This is based on an article by Bindel and Hale ([Bindel23]). 1.1. Controversy in the LAMPS Working Group On May 30th, 2023, the LAMPS working group had an adoption call for [I-D.ounsworth-pq-composite-sigs] that ultimately did not achieve consensus. There were various objections, some about the timeliness of adopting the drafts before NIST concluding the competition, some about the formatting within the drafts, and some questioning the very utility of hybrid signatures. Nir Expires 21 December 2023 [Page 3] Internet-Draft AltCompSig June 2023 This draft takes no position on this question. What it does claim, is that if we would like to get the benefit from hybrid signatures, then verifiers should be required to verify both the classic and post-quantum components of the signature. The catalyst for the hybrid signature effort was the idea that both the classic and the post-quantum algorithms have a non-trivial chance of compromise in the next few years. Fielding a verifier that checks only one algorithm or the other carries the risk that this verifier is checking only the first algorithm to be compromised. The algorithms in this draft force an implementation to check both signatures to get any security. If hybrid signatures are worth doing at all, they are worth doing in such a way. NOTE: This draft is (for now) an individual draft with an unclear destination. Its file name includes the LAMPS label not as a signal that I would like the LAMPS working group to adopt it at this time, but only because the LAMPS working group is the one where hybrid signature discussions are taking place. 2. Terminology 2.1. Requirement Keywords The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. 2.2. Non-Separability A hybrid signature is a signature that is created using more than one algorithm, typically at least one classic algorithm and at least one post-quantum algorithm. Non-separability (NS) is a property of hybrid signatures. With non- separable signatures, an adversary cannot remove one of the signatures (typically, the one that is not broken) forcing the verifier to rely only on the broken algorithm. Such an attempt would be detected. Strong Non-Separability (SNS) is a stronger property, where an adversary cannot convert an input hybrid signature into a single algorithm signature that will verify correctly. Nir Expires 21 December 2023 [Page 4] Internet-Draft AltCompSig June 2023 Simultaneous Verification (SV) is an even stronger property, that makes it impossible for the verifier to quit the verification after using just one algorithm. The hybrid signatures presented in this draft all require SV. 2.3. Backward Compatibility Backward Compatibility for hybrid signatures means that old verifying hardware or software that verifies the signature of one algorithm or the other can be used to verify the single-algorithm component of the hybrid signature. So the EdDSA component of a Dilithium-EdDSA hybrid signature can be verified using an EdDSA verifier. SNS and backward compatibility are mutually exclusive, meaning that to gain SNS, we have to give up on having backward compatibility. 3. Hybrid Schemes EDNOTE: As PQC standardization is still in process, both Dilithium and Falcon signature schemes can change in some aspects from their final form. To handle this situation both signatures will be described in more of a general form, Dilithium as a Fiat-Shamir based scheme with black box functions that will be replaced with the actual Dilithium implementation after the publication of parameters and implementations. Also, hybrid schemes with Falcon will be added. 3.1. Fiat-Shamir and Fiat-Shamir TODO: Add a 1-paragraph explanation of Fiat-Shamir signatures. A generic combination of Fiat-Shamir signatures is useful for hybrid signatures because both some classic and some post-quantum algorithms follow the Fiat-Shamir pattern. Specifically, Crystals-Dilithium is a Fiat-Shamir algorithm, as are the classic algorithms ECDSA and EdDSA. The following sections will use Dilithium and ECDSA as examples. 3.1.1. Key Generation Private keys for the two algorithms are generated separately. ECDSA signatures are generated as in [RFC6979]. 3.1.2. Signing Nir Expires 21 December 2023 [Page 5] Internet-Draft AltCompSig June 2023 Input: sk1 signer's Dilithium private key (A_Dil, t, s1, s2) sk2 signer's ECDSA private key (x, q) pk1 verifier's Dilithium public key (A_Dil, t) pk2 verifier's ECDSA public key (xG, q) M message to be signed of arbitrary size Output: S signature, contains (z, h, r, s) z the Dilithium signature proof h challenge combining both of the signatures r the X coordinate of a randomly generated point on the curve s the ECDSA signature proof - Steps: 1. Generate a random vector in the lattice based on the Dilithium final scheme. Let y denote this vector. 2. Compute w = HighBits(A_Dil, y). The HighBits function is described in detail in the round 3 submission of Dilithium [Dilithium]. 3. Let k denote a random value generated modulo q. k shall not be zero. 4. The point kG is computed; its X coordinate (a member of the field over which E is defined) is converted to an integer, which is reduced modulo q, yielding r. If r turns out to be zero, a new k should be selected and r computed again. 5. s = k^(-1)(H(w, H(M))+ x*r) mod q. EDNOTE: decide which hash functions H to use 6. h = P(w, D(r, s) XOR PH(M)). (EDNOTE: decide which hash functions P, PH, D to use) 7. Compute c = cast(h,B), Let cast denote the SampleInBall function described in the Dilithium round 3 submission. 8. z = y + c*s1 9. S = (z, h, r, s) The tuple (z, h, r, s) is the signature. Nir Expires 21 December 2023 [Page 6] Internet-Draft AltCompSig June 2023 3.1.3. Encoding All fields will be encoded as OCTET STRING The private key is an OCTET STRING, a concatenation of the OCTET STRING representations of the ECDSA and Dilithium private keys. Public keys are similarly concatenations. The signature is an OCTET STRING, a concatenation of the OCTET STRING representation of z, h, r, and s. 3.1.4. Example TO BE ADDED 3.2. Fiat-Shamir and RSA TODO: A paragraph explaining that RSA is popular, and that Dilithium- RSA is desirable TODO: Add the FS-RSA construction (but not in draft -00) 3.3. Fiat-Shamir and Falcon TODO: Add the FS-Falcon construction (but not in draft -00) 3.4. RSA and Falcon TODO: Add the RSA-Falcon construction (but not in draft -00) 4. IANA Considerations To Be Added. We need at least OIDs for the combinations above. 5. Comparison with Other Proposals TODO: Add here a discussion of the differences between this proposal and draft-ounsworth. Need to cover both advantages (SNS, SV) and disadvantages: backward compatibility. 6. Security Considerations Security considerations appear in this document, specifically in Section 2.2 and Section 2.3, when discussing SNS and BC. Proofs of the security of the constructions described in Section 3 are given in the Bindel-Hale article. Nir Expires 21 December 2023 [Page 7] Internet-Draft AltCompSig June 2023 7. References 7.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC6979] Pornin, T., "Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)", RFC 6979, DOI 10.17487/RFC6979, August 2013, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . 7.2. Informative References [Bindel23] Bindel, N. and B. Hale, "A Note on Hybrid Signature Schemes", 2023, . [Dilithium] Bai, S., Ducas, L., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., and D. Stehle, "CRYSTALS- Dilithium Algorithm Specifications and Supporting Documentation", 2021, . [I-D.ounsworth-pq-composite-sigs] Ounsworth, M., Gray, J., and M. Pala, "Composite Signatures For Use In Internet PKI", Work in Progress, Internet-Draft, draft-ounsworth-pq-composite-sigs-09, 29 May 2023, . [NIST-PQC] National Institute of Standards and Technology (NIST), "Post-Quantum Cryptography Project", 20 December 2016, . [SIKE-BREAK] Castryck, W. and T. Decru, "An efficient key recovery attack on SIDH", 2022, . Nir Expires 21 December 2023 [Page 8] Internet-Draft AltCompSig June 2023 Appendix A. Change Log RFC EDITOR: PLEASE REMOVE THIS SECTION AS IT IS ONLY MEANT TO AID THE WORKING GROUP IN TRACKING CHANGES TO THIS DOCUMENT. draft-nir-lamps-altcompsigs-00 - first version. Author's Address Yoav Nir Dell Technologies 9 Andrei Sakharov St Haifa 3190500 Israel Email: ynir.ietf@gmail.com Nir Expires 21 December 2023 [Page 9]