Protocol++® (Protocolpp®)  v5.7.0
jlmsa Class Reference

#include "include/jlmsa.h"

Detailed Description

Security Association for LMS Signature System (LMS)

Leighton-Micali Signatures

The Leighton-Micali Signature (LMS) method can sign a potentially large but fixed number of messages An LMS system uses two cryptographic components: a one-time signature method and a hash function. Each LMS public/private key pair is associated with a perfect binary tree, each node of which contains an m-byte value, where m is the output length of the hash function. Each leaf of the tree contains the value of the public key of an LM-OTS public/private key pair. The value contained by the root of the tree is the LMS key pair. The value contained by the root fo teh tree is the LMS key pair. Each interior node is computed by applying the hash function to the concatenation of the values of its children nodes

Each node of the tree is associated with a node number, an unsigned integer that is denoted as node_num in the algorithms below, which is computed as follows. The root node has node number 1; for each node with node number $ N lt {2}^{h} $ (where h is the height of the tree), its left child has node number $ 2*N $, while its right child has node number

$ {2}^{h}, ({2}^{h} + 1), ({2}^{h} + 2), ..., ({2}^{h})+({2}^{h})-1 $

In general, the j-th node at level i hash node $ {2}^{i} + j $. The node number can conveniently be computed when it is needed in the LMS algorithms, as described in those algorithms

LMS Parameters

An LMS system has the following parameters:

  • h - the height of the tree
  • m - the number of bytes associated with each node
  • H - a second-preimage-resistant cryptographic hash function that accepts byte strings of any length and returns an m-byte string
LMS Parameters
NameHmhtype value
LMOTS_SHA256_M32_H5SHA2563250x00000005
LMOTS_SHA256_M32_H10SHA25632100x00000006
LMOTS_SHA256_M32_H15SHA25632150x00000007
LMOTS_SHA256_M32_H20SHA25632200x00000008
LMOTS_SHA256_M32_H25SHA25632250x00000009
LMOTS_SHA256_M24_H5SHA2562450x0000000A
LMOTS_SHA256_M24_H10SHA25624100x0000000B
LMOTS_SHA256_M24_H15SHA25624150x0000000C
LMOTS_SHA256_M24_H20SHA25624200x0000000D
LMOTS_SHA256_M24_H25SHA25624250x0000000E
LMOTS_SHAKE_M32_H5SHAKE2563250x0000000F
LMOTS_SHAKE_M32_H10SHAKE25632100x00000010
LMOTS_SHAKE_M32_H15SHAKE25632150x00000011
LMOTS_SHAKE_M32_H20SHAKE25632200x00000012
LMOTS_SHAKE_M32_H25SHAKE25632250x00000013
LMOTS_SHAKE_M24_H5SHAKE2562450x00000014
LMOTS_SHAKE_M24_H10SHAKE25624100x00000015
LMOTS_SHAKE_M24_H15SHAKE25624150x00000016
LMOTS_SHAKE_M24_H20SHAKE25624200x00000017
LMOTS_SHAKE_M24_H25SHAKE25624250x00000018

LMS Private Key

The format of the LMS private key is an internal matter to the implementation, and this document does not attempt to define it. One possibility is that it may consist of an array OTS_PRIV[] of 2^h LM-OTS private keys and the leaf number q of the next LM-OTS private key that has not yet been used. The q-th element of OTS_PRIV[] is generated using Algorithm 0 with the identifiers I, q. The leaf number q is initialized to zero when the LMS private key is created. The format of the LMS Private Key consists of

------------------------------------------------
| LMOTSQ+1 | LMOTS_SK[0] | ... | LMOTS_SK[H-1] |
------------------------------------------------
ProtocolPP::LMOTSQ
@ LMOTSQ
LMOTS value of 'q' parameter.
Definition: jenum.h:839

LMS Public Key

