Just run into this “CredSSP encryption oracle remediation” error message while trying to connect to Windows Server 2016 from Windows 10 client today. This issue is explained in MSFT KB article – “CredSSP encryption oracle remediation” error when RDP to a Windows VM in Azure and it all boils down to specific updates missing either on the server or on the client. In my case I was sure that my client box was fully updated and it was un-patched server outside of my control which was a culprit. For this scenario workaround is to set Encryption Oracle Remediation policy to Enabled, and then change Protection Level to Vulnerable. Fastest way to do it on standalone box is to add registry key, which we can do using REG ADD command:
For workaround which works in un-patched client connecting to patched server scenarion refer to aforementioned MSFT KB article.