draft-ietf-lamps-cms-hash-sig-09.txt   draft-ietf-lamps-cms-hash-sig-10.txt 
INTERNET-DRAFT R. Housley INTERNET-DRAFT R. Housley
Internet Engineering Task Force (IETF) Vigil Security Internet Engineering Task Force (IETF) Vigil Security
Intended Status: Proposed Standard Intended Status: Proposed Standard
Expires: 10 February 2020 10 August 2019 Expires: 18 March 2020 18 September 2019
Use of the HSS/LMS Hash-based Signature Algorithm Use of the HSS/LMS Hash-based Signature Algorithm
in the Cryptographic Message Syntax (CMS) in the Cryptographic Message Syntax (CMS)
<draft-ietf-lamps-cms-hash-sig-09> <draft-ietf-lamps-cms-hash-sig-10>
Abstract Abstract
This document specifies the conventions for using the Hierarchical This document specifies the conventions for using the Hierarchical
Signature System (HSS) / Leighton-Micali Signature (LMS) hash-based Signature System (HSS) / Leighton-Micali Signature (LMS) hash-based
signature algorithm with the Cryptographic Message Syntax (CMS). In signature algorithm with the Cryptographic Message Syntax (CMS). In
addition, the algorithm identifier and public key syntax are addition, the algorithm identifier and public key syntax are
provided. The HSS/LMS algorithm is one form of hash-based digital provided. The HSS/LMS algorithm is one form of hash-based digital
signature; it is described in RFC 8554. signature; it is described in RFC 8554.
skipping to change at page 3, line 16 skipping to change at page 3, line 16
This document specifies the conventions for using the Hierarchical This document specifies the conventions for using the Hierarchical
Signature System (HSS) / Leighton-Micali Signature (LMS) hash-based Signature System (HSS) / Leighton-Micali Signature (LMS) hash-based
signature algorithm with the Cryptographic Message Syntax (CMS) [CMS] signature algorithm with the Cryptographic Message Syntax (CMS) [CMS]
signed-data content type. The LMS system provides a one-time digital signed-data content type. The LMS system provides a one-time digital
signature that is a variant of Merkle Tree Signatures (MTS). The HSS signature that is a variant of Merkle Tree Signatures (MTS). The HSS
is built on top of the LMS system to efficiently scale for a larger is built on top of the LMS system to efficiently scale for a larger
numbers of signatures. The HSS/LMS algorithm is one form of hash- numbers of signatures. The HSS/LMS algorithm is one form of hash-
based digital signature, and it is described in [HASHSIG]. The based digital signature, and it is described in [HASHSIG]. The
HSS/LMS signature algorithm can only be used for a fixed number of HSS/LMS signature algorithm can only be used for a fixed number of
signing operations. The number of signing operations depends upon signing operations with a given private key, and the number of
the size of the tree. The HSS/LMS signature algorithm uses small signing operations depends upon the size of the tree. The HSS/LMS
public keys, and it has low computational cost; however, the signature algorithm uses small public keys, and it has low
signatures are quite large. The HSS/LMS private key can be very computational cost; however, the signatures are quite large. The
small when the signer is willing to perform additional computation at HSS/LMS private key can be very small when the signer is willing to
signing time; alternatively, the private key can consume additional perform additional computation at signing time; alternatively, the
memory and provide a faster signing time. The HSS/LMS signatures private key can consume additional memory and provide a faster
[HASHSIG] are currently defined to use exclusively SHA-256 [SHS]. signing time. The HSS/LMS signatures [HASHSIG] are currently defined
to use exclusively SHA-256 [SHS].
1.1. ASN.1 1.1. ASN.1
CMS values are generated using ASN.1 [ASN1-B], using the Basic CMS values are generated using ASN.1 [ASN1-B], using the Basic
Encoding Rules (BER) and the Distinguished Encoding Rules (DER) Encoding Rules (BER) and the Distinguished Encoding Rules (DER)
[ASN1-E]. [ASN1-E].
1.2. Terminology 1.2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in "OPTIONAL" in this document are to be interpreted as described in
BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here. capitals, as shown here.
1.3. Motivation 1.3. Motivation
There have been recent advances in cryptanalysis and advances in the Recent advances in cryptanalysis [BH2013] and progress in the
development of quantum computers. Each of these advances pose a
threat to widely deployed digital signature algorithms.
Recent advances in cryptoanalysis [BH2013] and progress in the
development of quantum computers [NAS2019] pose a threat to widely development of quantum computers [NAS2019] pose a threat to widely
deployed digital signature algorithms. As a result, there is a need deployed digital signature algorithms. As a result, there is a need
to prepare for a day that cryptosystems such as RSA and DSA that to prepare for a day that cryptosystems such as RSA and DSA that
depend on discrete logarithm and factoring cannot be depended upon. depend on discrete logarithm and factoring cannot be depended upon.
If large-scale quantum computers are ever built, these computers will If large-scale quantum computers are ever built, these computers will
be able to break many of the public-key cryptosystems currently in be able to break many of the public-key cryptosystems currently in
use. A post-quantum cryptosystem [PQC] is a system that is secure use. A post-quantum cryptosystem [PQC] is a system that is secure
against quantum computers that have more than a trivial number of against quantum computers that have more than a trivial number of
quantum bits (qu-bits). It is open to conjecture when it will be quantum bits (qubits). It is open to conjecture when it will be
feasible to build such computers; however, RSA, DSA, ECDSA, and EdDSA feasible to build such computers; however, RSA, DSA, ECDSA, and EdDSA
are all vulnerable if large-scale quantum computers come to pass. are all vulnerable if large-scale quantum computers come to pass.
The HSS/LMS signature algorithm does not depend on the difficulty of Since the HSS/LMS signature algorithm does not depend on the
discrete logarithm or factoring, as a result these algorithms are difficulty of discrete logarithm or factoring, the HSS/LMS signature
considered to be post-quantum secure. One use of post-quantum secure algorithm is considered to be post-quantum secure. One use of post-
signatures is the protection of software updates, perhaps using the quantum secure signatures is the protection of software updates,
format described in [FWPROT], to enable deployment of software that perhaps using the format described in [FWPROT], to enable deployment
implements new cryptosystems. of software that implements new cryptosystems.
2. HSS/LMS Hash-based Signature Algorithm Overview 2. HSS/LMS Hash-based Signature Algorithm Overview
Merkle Tree Signatures (MTS) are a method for signing a large but Merkle Tree Signatures (MTS) are a method for signing a large but
fixed number of messages. An MTS system depends on a one-time fixed number of messages. An MTS system depends on a one-time
signature method and a collision-resistant hash function. signature method and a collision-resistant hash function.
This specification makes use of the hash-based algorithm specified in This specification makes use of the hash-based algorithm specified in
[HASHSIG], which is the Leighton and Micali adaptation [LM] of the [HASHSIG], which is the Leighton and Micali adaptation [LM] of the
original Lamport-Diffie-Winternitz-Merkle one-time signature system original Lamport-Diffie-Winternitz-Merkle one-time signature system
[M1979][M1987][M1989a][M1989b]. [M1979][M1987][M1989a][M1989b].
As implied by the name, the hash-based signature algorithm depends on As implied by the name, the hash-based signature algorithm depends on
a collision-resistant hash function. The hash-based signature a collision-resistant hash function. The hash-based signature
algorithm specified in [HASHSIG] currently uses only the SHA-256 one- algorithm specified in [HASHSIG] uses only the SHA-256 one-way hash
way hash function [SHS], but it also establishes an IANA registry function [SHS], but it establishes an IANA registry [IANA-LMS] to
[IANA-LMS] to permit the registration of additional one-way hash permit the registration of additional one-way hash functions in the
functions in the future. future.
2.1. Hierarchical Signature System (HSS) 2.1. Hierarchical Signature System (HSS)
The MTS system specified in [HASHSIG] uses a hierarchy of trees. The The MTS system specified in [HASHSIG] uses a hierarchy of trees. The
Hierarchical N-time Signature System (HSS) allows subordinate trees Hierarchical N-time Signature System (HSS) allows subordinate trees
to be generated when needed by the signer. Otherwise, generation of to be generated when needed by the signer. Otherwise, generation of
the entire tree might take weeks or longer. the entire tree might take weeks or longer.
An HSS signature as specified in [HASHSIG] carries the number of An HSS signature as specified in [HASHSIG] carries the number of
signed public keys (Nspk), followed by that number of signed public signed public keys (Nspk), followed by that number of signed public
skipping to change at page 5, line 36 skipping to change at page 5, line 36
the public key itself. Note that Nspk is the number of levels in the the public key itself. Note that Nspk is the number of levels in the
hierarchy of trees minus 1. hierarchy of trees minus 1.
2.2. Leighton-Micali Signature (LMS) 2.2. Leighton-Micali Signature (LMS)
Each tree in the system specified in [HASHSIG] uses the Leighton- Each tree in the system specified in [HASHSIG] uses the Leighton-
Micali Signature (LMS) system. LMS systems have two parameters. The Micali Signature (LMS) system. LMS systems have two parameters. The
first parameter is the height of the tree, h, which is the number of first parameter is the height of the tree, h, which is the number of
levels in the tree minus one. The [HASHSIG] specification supports levels in the tree minus one. The [HASHSIG] specification supports
five values for this parameter: h=5; h=10; h=15; h=20; and h=25. five values for this parameter: h=5; h=10; h=15; h=20; and h=25.
Note that there are 2^h leaves in the tree. The second parameter is Note that there are 2^h leaves in the tree. The second parameter, m,
the number of bytes output by the hash function, m, which is the is the number of bytes output by the hash function, and it is the
amount of data associated with each node in the tree. The [HASHSIG] amount of data associated with each node in the tree. The [HASHSIG]
specification supports only the SHA-256 hash function [SHS], with specification supports only the SHA-256 hash function [SHS], with
m=32. As a result, the [HASHSIG] specification supports five tree m=32. As a result, the [HASHSIG] specification supports five tree
sizes; they are identified as: sizes; they are identified as:
LMS_SHA256_M32_H5; LMS_SHA256_M32_H5;
LMS_SHA256_M32_H10; LMS_SHA256_M32_H10;
LMS_SHA256_M32_H15; LMS_SHA256_M32_H15;
LMS_SHA256_M32_H20; and LMS_SHA256_M32_H20; and
LMS_SHA256_M32_H25. LMS_SHA256_M32_H25.
skipping to change at page 7, line 43 skipping to change at page 7, line 43
The algorithm identifier for an HSS/LMS hash-based signatures is: The algorithm identifier for an HSS/LMS hash-based signatures is:
id-alg-hss-lms-hashsig OBJECT IDENTIFIER ::= { iso(1) id-alg-hss-lms-hashsig OBJECT IDENTIFIER ::= { iso(1)
member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9)
smime(16) alg(3) 17 } smime(16) alg(3) 17 }
When this object identifier is used for an HSS/LMS signature, the When this object identifier is used for an HSS/LMS signature, the
AlgorithmIdentifier parameters field MUST be absent (that is, the AlgorithmIdentifier parameters field MUST be absent (that is, the
parameters are not present; the parameters are not set to NULL). parameters are not present; the parameters are not set to NULL).
The signature value is a large OCTET STRING. The signature format is The signature value is a large OCTET STRING as described in Section 2
designed for easy parsing. Each format includes a counter and type of this document. The signature format is designed for easy parsing.
codes that indirectly providing all of the information that is needed The HSS, LMS, and LMOTS component of the signature value each format
to parse the value during signature validation. include a counter and a type code that indirectly provide all of the
information that is needed to parse the value during signature
validation.
The signature value identifies the hash function used in the HSS/LMS The signature value identifies the hash function used in the HSS/LMS
tree. In [HASHSIG] only the SHA-256 hash function [SHS] is tree. In [HASHSIG] uses only the SHA-256 hash function [SHS], but it
supported, but it also establishes an IANA registry [IANA-LMS] to establishes an IANA registry [IANA-LMS] to permit the registration of
permit the registration of additional hash functions in the future. additional hash functions in the future.
4. HSS/LMS Public Key Identifier 4. HSS/LMS Public Key Identifier
The AlgorithmIdentifier for an HSS/LMS public key uses the id-alg- The AlgorithmIdentifier for an HSS/LMS public key uses the id-alg-
hss-lms-hashsig object identifier, and the parameters field MUST be hss-lms-hashsig object identifier, and the parameters field MUST be
absent. absent.
When this AlgorithmIdentifier appears in the SubjectPublicKeyInfo When this AlgorithmIdentifier appears in the SubjectPublicKeyInfo
field of an X.509 certificate [RFC5280], the certificate key usage field of an X.509 certificate [RFC5280], the certificate key usage
extension MAY contain digitalSignature, nonRepudiation, keyCertSign, extension MAY contain digitalSignature, nonRepudiation, keyCertSign,
skipping to change at page 8, line 34 skipping to change at page 8, line 35
Note that the id-alg-hss-lms-hashsig algorithm identifier is also Note that the id-alg-hss-lms-hashsig algorithm identifier is also
referred to as id-alg-mts-hashsig. This synonym is based on the referred to as id-alg-mts-hashsig. This synonym is based on the
terminology used in an early draft of the document that became terminology used in an early draft of the document that became
[HASHSIG]. [HASHSIG].
The public key value is an OCTET STRING. Like the signature format, The public key value is an OCTET STRING. Like the signature format,
it is designed for easy parsing. The value is the number of levels it is designed for easy parsing. The value is the number of levels
in the public key, L, followed by the LMS public key. in the public key, L, followed by the LMS public key.
The HSS/LMS public key value can be summarized as: The HSS/LMS public key value can be described as:
u32str(L) || lms_public_key u32str(L) || lms_public_key
Note that the public key for the top-most LMS tree is the public key Note that the public key for the top-most LMS tree is the public key
of the HSS system. When L=1, the HSS system is a single tree. of the HSS system. When L=1, the HSS system is a single tree.
5. Signed-data Conventions 5. Signed-data Conventions
As specified in [CMS], the digital signature is produced from the As specified in [CMS], the digital signature is produced from the
message digest and the signer's private key. The signature is message digest and the signer's private key. The signature is
computed over different values depending on whether signed attributes computed over different values depending on whether signed attributes
are absent or present. are absent or present.
When signed attributes are absent, the HSS/LMS signature is computed When signed attributes are absent, the HSS/LMS signature is computed
over the content. When signed attributes are present, a hash is over the content. When signed attributes are present, a hash is
computed over the content using the same hash function that is used computed over the content using the same hash function that is used
in the HSS/LMS tree, and then a message-digest attribute is in the HSS/LMS tree, and then a message-digest attribute is
constructed to contain the resulting hash value, and then the result constructed with the hash of the content, and then the HSS/LMS
of DER encoding the set of signed attributes (which MUST include a signature is computed over the DER-encoded set of signed attributes
content-type attribute and a message-digest attribute, and then the (which MUST include a content-type attribute and a message-digest
HSS/LMS signature is computed over the DER-encoded output. In attribute). In summary:
summary:
IF (signed attributes are absent) IF (signed attributes are absent)
THEN HSS_LMS_Sign(content) THEN HSS_LMS_Sign(content)
ELSE message-digest attribute = Hash(content); ELSE message-digest attribute = Hash(content);
HSS_LMS_Sign(DER(SignedAttributes)) HSS_LMS_Sign(DER(SignedAttributes))
When using [HASHSIG], the fields in the SignerInfo are used as When using [HASHSIG], the fields in the SignerInfo are used as
follows: follows:
digestAlgorithm MUST contain the one-way hash function used to in digestAlgorithm MUST contain the one-way hash function used in the
the HSS/LMS tree. In [HASHSIG], SHA-256 is the only supported HSS/LMS tree. In [HASHSIG], SHA-256 is the only supported hash
hash function, but other hash functions might be registered in function, but other hash functions might be registered in the
the future. For convenience, the AlgorithmIdentifier for future. For convenience, the AlgorithmIdentifier for SHA-256
SHA-256 from [PKIXASN1] is repeated here: from [PKIXASN1] is repeated here:
mda-sha256 DIGEST-ALGORITHM ::= { mda-sha256 DIGEST-ALGORITHM ::= {
IDENTIFIER id-sha256 IDENTIFIER id-sha256
PARAMS TYPE NULL ARE preferredAbsent } PARAMS TYPE NULL ARE preferredAbsent }
id-sha256 OBJECT IDENTIFIER ::= { joint-iso-itu-t(2) id-sha256 OBJECT IDENTIFIER ::= { joint-iso-itu-t(2)
country(16) us(840) organization(1) gov(101) csor(3) country(16) us(840) organization(1) gov(101) csor(3)
nistAlgorithms(4) hashalgs(2) 1 } nistAlgorithms(4) hashalgs(2) 1 }
signatureAlgorithm MUST contain id-alg-hss-lms-hashsig, and the signatureAlgorithm MUST contain id-alg-hss-lms-hashsig, and the
skipping to change at page 9, line 45 skipping to change at page 9, line 46
the signing operation as specified in [HASHSIG]. the signing operation as specified in [HASHSIG].
6. Security Considerations 6. Security Considerations
Implementations MUST protect the private keys. Compromise of the Implementations MUST protect the private keys. Compromise of the
private keys may result in the ability to forge signatures. Along private keys may result in the ability to forge signatures. Along
with the private key, the implementation MUST keep track of which with the private key, the implementation MUST keep track of which
leaf nodes in the tree have been used. Loss of integrity of this 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 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- 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 volatile media or stored in a virtual machine environment, failed
be taken to preserve confidentiality and integrity. writes, virtual machine snapshotting or cloning, and other
operational concerns must be considered to ensure confidentiality and
integrity.
When generating an LMS key pair, an implementation MUST generate each When generating an LMS key pair, an implementation MUST generate each
key pair independently of all other key pairs in the HSS tree. key pair independently of all other key pairs in the HSS tree.
An implementation MUST ensure that a LM-OTS private key is used to An implementation MUST ensure that a LM-OTS private key is used to
generate a signature only one time, and ensure that it cannot be used generate a signature only one time, and ensure that it cannot be used
for any other purpose. for any other purpose.
The generation of private keys relies on random numbers. The use of The generation of private keys relies on random numbers. The use of
inadequate pseudo-random number generators (PRNGs) to generate these inadequate pseudo-random number generators (PRNGs) to generate these
values can result in little or no security. An attacker may find it values can result in little or no security. An attacker may find it
much easier to reproduce the PRNG environment that produced the keys, much easier to reproduce the PRNG environment that produced the keys,
searching the resulting small set of possibilities, rather than brute searching the resulting small set of possibilities, rather than brute
force searching the whole key space. The generation of quality force searching the whole key space. The generation of quality
random numbers is difficult, and [RFC4086] offers important guidance random numbers is difficult, and [RFC4086] offers important guidance
in this area. in this area.
The generation of hash-based signatures also depends on random The generation of hash-based signatures also depends on random
numbers. While the consequences of an inadequate pseudo-random numbers. While the consequences of an inadequate pseudo-random
number generator (PRNGs) to generate these values is much less severe number generator (PRNG) to generate these values is much less severe
than the generation of private keys, the guidance in [RFC4086] than in the generation of private keys, the guidance in [RFC4086]
remains important. remains important.
When computing signatures, the same hash function SHOULD be used to When computing signatures, the same hash function SHOULD be used to
compute the message digest of the content and the signed attributes, compute the message digest of the content and the signed attributes,
if they are present. if they are present.
7. IANA Considerations 7. IANA Considerations
SMI Security for S/MIME Module Identifier (1.2.840.113549.1.9.16.0) SMI Security for S/MIME Module Identifier (1.2.840.113549.1.9.16.0)
registry, change the reference for value 64 to point to this registry, change the reference for value 64 to point to this
skipping to change at page 14, line 34 skipping to change at page 14, line 34
SMimeCaps SMIME-CAPS ::= SMimeCaps SMIME-CAPS ::=
{ sa-HSS-LMS-HashSig.&smimeCaps, ... } { sa-HSS-LMS-HashSig.&smimeCaps, ... }
END END
<CODE ENDS> <CODE ENDS>
Acknowledgements Acknowledgements
Many thanks to Scott Fluhrer, Jonathan Hammell, Panos Kampanakis, Many thanks to Scott Fluhrer, Jonathan Hammell, Ben Kaduk, Panos
John Mattsson, Jim Schaad, Sean Turner, Daniel Van Geest, Roman Kampanakis, Barry Leiba, John Mattsson, Jim Schaad, Sean Turner,
Danyliw, Dale Worley, and Joe Clarke for their careful review and Daniel Van Geest, Roman Danyliw, Dale Worley, and Joe Clarke for
comments. their careful review and comments.
Author's Address Author's Address
Russ Housley Russ Housley
Vigil Security, LLC Vigil Security, LLC
516 Dranesville Road 516 Dranesville Road
Herndon, VA 20170 Herndon, VA 20170
USA USA
EMail: housley@vigilsec.com EMail: housley@vigilsec.com
 End of changes. 16 change blocks. 
54 lines changed or deleted 54 lines changed or added

This html diff was produced by rfcdiff 1.47. The latest version is available from http://tools.ietf.org/tools/rfcdiff/