diff options
Diffstat (limited to 'hashsig.c')
| -rw-r--r-- | hashsig.c | 1135 |
1 files changed, 573 insertions, 562 deletions
@@ -1,7 +1,7 @@ /* * hashsig.c * --------- - * Implementation of draft-mcgrew-hash-sigs-10.txt + * Implementation of draft-mcgrew-hash-sigs-15.txt * * Copyright (c) 2018, NORDUnet A/S All rights reserved. * @@ -33,13 +33,11 @@ */ #include "hal.h" -#include "hashsig.h" #include "ks.h" #include "asn1_internal.h" #include "xdr_internal.h" typedef struct { uint8_t bytes[32]; } bytestring32; -typedef struct { uint8_t bytes[16]; } bytestring16; #define D_PBLC 0x8080 #define D_MESG 0x8181 @@ -48,7 +46,7 @@ typedef struct { uint8_t bytes[16]; } bytestring16; #define u32str(X) htonl(X) #define u16str(X) htons(X) -#define u8str(X) (X & 0xff) +#define u8str(X) ((X) & 0xff) #define check(op) do { hal_error_t _err = (op); if (_err != HAL_OK) return _err; } while (0) @@ -73,19 +71,19 @@ static inline hal_error_t hal_xdr_decode_bytestring32(const uint8_t ** const inb return hal_xdr_decode_fixed_opaque(inbuf, limit, (uint8_t * const)value, sizeof(bytestring32)); } -static inline hal_error_t hal_xdr_encode_bytestring16(uint8_t ** const outbuf, const uint8_t * const limit, const bytestring16 *value) +static inline hal_error_t hal_xdr_encode_uuid(uint8_t ** const outbuf, const uint8_t * const limit, const hal_uuid_t *value) { - return hal_xdr_encode_fixed_opaque(outbuf, limit, (const uint8_t *)value, sizeof(bytestring16)); + return hal_xdr_encode_fixed_opaque(outbuf, limit, (const uint8_t *)value, sizeof(hal_uuid_t)); } -static inline hal_error_t hal_xdr_decode_bytestring16_ptr(const uint8_t ** const inbuf, const uint8_t * const limit, bytestring16 **value) +static inline hal_error_t hal_xdr_decode_uuid_ptr(const uint8_t ** const inbuf, const uint8_t * const limit, hal_uuid_t **value) { - return hal_xdr_decode_fixed_opaque_ptr(inbuf, limit, (const uint8_t ** const)value, sizeof(bytestring16)); + return hal_xdr_decode_fixed_opaque_ptr(inbuf, limit, (const uint8_t ** const)value, sizeof(hal_uuid_t)); } -static inline hal_error_t hal_xdr_decode_bytestring16(const uint8_t ** const inbuf, const uint8_t * const limit, bytestring16 * const value) +static inline hal_error_t hal_xdr_decode_uuid(const uint8_t ** const inbuf, const uint8_t * const limit, hal_uuid_t * const value) { - return hal_xdr_decode_fixed_opaque(inbuf, limit, (uint8_t * const)value, sizeof(bytestring16)); + return hal_xdr_decode_fixed_opaque(inbuf, limit, (uint8_t * const)value, sizeof(hal_uuid_t)); } /* ---------------------------------------------------------------- */ @@ -116,34 +114,34 @@ static inline hal_error_t hal_asn1_decode_size_t(size_t *np, const uint8_t * con } } -static inline hal_error_t hal_asn1_encode_lms_algorithm(const lms_algorithm_t type, uint8_t *der, size_t *der_len, const size_t der_max) +static inline hal_error_t hal_asn1_encode_lms_algorithm(const hal_lms_algorithm_t type, uint8_t *der, size_t *der_len, const size_t der_max) { return hal_asn1_encode_uint32((const uint32_t)type, der, der_len, der_max); } -static inline hal_error_t hal_asn1_decode_lms_algorithm(lms_algorithm_t *type, const uint8_t * const der, size_t *der_len, const size_t der_max) +static inline hal_error_t hal_asn1_decode_lms_algorithm(hal_lms_algorithm_t *type, const uint8_t * const der, size_t *der_len, const size_t der_max) { uint32_t n; hal_error_t err; if ((err = hal_asn1_decode_uint32(&n, der, der_len, der_max)) == HAL_OK) - *type = (lms_algorithm_t)n; + *type = (hal_lms_algorithm_t)n; return err; } -static inline hal_error_t hal_asn1_encode_lmots_algorithm(const lmots_algorithm_t type, uint8_t *der, size_t *der_len, const size_t der_max) +static inline hal_error_t hal_asn1_encode_lmots_algorithm(const hal_lmots_algorithm_t type, uint8_t *der, size_t *der_len, const size_t der_max) { return hal_asn1_encode_uint32((const uint32_t)type, der, der_len, der_max); } -static inline hal_error_t hal_asn1_decode_lmots_algorithm(lmots_algorithm_t *type, const uint8_t * const der, size_t *der_len, const size_t der_max) +static inline hal_error_t hal_asn1_decode_lmots_algorithm(hal_lmots_algorithm_t *type, const uint8_t * const der, size_t *der_len, const size_t der_max) { uint32_t n; hal_error_t err; if ((err = hal_asn1_decode_uint32(&n, der, der_len, der_max)) == HAL_OK) - *type = (lmots_algorithm_t)n; + *type = (hal_lmots_algorithm_t)n; return err; } @@ -158,16 +156,6 @@ static inline hal_error_t hal_asn1_decode_uuid(hal_uuid_t *data, const uint8_t * return hal_asn1_decode_octet_string((uint8_t *)data, sizeof(hal_uuid_t), der, der_len, der_max); } -static inline hal_error_t hal_asn1_encode_bytestring16(const bytestring16 * const data, uint8_t *der, size_t *der_len, const size_t der_max) -{ - return hal_asn1_encode_octet_string((const uint8_t * const)data, sizeof(bytestring16), der, der_len, der_max); -} - -static inline hal_error_t hal_asn1_decode_bytestring16(bytestring16 *data, const uint8_t * const der, size_t *der_len, const size_t der_max) -{ - return hal_asn1_decode_octet_string((uint8_t *)data, sizeof(bytestring16), der, der_len, der_max); -} - static inline hal_error_t hal_asn1_encode_bytestring32(const bytestring32 * const data, uint8_t *der, size_t *der_len, const size_t der_max) { return hal_asn1_encode_octet_string((const uint8_t * const)data, sizeof(bytestring32), der, der_len, der_max); @@ -185,44 +173,46 @@ static inline hal_error_t hal_asn1_decode_bytestring32(bytestring32 *data, const */ typedef const struct lmots_parameter_set { - lmots_algorithm_t type; - size_t n, w, p, ls; + hal_lmots_algorithm_t type; + size_t n, w, p, ls; } lmots_parameter_t; static lmots_parameter_t lmots_parameters[] = { - { lmots_sha256_n32_w1, 32, 1, 265, 7 }, - { lmots_sha256_n32_w2, 32, 2, 133, 6 }, - { lmots_sha256_n32_w4, 32, 4, 67, 4 }, - { lmots_sha256_n32_w8, 32, 8, 34, 0 }, + { HAL_LMOTS_SHA256_N32_W1, 32, 1, 265, 7 }, + { HAL_LMOTS_SHA256_N32_W2, 32, 2, 133, 6 }, + { HAL_LMOTS_SHA256_N32_W4, 32, 4, 67, 4 }, + { HAL_LMOTS_SHA256_N32_W8, 32, 8, 34, 0 }, }; typedef struct lmots_key { hal_key_type_t type; lmots_parameter_t *lmots; - bytestring16 I; + hal_uuid_t I; size_t q; bytestring32 * x; bytestring32 K; } lmots_key_t; -static inline lmots_parameter_t *lmots_select_parameter_set(const lmots_algorithm_t lmots_type) +static inline lmots_parameter_t *lmots_select_parameter_set(const hal_lmots_algorithm_t lmots_type) { - if (lmots_type < lmots_sha256_n32_w1 || lmots_type > lmots_sha256_n32_w8) + if (lmots_type < HAL_LMOTS_SHA256_N32_W1 || lmots_type > HAL_LMOTS_SHA256_N32_W8) return NULL; else - return &lmots_parameters[lmots_type - lmots_sha256_n32_w1]; + return &lmots_parameters[lmots_type - HAL_LMOTS_SHA256_N32_W1]; } static inline size_t lmots_private_key_len(lmots_parameter_t * const lmots) { /* u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1] */ - return 2 * sizeof(uint32_t) + sizeof(bytestring16) + (lmots->p * lmots->n); + return 2 * sizeof(uint32_t) + sizeof(hal_uuid_t) + (lmots->p * lmots->n); } +#if 0 /* currently unused */ static inline size_t lmots_public_key_len(lmots_parameter_t * const lmots) { /* u32str(type) || I || u32str(q) || K */ - return 2 * sizeof(uint32_t) + sizeof(bytestring16) + lmots->n; + return 2 * sizeof(uint32_t) + sizeof(hal_uuid_t) + lmots->n; } +#endif static inline size_t lmots_signature_len(lmots_parameter_t * const lmots) { @@ -235,31 +225,44 @@ static inline size_t lmots_signature_len(lmots_parameter_t * const lmots) * public key components (x and K). * Let the caller worry about storage. */ -static hal_error_t lmots_generate(lmots_key_t * const key) +static hal_error_t lmots_generate(lmots_key_t * const key, bytestring32 *seed) { if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_LMOTS || key->lmots == NULL || key->x == NULL) return HAL_ERROR_BAD_ARGUMENTS; -// Algorithm 0: Generating a Private Key - -// 3. set n and p according to the typecode and Table 1 - size_t n = key->lmots->n; size_t p = key->lmots->p; size_t w = key->lmots->w; -// 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 -// } + /* generate the private key */ - for (size_t i = 0; i < p; ++i) - check(hal_rpc_get_random(&key->x[i], n)); + if (seed == NULL) { + /* fill x[] with random goodness */ + for (size_t i = 0; i < p; ++i) + check(hal_rpc_get_random(&key->x[i], n)); + } -// Algorithm 1: Generating a One Time Signature Public Key From a -// Private Key + else { + /* use the pseudorandom key generation scheme */ + for (size_t i = 0; i < p; ++i) { + uint8_t statebuf[512]; + hal_hash_state_t *state = NULL; + uint32_t l; + uint16_t s; + uint8_t b; -// 4. compute the string K as follows: + /* x_q[i] = H(I || u32str(q) || u16str(i) || u8str(0xff) || SEED) */ + check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); + check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I))); + l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l))); + s = u16str(i); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s))); + b = u8str(0xff); check(hal_hash_update(state, (const uint8_t *)&b, sizeof(b))); + check(hal_hash_update(state, (const uint8_t *)seed, sizeof(bytestring32))); + check(hal_hash_finalize(state, (uint8_t *)&key->x[i], sizeof(bytestring32))); + } + } + + /* generate the public key */ uint8_t statebuf[512]; hal_hash_state_t *state = NULL; @@ -268,32 +271,21 @@ static hal_error_t lmots_generate(lmots_key_t * const key) uint16_t s; uint8_t b; -// for ( i = 0; i < p; i = i + 1 ) { for (size_t i = 0; i < p; ++i) { - -// tmp = x[i] - bytestring32 tmp; - memcpy(&tmp, &key->x[i], sizeof(tmp)); - -// for ( j = 0; j < 2^w - 1; j = j + 1 ) { + y[i] = key->x[i]; for (size_t j = 0; j < (1U << w) - 1; ++j) { - -// tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) + /* y[i] = H(I || u32str(q) || u16str(i) || u8str(j) || y[i]) */ check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I))); l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l))); s = u16str(i); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s))); b = u8str(j); check(hal_hash_update(state, (const uint8_t *)&b, sizeof(b))); - check(hal_hash_update(state, (const uint8_t *)&tmp, sizeof(tmp))); - check(hal_hash_finalize(state, (uint8_t *)&tmp, sizeof(tmp))); + check(hal_hash_update(state, (const uint8_t *)&y[i], sizeof(y[i]))); + check(hal_hash_finalize(state, (uint8_t *)&y[i], sizeof(y[i]))); } - -// y[i] = tmp - memcpy(&y[i], &tmp, sizeof(tmp)); -// } } -// K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1]) + /* K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1]) */ check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I))); l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l))); @@ -342,13 +334,6 @@ static hal_error_t lmots_sign(lmots_key_t *key, if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_LMOTS || msg == NULL || sig == NULL) return HAL_ERROR_BAD_ARGUMENTS; -// Algorithm 3: Generating a One Time Signature From a Private Key and a -// Message - -// 1. set type to the typecode of the algorithm -// -// 2. set n, p, and w according to the typecode and Table 1 - size_t n = key->lmots->n; size_t p = key->lmots->p; size_t w = key->lmots->w; @@ -356,15 +341,9 @@ static hal_error_t lmots_sign(lmots_key_t *key, if (sig_max < lmots_signature_len(key->lmots)) return HAL_ERROR_BAD_ARGUMENTS; -// 3. determine x, I and q from the private key -// -// 4. set C to a uniformly random n-byte string - bytestring32 C; check(hal_rpc_get_random(&C, n)); -// 5. compute the array y as follows: - uint8_t statebuf[512]; hal_hash_state_t *state = NULL; uint8_t Q[n + 2]; /* hash || 16-bit checksum */ @@ -372,7 +351,7 @@ static hal_error_t lmots_sign(lmots_key_t *key, uint16_t s; uint8_t b; -// Q = H(I || u32str(q) || u16str(D_MESG) || C || message) + /* Q = H(I || u32str(q) || u16str(D_MESG) || C || message) */ check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I))); l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l))); @@ -386,35 +365,22 @@ static hal_error_t lmots_sign(lmots_key_t *key, bytestring32 y[p]; -// for ( i = 0; i < p; i = i + 1 ) { for (size_t i = 0; i < p; ++i) { - -// a = coef(Q || Cksm(Q), i, w) uint8_t a = coef(Q, i, w); - -// tmp = x[i] - bytestring32 tmp; - memcpy(&tmp, &key->x[i], sizeof(tmp)); - -// for ( j = 0; j < a; j = j + 1 ) { + y[i] = key->x[i]; for (size_t j = 0; j < (size_t)a; ++j) { - -// tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) + /* y[i] = H(I || u32str(q) || u16str(i) || u8str(j) || y[i]) */ check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I))); l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l))); s = u16str(i); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s))); b = u8str(j); check(hal_hash_update(state, (const uint8_t *)&b, sizeof(b))); - check(hal_hash_update(state, (const uint8_t *)&tmp, sizeof(tmp))); - check(hal_hash_finalize(state, (uint8_t *)&tmp, sizeof(tmp))); -// } + check(hal_hash_update(state, (const uint8_t *)&y[i], sizeof(y[i]))); + check(hal_hash_finalize(state, (uint8_t *)&y[i], sizeof(y[i]))); } - -// y[i] = tmp - memcpy(&y[i], &tmp, sizeof(tmp)); } -// 6. return u32str(type) || C || y[0] || ... || y[p-1] + /* sig = 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, key->lmots->type)); @@ -440,45 +406,26 @@ static hal_error_t lmots_public_key_candidate(const lmots_key_t * const key, * at the start of lms_verify. */ -// 1. if the signature is not at least four bytes long, return INVALID -// -// 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; uint32_t sigtype; check(hal_xdr_decode_int(&sigptr, siglim, &sigtype)); -// b. if sigtype is not equal to pubtype, return INVALID - - if ((lmots_algorithm_t)sigtype != key->lmots->type) + if ((hal_lmots_algorithm_t)sigtype != key->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 = key->lmots->n; size_t p = key->lmots->p; size_t w = key->lmots->w; -// 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 - uint8_t statebuf[512]; hal_hash_state_t *state = NULL; uint8_t Q[n + 2]; /* hash || 16-bit checksum */ @@ -486,7 +433,7 @@ static hal_error_t lmots_public_key_candidate(const lmots_key_t * const key, uint16_t s; uint8_t b; -// Q = H(I || u32str(q) || u16str(D_MESG) || C || message) + /* Q = H(I || u32str(q) || u16str(D_MESG) || C || message) */ check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I))); l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l))); @@ -500,36 +447,22 @@ static hal_error_t lmots_public_key_candidate(const lmots_key_t * const key, bytestring32 z[p]; -// for ( i = 0; i < p; i = i + 1 ) { for (size_t i = 0; i < p; ++i) { - -// a = coef(Q || Cksm(Q), i, w) uint8_t a = coef(Q, i, w); - -// tmp = y[i] - bytestring32 tmp; - memcpy(&tmp, &y[i], sizeof(tmp)); - -// for ( j = a; j < 2^w - 1; j = j + 1 ) { + z[i] = y[i]; for (size_t j = (size_t)a; j < (1U << w) - 1; ++j) { - -// tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) + /* z[i] = H(I || u32str(q) || u16str(i) || u8str(j) || z[i]) */ check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I))); l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l))); s = u16str(i); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s))); b = u8str(j); check(hal_hash_update(state, (const uint8_t *)&b, sizeof(b))); - check(hal_hash_update(state, (const uint8_t *)&tmp, sizeof(tmp))); - check(hal_hash_finalize(state, (uint8_t *)&tmp, sizeof(tmp))); -// } + check(hal_hash_update(state, (const uint8_t *)&z[i], sizeof(z[i]))); + check(hal_hash_finalize(state, (uint8_t *)&z[i], sizeof(z[i]))); } - -// z[i] = tmp - memcpy(&z[i], &tmp, sizeof(tmp)); -// } } -// Kc = H(I || u32str(q) || u16str(D_PBLC) || z[0] || z[1] || ... || z[p-1]) + /* Kc = H(I || u32str(q) || u16str(D_PBLC) || z[] */ check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I))); l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l))); @@ -538,7 +471,6 @@ static hal_error_t lmots_public_key_candidate(const lmots_key_t * const key, check(hal_hash_update(state, (const uint8_t *)&z[i], sizeof(z[i]))); check(hal_hash_finalize(state, (uint8_t *)&key->K, sizeof(key->K))); -// 4. return Kc return HAL_OK; } @@ -549,17 +481,15 @@ static hal_error_t lmots_private_key_to_der(const lmots_key_t * const key, if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_LMOTS) return HAL_ERROR_BAD_ARGUMENTS; - // u32str(lmots_type) || I || u32str(q) || K || x[0] || x[1] || ... || x[p-1] + /* u32str(lmots_type) || I || u32str(q) || K || x[] */ /* K is not an integral part of the private key, but we store it to speed up restart */ - /* - * Calculate data length. - */ + /* Calculate data length. */ size_t len, vlen = 0, hlen; check(hal_asn1_encode_lmots_algorithm(key->lmots->type, NULL, &len, 0)); vlen += len; - check(hal_asn1_encode_bytestring16(&key->I, NULL, &len, 0)); vlen += len; + check(hal_asn1_encode_uuid(&key->I, NULL, &len, 0)); vlen += len; check(hal_asn1_encode_size_t(key->q, NULL, &len, 0)); vlen += len; check(hal_asn1_encode_bytestring32(&key->K, NULL, &len, 0)); vlen += len; for (size_t i = 0; i < key->lmots->p; ++i) { @@ -574,9 +504,7 @@ static hal_error_t lmots_private_key_to_der(const lmots_key_t * const key, if (der == NULL) return HAL_OK; - /* - * Encode data. - */ + /* Encode data. */ check(hal_asn1_encode_header(ASN1_SEQUENCE, vlen, der, &hlen, der_max)); @@ -584,7 +512,7 @@ static hal_error_t lmots_private_key_to_der(const lmots_key_t * const key, memset(d, 0, vlen); check(hal_asn1_encode_lmots_algorithm(key->lmots->type, d, &len, vlen)); d += len; vlen -= len; - check(hal_asn1_encode_bytestring16(&key->I, d, &len, vlen)); d += len; vlen -= len; + check(hal_asn1_encode_uuid(&key->I, d, &len, vlen)); d += len; vlen -= len; check(hal_asn1_encode_size_t(key->q, d, &len, vlen)); d += len; vlen -= len; check(hal_asn1_encode_bytestring32(&key->K, d, &len, vlen)); d += len; vlen -= len; for (size_t i = 0; i < key->lmots->p; ++i) { @@ -627,12 +555,12 @@ static hal_error_t lmots_private_key_from_der(lmots_key_t *key, const uint8_t *d = privkey + hlen; size_t len; - // u32str(lmots_type) || I || u32str(q) || K || x[0] || x[1] || ... || x[p-1] + /* u32str(lmots_type) || I || u32str(q) || K || x[] */ - lmots_algorithm_t lmots_type; + hal_lmots_algorithm_t lmots_type; check(hal_asn1_decode_lmots_algorithm(&lmots_type, d, &len, vlen)); d += len; vlen -= len; key->lmots = lmots_select_parameter_set(lmots_type); - check(hal_asn1_decode_bytestring16(&key->I, d, &len, vlen)); d += len; vlen -= len; + check(hal_asn1_decode_uuid(&key->I, d, &len, vlen)); d += len; vlen -= len; check(hal_asn1_decode_size_t(&key->q, d, &len, vlen)); d += len; vlen -= len; check(hal_asn1_decode_bytestring32(&key->K, d, &len, vlen)); d += len; vlen -= len; if (key->x != NULL) { @@ -655,15 +583,15 @@ static hal_error_t lmots_private_key_from_der(lmots_key_t *key, */ typedef const struct lms_parameter_set { - lms_algorithm_t type; - size_t m, h; + hal_lms_algorithm_t type; + size_t m, h; } lms_parameter_t; static lms_parameter_t lms_parameters[] = { - { lms_sha256_n32_h5, 32, 5 }, - { lms_sha256_n32_h10, 32, 10 }, - { lms_sha256_n32_h15, 32, 15 }, - { lms_sha256_n32_h20, 32, 20 }, - { lms_sha256_n32_h25, 32, 25 }, + { HAL_LMS_SHA256_N32_H5, 32, 5 }, + { HAL_LMS_SHA256_N32_H10, 32, 10 }, + { HAL_LMS_SHA256_N32_H15, 32, 15 }, + { HAL_LMS_SHA256_N32_H20, 32, 20 }, + { HAL_LMS_SHA256_N32_H25, 32, 25 }, }; typedef struct lms_key { @@ -671,8 +599,9 @@ typedef struct lms_key { size_t level; lms_parameter_t *lms; lmots_parameter_t *lmots; - bytestring16 I; + hal_uuid_t I; size_t q; /* index of next lmots signing key */ + size_t q_end; hal_uuid_t *lmots_keys; /* private key components */ bytestring32 *T; /* public key components */ bytestring32 T1; /* copy of T[1] */ @@ -682,12 +611,12 @@ typedef struct lms_key { size_t signature_len; } lms_key_t; -static inline lms_parameter_t *lms_select_parameter_set(const lms_algorithm_t lms_type) +static inline lms_parameter_t *lms_select_parameter_set(const hal_lms_algorithm_t lms_type) { - if (lms_type < lms_sha256_n32_h5 || lms_type > lms_sha256_n32_h25) + if (lms_type < HAL_LMS_SHA256_N32_H5 || lms_type > HAL_LMS_SHA256_N32_H25) return NULL; else - return &lms_parameters[lms_type - lms_sha256_n32_h5]; + return &lms_parameters[lms_type - HAL_LMS_SHA256_N32_H5]; } static inline size_t lms_public_key_len(lms_parameter_t * const lms) @@ -703,46 +632,68 @@ static inline size_t lms_signature_len(lms_parameter_t * const lms, lmots_parame } #if RPC_CLIENT == RPC_CLIENT_LOCAL -/* Given a key with most fields filled in, generate the lms private and - * public key components. - * Let the caller worry about storage. - */ -static hal_error_t lms_generate(lms_key_t *key) +static hal_error_t lms_compute_T_leaf(lms_key_t *key, lmots_key_t *lmots_key) { - if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_LMS || key->lms == NULL || key->lmots == NULL || key->lmots_keys == NULL || key->T == NULL) - return HAL_ERROR_BAD_ARGUMENTS; + /* compute T[r] = H(I || u32str(r) || u16str(D_LEAF) || K) */ + size_t r = (1U << key->lms->h) + lmots_key->q; + uint8_t statebuf[512]; + hal_hash_state_t *state = NULL; + check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); + check(hal_hash_update(state, (const uint8_t *)&lmots_key->I, sizeof(lmots_key->I))); + uint32_t l = u32str(r); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l))); + uint16_t s = u16str(D_LEAF); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s))); + check(hal_hash_update(state, (const uint8_t *)&lmots_key->K, sizeof(lmots_key->K))); + check(hal_hash_finalize(state, (uint8_t *)&key->T[r], sizeof(key->T[r]))); + + return HAL_OK; +} + +static hal_error_t lms_compute_T_intr(lms_key_t *key) +{ + /* generate the rest of T[r] = H(I || u32str(r) || u16str(D_INTR) || T[2*r] || T[2*r+1]) */ + for (size_t r = (1U << key->lms->h) - 1; r > 0; --r) { + uint8_t statebuf[512]; + hal_hash_state_t *state = NULL; + check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); + check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I))); + uint32_t l = u32str(r); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l))); + uint16_t s = u16str(D_INTR); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s))); + check(hal_hash_update(state, (const uint8_t *)&key->T[2*r], sizeof(key->T[r]))); + check(hal_hash_update(state, (const uint8_t *)&key->T[2*r+1], sizeof(key->T[r]))); + check(hal_hash_finalize(state, (uint8_t *)&key->T[r], sizeof(key->T[r]))); + hal_task_yield_maybe(); + } - check(hal_uuid_gen((hal_uuid_t *)&key->I)); - key->q = 0; + return HAL_OK; +} +static hal_error_t lms_generate_lmots(lms_key_t *key, size_t q, bytestring32 *seed) +{ bytestring32 x[key->lmots->p]; lmots_key_t lmots_key = { .type = HAL_KEY_TYPE_HASHSIG_LMOTS, .lmots = key->lmots, + .I = key->I, + .q = q, .x = x }; - memcpy(&lmots_key.I, &key->I, sizeof(key->I)); - hal_pkey_slot_t slot = { - .type = HAL_KEY_TYPE_HASHSIG_LMOTS, - .curve = HAL_CURVE_NONE, - .flags = HAL_KEY_FLAG_USAGE_DIGITALSIGNATURE | ((key->level == 0) ? HAL_KEY_FLAG_TOKEN: 0) - }; - hal_ks_t *ks = (key->level == 0) ? hal_ks_token : hal_ks_volatile; + /* generate the lmots private and public key components */ + check(lmots_generate(&lmots_key, seed)); - uint8_t statebuf[512]; - hal_hash_state_t *state = NULL; - uint32_t l; - uint16_t s; - size_t h2 = (1 << key->lms->h); - - /* private key - array of lmots key names */ - for (size_t q = 0; q < h2; ++q) { - /* generate the lmots private and public key components */ - lmots_key.q = q; - check(lmots_generate(&lmots_key)); + /* Note: we have to generate all the lmots keys, even if q > 0 or + * q_end < 2^h, because we need them to calculate T[]. + * We just don't need to store the ones that are out of range. + */ + if (q >= key->q && q < key->q_end) { /* store the lmots key */ + hal_ks_t *ks = (key->level == 0) ? hal_ks_token : hal_ks_volatile; + hal_pkey_slot_t slot = { + .type = HAL_KEY_TYPE_HASHSIG_LMOTS, + .curve = HAL_CURVE_NONE, + .flags = HAL_KEY_FLAG_USAGE_DIGITALSIGNATURE | ((key->level == 0) ? HAL_KEY_FLAG_TOKEN: 0) + }; uint8_t der[lmots_private_key_to_der_len(&lmots_key)]; size_t der_len; check(lmots_private_key_to_der(&lmots_key, der, &der_len, sizeof(der))); @@ -753,42 +704,53 @@ static hal_error_t lms_generate(lms_key_t *key) if (err != HAL_OK) return err; /* record the lmots keystore name */ - memcpy(&key->lmots_keys[q], &slot.name, sizeof(slot.name)); + key->lmots_keys[q] = slot.name; + } + else + memset(&x, 0, sizeof(x)); - /* compute T[r] = H(I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[r-2^h]) */ - size_t r = h2 + q; - check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); - check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I))); - l = u32str(r); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l))); - s = u16str(D_LEAF); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s))); - check(hal_hash_update(state, (const uint8_t *)&lmots_key.K, sizeof(lmots_key.K))); - check(hal_hash_finalize(state, (uint8_t *)&key->T[r], sizeof(key->T[r]))); + /* compute T[r] = H(I || u32str(r) || u16str(D_LEAF) || K) */ + check(lms_compute_T_leaf(key, &lmots_key)); + + return HAL_OK; +} + +/* Given a key with most fields filled in, generate the lms private and + * public key components. + * Let the caller worry about storage. + */ +static hal_error_t lms_generate(lms_key_t *key, bytestring32 *seed) +{ + if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_LMS || + key->lms == NULL || key->lmots == NULL || + key->lmots_keys == NULL || key->T == NULL) + return HAL_ERROR_BAD_ARGUMENTS; + + hal_uuid_t I_0 = {{0}}; + if (hal_uuid_cmp(&key->I, &I_0) == 0) + check(hal_uuid_gen(&key->I)); + + /* private key - array of lmots key names */ + for (size_t q = 0; q < (1U << key->lms->h); ++q) { + check(lms_generate_lmots(key, q, seed)); hal_task_yield_maybe(); } /* generate the rest of T[r] = H(I || u32str(r) || u16str(D_INTR) || T[2*r] || T[2*r+1]) */ - for (size_t r = h2 - 1; r > 0; --r) { - check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); - check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I))); - l = u32str(r); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l))); - s = u16str(D_INTR); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s))); - check(hal_hash_update(state, (const uint8_t *)&key->T[2*r], sizeof(key->T[r]))); - check(hal_hash_update(state, (const uint8_t *)&key->T[2*r+1], sizeof(key->T[r]))); - check(hal_hash_finalize(state, (uint8_t *)&key->T[r], sizeof(key->T[r]))); - hal_task_yield_maybe(); - } + check(lms_compute_T_intr(key)); - memcpy(&key->T1, &key->T[1], sizeof(key->T1)); + key->T1 = key->T[1]; /* generate the XDR encoding of the public key, which will be signed * by the previous lms key */ uint8_t *pubkey = key->pubkey; const uint8_t * const publim = key->pubkey + key->pubkey_len; - // u32str(lms_type) || u32str(lmots_type) || I || T[1] + + /* u32str(lms_type) || u32str(lmots_type) || I || T[1] */ check(hal_xdr_encode_int(&pubkey, publim, key->lms->type)); check(hal_xdr_encode_int(&pubkey, publim, key->lmots->type)); - check(hal_xdr_encode_bytestring16(&pubkey, publim, &key->I)); + check(hal_xdr_encode_uuid(&pubkey, publim, &key->I)); check(hal_xdr_encode_bytestring32(&pubkey, publim, &key->T1)); return HAL_OK; @@ -796,18 +758,21 @@ static hal_error_t lms_generate(lms_key_t *key) static hal_error_t lms_delete(const lms_key_t * const key) { - hal_pkey_slot_t slot = {0}; hal_ks_t *ks = (key->level == 0) ? hal_ks_token : hal_ks_volatile; + hal_pkey_slot_t slot = {{0}}; + hal_uuid_t uuid_0 = {{0}}; /* delete the lmots keys */ for (size_t i = 0; i < (1U << key->lms->h); ++i) { - memcpy(&slot.name, &key->lmots_keys[i], sizeof(slot.name)); - check(hal_ks_delete(ks, &slot)); - hal_task_yield_maybe(); + if (hal_uuid_cmp(&key->lmots_keys[i], &uuid_0) != 0) { + slot.name = key->lmots_keys[i]; + (void)hal_ks_delete(ks, &slot); + hal_task_yield_maybe(); + } } /* delete the lms key */ - memcpy(&slot.name, &key->I, sizeof(slot.name)); + slot.name = key->I; return hal_ks_delete(ks, &slot); } @@ -821,7 +786,7 @@ static hal_error_t lms_sign(lms_key_t * const key, if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_LMS || msg == NULL || sig == NULL) return HAL_ERROR_BAD_ARGUMENTS; - if (key->q >= (1U << key->lms->h)) + if (key->q >= key->q_end) return HAL_ERROR_HASHSIG_KEY_EXHAUSTED; if (sig_max < lms_signature_len(key->lms, key->lmots)) @@ -834,9 +799,9 @@ static hal_error_t lms_sign(lms_key_t * const key, check(hal_xdr_encode_int(&sigptr, siglim, key->q)); /* fetch and decode the lmots signing key from the keystore */ - hal_pkey_slot_t slot; - memset(&slot, 0, sizeof(slot)); - memcpy(&slot.name, &key->lmots_keys[key->q], sizeof(slot.name)); + hal_pkey_slot_t slot = { + .name = key->lmots_keys[key->q] + }; lmots_key_t lmots_key; memset(&lmots_key, 0, sizeof(lmots_key)); @@ -851,7 +816,7 @@ static hal_error_t lms_sign(lms_key_t * const key, check(lmots_private_key_from_der(&lmots_key, der, der_len)); memset(&der, 0, sizeof(der)); - //? check lmots_type and I vs. lms key? + /* check lmots_type and I vs. lms key? */ /* generate the lmots signature */ size_t lmots_sig_len; @@ -873,7 +838,7 @@ static hal_error_t lms_sign(lms_key_t * const key, check(lms_private_key_to_der(key, der, &der_len, sizeof(der))); slot.type = HAL_KEY_TYPE_HASHSIG_LMS; slot.flags = HAL_KEY_FLAG_USAGE_DIGITALSIGNATURE | ((key->level == 0) ? HAL_KEY_FLAG_TOKEN : 0); - memcpy(&slot.name, &key->I, sizeof(slot.name)); + slot.name = key->I; check(hal_ks_rewrite_der(ks, &slot, der, der_len)); return HAL_OK; @@ -899,34 +864,9 @@ static hal_error_t lms_verify(const lms_key_t * const key, if (sig_len != lms_signature_len(key->lms, key->lmots)) return HAL_ERROR_INVALID_SIGNATURE; -// Algorithm 6: LMS Signature Verification -// -// 1. if the public key is not at least eight bytes long, return -// INVALID -// -// 2. parse pubtype, I, and T[1] from the public key as follows: -// -// a. pubtype = strTou32(first 4 bytes of public key) -// -// b. ots_typecode = strTou32(next 4 bytes of public key) -// -// c. set m according to pubtype, based on Table 2 -// -// d. if the public key is not exactly 24 + m bytes -// long, return INVALID -// -// e. I = next 16 bytes of the public key -// -// f. T[1] = next m bytes of the public key -// -// 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(key, msg, msg_len, sig, sig_len, &Tc)); -// 4. if Tc is equal to T[1], return VALID; otherwise, return INVALID - return (memcmp(&Tc, &key->T1, sizeof(Tc)) ? HAL_ERROR_INVALID_SIGNATURE : HAL_OK); } @@ -935,100 +875,54 @@ static hal_error_t lms_public_key_candidate(const lms_key_t * const key, 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 - /* XXX and pubotstype */ - -// 1. if the signature is not at least eight bytes long, return INVALID -// -// 2. parse sigtype, q, ots_signature, and path from the signature as -// follows: -// -// a. q = strTou32(first 4 bytes of signature) - const uint8_t *sigptr = sig; const uint8_t * const siglim = sig + sig_len; uint32_t q; check(hal_xdr_decode_int(&sigptr, siglim, &q)); -// b. otssigtype = strTou32(next 4 bytes of signature) - uint32_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 ((lmots_algorithm_t)otssigtype != key->lmots->type) + if ((hal_lmots_algorithm_t)otssigtype != key->lmots->type) 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 -// -// e. ots_signature = bytes 8 through 8 + n * (p + 1) - 1 of signature - - /* XXX Technically, this is also wrong - 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(key->lmots); -// f. sigtype = strTou32(4 bytes of signature at location 8 + n * (p + 1)) - uint32_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 ((lms_algorithm_t)sigtype != key->lms->type) + if ((hal_lms_algorithm_t)sigtype != key->lms->type) return HAL_ERROR_INVALID_SIGNATURE; -// g. set m, h according to sigtype and Table 2 - size_t m = key->lms->m; size_t h = key->lms->h; size_t h2 = (1 << key->lms->h); -// h. if q >= 2^h or the signature is not exactly 12 + n * (p + 1) + m * h bytes long, return INVALID - if (q >= h2) 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 - lmots_key_t lmots_key = { .type = HAL_KEY_TYPE_HASHSIG_LMOTS, .lmots = key->lmots, + .I = key->I, .q = q }; - memcpy(&lmots_key.I, &key->I, sizeof(lmots_key.I)); check(lmots_public_key_candidate(&lmots_key, msg, msg_len, ots_signature, lmots_signature_len(key->lmots))); -// 4. compute the candidate LMS root value Tc as follows: - uint8_t statebuf[512]; hal_hash_state_t *state = NULL; uint32_t l; uint16_t s; -// node_num = 2^h + q size_t r = h2 + q; -// tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc) + /* tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc) */ bytestring32 tmp; check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); check(hal_hash_update(state, (const uint8_t *)&lmots_key.I, sizeof(lmots_key.I))); @@ -1037,15 +931,8 @@ static hal_error_t lms_public_key_candidate(const lms_key_t * const key, check(hal_hash_update(state, (const uint8_t *)&lmots_key.K, sizeof(lmots_key.K))); check(hal_hash_finalize(state, (uint8_t *)&tmp, sizeof(tmp))); -// 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 -// } + /* odd nodes: tmp = H(I || u32str(node_num/2) || u16str(D_INTR) || path[i] || tmp) */ + /* even nodes: tmp = H(I || u32str(node_num/2) || u16str(D_INTR) || tmp || path[i]) */ for (size_t i = 0; r > 1; r /= 2, ++i) { check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf))); check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I))); @@ -1062,8 +949,7 @@ static hal_error_t lms_public_key_candidate(const lms_key_t * const key, check(hal_hash_finalize(state, (uint8_t *)&tmp, sizeof(tmp))); } -// Tc = tmp - memcpy(Tc, &tmp, sizeof(*Tc)); + *Tc = tmp; return HAL_OK; } @@ -1075,18 +961,17 @@ static hal_error_t lms_private_key_to_der(const lms_key_t * const key, if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_LMS) return HAL_ERROR_BAD_ARGUMENTS; - /* - * Calculate data length. - */ + /* u32str(lms_type) || u32str(lmots_type) || I || q || q_end */ - // u32str(lms_type) || u32str(lmots_type) || I || q + /* Calculate data length. */ size_t len, vlen = 0, hlen; check(hal_asn1_encode_lms_algorithm(key->lms->type, NULL, &len, 0)); vlen += len; check(hal_asn1_encode_lmots_algorithm(key->lmots->type, NULL, &len, 0)); vlen += len; - check(hal_asn1_encode_bytestring16(&key->I, NULL, &len, 0)); vlen += len; + check(hal_asn1_encode_uuid(&key->I, NULL, &len, 0)); vlen += len; check(hal_asn1_encode_size_t(key->q, NULL, &len, 0)); vlen += len; + check(hal_asn1_encode_size_t(key->q_end, NULL, &len, 0)); vlen += len; check(hal_asn1_encode_header(ASN1_SEQUENCE, vlen, NULL, &hlen, 0)); @@ -1096,9 +981,7 @@ static hal_error_t lms_private_key_to_der(const lms_key_t * const key, if (der == NULL) return HAL_OK; - /* - * Encode data. - */ + /* Encode data. */ check(hal_asn1_encode_header(ASN1_SEQUENCE, vlen, der, &hlen, der_max)); @@ -1107,8 +990,9 @@ static hal_error_t lms_private_key_to_der(const lms_key_t * const key, check(hal_asn1_encode_lms_algorithm(key->lms->type, d, &len, vlen)); d += len; vlen -= len; check(hal_asn1_encode_lmots_algorithm(key->lmots->type, d, &len, vlen)); d += len; vlen -= len; - check(hal_asn1_encode_bytestring16(&key->I, d, &len, vlen)); d += len; vlen -= len; + check(hal_asn1_encode_uuid(&key->I, d, &len, vlen)); d += len; vlen -= len; check(hal_asn1_encode_size_t(key->q, d, &len, vlen)); d += len; vlen -= len; + check(hal_asn1_encode_size_t(key->q_end, d, &len, vlen)); d += len; vlen -= len; return hal_asn1_encode_pkcs8_privatekeyinfo(hal_asn1_oid_mts_hashsig, hal_asn1_oid_mts_hashsig_len, NULL, 0, der, d - der, der, der_len, der_max); @@ -1126,6 +1010,8 @@ static hal_error_t lms_private_key_from_der(lms_key_t *key, if (key == NULL || der == NULL) return HAL_ERROR_BAD_ARGUMENTS; + memset(key, 0, sizeof(*key)); + key->type = HAL_KEY_TYPE_HASHSIG_LMS; size_t hlen, vlen, alg_oid_len, curve_oid_len, privkey_len; @@ -1146,16 +1032,17 @@ static hal_error_t lms_private_key_from_der(lms_key_t *key, const uint8_t *d = privkey + hlen; size_t n; - // u32str(lms_type) || u32str(lmots_type) || I || q + /* u32str(lms_type) || u32str(lmots_type) || I || q || q_end */ - lms_algorithm_t lms_type; + hal_lms_algorithm_t lms_type; check(hal_asn1_decode_lms_algorithm(&lms_type, d, &n, vlen)); d += n; vlen -= n; key->lms = lms_select_parameter_set(lms_type); - lmots_algorithm_t lmots_type; + hal_lmots_algorithm_t lmots_type; check(hal_asn1_decode_lmots_algorithm(&lmots_type, d, &n, vlen)); d += n; vlen -= n; key->lmots = lmots_select_parameter_set(lmots_type); - check(hal_asn1_decode_bytestring16(&key->I, d, &n, vlen)); d += n; vlen -= n; + check(hal_asn1_decode_uuid(&key->I, d, &n, vlen)); d += n; vlen -= n; check(hal_asn1_decode_size_t(&key->q, d, &n, vlen)); d += n; vlen -= n; + check(hal_asn1_decode_size_t(&key->q_end, d, &n, vlen)); d += n; vlen -= n; if (d != privkey + privkey_len) return HAL_ERROR_ASN1_PARSE_FAILED; @@ -1183,8 +1070,10 @@ struct hal_hashsig_key { size_t L; lms_parameter_t *lms; lmots_parameter_t *lmots; - bytestring16 I; + hal_uuid_t I; + size_t q_start, q_end; bytestring32 T1; + bytestring32 seed; lms_key_t *lms_keys; }; @@ -1192,11 +1081,23 @@ const size_t hal_hashsig_key_t_size = sizeof(hss_key_t); static hss_key_t *hss_keys = NULL; +static hss_key_t *hss_find(hal_uuid_t *I) +{ + for (hss_key_t *key = hss_keys; key != NULL; key = key->next) { + if (memcmp(&key->I, I, sizeof(*I)) == 0) + return key; + } + + return NULL; +} + +#if 0 /* currently unused */ static inline size_t hss_public_key_len(lms_parameter_t * const lms) { /* L || pub[0] */ return sizeof(uint32_t) + lms_public_key_len(lms); } +#endif static inline size_t hss_signature_len(const size_t L, lms_parameter_t * const lms, lmots_parameter_t * const lmots) { @@ -1205,8 +1106,8 @@ static inline size_t hss_signature_len(const size_t L, lms_parameter_t * const l } size_t hal_hashsig_signature_len(const size_t L, - const lms_algorithm_t lms_type, - const lmots_algorithm_t lmots_type) + const hal_lms_algorithm_t lms_type, + const hal_lmots_algorithm_t lmots_type) { lms_parameter_t * const lms = lms_select_parameter_set(lms_type); if (lms == NULL) @@ -1219,7 +1120,7 @@ size_t hal_hashsig_signature_len(const size_t L, return hss_signature_len(L, lms, lmots); } -size_t hal_hashsig_lmots_private_key_len(const lmots_algorithm_t lmots_type) +size_t hal_hashsig_lmots_private_key_len(const hal_lmots_algorithm_t lmots_type) { lmots_parameter_t * const lmots = lmots_select_parameter_set(lmots_type); if (lmots == NULL) @@ -1241,25 +1142,18 @@ static inline void *gnaw(uint8_t **mem, size_t *len, const size_t size) return ret; } -static hal_error_t hss_alloc(hal_hashsig_key_t **key_, - const size_t L, - const lms_algorithm_t lms_type, - const lmots_algorithm_t lmots_type) +static hal_error_t hss_alloc(hal_hashsig_key_t **key_) { - if (key_ == NULL) + if (key_ == NULL || *key_ == NULL || + (*key_)->type != HAL_KEY_TYPE_HASHSIG_PRIVATE || + (*key_)->L == 0 || (*key_)->L > 8 || + (*key_)->lms == NULL || (*key_)->lmots == NULL) return HAL_ERROR_BAD_ARGUMENTS; - if (L == 0 || L > 8) - return HAL_ERROR_BAD_ARGUMENTS; - - lms_parameter_t *lms = lms_select_parameter_set(lms_type); - if (lms == NULL) - return HAL_ERROR_BAD_ARGUMENTS; - size_t h2 = (1 << lms->h); - - lmots_parameter_t *lmots = lmots_select_parameter_set(lmots_type); - if (lmots == NULL) - return HAL_ERROR_BAD_ARGUMENTS; + size_t L = (*key_)->L; + lms_parameter_t *lms = (*key_)->lms; + lmots_parameter_t *lmots = (*key_)->lmots; + size_t h2 = (1U << lms->h); /* w=1 fails on the Alpha, because the key exceeds the keystore block * size. The XDR encoding of the key is going to differ from the DER @@ -1294,114 +1188,163 @@ static hal_error_t hss_alloc(hal_hashsig_key_t **key_, memset(mem, 0, len); /* allocate the key that will stay in working memory */ - hss_key_t *key = gnaw(&mem, &len, sizeof(hss_key_t)); + hss_key_t *key = gnaw(&mem, &len, sizeof(*key)); + + /* initialize it from the transitory key */ + *key = **key_; *key_ = key; - key->type = HAL_KEY_TYPE_HASHSIG_PRIVATE; - key->L = L; - key->lms = lms; - key->lmots = lmots; - /* add to the list of active keys */ + /* add the in-memory key to the list of active keys */ key->next = hss_keys; hss_keys = key; /* allocate the list of lms trees */ key->lms_keys = gnaw(&mem, &len, L * sizeof(lms_key_t)); for (size_t i = 0; i < L; ++i) { - /* XXX some of this is redundant to lms_private_key_from_der */ lms_key_t * lms_key = &key->lms_keys[i]; lms_key->type = HAL_KEY_TYPE_HASHSIG_LMS; lms_key->lms = lms; lms_key->lmots = lmots; lms_key->level = i; - lms_key->lmots_keys = (hal_uuid_t *)gnaw(&mem, &len, h2 * sizeof(hal_uuid_t)); + lms_key->lmots_keys = gnaw(&mem, &len, h2 * sizeof(hal_uuid_t)); lms_key->T = gnaw(&mem, &len, (2 * h2) * sizeof(bytestring32)); lms_key->signature = gnaw(&mem, &len, lms_sig_len); lms_key->signature_len = lms_sig_len; lms_key->pubkey = gnaw(&mem, &len, lms_pub_len); lms_key->pubkey_len = lms_pub_len; + lms_key->q_end = h2; } return HAL_OK; } -/* called from pkey_local_generate_hashsig */ -hal_error_t hal_hashsig_key_gen(hal_core_t *core, - hal_hashsig_key_t **key_, - const size_t L, - const lms_algorithm_t lms_type, - const lmots_algorithm_t lmots_type) +static hal_error_t hss_generate(hss_key_t **key_, const hal_key_flags_t flags) { - /* hss_alloc does most of the checks */ - - if (restart_in_progress) - return HAL_ERROR_NOT_READY; + /* Hashsig keys can only be used for signing, so it makes sense to check + * that now, rather than waiting until the user tries to sign. + * + * Also, the top-level tree must be stored in the token (flash) keystore. + * I experimented with allowing keys to be stored in the volatile + * keystore, but that had some ugly consequences around the fact that + * volatile keys are automatically deleted when the user logs out. I'm + * also not sure there's a good use case for volatile hashsig keys. + */ + if (!(flags & HAL_KEY_FLAG_USAGE_DIGITALSIGNATURE) || + !(flags & HAL_KEY_FLAG_TOKEN)) + return HAL_ERROR_FORBIDDEN; - /* check flash keystore for space to store the root tree */ - lms_parameter_t *lms = lms_select_parameter_set(lms_type); - if (lms == NULL) + if (key_ == NULL || *key_ == NULL || (*key_)->lms == NULL) return HAL_ERROR_BAD_ARGUMENTS; + + /* hss_alloc does most of the sanity checks */ + + /* check flash keystore for space to store the root tree: + * 2^h lmots keys + 1 lms key + 1 hss key + */ size_t available; check(hal_ks_available(hal_ks_token, &available)); - if (available < (1U << lms->h) + 2) + if (available < (*key_)->q_end - (*key_)->q_start + 2) return HAL_ERROR_NO_KEY_INDEX_SLOTS; - check(hss_alloc(key_, L, lms_type, lmots_type)); + check(hss_alloc(key_)); hss_key_t *key = *key_; + hal_error_t err; /* generate the lms trees */ - for (size_t i = 0; i < L; ++i) { + for (size_t i = 0; i < key->L; ++i) { lms_key_t * lms_key = &key->lms_keys[i]; + bytestring32 *seed = NULL; + + if (i == 0) { + lms_key->I = key->I; + lms_key->q = key->q_start; + lms_key->q_end = key->q_end; + + /* If we're called from import, seed will be filled in. + * If called from key_gen, seed will be 0, and we may need to + * generate it. + */ + bytestring32 seed_0 = {{0}}; + if (memcmp(&key->seed, &seed_0, sizeof(seed_0)) != 0) { + seed = &key->seed; + } + else if (flags & HAL_KEY_FLAG_EXPORTABLE) { + seed = &key->seed; + if ((err = hal_rpc_get_random(seed, sizeof(*seed))) != HAL_OK) + goto err_out; + } + } - check(lms_generate(lms_key)); + if ((err = lms_generate(lms_key, seed)) != HAL_OK) + goto err_out; if (i > 0) /* sign this tree with the previous */ - check(lms_sign(&key->lms_keys[i-1], - (const uint8_t * const)lms_key->pubkey, lms_public_key_len(key->lms), - lms_key->signature, NULL, lms_signature_len(key->lms, key->lmots))); + if ((err = lms_sign(&key->lms_keys[i-1], + (const uint8_t * const)lms_key->pubkey, + lms_public_key_len(key->lms), + lms_key->signature, NULL, + lms_signature_len(key->lms, key->lmots))) != HAL_OK) + goto err_out; /* store the lms key */ + hal_ks_t *ks = (i == 0) ? hal_ks_token : hal_ks_volatile; hal_pkey_slot_t slot = { .type = HAL_KEY_TYPE_HASHSIG_LMS, - .curve = HAL_CURVE_NONE, + .name = lms_key->I, .flags = HAL_KEY_FLAG_USAGE_DIGITALSIGNATURE | ((i == 0) ? HAL_KEY_FLAG_TOKEN: 0) }; - hal_ks_t *ks = (i == 0) ? hal_ks_token : hal_ks_volatile; uint8_t der[lms_private_key_to_der_len(lms_key)]; size_t der_len; - memcpy(&slot.name, &lms_key->I, sizeof(slot.name)); - check(lms_private_key_to_der(lms_key, der, &der_len, sizeof(der))); - check(hal_ks_store(ks, &slot, der, der_len)); + if ((err = lms_private_key_to_der(lms_key, der, &der_len, sizeof(der))) != HAL_OK || + (err = hal_ks_store(ks, &slot, der, der_len)) != HAL_OK) + goto err_out; } - memcpy(&key->I, &key->lms_keys[0].I, sizeof(key->I)); - memcpy(&key->T1, &key->lms_keys[0].T1, sizeof(key->T1)); + key->I = key->lms_keys[0].I; + key->T1 = key->lms_keys[0].T1; /* pkey_local_generate_hashsig stores the key */ return HAL_OK; + +err_out: + (void)hal_free_static_memory(key); + return err; } -/* caller will delete the hss key from the keystore */ -hal_error_t hal_hashsig_key_delete(const hal_hashsig_key_t * const key) -{ +/* called from pkey_local_generate_hashsig + * caller will store the key + */ +hal_error_t hal_hashsig_key_gen(hal_core_t *core, + hal_hashsig_key_t **key_, + void *keybuf, const size_t keybuf_len, + const size_t L, + const hal_lms_algorithm_t lms_type, + const hal_lmots_algorithm_t lmots_type, + const hal_key_flags_t flags) +{ + if (key_ == NULL || keybuf == NULL || keybuf_len < sizeof(hss_key_t)) + return HAL_ERROR_BAD_ARGUMENTS; + if (restart_in_progress) return HAL_ERROR_NOT_READY; - if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_PRIVATE) - return HAL_ERROR_BAD_ARGUMENTS; - - /* delete the lms trees and their lmots keys */ - for (size_t level = 0; level < key->L; ++level) - check(lms_delete(&key->lms_keys[level])); + hss_key_t *key = *key_ = keybuf; + memset(key, 0, sizeof(*key)); + key->type = HAL_KEY_TYPE_HASHSIG_PRIVATE; + key->L = L; + key->lms = lms_select_parameter_set(lms_type); + key->lmots = lmots_select_parameter_set(lmots_type); + key->q_end = (1U << key->lms->h); - /* XXX free memory, if supported */ - (void)hal_free_static_memory(key); + return hss_generate(key_, flags); +} - /* remove from global hss_keys linked list */ - /* XXX or mark it unused, for possible re-use */ +static void hss_delete(hss_key_t *key) +{ + /* remove key from global hss_keys linked list */ if (hss_keys == key) { hss_keys = key->next; } @@ -1414,6 +1357,41 @@ hal_error_t hal_hashsig_key_delete(const hal_hashsig_key_t * const key) } } + /* delete the lms trees and their lmots keys */ + for (size_t level = 0; level < key->L; ++level) + (void)lms_delete(&key->lms_keys[level]); + + /* free memory, if possible */ + (void)hal_free_static_memory(key); +} + +/* caller will delete the hss key from the keystore */ +hal_error_t hal_hashsig_delete(const hal_uuid_t * const name) +{ + if (restart_in_progress) + return HAL_ERROR_NOT_READY; + + hal_pkey_slot_t slot = { .name = *name }; + uint8_t der[HAL_KS_WRAPPED_KEYSIZE]; + size_t der_len; + check(hal_ks_fetch(hal_ks_token, &slot, der, &der_len, sizeof(der))); + + hal_hashsig_key_t keybuf, *key; + check(hal_hashsig_private_key_from_der(&key, &keybuf, sizeof(keybuf), der, der_len)); + + /* hal_hashsig_private_key_from_der returns the key in the list of + * active hashsig keys, so we don't need this temporary key. + */ + memset(der, 0, sizeof(der)); + memset(&keybuf, 0, sizeof(keybuf)); + + /* OTOH, if we found the key in the keystore, but not in the list of + * active hashsig keys, that's Bad. + */ + if (key == &keybuf) + return HAL_ERROR_KEY_NOT_FOUND; + + hss_delete(key); return HAL_OK; } @@ -1431,24 +1409,10 @@ hal_error_t hal_hashsig_sign(hal_core_t *core, if (sig_max < hss_signature_len(key->L, key->lms, key->lmots)) return HAL_ERROR_RESULT_TOO_LONG; -// 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. - - size_t h2 = (1 << key->lms->h); - if (key->lms_keys[key->L-1].q >= h2) { + /* if the signing key is exhausted, try to regenerate it */ + if (key->lms_keys[key->L-1].q >= key->lms_keys[key->L-1].q_end) { size_t d; - for (d = key->L-1; d > 0 && key->lms_keys[d-1].q >= h2; --d) { + for (d = key->L-1; d > 0 && key->lms_keys[d-1].q >= key->lms_keys[d-1].q_end; --d) { } if (d == 0) return HAL_ERROR_HASHSIG_KEY_EXHAUSTED; @@ -1461,36 +1425,26 @@ hal_error_t hal_hashsig_sign(hal_core_t *core, * any additional memory. */ check(lms_delete(lms_key)); - check(lms_generate(lms_key)); + lms_key->q = 0; + check(lms_generate(lms_key, NULL)); check(lms_sign(&key->lms_keys[d-1], (const uint8_t * const)lms_key->pubkey, lms_key->pubkey_len, lms_key->signature, NULL, lms_key->signature_len)); hal_pkey_slot_t slot = { .type = HAL_KEY_TYPE_HASHSIG_LMS, - .curve = HAL_CURVE_NONE, - .flags = (lms_key->level == 0) ? HAL_KEY_FLAG_TOKEN: 0 + .name = lms_key->I, + .flags = HAL_KEY_FLAG_USAGE_DIGITALSIGNATURE | (lms_key->level == 0) ? HAL_KEY_FLAG_TOKEN: 0 }; - hal_ks_t *ks = (lms_key->level == 0) ? hal_ks_token : hal_ks_volatile; uint8_t der[lms_private_key_to_der_len(lms_key)]; size_t der_len; - memcpy(&slot.name, &lms_key->I, sizeof(slot.name)); check(lms_private_key_to_der(lms_key, der, &der_len, sizeof(der))); - check(hal_ks_store(ks, &slot, der, der_len)); + check(hal_ks_store(hal_ks_volatile, &slot, der, der_len)); } } -// 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]. - + /* sig = u32str(Nspk) || signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk] */ uint8_t *sigptr = sig; const uint8_t * const siglim = sig + sig_max; check(hal_xdr_encode_int(&sigptr, siglim, key->L - 1)); @@ -1517,19 +1471,10 @@ hal_error_t hal_hashsig_verify(hal_core_t *core, const uint8_t * const msg, const size_t msg_len, const uint8_t * const sig, const size_t sig_len) { - if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_PUBLIC || msg == NULL || sig == NULL) + if (key == NULL || (key->type != HAL_KEY_TYPE_HASHSIG_PRIVATE && key->type != HAL_KEY_TYPE_HASHSIG_PUBLIC) || msg == NULL || sig == NULL) return HAL_ERROR_BAD_ARGUMENTS; - core = core; - -// 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) -// if Nspk+1 is not equal to the number of levels L in pub: -// return INVALID + /* sig = u32str(Nspk) || signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk] */ const uint8_t *sigptr = sig; const uint8_t * const siglim = sig + sig_len; @@ -1539,22 +1484,13 @@ hal_error_t hal_hashsig_verify(hal_core_t *core, if (Nspk + 1 != key->L) return HAL_ERROR_INVALID_SIGNATURE; -// key = pub -// for (i = 0; i < Nspk; i = i + 1) { -// sig = next LMS signature parsed from S -// msg = next LMS public key parsed from S -// if (lms_verify(msg, key, sig) != VALID): -// return INVALID -// key = msg -// } - lms_key_t pub = { .type = HAL_KEY_TYPE_HASHSIG_LMS, .lms = key->lms, - .lmots = key->lmots + .lmots = key->lmots, + .I = key->I, + .T1 = key->T1 }; - memcpy(&pub.I, &key->I, sizeof(pub.I)); - memcpy(&pub.T1, &key->T1, sizeof(pub.T1)); for (size_t i = 0; i < Nspk; ++i) { const uint8_t * const lms_sig = sigptr; @@ -1567,7 +1503,7 @@ hal_error_t hal_hashsig_verify(hal_core_t *core, /* read lmots_type out of the ots_signature */ uint32_t lmots_type; check(hal_xdr_decode_int_peek(&sigptr, siglim, &lmots_type)); - lmots_parameter_t *lmots = lmots_select_parameter_set((lmots_algorithm_t)lmots_type); + lmots_parameter_t *lmots = lmots_select_parameter_set((hal_lmots_algorithm_t)lmots_type); if (lmots == NULL) return HAL_ERROR_INVALID_SIGNATURE; /* skip over ots_signature */ @@ -1575,7 +1511,7 @@ hal_error_t hal_hashsig_verify(hal_core_t *core, /* read lms_type after ots_signature */ uint32_t lms_type; check(hal_xdr_decode_int(&sigptr, siglim, &lms_type)); - lms_parameter_t *lms = lms_select_parameter_set((lms_algorithm_t)lms_type); + lms_parameter_t *lms = lms_select_parameter_set((hal_lms_algorithm_t)lms_type); if (lms == NULL) return HAL_ERROR_INVALID_SIGNATURE; /* skip over the path elements of the lms signature */ @@ -1587,14 +1523,14 @@ hal_error_t hal_hashsig_verify(hal_core_t *core, /* parse the signed public key */ check(hal_xdr_decode_int(&sigptr, siglim, &lms_type)); - pub.lms = lms_select_parameter_set((lmots_algorithm_t)lms_type); + pub.lms = lms_select_parameter_set((hal_lms_algorithm_t)lms_type); if (pub.lms == NULL) return HAL_ERROR_INVALID_SIGNATURE; check(hal_xdr_decode_int(&sigptr, siglim, &lmots_type)); - pub.lmots = lmots_select_parameter_set((lmots_algorithm_t)lmots_type); + pub.lmots = lmots_select_parameter_set((hal_lmots_algorithm_t)lmots_type); if (pub.lmots == NULL) return HAL_ERROR_INVALID_SIGNATURE; - check(hal_xdr_decode_bytestring16(&sigptr, siglim, &pub.I)); + check(hal_xdr_decode_uuid(&sigptr, siglim, &pub.I)); check(hal_xdr_decode_bytestring32(&sigptr, siglim, &pub.T1)); } @@ -1608,17 +1544,18 @@ hal_error_t hal_hashsig_private_key_to_der(const hal_hashsig_key_t * const key, if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_PRIVATE) return HAL_ERROR_BAD_ARGUMENTS; - /* - * Calculate data length. - */ + /* Calculate data length. */ size_t len, vlen = 0, hlen; check(hal_asn1_encode_size_t(key->L, NULL, &len, 0)); vlen += len; check(hal_asn1_encode_lms_algorithm(key->lms->type, NULL, &len, 0)); vlen += len; check(hal_asn1_encode_lmots_algorithm(key->lmots->type, NULL, &len, 0)); vlen += len; - check(hal_asn1_encode_bytestring16(&key->I, NULL, &len, 0)); vlen += len; + check(hal_asn1_encode_uuid(&key->I, NULL, &len, 0)); vlen += len; check(hal_asn1_encode_bytestring32(&key->T1, NULL, &len, 0)); vlen += len; + check(hal_asn1_encode_bytestring32(&key->seed, NULL, &len, 0)); vlen += len; + check(hal_asn1_encode_size_t(key->q_start, NULL, &len, 0)); vlen += len; + check(hal_asn1_encode_size_t(key->q_end, NULL, &len, 0)); vlen += len; check(hal_asn1_encode_header(ASN1_SEQUENCE, vlen, NULL, &hlen, 0)); @@ -1628,9 +1565,7 @@ hal_error_t hal_hashsig_private_key_to_der(const hal_hashsig_key_t * const key, if (der == NULL) return HAL_OK; - /* - * Encode data. - */ + /* Encode data. */ check(hal_asn1_encode_header(ASN1_SEQUENCE, vlen, der, &hlen, der_max)); @@ -1640,8 +1575,11 @@ hal_error_t hal_hashsig_private_key_to_der(const hal_hashsig_key_t * const key, check(hal_asn1_encode_size_t(key->L, d, &len, vlen)); d += len; vlen -= len; check(hal_asn1_encode_lms_algorithm(key->lms->type, d, &len, vlen)); d += len; vlen -= len; check(hal_asn1_encode_lmots_algorithm(key->lmots->type, d, &len, vlen)); d += len; vlen -= len; - check(hal_asn1_encode_bytestring16(&key->I, d, &len, vlen)); d += len; vlen -= len; + check(hal_asn1_encode_uuid(&key->I, d, &len, vlen)); d += len; vlen -= len; check(hal_asn1_encode_bytestring32(&key->T1, d, &len, vlen)); d += len; vlen -= len; + check(hal_asn1_encode_bytestring32(&key->seed, d, &len, vlen)); d += len; vlen -= len; + check(hal_asn1_encode_size_t(key->q_start, d, &len, vlen)); d += len; vlen -= len; + check(hal_asn1_encode_size_t(key->q_end, d, &len, vlen)); d += len; vlen -= len; return hal_asn1_encode_pkcs8_privatekeyinfo(hal_asn1_oid_mts_hashsig, hal_asn1_oid_mts_hashsig_len, NULL, 0, der, d - der, der, der_len, der_max); @@ -1688,14 +1626,17 @@ hal_error_t hal_hashsig_private_key_from_der(hal_hashsig_key_t **key_, size_t n; check(hal_asn1_decode_size_t(&key->L, d, &n, vlen)); d += n; vlen -= n; - lms_algorithm_t lms_type; + hal_lms_algorithm_t lms_type; check(hal_asn1_decode_lms_algorithm(&lms_type, d, &n, vlen)); d += n; vlen -= n; key->lms = lms_select_parameter_set(lms_type); - lmots_algorithm_t lmots_type; + hal_lmots_algorithm_t lmots_type; check(hal_asn1_decode_lmots_algorithm(&lmots_type, d, &n, vlen)); d += n; vlen -= n; key->lmots = lmots_select_parameter_set(lmots_type); - check(hal_asn1_decode_bytestring16(&key->I, d, &n, vlen)); d += n; vlen -= n; + check(hal_asn1_decode_uuid(&key->I, d, &n, vlen)); d += n; vlen -= n; check(hal_asn1_decode_bytestring32(&key->T1, d, &n, vlen)); d += n; vlen -= n; + check(hal_asn1_decode_bytestring32(&key->seed, d, &n, vlen)); d += n; vlen -= n; + check(hal_asn1_decode_size_t(&key->q_start, d, &n, vlen)); d += n; vlen -= n; + check(hal_asn1_decode_size_t(&key->q_end, d, &n, vlen)); d += n; vlen -= n; if (d != privkey + privkey_len) return HAL_ERROR_ASN1_PARSE_FAILED; @@ -1705,11 +1646,9 @@ hal_error_t hal_hashsig_private_key_from_der(hal_hashsig_key_t **key_, * structure. (The caller will wipe his own key structure when done, * and not molest ours.) */ - for (hss_key_t *hss_key = hss_keys; hss_key != NULL; hss_key = hss_key->next) { - if (memcmp(&key->I, &hss_key->lms_keys[0].I, sizeof(key->I)) == 0) { - *key_ = hss_key; - } - } + hss_key_t *hss_key = hss_find(&key->I); + if (hss_key != NULL) + *key_ = hss_key; return HAL_OK; } @@ -1721,14 +1660,14 @@ hal_error_t hal_hashsig_public_key_to_der(const hal_hashsig_key_t * const key, key->type != HAL_KEY_TYPE_HASHSIG_PUBLIC)) return HAL_ERROR_BAD_ARGUMENTS; - // L || u32str(lms_type) || u32str(lmots_type) || I || T[1] + /* L || u32str(lms_type) || u32str(lmots_type) || I || T[1] */ size_t len, vlen = 0, hlen; check(hal_asn1_encode_size_t(key->L, NULL, &len, 0)); vlen += len; check(hal_asn1_encode_lms_algorithm(key->lms->type, NULL, &len, 0)); vlen += len; check(hal_asn1_encode_lmots_algorithm(key->lmots->type, NULL, &len, 0)); vlen += len; - check(hal_asn1_encode_bytestring16(&key->I, NULL, &len, 0)); vlen += len; + check(hal_asn1_encode_uuid(&key->I, NULL, &len, 0)); vlen += len; check(hal_asn1_encode_bytestring32(&key->T1, NULL, &len, 0)); vlen += len; check(hal_asn1_encode_header(ASN1_SEQUENCE, vlen, der, &hlen, der_max)); @@ -1741,7 +1680,7 @@ hal_error_t hal_hashsig_public_key_to_der(const hal_hashsig_key_t * const key, check(hal_asn1_encode_size_t(key->L, d, &len, dlen)); d += len; dlen -= len; check(hal_asn1_encode_lms_algorithm(key->lms->type, d, &len, dlen)); d += len; dlen -= len; check(hal_asn1_encode_lmots_algorithm(key->lmots->type, d, &len, dlen)); d += len; dlen -= len; - check(hal_asn1_encode_bytestring16(&key->I, d, &len, dlen)); d += len; dlen -= len; + check(hal_asn1_encode_uuid(&key->I, d, &len, dlen)); d += len; dlen -= len; check(hal_asn1_encode_bytestring32(&key->T1, d, &len, dlen)); d += len; dlen -= len; } @@ -1787,17 +1726,17 @@ hal_error_t hal_hashsig_public_key_from_der(hal_hashsig_key_t **key_, const uint8_t * const pubkey_end = pubkey + hlen + vlen; const uint8_t *d = pubkey + hlen; - // L || u32str(lms_type) || u32str(lmots_type) || I || T[1] + /* L || u32str(lms_type) || u32str(lmots_type) || I || T[1] */ - lms_algorithm_t lms_type; - lmots_algorithm_t lmots_type; + hal_lms_algorithm_t lms_type; + hal_lmots_algorithm_t lmots_type; check(hal_asn1_decode_size_t(&key->L, d, &len, pubkey_end - d)); d += len; check(hal_asn1_decode_lms_algorithm(&lms_type, d, &len, pubkey_end - d)); d += len; key->lms = lms_select_parameter_set(lms_type); check(hal_asn1_decode_lmots_algorithm(&lmots_type, d, &len, pubkey_end - d)); d += len; key->lmots = lmots_select_parameter_set(lmots_type); - check(hal_asn1_decode_bytestring16(&key->I, d, &len, pubkey_end - d)); d += len; + check(hal_asn1_decode_uuid(&key->I, d, &len, pubkey_end - d)); d += len; check(hal_asn1_decode_bytestring32(&key->T1, d, &len, pubkey_end - d)); d += len; if (d != pubkey_end) @@ -1810,13 +1749,13 @@ hal_error_t hal_hashsig_public_key_from_der(hal_hashsig_key_t **key_, hal_error_t hal_hashsig_key_load_public(hal_hashsig_key_t **key_, void *keybuf, const size_t keybuf_len, const size_t L, - const lms_algorithm_t lms_type, - const lmots_algorithm_t lmots_type, + const hal_lms_algorithm_t lms_type, + const hal_lmots_algorithm_t lmots_type, const uint8_t * const I, const size_t I_len, const uint8_t * const T1, const size_t T1_len) { if (key_ == NULL || keybuf == NULL || keybuf_len < sizeof(hal_hashsig_key_t) || - I == NULL || I_len != sizeof(bytestring16) || + I == NULL || I_len != sizeof(hal_uuid_t) || T1 == NULL || T1_len != sizeof(bytestring32)) return HAL_ERROR_BAD_ARGUMENTS; @@ -1851,17 +1790,17 @@ hal_error_t hal_hashsig_key_load_public_xdr(hal_hashsig_key_t **key_, /* L || u32str(lms_type) || u32str(lmots_type) || I || T[1] */ uint32_t L, lms_type, lmots_type; - bytestring16 *I; + hal_uuid_t *I; bytestring32 *T1; check(hal_xdr_decode_int(&xdrptr, xdrlim, &L)); check(hal_xdr_decode_int(&xdrptr, xdrlim, &lms_type)); check(hal_xdr_decode_int(&xdrptr, xdrlim, &lmots_type)); - check(hal_xdr_decode_bytestring16_ptr(&xdrptr, xdrlim, &I)); + check(hal_xdr_decode_uuid_ptr(&xdrptr, xdrlim, &I)); check(hal_xdr_decode_bytestring32_ptr(&xdrptr, xdrlim, &T1)); return hal_hashsig_key_load_public(key_, keybuf, keybuf_len, L, lms_type, lmots_type, - (const uint8_t * const)I, sizeof(bytestring16), + (const uint8_t * const)I, sizeof(hal_uuid_t), (const uint8_t * const)T1, sizeof(bytestring32)); } @@ -1887,18 +1826,18 @@ hal_error_t hal_hashsig_public_key_der_to_xdr(const uint8_t * const der, const s const uint8_t * const pubkey_end = pubkey + hlen + vlen; const uint8_t *d = pubkey + hlen; - // L || u32str(lms_type) || u32str(lmots_type) || I || T[1] + /* L || u32str(lms_type) || u32str(lmots_type) || I || T[1] */ size_t L; - lms_algorithm_t lms_type; - lmots_algorithm_t lmots_type; - bytestring16 I; + hal_lms_algorithm_t lms_type; + hal_lmots_algorithm_t lmots_type; + hal_uuid_t I; bytestring32 T1; check(hal_asn1_decode_size_t(&L, d, &len, pubkey_end - d)); d += len; check(hal_asn1_decode_lms_algorithm(&lms_type, d, &len, pubkey_end - d)); d += len; check(hal_asn1_decode_lmots_algorithm(&lmots_type, d, &len, pubkey_end - d)); d += len; - check(hal_asn1_decode_bytestring16(&I, d, &len, pubkey_end - d)); d += len; + check(hal_asn1_decode_uuid(&I, d, &len, pubkey_end - d)); d += len; check(hal_asn1_decode_bytestring32(&T1, d, &len, pubkey_end - d)); d += len; if (d != pubkey_end) @@ -1910,7 +1849,7 @@ hal_error_t hal_hashsig_public_key_der_to_xdr(const uint8_t * const der, const s check(hal_xdr_encode_int(&xdrptr, xdrlim, L)); check(hal_xdr_encode_int(&xdrptr, xdrlim, lms_type)); check(hal_xdr_encode_int(&xdrptr, xdrlim, lmots_type)); - check(hal_xdr_encode_bytestring16(&xdrptr, xdrlim, &I)); + check(hal_xdr_encode_uuid(&xdrptr, xdrlim, &I)); check(hal_xdr_encode_bytestring32(&xdrptr, xdrlim, &T1)); if (xdr_len != NULL) @@ -1927,7 +1866,7 @@ hal_error_t hal_hashsig_ks_init(void) const hal_session_handle_t session = { HAL_HANDLE_NONE }; hal_uuid_t prev_name = {{0}}; unsigned len; - hal_pkey_slot_t slot = {0}; + hal_pkey_slot_t slot = {{0}}; uint8_t der[HAL_KS_WRAPPED_KEYSIZE]; size_t der_len; @@ -1941,36 +1880,47 @@ hal_error_t hal_hashsig_ks_init(void) if (hal_ks_fetch(hal_ks_token, &slot, der, &der_len, sizeof(der)) != HAL_OK || hal_hashsig_private_key_from_der(&key, (void *)&keybuf, sizeof(keybuf), der, der_len) != HAL_OK) { (void)hal_ks_delete(hal_ks_token, &slot); + memset(der, 0, sizeof(der)); + memset(&keybuf, 0, sizeof(keybuf)); + key = NULL; continue; } /* Make sure we have the lms key */ - hal_pkey_slot_t lms_slot = {0}; + hal_pkey_slot_t lms_slot = { + .name = key->I + }; lms_key_t lms_key; - memcpy(&lms_slot.name, &key->I, sizeof(lms_slot.name)); if (hal_ks_fetch(hal_ks_token, &lms_slot, der, &der_len, sizeof(der)) != HAL_OK || lms_private_key_from_der(&lms_key, der, der_len) != HAL_OK || /* check keys for consistency */ lms_key.lms != key->lms || lms_key.lmots != key->lmots || memcmp(&lms_key.I, &key->I, sizeof(lms_key.I)) != 0 || + /* check that key isn't exhausted */ + lms_key.q >= lms_key.q_end || /* optimistically allocate the full hss key structure */ - hss_alloc(&key, key->L, key->lms->type, key->lmots->type) != HAL_OK) { + hss_alloc(&key) != HAL_OK) { (void)hal_ks_delete(hal_ks_token, &slot); (void)hal_ks_delete(hal_ks_token, &lms_slot); + memset(der, 0, sizeof(der)); + memset(&lms_key, 0, sizeof(lms_key)); + memset(&keybuf, 0, sizeof(keybuf)); + key = NULL; continue; } - /* hss_alloc redefines key, so copy fields from the old version of the key */ - memcpy(&key->I, &keybuf.I, sizeof(key->I)); - memcpy(&key->T1, &keybuf.T1, sizeof(key->T1)); - key->name = slot.name; - /* initialize top-level lms key (beyond what hss_alloc did) */ - memcpy(&key->lms_keys[0].I, &lms_key.I, sizeof(lms_key.I)); + key->lms_keys[0].I = lms_key.I; key->lms_keys[0].q = lms_key.q; + key->lms_keys[0].q_end = key->q_end; - prev_name = slot.name; + prev_name = key->name = slot.name; + memset(der, 0, sizeof(der)); + memset(&lms_key, 0, sizeof(lms_key)); + memset(&keybuf, 0, sizeof(keybuf)); + key = NULL; + hal_task_yield_maybe(); } /* Delete orphaned lms keys */ @@ -1978,17 +1928,13 @@ hal_error_t hal_hashsig_ks_init(void) while ((hal_ks_match(hal_ks_token, client, session, HAL_KEY_TYPE_HASHSIG_LMS, HAL_CURVE_NONE, 0, 0, NULL, 0, &slot.name, &len, 1, &prev_name) == HAL_OK) && (len > 0)) { - hss_key_t *hss_key; - for (hss_key = hss_keys; hss_key != NULL; hss_key = hss_key->next) { - if (memcmp(&slot.name, &hss_key->I, sizeof(slot.name)) == 0) - break; - } - if (hss_key == NULL) { + if (hss_find(&slot.name) == NULL) { (void)hal_ks_delete(hal_ks_token, &slot); continue; } prev_name = slot.name; + hal_task_yield_maybe(); } /* Find all lmots keys */ @@ -2006,35 +1952,31 @@ hal_error_t hal_hashsig_ks_init(void) if (hal_ks_fetch(hal_ks_token, &slot, der, &der_len, sizeof(der)) != HAL_OK || lmots_private_key_from_der(&lmots_key, der, der_len) != HAL_OK) { (void)hal_ks_delete(hal_ks_token, &slot); + memset(&lmots_key, 0, sizeof(lmots_key)); continue; } - hss_key_t *hss_key; - for (hss_key = hss_keys; hss_key != NULL; hss_key = hss_key->next) { - if (memcmp(&hss_key->I, &lmots_key.I, sizeof(lmots_key.I)) == 0) - break; - } + hss_key_t *hss_key = hss_find(&lmots_key.I); if (hss_key == NULL) { /* delete orphaned key */ (void)hal_ks_delete(hal_ks_token, &slot); + memset(&lmots_key, 0, sizeof(lmots_key)); continue; } /* record this lmots key in the top-level lms key */ - memcpy(&hss_key->lms_keys[0].lmots_keys[lmots_key.q], &slot.name, sizeof(slot.name)); + hss_key->lms_keys[0].lmots_keys[lmots_key.q] = slot.name; /* compute T[r] = H(I || u32str(r) || u16str(D_LEAF) || K) */ - size_t r = (1U << hss_key->lms->h) + lmots_key.q; - uint8_t statebuf[512]; - hal_hash_state_t *state = NULL; - hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf)); - hal_hash_update(state, (const uint8_t *)&hss_key->I, sizeof(hss_key->I)); - uint32_t l = u32str(r); hal_hash_update(state, (const uint8_t *)&l, sizeof(l)); - uint16_t s = u16str(D_LEAF); hal_hash_update(state, (const uint8_t *)&s, sizeof(s)); - hal_hash_update(state, (const uint8_t *)&lmots_key.K, sizeof(lmots_key.K)); - hal_hash_finalize(state, (uint8_t *)&hss_key->lms_keys[0].T[r], sizeof(hss_key->lms_keys[0].T[r])); + if (lms_compute_T_leaf(&hss_key->lms_keys[0], &lmots_key) != HAL_OK) { + (void)hal_ks_delete(hal_ks_token, &slot); + memset(&lmots_key, 0, sizeof(lmots_key)); + continue; + } prev_name = slot.name; + memset(&lmots_key, 0, sizeof(lmots_key)); + hal_task_yield_maybe(); } /* After all keys have been read, scan for completeness. */ @@ -2043,69 +1985,49 @@ hal_error_t hal_hashsig_ks_init(void) for (hss_key = hss_keys; hss_key != NULL; hss_key = hss_next) { hss_next = hss_key->next; int fail = 0; - for (size_t i = 0; i < (1U << hss_key->lms->h); ++i) { - if (hal_uuid_cmp(&hss_key->lms_keys[0].lmots_keys[i], &uuid_0) == 0) { - fail = 1; - break; + lms_key_t *lms_key = hss_key->lms_keys; + for (size_t q = 0; q < (1U << hss_key->lms->h); ++q) { + if (hal_uuid_cmp(&lms_key->lmots_keys[q], &uuid_0) == 0) { + bytestring32 seed_0 = {{0}}; + if (memcmp(&hss_key->seed, &seed_0, sizeof(seed_0)) == 0) { + /* lms key is incomplete, give up on it */ + fail = 1; + break; + } + else { + /* This key was generated with the pseudo-random method, + * and can be regenerated. + */ + check(lms_generate_lmots(lms_key, q, &hss_key->seed)); + hal_task_yield_maybe(); + } } } if (fail) { fail: - /* lms key is incomplete, give up on it */ - /* delete lmots keys */ - for (size_t i = 0; i < (1U << hss_key->lms->h); ++i) { - if (hal_uuid_cmp(&hss_key->lms_keys[0].lmots_keys[i], &uuid_0) != 0) { - memcpy(&slot.name, &hss_key->lms_keys[0].lmots_keys[i], sizeof(slot.name)); - (void)hal_ks_delete(hal_ks_token, &slot); - } - } - /* delete lms key */ - memcpy(&slot.name, &hss_key->I, sizeof(slot.name)); - (void)hal_ks_delete(hal_ks_token, &slot); /* delete hss key */ + hss_delete(hss_key); slot.name = hss_key->name; (void)hal_ks_delete(hal_ks_token, &slot); - /* remove the hss key from the key list */ - if (hss_keys == hss_key) { - hss_keys = hss_key->next; - } - else { - for (hss_key_t *prev = hss_keys; prev != NULL; prev = prev->next) { - if (prev->next == hss_key) { - prev->next = hss_key->next; - break; - } - } - } - (void)hal_free_static_memory(hss_key); + hal_task_yield_maybe(); continue; } /* generate the rest of T[] */ - for (size_t r = (1U << hss_key->lms->h) - 1; r > 0; --r) { - uint8_t statebuf[512]; - hal_hash_state_t *state = NULL; - hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf)); - hal_hash_update(state, (const uint8_t *)&hss_key->I, sizeof(hss_key->I)); - uint32_t l = u32str(r); hal_hash_update(state, (const uint8_t *)&l, sizeof(l)); - uint16_t s = u16str(D_INTR); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s))); - hal_hash_update(state, (const uint8_t *)&hss_key->lms_keys[0].T[2*r], sizeof(hss_key->lms_keys[0].T[r])); - hal_hash_update(state, (const uint8_t *)&hss_key->lms_keys[0].T[2*r+1], sizeof(hss_key->lms_keys[0].T[r])); - hal_hash_finalize(state, (uint8_t *)&hss_key->lms_keys[0].T[r], sizeof(hss_key->lms_keys[0].T[r])); - } - if (memcmp(&hss_key->lms_keys[0].T[1], &hss_key->T1, sizeof(hss_key->lms_keys[0].T[1])) != 0) + lms_compute_T_intr(lms_key); + if (memcmp(&lms_key->T[1], &hss_key->T1, sizeof(lms_key->T[1])) != 0) goto fail; /* generate the lower-level lms keys */ for (size_t i = 1; i < hss_key->L; ++i) { - lms_key_t * lms_key = &hss_key->lms_keys[i]; - if (lms_generate(lms_key) != HAL_OK) + lms_key = &hss_key->lms_keys[i]; + if (lms_generate(lms_key, NULL) != HAL_OK) goto fail; /* store the lms key */ slot.type = HAL_KEY_TYPE_HASHSIG_LMS; slot.flags = HAL_KEY_FLAG_USAGE_DIGITALSIGNATURE; - memcpy(&slot.name, &lms_key->I, sizeof(slot.name)); + slot.name = lms_key->I; if (lms_private_key_to_der(lms_key, der, &der_len, sizeof(der)) != HAL_OK || hal_ks_store(hal_ks_volatile, &slot, der, der_len) != HAL_OK || /* sign this lms key with the previous */ @@ -2113,10 +2035,99 @@ hal_error_t hal_hashsig_ks_init(void) (const uint8_t * const)lms_key->pubkey, lms_key->pubkey_len, lms_key->signature, NULL, lms_key->signature_len) != HAL_OK) goto fail; + hal_task_yield_maybe(); } } restart_in_progress = 0; return HAL_OK; } + +hal_error_t hal_hashsig_export(const hal_uuid_t * const name, uint8_t *der, size_t *der_len, const size_t der_max) +{ + hal_error_t err; + hal_hashsig_key_t keybuf, *tmp_key = &keybuf, *hss_key; + + if ((err = hal_hashsig_private_key_from_der(&hss_key, &keybuf, sizeof(keybuf), der, *der_len)) != HAL_OK) + goto err_out; + if (hss_key == tmp_key) { + err = HAL_ERROR_KEY_NOT_FOUND; /* or IMPOSSIBLE? */ + goto err_out; + } + + /* adjust hss_key->end and tmp_key->start */ + size_t new_end = (hss_key->lms_keys[0].q + hss_key->lms_keys[0].q_end) / 2; + if (new_end == hss_key->lms_keys[0].q) { + err = HAL_ERROR_HASHSIG_KEY_EXHAUSTED; + goto err_out; + } + hss_key->q_end = hss_key->lms_keys[0].q_end = tmp_key->q_start = new_end; + + /* store updated hss_key */ + hal_pkey_slot_t slot = { + .type = HAL_KEY_TYPE_HASHSIG_PRIVATE, + .name = *name, + .flags = HAL_KEY_FLAG_USAGE_DIGITALSIGNATURE | HAL_KEY_FLAG_TOKEN | HAL_KEY_FLAG_EXPORTABLE + }; + if ((err = hal_hashsig_private_key_to_der(hss_key, der, der_len, der_max)) != HAL_OK || + (err = hal_ks_rewrite_der(hal_ks_token, &slot, der, *der_len)) != HAL_OK) + goto err_out; + + /* store updated lms_key */ + lms_key_t *lms_key = &hss_key->lms_keys[0]; + uint8_t lms_der[HAL_KS_WRAPPED_KEYSIZE]; + size_t lms_der_len; + if ((err = lms_private_key_to_der(lms_key, lms_der, &lms_der_len, sizeof(lms_der))) != HAL_OK) + goto err_out; + + hal_pkey_slot_t lms_slot = { + .type = HAL_KEY_TYPE_HASHSIG_LMS, + .name = lms_key->I, + .flags = HAL_KEY_FLAG_USAGE_DIGITALSIGNATURE | HAL_KEY_FLAG_TOKEN + }; + if ((err = hal_ks_rewrite_der(hal_ks_token, &lms_slot, lms_der, lms_der_len)) != HAL_OK) + goto err_out; + + /* re-encode tmp_key to der */ + if ((err = hal_hashsig_private_key_to_der(tmp_key, der, der_len, der_max)) != HAL_OK) + goto err_out; + + /* delete unused lmots keys? */ + +err_out: + memset(&keybuf, 0, sizeof(keybuf)); + hss_key = NULL; + return err; +} + +hal_error_t hal_hashsig_import(const uint8_t *der, const size_t der_len, + const hal_key_flags_t flags) +{ + if (restart_in_progress) + return HAL_ERROR_NOT_READY; + + hss_key_t keybuf, *key; + hal_error_t err; + + if ((err = hal_hashsig_private_key_from_der(&key, &keybuf, sizeof(keybuf), der, der_len)) != HAL_OK) + goto err_out; + + /* If the key already exists, it could be that the user is attempting to + * return an exported key to its origin, and we could consolidate them, + * but then we have to deal with the possibility of disjoint partitions of + * the keyspace (or worse, overlapping or duplicate partitions, which is + * always an error). In any case, it's easier just to disallow it. + */ + if (hss_find(&key->I) != NULL) { + err = HAL_ERROR_KEY_NAME_IN_USE; + goto err_out; + } + + err = hss_generate(&key, flags); + +err_out: + memset(&keybuf, 0, sizeof(keybuf)); + key = NULL; + return err; +} #endif |