 1/draftietflampscmshashsig03.txt 20190212 13:13:10.707210626 0800
+++ 2/draftietflampscmshashsig04.txt 20190212 13:13:10.747211605 0800
@@ 1,26 +1,27 @@
INTERNETDRAFT R. Housley
Internet Engineering Task Force (IETF) Vigil Security
Intended Status: Proposed Standard
Expires: 20 June 2019 20 December 2018
+Expires: 12 August 2019 12 February 2019
Use of the HSS/LMS Hashbased Signature Algorithm
in the Cryptographic Message Syntax (CMS)

+
Abstract
This document specifies the conventions for using the the HSS/LMS
hashbased signature algorithm with the Cryptographic Message Syntax
 (CMS). The HSS/LMS algorithm is one form of hashbased digital
 signature; it is described in [HASHSIG].
+ (CMS). In addition, the algorithm identifier and public key syntax
+ are provided. The HSS/LMS algorithm is one form of hashbased
+ digital signature; it is described in [HASHSIG].
Status of this Memo
This InternetDraft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
InternetDrafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet
Drafts.
@@ 78,38 +79,73 @@
This document specifies the conventions for using the HSS/LMS hash
based signature algorithm with the Cryptographic Message Syntax (CMS)
[CMS] signeddata content type. The LeightonMicali Signature (LMS)
system provides a onetime digital signature that is a variant of
Merkle Tree Signatures (MTS). The Hierarchical Signature System
(HSS) 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
hashbased digital signature, and it is described in [HASHSIG]. The
HSS/LMS signature algorithm can only be used for a fixed number of
 signing operations. The HSS/LMS signature algorithm uses small
+ signing operations. The number of signing operations depends upon
+ the size of the tree. The HSS/LMS signature algorithm uses small
private and public keys, and it has low computational cost; however,
the signatures are quite large.
1.1. ASN.1
CMS values are generated using ASN.1 [ASN1B], using the Basic
Encoding Rules (BER) and the Distinguished Encoding Rules (DER)
[ASN1E].
1.2. 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.
+1.3. Algorithm Considerations
+
+ At Black Hat USA 2013, some researchers gave a presentation on the
+ current state of public key cryptography. They said: "Current
+ cryptosystems depend on discrete logarithm and factoring which has
+ seen some major new developments in the past 6 months" [BH2013].
+ They encouraged preparation for a day when RSA and DSA cannot be
+ depended upon.
+
+ A postquantum cryptosystem is a system that is secure against
+ quantum computers that have more than a trivial number of quantum
+ bits. It is open to conjecture when it will be feasible to build
+ such a machine. RSA, DSA, and ECDSA are not postquantum secure.
+
+ The LMOTS onetime signature, LMS, and HSS do not depend on discrete
+ logarithm or factoring, as a result these algorithms are considered
+ to be postquantum secure.
+
+ Hashbased signatures [HASHSIG] are currently defined to use
+ exclusively SHA256. An IANA registry is defined so that other hash
+ functions could be used in the future. LMOTS signature generation
+ prepends a random string as well as other metadata before computing
+ the hash value. The inclusion of the random value reduces the
+ chances of an attacker being able to find collisions, even if the
+ attacker has a largescale quantum computer.
+
+ Today, RSA is often used to digitally sign software updates. This
+ means that the distribution of software updates could be compromised
+ if a significant advance is made in factoring or a quantum computer
+ is invented. The use of HSS/LMS hashbased signatures to protect
+ software update distribution, perhaps using the format described in
+ [FWPROT], will allow the deployment of software that implements new
+ cryptosystems.
+
2. HSS/LMS Hashbased Signature Algorithm Overview
Merkle Tree Signatures (MTS) are a method for signing a large but
fixed number of messages. An MTS system depends on a onetime
signature method and a collisionresistant hash function.
This specification makes use of the hashbased algorithm specified in
[HASHSIG], which is the Leighton and Micali adaptation [LM] of the
original LamportDiffieWinternitzMerkle onetime signature system
[M1979][M1987][M1989a][M1989b].
@@ 123,42 +159,44 @@
2.1. Hierarchical Signature System (HSS)
The MTS system specified in [HASHSIG] uses a hierarchy of trees. The
Hierarchical Ntime Signature System (HSS) allows subordinate trees
to be generated when needed by the signer. Otherwise, generation of
the entire tree might take weeks or longer.
An HSS signature as specified in [HASHSIG] carries the number of
signed public keys (Nspk), followed by that number of signed public
 keys, followed by the LMS signature as described in Section 2.2.
 Each signed public key is represented by the hash value at the root
 of the tree, and it also contains information about the tree
 structure. The signature over the public key is an LMS signature as
 described in Section 2.2.
