When you see an error like this that means the user/client/caller is trying to authenticate with a credential type that the KDC says is unsupported (the error is literally correct). This can happen for any number of specific reasons, but it basically boils down to this formula:
- Client (computer) is configured to tell KDC it supports X, Y, Z encryption types
- User in AD has X, Y, Z keys and is configured to be allowed to use X, Y, Z encryption types
- Krbtgt account has X, Y, Z keys and is configured to be allowed to use X, Y, Z encryption types
The client sends X, Y, Z and the KDC compares that with the list configured for the user. If there's an intersection of any of them then the strongest is chosen. Repeat against the krbtgt account, and then again for whatever service account they're requesting a ticket to.
In your case you've disabled RC4, so remove X from the equation. That leaves AES 128 and AES 256. Kerberos MUST have a key for each specific encryption type to use it, and the KDC only knows these keys for the user when they rotate their password. AES was added in 2008. If they have a sufficiently old account and haven't changed their password since then, they'll only have RC4 (X), where the KDC is expecting Y and Z to be present.
As such there is no intersection of encryption types and the system falls over, returning that error. Repeat this process for krbtgt, the computer account, and the service principal you're getting a ticket to.
Long story short: go have them reset their password (seriously, how old is that password?). Then for good measure go reset the krbtgt password.
I notice Microsoft's example of the "legitimate SPN" is Ldap/machine1.contoso.com/contoso.com - missing the @FQDN.COM at the end of what my user's machine is attempting to send.
The @FQDN.COM is always implied within Windows and is there to disambiguate domains when all you're presented with is an SPN. It provides a hint to other parts of the system that it should go directly to that particular domain.
host/somemachine is the same as foo/somemachine.yourdomain.com which is the same as host/
somemachine.yourdomain.com@yourdomain.com which is wholly different from host/
somemachine.yourdomain.com@someotherdomain.com. The latter tells the client that you
know they gotta go to another domain to get the ticket, so just skip the searching and go straight there.
For completeness SPNs come in 2 forms: the two-part SPN service/name[@domain] and the three-part SPN service/name/domain[@domain]. The former represents any service in the domain and is the usual run of the mill service, nothing special. The second form indicates that the service is
only run on a domain controller. It is a way to tell every party that if you've presented this and the service
isn't a domain controller then something
very bad just happened. LDAP is one of those services for instance.