Internet DRAFT - draft-nir-lamps-altcompsigs
draft-nir-lamps-altcompsigs
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,
<https://www.rfc-editor.org/info/rfc2119>.
[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, <https://www.rfc-editor.org/info/rfc6979>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
7.2. Informative References
[Bindel23] Bindel, N. and B. Hale, "A Note on Hybrid Signature
Schemes", 2023, <https://eprint.iacr.org/2023/423.pdf>.
[Dilithium]
Bai, S., Ducas, L., Lepoint, T., Lyubashevsky, V.,
Schwabe, P., Seiler, G., and D. Stehle, "CRYSTALS-
Dilithium Algorithm Specifications and Supporting
Documentation", 2021, <https://pq-
crystals.org/dilithium/data/dilithium-specification-
round3-20210208.pdf>.
[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, <https://datatracker.ietf.org/doc/html/draft-
ounsworth-pq-composite-sigs-09>.
[NIST-PQC] National Institute of Standards and Technology (NIST),
"Post-Quantum Cryptography Project", 20 December 2016,
<https://csrc.nist.gov/Projects/post-quantum-
cryptography>.
[SIKE-BREAK]
Castryck, W. and T. Decru, "An efficient key recovery
attack on SIDH", 2022,
<https://eprint.iacr.org/2022/975.pdf>.
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]