+ keys, followed by the LMS signature as described in Section 2.2. The
+ public key for the topmost LMS tree is the public key of the HSS
+ system. The LMS private key in the parent tree signs the LMS public
+ key in the child tree, and the LMS private key in the bottommost
+ tree signs the actual message. The signature over the public key and
+ the signature over the actual message are LMS signatures as described
+ in Section 2.2.
 The elements of the HSS signature value for a standalone tree can be
 summarized as:
+ The elements of the HSS signature value for a standalone tree (a top
+ tree with no children) can be summarized as:
u32str(0) 
lms_signature /* signature of message */
The elements of the HSS signature value for a tree with Nspk signed
public keys can be summarized as:
u32str(Nspk) 
signed_public_key[0] 
signed_public_key[1] 
...
signed_public_key[Nspk2] 
signed_public_key[Nspk1] 
 lms_signature_on_message
+ lms_signature /* signature of message */
where, as defined in Section 3.3 of [HASHSIG], a signed_public_key is
the lms_signature over the public key followed by the public key
itself. Note that Nspk is the number of levels in the hierarchy of
trees minus 1.
2.2. LeightonMicali Signature (LMS)
Each tree in the system specified in [HASHSIG] uses the Leighton
Micali Signature (LMS) system. LMS systems have two parameters. The
@@ 175,22 +213,32 @@
LMS_SHA256_M32_H5;
LMS_SHA256_M32_H10;
LMS_SHA256_M32_H15;
LMS_SHA256_M32_H20; and
LMS_SHA256_M32_H25.
The [HASHSIG] specification establishes an IANA registry to permit
the registration of additional tree sizes in the future.
+ The LMS public key is the string consists of four elements: the
+ lms_algorithm_type from the list above, the otstype to identify the
+ LMOTS type as discussed in Section 2.3, the private key identifier
+ (I) as described in Section 5.3 of [HASHSIG], and the mbyte string
+ associated with the root node of the tree.
+
+ The LMS public key can be summarized as:
+
+ u32str(lms_algorithm_type)  u32str(otstype)  I  T[1]
+
An LMS signature consists of four elements: the number of the leaf
 associated with the LMOTS signature, an LMOTS signature as
+ (q) associated with the LMOTS signature, an LMOTS signature as
described in Section 2.3, a typecode indicating the particular LMS
algorithm, and an array of values that is associated with the path
through the tree from the leaf associated with the LMOTS signature
to the root. The array of values contains the siblings of the nodes
on the path from the leaf to the root but does not contain the nodes
on the path itself. The array for a tree with height h will have h
values. The first value is the sibling of the leaf, the next value
is the sibling of the parent of the leaf, and so on up the path to
the root.
@@ 231,21 +279,24 @@
LMOTS_SHA256_N32_W1;
LMOTS_SHA256_N32_W2;
LMOTS_SHA256_N32_W4; and
LMOTS_SHA256_N32_W8.
The [HASHSIG] specification establishes an IANA registry to permit
the registration of additional variants in the future.
Signing involves the generation of C, an nbyte random value.
 The LMOTS signature value can be summarized as:
