/* * hashsig.c * --------- * Naive implementation of draft-mcgrew-hash-sigs-10.txt * * Copyright (c) 2018, NORDUnet A/S All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: * - Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * - Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * - Neither the name of the NORDUnet nor the names of its contributors may * be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ /* * This is a naive implementation of McGrew et al's Hash-Based Signature * scheme, which hews as closely as possible to the text of the draft, * without any regard for performance (or security - keys are stored * unencrypted in the local file system). * * For simplicity, this implemention restricts all LMS keys in the HSS scheme * to use the same LMS type and LM-OTS type. */ #include /* htonl and friends */ #include #include #include "hal.h" #include "hashsig.h" #include "xdr_internal.h" typedef struct { uint8_t bytes[32]; } bytestring32; typedef struct { uint8_t bytes[16]; } bytestring16; #define check(op) do { hal_error_t _err = (op); if (_err != HAL_OK) return _err; } while (0) #define checkssl(op) do { if ((op) == 0) { return HAL_ERROR_IMPOSSIBLE; } } while (0) /* ---------------------------------------------------------------- */ /* * XDR extensions */ static inline hal_error_t hal_xdr_encode_bytestring32(uint8_t **outbuf, const uint8_t * const limit, const bytestring32 * const value) { return hal_xdr_encode_fixed_opaque(outbuf, limit, (const uint8_t *)value, sizeof(bytestring32)); } static inline hal_error_t hal_xdr_decode_bytestring32(const uint8_t ** const inbuf, const uint8_t * const limit, bytestring32 *value) { return hal_xdr_decode_fixed_opaque(inbuf, limit, (uint8_t *)value, sizeof(bytestring32)); } static inline hal_error_t hal_xdr_decode_bytestring32_ptr(const uint8_t ** const inbuf, const uint8_t * const limit, bytestring32 **value) { return hal_xdr_decode_fixed_opaque_ptr(inbuf, limit, (const uint8_t ** const)value, sizeof(bytestring32)); } static inline hal_error_t hal_xdr_encode_bytestring16(uint8_t **outbuf, const uint8_t * const limit, const bytestring16 *value) { return hal_xdr_encode_fixed_opaque(outbuf, limit, (const uint8_t *)value, sizeof(bytestring16)); } static inline hal_error_t hal_xdr_decode_bytestring16(const uint8_t ** const inbuf, const uint8_t * const limit, bytestring16 *value) { return hal_xdr_decode_fixed_opaque(inbuf, limit, (uint8_t *)value, sizeof(bytestring16)); } static inline hal_error_t hal_xdr_decode_bytestring16_ptr(const uint8_t ** const inbuf, const uint8_t * const limit, bytestring16 **value) { return hal_xdr_decode_fixed_opaque_ptr(inbuf, limit, (const uint8_t ** const)value, sizeof(bytestring16)); } /* ---------------------------------------------------------------- */ // 3.1. Data Types #define u32str(X) htonl(X) #define u16str(X) htons(X) #define u8str(X) (X & 0xff) // 3.1.3. Strings of w-bit elements static uint8_t coef(const uint8_t * const S, const size_t i, size_t w) { switch (w) { case 1: return (S[i/8] >> (7 - (i % 8))) & 0x01; case 2: return (S[i/4] >> (6 - (2 * (i % 4)))) & 0x03; case 4: return (S[i/2] >> (4 - (4 * (i % 2)))) & 0x0f; case 8: return S[i]; default: return 0; } } // 3.2. Security string #define D_PBLC 0x8080 #define D_MESG 0x8181 #define D_LEAF 0x8282 #define D_INTR 0x8383 /* ---------------------------------------------------------------- */ // 4. LM-OTS One-Time Signatures // 4.2. Parameter Sets static inline size_t lmots_type_to_n(const lmots_algorithm_t lmots_type) { switch (lmots_type) { case lmots_sha256_n32_w1: case lmots_sha256_n32_w2: case lmots_sha256_n32_w4: case lmots_sha256_n32_w8: return 32; default: return 0; } } static inline size_t lmots_type_to_w(const lmots_algorithm_t lmots_type) { switch (lmots_type) { case lmots_sha256_n32_w1: return 1; case lmots_sha256_n32_w2: return 2; case lmots_sha256_n32_w4: return 4; case lmots_sha256_n32_w8: return 8; default: return 0; } } static inline size_t lmots_type_to_p(const lmots_algorithm_t lmots_type) { switch (lmots_type) { case lmots_sha256_n32_w1: return 265; case lmots_sha256_n32_w2: return 133; case lmots_sha256_n32_w4: return 67; case lmots_sha256_n32_w8: return 34; default: return 0; } } static inline size_t lmots_type_to_ls(const lmots_algorithm_t lmots_type) { switch (lmots_type) { case lmots_sha256_n32_w1: return 7; case lmots_sha256_n32_w2: return 6; case lmots_sha256_n32_w4: return 4; case lmots_sha256_n32_w8: return 0; default: return 0; } } // 4.3. Private Key static inline size_t lmots_private_key_len(const lmots_algorithm_t lmots_type) { /* u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1] */ return 2 * sizeof(uint32_t) + sizeof(bytestring16) + lmots_type_to_p(lmots_type) * lmots_type_to_n(lmots_type); } static hal_error_t lmots_generate_private_key(const lmots_algorithm_t lmots_type, const bytestring16 * const I, const size_t q, uint8_t *key, size_t *key_len, const size_t key_max) { if (I == NULL || key == NULL|| key_max < lmots_private_key_len(lmots_type)) return HAL_ERROR_BAD_ARGUMENTS; // Algorithm 0: Generating a Private Key // 1. retrieve the value p from the type, and the value I the 16 byte // identifier of the LMS public/private keypair that this LM-OTS private // key will be used with // 2. set type to the typecode of the algorithm // 3. set n and p according to the typecode and Table 1 size_t n = lmots_type_to_n(lmots_type); size_t p = lmots_type_to_p(lmots_type); // 4. compute the array x as follows: // for ( i = 0; i < p; i = i + 1 ) { // set x[i] to a uniformly random n-byte string // } bytestring32 x[p]; for (size_t i = 0; i < p; ++i) checkssl(RAND_bytes((unsigned char *)&x[i], n)); // 5. return u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1] uint8_t *keyptr = key; const uint8_t * const keylim = key + key_max; check(hal_xdr_encode_int(&keyptr, keylim, lmots_type)); check(hal_xdr_encode_bytestring16(&keyptr, keylim, I)); check(hal_xdr_encode_int(&keyptr, keylim, q)); for (size_t i = 0; i < p; ++i) check(hal_xdr_encode_bytestring32(&keyptr, keylim, &x[i])); if (key_len != NULL) *key_len = keyptr - key; return HAL_OK; } // 4.4. Public Key static inline size_t lmots_public_key_len(const lmots_algorithm_t lmots_type) { /* u32str(type) || I || u32str(q) || K */ return ((2 * sizeof(uint32_t)) + sizeof(bytestring16) + lmots_type_to_n(lmots_type)); } static hal_error_t lmots_generate_public_key(const uint8_t * const key, const size_t key_len, uint8_t *pub, size_t *pub_len, const size_t pub_max) { if (key == NULL || pub == NULL) return HAL_ERROR_BAD_ARGUMENTS; // Algorithm 1: Generating a One Time Signature Public Key From a // Private Key // // 1. set type to the typecode of the algorithm const uint8_t *keyptr = key; const uint8_t * const keylim = key + key_len; lmots_algorithm_t lmots_type; check(hal_xdr_decode_int(&keyptr, keylim, &lmots_type)); /* private key format * u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1] */ // 2. set the integers n, p, and w according to the typecode and Table 1 /* XXX n is not used here */ size_t p = lmots_type_to_p(lmots_type); size_t w = lmots_type_to_w(lmots_type); // 3. determine x, I and q from the private key bytestring16 I; check(hal_xdr_decode_bytestring16(&keyptr, keylim, &I)); uint32_t q; check(hal_xdr_decode_int(&keyptr, keylim, &q)); bytestring32 x[p]; for (size_t i = 0; i < p; ++i) check(hal_xdr_decode_bytestring32(&keyptr, keylim, &x[i])); // 4. compute the string K as follows: // for ( i = 0; i < p; i = i + 1 ) { // tmp = x[i] // for ( j = 0; j < 2^w - 1; j = j + 1 ) { // tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) // } // y[i] = tmp // } // K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1]) SHA256_CTX ctx; bytestring32 y[p]; for (size_t i = 0; i < p; ++i) { bytestring32 tmp; memcpy(&tmp, &x[i], sizeof(tmp)); for (size_t j = 0; j < (1U << w) - 1; ++j) { checkssl(SHA256_Init(&ctx)); checkssl(SHA256_Update(&ctx, &I, sizeof(I))); uint32_t l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l))); uint16_t s = u16str(i); checkssl(SHA256_Update(&ctx, &s, sizeof(s))); uint8_t b = u8str(j); checkssl(SHA256_Update(&ctx, &b, sizeof(b))); checkssl(SHA256_Update(&ctx, &tmp, sizeof(tmp))); checkssl(SHA256_Final((unsigned char *)&tmp, &ctx)); } memcpy(&y[i], &tmp, sizeof(tmp)); } bytestring32 K; checkssl(SHA256_Init(&ctx)); checkssl(SHA256_Update(&ctx, &I, sizeof(I))); uint32_t l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l))); uint16_t s = u16str(D_PBLC); checkssl(SHA256_Update(&ctx, &s, sizeof(s))); for (size_t i = 0; i < p; ++i) checkssl(SHA256_Update(&ctx, (uint8_t *)&y[i], sizeof(y[i]))); checkssl(SHA256_Final((unsigned char *)&K, &ctx)); // 5. return u32str(type) || I || u32str(q) || K uint8_t *pubptr = pub; const uint8_t * const publim = pub + pub_max; check(hal_xdr_encode_int(&pubptr, publim, lmots_type)); check(hal_xdr_encode_bytestring16(&pubptr, publim, &I)); check(hal_xdr_encode_int(&pubptr, publim, q)); check(hal_xdr_encode_bytestring32(&pubptr, publim, &K)); if (pub_len != NULL) *pub_len = pubptr - pub; return HAL_OK; } // 4.5. Checksum static uint16_t Cksm(const uint8_t * const S, const lmots_algorithm_t lmots_type) { // Algorithm 2: Checksum Calculation // sum = 0 // for ( i = 0; i < (n*8/w); i = i + 1 ) { // sum = sum + (2^w - 1) - coef(S, i, w) // } // return (sum << ls) size_t n = lmots_type_to_n(lmots_type); size_t w = lmots_type_to_w(lmots_type); size_t ls = lmots_type_to_ls(lmots_type); uint16_t sum = 0; for (size_t i = 0; i < (n * 8 / w); ++i) sum += ((1 << w) - 1) - coef(S, i, w); return (sum << ls); } // 4.6. Signature Generation static inline size_t lmots_signature_len(const lmots_algorithm_t lmots_type) { /* u32str(type) || C || y[0] || ... || y[p-1] */ return (sizeof(uint32_t) + ((lmots_type_to_p(lmots_type) + 1) * lmots_type_to_n(lmots_type))); } static hal_error_t lmots_sign(const uint8_t * const key, const size_t key_len, const uint8_t * const msg, const size_t msg_len, uint8_t *sig, size_t *sig_len, const size_t sig_max) { if (key == NULL || msg == NULL || sig == NULL) return HAL_ERROR_BAD_ARGUMENTS; // Algorithm 3: Generating a One Time Signature From a Private Key and a // Message const uint8_t *keyptr = key; const uint8_t * const keylim = key + key_len; /* private key format * u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1] */ // 1. set type to the typecode of the algorithm lmots_algorithm_t lmots_type; check(hal_xdr_decode_int(&keyptr, keylim, &lmots_type)); // 2. set n, p, and w according to the typecode and Table 1 size_t n = lmots_type_to_n(lmots_type); size_t p = lmots_type_to_p(lmots_type); size_t w = lmots_type_to_w(lmots_type); // 3. determine x, I and q from the private key bytestring16 I; check(hal_xdr_decode_bytestring16(&keyptr, keylim, &I)); uint32_t q; check(hal_xdr_decode_int(&keyptr, keylim, &q)); bytestring32 x[p]; for (size_t i = 0; i < p; ++i) check(hal_xdr_decode_bytestring32(&keyptr, keylim, &x[i])); // 4. set C to a uniformly random n-byte string bytestring32 C; checkssl(RAND_bytes((unsigned char *)&C, n)); // 5. compute the array y as follows: // Q = H(I || u32str(q) || u16str(D_MESG) || C || message) // for ( i = 0; i < p; i = i + 1 ) { // a = coef(Q || Cksm(Q), i, w) // tmp = x[i] // for ( j = 0; j < a; j = j + 1 ) { // tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) // } // y[i] = tmp // } SHA256_CTX ctx; uint8_t Q[n + 2]; /* hash || 16-bit checksum */ checkssl(SHA256_Init(&ctx)); checkssl(SHA256_Update(&ctx, &I, sizeof(I))); uint32_t l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l))); uint16_t s = u16str(D_MESG); checkssl(SHA256_Update(&ctx, &s, sizeof(s))); checkssl(SHA256_Update(&ctx, &C, sizeof(C))); checkssl(SHA256_Update(&ctx, msg, msg_len)); checkssl(SHA256_Final((unsigned char *)Q, &ctx)); /* append checksum */ *(uint16_t *)&Q[n] = u16str(Cksm((uint8_t *)Q, lmots_type)); bytestring32 y[p]; for (size_t i = 0; i < p; ++i) { size_t a = coef(Q, i, w); bytestring32 tmp; memcpy(&tmp, &x[i], sizeof(tmp)); for (size_t j = 0; j < a; ++j) { checkssl(SHA256_Init(&ctx)); checkssl(SHA256_Update(&ctx, &I, sizeof(I))); uint32_t l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l))); uint16_t s = u16str(i); checkssl(SHA256_Update(&ctx, &s, sizeof(s))); uint8_t b = u8str(j); checkssl(SHA256_Update(&ctx, &b, sizeof(b))); checkssl(SHA256_Update(&ctx, &tmp, sizeof(tmp))); checkssl(SHA256_Final((unsigned char *)&tmp, &ctx)); } memcpy(&y[i], &tmp, sizeof(tmp)); } // 6. return u32str(type) || C || y[0] || ... || y[p-1] uint8_t *sigptr = sig; const uint8_t * const siglim = sig + sig_max; check(hal_xdr_encode_int(&sigptr, siglim, lmots_type)); check(hal_xdr_encode_bytestring32(&sigptr, siglim, &C)); for (size_t i = 0; i < p; ++i) check(hal_xdr_encode_bytestring32(&sigptr, siglim, &y[i])); if (sig_len != NULL) *sig_len = sigptr - sig; return HAL_OK; } // 4.7. Signature Verification static hal_error_t lmots_public_key_candidate(const lmots_algorithm_t pubtype, const bytestring16 * const I, const size_t q, const uint8_t * const msg, const size_t msg_len, const uint8_t * const sig, const size_t sig_len, bytestring32 * Kc); #if 0 /* unused */ static hal_error_t lmots_verify(const uint8_t * const key, const size_t key_len, const uint8_t * const msg, const size_t msg_len, const uint8_t * const sig, const size_t sig_len) { if (key == NULL || key_len < lmots_private_key_len(lmots_type) || msg == NULL || sig == NULL || sig_len < lmots_signature_len(lmots_type)) return HAL_ERROR_BAD_ARGUMENTS; // Algorithm 4a: Verifying a Signature and Message Using a Public Key // // 1. if the public key is not at least four bytes long, return INVALID if (key_len < 4) return HAL_ERROR_INVALID_SIGNATURE; // 2. parse pubtype, I, q, and K from the public key as follows: // a. pubtype = strTou32(first 4 bytes of public key) const uint8_t *keyptr = key; const uint8_t * const keylim = key + key_len; lmots_algorithm_t lmots_type; check(hal_xdr_decode_int(&keyptr, keylim, &lmots_type)); /* XXX missing from draft */ size_t n = lmots_type_to_n(lmots_type); // b. if the public key is not exactly 24 + n bytes long, // return INVALID if (key_len != 24 + n) return HAL_ERROR_INVALID_SIGNATURE; // c. I = next 16 bytes of public key bytestring16 I; check(hal_xdr_decode_bytestring16(&keyptr, keylim, &I)); // d. q = strTou32(next 4 bytes of public key) uint32_t q; check(hal_xdr_decode_int(&keyptr, keylim, &q)); // e. K = next n bytes of public key bytestring32 K; check(hal_xdr_decode_bytestring32(&keyptr, keylim, &K)); // 3. compute the public key candidate Kc from the signature, // message, and the identifiers I and q obtained from the // public key, using Algorithm 4b. If Algorithm 4b returns // INVALID, then return INVALID. bytestring32 Kc; check(lmots_public_key_candidate(lmots_type, &I, q, msg, msg_len, sig, sig_len, &Kc)); // 4. if Kc is equal to K, return VALID; otherwise, return INVALID return (memcmp(&Kc, &K, sizeof(Kc)) ? HAL_ERROR_INVALID_SIGNATURE : HAL_OK); } #endif static hal_error_t lmots_public_key_candidate(const lmots_algorithm_t lmots_type, const bytestring16 * const I, const size_t q, const uint8_t * const msg, const size_t msg_len, const uint8_t * const sig, const size_t sig_len, bytestring32 * const Kc) { if (I == NULL || msg == NULL || sig == NULL || Kc == NULL) return HAL_ERROR_BAD_ARGUMENTS; // Algorithm 4b: Computing a Public Key Candidate Kc from a Signature, // Message, Signature Typecode Type, and identifiers I, q // // 1. if the signature is not at least four bytes long, return INVALID if (sig_len < 4) return HAL_ERROR_INVALID_SIGNATURE; // 2. parse sigtype, C, and y from the signature as follows: // a. sigtype = strTou32(first 4 bytes of signature) const uint8_t *sigptr = sig; const uint8_t * const siglim = sig + sig_len; lmots_algorithm_t sigtype; check(hal_xdr_decode_int(&sigptr, siglim, &sigtype)); // b. if sigtype is not equal to pubtype, return INVALID if (sigtype != lmots_type) return HAL_ERROR_INVALID_SIGNATURE; // c. set n and p according to the pubtype and Table 1; if the // signature is not exactly 4 + n * (p+1) bytes long, return INVALID size_t n = lmots_type_to_n(lmots_type); size_t p = lmots_type_to_p(lmots_type); if (sig_len != 4 + n * (p + 1)) return HAL_ERROR_INVALID_SIGNATURE; // d. C = next n bytes of signature bytestring32 C; check(hal_xdr_decode_bytestring32(&sigptr, siglim, &C)); // e. y[0] = next n bytes of signature // y[1] = next n bytes of signature // ... // y[p-1] = next n bytes of signature bytestring32 y[p]; for (size_t i = 0; i < p; ++i) check(hal_xdr_decode_bytestring32(&sigptr, siglim, &y[i])); // 3. compute the string Kc as follows // Q = H(I || u32str(q) || u16str(D_MESG) || C || message) // for ( i = 0; i < p; i = i + 1 ) { // a = coef(Q || Cksm(Q), i, w) // tmp = y[i] // for ( j = a; j < 2^w - 1; j = j + 1 ) { // tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) // } // z[i] = tmp // } // Kc = H(I || u32str(q) || u16str(D_PBLC) || z[0] || z[1] || ... || z[p-1]) SHA256_CTX ctx; uint8_t Q[n + 2]; /* hash || 16-bit checksum */ checkssl(SHA256_Init(&ctx)); checkssl(SHA256_Update(&ctx, I, sizeof(*I))); uint32_t l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l))); uint16_t s = u16str(D_MESG); checkssl(SHA256_Update(&ctx, &s, sizeof(s))); checkssl(SHA256_Update(&ctx, &C, sizeof(C))); checkssl(SHA256_Update(&ctx, msg, msg_len)); checkssl(SHA256_Final((unsigned char *)Q, &ctx)); /* append checksum */ *(uint16_t *)&Q[n] = u16str(Cksm((uint8_t *)Q, lmots_type)); size_t w = lmots_type_to_w(lmots_type); bytestring32 z[p]; for (size_t i = 0; i < p; ++i) { uint8_t a = coef(Q, i, w); bytestring32 tmp; memcpy(&tmp, &y[i], sizeof(tmp)); for (size_t j = (size_t)a; j < (1U << w) - 1; ++j) { checkssl(SHA256_Init(&ctx)); checkssl(SHA256_Update(&ctx, I, sizeof(*I))); l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l))); s = u16str(i); checkssl(SHA256_Update(&ctx, &s, sizeof(s))); uint8_t b = u8str(j); checkssl(SHA256_Update(&ctx, &b, sizeof(b))); checkssl(SHA256_Update(&ctx, &tmp, sizeof(tmp))); checkssl(SHA256_Final((unsigned char *)&tmp, &ctx)); } memcpy(&z[i], &tmp, sizeof(tmp)); } checkssl(SHA256_Init(&ctx)); checkssl(SHA256_Update(&ctx, I, sizeof(*I))); l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l))); s = u16str(D_PBLC); checkssl(SHA256_Update(&ctx, &s, sizeof(s))); for (size_t i = 0; i < p; ++i) checkssl(SHA256_Update(&ctx, &z[i], sizeof(z[i]))); checkssl(SHA256_Final((unsigned char *)Kc, &ctx)); // 4. return Kc return HAL_OK; } /* ---------------------------------------------------------------- */ // 5. Leighton Micali Signatures // 5.1. Parameters static inline size_t lms_type_to_h(const lms_algorithm_t lms_type) { switch (lms_type) { case lms_sha256_n32_h5: return 5; case lms_sha256_n32_h10: return 10; case lms_sha256_n32_h15: return 15; case lms_sha256_n32_h20: return 20; case lms_sha256_n32_h25: return 25; default: return 0; } } static inline size_t lms_type_to_m(const lms_algorithm_t lms_type) { switch (lms_type) { case lms_sha256_n32_h5: case lms_sha256_n32_h10: case lms_sha256_n32_h15: case lms_sha256_n32_h20: case lms_sha256_n32_h25: return 32; default: return 0; } } // 5.2. LMS Private Key static inline size_t lms_private_key_len(const lms_algorithm_t lms_type, const lmots_algorithm_t lmots_type) { /* u32str(type) || u32str(q) || OTS_PRIV[0] || OTS_PRIV[1] || ... || OTS_PRIV[2^h - 1] */ return ((2 * sizeof(uint32_t)) + ((1 << lms_type_to_h(lms_type)) * lmots_private_key_len(lmots_type))); } static hal_error_t lms_generate_private_key(const lms_algorithm_t lms_type, const lmots_algorithm_t lmots_type, uint8_t * const key, size_t * const key_len, const size_t key_max) { if (key == NULL || key_max < lms_private_key_len(lms_type, lmots_type)) return HAL_ERROR_BAD_ARGUMENTS; // Algorithm 5: Computing an LMS Private Key. // 1. determine h and m from the typecode and Table 2. size_t h = lms_type_to_h(lms_type); /* XXX m is not used here */ /* XXX missing from draft: generate I for this keypair */ bytestring16 I; checkssl(RAND_bytes((unsigned char *)&I, sizeof(I))); // 2. compute the array OTS_PRIV[] as follows: // for ( q = 0; q < 2^h; q = q + 1) { // OTS_PRIV[q] = LM-OTS private key with identifiers I, q // } /* initialize the key buffer with type and q=0, so we can generate the * lmots private keys directly in the key buffer */ uint8_t *keyptr = key; uint8_t *keylim = key + key_max; check(hal_xdr_encode_int(&keyptr, keylim, lms_type)); check(hal_xdr_encode_int(&keyptr, keylim, 0)); for (size_t q = 0; q < (1U << h); ++q) { size_t ots_len; check(lmots_generate_private_key(lmots_type, &I, q, keyptr, &ots_len, keylim - keyptr)); keyptr += ots_len; } // 3. q = 0 /* XXX missing from draft: return the key in output format */ /* 4. return u32str(type) || u32str(q) || OTS_PRIV[0] || OTS_PRIV[1] || ... || OTS_PRIV[2^h - 1] */ if (key_len != NULL) *key_len = keyptr - key; return HAL_OK; } // 5.3. LMS Public Key static inline size_t lms_public_key_len(const lms_algorithm_t lms_type) { /* u32str(type) || u32str(otstype) || I || T[1] */ return ((2 * sizeof(uint32_t)) + 16 + lms_type_to_m(lms_type)); } static hal_error_t lms_generate_T(const lms_algorithm_t lms_type, const lmots_algorithm_t lmots_type, const bytestring16 * const I, const uint8_t * const key, bytestring32 * const T) { size_t h = lms_type_to_h(lms_type); size_t lmots_prv_len = lmots_private_key_len(lmots_type); size_t lmots_pub_len = lmots_public_key_len(lmots_type); const uint8_t *keyptr = key; SHA256_CTX ctx; // T[r]=/ H(I||u32str(r)||u16str(D_LEAF)||OTS_PUB_HASH[r-2^h]) if r >= 2^h, // \ H(I||u32str(r)||u16str(D_INTR)||T[2*r]||T[2*r+1]) otherwise. /* first generate the leaf-node T values */ for (size_t q = 0; q < (1U << h); ++q) { /* generate OTS_PUB_HASH[q] */ size_t r = (1 << h) + q; uint8_t pub[lmots_pub_len]; check(lmots_generate_public_key(keyptr, lmots_prv_len, pub, NULL, lmots_pub_len)); keyptr += lmots_prv_len; checkssl(SHA256_Init(&ctx)); checkssl(SHA256_Update(&ctx, I, sizeof(*I))); uint32_t l = u32str(r); checkssl(SHA256_Update(&ctx, &l, sizeof(l))); uint16_t s = u16str(D_LEAF); checkssl(SHA256_Update(&ctx, &s, sizeof(s))); checkssl(SHA256_Update(&ctx, &pub[24], sizeof(bytestring32))); checkssl(SHA256_Final((unsigned char *)&T[r], &ctx)); } /* then generate the rest of T[], from bottom to top */ for (size_t r = (1 << h) - 1; r > 0; --r) { checkssl(SHA256_Init(&ctx)); checkssl(SHA256_Update(&ctx, I, sizeof(*I))); uint32_t l = u32str(r); checkssl(SHA256_Update(&ctx, &l, sizeof(l))); uint16_t s = u16str(D_INTR); checkssl(SHA256_Update(&ctx, &s, sizeof(s))); checkssl(SHA256_Update(&ctx, &T[2*r], sizeof(T[r]))); checkssl(SHA256_Update(&ctx, &T[2*r+1], sizeof(T[r]))); checkssl(SHA256_Final((unsigned char *)&T[r], &ctx)); } return HAL_OK; } static hal_error_t lms_generate_public_key(const uint8_t * const key, const size_t key_len, uint8_t *pub, size_t *pub_len, const size_t pub_max) { if (key == NULL || pub == NULL) return HAL_ERROR_BAD_ARGUMENTS; const uint8_t *keyptr = key; const uint8_t * const keylim = key + key_len; /* private key format * u32str(type) || u32str(q) || OTS_PRIV[0] || OTS_PRIV[1] || ... || OTS_PRIV[2^h - 1] */ lms_algorithm_t lms_type; check(hal_xdr_decode_int(&keyptr, keylim, &lms_type)); size_t h = lms_type_to_h(lms_type); /* skip over q, which will be 0 */ keyptr += 4; /* peek into the first lmots private key for type and I */ /* u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1] */ const uint8_t *lookahead = keyptr; lmots_algorithm_t lmots_type; bytestring16 I; check(hal_xdr_decode_int(&lookahead, keylim, &lmots_type)); check(hal_xdr_decode_bytestring16(&lookahead, keylim, &I)); // The LMS public key is the string u32str(type) || u32str(otstype) || I || T[1]. uint8_t *pubptr = pub; const uint8_t * const publim = pub + pub_max; check(hal_xdr_encode_int(&pubptr, publim, lms_type)); check(hal_xdr_encode_int(&pubptr, publim, lmots_type)); check(hal_xdr_encode_bytestring16(&pubptr, publim, &I)); bytestring32 T[1 << (h + 1)]; check(lms_generate_T(lms_type, lmots_type, &I, keyptr, T)); check(hal_xdr_encode_bytestring32(&pubptr, publim, &T[1])); if (pub_len != NULL) *pub_len = pubptr - pub; return HAL_OK; } // 5.4. LMS Signature static inline size_t lms_signature_len(const lms_algorithm_t lms_type, const lmots_algorithm_t lmots_type) { /* u32str(q) || ots_signature || u32str(type) || path[0] || path[1] || ... || path[h-1] */ return ((2 * sizeof(uint32_t)) + lmots_signature_len(lmots_type) + (lms_type_to_h(lms_type) * lms_type_to_m(lms_type))); } static hal_error_t lms_sign(const uint8_t * const key, const size_t key_len, const uint8_t * const msg, const size_t msg_len, uint8_t *sig, size_t *sig_len, const size_t sig_max) { // An LMS signature consists of // // the number q of the leaf associated with the LM-OTS signature, as // a four-byte unsigned integer in network byte order, // // an LM-OTS signature, and // // a typecode indicating the particular LMS algorithm, // // an array of h m-byte values that is associated with the path // through the tree from the leaf associated with the LM-OTS // signature to the root. // // Symbolically, the signature can be represented as u32str(q) || // ots_signature || u32str(type) || path[0] || path[1] || ... || // path[h-1]. const uint8_t *keyptr = key; const uint8_t * const keylim = key + key_len; /* private key format * u32str(type) || u32str(q) || OTS_PRIV[0] || OTS_PRIV[1] || ... || OTS_PRIV[2^h - 1] */ lms_algorithm_t lms_type; check(hal_xdr_decode_int(&keyptr, keylim, &lms_type)); size_t h = lms_type_to_h(lms_type); uint32_t q; check(hal_xdr_decode_int(&keyptr, keylim, &q)); if (q >= (1U << h)) return HAL_ERROR_HASHSIG_KEY_EXHAUSTED; /* peek into the first lmots private key for lmots_type and I */ const uint8_t *lookahead = keyptr; lmots_algorithm_t lmots_type; check(hal_xdr_decode_int(&lookahead, keylim, &lmots_type)); bytestring16 I; check(hal_xdr_decode_bytestring16(&lookahead, keylim, &I)); if (sig_max < lms_signature_len(lms_type, lmots_type)) return HAL_ERROR_BAD_ARGUMENTS; uint8_t *sigptr = sig; const uint8_t * const siglim = sig + sig_max; check(hal_xdr_encode_int(&sigptr, siglim, q)); /* locate the lmots signing key OTS_PRIV[q] */ const size_t lmots_key_len = lmots_private_key_len(lmots_type); const uint8_t * const lmots_key = keyptr + q * lmots_key_len; /* generate the lmots signature */ size_t lmots_sig_len; check(lmots_sign(lmots_key, lmots_key_len, msg, msg_len, sigptr, &lmots_sig_len, siglim - sigptr)); sigptr += lmots_sig_len; check(hal_xdr_encode_int(&sigptr, siglim, lms_type)); /* generate the path array */ bytestring32 T[1 << (h + 1)]; check(lms_generate_T(lms_type, lmots_type, &I, keyptr, T)); for (size_t r = (1 << h) + q; r > 1; r /= 2) check(hal_xdr_encode_bytestring32(&sigptr, siglim, ((r & 1) ? &T[r-1] : &T[r+1]))); if (sig_len != NULL) *sig_len = sigptr - sig; /* update q before returning the signature */ keyptr = key + 4; check(hal_xdr_encode_int((uint8_t ** const)&keyptr, keylim, ++q)); return HAL_OK; } // 5.5. LMS Signature Verification static hal_error_t lms_public_key_candidate(const lms_algorithm_t pubtype, const lmots_algorithm_t pubotstype, const bytestring16 * const I, const uint8_t * const msg, const size_t msg_len, const uint8_t * const sig, const size_t sig_len, bytestring32 * Tc); static hal_error_t lms_verify(const uint8_t * const key, const size_t key_len, const uint8_t * const msg, const size_t msg_len, const uint8_t * const sig, const size_t sig_len) { if (key == NULL || msg == NULL || sig == NULL) return HAL_ERROR_BAD_ARGUMENTS; // Algorithm 6: LMS Signature Verification // 1. if the public key is not at least eight bytes long, return // INVALID if (key_len < 8) return HAL_ERROR_INVALID_SIGNATURE; // 2. parse pubtype, I, and T[1] from the public key as follows: // // a. pubtype = strTou32(first 4 bytes of public key) const uint8_t *keyptr = key; const uint8_t * const keylim = key + key_len; lms_algorithm_t pubtype; check(hal_xdr_decode_int(&keyptr, keylim, &pubtype)); // b. ots_typecode = strTou32(next 4 bytes of public key) lmots_algorithm_t pubotstype; check(hal_xdr_decode_int(&keyptr, keylim, &pubotstype)); // c. set m according to pubtype, based on Table 2 size_t m = lms_type_to_m(pubtype); // d. if the public key is not exactly 24 + m bytes // long, return INVALID if (key_len != 24 + m) return HAL_ERROR_INVALID_SIGNATURE; // e. I = next 16 bytes of the public key bytestring16 I; check(hal_xdr_decode_bytestring16(&keyptr, keylim, &I)); // f. T[1] = next m bytes of the public key bytestring32 T1; check(hal_xdr_decode_bytestring32(&keyptr, keylim, &T1)); // 3. compute the candidate LMS root value Tc from the signature, // message, identifier and pubtype using Algorithm 6b. bytestring32 Tc; check(lms_public_key_candidate(pubtype, pubotstype, &I, msg, msg_len, sig, sig_len, &Tc)); // 4. if Tc is equal to T[1], return VALID; otherwise, return INVALID return (memcmp(&Tc, &T1, sizeof(Tc)) ? HAL_ERROR_INVALID_SIGNATURE : HAL_OK); } static hal_error_t lms_public_key_candidate(const lms_algorithm_t pubtype, const lmots_algorithm_t pubotstype, // XXX missing from draft const bytestring16 * const I, const uint8_t * const msg, const size_t msg_len, const uint8_t * const sig, const size_t sig_len, bytestring32 * Tc) { // Algorithm 6b: Computing an LMS Public Key Candidate from a Signature, // Message, Identifier, and algorithm typecode // 1. if the signature is not at least eight bytes long, return INVALID if (sig_len < 8) return HAL_ERROR_INVALID_SIGNATURE; // 2. parse sigtype, q, ots_signature, and path from the signature as // follows: const uint8_t *sigptr = sig; const uint8_t * const siglim = sig + sig_len; // a. q = strTou32(first 4 bytes of signature) uint32_t q; check(hal_xdr_decode_int(&sigptr, siglim, &q)); // b. otssigtype = strTou32(next 4 bytes of signature) lmots_algorithm_t otssigtype; check(hal_xdr_decode_int_peek(&sigptr, siglim, &otssigtype)); // c. if otssigtype is not the OTS typecode from the public key, return INVALID if (otssigtype != pubotstype) return HAL_ERROR_INVALID_SIGNATURE; // d. set n, p according to otssigtype and Table 1; if the // signature is not at least 12 + n * (p + 1) bytes long, return INVALID size_t n = lmots_type_to_n(otssigtype); size_t p = lmots_type_to_p(otssigtype); if (sig_len < 12 + n * (p + 1)) return HAL_ERROR_INVALID_SIGNATURE; // e. ots_signature = bytes 8 through 8 + n * (p + 1) - 1 of signature /* XXX This is the remainder of ots_signature after otssigtype. * The full ots_signature would be bytes 4 through 8 + n * (p + 1) - 1. */ const uint8_t * const ots_signature = sigptr; sigptr += lmots_signature_len(otssigtype); // f. sigtype = strTou32(4 bytes of signature at location 8 + n * (p + 1)) lms_algorithm_t sigtype; check(hal_xdr_decode_int(&sigptr, siglim, &sigtype)); // f. if sigtype is not the LM typecode from the public key, return INVALID if (sigtype != pubtype) return HAL_ERROR_INVALID_SIGNATURE; // g. set m, h according to sigtype and Table 2 size_t m = lms_type_to_m(sigtype); size_t h = lms_type_to_h(sigtype); // h. if q >= 2^h or the signature is not exactly 12 + n * (p + 1) + m * h bytes long, return INVALID if (q >= (1U << h) || sig_len != 12 + n * (p + 1) + m * h) return HAL_ERROR_INVALID_SIGNATURE; // i. set path as follows: // path[0] = next m bytes of signature // path[1] = next m bytes of signature // ... // path[h-1] = next m bytes of signature bytestring32 path[h]; for (size_t i = 0; i < h; ++i) check(hal_xdr_decode_bytestring32(&sigptr, siglim, &path[i])); // 3. Kc = candidate public key computed by applying Algorithm 4b // to the signature ots_signature, the message, and the // identifiers I, q bytestring32 Kc; check(lmots_public_key_candidate(pubotstype, I, q, msg, msg_len, ots_signature, lmots_signature_len(otssigtype), &Kc)); // 4. compute the candidate LMS root value Tc as follows: // node_num = 2^h + q size_t r = (1 << h) + q; // tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc) bytestring32 tmp; SHA256_CTX ctx; checkssl(SHA256_Init(&ctx)); checkssl(SHA256_Update(&ctx, I, sizeof(*I))); uint32_t l = u32str(r); checkssl(SHA256_Update(&ctx, &l, sizeof(l))); uint16_t s = u16str(D_LEAF); checkssl(SHA256_Update(&ctx, &s, sizeof(s))); checkssl(SHA256_Update(&ctx, &Kc, sizeof(Kc))); checkssl(SHA256_Final((unsigned char *)&tmp, &ctx)); // i = 0 // while (node_num > 1) { // if (node_num is odd): // tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||path[i]||tmp) // else: // tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||tmp||path[i]) // node_num = node_num/2 // i = i + 1 // } for (size_t i = 0; r > 1; r /= 2, ++i) { checkssl(SHA256_Init(&ctx)); checkssl(SHA256_Update(&ctx, I, sizeof(*I))); uint32_t l = u32str(r/2); checkssl(SHA256_Update(&ctx, &l, sizeof(l))); uint16_t s = u16str(D_INTR); checkssl(SHA256_Update(&ctx, &s, sizeof(s))); if (r & 1) { checkssl(SHA256_Update(&ctx, &path[i], m)); checkssl(SHA256_Update(&ctx, &tmp, sizeof(tmp))); } else { checkssl(SHA256_Update(&ctx, &tmp, sizeof(tmp))); checkssl(SHA256_Update(&ctx, &path[i], m)); } checkssl(SHA256_Final((unsigned char *)&tmp, &ctx)); } // Tc = tmp memcpy(Tc, &tmp, sizeof(*Tc)); return HAL_OK; } /* ---------------------------------------------------------------- */ //6. Hierarchical signatures // 6.1. Key Generation static inline size_t hss_private_key_len(const size_t L, const lms_algorithm_t lms_type, const lmots_algorithm_t lmots_type) { /* u32str(L) || lms_priv[0] || lms_priv[1] || ... || lms_priv[L-1] || sig[0] || pub[1] || ... || sig[L-2] || pub[L-1] */ return (4 + (L * lms_private_key_len(lms_type, lmots_type)) + ((L - 1) * (lms_signature_len(lms_type, lmots_type) + lms_public_key_len(lms_type)))); } static hal_error_t hss_generate_private_key(const size_t L, const lms_algorithm_t lms_type, const lmots_algorithm_t lmots_type, uint8_t * const key, size_t * const key_len, const size_t key_max) { if (L == 0 || L > 8 || lms_type < lms_sha256_n32_h5 || lms_type > lms_sha256_n32_h25 || lmots_type < lmots_sha256_n32_w1 || lmots_type > lmots_sha256_n32_w8 || key == NULL || key_max < hss_private_key_len(L, lms_type, lmots_type)) return HAL_ERROR_BAD_ARGUMENTS; uint8_t *keyptr = key; const uint8_t * const keylim = key + key_max; // The HSS private key consists of prv[0], ... , prv[L-1]. /* XXX This omits L */ check(hal_xdr_encode_int(&keyptr, keylim, L)); size_t lms_prv_len = lms_private_key_len(lms_type, lmots_type); size_t lms_pub_len = lms_public_key_len(lms_type); size_t lms_sig_len = lms_signature_len(lms_type, lmots_type); for (size_t i = 0; i < L; ++i, keyptr += lms_prv_len) { check(lms_generate_private_key(lms_type, lmots_type, keyptr, NULL, lms_prv_len)); if (i > 0) { /* Generate the public key, and sign it with the previous private * key. Stash the signed public keys at the end of the private * key file, so we can copy them wholesale into the signature. */ uint8_t *sigptr = key + 4 + (L * lms_prv_len) + ((i - 1) * (lms_sig_len + lms_pub_len)); uint8_t *pubptr = sigptr + lms_sig_len; check(lms_generate_public_key(keyptr, lms_prv_len, pubptr, NULL, lms_pub_len)); check(lms_sign(keyptr - lms_prv_len, lms_prv_len, pubptr, lms_pub_len, sigptr, NULL, lms_sig_len)); } } keyptr += (L - 1) * (lms_sig_len + lms_pub_len); if (key_len != NULL) *key_len = keyptr - key; return HAL_OK; } static inline size_t hss_public_key_len(const lms_algorithm_t lms_type) { /* L || pub[0] */ return (sizeof(uint32_t) + lms_public_key_len(lms_type)); } static hal_error_t hss_generate_public_key(const size_t L, const lms_algorithm_t lms_type, const lmots_algorithm_t lmots_type, const uint8_t * const key, const size_t key_len, uint8_t *pub, size_t *pub_len, const size_t pub_max) { if (key == NULL || key_len < hss_private_key_len(L, lms_type, lmots_type) || pub == NULL || pub_max < hss_public_key_len(lms_type)) return HAL_ERROR_BAD_ARGUMENTS; const uint8_t *keyptr = key; const uint8_t * const keylim = key + key_len; uint8_t *pubptr = pub; const uint8_t * const publim = pub + pub_max; // The public key of the HSS scheme consists of the number of levels L, // followed by pub[0], the public key of the top level. uint32_t L_key; check(hal_xdr_decode_int(&keyptr, keylim, &L_key)); if ((size_t)L_key != L) return HAL_ERROR_BAD_ARGUMENTS; check(hal_xdr_encode_int(&pubptr, publim, L)); /* generate the lms public key from the first lms private key */ size_t len; check(lms_generate_public_key(keyptr, lms_private_key_len(lms_type, lmots_type), pubptr, &len, publim - pubptr)); pubptr += len; if (pub_len != NULL) *pub_len = pubptr - pub; return HAL_OK; } //6.2. Signature Generation static inline size_t hss_signature_len(const size_t L, const lms_algorithm_t lms_type, const lmots_algorithm_t lmots_type) { /* u32str(Nspk) || sig[0] || pub[1] || ... || sig[Nspk-1] || pub[Nspk] || sig[Nspk] */ return (sizeof(uint32_t) + (L * lms_signature_len(lms_type, lmots_type)) + ((L - 1) * lms_public_key_len(lms_type))); } static hal_error_t hss_sign(const uint8_t * const key, const size_t key_len, const uint8_t * const msg, const size_t msg_len, uint8_t *sig, size_t *sig_len, const size_t sig_max) { if (key == NULL || msg == NULL || sig == NULL) return HAL_ERROR_BAD_ARGUMENTS; const uint8_t *keyptr = key; const uint8_t * const keylim = key + key_len; /* private key format: * u32str(L) || lms_priv[0] || lms_priv[1] || ... || lms_priv[L-1] */ uint32_t L; check(hal_xdr_decode_int(&keyptr, keylim, &L)); /* peek into the first lms private key for lms and lmots types */ lms_algorithm_t lms_type; check(hal_xdr_decode_int(&keyptr, keylim, &lms_type)); keyptr += 4; /* skip over q */ lmots_algorithm_t lmots_type; check(hal_xdr_decode_int(&keyptr, keylim, &lmots_type)); size_t h = lms_type_to_h(lms_type); size_t lms_prv_len = lms_private_key_len(lms_type, lmots_type); size_t lms_pub_len = lms_public_key_len(lms_type); size_t lms_sig_len = lms_signature_len(lms_type, lmots_type); // To sign a message using the private key prv, the following steps are // performed: // // If prv[L-1] is exhausted, then determine the smallest integer d // such that all of the private keys prv[d], prv[d+1], ... , prv[L-1] // are exhausted. If d is equal to zero, then the HSS key pair is // exhausted, and it MUST NOT generate any more signatures. // Otherwise, the key pairs for levels d through L-1 must be // regenerated during the signature generation process, as follows. // For i from d to L-1, a new LMS public and private key pair with a // new identifier is generated, pub[i] and prv[i] are set to those // values, then the public key pub[i] is signed with prv[i-1], and // sig[i-1] is set to the resulting value. uint32_t q; keyptr = key + 4 + ((L - 1) * lms_prv_len) + 4; check(hal_xdr_decode_int_peek(&keyptr, keylim, &q)); if (q >= (1U << h)) { size_t d; for (d = L - 1; d > 0; --d) { keyptr = key + 4 + ((d -1) * lms_prv_len) + 4; check(hal_xdr_decode_int_peek(&keyptr, keylim, &q)); if (q < (1U << h)) break; } if (d == 0) return HAL_ERROR_HASHSIG_KEY_EXHAUSTED; for ( ; d < L; ++d) { keyptr = key + 4 + (d * lms_prv_len); /* generate the new private key */ check(lms_generate_private_key(lms_type, lmots_type, (uint8_t * const)keyptr, NULL, lms_prv_len)); /* generate the new signed public key, after all the private keys */ uint8_t *sigptr = (uint8_t *)key + 4 + (L * lms_prv_len) + ((d - 1) * (lms_sig_len + lms_pub_len)); uint8_t *pubptr = sigptr + lms_pub_len; check(lms_generate_public_key(keyptr, lms_prv_len, pubptr, NULL, lms_pub_len)); check(lms_sign(keyptr - lms_prv_len, lms_prv_len, pubptr, lms_pub_len, sigptr, NULL, lms_sig_len)); } } uint8_t *sigptr = sig; const uint8_t * const siglim = sig + sig_max; check(hal_xdr_encode_int(&sigptr, siglim, L - 1)); // The message is signed with prv[L-1], and the value sig[L-1] is set // to that result. // // The value of the HSS signature is set as follows. We let // signed_pub_key denote an array of octet strings, where // signed_pub_key[i] = sig[i] || pub[i+1], for i between 0 and Nspk- // 1, inclusive, where Nspk = L-1 denotes the number of signed public // keys. Then the HSS signature is u32str(Nspk) || // signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk]. /* copy the precomputed signed public keys from the end of the private key */ keyptr = key + 4 + (L * lms_prv_len); check(hal_xdr_encode_fixed_opaque(&sigptr, siglim, keyptr, (L - 1) * (lms_sig_len + lms_pub_len))); /* sign the message with the last lms private key */ keyptr -= lms_prv_len; check(lms_sign(keyptr, lms_prv_len, msg, msg_len, sigptr, NULL, lms_sig_len)); sigptr += lms_sig_len; if (sig_len != NULL) *sig_len = sigptr - sig; return HAL_OK; } //6.3. Signature Verification static hal_error_t hss_verify(const uint8_t * const pub, const size_t pub_len, const uint8_t * const message, const size_t message_len, const uint8_t * const signature, const size_t signature_len) { if (pub == NULL || message == NULL || signature == NULL) return HAL_ERROR_BAD_ARGUMENTS; // To verify a signature sig and message using the public key pub, the // following steps are performed: // // The signature S is parsed into its components as follows: // Nspk = strTou32(first four bytes of S) const uint8_t * sigptr = signature; const uint8_t * const siglim = signature + signature_len; uint32_t Nspk; check(hal_xdr_decode_int(&sigptr, siglim, &Nspk)); // if Nspk+1 is not equal to the number of levels L in pub: // return INVALID const uint8_t * pubptr = pub; const uint8_t * const publim = pub + pub_len; uint32_t L; check(hal_xdr_decode_int(&pubptr, publim, &L)); if (Nspk + 1 != L) return HAL_ERROR_INVALID_SIGNATURE; // key = pub const uint8_t *key = pubptr; size_t key_len = pub_len - sizeof(uint32_t); const uint8_t *sig; size_t sig_len; const uint8_t *msg; size_t msg_len; // for (i = 0; i < Nspk; i = i + 1) { for (size_t i = 0; i < Nspk; ++i) { /* peek into the lms public key for lms and lmots types */ const uint8_t *keyptr = key; const uint8_t * const keylim = key + key_len; lms_algorithm_t lms_type; check(hal_xdr_decode_int(&keyptr, keylim, &lms_type)); lmots_algorithm_t lmots_type; check(hal_xdr_decode_int(&keyptr, keylim, &lmots_type)); // sig = next LMS signature parsed from S // msg = next LMS public key parsed from S sig = sigptr; sig_len = lms_signature_len(lms_type, lmots_type); sigptr += sig_len; msg = sigptr; msg_len = lms_public_key_len(lms_type); sigptr += msg_len; if (sigptr > siglim) return HAL_ERROR_INVALID_SIGNATURE; // if (lms_verify(msg, key, sig) != VALID): // return INVALID check(lms_verify(key, key_len, msg, msg_len, sig, sig_len)); // key = msg key = msg; key_len = msg_len; // } } /* peek into the lms public key for lms and lmots types */ const uint8_t *keyptr = key; const uint8_t * const keylim = key + key_len; lms_algorithm_t lms_type; check(hal_xdr_decode_int(&keyptr, keylim, &lms_type)); lmots_algorithm_t lmots_type; check(hal_xdr_decode_int(&keyptr, keylim, &lmots_type)); // sig = next LMS signature parsed from S sig = sigptr; sig_len = lms_signature_len(lms_type, lmots_type); sigptr += sig_len; if (sigptr != siglim) return HAL_ERROR_INVALID_SIGNATURE; // return lms_verify(message, key, sig) check(lms_verify(key, key_len, message, message_len, sig, sig_len)); return HAL_OK; } /* ---------------------------------------------------------------- */ /* * driver code, roughly like hash-sigs-c/demo.c */ #include #include #include #include #include #include #include static void hexdump(const char * const label, const void * const buf, const size_t len) { printf("%-11s ", label); const uint8_t *b = buf; for (size_t i = 0; i < len; ++i, ++b) { printf("%02x", *b); if ((i & 0x0f) == 0x0f) { printf("\n"); if (i < len - 1) printf(" "); } } if ((len & 0x0f) != 0) printf("\n"); } static hal_error_t dump_lmots_prv(const uint8_t * const buf, size_t * const len, const size_t max) { const uint8_t *bufptr = buf; const uint8_t * const buflim = buf + max; hexdump("lmots type", bufptr, 4); uint32_t lmots_type; check(hal_xdr_decode_int(&bufptr, buflim, &lmots_type)); hexdump("I", bufptr, 16); bufptr += 16; hexdump("q", bufptr, 4); bufptr += 4; size_t p = lmots_type_to_p(lmots_type); for (size_t i = 0; i < p && bufptr < buflim; ++i) { char label[16]; sprintf(label, "x[%lu]", i); hexdump(label, bufptr, 32); bufptr += 32; } if (len != NULL) *len = bufptr - buf; return HAL_OK; } static hal_error_t dump_lmots_sig(const uint8_t * const buf, size_t * const len, const size_t max) { const uint8_t *bufptr = buf; const uint8_t * const buflim = buf + max; hexdump("lmots type", bufptr, 4); uint32_t lmots_type; check(hal_xdr_decode_int(&bufptr, buflim, &lmots_type)); hexdump("C", bufptr, 32); bufptr += 32; size_t p = lmots_type_to_p(lmots_type); for (size_t i = 0; i < p && bufptr < buflim; ++i) { char label[16]; sprintf(label, "y[%lu]", i); hexdump(label, bufptr, 32); bufptr += 32; } if (len != NULL) *len = bufptr - buf; return HAL_OK; } static hal_error_t dump_lms_prv(const uint8_t * const buf, size_t * const len, const size_t max) { const uint8_t *bufptr = buf; const uint8_t * const buflim = buf + max; hexdump("lms type", bufptr, 4); uint32_t lms_type; check(hal_xdr_decode_int(&bufptr, buflim, &lms_type)); hexdump("q", bufptr, 4); uint32_t q; check(hal_xdr_decode_int(&bufptr, buflim, &q)); size_t h = lms_type_to_h(lms_type); for (size_t i = 0; i < (1U << h) && bufptr < buflim; ++i) { printf("--------------------------------------------\notsprv[%lu]\n", i); size_t lmots_len; check(dump_lmots_prv(bufptr, &lmots_len, buflim - bufptr)); bufptr += lmots_len; } if (len != NULL) *len = bufptr - buf; return HAL_OK; } static hal_error_t dump_lms_pub(const uint8_t * const buf, size_t * const len, const size_t max) { const uint8_t *bufptr = buf; const uint8_t * const buflim = buf + max; hexdump("lms type", bufptr, 4); uint32_t lms_type; check(hal_xdr_decode_int(&bufptr, buflim, &lms_type)); hexdump("lmots type", bufptr, 4); bufptr += 4; hexdump("I", bufptr, 16); bufptr += 16; hexdump("T[1]", bufptr, 32); bufptr += 32; if (len != NULL) *len = bufptr - buf; return HAL_OK; } static hal_error_t dump_lms_sig(const uint8_t * const buf, size_t * const len, const size_t max) { const uint8_t *bufptr = buf; const uint8_t * const buflim = buf + max; hexdump("q", bufptr, 4); bufptr += 4; size_t lmots_len; check(dump_lmots_sig(bufptr, &lmots_len, buflim - bufptr)); bufptr += lmots_len; hexdump("lms type", bufptr, 4); uint32_t lms_type; check(hal_xdr_decode_int(&bufptr, buflim, &lms_type)); size_t h = lms_type_to_h(lms_type); for (size_t i = 0; i < h && bufptr < buflim; ++i) { char label[16]; sprintf(label, "path[%lu]", i); hexdump(label, bufptr, 32); bufptr += 32; } if (len != NULL) *len = bufptr - buf; return HAL_OK; } static hal_error_t dump_hss_prv(const uint8_t * const buf, const size_t max) { const uint8_t *bufptr = buf; const uint8_t * const buflim = buf + max; size_t len; hexdump("L", bufptr, 4); uint32_t L; check(hal_xdr_decode_int(&bufptr, buflim, &L)); for (size_t i = 0; i < L && bufptr < buflim; ++i) { printf("--------------------------------------------\nlmsprv[%lu]\n", i); check(dump_lms_prv(bufptr, &len, buflim - bufptr)); bufptr += len; } printf("--------------------------------------------\n"); for (size_t i = 0; i < L - 1 && bufptr < buflim; ++i) { printf("--------------------------------------------\nsig[%lu]\n", i); check(dump_lms_sig(bufptr, &len, buflim - bufptr)); bufptr += len; printf("--------------------------------------------\npub[%lu]\n", i + 1); check(dump_lms_pub(bufptr, &len, buflim - bufptr)); bufptr += len; } return HAL_OK; } static hal_error_t dump_hss_pub(const uint8_t * const buf, const size_t max) { const uint8_t *bufptr = buf; const uint8_t * const buflim = buf + max; hexdump("L", bufptr, 4); uint32_t L; check(hal_xdr_decode_int(&bufptr, buflim, &L)); printf("--------------------------------------------\npubkey[0]\n"); size_t lms_len; check(dump_lms_pub(bufptr, &lms_len, buflim - bufptr)); bufptr += lms_len; return HAL_OK; } static hal_error_t dump_hss_sig(const uint8_t * const buf, const size_t max) { const uint8_t *bufptr = buf; const uint8_t * const buflim = buf + max; hexdump("Nspk", bufptr, 4); uint32_t Nspk; check(hal_xdr_decode_int(&bufptr, buflim, &Nspk)); for (size_t i = 0; i <= Nspk && bufptr < buflim; ++i) { printf("--------------------------------------------\nsig[%lu]\n", i); size_t lms_len; check(dump_lms_sig(bufptr, &lms_len, buflim - bufptr)); bufptr += lms_len; if (bufptr < buflim) { printf("--------------------------------------------\npubkey[%lu]\n", i + 1); check(dump_lms_pub(bufptr, &lms_len, buflim - bufptr)); bufptr += lms_len; } } return HAL_OK; } int main(int argc, char *argv[]) { char usage[] = "\ Usage: %s genkey [parameters]\n\ %s sign \n\ %s verify \n"; int fd; struct stat statbuf; size_t len; hal_error_t err; if (argc < 3) { fprintf(stderr, usage, argv[0], argv[0], argv[0]); return 1; } if (strcmp(argv[1], "genkey") == 0) { /* default parameter set */ size_t L = 2; lms_algorithm_t lms_type = lms_sha256_n32_h5; lmots_algorithm_t lmots_type = lmots_sha256_n32_w8; if (argc > 3) { int val[3]; for (int i = 0; i < 3; ++i) { char *str = strtok(i == 0 ? argv[3] : NULL, "/"); if (str == NULL) { fprintf(stderr, "genkey parameters are of the form \"L/h/w\", e.g. \"3/10/4\"\n"); return 1; } val[i] = atoi(str); } L = (size_t)val[0]; if (L < 1 || L > 8) { fprintf(stderr, "unsupported value of L (%d), must be 1-8\n", val[0]); return 1; } switch (val[1]) { case 5: lms_type = lms_sha256_n32_h5; break; case 10: lms_type = lms_sha256_n32_h10; break; case 15: lms_type = lms_sha256_n32_h15; break; case 20: lms_type = lms_sha256_n32_h20; break; case 25: lms_type = lms_sha256_n32_h25; break; default: fprintf(stderr, "unsupported value of h (%d), must be 5,10,15,20,25\n", val[1]); return 1; } switch (val[2]) { case 1: lmots_type = lmots_sha256_n32_w1; break; case 2: lmots_type = lmots_sha256_n32_w2; break; case 4: lmots_type = lmots_sha256_n32_w4; break; case 8: lmots_type = lmots_sha256_n32_w8; break; default: fprintf(stderr, "unsupported value of w (%d), must be 1,2,4,8\n", val[2]); return 1; } } uint8_t prv[hss_private_key_len(L, lms_type, lmots_type)]; size_t prv_len; if ((err = hss_generate_private_key(L, lms_type, lmots_type, prv, &prv_len, sizeof(prv))) != HAL_OK) { fprintf(stderr, "hss_generate_private_key: %s\n", hal_error_string(err)); return 1; } if (prv_len != sizeof(prv)) { fprintf(stderr, "hss_generate_private_key returned length %lu, expected %lu\n", prv_len, sizeof(prv)); return 1; } char fn[strlen(argv[2]) + 5]; strcpy(fn, argv[2]); strcat(fn, ".prv"); if ((fd = creat(fn, S_IRUSR|S_IWUSR)) == -1) { perror("creat prv"); return 1; } if ((len = write(fd, prv, sizeof(prv))) != sizeof(prv)) { fprintf(stderr, "write prv returned %lu, expected %lu\n", len, sizeof(prv)); return 1; } if (close(fd) != 0) { perror("close prv"); return 1; } uint8_t pub[hss_public_key_len(lms_type)]; if ((err = hss_generate_public_key(L, lms_type, lmots_type, prv, sizeof(prv), pub, &len, sizeof(pub))) != HAL_OK) { fprintf(stderr, "hss_generate_public_key: %s\n", hal_error_string(err)); return 1; } if (len != sizeof(pub)) { fprintf(stderr, "hss_generate_public_key returned length %lu, expected %lu\n", len, sizeof(pub)); return 1; } strcpy(fn, argv[2]); strcat(fn, ".pub"); if ((fd = creat(fn, S_IRUSR|S_IWUSR)) == -1) { perror("creat pub"); return 1; } if ((len = write(fd, pub, sizeof(pub))) != sizeof(pub)) { fprintf(stderr, "write pub returned %lu, expected %lu\n", len, sizeof(pub)); return 1; } if (close(fd) != 0) { perror("close pub"); return 1; } return 0; } else if (strcmp(argv[1], "sign") == 0) { if (argc < 4) { fprintf(stderr, usage, argv[0], argv[0], argv[0]); return 1; } char fn[strlen(argv[2]) + 5]; strcpy(fn, argv[2]); strcat(fn, ".prv"); if (stat(fn, &statbuf) != 0) { perror("stat prv"); return 1; } if ((fd = open(fn, O_RDONLY)) == -1) { perror("open prv"); return 1; } uint8_t prv[statbuf.st_size]; if ((len = read(fd, prv, sizeof(prv))) != sizeof(prv)) { fprintf(stderr, "read prv returned %lu, expected %lu\n", len, sizeof(prv)); return 1; } if (close(fd) != 0) { perror("close prv"); return 1; } strcpy(fn, argv[2]); strcat(fn, ".pub"); if (stat(fn, &statbuf) != 0) { perror("stat pub"); return 1; } if ((fd = open(fn, O_RDONLY)) == -1) { perror("open pub"); return 1; } uint8_t pub[statbuf.st_size]; if ((len = read(fd, pub, sizeof(pub))) != sizeof(pub)) { fprintf(stderr, "read pub returned %lu, expected %lu\n", len, sizeof(pub)); return 1; } if (close(fd) != 0) { perror("close pub"); return 1; } for (int i = 3; i < argc; ++i) { char *fn = argv[i]; printf("signing %s\n", fn); if (stat(fn, &statbuf) != 0) { perror("stat msg"); return 1; } if ((fd = open(fn, O_RDONLY)) == -1) { perror("open msg"); return 1; } uint8_t msg[statbuf.st_size]; if ((len = read(fd, msg, sizeof(msg))) != sizeof(msg)) { fprintf(stderr, "read msg returned %lu, expected %lu\n", len, sizeof(msg)); return 1; } if (close(fd) != 0) { perror("close msg"); return 1; } const uint8_t * pubptr = pub; const uint8_t * const publim = pub + sizeof(pub); uint32_t L; check(hal_xdr_decode_int(&pubptr, publim, &L)); lms_algorithm_t lms_type; check(hal_xdr_decode_int(&pubptr, publim, &lms_type)); lmots_algorithm_t lmots_type; check(hal_xdr_decode_int(&pubptr, publim, &lmots_type)); uint8_t sig[hss_signature_len(L, lms_type, lmots_type)]; if ((err = hss_sign(prv, sizeof(prv), msg, sizeof(msg), sig, &len, sizeof(sig))) != HAL_OK) { fprintf(stderr, "hss_sign: %s\n", hal_error_string(err)); return 1; } if (len != sizeof(sig)) { fprintf(stderr, "hss_sign returned length %lu, expected %lu\n", len, sizeof(sig)); return 1; } char sn[strlen(fn) + 5]; strcpy(sn, fn); strcat(sn, ".sig"); if ((fd = creat(sn, S_IRUSR|S_IWUSR)) == -1) { perror("creat sig"); return 1; } if ((len = write(fd, sig, sizeof(sig))) != sizeof(sig)) { fprintf(stderr, "write sig returned %lu, expected %lu\n", len, sizeof(sig)); return 1; } if (close(fd) != 0) { perror("close sig"); return 1; } } strcpy(fn, argv[2]); strcat(fn, ".prv"); if ((fd = creat(fn, S_IRUSR|S_IWUSR)) == -1) { perror("creat prv"); return 1; } if ((len = write(fd, prv, sizeof(prv))) != sizeof(prv)) { fprintf(stderr, "write prv returned %lu, expected %lu\n", len, sizeof(prv)); return 1; } if (close(fd) != 0) { perror("close prv"); return 1; } return 0; } else if (strcmp(argv[1], "verify") == 0) { if (argc < 4) { fprintf(stderr, usage, argv[0], argv[0], argv[0]); return 1; } char fn[strlen(argv[2]) + 5]; strcpy(fn, argv[2]); strcat(fn, ".pub"); if (stat(fn, &statbuf) != 0) { perror("stat pub"); return 1; } if ((fd = open(fn, O_RDONLY)) == -1) { perror("open pub"); return 1; } uint8_t pub[statbuf.st_size]; if ((len = read(fd, pub, sizeof(pub))) != sizeof(pub)) { fprintf(stderr, "read pub returned %lu, expected %lu\n", len, sizeof(pub)); return 1; } if (close(fd) != 0) { perror("close pub"); return 1; } int ret = 0; for (int i = 3; i < argc; ++i) { char *fn = argv[i]; printf("verifying %s\n", fn); if (stat(fn, &statbuf) != 0) { perror("stat msg"); return 1; } if ((fd = open(fn, O_RDONLY)) == -1) { perror("open msg"); return 1; } uint8_t msg[statbuf.st_size]; if ((len = read(fd, msg, sizeof(msg))) != sizeof(msg)) { fprintf(stderr, "read msg returned %lu, expected %lu\n", len, sizeof(msg)); return 1; } if (close(fd) != 0) { perror("close msg"); return 1; } char sn[strlen(fn) + 5]; strcpy(sn, fn); strcat(sn, ".sig"); if (stat(sn, &statbuf) != 0) { perror("stat sig"); return 1; } uint8_t sig[statbuf.st_size]; if ((fd = open(sn, O_RDONLY)) == -1) { perror("open sig"); return 1; } if ((len = read(fd, sig, sizeof(sig))) != sizeof(sig)) { fprintf(stderr, "write sig returned %lu, expected %lu\n", len, sizeof(sig)); return 1; } if (close(fd) != 0) { perror("close sig"); return 1; } if ((err = hss_verify(pub, sizeof(pub), msg, sizeof(msg), sig, sizeof(sig))) != HAL_OK) { fprintf(stderr, "hss_verify: %s\n", hal_error_string(err)); ret++; } else printf("signature verified\n"); } return ret; } else if (strcmp(argv[1], "read") == 0) { if (argc < 3) { fprintf(stderr, usage, argv[0], argv[0], argv[0]); return 1; } for (int i = 2; i < argc; ++i) { char *fn = argv[i]; printf("reading %s\n", fn); if (stat(fn, &statbuf) != 0) { perror("stat"); return 1; } if ((fd = open(fn, O_RDONLY)) == -1) { perror("open"); return 1; } uint8_t buf[statbuf.st_size]; if ((len = read(fd, buf, sizeof(buf))) != sizeof(buf)) { fprintf(stderr, "read returned %lu, expected %lu\n", len, sizeof(buf)); return 1; } if (close(fd) != 0) { perror("close"); return 1; } char *ext = strrchr(fn, '.'); if (strcmp(ext, ".prv") == 0) { if (dump_hss_prv(buf, sizeof(buf)) != HAL_OK) return 1; } else if (strcmp(ext, ".pub") == 0) { if (dump_hss_pub(buf, sizeof(buf)) != HAL_OK) return 1; } else if (strcmp(ext, ".sig") == 0) { if (dump_hss_sig(buf, sizeof(buf)) != HAL_OK) return 1; } else { fprintf(stderr, "unknown file type\n"); return 1; } } return 0; } fprintf(stderr, usage, argv[0], argv[0], argv[0]); return 1; }