#include "include/jxmss.h"
Detailed Description
The eXtended Merkel Signature Scheme (XMSS), a hash-bashed digital signature scheme that is based on existing descriptions in scientific literature. There are three types of signatures specified for Winternitz One-Time Signature Plus (WOTS+), a one-time signature scheme; XMSS, a single-tree scheme; and XMSS^MT, a multi-tree variant of XMSS. Both XMSS and XMSS^MT use WOTS+ as a main bulding block. XMSS provides cryptographic digital signatures without relying on the conjectured hardness of mathematical problems. Instead, it is proven that it only relies on the properties of cryptographic hash functions. XMSS provides strong security guarantees and is even secure when the collison resistance of the underlying hash function is broken. Its is suitable for compact implementations, is relatively simple to implement, and naturally resists side-channel attacks. Unlike most other signature systems, hash-based signatures can so far withstand known attacks using quantum computers
XMSS uses four cryptographic components: WOTS+ as OTS method, two additional cryptographic hash functions H and H_msg, and a pseudorandom function PRF. One of the main advantages of XMSS with WOTS+ is that is does not rely on the collision resistance of the used hash functions but on weaker properties. Each XMSS public/private key pair is associated with a perfect binary tree, every node of which contains an n-byte value
XMSS has the following parameters:
- h - the height (number of levels - 1) of the tree
- n - the length in bytes of the message digest as well as each node
- w - the Winternitz parameter as defined for WOTS+ (16)
There are 2^h leaves in the tree
XMSS Hash Functions
XMSS uses two additional cryptographic functions besides hash function F and pseudorandom function PRF required by WOTS+ which are
- A cryptographic function H. H accepts n-byte keys and byte strings of length 2n and returns an n-byte string
- A cryptographic hash functions H_msg. H_msg accepts 3n-byte keys and byte strings of arbitrary length and returns an n-byte string
XMSS Private Key
An XMSS private key SK contains 2^h WOTS+ private keys, the leaf index idx of the next WOTS+ private key that has not yet been used, SK_PRF (an n-byte key to generate pseudorandom values for randomized message hashing), the n-byte value root (which is the root node of the tree and SEED), and the n-byte public seed used to pseudorandomly generate bitmasks and hash function keys. The root and SEED are required for functions that do not take the public key as input
XMSS Key Generation
The XMSS public key PK consists of the root of the binary hash tree and the seed SEED, both also stored in SK. The root is computed using treeHash. For XMSS, there is only a single main tree. Hence, the used address is set to the all-zero string in the beginning. Note that we do not define any specific format or handling for the XMSS private key SK by introducing this algorithm
It is strongly RECOMMENDED to use pseudorandom key generation to reduce the private key size
The format of an XMSS public key is given below
The authentication path is an array of h n-byte strings. It contains the siblings of the nodes on the path from the used leaf to the root. It does not contain the nodes on the path itself. A verifier needs these nodes to compute a root node for the tree from the WOTS+ public key. A node Node is addressed by its position in the tree. Node(x,y) denotes the y^th node on level x with y=0 being the leftmost node on a level. The leaves are on level 0; the root is on level h. An authentication path contains exactly one node on every layer 0 <= x <= (h-1). For the i^th WOTS+ key pair, counting from zero, the j^th authentication path node is
XMSS Signature Generation
To compute the XMSS signature of a message M with an XMSS private key, the signer first computes a randomized message digest using a random value r, idx_sig, the index of the WOTS+ key pair to be used, and the root value from the public key as key. Then, a WOTS+ signature of the message digest is computed using the next unused WOTS+ private key. Next, the authentication path is computed. Finally, the private key is updated, i.e., idx is incremented. An implementation MUST NOT output the signature before the private key is updated. The data format for a signature is given below
XMSS Signature Verification
An XMSS signature is verified by first computing the message digest using randomness r, index idx_sig, the root from PK and message M. The used WOTS+ public key pk_ots is computed from the WOTS+ signature using WOTS_pkFromSig. The WOTS+ public key in turn is used to compute the corresponding leaf using an L-tree. The leaf, together with idex idx_sig and authentication root value for the tree. The verification succeeds if and only if the computed root value matches the one in the XMSS public key. In any other case, it MUST return fail
The main part of the XMSS signature verification is done by the function XMSS_rootFromSig described below. XMSS_rootFromSig takes as input an index idx_sig, a WOTS+ signature sig_ots an authentication path auth, an n-byte message M', seed SEED, and address ADRS. XMSS_rootFromSig returns an n-byte string holding the value of the root of a tree defiend by the input data
XMSS^MT: Multi-Tree XMSS
XMSS^MT builds on XMSS by using a tree of several layers of XMSS trees, a so-called hypertree. The trees on top and intermediate layers are used to sign the root nodes of the trees on the respective layer below. Trees on the lowest layer are used to sign the acutal messages. All XMSS trees in XMSS^MT have equal height
XMSS^MT Parameters
In addition to XMSS parameters, an XMSS^MT system requires the number of tree layers d, specified as an integer value that divides h without remainder. The same tree height h/d and the same Winternitz parameter w are used for all tree layers
XMSS^MT Signature
An XMSS^MT signature Sig_MT is a byte string of length (std::ceil(h / 8) + n (h + d * len) * n) It consists of:
- the index idx_sig of the used WOTS+ key pair on the bottom layer std::ceil(h / 8) bytes
- a byte string r used for randomized message hashing (n bytes)
- d reduced XMSS signatures ((h / d + len) * n bytes each)
The reduced XMSS signatures only contain a WOTS+ signature sig_ots and an authentication path auth. They contain no index idx and no byte string r. The XMSS^MT signature has the following format
NIST SP 800-208 Additions - eXtended Merkle Signature Scheme (XMSS) Parameter Sets
The XMSS and XMSSMT algorithms are described in RFC 8391 [1]. This Special Publication approves the use of XMSS and XMSSMT with four different hash functions: SHA-256, SHA-256/192, SHAKE256/256, and SHAKE256/192 (see Section 2.3). 5 The parameter sets that use SHA-256 are defined in RFC 8391 [1]. The parameter sets that use SHA-256/192, SHAKE256/256, and SHAKE256/192 are defined below
The WOTS+ parameters that correspond to the use of each of these hash functions are specified in table 9
XMSS and XMSSMT Random Number Generation Requirements
The n-byte values SK_PRF and SEED 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 8n bits of security strength
The private n-byte strings in the WOTS+ private keys (sk[i] in Section 3.1.3 of [1]) shall be generated using the pseudorandom key generation method specified in Algorithm 10' in Section 7.2.1:
sk[j] = PRFkeygen(S_XMSS, SEED || ADRS)
where PRFkeygen is as defined in Section 5 for the parameter set being used. 6 The private seed, S_XMSS, 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 XMSS key pair is being created within a cryptographic module (including XMSS keys that belong to a single XMSSMT instance), then a separate random S_XMSS shall be generated for each XMSS key pair
XMSS^MT Key Generation
Distributing the implementation of an XMSSMT instance across multiple cryptographic modules requires each cryptographic module to implement slightly modified versions of the XMSS key and signature generation algorithms provided in [1]. The modified versions of these algorithms are provided in Section 7.2.1. The modifications are primarily intended to ensure that each XMSS key uses the appropriate values for its layer and tree addresses when computing prefixes and bitmasks. The modifications also ensure that every XMSS key uses the same value for SEED and that the root of the top-level tree is used when computing the hashes of messages to be signed
Note that while Algorithm 15 in [1] indicates that an XMSSMT secret key has a single SK_PRF value that is shared by all of the XMSS secret keys, Algorithm 10' in Section 7.2.1 has each cryptographic module generate its own value for SK_PRF. While generating a different SK_PRF for each cryptographic module does not exactly align with the specification in [1], doing so does not affect either interoperability or security. SK_PRF is only used to pseudorandomly generate the value r in Algorithm 16, which is used for randomized hashing, and any secure method for generating random values could be used to generate r
Section 7.2.2 describes the steps that an external, non-cryptographic device needs to perform in order to implement XMSSMT key and signature generation using a set of cryptographic modules that implement the algorithms in Section 7.2.1. While Algorithms 10' and 12' in Section 7.2.1 have been designed to work with XMSSMT instances that have more than two layers, the algorithms in Section 7.2.2 assume that an XMSSMT instance with exactly two layers is being created
Supported XMSS Parameters
| Name | H | m | h | type value |
|---|---|---|---|---|
| XMSS_SHA2_10_256 | SHA256 | 32 | 10 | 0x00000001 |
| XMSS_SHA2_16_256 | SHA256 | 32 | 16 | 0x00000002 |
| XMSS_SHA2_20_256 | SHA256 | 32 | 20 | 0x00000003 |
| XMSS_SHA2_10_192 | SHA256 | 24 | 10 | 0x0000000D |
| XMSS_SHA2_16_192 | SHA256 | 24 | 16 | 0x0000000E |
| XMSS_SHA2_20_192 | SHA256 | 24 | 20 | 0x0000000F |
| XMSS_SHAKE256_10_256 | SHAKE256 | 32 | 10 | 0x00000010 |
| XMSS_SHAKE256_16_256 | SHAKE256 | 32 | 16 | 0x00000011 |
| XMSS_SHAKE256_20_256 | SHAKE256 | 32 | 20 | 0x00000012 |
| XMSS_SHAKE256_10_192 | SHAKE256 | 24 | 10 | 0x00000013 |
| XMSS_SHAKE256_16_192 | SHAKE256 | 24 | 16 | 0x00000014 |
| XMSS_SHAKE256_20_192 | SHAKE256 | 24 | 20 | 0x00000015 |
Supported XMSS^MT Parameters
| Name | H | m | h | d | type value |
|---|---|---|---|---|---|
| XMSSMT_SHA2_20_2_256 | SHA256 | 32 | 20 | 2 | 0x00000001 |
| XMSSMT_SHA2_20_4_256 | SHA256 | 32 | 20 | 4 | 0x00000002 |
| XMSSMT_SHA2_40_2_256 | SHA256 | 32 | 40 | 2 | 0x00000003 |
| XMSSMT_SHA2_40_4_256 | SHA256 | 32 | 40 | 4 | 0x00000004 |
| XMSSMT_SHA2_40_8_256 | SHA256 | 32 | 40 | 4 | 0x00000005 |
| XMSSMT_SHA2_60_3_256 | SHA256 | 32 | 60 | 3 | 0x00000006 |
| XMSSMT_SHA2_60_6_256 | SHA256 | 32 | 60 | 6 | 0x00000007 |
| XMSSMT_SHA2_60_12_256 | SHA256 | 32 | 60 | 12 | 0x00000008 |
| XMSSMT_SHA2_20_2_192 | SHA256 | 32 | 20 | 2 | 0x00000021 |
| XMSSMT_SHA2_20_4_192 | SHA256 | 32 | 20 | 4 | 0x00000022 |
| XMSSMT_SHA2_40_2_192 | SHA256 | 32 | 40 | 2 | 0x00000023 |
| XMSSMT_SHA2_40_4_192 | SHA256 | 32 | 40 | 4 | 0x00000024 |
| XMSSMT_SHA2_40_8_192 | SHA256 | 32 | 40 | 4 | 0x00000025 |
| XMSSMT_SHA2_60_3_192 | SHA256 | 32 | 60 | 3 | 0x00000026 |
| XMSSMT_SHA2_60_6_192 | SHA256 | 32 | 60 | 6 | 0x00000027 |
| XMSSMT_SHA2_60_12_192 | SHA256 | 32 | 60 | 12 | 0x00000028 |
| XMSSMT_SHAKE256_20_2_256 | SHAKE256 | 32 | 20 | 2 | 0x00000029 |
| XMSSMT_SHAKE256_20_4_256 | SHAKE256 | 32 | 20 | 4 | 0x0000002A |
| XMSSMT_SHAKE256_40_2_256 | SHAKE256 | 32 | 40 | 2 | 0x0000002B |
| XMSSMT_SHAKE256_40_4_256 | SHAKE256 | 32 | 40 | 4 | 0x0000002C |
| XMSSMT_SHAKE256_40_8_256 | SHAKE256 | 32 | 40 | 4 | 0x0000002D |
| XMSSMT_SHAKE256_60_3_256 | SHAKE256 | 32 | 60 | 3 | 0x0000002E |
| XMSSMT_SHAKE256_60_6_256 | SHAKE256 | 32 | 60 | 6 | 0x0000002F |
| XMSSMT_SHAKE256_60_12_256 | SHAKE256 | 32 | 60 | 12 | 0x00000030 |
| XMSSMT_SHAKE256_20_2_192 | SHAKE256 | 32 | 20 | 2 | 0x00000031 |
| XMSSMT_SHAKE256_20_4_192 | SHAKE256 | 32 | 20 | 4 | 0x00000032 |
| XMSSMT_SHAKE256_40_2_192 | SHAKE256 | 32 | 40 | 2 | 0x00000033 |
| XMSSMT_SHAKE256_40_4_192 | SHAKE256 | 32 | 40 | 4 | 0x00000034 |
| XMSSMT_SHAKE256_40_8_192 | SHAKE256 | 32 | 40 | 4 | 0x00000035 |
| XMSSMT_SHAKE256_60_3_192 | SHAKE256 | 32 | 60 | 3 | 0x00000036 |
| XMSSMT_SHAKE256_60_6_192 | SHAKE256 | 32 | 60 | 6 | 0x00000037 |
| XMSSMT_SHAKE256_60_12_192 | SHAKE256 | 32 | 60 | 12 | 0x00000038 |
For API Documentation:
- See also
- ProtocolPP::jxmss
- ProtocolPP::jxmssa
For Additional Documentation:
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)
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:
- jxmss/include/jxmss.h
