I was getting this strange error in Windows Server 2012 even after installing the right Signature certificates for SP in ADFS. The error logs shows something like this :
The Federation Service encountered an error while processing the SAML authentication request.
Additional Data
Exception details:
System.IdentityModel.SignatureVerificationFailedException: MSIS0038: SAML Message has wrong signature. Issuer: 'XXX-XXX-XX'.
at Microsoft.IdentityServer.Protocols.Saml.Contract.SamlContractUtility.CreateSamlMessage(MSISSamlBindingMessage message)
at Microsoft.IdentityServer.Service.SamlProtocol.SamlProtocolService.Issue(IssueRequest issueRequest)
at Microsoft.IdentityServer.Service.SamlProtocol.SamlProtocolService.ProcessRequest(Message requestMessage)
After several hours of unproductive debugging I found that this is a known ADFS issue and has nothing to do with validity of certificates, thumbprints, etc..
Microsoft has provided the below update to rectify this issue.
This issue occurs if the system has security update 2843639 installed on Windows 2012 Server.