draft-hale-pquip-hybrid-signature-spectrums-03.txt		draft-hale-pquip-hybrid-signature-spectrums-04.txt
	Network Working Group N. Bindel		Network Working Group N. Bindel
	Internet-Draft SandboxAQ		Internet-Draft SandboxAQ
	Intended status: Informational B. Hale		Intended status: Informational B. Hale
	Expires: 26 August 2024 Naval Postgraduate School		Expires: 22 September 2024 Naval Postgraduate School
	D. Connolly		D. Connolly
	SandboxAQ		SandboxAQ
	F. Driscoll		F. Driscoll
	UK National Cyber Security Centre		UK National Cyber Security Centre
	23 February 2024		21 March 2024
	Hybrid signature spectrums		Hybrid signature spectrums
	draft-hale-pquip-hybrid-signature-spectrums-03		draft-hale-pquip-hybrid-signature-spectrums-04
	Abstract		Abstract
	This document describes classification of design goals and security		This document describes classification of design goals and security
	considerations for hybrid digital signature schemes, including proof		considerations for hybrid digital signature schemes, including proof
	composability, non-separability of the component signatures given a		composability, non-separability of the component signatures given a
	hybrid signature, backwards/forwards compatiblity, hybrid generality,		hybrid signature, backwards/forwards compatiblity, hybrid generality,
	and simultaneous verification.		and simultaneous verification.
	Discussion of this work is encouraged to happen on the IETF PQUIP		Discussion of this work is encouraged to happen on the IETF PQUIP
	mailing list pqc@ietf.org or on the GitHub repository which contains		mailing list pqc@ietf.org or on the GitHub repository which contains
	the draft: https://github.com/dconnolly/draft-hale-pquip-hybrid-		the draft: https://github.com/dconnolly/draft-hale-pquip-hybrid-
	signature-spectrums		signature-spectrums
	Discussion Venues
	This note is to be removed before publishing as an RFC.
	Discussion of this document takes place on the Post-Quantum Use In
	Protocols Working Group mailing list (pqc@ietf.org), which is
	archived at https://mailarchive.ietf.org/arch/browse/pqc/.
	Source for this draft and an issue tracker can be found at
	https://github.com/dconnolly/draft-connolly-pquip-hybrid-signature-
	spectrums.
	Status of This Memo		Status of This Memo
	This Internet-Draft is submitted in full conformance with the		This Internet-Draft is submitted in full conformance with the
	provisions of BCP 78 and BCP 79.		provisions of BCP 78 and BCP 79.
	Internet-Drafts are working documents of the Internet Engineering		Internet-Drafts are working documents of the Internet Engineering
	Task Force (IETF). Note that other groups may also distribute		Task Force (IETF). Note that other groups may also distribute
	working documents as Internet-Drafts. The list of current Internet-		working documents as Internet-Drafts. The list of current Internet-
	Drafts is at https://datatracker.ietf.org/drafts/current/.		Drafts is at https://datatracker.ietf.org/drafts/current/.
	Internet-Drafts are draft documents valid for a maximum of six months		Internet-Drafts are draft documents valid for a maximum of six months
	and may be updated, replaced, or obsoleted by other documents at any		and may be updated, replaced, or obsoleted by other documents at any
	time. It is inappropriate to use Internet-Drafts as reference		time. It is inappropriate to use Internet-Drafts as reference
	material or to cite them other than as "work in progress."		material or to cite them other than as "work in progress."
	This Internet-Draft will expire on 26 August 2024.		This Internet-Draft will expire on 22 September 2024.
	Copyright Notice		Copyright Notice
	Copyright (c) 2024 IETF Trust and the persons identified as the		Copyright (c) 2024 IETF Trust and the persons identified as the
	document authors. All rights reserved.		document authors. All rights reserved.
	This document is subject to BCP 78 and the IETF Trust's Legal		This document is subject to BCP 78 and the IETF Trust's Legal
	Provisions Relating to IETF Documents (https://trustee.ietf.org/		Provisions Relating to IETF Documents (https://trustee.ietf.org/
	license-info) in effect on the date of publication of this document.		license-info) in effect on the date of publication of this document.
	Please review these documents carefully, as they describe your rights		Please review these documents carefully, as they describe your rights
	skipping to change at page 2, line 39 ¶		skipping to change at page 2, line 27 ¶
	1.1. Revision history . . . . . . . . . . . . . . . . . . . . 4		1.1. Revision history . . . . . . . . . . . . . . . . . . . . 4
	1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4		1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4
	1.3. Motivation for use of hybrid signature schemes . . . . . 6		1.3. Motivation for use of hybrid signature schemes . . . . . 6
	1.3.1. *Complexity* . . . . . . . . . . . . . . . . . . . . 6		1.3.1. *Complexity* . . . . . . . . . . . . . . . . . . . . 6
	1.3.2. *Time* . . . . . . . . . . . . . . . . . . . . . . . 7		1.3.2. *Time* . . . . . . . . . . . . . . . . . . . . . . . 7
	1.4. Goals . . . . . . . . . . . . . . . . . . . . . . . . . . 8		1.4. Goals . . . . . . . . . . . . . . . . . . . . . . . . . . 8
	1.4.1. *Hybrid Authentication* . . . . . . . . . . . . . . . 8		1.4.1. *Hybrid Authentication* . . . . . . . . . . . . . . . 8
	1.4.2. *Proof Composability* . . . . . . . . . . . . . . . . 9		1.4.2. *Proof Composability* . . . . . . . . . . . . . . . . 9
	1.4.3. *Weak Non-Separability* . . . . . . . . . . . . . . . 9		1.4.3. *Weak Non-Separability* . . . . . . . . . . . . . . . 9
	1.4.4. *Strong Non-Separability* . . . . . . . . . . . . . . 10		1.4.4. *Strong Non-Separability* . . . . . . . . . . . . . . 10
	1.4.5. *Backwards/Forwards Compatibility* . . . . . . . . . 10		1.4.5. *Backwards/Forwards Compatibility* . . . . . . . . . 11
	1.4.6. *Simultaneous Verification* . . . . . . . . . . . . . 11		1.4.6. *Simultaneous Verification* . . . . . . . . . . . . . 11
	1.4.7. *Hybrid Generality* . . . . . . . . . . . . . . . . . 12		1.4.7. *Hybrid Generality* . . . . . . . . . . . . . . . . . 12
	1.4.8. *High performance* . . . . . . . . . . . . . . . . . 12		1.4.8. *High performance* . . . . . . . . . . . . . . . . . 12
	1.4.9. *High space efficiency* . . . . . . . . . . . . . . . 12		1.4.9. *High space efficiency* . . . . . . . . . . . . . . . 12
	1.4.10. *Minimal duplicate information* . . . . . . . . . . . 12		1.4.10. *Minimal duplicate information* . . . . . . . . . . . 12
	2. Non-separability spectrum . . . . . . . . . . . . . . . . . . 12		2. Non-separability spectrum . . . . . . . . . . . . . . . . . . 13
	3. Artifacts . . . . . . . . . . . . . . . . . . . . . . . . . . 14		3. Artifacts . . . . . . . . . . . . . . . . . . . . . . . . . . 14
	3.1. Artifact locations . . . . . . . . . . . . . . . . . . . 15		3.1. Artifact locations . . . . . . . . . . . . . . . . . . . 15
	3.2. Artifact Location Comparison Example . . . . . . . . . . 15		3.2. Artifact Location Comparison Example . . . . . . . . . . 16
	4. Need-For-Approval Spectrum . . . . . . . . . . . . . . . . . 19		4. Need-For-Approval Spectrum . . . . . . . . . . . . . . . . . 19
	5. EUF-CMA Challenges . . . . . . . . . . . . . . . . . . . . . 21		5. EUF-CMA Challenges . . . . . . . . . . . . . . . . . . . . . 21
	6. Security Considerations . . . . . . . . . . . . . . . . . . . 21		6. Security Considerations . . . . . . . . . . . . . . . . . . . 21
	7. Discussion of Advantages/Disadvantages . . . . . . . . . . . 21		7. Discussion of Advantages/Disadvantages . . . . . . . . . . . 21
	7.1. Backwards compatibility vs. SNS. . . . . . . . . . . . . 21		7.1. Backwards compatibility vs. SNS. . . . . . . . . . . . . 21
	7.2. Backwards compatibility vs. hybrid unforgeability. . . . 22		7.2. Backwards compatibility vs. hybrid unforgeability. . . . 22
	7.3. Simultaneous verification vs. low need for approval. . . 22		7.3. Simultaneous verification vs. low need for approval. . . 22
	8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 22		8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 22
	9. Informative References . . . . . . . . . . . . . . . . . . . 22		9. Informative References . . . . . . . . . . . . . . . . . . . 22
	Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 24		Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 24
	skipping to change at page 3, line 26 ¶		skipping to change at page 3, line 20 ¶
	traditional algorithms could be decrypted in the future by an		traditional algorithms could be decrypted in the future by an
	attacker with a Cryptographically-Relevant Quantum Computer (CRQC).		attacker with a Cryptographically-Relevant Quantum Computer (CRQC).
	While traditional authentication is only at risk once a CRQC exists,		While traditional authentication is only at risk once a CRQC exists,
	it is important to consider the transition to post-quantum		it is important to consider the transition to post-quantum
	authentication before this point. This is particularly relevant for		authentication before this point. This is particularly relevant for
	systems where algorithm turn-over is complex or takes a long time		systems where algorithm turn-over is complex or takes a long time
	(e.g., long-lived systems with hardware roots of trust), or where		(e.g., long-lived systems with hardware roots of trust), or where
	future checks on past authenticity play a role (e.g., digital		future checks on past authenticity play a role (e.g., digital
	signatures on legal documents).		signatures on legal documents).
	One approach to design quantum-resistant protocols, particularly		The relative newness of many (although not all) post-quantum
	during the transition period from traditional to post-quantum		algorithms means that less cryptanalysis of such algorithms is
	algorithms, is incorporating hybrid signatures schemes, which combine		available than for long-established counterparts, such as RSA and
	both traditional and post-quantum (or more generally next-generation)		elliptic-curve based solutions for confidentiality and authenticity.
	algorithms in one cryptographic scheme. Hybridization has been		This has drawn attention to hybrid cryptographic schemes, which
	looked at for key encapsulation [HYBRIDKEM], and in an initial sense		combine both traditional and post-quantum (or more generally next-
	for digital signatures [HYBRIDSIG]. Compared to key encapsulation,		generation) algorithms in one cryptographic scheme. These may offer
	hybridization of digital signatures, where the verification tag may		increased assurance for implementers, namely that as long as the
	be expected to attest to both standard and post-quantum components,		security of one of the two component algorithms of the hybrid scheme
	is subtler to design and implement due to the potential separability		holds, the confidentiality or authenticity offered by that scheme is
	of the hybrid/dual signatures and the risk of downgrade/stripping		maintained.
	attacks. There are also a range of requirements and properties that
	may be required from dual signatures, not all of which can be		Whether or not hybridization is desired depends on the use case and
	achieved at once.		security threat model. Conservative users may not have complete
			trust in the post-quantum algorithms or implementations available,
			while also recognizing a need to start post-quantum transition. For
			such users, hybridization can support near-term transition while also
			avoiding trusting solo post-quantum algorithms too early. On the
			other hand, hybrid schemes, particularly for authentication, may
			introduce significant complexity into a system or a migration
			process, so might not be the right choice for all. For cases where
			hybridization is determined to be advantageous, a decision on how to
			hybridize needs to be made. With many options available, this
			document is intended to provide context on some of the trade-offs and
			nuances to consider.
			Hybridization has been looked at for key encapsulation [HYBRIDKEM],
			and in an initial sense for digital signatures [HYBRIDSIG]. Compared
			to key encapsulation, hybridization of digital signatures, where the
			verification tag may be expected to attest to both standard and post-
			quantum components, is subtler to design and implement due to the
			potential separability of the hybrid/dual signatures and the risk of
			downgrade/stripping attacks. There are also a range of requirements
			and properties that may be required from hybrid signatures, not all
			of which can be achieved at once.
	This document focuses on explaining advantages and disadvantages of		This document focuses on explaining advantages and disadvantages of
	different hybrid signature scheme designs and different security		different hybrid signature scheme designs and different security
	goals for them. It is intended as a resource for designers and		goals for them. It is intended as a resource for designers and
	implementers of hybrid signature schemes to help them decide what		implementers of hybrid signature schemes to help them decide what
	properties they do and do not require from their scheme. It		properties they do and do not require from their scheme. It does not
			attempt to answer the question of whether or not a hybrid scheme is
			desirable for, or should be used in a given case. It also
	intentionally does not propose concrete hybrid signature combiners or		intentionally does not propose concrete hybrid signature combiners or
	instantiations thereof.		instantiations thereof.
	1.1. Revision history		1.1. Revision history
	*RFC Editor's Note:* Please remove this section prior to		*RFC Editor's Note:* Please remove this section prior to
	publication of a final version of this document.		publication of a final version of this document.
	* 01: Significant fleshing out after feedback from IETF 118.		* 01: Significant fleshing out after feedback from IETF 118.
	skipping to change at page 6, line 41 ¶		skipping to change at page 7, line 9 ¶
	traditional algorithms, such as RSA. RSA is a relatively simple		traditional algorithms, such as RSA. RSA is a relatively simple
	algorithm to understand and explain, yet during its existence and use		algorithm to understand and explain, yet during its existence and use
	there have been multiple attacks and refinements, such as adding		there have been multiple attacks and refinements, such as adding
	requirements to how padding and keys are chosen, and implementation		requirements to how padding and keys are chosen, and implementation
	issues such as cross-protocol attacks. Thus, even in a relatively		issues such as cross-protocol attacks. Thus, even in a relatively
	simple algorithm subtleties and caveats on implementation and use can		simple algorithm subtleties and caveats on implementation and use can
	arise over time. Given the complexity of next generation algorithms,		arise over time. Given the complexity of next generation algorithms,
	the chance of such discoveries and caveats needs to be taken into		the chance of such discoveries and caveats needs to be taken into
	account.		account.
	Of note, next generation algorithms have been heavily vetted. Thus,		Of note, some next generation algorithms have received substantial
	if and when further information on caveats and implementation issues		analysis attention, for example through the NIST Post-Quantum Process
	come to light, it is less likely that a "break" will be catastrophic.		[NIST_PQC_FAQ]. Thus, if and when further information on caveats and
	Instead, such vulnerabilities and issues may represent a weakening of		implementation issues come to light, it is less likely that a "break"
	security - which may in turn be offset if a hybrid approach has been		will be catastrophic. Instead, such vulnerabilities and issues may
	used. The complexity of post-quantum algorithms needs to be balanced		represent a weakening of security - which may in turn be offset if a
	against the fact that hybridization itself adds more complexity to a		hybrid approach has been used. The complexity of post-quantum
	protocol and introduces the risk of implementation mistakes in the		algorithms needs to be balanced against the fact that hybridization
	hybridization process.		itself adds more complexity to a protocol and introduces the risk of
			implementation mistakes in the hybridization process.
	One example of a next generation algorithm is the signature scheme		One example of a next generation algorithm is the signature scheme
	ML-DSA (a.k.a. CRYSTALS-Dilithium) that has been selected for		ML-DSA (a.k.a. CRYSTALS-Dilithium) that has been selected for
	standardization by NIST. While the scheme follows the well-known		standardization by NIST. While the scheme follows the well-known
	Fiat-Shamir transform to construct the signature scheme, it also		Fiat-Shamir transform to construct the signature scheme, it also
	relies on rejection sampling that is known to give cache side channel		relies on rejection sampling that is known to give cache side channel
	information (although this does not lead to a known attack).		information (although this does not lead to a known attack).
	Furthermore, recent attacks again the post-quantum multivariate		Furthermore, recent attacks again the post-quantum multivariate
	schemes Rainbow and GeMSS might call into question the asymptotic and		schemes Rainbow and GeMSS might call into question the asymptotic and
	concrete security for conservative adopters and therefore might		concrete security for conservative adopters and therefore might
	skipping to change at page 23, line 39 ¶		skipping to change at page 23, line 39 ¶
	[I-D.ietf-tls-hybrid-design]		[I-D.ietf-tls-hybrid-design]
	Stebila, D., Fluhrer, S., and S. Gueron, "Hybrid key		Stebila, D., Fluhrer, S., and S. Gueron, "Hybrid key
	exchange in TLS 1.3", Work in Progress, Internet-Draft,		exchange in TLS 1.3", Work in Progress, Internet-Draft,
	draft-ietf-tls-hybrid-design-09, 7 September 2023,		draft-ietf-tls-hybrid-design-09, 7 September 2023,
	<https://datatracker.ietf.org/doc/html/draft-ietf-tls-		<https://datatracker.ietf.org/doc/html/draft-ietf-tls-
	hybrid-design-09>.		hybrid-design-09>.
	[I-D.ounsworth-pq-composite-sigs]		[I-D.ounsworth-pq-composite-sigs]
	Ounsworth, M., Gray, J., Pala, M., and J. Klaußner,		Ounsworth, M., Gray, J., Pala, M., and J. Klaußner,
	"Composite Signatures For Use In Internet PKI", Work in		"Composite ML-DSA for use in Internet PKI", Work in
	Progress, Internet-Draft, draft-ounsworth-pq-composite-		Progress, Internet-Draft, draft-ounsworth-pq-composite-
	sigs-12, 11 February 2024,		sigs-13, 4 March 2024,
	<https://datatracker.ietf.org/doc/html/draft-ounsworth-pq-		<https://datatracker.ietf.org/doc/html/draft-ounsworth-pq-
	composite-sigs-12>.		composite-sigs-13>.
	[MOSCA] Kaye, P., Laflamme, R., and M. Mosca, "An Introduction to		[MOSCA] Kaye, P., Laflamme, R., and M. Mosca, "An Introduction to
	Quantum Computing, Oxford University Press", November		Quantum Computing, Oxford University Press", November
	2007.		2007.
	[NIST_PQC_FAQ]		[NIST_PQC_FAQ]
	National Institute of Standards and Technology (NIST),		National Institute of Standards and Technology (NIST),
	"Post-Quantum Cryptography FAQs", 5 July 2022,		"Post-Quantum Cryptography FAQs", 5 July 2022,
	<https://csrc.nist.gov/Projects/post-quantum-cryptography/		<https://csrc.nist.gov/Projects/post-quantum-cryptography/
	faqs>.		faqs>.
End of changes. 14 change blocks.
	46 lines changed or deleted		58 lines changed or added
This html diff was produced by rfcdiff 1.45. The latest version is available from http://tools.ietf.org/tools/rfcdiff/