Azure VM Remote Desktop error- CredSSP encryption oracle remediation

I ran into an issue where I could not Remote Desktop to my Azure VM and was getting this error:

Remote Desktop Connection
An authentication error has occurred.
The function requested is not supported

Remote computer: 13.64.xx.xxx
This could be due to CredSSP encryption oracle remediation.
For more information, see https://go.microsoft.com/fwlink/?linkid=866660

The issue was a March 2018 security update patch that was applied to my CLIENT computer, so I cannot connect to the Azure SERVER Windows Server 2012 R2 Datacenter VM that has not had updates applied recently.

https://blogs.technet.microsoft.com/mckittrick/unable-to-rdp-to-virtual-machine-credssp-encryption-oracle-remediation/

Examples:
1.       If the client is updated and you try to RDP to an Azure VM that was not updated, then it will be blocked and see the error message.
2.       If the client is not patched while server is updated, RDP can still work. But the session will be exposed to the attack.
3.       If both client & server are patched with default setting (Mitigated), RDP will work in a secure way.

I really could not find a solution anywhere that worked. Just a bunch of links to archaic Windows Updates websites from the early 2000’s (reminds me how far we came)

Solution

The solution is to Uninstall the KB on your CLIENT computer so you can install the KB on your SERVER VMs, then you can reinstall the KB on your CLIENT if you would like.

Detailed Steps

1. I UNINSTALLED the KB4103721 from my Windows 10 machine, so I could patch my VM’s and rebooted.
   1. 
2. I RDP’ed from my CLIENT to each SERVER that was not patched, and installed the patch (note a different OS so a different KB patch)
3. Applied Installed a KB on each SERVER and rebooted http://www.catalog.update.microsoft.com/Search.aspx?q=KB4103715
   1. 
   2. 
4. On my CLIENT Windows 10 PC, I reinstalled the KB
   1. Go to https://portal.msrc.microsoft.com/en-us/security-guidance/advisory/CVE-2018-0886 and find your OS, then click Security Update
   2. 
   3. Continue to download the appropriate patch (https://www.catalog.update.microsoft.com/Search.aspx?q=KB4103721)
   4. 
   5. Once downloaded, install the KB
   6. 

That’s it! I could not find an easy explanation of what KB to uninstall and which one to install.

A side note, if I enabled automatic updates, I think this wouldn’t have happened. My SharePoint VMs are not patched automatically since they are Dev machines.

Hope this helps.