You may see this authentication error when attempting to log in to a server using RDP (Remote Desktop). The issue generally impacts Windows Server 2012/2016. The new error message, added by Microsoft on May 8, 2018, indicates a specific patch issue.

A security update to address a remote code execution vulnerability was pushed to Server 2012/2016 in March 2018. In May, Microsoft pushed a patch to all workstation OS to enforce this server-side patch. It will refuse to connect to any server which does not have the patch. Though it looks like a server-side issue, the patch is actually on the client/workstation side.
The long-term fix is to patch all 2012/2016 servers with the patch released in March. In the short term, you can apply a registry fix on the WORKSTATION that cannot connect. Add the following registry key with a DWORD value of 2:

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\System\CredSSP\Parameters
Add a DWORD value of 2: “AllowEncryptionOracle”

The key can be pushed via GPO or done individually by hand on each workstation. This turns off the patch. Once the server side patching is done it will need to be removed or changed to a value of 0 (enforced). Updating the key is a temporary workaround until patching can be completed on your 2012/2016 servers.