[ksk-rollover] Root Zone KSK Rollover and HSM Update

[Michael StJohns]

On 7/31/2023 10:23 AM, Jakob Schlyter via ksk-rollover wrote:
> On 2023-07-31 at 14:53, Frederico A C Neves via ksk-rollover wrote:
>
>>  From our experience besides admin interfaces, standard APIs for
>> regular operations, generating keys, sign, verify etc... are available
>> (PKCS#11/KMIP) from multiple vendors. But exporting/importing a key,
>> specially with the no-export attribute set, among vendors is not
>> available.
> I concur; moving keys not marked as CKA_EXTRACTABLE (at time of generation) is generally not supported (due to FIPS requirements).
>
> 	jakob
>

A long while back (~15 years), I approached the CTO of a crypto token 
company about this specific problem.  I had a need to be able to use the 
same root key pair for 20+ years over many different technologies/device 
types.  He made a simple suggestion - generate the key pair outside the 
HSM, generate an encryption key, encrypt the private key, split the 
encryption key using Shamirs Secret Sharing.  Print everything to 
archival paper.  Lock up the printed shares in different places that 
were set up for physical escrow of intellectual property.  When you need 
to load the stuff on a new device or new technology, combine the shares, 
decrypt the private key and load the HSM from the reconstituted keys.

We ended up building a set of tools to do this - the key generation tool 
to print the shares, and the key combination tool to decrypt the private 
key.  Every few years we send a few people out to a randomly selected PC 
parts place to randomly select a motherboard and all the parts we need 
to build a disk-less PC.  We built a Linux live DVD (read-only) to run 
it.   As part of all of this, we selected a good HSM that had both a 
rack mount format and a compatible PCIe card - the latter for use on the 
kiosk PC. Using the backup/restore functions we could load the kiosk HSM 
with the master keys the other HSM, create a PKCS11 token and key set, 
and back up that token.  We could then secure wipe the kiosk HSM, and 
load the back up into the production HSM.

The hardest part about the above is making sure data doesn't exfiltrate 
to things like printers (which sometimes sneakily have NV storage) via 
the USB connections.  We actually considered shredding the printer after 
share creation, but believed we had locked things down enough that we 
shouldn't have an issue if we followed the correct steps and protected 
the tools when not in use (e.g. tamper bags, serialize tamper packaging)

Our first technology was a PCMCIA card, our second was big iron HSMs 
with PKCS11 support.  We've moved technology generations once within our 
current vendor and don't expect to have issues doing it again.

There are quite a number of "rituals" needed to support something like 
this, and ours have evolved over many years.  We use tamper bags and 
envelopes for the printed shares.  We've got safe deposit boxes that 
require two party access to get to for most shares. Etc, etc.

----------------------------------
The above is one thought.
----------------------------------

Another approach is to use RSA threshold signatures based on Shoup's 
Practical Threshold Signatures paper.  An implementation of this is here 
https://github.com/sweis/threshsig.

A long while back (~2005) I wrote a DNSSEC signing tool using that as a 
core.   This approach has a neat attribute - all the partial signature 
blobs are public and can be combined by anyone without the need for them 
to have a copy of any secrets.  The KSK signing authority would send out 
something to be signed to the N key share holders and would get back ~N 
partial signatures over that data.  Those partial signatures would be 
published, and the KSK signing authority would then publish a signature 
derived from M of those partial signatures to the DNS once verified.  
The output of the combining operation is verifiable using normal RSA math.

This would obviate the need for a central HSM and people actually 
showing up to the facility to do the work.  There would still be a need 
for a central facility to generate the individual key shares and provide 
them to the key share holders.

All of my implementations were soft-keys, but it shouldn't be all that 
hard to build a smart card applet that does the partial signature 
stuff.  I can think of a few ways to further secure these so it would be 
difficult or impossible to extract information from them without the 
collaboration of a few other key share cards.

The way the math works, possession of less than N key shares provides an 
attacker with no information.


The FROST2 threshold signature stuff currently wending its way through 
the CFRG does similar things for EC signatures - unfortunately not ECDSA 
compatible.  That would require publication of a different EC signature 
algorithm with the associated time to implement and deploy.

----------------------------------

The above is a long way of saying - don't get hung up on a set of HSM 
requirements that may have made sense originally, but might be 
problematic now.   It's probably time to reassess the HSM requirements 
in light of small number of big iron HSMs vendors left.


Mike