a then 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 this action, the checksum will decrease, and 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 have a minimum of security conjectures. In particular, their security does not rely on the computational difficulty of factoring composites with large prime factors (as does McGrew & Curcio Expires August 26, 2013 [Page 26] Internet-Draft Hash-Based Signatures February 2013 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 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 August 26, 2013 [Page 27] Internet-Draft Hash-Based Signatures February 2013 9. Acknowledgements Thanks are due to Chirag Shroff for constructive feedback. McGrew & Curcio Expires August 26, 2013 [Page 28] Internet-Draft Hash-Based Signatures February 2013 10. References 10.1. Normative References [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 [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 August 26, 2013 [Page 29] Internet-Draft Hash-Based Signatures February 2013 Appendix A. LDWM Parameter Options A table illustrating various combinations of n, w, p, and ls is provided in Table 4. The parameters p and ls are computed as follows: u = ceil(8*n/w) v = ceil(floor(lg(u)) / w) + 1 p = u + v ls = (number of bits in sum) - (v * w) Here u and v represent the number of w-bit fields required to contain the hash of the message message and the checksum byte strings, respectively. For a further explanation of the values of v and sum, see Section 3.6. McGrew & Curcio Expires August 26, 2013 [Page 30] Internet-Draft Hash-Based Signatures February 2013 +------------+--------------+--------------+----------+-------------+ | Hash | Winternitz | w-bit | Left | Number of | | Length in | Parameter | Elements in | Shift | Elements | | Bytes (n) | (w) | Checksum | (ls) | (p) | +------------+--------------+--------------+----------+-------------+ | 20 | 1 | 8 | 8 | 168 | | | | | | | | 20 | 2 | 4 | 8 | 84 | | | | | | | | 20 | 4 | 3 | 4 | 43 | | | | | | | | 20 | 8 | 2 | 0 | 22 | | | | | | | | 32 | 1 | 9 | 7 | 265 | | | | | | | | 32 | 2 | 5 | 6 | 133 | | | | | | | | 32 | 4 | 3 | 4 | 67 | | | | | | | | 32 | 8 | 2 | 0 | 34 | | | | | | | | 48 | 1 | 9 | 7 | 393 | | | | | | | | 48 | 2 | 5 | 6 | 197 | | | | | | | | 48 | 4 | 3 | 4 | 99 | | | | | | | | 48 | 8 | 2 | 0 | 50 | | | | | | | | 64 | 1 | 10 | 6 | 522 | | | | | | | | 64 | 2 | 5 | 6 | 261 | | | | | | | | 64 | 4 | 3 | 4 | 131 | | | | | | | | 64 | 8 | 2 | 0 | 66 | +------------+--------------+--------------+----------+-------------+ Table 4 McGrew & Curcio Expires August 26, 2013 [Page 31] Internet-Draft Hash-Based Signatures February 2013 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 | l | 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 public/private key pairs of the one-time signatures are unique. 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 August 26, 2013 [Page 32] Internet-Draft Hash-Based Signatures February 2013 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. 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 August 26, 2013 [Page 33] Internet-Draft Hash-Based Signatures February 2013 | 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 August 26, 2013 [Page 34] Internet-Draft Hash-Based Signatures February 2013 | 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 August 26, 2013 [Page 35] Internet-Draft Hash-Based Signatures February 2013 | 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 August 26, 2013 [Page 36] Internet-Draft Hash-Based Signatures February 2013 | 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 SHA-256-20 function F^(2^w - 1)(x[i]) are provided in Table 13. +-------------------------------------------------------------------+ | OTS Public Key 0 | +-------------------------------------------------------------------+ | 0x2db55a72075fcfab5aedbef77bf6b371 | | dfb489d6e61ad2884a248345e6910618 | +-------------------------------------------------------------------+ Table 8 McGrew & Curcio Expires August 26, 2013 [Page 37] Internet-Draft Hash-Based Signatures February 2013 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")) | +-------------------------------------------------------------------+ | 0x0ba904eae8773b70c75333db4de2f3ac4 | | 5a8ad4ddba1b242f0b3cfc199391dd81c | +-------------------------------------------------------------------+ 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 August 26, 2013 [Page 38] Internet-Draft Hash-Based Signatures February 2013 +---------+------------+--------------------------------------------+ | 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 August 26, 2013 [Page 39] Internet-Draft Hash-Based Signatures February 2013 | 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 August 26, 2013 [Page 40] Internet-Draft Hash-Based Signatures February 2013 | 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 August 26, 2013 [Page 41] Internet-Draft Hash-Based Signatures February 2013 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 August 26, 2013 [Page 42] Internet-Draft Hash-Based Signatures February 2013 | 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 August 26, 2013 [Page 43] Internet-Draft Hash-Based Signatures February 2013 | 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 August 26, 2013 [Page 44] Internet-Draft Hash-Based Signatures February 2013 | 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 August 26, 2013 [Page 45] Internet-Draft Hash-Based Signatures February 2013 +-----------+------------------------------------+------------------+ | MTS Leaf | OTS Public Key | Member of | | (Level 2) | (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 August 26, 2013 [Page 46] Internet-Draft Hash-Based Signatures February 2013 | 14 | 0x773d5206e40065d3553c3c2ed2500122 | | | | e3ee6fd2c91f35a57f084dc839aab1fc | | | | | | | 15 | 0xcda7fae67ce2c3ed29ce426fdcd3f2a8 | | | | eb699e47a67a52f1c94e89726ffe97fa | | +-----------+------------------------------------+------------------+ Table 14 +------------+------------------------------------+-----------------+ | MTS | Node Value | Member of | | Interior | (H(child_0 || child_1 || ... || | Authentication | | (Level 1) | 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 August 26, 2013 [Page 47] Internet-Draft Hash-Based Signatures February 2013 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 August 26, 2013 [Page 48]