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/ |