Crypto Forum Research Group D. McGrew
Internet-Draft M. Curcio
Intended status: Informational Cisco Systems
Expires: January 5, 2015 July 4, 2014
Hash-Based Signatures
draft-mcgrew-hash-sigs-02
Abstract
This note describes a digital signature system based on cryptographic
hash functions, following the seminal work in this area. It
specifies a one-time signature scheme based on the work of Lamport,
Diffie, Winternitz, and Merkle (LDWM), and a general signature
scheme, Merkle Tree Signatures (MTS). These systems provide
asymmetric authentication without using large integer mathematics and
can achieve a high security level. They are suitable for compact
implementations, are relatively simple to implement, and naturally
resist side-channel attacks. Unlike most other signature systems,
hash-based signatures would still be secure even if it proves
feasible for an attacker to build a quantum computer.
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on January 5, 2015.
Copyright Notice
Copyright (c) 2014 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
McGrew & Curcio Expires January 5, 2015 [Page 1]
Internet-Draft Hash-Based Signatures July 2014
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
McGrew & Curcio Expires January 5, 2015 [Page 2]
Internet-Draft Hash-Based Signatures July 2014
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1. Conventions Used In This Document . . . . . . . . . . . . 5
2. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1. Operators . . . . . . . . . . . . . . . . . . . . . . 6
2.1.2. Strings of w-bit elements . . . . . . . . . . . . . . 6
2.2. Functions . . . . . . . . . . . . . . . . . . . . . . . . 7
3. LDWM One-Time Signatures . . . . . . . . . . . . . . . . . . . 9
3.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2. Hashing Functions . . . . . . . . . . . . . . . . . . . . 9
3.3. Signature Methods . . . . . . . . . . . . . . . . . . . . 10
3.4. Private Key . . . . . . . . . . . . . . . . . . . . . . . 10
3.5. Public Key . . . . . . . . . . . . . . . . . . . . . . . . 11
3.6. Checksum . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.7. Signature Generation . . . . . . . . . . . . . . . . . . . 12
3.8. Signature Verification . . . . . . . . . . . . . . . . . . 13
3.9. Notes . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.10. Formats . . . . . . . . . . . . . . . . . . . . . . . . . 13
4. Merkle Tree Signatures . . . . . . . . . . . . . . . . . . . . 17
4.1. Private Key . . . . . . . . . . . . . . . . . . . . . . . 17
4.2. MTS Public Key . . . . . . . . . . . . . . . . . . . . . . 17
4.3. MTS Signature . . . . . . . . . . . . . . . . . . . . . . 18
4.3.1. MTS Signature Generation . . . . . . . . . . . . . . . 19
4.4. MTS Signature Verification . . . . . . . . . . . . . . . . 19
4.5. MTS Formats . . . . . . . . . . . . . . . . . . . . . . . 20
5. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6. History . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25
8. Security Considerations . . . . . . . . . . . . . . . . . . . 28
8.1. Security of LDWM Checksum . . . . . . . . . . . . . . . . 29
8.2. Security Conjectures . . . . . . . . . . . . . . . . . . . 29
8.3. Post-Quantum Security . . . . . . . . . . . . . . . . . . 30
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 31
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 32
10.1. Normative References . . . . . . . . . . . . . . . . . . . 32
10.2. Informative References . . . . . . . . . . . . . . . . . . 32
McGrew & Curcio Expires January 5, 2015 [Page 3]
Internet-Draft Hash-Based Signatures July 2014
Appendix A. LDWM Parameter Options . . . . . . . . . . . . . . . 33
Appendix B. Example Data for Testing . . . . . . . . . . . . . . 35
B.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . . 35
B.2. Key Generation . . . . . . . . . . . . . . . . . . . . . . 35
B.3. Signature Generation . . . . . . . . . . . . . . . . . . . 41
B.4. Signature Verification . . . . . . . . . . . . . . . . . . 45
B.5. Intermediate Calculation Values . . . . . . . . . . . . . 45
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 51
McGrew & Curcio Expires January 5, 2015 [Page 4]
Internet-Draft Hash-Based Signatures July 2014
1. Introduction
One-time signature systems, and general purpose signature systems
built out of one-time signature systems, have been known since 1979
[Merkle79], were well studied in the 1990s, and have benefited from
renewed development in the last decade. The characteristics of these
signature systems are small private and public keys and fast
signature generation and verification, but large signatures and
relatively slow key generation. In recent years there has been
interest in these systems because of their post-quantum security (see
Section 8.3) and their suitability for compact implementations.
This note describes the original Lamport-Diffie-Winternitz-Merkle
(LDWM) one-time signature system (following Merkle 1979 but also
using a technique from Merkle's later work [C:Merkle87][C:
Merkle89a][C:Merkle89b]) and Merkle tree signature system (following
Merkle 1979) with enough specificity to ensure interoperability
between implementations.
A signature system provides asymmetric message authentication. The
key generation algorithm produces a public/private key pair. A
message is signed by a private key, producing a signature, and a
message/signature pair can be verified by a public key. A One-Time
Signature (OTS) system can be used to sign exactly one message
securely. A general signature system can be used to sign multiple
messages. The Merkle Tree Signatures (MTS) is a general signature
system that uses an OTS system as a component. In principle the MTS
can be used with any OTS system, but in this note we describe its use
with the LDWM system.
This note is structured as follows. Notation is introduced in
Section 2. The LDWM signature system is described in Section 3, and
the Merkle tree signature system is described in Section 4.
Sufficient detail is provided to ensure interoperability. Appendix B
describes test considerations and contains test cases that can be
used to validate an implementation. The IANA registry for these
signature systems is described in Section 7. Security considerations
are presented in Section 8.
1.1. Conventions Used In This Document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
McGrew & Curcio Expires January 5, 2015 [Page 5]
Internet-Draft Hash-Based Signatures July 2014
2. Notation
2.1. Data Types
Bytes and byte strings are the fundamental data types. A single byte
is denoted as a pair of hexadecimal digits with a leading "0x". A
byte string is an ordered sequence of zero or more bytes and is
denoted as an ordered sequence of hexadecimal characters with a
leading "0x". For example, 0xe534f0 is a byte string with a length
of three. An array of byte strings is an ordered set, indexed
starting at zero, in which all strings have the same length.
2.1.1. Operators
When a and b are real numbers, mathematical operators are defined as
follows:
^ : a ^ b denotes the result of a raised to the power of b
* : a * b denotes the product of a multiplied by b
/ : a / b denotes the quotient of a divided by b
% : a % b denotes the remainder of the integer division of a by b
+ : a + b denotes the sum of a and b
- : a - b denotes the difference of a and b
The standard order of operations is used when evaluating arithmetic
expressions.
If A and B are bytes, then A AND B denotes the bitwise logical and
operation.
When B is a byte and i is an integer, then B >> i denotes the logical
right-shift operation. Similarly, B << i denotes the logical left-
shift operation.
If S and T are byte strings, then S || T denotes the concatenation of
S and T.
The i^th byte string in an array A is denoted as A[i].
2.1.2. Strings of w-bit elements
If S is a byte string, then byte(S, i) denotes its i^th byte, where
byte(S, 0) is the leftmost byte. In addition, bytes(S, i, j) denotes
McGrew & Curcio Expires January 5, 2015 [Page 6]
Internet-Draft Hash-Based Signatures July 2014
the range of bytes from the i^th to the j^th byte, inclusive. For
example, if S = 0x02040608, then byte(S, 0) is 0x02 and bytes(S, 1,
2) is 0x0406.
A byte string can be considered to be a string of w-bit unsigned
integers; the correspondence is defined by the function coef(S, i, w)
as follows:
If S is a string, i is a positive integer, and w is a member of the
set { 1, 2, 4, 8 }, then coef(S, i, w) is the i^th, w-bit value, if S
is interpreted as a sequence of w-bit values. That is,
coef(S, i, w) = (2^w - 1) AND
( byte(S, floor(i * w / 8)) >>
(8 - (w * (i % (8 / w)) + w)) )
For example, if S is the string 0x1234, then coef(S, 7, 1) is 0 and
coef(S, 0, 4) is 1.
S (represented as bits)
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
^
|
coef(S, 7, 1)
S (represented as four-bit values)
+-----------+-----------+-----------+-----------+
| 1 | 2 | 3 | 4 |
+-----------+-----------+-----------+-----------+
^
|
coef(S, 0, 4)
The return value of coef is an unsigned integer. If i is larger than
the number of w-bit values in S, then coef(S, i, w) is undefined, and
an attempt to compute that value should raise an error.
2.2. Functions
If r is a non-negative real number, then we define the following
functions:
ceil(r) : returns the smallest integer larger than r
McGrew & Curcio Expires January 5, 2015 [Page 7]
Internet-Draft Hash-Based Signatures July 2014
floor(r) : returns the largest integer smaller than r
lg(r) : returns the base-2 logarithm of r
When F is a function that takes r-byte strings as input and returns
r-byte strings as output, we denote the repeated applications of F
with itself a non-negative, integral number of times i as F^i.
Thus for any m-byte string x ,
F^i(x) = / F( F^(i-1)(x) ) for i > 0
\ x for i = 0.
For example, F^2(x) = F(F(x)).
McGrew & Curcio Expires January 5, 2015 [Page 8]
Internet-Draft Hash-Based Signatures July 2014
3. LDWM One-Time Signatures
This section defines LDWM signatures. The signature is used to
validate the authenticity of a message by associating a secret
private key with a shared public key. These are one-time signatures;
each private key MUST be used only one time to sign any given
message.
As part of the signing process, a digest of the original message is
computed using the collision-resistant hash function H (see
Section 3.2), and the resulting digest is signed.
3.1. Parameters
The signature system uses the parameters m, n, and w; they are all
positive integers. The algorithm description also uses the values p
and ls. These parameters are summarized as follows:
m : the length in bytes of each element of an LDWM signature
n : the length in bytes of the result of the hash function
w : the Winternitz parameter; it is a member of the set
{ 1, 2, 4, 8 }
p : the number of m-byte string elements that make up the LDWM
signature
ls : the number of left-shift bits used in the checksum function C
(defined in Section 3.6).
The values of m and n are determined by the functions selected for
use as part of the LDWM algorithm. They are chosen to ensure an
appropriate level of security. The parameter w can be chosen to set
the number of bytes in the signature; it has little effect on
security. Note however, that there is a larger computational cost to
generate and verify a shorter signature. The values of p and ls are
dependent on the choices of the parameters n and w, as described in
Appendix A. A table illustrating various combinations of n, w, p,
and ls is provided in Table 4.
3.2. Hashing Functions
The LDWM algorithm uses a collision-resistant hash function H and a
one way (preimage resistant) function F. H accepts byte strings of
any length, and returns an n-byte string. F has m-byte inputs and
m-byte outputs.
McGrew & Curcio Expires January 5, 2015 [Page 9]
Internet-Draft Hash-Based Signatures July 2014
3.3. Signature Methods
To fully describe a LDWM signature method, the parameters m, n, and
w, as well as the functions H and F MUST be specified. This section
defines several LDWM signature systems, each of which is identified
by a name. Values for p and ls are provided as a convenience.
+--------------------+--------+-----------+----+----+---+-----+----+
| Name | H | F | m | n | w | p | ls |
+--------------------+--------+-----------+----+----+---+-----+----+
| LDWM_SHA512_M64_W1 | SHA512 | SHA512 | 32 | 32 | 1 | 265 | 7 |
| | | | | | | | |
| LDWM_SHA512_M64_W2 | SHA512 | SHA512 | 32 | 32 | 2 | 133 | 6 |
| | | | | | | | |
| LDWM_SHA512_M64_W4 | SHA512 | SHA512 | 32 | 32 | 4 | 67 | 4 |
| | | | | | | | |
| LDWM_SHA512_M64_W8 | SHA512 | SHA512 | 32 | 32 | 8 | 34 | 0 |
| | | | | | | | |
| LDWM_SHA256_M32_W1 | SHA256 | SHA256 | 32 | 32 | 1 | 265 | 7 |
| | | | | | | | |
| LDWM_SHA256_M32_W2 | SHA256 | SHA256 | 32 | 32 | 2 | 133 | 6 |
| | | | | | | | |
| LDWM_SHA256_M32_W4 | SHA256 | SHA256 | 32 | 32 | 4 | 67 | 4 |
| | | | | | | | |
| LDWM_SHA256_M32_W8 | SHA256 | SHA256 | 32 | 32 | 8 | 34 | 0 |
| | | | | | | | |
| LDWM_SHA256_M20_W1 | SHA256 | SHA256-20 | 20 | 32 | 1 | 265 | 7 |
| | | | | | | | |
| LDWM_SHA256_M20_W2 | SHA256 | SHA256-20 | 20 | 32 | 2 | 133 | 6 |
| | | | | | | | |
| LDWM_SHA256_M20_W4 | SHA256 | SHA256-20 | 20 | 32 | 4 | 67 | 4 |
| | | | | | | | |
| LDWM_SHA256_M20_W8 | SHA256 | SHA256-20 | 20 | 32 | 8 | 34 | 0 |
+--------------------+--------+-----------+----+----+---+-----+----+
Table 1
Here SHA512 and SHA256 denotes the NIST standard hash functions
[FIPS180]. SHA256-20 denotes the SHA256 hash function with its final
output truncated to return the leftmost 20 bytes.
3.4. Private Key
The LDWM private key is an array of size p containing m-byte strings.
Let x denote the private key. This private key must be used to sign
one and only one message. It must therefore be unique from all other
private keys. The following algorithm shows pseudocode for
generating x.
McGrew & Curcio Expires January 5, 2015 [Page 10]
Internet-Draft Hash-Based Signatures July 2014
Algorithm 0: Generating a Private Key
for ( i = 0; i < p; i = i + 1 ) {
set x[i] to a uniformly random m-byte string
}
return x
An implementation MAY use a pseudorandom method to compute x[i], as
suggested in [Merkle79], page 46. The details of the pseudorandom
method do not affect interoperability, but the cryptographic strength
MUST match that of the LDWM algorithm.
3.5. Public Key
The LDWM public key is generated from the private key by applying the
function F^(2^w - 1) to each individual element of x, then hashing
all of the resulting values. The following algorithm shows
pseudocode for generating the public key, where the array x is the
private key.
Algorithm 1: Generating a Public Key From a Private Key
e = 2^w - 1
for ( i = 0; i < p; i = i + 1 ) {
y[i] = F^e(x[i])
}
return H(y[0] || y[1] || ... || y[p-1])
3.6. Checksum
A checksum is used to ensure that any forgery attempt that
manipulates the elements of an existing signature will be detected.
The security property that it provides is detailed in Section 8.
The checksum value is calculated using a non-negative integer, sum,
whose width is sized an integer number of w-bit fields such that it
is capable of holding the difference of the total possible number of
applications of the function F as defined in the signing algorithm of
Section 3.7 and the total actual number. In the worst case (i.e. the
actual number of times F is iteratively applied is 0), the sum is
(2^w - 1) * ceil(8*n/w). Thus for the purposes of this document,
which describes signature methods based on H = SHA256 (n = 32 bytes)
and w = { 1, 2, 4, 8 }, let sum be a 16-bit non-negative integer for
all combinations of n and w. The calculation uses the parameter ls
defined in Section 3.1 and calculated in Appendix A, which indicates
the number of bits used in the left-shift operation. The checksum
function C is defined as follows, where S denotes the byte string
that is input to that function.
McGrew & Curcio Expires January 5, 2015 [Page 11]
Internet-Draft Hash-Based Signatures July 2014
Algorithm 2: Checksum Calculation
sum = 0
for ( i = 0; i < u; i = i + 1 ) {
sum = sum + (2^w - 1) - coef(S, i, w)
}
return (sum << ls)
Because of the left-shift operation, the rightmost bits of the result
of C will often be zeros. Due to the value of p, these bits will not
be used during signature generation or verification.
Implementation Note: Based on the previous fact, an implementation
MAY choose to optimize the width of sum to (v * w) bits and set ls
to 0. The rationale for this is given that (2^w - 1) *
ceil(8*n/w) is the maximum value of sum and the value of (2^w - 1)
is represented by w bits, the result of adding u w-bit numbers,
where u = ceil(8*n/w), requires at most (ceil(lg(u)) + w) bits.
Dividing by w and taking the next largest integer gives the total
required number of w-bit fields and gives (ceil(lg(u)) / w) + 1,
or v. Thus sum requires a minimum width of (v * w) bits and no
left-shift operation is performed.
3.7. Signature Generation
The LDWM signature is generated by using H to compute the hash of the
message, concatenating the checksum of the hash to the hash itself,
then considering the resulting value as a sequence of w-bit values,
and using using each of the the w-bit values to determine the number
of times to apply the function F to the corresponding element of the
private key. The outputs of the function F are concatenated together
and returned as the signature. The pseudocode for this procedure is
shown below.
Algorithm 3: Generating a Signature From a Private Key and a Message
V = ( H(message) || C(H(message)) )
for ( i = 0; i < p; i = i + 1 ) {
a = coef(V, i, w)
y[i] = F^a(x[i])
}
return (y[0] || y[1] || ... || y[p-1])
Note that this algorithm results in a signature whose elements are
intermediate values of the elements computed by the public key
algorithm in Section 3.5.
The signature should be provided by the signer to the verifier, along
McGrew & Curcio Expires January 5, 2015 [Page 12]
Internet-Draft Hash-Based Signatures July 2014
with the message and the public key.
3.8. Signature Verification
In order to verify a message with its signature (an array of m-byte
strings, denoted as y), the receiver must "complete" the series of
applications of F, using the w-bit values of the message hash and its
checksum. This computation should result in a value that matches the
provided public key.
Algorithm 4: Verifying a Signature and Message Using a Public Key
V = ( H(message) || C(H(message)) )
for ( i = 0; i < p; i = i + 1 ) {
a = (2^w - 1) - coef(V, i, w)
z[i] = F^a(y'[i])
}
if public key is equal to H(z[0] || z[1] || ... || z[p-1])
return 1 (message signature is valid)
else
return 0 (message signature is invalid)
3.9. Notes
A future version of this specification may define a method for
computing the signature of a very short message in which the hash is
not applied to the message during the signature computation. That
would allow the signatures to have reduced size.
3.10. Formats
The signature and public key formats are formally defined using XDR
[RFC4506] in order to provide an unambiguous, machine readable
definition. For clarity, we also include a private key format as
well, though consistency is not needed for interoperability and an
implementation MAY use any private key format. Though XDR is used,
these formats are simple and easy to parse without any special tools.
To avoid the need to convert to and from network / host byte order,
the enumeration values are all palindromes. The definitions are as
follows:
/*
* ots_algorithm_type identifies a particular signature algorithm
*/
enum ots_algorithm_type {
ots_reserved = 0,
ldwm_sha256_m20_w1 = 0x01000001,
McGrew & Curcio Expires January 5, 2015 [Page 13]
Internet-Draft Hash-Based Signatures July 2014
ldwm_sha256_m20_w2 = 0x02000002,
ldwm_sha256_m20_w4 = 0x03000003,
ldwm_sha256_m20_w8 = 0x04000004,
ldwm_sha256_m32_w1 = 0x05000005,
ldwm_sha256_m32_w2 = 0x06000006,
ldwm_sha256_m32_w4 = 0x07000007,
ldwm_sha256_m32_w8 = 0x08000008,
ldwm_sha512_m64_w1 = 0x09000009,
ldwm_sha512_m64_w2 = 0x0a00000a,
ldwm_sha512_m64_w4 = 0x0b00000b,
ldwm_sha512_m64_w8 = 0x0c00000c
};
/*
* byte string
*/
typedef opaque bytestring20[20];
typedef opaque bytestring32[32];
typedef opaque bytestring64[64];
union ots_signature switch (ots_algorithm_type type) {
case ldwm_sha256_m20_w1:
bytestring20 y_m20_p265[265];
case ldwm_sha256_m20_w2:
bytestring20 y_m20_p133[133];
case ldwm_sha256_m20_w4:
bytestring20 y_m20_p67[67];
case ldwm_sha256_m20_w8:
bytestring20 y_m20_p34[34];
case ldwm_sha256_m32_w1:
bytestring32 y_m32_p265[265];
case ldwm_sha256_m32_w2:
bytestring32 y_m3_p133[133];
case ldwm_sha256_m32_w4:
bytestring32 y_m32_y_p67[67];
case ldwm_sha256_m32_w8:
bytestring32 y_m32_p34[34];
case ldwm_sha512_m64_w1:
bytestring64 y_m64_p265[265];
case ldwm_sha512_m64_w2:
bytestring64 y_m64_p133[133];
case ldwm_sha512_m64_w4:
bytestring64 y_m64_y_p67[67];
case ldwm_sha512_m64_w8:
bytestring64 y_m64_p34[34];
default:
void; /* error condition */
};
McGrew & Curcio Expires January 5, 2015 [Page 14]
Internet-Draft Hash-Based Signatures July 2014
union ots_public_key switch (ots_algorithm_type type) {
case ldwm_sha256_m20_w1:
case ldwm_sha256_m20_w2:
case ldwm_sha256_m20_w4:
case ldwm_sha256_m20_w8:
case ldwm_sha256_m32_w1:
case ldwm_sha256_m32_w2:
case ldwm_sha256_m32_w4:
case ldwm_sha256_m32_w8:
bytestring32 y32;
case ldwm_sha512_m64_w1:
case ldwm_sha512_m64_w2:
case ldwm_sha512_m64_w4:
case ldwm_sha512_m64_w8:
bytestring64 y64;
default:
void; /* error condition */
};
union ots_private_key switch (ots_algorithm_type type) {
case ldwm_sha256_m20_w1:
case ldwm_sha256_m20_w2:
case ldwm_sha256_m20_w4:
case ldwm_sha256_m20_w8:
bytestring20 x20;
case ldwm_sha256_m32_w1:
case ldwm_sha256_m32_w2:
case ldwm_sha256_m32_w4:
case ldwm_sha256_m32_w8:
bytestring32 x32;
case ldwm_sha512_m64_w1:
case ldwm_sha512_m64_w2:
case ldwm_sha512_m64_w4:
case ldwm_sha512_m64_w8:
bytestring64 y64;
default:
void; /* error condition */
};
Though the data formats are formally defined by XDR, we diagram the
format as well as a convenience to the reader. An example of the
format of an ldwm_signature is illustrated below, for
ldwm_sha256_m32_w1. An ots_signature consists of a 32-bit unsigned
integer that indicates the ots_algorithm_type, followed by other
data, whose format depends only on the ots_algorithm_type. In the
case of LDWM, the data is an array of equal-length byte strings. The
number of bytes in each byte string, and the number of elements in
the array, are determined by the ots_algorithm_type field. In the
McGrew & Curcio Expires January 5, 2015 [Page 15]
Internet-Draft Hash-Based Signatures July 2014
case of ldwm_sha256_m32_w1, the array has 265 elements, each of which
is a 32-byte string. The XDR array y_m32_p265 denotes the array y as
used in the algorithm descriptions above, using the parameters of
m=32 and p=265 for ldwm_sha256_m32_w1.
A verifier MUST check the ots_algorithm_type field, and a
verification operation on a signature with an unknown
ldwm_algorithm_type MUST return FAIL.
+---------------------------------+
| ots_algorithm_type |
+---------------------------------+
| |
| y_m32_p265[0] |
| |
+---------------------------------+
| |
| y_m32_p265[1] |
| |
+---------------------------------+
| |
~ .... ~
| |
+---------------------------------+
| |
| y_m32_p265[264] |
| |
+---------------------------------+
McGrew & Curcio Expires January 5, 2015 [Page 16]
Internet-Draft Hash-Based Signatures July 2014
4. Merkle Tree Signatures
Merkle Tree Signatures (MTS) are a method for signing a potentially
large but fixed number of messages. An MTS system uses two
cryptographic components: a one-time signature method and a
collision-resistant hash function. Each MTS public/private key pair
is associated with a perfect k-ary tree, each node of which contains
an n-byte value. Each leaf of the tree contains the value of the
public key of an LDWM public/private key pair. The value contained
by the root of the tree is the MTS public key. Each interior node is
computed by applying the hash function to the concatenation of the
values of its children nodes.
An MTS system has the following parameters:
k : the number of children nodes of an interior node,
h : the height (number of levels - 1) in the tree, and
n : the number of bytes associated with each node.
There are k^h leaves in the tree.
4.1. Private Key
An MTS private key consists of k^h one-time signature private keys
and the leaf number of the next LDWM private key that has not yet
been used. The leaf number is initialized to zero when the MTS
private key is created.
An MTS private key MAY be generated pseudorandomly from a secret
value, in which case the secret value MUST be at least n bytes long,
be uniformly random, and MUST NOT be used for any other purpose than
the generation of the MTS private key. The details of how this
process is done do not affect interoperability; that is, the public
key verification operation is independent of these details.
4.2. MTS Public Key
An MTS public key is defined as follows, where we denote the public
key associated with the i^th LDWM private key as ldwm_public_key(i).
The MTS public key can be computed using the following algorithm or
any equivalent method. The algorithm uses a stack of hashes for data
and a separate stack of integers to keep track of the level of the
Merkle tree.
McGrew & Curcio Expires January 5, 2015 [Page 17]
Internet-Draft Hash-Based Signatures July 2014
Algorithm 5: Generating an MTS Public Key From an MTS Private Key
for ( i = 0; i < num_ldwm_keys; i = i + k ) {
level = 0;
for ( j = 0; j < k; j = j + 1 ) {
push ldwm_public_key(i+j) onto the data stack
push level onto the integer stack
}
while ( height of the integer stack >= k ) {
if level of the top k elements on the integer stack are equal {
hash_init()
siblings = ""
repeat ( k ) {
siblings = (pop(data stack) || siblings)
level = pop(integer stack)
}
hash_update(siblings)
push hash_final() onto the data stack
push (level + 1) onto the integer stack
}
}
}
public_key = pop(data stack)
Note that this pseudocode expects, as was defined earlier, the Merkle
Tree to be perfect. That is, all h^k leaves of the tree have equal
depth. Also, neither stack ever contains more than h*(k-1)+1
elements. For typical parameters, it will hold roughly 20 32-byte
values.
4.3. MTS Signature
An MTS signature consists of
an LDWM signature,
a node number that identifies the leaf node associated with the
signature, and
an array of values that is associated with the path through the
tree from the leaf associated with the LDWM signature to the root.
The array of values contains 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 branching number k and
height h will have (k-1)*h values. The first (k-1) values are the
siblings of the leaf, the next (k-1) values are the siblings of the
parent of the leaf, and so on.
McGrew & Curcio Expires January 5, 2015 [Page 18]
Internet-Draft Hash-Based Signatures July 2014
4.3.1. MTS Signature Generation
To compute the MTS signature of a message with an MTS private key,
the signer first computes the LDWM signature of the message using the
leaf number of the next unused LDWM private key. Before releasing
the signature, the leaf number in the MTS private key MUST be
incremented to prevent the LDWM private key from being used again.
The node number in the signature is set to the leaf number of the MTS
private key that was used in the signature.
The array of node values MAY be computed in any way. There are many
potential time/storage tradeoffs. The fastest alternative is to
store all of the nodes of the tree and set the array in the signature
by copying them. The least storage intensive alternative is to
recompute all of the nodes for each signature. Note that the details
of this procedure are not important for interoperability; it is not
necessary to know any of these details in order to perform the
signature verification operation.
4.4. MTS Signature Verification
An MTS signature is verified by first using the LDWM signature
verification algorithm to compute the LDWM public key from the LDWM
signature and the message. The value of the leaf associated with the
LDWM signature is assigned to the public key. Then the root of the
tree is computed from the leaf value and the node array (path[]) as
described below. If the root value matches the public key, then the
signature is valid; otherwise, the signature fails.
McGrew & Curcio Expires January 5, 2015 [Page 19]
Internet-Draft Hash-Based Signatures July 2014
Algorithm 6: Computing the MTS Root Value
n = node number
v = leaf
step = 0
for ( i = 0; i < h; i = i + 1 ) {
position = n % k
hash_init()
for ( j = 0; j < position; j = j + 1 ) {
hash_update(path[step + j])
}
hash_update(v)
for ( j = position; j < (k-1); j = j + 1 ) {
hash_update(path[step + j])
}
v = hash_final()
n = floor(n/k)
step = step + (k-1)
}
Upon completion, v contains the value of the root of the Merkle Tree
for comparison.
This algorithm uses the typical init/update/final interface to hash
functions; the result of the invocations hash_init(),
hash_update(N[1]), hash_update(N[2]), ... , hash_update(N[n]), v =
hash_final(), in that order, is identical to that of the invocation
of H(N[1] || N[2] || ... || N[n]).
This algorithm works because the leaves of the MTS tree are numbered
starting at zero. Therefore leaf n is in the position (n % k) in the
highest level of the tree.
The verifier MAY cache interior node values that have been computed
during a successful signature verification for use in subsequent
signature verifications. However, any implementation that does so
MUST make sure any nodes that are cached during a signature
verification process are deleted if that process does not result in a
successful match between the root of the tree and the MTS public key.
A full test example that combines the LDWM OTS and MTS algorithms is
given in Appendix B.
4.5. MTS Formats
MTS signatures and public keys are defined using XDR syntax as
follows:
McGrew & Curcio Expires January 5, 2015 [Page 20]
Internet-Draft Hash-Based Signatures July 2014
enum mts_algorithm_type {
mts_reserved = 0x00000000,
mts_sha256_k2_h20 = 0x01000001,
mts_sha256_k4_h10 = 0x02000002,
mts_sha256_k8_h7 = 0x03000003,
mts_sha256_k16_h5 = 0x04000004,
mts_sha512_k2_h20 = 0x05000005,
mts_sha512_k4_h10 = 0x06000006,
mts_sha512_k8_h7 = 0x07000007,
mts_sha512_k16_h5 = 0x08000008
};
union mts_path switch (mts_algorithm_type type) {
case mts_sha256_k2_h20:
bytestring32 path_n32_t20[20];
case mts_sha256_k4_h10:
bytestring32 path_n32_t30[30];
case mts_sha256_k8_h7:
bytestring32 path_n32_t49[49];
case mts_sha256_k16_h5:
bytestring32 path_n32_t75[75];
case mts_sha512_k2_h20:
bytestring64 path_n64_t20[20];
case mts_sha512_k4_h10:
bytestring64 path_n64_t30[30];
case mts_sha512_k8_h7:
bytestring64 path_n64_t49[49];
case mts_sha512_k16_h5:
bytestring64 path_n64_t75[75];
default:
void; /* error condition */
};
struct mts_signature {
ots_signature ots_sig;
unsigned int signature_leaf_number;
mts_path nodes;
};
struct mts_public_key_n32 {
ots_algorithm_type ots_alg_type;
opaque value[32]; /* public key */
};
struct mts_public_key_n64 {
ots_algorithm_type ots_alg_type;
opaque value[64]; /* public key */
};
McGrew & Curcio Expires January 5, 2015 [Page 21]
Internet-Draft Hash-Based Signatures July 2014
union mts_public_key switch (mts_algorithm_type type) {
case mts_sha256_k2_h20:
case mts_sha256_k4_h10:
case mts_sha256_k8_h7:
case mts_sha256_k16_h5:
mts_public_key_n32 z_n32;
case mts_sha512_k2_h20:
case mts_sha512_k4_h10:
case mts_sha512_k8_h7:
case mts_sha512_k16_h5:
mts_public_key_n64 z_n64;
default:
void; /* error condition */
};
struct mts_private_key_n32 {
ots_algorithm_type ots_alg_type;
unsigned int next_ldwm_leaf_number; /* leaf # for next signature */
opaque value[32]; /* private key */
};
struct mts_private_key_n64 {
ots_algorithm_type ots_alg_type;
unsigned int next_ldwm_leaf_number; /* leaf # for next signature */
opaque value[64]; /* private key */
};
union mts_private_key switch (mts_algorithm_type mts_alg_type) {
case mts_sha256_k2_h20:
case mts_sha256_k4_h10:
case mts_sha256_k8_h7:
case mts_sha256_k16_h5:
mts_private_key_n32 body_n32;
case mts_sha512_k2_h20:
case mts_sha512_k4_h10:
case mts_sha512_k8_h7:
case mts_sha512_k16_h5:
mts_private_key_n64 body_n64;
default:
void; /* error condition */
};
McGrew & Curcio Expires January 5, 2015 [Page 22]
Internet-Draft Hash-Based Signatures July 2014
5. Rationale
The goal of this note is to describe the LDWM and MTS algorithms
following the original references and present the modern security
analysis of those algorithms. Other signature methods are out of
scope and may be interesting follow-on work.
The signature and public key formats are designed so that they are
easy to parse. Each format starts with a 32-bit enumeration value
that indicates all of the details of the signature algorithm and
hence defines all of the information that is needed in order to parse
the format.
The enumeration values used in this note are palindromes, which have
the same byte representation in either host order or network order.
This fact allows an implementation to omit the conversion between
byte order for those enumerations. Note however that the leaf number
field used in the MTS signature and keys must be properly converted
to and from network byte order; this is the only field that requires
such conversion. There are 2^32 XDR enumeration values, 2^16 of
which are palindromes, which is more than enough for the foreseeable
future. If there is a need for more assignments, non-palindromes can
be assigned.
McGrew & Curcio Expires January 5, 2015 [Page 23]
Internet-Draft Hash-Based Signatures July 2014
6. History
This is the initial version of this draft.
This section is to be removed by the RFC editor upon publication.
McGrew & Curcio Expires January 5, 2015 [Page 24]
Internet-Draft Hash-Based Signatures July 2014
7. IANA Considerations
The Internet Assigned Numbers Authority (IANA) is requested to create
two registries: one for OTS signatures, which includes all of the
LDWM signatures as defined in Section 3, and one for Merkle Tree
Signatures, as defined in Section 4. Additions to these registries
require that a specification be documented in an RFC or another
permanent and readily available reference in sufficient detail that
interoperability between independent implementations is possible.
Each entry in the registry contains the following elements:
a short name, such as "MTS_SHA256_K16_H5",
a positive number, and
a reference to a specification that completely defines the
signature method test cases that can be used to verify the
correctness of an implementation.
Requests to add an entry to the registry MUST include the name and
the reference. The number is assigned by IANA. These number
assignments SHOULD use the smallest available palindromic number.
Submitters SHOULD have their requests reviewed by the IRTF Crypto
Forum Research Group (CFRG) at cfrg@ietf.org. Interested applicants
that are unfamiliar with IANA processes should visit
http://www.iana.org.
The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF
(decimal 4,294,967,295) inclusive, will not be assigned by IANA, and
are reserved for private use; no attempt will be made to prevent
multiple sites from using the same value in different (and
incompatible) ways [RFC2434].
The LDWM registry is as follows.
McGrew & Curcio Expires January 5, 2015 [Page 25]
Internet-Draft Hash-Based Signatures July 2014
+--------------------+-----------+--------------------+
| Name | Reference | Numeric Identifier |
+--------------------+-----------+--------------------+
| LDWM_SHA256_M20_W1 | Section 3 | 0x01000001 |
| | | |
| LDWM_SHA256_M20_W2 | Section 3 | 0x02000002 |
| | | |
| LDWM_SHA256_M20_W4 | Section 3 | 0x03000003 |
| | | |
| LDWM_SHA256_M20_W8 | Section 3 | 0x04000004 |
| | | |
| LDWM_SHA256_M32_W1 | Section 3 | 0x05000005 |
| | | |
| LDWM_SHA256_M32_W2 | Section 3 | 0x06000006 |
| | | |
| LDWM_SHA256_M32_W4 | Section 3 | 0x07000007 |
| | | |
| LDWM_SHA256_M32_W8 | Section 3 | 0x08000008 |
| | | |
| LDWM_SHA512_M64_W1 | Section 3 | 0x09000009 |
| | | |
| LDWM_SHA512_M64_W2 | Section 3 | 0x0a00000a |
| | | |
| LDWM_SHA512_M64_W4 | Section 3 | 0x0b00000b |
| | | |
| LDWM_SHA512_M64_W8 | Section 3 | 0x0c00000c |
+--------------------+-----------+--------------------+
Table 2
The MTS registry is as follows.
McGrew & Curcio Expires January 5, 2015 [Page 26]
Internet-Draft Hash-Based Signatures July 2014
+-------------------+-----------+--------------------+
| Name | Reference | Numeric Identifier |
+-------------------+-----------+--------------------+
| MTS_SHA256_K2_H20 | Section 4 | 0x01000001 |
| | | |
| MTS_SHA256_K4_H10 | Section 4 | 0x02000002 |
| | | |
| MTS_SHA256_K8_H7 | Section 4 | 0x03000003 |
| | | |
| MTS_SHA256_K16_H5 | Section 4 | 0x04000004 |
| | | |
| MTS_SHA512_K2_H20 | Section 4 | 0x05000005 |
| | | |
| MTS_SHA512_K4_H10 | Section 4 | 0x06000006 |
| | | |
| MTS_SHA512_K8_H7 | Section 4 | 0x07000007 |
| | | |
| MTS_SHA512_K16_H5 | Section 4 | 0x08000008 |
+-------------------+-----------+--------------------+
Table 3
An IANA registration of a signature system does not constitute an
endorsement of that system or its security.
McGrew & Curcio Expires January 5, 2015 [Page 27]
Internet-Draft Hash-Based Signatures July 2014
8. Security Considerations
The security goal of a signature system is to prevent forgeries. A
successful forgery occurs when an attacker who does not know the
private key associated with a public key can find a message and
signature that are valid with that public key (that is, the Signature
Verification algorithm applied to that signature and message and
public key will return "valid"). Such an attacker, in the strongest
case, may have the ability to forge valid signatures for an arbitrary
number of other messages.
The security of the algorithms defined in this note can be roughly
described as follows. For a security level of roughly 128 bits,
assuming that there are no quantum computers, use the LDWM algorithms
with m=32 and MTS with n=32. For a security level of roughly 128
bits, assuming that there are quantum computers, use the LDWM
algorithms with m=64 and the MTS algorithms with n=64. For the
smallest possible signatures that provide a currently adequate
security level, use the LDWM algorithms with m=20 and MTS algorithms
with n=32. We emphasize that this is a rough estimate, and not a
security proof.
LDWM signatures rely on the fact that, given an m-byte string y, it
is prohibitively expensive to compute a value x such that F^i(x) = y
for any i. Informally, F is said to be a "one-way" function, or a
preimage-resistant function. Both LDWM and MTS signatures rely on
the fact that H is collision-resistant, that is, it is prohibitively
expensive for an attacker to find two byte strings a and b such that
H(a) = H(b).
There are several formal security proofs for one time signatures and
Merkle tree signatures in the cryptographic literature. Several of
these analyze variants of those algorithms, and are not directly
applicable to the original algorithms; thus caution is needed when
applying these analyses. The MTS scheme has been shown to provide
roughly b bits of security when used with a hash function with an
output size of 2*b bits [BDM08]. (A cryptographic scheme has b bits
of security when an attacker must perform O(2^b) computations to
defeat it.) More precisely, that analysis shows that MTS is
existentially unforgeable under an adaptive chosen message attack.
However, the analysis assumes that the hash function is chosen
uniformly at random from a family of hash functions, and thus is not
completely applicable. Similarly, LDWM with w=1 has been shown to be
existentially unforgeable under an adaptive chosen message attack,
when F is a one-way function [BDM08], when F is chosen uniformly at
random from a family of one-way functions; when F has c-bit inputs
and outputs, it provides roughly b bits of security. LDWM
signatures, as specified in this note, have been shown to be secure
McGrew & Curcio Expires January 5, 2015 [Page 28]
Internet-Draft Hash-Based Signatures July 2014
based on the collision resistance of F [C:Dods05]; that analysis
provides a lower bound on security (and it appears to be pessimistic,
especially in the case of the m=20 signatures).
It may be desirable to adapt this specification in a way that better
aligns with the security proofs. In particular, a random "salt"
value could be generated along with the key, used as an additional
input to F and H, and then provided as part of the public key. This
change appears to make the analysis of [BDM08] applicable, and it
would improve the resistance of these signature schemes against key
collision attacks, that is, scenarios in which an attacker
concurrently attacks many signatures made with many private keys.
8.1. Security of LDWM Checksum
To show the security of LDWM checksum, we consider the signature y of
a message with a private key x and let h = H(message) and
c = C(H(message)) (see Section 3.7). To attempt a forgery, an
attacker may try to change the values of h and c. Let h' and c'
denote the values used in the forgery attempt. If for some integer j
in the range 0 to (u-1), inclusive,
a' = coef(h', j, w),
a = coef(h, j, w), and
a' > a
then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j] by
iteratively applying function F to the j^th term of the signature an
additional (a' - a) times. However, as a result of the increased
number of hashing iterations, the checksum value c' will decrease
from its original value of c. Thus a valid signature's checksum will
have, for some number k in the range u to (p-1), inclusive,
b' = coef(c', k, w),
b = coef(c, k, w), and
b' < b
Due to the one-way property of F, the attacker cannot easily compute
F^b'(x[k]) from F^b(x[k]) = y[k].
8.2. Security Conjectures
LDWM and MTS signatures rely on a minimum of security conjectures.
In particular, their security does not rely on the computational
McGrew & Curcio Expires January 5, 2015 [Page 29]
Internet-Draft Hash-Based Signatures July 2014
difficulty of factoring composites with large prime factors (as does
RSA) or the difficulty of computing the discrete logarithm in a
finite field (as does DSA) or an elliptic curve group (as does
ECDSA). All of these signature schemes also rely on the security of
the hash function that they use, but with LDWM and MTS, the security
of the hash function is sufficient.
8.3. Post-Quantum Security
A post-quantum 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 whether or not it is feasible to
build such a machine.
The LDWM and Merkle signature systems are post-quantum secure if they
are used with an appropriate underlying hash function, in which the
size of m and n are double what they would be otherwise, in order to
protect against quantum square root attacks due to Grover's
algorithm. In contrast, the signature systems in wide use (RSA, DSA,
and ECDSA) are not post-quantum secure.
McGrew & Curcio Expires January 5, 2015 [Page 30]
Internet-Draft Hash-Based Signatures July 2014
9. Acknowledgements
Thanks are due to Chirag Shroff for constructive feedback, and to
Andreas Hulsing, Burt Kaliski, Eric Osterweil, Ahmed Kosba, and Russ
Housley for valuable detailed review.
McGrew & Curcio Expires January 5, 2015 [Page 31]
Internet-Draft Hash-Based Signatures July 2014
10. References
10.1. Normative References
[FIPS180] National Institute of Standards and Technology, "Secure
Hash Standard (SHS)", FIPS 180-4, March 2012.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an
IANA Considerations Section in RFCs", BCP 26, RFC 2434,
October 1998.
[RFC4506] Eisler, M., "XDR: External Data Representation Standard",
STD 67, RFC 4506, May 2006.
10.2. Informative References
[BDM08] Buchmann, J., Dahmen, E., and M. Szydlo, "Hash-based
Digital Signature Schemes", Technische Universitat
Darmstadt Technical Report https://
www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/
hashbasedcrypto.pdf, 2008.
[C:Dods05]
Dods, C., Smart, N., and M. Stam, "Hash Based Digital
Signature Schemes", Lecture Notes in Computer Science vol.
3796 Cryptography and Coding, 2005.
[C:Merkle87]
Merkle, R., "A Digital Signature Based on a Conventional
Encryption Function", Lecture Notes in Computer
Science crypto87vol, 1988.
[C:Merkle89a]
Merkle, R., "A Certified Digital Signature", Lecture Notes
in Computer Science crypto89vol, 1990.
[C:Merkle89b]
Merkle, R., "One Way Hash Functions and DES", Lecture
Notes in Computer Science crypto89vol, 1990.
[Merkle79]
Merkle, R., "Secrecy, Authentication, and Public Key
Systems", Stanford University Information Systems
Laboratory Technical Report 1979-1, 1979.
McGrew & Curcio Expires January 5, 2015 [Page 32]
Internet-Draft Hash-Based Signatures July 2014
Appendix A. LDWM Parameter Options
A table illustrating various combinations of n and w with the
associated values of u, v, ls, and p is provided in Table 4.
The parameters u, v, ls, and p are computed as follows:
u = ceil(8*n/w)
v = ceil((floor(lg((2^w - 1) * u)) + 1) / w)
ls = (number of bits in sum) - (v * w)
p = u + v
Here u and v represent the number of w-bit fields required to contain
the hash of the message and the checksum byte strings, respectively.
The "number of bits in sum" is defined according to Section 3.6. And
as the value of p is the number of w-bit elements of ( H(message) ||
C(H(message)) ), it is also equivalently the number of byte strings
that form the private key and the number of byte strings in the
signature.
McGrew & Curcio Expires January 5, 2015 [Page 33]
Internet-Draft Hash-Based Signatures July 2014
+---------+------------+-----------+-----------+-------+------------+
| Hash | Winternitz | w-bit | w-bit | Left | Total |
| Length | Parameter | Elements | Elements | Shift | Number of |
| in | (w) | in Hash | in | (ls) | w-bit |
| Bytes | | (u) | Checksum | | Elements |
| (n) | | | (v) | | (p) |
+---------+------------+-----------+-----------+-------+------------+
| 20 | 1 | 160 | 8 | 8 | 168 |
| | | | | | |
| 20 | 2 | 80 | 4 | 8 | 84 |
| | | | | | |
| 20 | 4 | 40 | 3 | 4 | 43 |
| | | | | | |
| 20 | 8 | 20 | 2 | 0 | 22 |
| | | | | | |
| 32 | 1 | 256 | 9 | 7 | 265 |
| | | | | | |
| 32 | 2 | 128 | 5 | 6 | 133 |
| | | | | | |
| 32 | 4 | 64 | 3 | 4 | 67 |
| | | | | | |
| 32 | 8 | 32 | 2 | 0 | 34 |
| | | | | | |
| 48 | 1 | 384 | 9 | 7 | 393 |
| | | | | | |
| 48 | 2 | 192 | 5 | 6 | 197 |
| | | | | | |
| 48 | 4 | 96 | 3 | 4 | 99 |
| | | | | | |
| 48 | 8 | 48 | 2 | 0 | 50 |
| | | | | | |
| 64 | 1 | 512 | 10 | 6 | 522 |
| | | | | | |
| 64 | 2 | 256 | 5 | 6 | 261 |
| | | | | | |
| 64 | 4 | 128 | 3 | 4 | 131 |
| | | | | | |
| 64 | 8 | 64 | 2 | 0 | 66 |
+---------+------------+-----------+-----------+-------+------------+
Table 4
McGrew & Curcio Expires January 5, 2015 [Page 34]
Internet-Draft Hash-Based Signatures July 2014
Appendix B. Example Data for Testing
As with all cryptosystems, implementations of LDWM signatures and
Merkle signatures need to be tested before they are used. This
section contains sample data generated from the signing and
verification operations of software that implements the algorithms
described in this document.
B.1. Parameters
The example contained in this section demonstrates the calculations
of LDWM_SHA256_M20_W4 using a Merkle Tree Signature of degree 4 and
height 2. This corresponds to the following parameter values:
+----+----+---+----+----+---+---+
| m | n | w | p | ls | k | h |
+----+----+---+----+----+---+---+
| 20 | 32 | 4 | 67 | 4 | 4 | 2 |
+----+----+---+----+----+---+---+
Table 5
The non-standard size of the Merkle tree (h = 2) has been selected
specifically for this example to reduce the amount of data presented.
B.2. Key Generation
The LDWM algorithm does not define a required method of key
generation. This is left to the implementer. The selected method,
however, must satisfy the requirement that the private keys of the
one-time signatures are uniformly random, independent, and
unpredicable. In addition, all LDWM key pairs must be generated in
advance in order to calculate the value of the Merkle public key.
For the test data presented here, a summary of the key generation
method is as follows:
1. MTS Private Key - Set mts_private_key to a pseudorandomly
generated n-byte value.
2. OTS Private Keys - Use the mts_private_key as a key derivation
key input to some key derivation function, thereby producing n^k
derived keys. Then use each derived key as an input to the same
function again to further derive p elements of n-bytes each.
This accomplishes the result of Algorithm 0 of Section 3.4 for
each leaf of the Merkle tree.
McGrew & Curcio Expires January 5, 2015 [Page 35]
Internet-Draft Hash-Based Signatures July 2014
3. OTS Public Keys - For each OTS private key, calculate the
corresponding OTS public key as in Algorithm 1 of Section 3.5.
4. MTS Public Key - Each OTS public key is the value of a leaf on
the Merkle tree. Calculate the MTS public key using the
pseudocode algorithm of Section 4.2 or some equivalent
implementation.
The above steps result in the following data values associated with
the first leaf of the Merkle tree, leaf 0.
+-------------------------------------------------------------------+
| MTS Private Key |
+-------------------------------------------------------------------+
| 0x0f677ff1b4cbf10baec89959f051f203 |
| 3371492da02f62dd61d6fbd1cee1bd14 |
+-------------------------------------------------------------------+
Table 6
+-----------------+-------------------------------------------------+
| Key Element | OTS Private Key 0 Element (x[i]) |
| Index (i) | |
+-----------------+-------------------------------------------------+
| 0 | 0xbfb757383fb08d324629115a84daf00b |
| | 188d5695303c83c184e1ec7a501c431f |
| | |
| 1 | 0x7ce628fb82003a2829aab708432787d0 |
| | fc735a29d671c7d790068b453dc8c913 |
| | |
| 2 | 0x8174929461329d15068a4645a34412bd |
| | 446d4c9e757463a7d5164efd50e05c93 |
| | |
| 3 | 0xf283f3480df668de4daa74bb0e4c5531 |
| | 5bc00f7d008bb6311e59a5bbca910fd7 |
| | |
| 4 | 0xe62708eaf9c13801622563780302a068 |
| | 0ba9d39c078daa5ebc3160e1d80a1ea7 |
| | |
| 5 | 0x1f002efad2bfb4275e376af7138129e3 |
| | 3e88cf7512ec1dcdc7df8d5270bc0fd7 |
| | |
| 6 | 0x8ed5a703e9200658d18bc4c05dd0ca8a |
| | 356448a26f3f4fe4e0418b52bd6750a2 |
| | |
| 7 | 0xc74e56d61450c5387e86ddad5a8121c8 |
| | 8b1bc463e64f248a1f1d91d950957726 |
| | |
McGrew & Curcio Expires January 5, 2015 [Page 36]
Internet-Draft Hash-Based Signatures July 2014
| 8 | 0x629f18b6a2a4ea65fff4cf758b57333f |
| | e1d34af05b1cd7763696899c9869595f |
| | |
| 9 | 0x1741c31fdbb4864712f6b17fadc05d45 |
| | 926c831c7a755b7d7af57ac316ba6c2a |
| | |
| 10 | 0xe59a7b81490c5d1333a9cdd48b9cb364 |
| | 56821517a3a13cb7a8ed381d4d5f3545 |
| | |
| 11 | 0x3ba97fe8b2967dd74c8b10f31fc5f527 |
| | a23b89c1266202a4d7c281e1f41fa020 |
| | |
| 12 | 0xa262a9287cc979aaa59225d75df51b82 |
| | 57b92e780d1ab14c4ac3ecdac58f1280 |
| | |
| 13 | 0x9dfe0af1a3d9064338d96cb8eae88baa |
| | 6a69265538873b4c17265fa9d573bcff |
| | |
| 14 | 0xde9c5c6a5c6a274eabe90ed2a8e6148c |
| | 720196d237a839aaf5868af8da4d0829 |
| | |
| 15 | 0x5de81ec17090a82cb722f616362d3808 |
| | 30f04841191e44f1f81b9880164b14cd |
| | |
| 16 | 0xc0d047000604105bad657d9fa2f9ef10 |
| | 1cfd9490f4668b700d738f2fa9e1d11a |
| | |
| 17 | 0xf45297ef310941e1e855f97968129bb1 |
| | 73379193919f7b0fee9c037ae507c2d2 |
| | |
| 18 | 0x46ef43a877f023e5e66bbcd4f06b839f |
| | 3bfb2b64de25cd67d1946b0711989129 |
| | |
| 19 | 0x46e2a599861bd9e8722ad1b55b8f0139 |
| | 305fcf8b6077d545d4488c4bcb652f29 |
| | |
| 20 | 0xe1ad4d2d296971e4b0b7a57de305779e |
| | 82319587b58d3ef4daeb08f630bd5684 |
| | |
| 21 | 0x7a07fa7aed97cb54ae420a0e6a58a153 |
| | 38110f7743cab8353371f8ca710a4409 |
| | |
| 22 | 0x40601f6c4b35362dd4948d5687b5cb6b |
| | 5ec8b2ec59c2f06fd50f8919ebeaae92 |
| | |
| 23 | 0xa061b0ba9f493c4991be5cd3a9d15360 |
| | a9eb94f6f7adc28dddf174074f3df3c4 |
| | |
McGrew & Curcio Expires January 5, 2015 [Page 37]
Internet-Draft Hash-Based Signatures July 2014
| 24 | 0xcf1546a814ff16099cebf1fe0db1ace5 |
| | 1c272fda9846fbb535815924b0077fa4 |
| | |
| 25 | 0xcbb06f13155ce4e56c85a32661c90142 |
| | 8b630a4c37ea5c7062156f07f6b3efff |
| | |
| 26 | 0x1181ee7fc03342415094e36191eb450a |
| | 11cdea9c6f6cdc34de79cee0ba5bf230 |
| | |
| 27 | 0xe9f1d429b343bb897881d2a19ef363cd |
| | 1ab4117cbaad54dc292b74b8af9f5cf2 |
| | |
| 28 | 0x87f34b2551ef542f579fa65535c5036f |
| | 80eb83be4c898266ffc531da2e1a9122 |
| | |
| 29 | 0x9b4b467852fe33a03a872572707342fd |
| | ddeae64841225186babf353fa2a0cd09 |
| | |
| 30 | 0x19d58cd240ab5c80be6ddf5f60d18159 |
| | 2dca2be40118c1fdd46e0f14dffbcc7d |
| | |
| 31 | 0x5c9ad386547ba82939e49c9c74a8eccf |
| | 1cea60aa327b5d2d0a66b1ca48912d6d |
| | |
| 32 | 0xf49083e502400ffae9273c6de92a301e |
| | 7bda1537cab085e5adfa9eb746e8eca9 |
| | |
| 33 | 0x4074e1812d69543ce3c1ce706f6e0b45 |
| | f5f26f4ef39b34caa709335fd71e8fc0 |
| | |
| 34 | 0x1256612b0ca8398e97b247ae564b74b1 |
| | 3839b3b1cf0a0dd8ba629a2c58355f84 |
| | |
| 35 | 0xbab3989f00fd2c327bbfb35a218cc3ce |
| | 49d6b34cbf8b6e8919e90c4eff400ca9 |
| | |
| 36 | 0x96b52a5d395a5615b73dae65586ac5c8 |
| | 7f9dd3b9b3f82dbf509b5881f0643fa8 |
| | |
| 37 | 0x5d05ca4c644e1c41ccdaedbd2415d4f0 |
| | 9b4a1b940b51fe823dff7617b8ee8304 |
| | |
| 38 | 0xd96aab95ef6248e235d91d0f23b64727 |
| | a6675adfc64efea72f6f8b4a47996c0d |
| | |
| 39 | 0xfd9c384d52d3ac27c4f4898fcc15e83a |
| | c182f97ea63f7d489283e2cc7e6ed180 |
| | |
McGrew & Curcio Expires January 5, 2015 [Page 38]
Internet-Draft Hash-Based Signatures July 2014
| 40 | 0xc86eaed6a9e3fbe5b262c1fa1f099f7c |
| | 35ece71d9e467fab7a371dbcf400b544 |
| | |
| 41 | 0xf462b3719a2ed8778155638ff814dbf4 |
| | 2b107bb5246ee3dd82abf97787e6a69e |
| | |
| 42 | 0x014670912e3eb74936ebb64168b447e4 |
| | 2522b57c2540ac4b49b9ae356c01eca6 |
| | |
| 43 | 0x2b411096e0ca16587830d3acd673e858 |
| | 863fedc4cea046587cba0556d2bf9884 |
| | |
| 44 | 0xa73917c74730582e8e1815b8a07b1896 |
| | 2ac05e500e045676be3f1495fcfa18ca |
| | |
| 45 | 0xa4ab61e6962fe39a255dbf8a46d25110 |
| | 0d127fab08db59512653607bda24302c |
| | |
| 46 | 0x9b910ca516413f376b9eba4b0d571b22 |
| | 253c2a9646131ac9a2af5f615f7322b8 |
| | |
| 47 | 0xfc1b4ce627c77ad35a21ea9ded2cce91 |
| | b3758a758224e35cf2918153a513d64c |
| | |
| 48 | 0xc1902d8e8c02d9442581d7e053a2798a |
| | a84d77a74b6e7f2cc5096d50646c890f |
| | |
| 49 | 0xb3f47e2e8e2dcdd890ea00934b9d8234 |
| | 830dbc4a30ac996b144f12b3e463c77f |
| | |
| 50 | 0x8188d1ecfc6ae6118911f2b9b3a6c7a1 |
| | e5f909aa8b5c0aab8c69f1a7d436c307 |
| | |
| 51 | 0xca42d985974c7b870bc76494604eff49 |
| | 2676c942c6cb7c75d4938805885dd054 |
| | |
| 52 | 0xbe58851ebe566057e1ee16b8c604a473 |
| | 4c373af622660b2a82357ac6effb4566 |
| | |
| 53 | 0xc22d493f7a5642fceba2404dbefa8f95 |
| | 6323fac87fac425f6de8d23c9e8b20ca |
| | |
| 54 | 0x1a76c1ffa467906173fd0245b0cd6639 |
| | e6013ca79c4ed92426ee69ff5beeac0b |
| | |
| 55 | 0xbc6c0cb7808f379af1b7b7327436ad65 |
| | c05458f2d0a6923c333e5129c4c99671 |
| | |
McGrew & Curcio Expires January 5, 2015 [Page 39]
Internet-Draft Hash-Based Signatures July 2014
| 56 | 0xfbb04488c3c088dc5e63d13e6a701036 |
| | 6109ca4c5f4b0a8d37780187e2e9930e |
| | |
| 57 | 0xaec10811569d4d72e3a1baf71a886b75 |
| | eba6dc07ed027af0b2beffa71f9b43c8 |
| | |
| 58 | 0xf5529be3b7a19212e8baa970d2420bf4 |
| | 123f678267f96c1c3ef26ab610cb0061 |
| | |
| 59 | 0x172ba1ba0b701eeafe00692d1eb90181 |
| | 8ccaefaeb8f799395da81711766d1f43 |
| | |
| 60 | 0xfe1f8c15825208f3a21346b894b3d94e |
| | 4f3aa29cbc194a7b2c8a810c4c509042 |
| | |
| 61 | 0x2e81c66cc914ea1b0fa5942fe9780d54 |
| | 8c0b330e3bf73f0cb0bda4bc9c9e6ff4 |
| | |
| 62 | 0xfc3453aec5cc19a6a4bda4bc25931604 |
| | 704bf4386cd65780c6e73214c1da85ba |
| | |
| 63 | 0x4e8000c587dc917888e7e3d817672c0a |
| | ef812788cc8579afa7e9b2e566309003 |
| | |
| 64 | 0xba667ca0e44a8601a0fde825d4d2cf1b |
| | b9cf467041e04af84c9d0cd9fd8dc784 |
| | |
| 65 | 0x4965db75f81c8a596680753ce70a94c6 |
| | 156253bb426947de1d7662dd7e05e9a8 |
| | |
| 66 | 0x2c23cc3e5ca37dec279c506101a3d8d9 |
| | f1e4f99b2a33741b59f8bddba7455419 |
+-----------------+-------------------------------------------------+
Table 7
Using the value of the OTS private key above, the corresponding
public key is given below. Intermediate values of the SHA256-20
function F^(2^w - 1)(x[i]) are provided in Table 13.
+-------------------------------------------------------------------+
| OTS Public Key 0 |
+-------------------------------------------------------------------+
| 0x2db55a72075fcfab5aedbef77bf6b371 |
| dfb489d6e61ad2884a248345e6910618 |
+-------------------------------------------------------------------+
Table 8
McGrew & Curcio Expires January 5, 2015 [Page 40]
Internet-Draft Hash-Based Signatures July 2014
Following the creation of all OTS public/private key pairs, the OTS
public keys in Table 14 are used to determine the MTS public key
below. Intermediate values of the interior nodes of the Merkle tree
are provided in Table 15.
+-------------------------------------------------------------------+
| MTS Public Key |
+-------------------------------------------------------------------+
| 0x6610803d9a3546fb0a7895f6a4a0cfed |
| 3a07d45e51d096e204b018e677453235 |
+-------------------------------------------------------------------+
Table 9
B.3. Signature Generation
In order to test signature generation, a text file containing the
content "Hello world!\n", where '\n' represents the ASCII line feed
character, was created and signed. A raw hex dump of the file
contents is shown in the table below.
+-------------------------------+-----------------------------------+
| Hexadecimal Byte Values | ASCII Representation |
| | ('.' is substituted for |
| | non-printing characters) |
+-------------------------------+-----------------------------------+
| 0x48 0x65 0x6c 0x6c 0x6f 0x20 | Hello world!. |
| 0x77 0x6f 0x72 0x6c 0x64 0x21 | |
| 0x0a | |
+-------------------------------+-----------------------------------+
Table 10
The SHA256 hash of the text file is provided below.
+-------------------------------------------------------------------+
| SHA256 Hash of Signed File (H("Hello world!\n")) |
+-------------------------------------------------------------------+
| 0x0ba904eae8773b70c75333db4de2f3ac |
| 45a8ad4ddba1b242f0b3cfc199391dd8 |
+-------------------------------------------------------------------+
Table 11
This value was subsequently used in Algorithm 3 of Section 3.7 to
create the one-time signature of the message. Algorithm 2 of
Section 3.6 was applied to calculate a checksum of 0x1cc. The
resulting signature is shown in the following table.
McGrew & Curcio Expires January 5, 2015 [Page 41]
Internet-Draft Hash-Based Signatures July 2014
+---------+------------+--------------------------------------------+
| OTS | Function | OTS Element (y[i] = F^a(x[i])) |
| Element | Iteration | |
| Index | Count | |
| (i) | (a = coef( | |
| | H(msg) || | |
| | C(H(msg)), | |
| | i, w )) | |
+---------+------------+--------------------------------------------+
| 0 | 0 | 0xbfb757383fb08d324629115a84daf00b188d5695 |
| | | |
| 1 | 11 | 0x4af079e885ddfd3245f29778d265e868a3bfeaa4 |
| | | |
| 2 | 10 | 0xfbad1928bfc57b22bcd949192452293d07d6b9ad |
| | | |
| 3 | 9 | 0xb98063e184b4cb949a51e1bb76d99d4249c0b448 |
| | | |
| 4 | 0 | 0xe62708eaf9c13801622563780302a0680ba9d39c |
| | | |
| 5 | 4 | 0x39343cba3ffa6d75074ce89831b3f3436108318c |
| | | |
| 6 | 14 | 0xfe08aa73607aec5664188a9dacdc34a295588c9a |
| | | |
| 7 | 10 | 0xd3346382119552d1ceb92a78597a00c956372bf0 |
| | | |
| 8 | 14 | 0xf1dd245ec587c0a7a1b754cc327b27c839a6e46a |
| | | |
| 9 | 8 | 0xa5f158adc1decaf0c1edc1a3a5d8958d726627b5 |
| | | |
| 10 | 7 | 0x06d2990f62f22f0c943a418473678e3ffdbff482 |
| | | |
| 11 | 7 | 0xf3390b8d6e5229ae9c5d4c3f45e10455d8241a49 |
| | | |
| 12 | 3 | 0x22dd5f9d3c89180caa0f695203d8cf90f3c359be |
| | | |
| 13 | 11 | 0x67999c4043f95de5f07d82b741347a3eb6ac0c25 |
| | | |
| 14 | 7 | 0xc4ffe472d48adeb37c7360da70711462013b7a4e |
| | | |
| 15 | 0 | 0x5de81ec17090a82cb722f616362d380830f04841 |
| | | |
| 16 | 12 | 0x2f892c824af65cc749f912a36dfa8ade2e4c3fd1 |
| | | |
| 17 | 7 | 0xb644393e8030924403b594fb5cacd8b2d28862e2 |
| | | |
| 18 | 5 | 0x31b8d2908911dbbf5ba1f479a854808945d9e948 |
| | | |
| 19 | 3 | 0xa9a02269d24eb8fed6fb86101cbd0d8977219fb1 |
McGrew & Curcio Expires January 5, 2015 [Page 42]
Internet-Draft Hash-Based Signatures July 2014
| 20 | 3 | 0xe4aae6e6a9fe1b0d5099513f170c111dee95714d |
| | | |
| 21 | 3 | 0xd79c16e7f2d4dd790e28bab0d562298c864e31e9 |
| | | |
| 22 | 13 | 0xc29678f0bb4744597e04156f532646c98a0b42e8 |
| | | |
| 23 | 11 | 0x57b31d75743ff0f9bcf2db39d9b6224110b8d27b |
| | | |
| 24 | 4 | 0x0a336d93aac081a2d849c612368b8cbb2fa9563a |
| | | |
| 25 | 13 | 0x917be0c94770a7bb12713a4bae801fb3c1c43002 |
| | | |
| 26 | 14 | 0x91586feaadcf691b6cb07c16c8a2ed0884666e84 |
| | | |
| 27 | 2 | 0xdd4e4b720fb2517c4bc6f91ccb8725118e5770c6 |
| | | |
| 28 | 15 | 0x491f6ec665f54c4b3cffaa02ec594d31e6e26c0e |
| | | |
| 29 | 3 | 0x4f5a082c9d9c9714701de0bf426e9f893484618c |
| | | |
| 30 | 10 | 0x11f7017313f0c9549c5d415a8abc25243028514d |
| | | |
| 31 | 12 | 0x6839a994fccb9cb76241d809146906a3d13f89f1 |
| | | |
| 32 | 4 | 0x71cd1d9163d7cd563936837c61d97bb1a5337cc0 |
| | | |
| 33 | 5 | 0x77c9034ffc0f9219841aa8e1edbfb62017ef9fd1 |
| | | |
| 34 | 10 | 0xad9f6034017d35c338ac35778dd6c4c1abe4472a |
| | | |
| 35 | 8 | 0x4a1c396b22e4f5cc2428045b36d13737c4007515 |
| | | |
| 36 | 10 | 0x98cb57b779c5fd3f361cd5debc243303ae5baefd |
| | | |
| 37 | 13 | 0x29857298f274d6bf595eadc89e5464ccf9608a6c |
| | | |
| 38 | 4 | 0x95e35a26815a3ae9ad84a24464b174a29364da18 |
| | | |
| 39 | 13 | 0x4afeb3b95b5b333759c0acdd96ce3f26314bb22b |
| | | |
| 40 | 13 | 0x325a37ee5e349b22b13b54b24be5145344e7b8f3 |
| | | |
| 41 | 11 | 0x4f772c93f56fd6958ce135f02847996c67e1f2ef |
| | | |
| 42 | 10 | 0xd4f6d91c577594060be328b013c9e9b0e8a2e5d8 |
| | | |
| 43 | 1 | 0x717e1a81c325cdccacb6e9fd9e92dd3e1bb84ae8 |
| | | |
McGrew & Curcio Expires January 5, 2015 [Page 43]
Internet-Draft Hash-Based Signatures July 2014
| 44 | 11 | 0x1dd363724ec66c090a1228dfa1cd3d9cc806f346 |
| | | |
| 45 | 2 | 0x64b4110476dd0beea78714c5ab71278818792cfa |
| | | |
| 46 | 4 | 0xe22290e740056a144af50f0b10962b5bcc18fc82 |
| | | |
| 47 | 2 | 0x34fd87046a183f4732a52bb7805ce207eebdafc5 |
| | | |
| 48 | 15 | 0xbd2fdc5e4e8d0ed7c48c1bad9c2f7793fc2c9303 |
| | | |
| 49 | 0 | 0xb3f47e2e8e2dcdd890ea00934b9d8234830dbc4a |
| | | |
| 50 | 11 | 0xcd29719c56cdb507030e6132132179e5807e1d3b |
| | | |
| 51 | 3 | 0xf9edb9b301916217de0d746a0542316bebe9e806 |
| | | |
| 52 | 12 | 0x7a3801cbfe0cafed863d81210c1ec721eede49e5 |
| | | |
| 53 | 15 | 0x5caba3ec960efa210f5f3e1c22c567ca475ef3ec |
| | | |
| 54 | 12 | 0xf911b5d148e1b03fe6983c53411f76ea78772379 |
| | | |
| 55 | 1 | 0x06da2baa75c6ef752bf59f3812fa042ff8181209 |
| | | |
| 56 | 9 | 0x2b29f5aa2f34af51a78a5fac586004f749c6e6dc |
| | | |
| 57 | 9 | 0x55e033ababac0845cc9142e24f9ef0a641c51cbe |
| | | |
| 58 | 3 | 0xb62d207bb700071fba8a68312ca204ce4d994c33 |
| | | |
| 59 | 9 | 0x551d5c00fad905bdb99c4f70ec7590a10d3ff8ca |
| | | |
| 60 | 1 | 0x0d03b1845b5f8838d735142f185f9cf8f8d2db6c |
| | | |
| 61 | 13 | 0x3b5d9e49e7ede41cd9aa5a09f72a0384fd4ff511 |
| | | |
| 62 | 13 | 0xa766b0278d14a9b7d32bf0307c0737a8ecf82ab1 |
| | | |
| 63 | 8 | 0xca85296f354e6e3d2a96ab497c01e5ccd4530cf1 |
| | | |
| 64 | 1 | 0x7bb29db7dd8aaaf1cd11487cea0d13730edb1df3 |
| | | |
| 65 | 12 | 0x547ef341b3cf3208753bb1b62d85a4e3fc2cffe0 |
| | | |
| 66 | 12 | 0xb890e1a99da4b2e0a9dde42f82f92d0946327cee |
+---------+------------+--------------------------------------------+
Table 12
McGrew & Curcio Expires January 5, 2015 [Page 44]
Internet-Draft Hash-Based Signatures July 2014
Finally, based on the fact that the message is the first to be signed
by the Merkle tree (i.e. using leaf node 0), the values of the leaf
and interior nodes that compose the authentication path from leaf to
root are determined as described in Section 4.3. These values are
marked with an asterisk ('*') in Table 14 and Table 15.
B.4. Signature Verification
The signature verification step was provided the following items:
1. OTS = (y[0] || y[1] || ... || y[p-1]) - from Table 12.
2. Authentication Path = concatenation of (k-1)*h Merkle tree node
values - from Table 14 and Table 15.
3. Message Number = leaf number of Merkle tree.
4. Merkle Public Key = root of Merkle tree - from Table 9.
Using Algorithm 4 of Section 3.8 as a start, the potential OTS public
key was calculated from the value of the OTS. Since the actual OTS
public key was not provided to the verifier, the calculated key was
checked for validity using the pseudocode algorithm of Section 4.4
and the provided values of the Authentication Path and Message
Number. Since the message was valid, the calculated value of the
root matched the Merkle public key. Otherwise, verification would
have failed.
B.5. Intermediate Calculation Values
+----------------------+--------------------------------------------+
| Key Element Index | SHA256-20 Result for w = 4 (F^15(x[i])) |
| (i) | |
+----------------------+--------------------------------------------+
| 0 | 0x6eff4b0c224874ecc4e4f4500da53dbe2a030e45 |
| | |
| 1 | 0x58ac2c6c451c7779d67efefdb12e5c3d85475a94 |
| | |
| 2 | 0xb1f3e42e29c710d69268eed1bbdb7f5a500b7937 |
| | |
| 3 | 0x51d28e573aac2b84d659abb961c32c465e911b55 |
| | |
| 4 | 0xa0ed62bccac5888f5000ca6a01e5ffefd442a1c6 |
| | |
| 5 | 0x44da9e145666322422c1e2b5e21627e05aeb4367 |
| | |
| 6 | 0x04e7ff9213c2655f28364f659c35d3086d7414e1 |
| | |
McGrew & Curcio Expires January 5, 2015 [Page 45]
Internet-Draft Hash-Based Signatures July 2014
| 7 | 0x414cdb3215408b9722a02577eeb71f9e016e4251 |
| | |
| 8 | 0xa3ab06b90a2b20f631175daa9454365a4f408e9e |
| | |
| 9 | 0xe38acfd3c0a03faa82a0f4aeac1a7c04983fad25 |
| | |
| 10 | 0xd95a289094ccce8ad9ff1d5f9e38297f9bb306ff |
| | |
| 11 | 0x593d148b22e33c32f18b66340bdaffceb3ad1a55 |
| | |
| 12 | 0x16b53fbea11dc7ab70c8336ec3c23881ae5d51bf |
| | |
| 13 | 0xa639ca0cf871188cadd0020832c4f06e6ebd5f98 |
| | |
| 14 | 0xe3ab3e0c5ad79d6c8c2a7e9a79856d4380941fe0 |
| | |
| 15 | 0x8368c2933dabcde69c373867a9bf2dc78df97bea |
| | |
| 16 | 0xe3609fca11545da156a7779ae565b1e3c87902c0 |
| | |
| 17 | 0xab029e62c7011772dc0589d79fad01aacf8d2177 |
| | |
| 18 | 0xa8310f1c27c1aa481192de07d4397b8c4716e25f |
| | |
| 19 | 0xdbdbb14dbd9a5f03c1849af24b69b9e3f80faca2 |
| | |
| 20 | 0x1a17399d555dec07d3d4f6d54b2b87d2bcaa398b |
| | |
| 21 | 0xf81c66cc522bfb203232e44d0003ed65d2462867 |
| | |
| 22 | 0x202a625b8c5f22de6ea081af6da077cf5c63202f |
| | |
| 23 | 0x2e080f3591f5ff3d5de39c2698846cc107a09816 |
| | |
| 24 | 0xa1d9c78c22f9810e3b7db2d59ad9f5fdd259f4d4 |
| | |
| 25 | 0x658eeb85ebe0f4542c4d32dced2d7226929266b2 |
| | |
| 26 | 0x67fae1a784f919577afc091504d82d31b4ba9fc7 |
| | |
| 27 | 0xfc39fb43677fb2d433a6292f19c6e7320279655a |
| | |
| 28 | 0x491f6ec665f54c4b3cffaa02ec594d31e6e26c0e |
| | |
| 29 | 0x17cec813a5781409b11d2e4a85f62301c2fd8873 |
| | |
| 30 | 0xc578eb105454d900c053eb55833db607aa5757e0 |
| | |
McGrew & Curcio Expires January 5, 2015 [Page 46]
Internet-Draft Hash-Based Signatures July 2014
| 31 | 0xaed094323290a41fd4b546919620e2f6b23916c8 |
| | |
| 32 | 0x192b5a87b5124dc287e06cdd4ec7c0c11f67dda6 |
| | |
| 33 | 0x4e9e2bdc1b0204d1ceeb68fb4159e752c40b9608 |
| | |
| 34 | 0xf34c57ad9ce45d67fd32dc2737e6263bcc5cc61f |
| | |
| 35 | 0xf73bd27d376186310f83cc66e72060aeaccde371 |
| | |
| 36 | 0xeea482511acd8be783e9be42b48799653b222db4 |
| | |
| 37 | 0xa2e53196fec8676065b8f32b3e8498e66a4af3cf |
| | |
| 38 | 0x670c98185157e1b28d38f7dafb00796b434c8316 |
| | |
| 39 | 0x441afbb265b93595389aaa66325de792f343f209 |
| | |
| 40 | 0x7b6c50d20b5edc0bc90eb4b289770514cbc8d547 |
| | |
| 41 | 0xfde6e862a7ba3534893a3e630e209a24be590b1e |
| | |
| 42 | 0xc59611200c20b2e73dfb24c84cedf4792d6daf10 |
| | |
| 43 | 0x66e3527bee88373d18f91b230b53b569361f0a15 |
| | |
| 44 | 0xd0fd79c7116198e689275fec9b4c46f4aac73293 |
| | |
| 45 | 0x65f07406ad4241e7cf4174c5f284267292cdbc32 |
| | |
| 46 | 0x7b1b5535d45f46542e2b876245b66ea83cde3d8f |
| | |
| 47 | 0x7a11620934eb0eb17e10e4a8bbd52aa4b020da0e |
| | |
| 48 | 0xbd2fdc5e4e8d0ed7c48c1bad9c2f7793fc2c9303 |
| | |
| 49 | 0x00432602437252a0622a30676dbaaef3023328b9 |
| | |
| 50 | 0x09a9c4b25034466a5acd7ff681af1c27e8f97577 |
| | |
| 51 | 0x4b31481d52aa5e1a261064bbd87ea46479a6be23 |
| | |
| 52 | 0xaca2ad4aa1264618ab633bf11cbca3cc8fa43091 |
| | |
| 53 | 0x5caba3ec960efa210f5f3e1c22c567ca475ef3ec |
| | |
| 54 | 0x353e3ffcedfd9500141921cf2aebc2e111364dad |
| | |
McGrew & Curcio Expires January 5, 2015 [Page 47]
Internet-Draft Hash-Based Signatures July 2014
| 55 | 0xe1c498c32169c869174ccf2f1e71e7202f45fba7 |
| | |
| 56 | 0x5b8519a40d4305813936c7c00a96f5b4ceb603f1 |
| | |
| 57 | 0x3b942ae6a6bd328d08804ade771a0775bb3ff8f8 |
| | |
| 58 | 0x6f3be60ee1c34372599b8d634be72e168453bf10 |
| | |
| 59 | 0xf700c70bac24db0aab1257940661f5b57da6e817 |
| | |
| 60 | 0x85ccf60624b13663a290fa808c6bbecaf89523cd |
| | |
| 61 | 0xd049be55ab703c44f42167d5d9e939c830df960f |
| | |
| 62 | 0xd27a178ccc3b364c7e03d2266093a0d1dfdd9d51 |
| | |
| 63 | 0xd73c53fdddbe196b9ab56fcc5c9a4a57ad868cd1 |
| | |
| 64 | 0xb59a70a7372f0c121fa71727baaf6588eccec400 |
| | |
| 65 | 0x9b5bf379f989f9a499799c12a3202db58b084eed |
| | |
| 66 | 0xccabf40f3c1dacf114b5e5f98a73103b4c1f9b55 |
+----------------------+--------------------------------------------+
Table 13
McGrew & Curcio Expires January 5, 2015 [Page 48]
Internet-Draft Hash-Based Signatures July 2014
+-----------+------------------------------------+------------------+
| MTS Leaf | OTS Public Key | Member of |
| (Level 3) | (H(x[0] || x[1] || ... || x[p-1])) | Authentication |
| Node | | Path of |
| Number | | Message 0 |
+-----------+------------------------------------+------------------+
| 0 | 0x2db55a72075fcfab5aedbef77bf6b371 | |
| | dfb489d6e61ad2884a248345e6910618 | |
| | | |
| 1 | 0x8c6c6a1215bfe7fda10b7754e73cd984 | * |
| | a64823b1ab9d5f50feda6b151c0fee6d | |
| | | |
| 2 | 0xc1fb91de68b3059c273e53596108ec7c | * |
| | f39923757597fe86439e91ce1c25fc84 | |
| | | |
| 3 | 0x1b511189baee50251335695b74d67c40 | * |
| | 5a04eddaa79158a9090cc7c3eb204cbf | |
| | | |
| 4 | 0xf3bcf088ccf9d00338b6c87e8f822da6 | |
| | 8ec471f88d1561193b3c017d20b3c971 | |
| | | |
| 5 | 0x40584c059e6cc72fb61f7bd1b9c28e73 | |
| | c689551e6e7de6b0b9b730fab9237531 | |
| | | |
| 6 | 0x1b1d09de1ca16ca890036e018d7e73de | |
| | b39b07de80c19dcc5e55a699f021d880 | |
| | | |
| 7 | 0x83a82632acaac5418716f4f357f5007f | |
| | 719d604525dbe1831c09a2ead9400a52 | |
| | | |
| 8 | 0xccb8b2a1d60f731b5f51910eb427e211 | |
| | 96090d5cd2a077f33968b425301e3fbd | |
| | | |
| 9 | 0x616767ebf3c1f3ec662d8c57c630c6ae | |
| | b31853fd40a18c3d831f5490610c1f16 | |
| | | |
| 10 | 0x5a4b3e157b66327c75d7f01304d188e2 | |
| | cecd1b6168240c11a01775d581b01fb6 | |
| | | |
| 11 | 0xf25744b8a1c2184ba38521801bf4727c | |
| | 407b85eb5aef8884d8fbb1c12e2f6108 | |
| | | |
| 12 | 0xaf8189f51874999162890f72e0ef25e6 | |
| | f76b4ab94dc53569bdd66507f5ab0d8e | |
| | | |
| 13 | 0x96251e396756686645f35cd059da329f | |
| | 7083838d56c9ccacebbaf8486af18844 | |
| | | |
McGrew & Curcio Expires January 5, 2015 [Page 49]
Internet-Draft Hash-Based Signatures July 2014
| 14 | 0x773d5206e40065d3553c3c2ed2500122 | |
| | e3ee6fd2c91f35a57f084dc839aab1fc | |
| | | |
| 15 | 0xcda7fae67ce2c3ed29ce426fdcd3f2a8 | |
| | eb699e47a67a52f1c94e89726ffe97fa | |
+-----------+------------------------------------+------------------+
Table 14
+------------+------------------------------------+-----------------+
| MTS | Node Value | Member of |
| Interior | (H(child_0 || child_1 || ... || | Authentication |
| (Level 2) | child_k-1)) | Path of |
| Node | | Message 0 |
| Number | | |
+------------+------------------------------------+-----------------+
| 0 | 0xb6a310deb55ed48004133ece2aebb25e | |
| | d74defb77ebd8d63c79a42b5b4191b0c | |
| | | |
| 1 | 0x71a0c8b767ade2c97ebac069383e4dfb | * |
| | a1c06d5fd3f69a775711ea6470747664 | |
| | | |
| 2 | 0x91109fa97662dc88ae63037391ac2650 | * |
| | f6c664ac2448b54800a1df748953af31 | |
| | | |
| 3 | 0xd277fb8c89689525f90de567068d6c93 | * |
| | 565df3588b97223276ef8e9495468996 | |
+------------+------------------------------------+-----------------+
Table 15
McGrew & Curcio Expires January 5, 2015 [Page 50]
Internet-Draft Hash-Based Signatures July 2014
Authors' Addresses
David McGrew
Cisco Systems
13600 Dulles Technology Drive
Herndon, VA 20171
USA
Email: mcgrew@cisco.com
Michael Curcio
Cisco Systems
7025-2 Kit Creek Road
Research Triangle Park, NC 27709-4987
USA
Email: micurcio@cisco.com
McGrew & Curcio Expires January 5, 2015 [Page 51]