An LMS public key is defined as follows, where we denote the public key final hash value (namely, the K value computed in Algorithm 1) associated with the i-th LM-OTS private key as OTS_PUB_HASH[i], with i ranging from 0 to (2^h)-1. Each instance of an LMS public/private key pair is associated with a balanced binary tree, and the nodes of that tree are indexed from 1 to 2^(h+1)-1. Each node is associated with an m-byte string. The string for the r-th node is denoted as T[r]. The format of the LMS Public Key consists of

------------------------------------------
| LMS_TYPE | LMOTS_TYPE | I | LMOTS_T[1] |
------------------------------------------

LMS Signature

An LMS signature consists of

  • the number q of the leaf associated with the LM-OTS signature, as a four-byte unsigned integer in network byte order, an LM-OTS signature
  • a typecode indicating the particular LMS algorithm
  • an array of h m-byte values that is associated with the path through the tree from the leaf associated with the LM-OTS signature to the root

The format for the LMS Signature consists of

-------------------------------------------------------------------
| LMOTSQ | LMOTS_SIGNATURE | LMS_TYPE | PATH[0] | ... | PATH[H-1] |
-------------------------------------------------------------------

To compute the LMS signature of a message with an LMS private key, the signer first computes the LM-OTS signature of the message using the leaf number of the next unused LM-OTS private key. The leaf number q in the signature is set to the leaf number of the LMS private key that was used in the signature. Before releasing the signature, the leaf number q in the LMS private key MUST be incremented to prevent the LM-OTS private key from being used again. If the LMS private key is maintained in nonvolatile memory, then the implementation MUST ensure that the incremented value has been stored before releasing the signature. The issue this tries to prevent is a scenario where

a) we generate a signature using one LM-OTS private key and release it to the application

b) before we update the nonvolatile memory, we crash, and

c) we reboot and generate a second signature using the same LM-OTS private key. With two different signatures using the same LM-OTS private key, an attacker could potentially generate a forged signature of a third message

LMS Tree

LMS Signature Verification

An LMS signature is verified by first using the LM-OTS signature verification algorithm (Algorithm 4b) to compute the LM-OTS public key from the LM-OTS signature and the message. The value of that public key is then assigned to the associated leaf of the LMS tree, and then the root of the tree is computed from the leaf value and the array path[] as described in Algorithm 6 If the root value matches the public key, then the signature is valid; otherwise, the signature verification fails

Comparison with Other Work

The eXtended Merkle Signature Scheme (XMSS) is similar to HSS in several ways. Both are stateful hash-based signature schemes, and both use a hierarchical approach, with a Merkle tree at each level of the hierarchy. XMSS signatures are slightly shorter than HSS signatures, for equivalent security and an equal number of signatures

HSS has several advantages over XMSS. HSS operations are roughly four times faster than the comparable XMSS ones, when SHA256 is used as the underlying hash. This occurs because the hash operation done as a part of the Winternitz iterations dominates performance, and XMSS performs four compression-function invocations (two for the PRF, two for the F function) where HSS only needs to perform one. Additionally, HSS is somewhat simpler (as each hash invocation is just a prefix followed by the data being hashed)

NIST SP 800-208 Additions - Leighton-Micali Signatures (LMS) Parameter Sets

This Special Publication approves the use of LMS and HSS with four different hash functions: SHA-256, SHA-256/192, SHAKE256/256, and SHAKE256/192 (see Section 2.3). The parameter sets that use SHA-256 are defined in RFC 8554 [2]. The parameter sets that use SHA-256/192, SHAKE256/256, and SHAKE256/192 are defined in this publication

When generating a key pair for an LMS instance, each LM-OTS key in the system shall use the same parameter set, and the hash function used for the LMS system shall be the same as the hash function used in the LM-OTS keys. The height of the tree (h) shall be 5, 10, 15, 20, or 25

When generating a key pair for an HSS instance, the requirements specified in the previous paragraph apply to each LMS tree in the instance. If the HSS instance has more than one level, then the hash function used for the tree at level 0 shall be used for every LMS tree at every other level. For each level, the same LMS and LM-OTS parameter sets shall be used for every LMS tree at that level. Different LMS and LM-OTS parameter sets may be used at different levels, as long as all chosen parameter sets use the same hash function

