User Certificate's show "Cannot find the certificate and private key for decryption." in Windows

Have a number of computers where user certificates suddenly stop working.

Running certutil -silent -user -store my shows that all user certificates for the affected user have stopped working.

    my
================ Certificate 0 ================
Serial Number: 2a0000210be8f0775a3a2e2b7200040000210b
Issuer: CN=PROD Issuing CA, DC=somecompany, DC=Com, DC=Au
 NotBefore: 10/01/2017 7:46 AM
 NotAfter: 10/01/2018 7:46 AM
Subject: CN=username, OU=somecompany, OU=Level 1, OU=Laptop Users, OU=Special Group Users, DC=somecompany, DC=Com, DC=Au
Non-root Certificate
Template: 1.3.6.1.4.1.311.21.8.4586432.4805332.10505398.7351119.9274134.0.14270575.7769536
Cert Hash(sha1): cc 3b d0 2c 03 a1 d9 d4 0d 28 31 a7 84 c8 6d cb 6d 97 27 d8
  Key Container = 48fa6c038e897eb98ea252b465308c55_7cc43284-5d87-4ba0-8673-6fb4d4de8f2d
  Provider = Microsoft Enhanced Cryptographic Provider v1.0
Cannot find the certificate and private key for decryption.

================ Certificate 1 ================
Serial Number: 7b4d6131959b5f6cd272
Issuer: CN=Communications Server
 NotBefore: 25/08/2017 10:41 AM
 NotAfter: 25/08/2017 6:41 PM
Subject: CN=someguy@somecompany.com.au
Non-root Certificate
Template: 
Cert Hash(sha1): 80 25 75 64 60 77 21 16 35 18 ee 04 4f 87 bc 5f f0 ae b3 2a
  Key Container = OC_KeyContainer_Lync_someguy@somecompany.com.au
  Provider = Microsoft Enhanced Cryptographic Provider v1.0
Cannot find the certificate and private key for decryption.

Checking %APPDATA%\Microsoft\Crypto\RSA folder can see the private key files are present i.e. in this case of first certificate 48fa6c038e897eb98ea252b465308c55_7cc43284-5d87-4ba0-8673-6fb4d4de8f2d.

What are potential causes for this issue ? I suspect the encryption key for the private key is being erased/modified; but wonder how to confirm if this is being changed.

In this case we use the Cert Hash(sha1) to find the user’s certificate in %APPDATA%\Microsoft\SystemCertificates\My\Certificates\CC3BD02C03A1D9D40D2831A784C86DCB6D9727D8 which is present.

Then using key container field we find the private key in %APPDATA%\Microsoft\Crypto\RSA\S-1-5-21-2091123715-180627453-533688462-45495\48fa6c038e897eb98ea252b465308c55_7cc43284-5d87-4ba0-8673-6fb4d4de8f2d which is also present.

The files were modified:

• SystemCertificates file CC3BD02C03A1D9D40D2831A784C86DCB6D9727D8 was last modified 25/08/2017 10:55am. Was this when a new key was requested i.e. had user reported problem before this time?

• Private key file under %APPDATA%\Microsoft\Crypto\RSA\S-1-5-21-2091123715-180627453-533688462-45495\48fa6c038e897eb98ea252b465308c55_7cc43284-5d87-4ba0-8673-6fb4d4de8f2d was last modified 10/01/2017 7:56 am (Close to time issued on system certificate file)

• The private key was encrypted with master key stored in %APPDATA%\Microsoft\Protect\<user SID>\c77f3872-e1e2-4449-9729-cc97e85e4a3c which was last modified 25/07/2017 8:19 am

• The Protect folder containing master key used to decrypt private keys, has files last modified on 14/08/2017 8:23am

• %APPDATA%\Microsoft\SystemCertificates\My\Certificates has 0 byte certificate files modified 12/07/2017 12:00am – 7:50 am at different intervals and 8/06/2017 11:52 pm – 9/06/2017 8:33 am every 8 minutes

Currently we are using Windows auditing to look for modifications to %APPDATA%\Microsoft\SystemCertificates folder and %APPDATA%\Microsoft\Crypto and %APPDATA%\Microsoft\Protect

However given that the certificate and private key files seem to exist, not sure if this will identify cause.

The application log also has errors for CertificateServicesClient-AutoEnrollment source:

Automatic certificate enrollment for domain\username failed (0x8007003a) The specified server cannot perform the requested operation.

Any recommended steps for further identifying root cause of "Cannot find the certificate and private key for decryption." error?

The issue seems to be cause by remote password resets. In a test environment replicated the issue:

• Server 2012 R2 Domain Controller with Certificate Authority configured with Auto Enrollment

• Windows 7 x64 client joined to domain

• Isolated network hosting only the DC and client

• User certificate template with exportable private key

1. Deployed User Certificate to client via Auto Enrollment Group Policy
2. Removed client from network
3. Confirmed user could export private key for certificate allowing export using certmgr on Windows 7 client
4. Reconnected client to network
5. Reset password of user logged onto client from the domain controller
6. Used “Run As” to cache the updated password on client
7. Disconnected client from network
8. Logged off / Logged on disconnected from network with the updated cached credentials
9. Cannot export the private key
10. Reconnected client to network
11. Cannot export the private key
12. Log off / Log on connected to network – Can now export private key again

Private keys are protected by encrypting using master keys stored in %APPDATA%\Microsoft\Protect\\ The master keys are further encrypted by a combination of items, including the user's password. If the master key can't be decrypted, the private key can't be used.

Password Change Method - Ctrl+Alt+Del "Change Password" on client

Using Process Monitor identified Local Security Authority Process (LSASS.exe) performs the following actions:

1. Communication with domain controller over port TCP port 88 (kerberos) and TCP port 464 (kpasswd / kerberos v5)
2. Update reg key under HKLM\Security\Cache
3. Write to \domaincontroller\PIPE\protected_storage
4. User Profile Serivce updates HKLM\Software\Microsoft\Windows NT\CurrentVersion\ProfileList\\RefCount
5. Update master keys, used to decrypt private keys:

%APPDATA%\Microsoft\Protect\\

6. Read SYNCHIST & CREDHIST file under %APPDATA%\Microsoft\Protect
7. Update %APPDATA%\Microsoft\Protect\SYNCHIST file
8. Process 1-7 may repeat several times
9. Update C:\Windows\debug\PASSWD.log with message "Attempting password change server/domain for user

Private keys continune to work due to steps 5 - 7.

Password Change Method - Remote reset via Active Directory Users & Computers

1. SYNCHIST & Master key files are not automatically updated instantly
2. Log Off / Log On on network updates SYNCHIST and Master key files, Certificates are OK