Internet-Draft SPHINCS+ Signature Algorithm in CMS August 2022
Housley, et al. Expires 20 February 2023 [Page]
Workgroup:
Network Working Group
Internet-Draft:
draft-housley-lamps-cms-sphincs-plus-00
Published:
Intended Status:
Standards Track
Expires:
Authors:
R. Housley
Vigil Security
S. Fluhrer
Cisco Systems
P. Kampanakis
Amazon Web Services
B. Westerbaan
Cloudflare

Use of the SPHINCS+ Signature Algorithm in the Cryptographic Message Syntax (CMS)

Abstract

SPHINCS+ is a stateless hash-based signature scheme. This document specifies the conventions for using the SPHINCS+ stateless hash-based signature algorithm with the Cryptographic Message Syntax (CMS). In addition, the algorithm identifier and public key syntax are provided.

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 20 February 2023.

Table of Contents

1. Introduction

NOTICE: This document will be adjusted to match the SPHINCS+ specification that is published by NIST. Until that happens, just about everything in this document is likely to change.

This document specifies the conventions for using the SPHINCS+ hash-based signature algorithm (add reference to the NIST document here) with the Cryptographic Message Syntax (CMS) [RFC5652] signed-data content type.

SPHINCS+ offers three security levels. The parameters for each of the security levels were chosen to provide 128 bits of security, 192 bits of security, and 256 bits of security. A separate algorithm identifier has been assigned for SPHINCS+ at each of these security levels.

SPHINCS+ is a stateless hash-based signature algorithm. Other hash-based signature algorithms are stateful, including HSS/LMS [RFC8554] and XMSS [RFC8391]. Without the need for state kept by the signer, SPHINCS+ is much less fragile.

1.1. ASN.1

CMS values are generated using ASN.1 [X680], using the Basic Encoding Rules (BER) and the Distinguished Encoding Rules (DER) [X690].

1.2. Motivation

There have been recent advances in cryptanalysis and advances in the development of quantum computers. Each of these advances pose a threat to widely deployed digital signature.

If large-scale quantum computers are ever built, they will be able to break many of the public-key cryptosystems currently in use, including RSA, DSA, ECDSA, and EdDSA. A post-quantum cryptosystem (PQC) is secure against quantum computers that have more than a trivial number of quantum bits (qu-bits). It is open to conjecture when it will be feasible to build such quantum computers; however, it is prudent to use cryptographic algorithms that remain secure if a large-scale quantum computer is invented. SPHINCS+ is a PQC signature algorithm.

One use of a PQC signature algoritm is the protection of software updates, perhaps using the format described in [RFC4108], to enable deployment of software that implements other new PQC algorithms for key management and confidentiality.

1.3. Terminology

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "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. SPHINCS+ Hash-based Signature Algorithm Overview

SPHINCS+ is a hash-based signature scheme which consists of a few time signature construction, namely Forest of Random Subsets (FORS) and a hypertree. FORS signs a message with a private key. The corresponding FIPS public keys are the leaves in k binary trees. The roots of these trees are hashed together to form a FORS root. The FORS tree roots are signed by a WOTS+ one-time signature private key. The corresponding WOTS+ public keys form the leaves in d-layers of Merkle subtrees in the SPHINCS+ hypertree. The bottom layer of that hypertree signs (with WOTS+) the FORS roots. The root of the bottom Merkle subtrees are then signed with WOTS+ and the corresponding WOTS+ public keys form the leaves of the next level up subtree. Subtree roots are consequently signed by their corresponding subtree layers until we reach the top subtree. The top layer subtree forms the hypertree root which is trusted at the verifier.

A SPHINCS+ signature consists of the FORS signature, the WOTS+ signature in each layer and the path to the root of each subtree until we reach the root of the hypertree. The signature is verified by verifying the FORS signature, the WOTS+ signatures and the path to the root of each subtree. When reaching the root of the hypertree, the signature verifies only if it hashes to the pre-trusted root of the SPHINCS+ hypertree.

SPHINCS+ is a stateless hash-based signature algorithm. Stateful hash-based signature schemes require that the WOTS+ private key (generated by using a state index) is never reused or the scheme loses it security. Although its security decreases, FORS which is used at the bottom of the SPHINCS+ hypertree does not collapse if the same private key used to sign two or more different messages like in stateful hash-based signature schemes. Without the need for state kept by the signer to ensure it is not reused, SPHINCS+ is much less fragile.

SPHINCS+ was designed to sign up to 2^64 messages and offers three security levels. The parameters of the SPHINCS+ hypertree include the security parameter, the hash function, the tree height, the number of layers of subtrees, the Winternitz parameter of WOTS+, the number of FORS trees and leaves in each. The parameters for each of the security levels were chosen to provide 128 bits of security, 192 bits of security, and 256 bits of security.

3. SPHINCS+ Public Key Identifier

The AlgorithmIdentifier for an SPHINCS+ public key uses the id-alg-sphincs-plus object identifier, and the parameters field MUST be absent.

When this AlgorithmIdentifier appears in the SubjectPublicKeyInfo field of an X.509 certificate [RFC5280], the certificate key usage extension MAY contain digitalSignature, nonRepudiation, keyCertSign, and cRLSign; the certificate key usage extension MUST NOT contain other values.

   pk-sphincs-plus-128 PUBLIC-KEY ::= {
       IDENTIFIER id-alg-sphincs-plus-128
       KEY SPHINCS-Plus-PublicKey
       PARAMS ARE absent
       CERT-KEY-USAGE
         { digitalSignature, nonRepudiation, keyCertSign, cRLSign } }

   pk-sphincs-plus-192 PUBLIC-KEY ::= {
       IDENTIFIER id-alg-sphincs-plus-192
       KEY SPHINCS-Plus-PublicKey
       PARAMS ARE absent
       CERT-KEY-USAGE
         { digitalSignature, nonRepudiation, keyCertSign, cRLSign } }

   pk-sphincs-plus-256 PUBLIC-KEY ::= {
       IDENTIFIER id-alg-sphincs-plus-256
       KEY SPHINCS-Plus-PublicKey
       PARAMS ARE absent
       CERT-KEY-USAGE
         { digitalSignature, nonRepudiation, keyCertSign, cRLSign } }

   SPHINCS-Plus-PublicKey ::= OCTET STRING

The SPHINCS+ public key value is an OCTET STRING. (Should we say something more here about the size?)

4. Signed-data Conventions

As specified in CMS [RFC5652], the digital signature is produced from the message digest and the signer's private key. The signature is computed over different values depending on whether signed attributes are absent or present.

When signed attributes are absent, the SPHINCS+ signature is computed over the content. When signed attributes are present, a hash is computed over the content using the same hash function that is used in the SPHINCS+ tree, and then a message-digest attribute is constructed to contain the resulting hash value, and then the result of DER encoding the set of signed attributes, which MUST include a content-type attribute and a message-digest attribute, and then the SPHINCS+ signature is computed over the DER-encoded output. In summary:

   IF (signed attributes are absent)
   THEN SPHINCS+_Sign(content)
   ELSE message-digest attribute = Hash(content);
        SPHINCS+_Sign(DER(SignedAttributes))

When using SPHINCS+, the fields in the SignerInfo are used as follows:

digestAlgorithm:

The digestAlgorithm MUST contain the one-way hash function used to in the SPHINCS+ tree. The algorithm identifiers for [FIPS180] and [FIPS202] are repeated below for convenience.

      mda-sha256 DIGEST-ALGORITHM ::= {
        IDENTIFIER id-sha256
        PARAMS TYPE NULL ARE preferredAbsent }

      mda-shake256 DIGEST-ALGORITHM ::= {
        IDENTIFIER id-shake256
        PARAMS TYPE NULL ARE preferredAbsent }

      hashalgs OBJECT IDENTIFIER ::= { joint-iso-itu-t(2)
        country(16) us(840) organization(1) gov(101) csor(3)
        nistAlgorithms(4) 2 }

      id-sha256 OBJECT IDENTIFIER ::= { hashalgs 1 }

      id-shake256 OBJECT IDENTIFIER ::= { hashAlgs 12 }
signatureAlgorithm:

The signatureAlgorithm MUST contain one of the the SPHINCS+ algorithm identifiers, and the algorithm parameters field MUST be absent. The algorithm identifier MUST be one of the following: id-alg-sphincs-plus-128, id-alg-sphincs-plus-192, or id-alg-sphincs-plus-256.