The LMS and LM-OTS parameter sets that are approved for use by this Special Publication are specified in tables in Sections 4.1 through 4.4. The parameters n, w, p, m, and h specified in the tables are defined in Sections 4.1 and 5.1

LMS and HSS Random Number Generation Requirements

The LMS key pair identifier, I, shall be generated using an approved random bit generator (see the SP 800-90 series of publications [6]), where the instantiation of the random bit generator supports at least 128 bits of security strength

The n-byte private elements of the LM-OTS private keys (x[i] in Section 4.2 of [2]) shall be generated using the pseudorandom key generation method specified in Appendix A of [2]. The same SEED value shall be used to generate every private element in a single LMS instance, and SEED shall be generated using an approved random bit generator [6], where the instantiation of the random bit generator supports at least 8n bits of security strength

If more than one LMS instance is being created (e.g., for an HSS instance), then a separate key pair identifier, I, and SEED shall be generated for each LMS instance

When generating a signature, the n-byte randomizer C (see Section 4.5 of [2]) shall be generated using an approved random bit generator [6], where the instantiation of the random bit generator supports at least 8n bits of security strength

For API Documentation:

See also
ProtocolPP::jlmsa
ProtocolPP::jlms

For Additional Documentation:

See also
jlmsa
jlms
Protocol++® (ProtocolPP®) written by : John Peter Greninger • © John Peter Greninger 2015-2024 • All Rights Reserved
All copyrights and trademarks are the property of their respective owners

The source code contained or described herein and all documents related to the source code (herein called "Material") are owned by John Peter Greninger and Sheila Rocha Greninger. Title to the Material remains with John Peter Greninger and Sheila Rocha Greninger. The Material contains trade secrets and proprietary and confidential information of John Peter Greninger and Sheila Rocha Greninger. The Material is protected by worldwide copyright and trade secret laws and treaty provisions. No part of the Material may be used, copied, reproduced, modified, published, uploaded, posted, transmitted, distributed, or disclosed in any way without prior express written consent of John Peter Greninger and Sheila Rocha Greninger (both are required)

No license under any patent, copyright, trade secret, or other intellectual property right is granted to or conferred upon you by disclosure or delivery of the Materials, either expressly, by implication, inducement, estoppel, or otherwise. Any license under such intellectual property rights must be express and approved by John Peter Greninger and Sheila Rocha Greninger in writing

Licensing information can be found at www.protocolpp.com/license with use of the binary forms permitted provided that the following conditions are met:

  • Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution
  • Any and all modifications must be returned to John Peter Greninger at GitHub.com https://github.com/jpgreninger/protocolpp for evaluation. Inclusion of modifications in the source code shall be determined solely by John Peter Greninger. Failure to provide modifications shall render this license NULL and VOID and revoke any rights to use of Protocol++®
  • Commercial use (incidental or not) requires a fee-based license obtainable at www.protocolpp.com/shop
  • Academic or research use requires prior written and notarized permission from John Peter and Sheila Rocha Greninger

Use of the source code requires purchase of the source code. Source code can be purchased at www.protocolpp.com/shop

  • US Copyrights at https://www.copyright.gov/
    • TXu002059872 (Version 1.0.0)
    • TXu002066632 (Version 1.2.7)
    • TXu002082674 (Version 1.4.0)
    • TXu002097880 (Version 2.0.0)
    • TXu002169236 (Version 3.0.1)
    • TXu002182417 (Version 4.0.0)
    • TXu002219402 (Version 5.0.0)
    • TXu002272076 (Version 5.2.1)
    • TXu002383571 (Version 5.4.3)

The name of its contributor may not be used to endorse or promote products derived from this software without specific prior written permission and licensing

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTOR "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE

The documentation for this class was generated from the following file: