Failure renewing root CA certificate - 0x80090016 NTE_BAD_KEYSET

We have a multi-tiered PKI infrastructure with a standalone, offline Root CA. Every year we go through a process of extending the root CA certificate (renewing while reusing existing keys) and reissuing the subordinate CA certificates. The server stays offline, except for that once per year process, when it is turned on, windows is patched, and then CA renewed.

This year, upon trying to renew the CA certificate from the certificate authority console, it would fail to generate a new certificate, but not provide any errors. When trying to issue the command certutil -renewCert ReuseKeys we would receive the following output:

437.2762.0:<2021/3/3, 14:10:1>: 0x2 (WIN32: 2 ERROR_FILE_NOT_FOUND): SOFTWARE\Microsoft\Cryptography\AutoEnrollment
437.2780.0:<2021/3/3, 14:10:1>: 0x2 (WIN32: 2 ERROR_FILE_NOT_FOUND): SOFTWARE\Microsoft\Cryptography\AutoEnrollment
437.2904.0:<2021/3/3, 14:10:1>: 0x80070002 (WIN32: 2 ERROR_FILE_NOT_FOUND)
437.1618.0:<2021/3/3, 14:10:1>: 0x80070002 (WIN32: 2 ERROR_FILE_NOT_FOUND)
437.625.0:<2021/3/3, 14:10:1>: 0x80070002 (WIN32: 2 ERROR_FILE_NOT_FOUND): CADescription
437.625.0:<2021/3/3, 14:10:1>: 0x80070002 (WIN32: 2 ERROR_FILE_NOT_FOUND): ParentCAName
420.385.0:<2021/3/3, 14:10:1>: 0x2 (WIN32: 2 ERROR_FILE_NOT_FOUND)
3109.1367.0:<2021/3/3, 14:10:1>: 0x80090016 (-2146893802 NTE_BAD_KEYSET): <root CA Name>
3109.1368.0:<2021/3/3, 14:10:1>: 0x2 (WIN32: 2 ERROR_FILE_NOT_FOUND)
3109.1369.0:<2021/3/3, 14:10:1>: 0x20 (WIN32: 32 ERROR_SHARING_VIOLATION)
201.970.0:<2021/3/3, 14:10:1>: 0x80090016 (-2146893802 NTE_BAD_KEYSET): Exception at ds\security\services\ca\fs\crypto\cngcryptofactory.cpp(441): NCryptOpenKey(hProv, &hKey, pwszKeyName, nLegacyKeySpec, acquireToOpenKeyFlags(fAcquire)) HRESULT = 0x80090016
201.1128.0:<2021/3/3, 14:10:1>: 0x80090016 (-2146893802 NTE_BAD_KEYSET)
201.2448.0:<2021/3/3, 14:10:1>: 0x80090016 (-2146893802 NTE_BAD_KEYSET)
310.3755.0:<2021/3/3, 14:10:1>: 0x80090016 (-2146893802 NTE_BAD_KEYSET)
310.3829.0:<2021/3/3, 14:10:1>: 0x80090016 (-2146893802 NTE_BAD_KEYSET)
CertUtil: -renewCert command FAILED: 0x80090016 (-2146893802 NTE_BAD_KEYSET)
CertUtil: Keyset does not exist
449.199.0:<2021/3/3, 14:10:1>: 0x80090016 (-2146893802 NTE_BAD_KEYSET)

After several hours of troubleshooting, the problem was solved in a most unlikely way. I am posting this for others who may run into this strange bug, with the answer added below.

EDIT: I also subsequently found the following audit failure in the Security event log each time I tried to renew the cert:

Cryptographic operation.

Subject:
    Security ID:        <ca host name>\Administrator
    Account Name:       Administrator
    Account Domain:     <ca host name>
    Logon ID:       0x4BD68

Cryptographic Parameters:
    Provider Name:  Microsoft Software Key Storage Provider
    Algorithm Name: UNKNOWN
    Key Name:   <keystore name>
    Key Type:   Machine key.

Cryptographic Operation:
    Operation:  Open Key.
    Return Code:    0x80090016

afterwards, when it worked, the event showed:

Cryptographic operation.

Subject:
    Security ID:        <ca host name>\Administrator
    Account Name:       Administrator
    Account Domain:     <ca host name>
    Logon ID:       0x4BD68

Cryptographic Parameters:
    Provider Name:  Microsoft Software Key Storage Provider
    Algorithm Name: RSA
    Key Name:   <keystore name>
    Key Type:   Machine key.

Cryptographic Operation:
    Operation:  Open Key.
    Return Code:    0x0

It turns out this appears to be some kind of windows bug.

I did only two things between the time it didn't work, and the time it did work.

1. I opened the Certificate Management MMC and navigated to Trusted Root Certification Authorities and right-clicked and chose to export one of the existing root CA certificates for my system. But, I cancelled the export.
2. I opened Google Chrome and downloaded Process Monitor.

I believe step 2 resolved the issue for some strange reason. I suspect this kicked off a renewal of some root certificates on the server. In addition, this was confirmed in the Windows Application log with the following event:

Successful auto update of third-party root certificate:: Subject: <OU=Starfield Class 2 Certification Authority, O="Starfield Technologies, Inc.", C=US> Sha1 thumbprint: <AD7E1C28B064EF8F6003402014C3D0E3370EB58A>.

- <Event xmlns="http://schemas.microsoft.com/win/2004/08/events/event">
- <System>
  <Provider Name="Microsoft-Windows-CAPI2" Guid="{5bbca4a8-b209-48dc-a8c7-b23d3e5216fb}" EventSourceName="Microsoft-Windows-CAPI2" /> 
  <EventID Qualifiers="0">4097</EventID> 
  <Version>0</Version> 
  <Level>4</Level> 
  <Task>0</Task> 
  <Opcode>0</Opcode> 
  <Keywords>0x8080000000000000</Keywords> 
  <TimeCreated SystemTime="2021-03-03T19:19:29.273730500Z" /> 
  <EventRecordID>6046</EventRecordID> 
  <Correlation ActivityID="{A236C963-0FA7-0001-19CA-36A2A70FD701}" /> 
  <Execution ProcessID="996" ThreadID="1356" /> 
  <Channel>Application</Channel> 
  <Computer>removed</Computer> 
  <Security /> 
  </System>
- <EventData>
  <Data>OU=Starfield Class 2 Certification Authority, O="Starfield Technologies, Inc.", C=US</Data> 
  <Data>AD7E1C28B064EF8F6003402014C3D0E3370EB58A</Data> 
  </EventData>
  </Event>

After the ridiculous waste of time on this issue, I figured it would be helpful to post this solution here for others. I suspect the automatic certificate update played a roll, because I also dealt with other certificate errors this year in regards to third party root certificates that expired at the end of 2020.