RE: HSS strength attribute for public key

Hi Philip,

Thank you for your insight!

My takeaway is that the CKA_VALUE of the public key suffices to specify the security (since it contains the CK_LMS/LMOTS_TYPE of the top level tree, and we are guaranteed that the hash function used will be the same through the hierarchy). Thus, we do not need an additional attribute for this purpose.

I will upload an updated version of the HSS spec shortly.

Michelle

From: Philip Lafrance <Philip.Lafrance@isara.com>
Sent: Wednesday, March 31, 2021 11:11 AM
To: Michelle Brochmann <mbrochmann@infoseccorp.com>; pkcs11@lists.oasis-open.org
Subject: RE: HSS strength attribute for public key

Greetings all,

HSS allows different parameter sets to be used on different layers of the hierarchy. However, there are still some restrictions. The hash function used must be the same across all OTS instances and all LMS instances across all layers of the hierarchy. I.e., you cannot use something like SHA256/192 on one layer and SHA256/256 on another. Further, the (theoretical) security of the scheme is essentially just the security of the hash function.

With that in mind, I believe the security of LMS/HSS boils down to Second-preimage resistance essentially (see section 9 of RFC 8554). So, for example, HSS with SHA256 should offer 256-bits of classic security and 128-bits of post-quantum security.

The following is from page 12 (section 4) of NIST SP 800-208,

"When generating a key pair for an LMS instance, each LM-OTS key in the system shall use the same parameter set, and the hash function used for the LMS system shall be the same as the hash function used in the LM-OTS keys. The height of the tree (h) shall be 5, 10, 15, 20, or 25.

When generating a key pair for an HSS instance, the requirements specified in the previous paragraph apply to each LMS tree in the instance. If the HSS instance has more than one level, then the hash function used for the tree at level 0 shall be used for every LMS tree at every other level. For each level, the same LMS and LM-OTS parameter sets shall be used for every LMS tree at that level. Different LMS and LM-OTS parameter sets may be used at different levels, as long as all chosen parameter sets use the same hash function."

Basically, you can use different heights and Winternitz parameters, but you’re stuck with your choice of hash function.

I don't think this came up in the RFC (RFC 8554) as that document only uses SHA256.

I hope this helps!

Best regards,

Philip

P.S I will endeavour to attend today’s call, but an on-coming migraine might prevent that…

From: pkcs11@lists.oasis-open.org <pkcs11@lists.oasis-open.org> On Behalf Of Michelle Brochmann
Sent: March 31, 2021 11:07 AM
To: pkcs11@lists.oasis-open.org
Subject: [External][pkcs11] HSS strength attribute for public key

Hi all,

Something I’m hoping to discuss this afternoon:

I’m trying to decide on the best way to describe the strength of the HSS scheme in the public key. Possibilities are:

Choose the level using the weakest/lowest OTS parameter, and if there is more than 1 level using that OTS parameter, choose the level that has that OTS parameter and the weakest/lowest LMOTS parameter. Describe the strength with the OTS and LMOTS parameters from this level as well as the number of HSS levels.
Describe the strength with the weakest/lowest OTS parameter used in the entire scheme, and the weakest/lowest LMOTS parameter used in the entire scheme as well as the number of HSS levels.
A parameter calculated from the full set of parameters describing the security strength. I haven’t been able to find a security analysis that easily maps the full HSS params to a measure of security. There was some information here: https://eprint.iacr.org/2017/553.pdf but it wasn’t clear to me how to map our parameters to the equations they came up with there.
The full CKA_HSS_PARAMS as originally included (but we decided was too complicated to have the user have to determine the security from).

Then I need to come up with names for these two attributes:

Case 1) could be something like CKA_HSS_WEAKEST_LEVEL_OTS and CKA_HSS_WEAKEST_LEVEL_LMOTS

Case 2) could be something like CKA_HSS_LOWEST_OTS and CKA_HSS_LOWEST_LMOTS

Case 3) could be something like the log of the probability of a forgery given some predefined conditions, CKA_HSS_STRENGTH could suffice. The problem is calculating it!

Case 4) would just be the CKA_HSS_PARAMS as originally given.

Note: I’m thinking it would be best to avoid saying anything like “LOWEST_LEVEL” anywhere since that could be taken to imply “lowest level in the HSS hierarchy”.

I’m not sure that 1) or 2) fully specify the strength of the scheme. I.e. how can we compare (without a case 3) style calculation) two schemes with the same number of HSS levels, where one has the highest possible LMS and lowest possible LMOTS and the other has the lowest possible LMS and highest possible LMOTS? This is partly why I think 4) might be necessary to give a complete picture of the security level of the scheme. I’m hoping someone with a better understanding of security analysis than me can weigh in on this!

Michelle

pkcs11 message