Hi all,
We would like to share some comments on the PKCS11 HSS Draft from Philip Lafrance and Mark Paruzel of ISARA corporation, in hopes of opening up the discussion to the whole group.
The current draft can be found at:
https://www.oasis-open.org/committees/document.php?document_id=66342
The full conversation thread can be found below, but to summarize, the main concerns are:
- Storing the state separately from the key to avoid accidental key reuse
- Accommodating variation in key/state storage formats
- Whether private keys should be exportable
- Impacts of the time needed for key generation at large tree sizes
We look forward to any feedback you may have!
Michelle
From: Michelle Brochmann
Sent: Thursday, December 26, 2019 11:56 AM
To: Mark.Paruzel@isara.com; Philip.Lafrance@isara.com; Jonathan Schulze-Hewett <schulze-hewett@infoseccorp.com>; Michael Markowitz <markowitz@infoseccorp.com>
Subject: RE: RE: Some comments on the PKCS11 HSS Draft
Hi Mark,
We hadn’t considered this issue. In fact, Jonathan points out that some HSMs have specialized hardware that can perform operations much faster than a general purpose CPU.
Still, since this kind of signature scheme does take a relatively long time for key generation and signing, we expect that it would be used in applications (such as code-signing) where this kind of wait is acceptable.
We aren’t sure exactly what you mean by “PKCS11 connection timeouts” – is this something specific in the PKCS11 framework or just timeouts that will occur in applications using PKCS?
Michelle
From: Mark Paruzel <Mark.Paruzel@isara.com>
Sent: Friday, December 20, 2019 8:36 AM
To: Philip Lafrance <Philip.Lafrance@isara.com>; Michelle Brochmann <mbrochmann@infoseccorp.com>; Jonathan Schulze-Hewett <schulze-hewett@infoseccorp.com>; Michael Markowitz <markowitz@infoseccorp.com>
Subject: Re: RE: Some comments on the PKCS11 HSS Draft
Hi Michelle,
Have you and your team given thought to how the long-running nature of HSS key gen impacts PKCS11 connection timeouts?
On modern desktops, a H25-W8 tree could take many hours to compute. HSMs generally run on slower hardware compared to their desktop counterparts, which may result in a key generation ceremony that runs for 24+ hours. How do you suppose this impacts connection timeouts in P11?
Cheers,
-M
From: Philip Lafrance
Sent: Friday, December 20, 2019 9:25:21 AM
To: Michelle Brochmann; Mark Paruzel; Jonathan Schulze-Hewett; Michael Markowitz
Subject: RE: RE: Some comments on the PKCS11 HSS Draft
Good morning all,
By all means, feel free to share these comments with the P11 group. I’d also be curious to hear the comments provided by the other TC members.
Best regards,
Philip
From: Michelle Brochmann <mbrochmann@infoseccorp.com>
Sent: December 19, 2019 5:12 PM
To: Philip Lafrance <Philip.Lafrance@isara.com>; Mark Paruzel <Mark.Paruzel@isara.com>; Jonathan Schulze-Hewett <schulze-hewett@infoseccorp.com>; Michael Markowitz <markowitz@infoseccorp.com>
Subject: [External]RE: RE: Some comments on the PKCS11 HSS Draft
Hi Philip and Mark,
Thanks for the additional information. Do you mind if I forward this to the OASIS PKCS11 mailing list for further discussion?
Michelle
From: Philip Lafrance <Philip.Lafrance@isara.com>
Sent: Thursday, December 19, 2019 2:36 PM
To: Michelle Brochmann <mbrochmann@infoseccorp.com>
Cc: Mark Paruzel <Mark.Paruzel@isara.com>
Subject: Re: RE: Some comments on the PKCS11 HSS Draft
Hello Michelle,
I hope you’re well.
Sorry for the delayed response on this. I’ve also cc’d my colleague Mark Paruzel on this thread.
As per your proposed text: "An OCTET-STRING containing the information needed, in the context of the vendor-determined implementation, to obtain the private key information necessary to generate the next signature. This will include seed or other information necessary to generate the full HSS tree, and must include state information unless the state is maintained separately by the HSM."
I like this—and I agree that the second sentence is probably not necessary. The important thing is that state information is not specified by the user. Rather, it should be handled mechanically by the HSM so as to mitigate the possibility of human error. We almost feel as though the requirement should be that state must be handled separately inside the HSM, and likely out of band of P11 or in a private key blob/format. Doing so would force implementors to treat the state as a special blob with special rules. This would yield new operational measures (from an administrative point of view) that treat the state in a careful manner with respect to backup/restore and key propagation.
Regarding the NIST document. It is still a draft, and comments will be accepted by NIST up until the end of February. Our thinking is that wholesale banning of exporting keying material is not a good idea, and probably causes more problems than it solves. I’m not sure what your timeline is for getting your document published, but we should be careful to note that the requirements in the current SP 800-208 draft are subject to change.
That said, we agree that back-up/restore mechanisms should be vendor defined.
Best regards,
Philip & Mark
--
| Philip Lafrance | Standards Manager |
www.isara.com · 560 Westmount Road North, Waterloo, Ontario N2L 0A9 CANADA | |
From: Michelle Brochmann <mbrochmann@infoseccorp.com>
Date: Tuesday, December 17, 2019 at 12:39 PM
To: Philip Lafrance <Philip.Lafrance@isara.com>
Subject: [External]RE: Some comments on the PKCS11 HSS Draft
Hi Philip,
Thanks again for bringing up these points. It seems that they can largely be mitigated by a simple change – instead of the current highly prescriptive definition of the CKA_VALUE in the private key, replace the “Meaning” entry in Table 1.5 with the following:
"An OCTET-STRING containing the information needed, in the context of the vendor-determined implementation, to obtain the private key information necessary to generate the next signature. This will include seed or other information necessary to generate the full HSS tree, and must include state information unless the state is maintained separately by the HSM."
What do you think of this? I’m not sure if the second sentence is necessary.
Another thing we have noticed is that in this draft:
https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-208-draft.pdf
“It requires that key and signature generation be performed in hardware cryptographic modules that do not allow secret keying material to be exported.”
Since the NIST pub says they can't be exported, do you agree that the PKCS#11 spec should ban export/import of private certificates? If it is not exportable, backup/restore and the prevention of accidental key reuse will be the responsibility of the HSM vendor.
And, if we don't allow import/export, do we even need to specify the private key in the template?
Thanks,
Michelle
From: Philip Lafrance <Philip.Lafrance@isara.com>
Sent: Thursday, December 12, 2019 12:07 PM
To: Michelle Brochmann <mbrochmann@infoseccorp.com>
Cc: Michael Markowitz <markowitz@infoseccorp.com>; Jonathan Schulze-Hewett <schulze-hewett@infoseccorp.com>
Subject: Re: RE: Some comments on the PKCS11 HSS Draft
Thanks for the speedy reply!
I appreciate that. Additionally, we’re open to further collaboration going forward if you’re interested. I’m still new to OASIS and am learning how the TC operates, but I feel this is very important work. So, thank you for proposing this draft in the first place! I’m glad to see other people are taking this seriously.
Best regards,
Philip
--
| Philip Lafrance | Standards Manager |
www.isara.com · 560 Westmount Road North, Waterloo, Ontario N2L 0A9 CANADA | |
From: Michelle Brochmann <mbrochmann@infoseccorp.com>
Date: Thursday, December 12, 2019 at 11:38 AM
To: "Philip.Lafrance@isara.com" <Philip.Lafrance@isara.com>
Cc: Michael Markowitz <markowitz@infoseccorp.com>, Jonathan Schulze-Hewett <schulze-hewett@infoseccorp.com>
Subject: [External]RE: Some comments on the PKCS11 HSS Draft
Dear Philip,
Thank you very much for this information. I’m sharing it with my supervisors (cc’d in this reply) and hopefully it will spark some discussions leading to important improvements in the draft!
Sincerely,
Michelle
From: Philip Lafrance <Philip.Lafrance@isara.com>
Sent: Thursday, December 12, 2019 10:29 AM
To: Michelle Brochmann <mbrochmann@infoseccorp.com>
Subject: Some comments on the PKCS11 HSS Draft
Greetings Michelle,
I hope this e-mail finds you quite well.
My name is Philip Lafrance, from ISARA Corp. in Waterloo, Canada. I’ve only recently joined the PCKS#11 TC. Our team here has been developing, testing, and using HSS (and other hash-based schemes) for over four years now, and have amassed some knowledge in this area. Notably some of our team members were contributors to the HSS RFC. We have been working on a potential P11 draft as well, but it seems you beat us to the punch. If you would be so kind as to oblige me, I have some comments regarding your current draft.
First, regarding the private key data in section 1.1.3. The private key format for CKA_VALUE states: “8 bytes encoding the private key index as a big-endian integer (initially 0, then updated whenever a signature is performed).” A few points on this:
- This integer would max out at 2^64-1, while the scheme itself can support up to 2^200-1 given the parameter selection in section 1.1.2 and the maximum length of a signature (74,988 bytes) in section 1.1.5. Note: this maximum is obtained using 8 levels, each of height 25. Obviously, this is an impractical parameter set, but it is nonetheless allowed by the specification.
- If the rationale behind this value is that it can be clamped to a 64-bit integer, some hardware platforms may not support such an integer type.
- Perhaps the private key should have a well-defined PKCS8 format first?
Second, we have found that storing the state information with the private key is especially troublesome; for a few reasons. The possible consequences of these issues are that it allows for accidental reuse of state and implementation limitations. Here are some thoughts:
- Key transfer (e.g., Backup and Restore) would restore old state (state that has already been used). Accidental state reuse is by far the most important issue. Administrators are accustomed to blindly moving data from one machine to another, whether to restore keys created at key gen or to propagate keys across multiple machines in a cluster. While P11 cannot change IT administrator behaviour, the threat can be mitigated by keeping the state separate and instead forcing vendors to come up with custom solutions.
- Internal key store mechanisms may not allow mutable keys during signing. Flash memory is especially tricky in this regard; overwriting data in a single block would not replace the data. Flash chips merge data instead and writing new data will result in zeroing of old data.
- Internal signing operations may treat keys as a constant value. We found that many bodies of code use this model. The private key is passed in as a constant buffer and is expected to be immutable. If state is kept as part of the private key, then we run into issues with incrementing state.
- State is implementation defined (it is not defined in the HSS RFC). A single integer may point to a location in the Merkle tree, but the state could take many forms. With a single integer, the entire tree is stored in memory (which can be gigantic, again assuming the maximum state value can be held in that integer), or one must keep track of both an integer and the parameters of a tree traversal algorithm; and making sure they are in sync. There is a slew of Merkle tree traversal algorithms out there (the most famous of which is the BDS algorithm). By keeping track of only one integer, it would make such algorithms hard to manage (especially when considering the above points). Such trade-offs should be left to the hardware implementer.
By removing state from the private key, many of the above issues are mitigated. Hardware vendors can come up with custom ways to tackle any remaining issues, such as transferring state from one machine to another. We found that by treating the state as an object separate from the private-public key pair, users are forced to think of this scheme carefully.
I hope you will find these comments useful, and I look forward to your reply.
Best regards,
Philip Lafrance
--
| Philip Lafrance | Standards Manager |
www.isara.com · 560 Westmount Road North, Waterloo, Ontario N2L 0A9 CANADA | |