signature:

The signature contains the signature value resulting from the SPHINCS+ signing operation with the parameters associated with the selected signatureAlgorithm. The SPHINCS+ signing operation and the signature verification operation are specified in TBD.

5. Security Considerations

Implementations MUST protect the private keys. Compromise of the private keys may result in the ability to forge signatures. Along with the private key, the implementation MUST keep track of which leaf nodes in the tree have been used. Loss of integrity of this tracking data can cause a one-time key to be used more than once. As a result, when a private key and the tracking data are stored on non-volatile media or stored in a virtual machine environment, care must be taken to preserve confidentiality and integrity.

When generating an SPHINCS+ key pair, an implementation MUST generate each key pair independently of all other key pairs in the SPHINCS+ tree.

A SPHINCS+ tree MUST NOT be used for more than 2^64 signing operations.

The generation of private keys relies on random numbers. The use of inadequate pseudo-random number generators (PRNGs) to generate these values can result in little or no security. An attacker may find it much easier to reproduce the PRNG environment that produced the keys, searching the resulting small set of possibilities, rather than brute force searching the whole key space. The generation of quality random numbers is difficult, and [RFC4086] offers important guidance in this area.

When computing signatures, the same hash function SHOULD be used to compute the message digest of the content and the signed attributes, if they are present.

When computing signatures, implementations SHOULD include protections against fault injection attacks [CMP2018]. Protections against these attacks include signature verification prior to releasing the signature value to confirm that no error injected and generating the signature a few times to confirm that the same signature value is produced each time.

6. IANA Considerations

TBD

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, , <https://www.rfc-editor.org/info/rfc2119>.
[RFC5280]
Cooper, D., Santesson, S., Farrell, S., Boeyen, S., Housley, R., and W. Polk, "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, , <https://www.rfc-editor.org/info/rfc5280>.
[RFC5652]
Housley, R., "Cryptographic Message Syntax (CMS)", STD 70, RFC 5652, DOI 10.17487/RFC5652, , <https://www.rfc-editor.org/info/rfc5652>.
[RFC8174]
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <https://www.rfc-editor.org/info/rfc8174>.
[X680]
ITU-T, "Information technology -- Abstract Syntax Notation One (ASN.1): Specification of basic notation", ITU-T Recommendation X.680, ISO/IEC 8824-1:2021, , <https://www.itu.int/rec/T-REC-X.680>.
[X690]
ITU-T, "Information technology -- ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER)", ITU-T Recommendation X.690, ISO/IEC 8825-1-2021, , <https://www.itu.int/rec/T-REC-X.690>.

7.2. Informative References

[CMP2018]
Castelnovi, L., A, Martinelli, and T. Prest, "Grafting Trees: A Fault Attack Against the SPHINCS Framework", Post-Quantum Cryptography pp. 165-184, PQCrypto 2018, Lecture Notes in Computer Science vol 10786, , <https://link.springer.com/chapter/10.1007/978-3-319-79063-3_8>.
[FIPS180]
National Institute of Standards and Technology (NIST), "Secure Hash Standard (SHS)", FIPS PUB 180-4, .
[FIPS202]
National Institute of Standards and Technology (NIST), "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions", FIPS PUB 202, .
[RFC4086]
Eastlake 3rd, D., Schiller, J., and S. Crocker, "Randomness Requirements for Security", BCP 106, RFC 4086, DOI 10.17487/RFC4086, , <https://www.rfc-editor.org/info/rfc4086>.
[RFC4108]
Housley, R., "Using Cryptographic Message Syntax (CMS) to Protect Firmware Packages", RFC 4108, DOI 10.17487/RFC4108, , <https://www.rfc-editor.org/info/rfc4108>.
[RFC5911]
Hoffman, P. and J. Schaad, "New ASN.1 Modules for Cryptographic Message Syntax (CMS) and S/MIME", RFC 5911, DOI 10.17487/RFC5911, , <https://www.rfc-editor.org/info/rfc5911>.
[RFC8391]
Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. Mohaisen, "XMSS: eXtended Merkle Signature Scheme", RFC 8391, DOI 10.17487/RFC8391, , <https://www.rfc-editor.org/info/rfc8391>.
[RFC8554]
McGrew, D., Curcio, M., and S. Fluhrer, "Leighton-Micali Hash-Based Signatures", RFC 8554, DOI 10.17487/RFC8554, , <https://www.rfc-editor.org/info/rfc8554>.