+ The LMOTS signature value can be summarized as the identifier of the
+ LMOTS variant, the random value, and a sequence of hash values that
+ correspond to the elements of the public key as described in Section
+ 4.5 of [HASHSIG]:
u32str(otstype)  C  y[0]  ...  y[p1]
3. Algorithm Identifiers and Parameters
The algorithm identifier for an HSS/LMS hashbased signature when
SHA256 [SHS] is used to hash the content is the
idalghsslmshashsigwithsha256 object identifier:
idalghsslmshashsigwithsha256 OBJECT IDENTIFIER ::= { iso(1)
@@ 272,21 +323,21 @@
AlgorithmIdentifier parameters field MUST be absent (that is, the
parameters are not present; the parameters are not set to NULL).
The signature values is a large OCTET STRING. The signature format
is designed for easy parsing. Each format includes a counter and
type codes that indirectly providing all of the information that is
needed to parse the value during signature validation.
4. HSS/LMS Public Key Identifier
 The AlgorithmIdentifier for an HHS/LMS public key uses the idalg
+ The AlgorithmIdentifier for an HSS/LMS public key uses the idalg
hsslmshashsig object identifier, and the parameters field MUST be
absent.
The SubjectPublicKeyInfo field of an X.509 certificate [RFC5280] is
one place where this algorithm identifier appears. In this
situation, the certificate key usage extension MAY contain
digitalSignature, nonRepudiation, keyCertSign, and cRLSign; however,
it MUST NOT contain other values.
pkHSSLMSHashSig PUBLICKEY ::= {
@@ 302,22 +353,24 @@
referred to as idalgmtshashsig. This synonym is based on the
terminology used in an early draft of the document that became
[HASHSIG].
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
in the public key, L, followed by the LMS public key.
The HSS/LMS public key value can be summarized as:
 u32str(L) 
 lms_public_key
+ u32str(L)  lms_public_key
+
+ Note that the public key for the topmost LMS tree is the public key
+ of the HSS system, and when L=1 it is a standalone tree.
5. Signeddata Conventions
As specified in [CMS], the digital signature is produced from the
message digest and the signer's private key. If signed attributes
are absent, then the message digest is the hash of the content. If
signed attributes are present, then the hash of the content is placed
in the messagedigest attribute, the set of signed attributes is DER
encoded, and the message digest is the hash of the encoded
attributes. In summary:
@@ 331,140 +384,106 @@
When using [HASHSIG], the fields in the SignerInfo are used as
follows:
digestAlgorithms SHOULD contain the oneway hash function used to
compute the message digest on the eContent value. In
[HASHSIG], SHA256 is used throughout the hash tree, and the
hash computation includes a random string. This random data
makes it harder for an attacker to find collisions. The signer
SHOULD use SHA256 or a stronger hash function to compute the
 message digest on the content. For
 this purpose, Algorithm identifiers for SHA256, SHA384, and
 SHA512 are provided in this document.
+ message digest on the content. For this purpose, Algorithm
+ identifiers for SHA256, SHA384, and SHA512 are provided in
+ this document.
Further, the same oneway hash function SHOULD be used to
compute the message digest on both the eContent and the
signedAttributes value if signedAttributes are present.
signatureAlgorithm MUST contain idalghsslmshashsigwith
sha256, idalghsslmshashsigwithsha384, or idalghsslms
hashsigwithsha512. The algorithm parameters field MUST be
absent.
signature contains the single HSS signature value resulting from
the signing operation as specified in [HASHSIG].
6. Security Considerations
6.1. Implementation 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
 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
tracking data can cause an onetime key to be used more than once.
As a result, when a private key and the tracking data are stored on
nonvolatile media or stored in a virtual machine environment, care
must be taken to preserve confidentiality and integrity.
 When a LMS key pair is generating a LMS key pair, an implementation
 must must generate the key pair and the corresponding identifier
 independently of all other key pairs in the HSS tree.
+ When generating a LMS key pair, an implementation MUST generate each
+ key pair independently of all other key pairs in the HSS tree.
 An implementation must ensure that a LMOTS private key is used to
+ An implementation MUST ensure that a LMOTS private key is used to
generate a signature only one time, and ensure that it cannot be used
for any other purpose.
The generation of private keys relies on random numbers. The use of
inadequate pseudorandom 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. RFC 4086 [RANDOM] offers important
 guidance in this area.
+ random numbers is difficult, and [RFC4086] offers important guidance
+ in this area.
The generation of hashbased signatures also depends on random
numbers. While the consequences of an inadequate pseudorandom
number generator (PRNGs) to generate these values is much less severe
than the generation of private keys, the guidance in [RFC4086]
remains important.
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.
6.2. Algorithm Security Considerations

 At Black Hat USA 2013, some researchers gave a presentation on the
 current sate of public key cryptography. They said: "Current
 cryptosystems depend on discrete logarithm and factoring which has
 seen some major new developments in the past 6 months" [BH2013].
 They encouraged preparation for a day when RSA and DSA cannot be
 depended upon.

 A postquantum cryptosystem is a system that is secure against
 quantum computers that have more than a trivial number of quantum
 bits. It is open to conjecture when it will be feasible to build
 such a machine. RSA, DSA, and ECDSA are not postquantum secure.

 The LMOTP onetime signature, LMS, and HSS do not depend on discrete
 logarithm or factoring, as a result these algorithms are considered
 to be postquantum secure.

 Hashbased signatures [HASHSIG] are currently defined to use
 exclusively SHA256. An IANA registry is defined to that other hash
 functions could be used in the future. LMOTS signature generation
 prepends a random string as well as other metadata before computing
 the hash value. The inclusion of the random value reduces the
 chances of an attacker being able to find collisions, even if the
 attacker has a largescale quantum computer.

 Today, RSA is often used to digitally sign software updates. This
 means that the distribution of software updates could be compromised
 if a significant advance is made in factoring or a quantum computer
 is invented. The use of HSS/LMS hashbased signatures to protect
 software update distribution, perhaps using the format described in
 [FWPROT], will allow the deployment of software that implements new
 cryptosystems.

7. IANA Considerations
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
document.
In the SMI Security for S/MIME Algorithms (1.2.840.113549.1.9.16.3)
registry, change the description for value 17 to
"idalghsslmshashsig" and change the reference to point to this
 document. Also, add the following note to the registry:
+ document.
+
+ Also, add the following note to the registry:
Value 17, "idalghsslmshashsig", is also referred to as
"idalgmtshashsig".
In the SMI Security for S/MIME Algorithms (1.2.840.113549.1.9.16.3)
registry, assign a new value for idalghsslmshashsigwithsha256
with a reference to this document.
In the SMI Security for S/MIME Algorithms (1.2.840.113549.1.9.16.3)
registry, assign a new value for idalghsslmshashsigwithsha384
with a reference to this document.
In the SMI Security for S/MIME Algorithms (1.2.840.113549.1.9.16.3)
registry, assign a new value for idalghsslmshashsigwithsha512
with a reference to this document.
8. Acknowledgements
 Many thanks to Panos Kampanakis, Jim Schaad, Sean Turner, and Daniel
 Van Geest for their careful review and comments.
+ Many thanks to Scott Fluhrer, Jonathan Hammell, Panos Kampanakis, Jim
+ Schaad, Sean Turner, and Daniel Van Geest for their careful review
+ and comments.
9. References
9.1. Normative References
[ASN1B] ITUT, "Information technology  Abstract Syntax Notation
One (ASN.1): Specification of basic notation", ITUT
Recommendation X.680, 2015.
[ASN1E] ITUT, "Information technology  ASN.1 encoding rules:
@@ 473,21 +492,21 @@
(DER)", ITUT Recommendation X.690, 2015.
[CMS] Housley, R., "Cryptographic Message Syntax (CMS)", STD 70,
RFC 5652, DOI 10.17487/RFC5652, September 2009,
.
[HASHSIG] McGrew, D., M. Curcio, and S. Fluhrer, "HashBased
Signatures", Work in progress.
 [RFC2219] Bradner, S., "Key words for use in RFCs to Indicate
+ [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, DOI
10.17487/RFC2119, March 1997, .
[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, May 2008,
.
@@ 544,21 +563,21 @@
[PKIXASN1] Hoffman, P. and J. Schaad, "New ASN.1 Modules for the
Public Key Infrastructure Using X.509 (PKIX)", RFC 5912,
DOI 10.17487/RFC5912, June 2010, .
[PQC] Bernstein, D., "Introduction to postquantum
cryptography", 2009.
 [RANDOM] Eastlake 3rd, D., Schiller, J., and S. Crocker,
+ [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker,
"Randomness Requirements for Security", BCP 106, RFC 4086,
DOI 10.17487/RFC4086, June 2005, .
Appendix: ASN.1 Module
MTSHashSig2013
{ iso(1) memberbody(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9)
idsmime(16) idmod(0) idmodmtshashsig2013(64) }
@@ 579,20 +598,22 @@
idmodpkix1rsapkalgs02(54) } ;

 Object Identifiers

idalghsslmshashsig OBJECT IDENTIFIER ::= { iso(1)
memberbody(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9)
smime(16) alg(3) 17 }
+ idalgmtshashsig OBJECT IDENTIFIER ::= idalghsslmshashsig
+
idalghsslmshashsigwithsha256 OBJECT IDENTIFIER ::= { iso(1)
memberbody(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9)
smime(16) alg(3) TBD }
idalghsslmshashsigwithsha384 OBJECT IDENTIFIER ::= { iso(1)
memberbody(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9)
smime(16) alg(3) TBD }
idalghsslmshashsigwithsha512 OBJECT IDENTIFIER ::= { iso(1)
memberbody(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9)
@@ 649,15 +670,15 @@
{ saHSSLMSHashSigwithSHA256.&smimeCaps 
saHSSLMSHashSigwithSHA384.&smimeCaps 
saHSSLMSHashSigwithSHA512.&smimeCaps, ... }
END
Author's Address
Russ Housley
Vigil Security, LLC
 918 Spring Knoll Drive
+ 516 Dranesville Road
Herndon, VA 20170
USA
EMail: housley@vigilsec.com