Appendix A. Appendix: ASN.1 Module

This ASN.1 Module builds upon the conventions established in [RFC5911].

<CODE STARTS>

SPHINCS-Plus-Module-2022
  { iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9)
    id-smime(16) id-mod(0) id-mod-sphincs-plus-2022(TBD) }

DEFINITIONS IMPLICIT TAGS ::= BEGIN

EXPORTS ALL;

IMPORTS
  PUBLIC-KEY, SIGNATURE-ALGORITHM, SMIME-CAPS
    FROM AlgorithmInformation-2009  -- RFC 5911
      { iso(1) identified-organization(3) dod(6) internet(1)
        security(5) mechanisms(5) pkix(7) id-mod(0)
        id-mod-algorithmInformation-02(58) } ;

--
-- Object Identifiers
--

id-alg-sphincs-plus-128 OBJECT IDENTIFIER ::= { TBD }

id-alg-sphincs-plus-192 OBJECT IDENTIFIER ::= { TBD }

id-alg-sphincs-plus-256 OBJECT IDENTIFIER ::= { TBD }

--
-- Signature Algorithm and Public Key
--

sa-sphincs-plus-128 SIGNATURE-ALGORITHM ::= {
    IDENTIFIER id-alg-sphincs-plus-128
    PARAMS ARE absent
    PUBLIC-KEYS { pk-sphincs-plus-128 }
    SMIME-CAPS { IDENTIFIED BY id-alg-sphincs-plus-128 } }

sa-sphincs-plus-192 SIGNATURE-ALGORITHM ::= {
    IDENTIFIER id-alg-sphincs-plus-192
    PARAMS ARE absent
    PUBLIC-KEYS { pk-sphincs-plus-192 }
    SMIME-CAPS { IDENTIFIED BY id-alg-sphincs-plus-192 } }

sa-sphincs-plus-256 SIGNATURE-ALGORITHM ::= {
    IDENTIFIER id-alg-sphincs-plus-256
    PARAMS ARE absent
    PUBLIC-KEYS { pk-sphincs-plus-256 }
    SMIME-CAPS { IDENTIFIED BY id-alg-sphincs-plus-256 } }

pk-sphincs-plus-128 PUBLIC-KEY ::= {
    IDENTIFIER id-alg-sphincs-plus-128
    KEY SPHINCS-Plus-PublicKey
    PARAMS ARE absent
    CERT-KEY-USAGE
        { digitalSignature, nonRepudiation, keyCertSign, cRLSign } }

pk-sphincs-plus-192 PUBLIC-KEY ::= {
    IDENTIFIER id-alg-sphincs-plus-192
    KEY SPHINCS-Plus-PublicKey
    PARAMS ARE absent
    CERT-KEY-USAGE
        { digitalSignature, nonRepudiation, keyCertSign, cRLSign } }

pk-sphincs-plus-256 PUBLIC-KEY ::= {
    IDENTIFIER id-alg-sphincs-plus-256
    KEY SPHINCS-Plus-PublicKey
    PARAMS ARE absent
    CERT-KEY-USAGE
        { digitalSignature, nonRepudiation, keyCertSign, cRLSign } }

SPHINCS-Plus-PublicKey ::= OCTET STRING

--
-- Expand the signature algorithm set used by CMS [RFC5911]
--

SignatureAlgorithmSet SIGNATURE-ALGORITHM ::=
    { sa-sphincs-plus-128 |
      sa-sphincs-plus-192 |
      sa-sphincs-plus-256,
      ... }

--
-- Expand the S/MIME capabilities set used by CMS [RFC5911]
--

SMimeCaps SMIME-CAPS ::=
    { sa-sphincs-plus-128.&smimeCaps |
      sa-sphincs-plus-192.&smimeCaps |
      sa-sphincs-plus-256.&smimeCaps,
      ... }

END

<CODE ENDS>

Authors' Addresses

Russ Housley
Vigil Security, LLC
Scott Fluhrer
Cisco Systems
Panos Kampanakis
Amazon Web Services
Bas Westerbaan
Cloudflare