"Unable to validate Signature" in responses from some Azure AD IdPs, but not others

[pa...@elphin.com]

Trying to integrate a customer's Azure AD into SimpleSAMLphp 1.14.17 running as an SP. I can get this working fine with my own Azure AD, but attempting to authenticate via the customer's AD results in the error "Unable to validate Signature" 

• In both cases, the XML  entity descriptor has been pulled from https://login.microsoftonline.com/xxxx-xxx-xxxx/federationmetadata/2007-06/federationmetadata.xml and converted to SimpleSAMLphp format
• The descriptors contain 3 signing keys - these are identical, Microsoft appear to use the same keys for all Azure ADs. They are all up to date.
• We've enabled debug logging in SimpleSAMLphp

The backtrace we get on failure is

Backtrace:
0 /xxx/vendor/simplesamlphp/simplesamlphp/www/module.php:180 (N/A)
Caused by: Exception: Unable to validate Signature
Backtrace:
6 /xxx/vendor/simplesamlphp/saml2/src/SAML2/Utils.php:157 (SAML2_Utils::validateSignature)
5 /xxx/vendor/simplesamlphp/saml2/src/SAML2/Assertion.php:584 (SAML2_Assertion::validate)
4 /xxx/vendor/simplesamlphp/simplesamlphp/modules/saml/lib/Message.php:201 (sspmod_saml_Message::checkSign)
3 /xxx/vendor/simplesamlphp/simplesamlphp/modules/saml/lib/Message.php:552 (sspmod_saml_Message::processAssertion)
2 /xxx/vendor/simplesamlphp/simplesamlphp/modules/saml/lib/Message.php:524 (sspmod_saml_Message::processResponse)
1 /xxx/vendor/simplesamlphp/simplesamlphp/modules/saml/www/sp/saml2-acs.php:129 (require)
0 /xxx/vendor/simplesamlphp/simplesamlphp/www/module.php:137 (N/A)

The debugging log entries leading up to his failures show tis

Nov 17 13:14:32 simplesamlphp DEBUG [134d85d59d] Loading state: '_0b6f8ad0000e9b3cafc107aac391826798ccb266fd'
Nov 17 13:14:32 simplesamlphp DEBUG [134d85d59d] Received SAML2 Response from 'https://sts.windows.net/xxxx-xxxx-xxxx-xxxx-xxxx/'.
Nov 17 13:14:32 simplesamlphp DEBUG [134d85d59d] Has 3 candidate keys for validation.
Nov 17 13:14:32 simplesamlphp DEBUG [134d85d59d] Validation with key #0 failed without exception.
Nov 17 13:14:32 simplesamlphp DEBUG [134d85d59d] Validation with key #1 failed without exception.
Nov 17 13:14:32 simplesamlphp DEBUG [134d85d59d] Validation with key #2 failed without exception.
Nov 17 13:14:32 simplesamlphp DEBUG [134d85d59d] Has 3 candidate keys for validation.
Nov 17 13:14:32 simplesamlphp DEBUG [134d85d59d] Validation with key #0 failed with exception: Unable to validate Signature
Nov 17 13:14:32 simplesamlphp DEBUG [134d85d59d] Validation with key #1 failed with exception: Unable to validate Signature
Nov 17 13:14:32 simplesamlphp DEBUG [134d85d59d] Validation with key #2 failed with exception: Unable to validate Signature
Nov 17 13:14:32 simplesamlphp ERROR [134d85d59d] SimpleSAML_Error_Error: UNHANDLEDEXCEPTION

Compare with this trace for a successful response from a different AzureAD

Nov 17 13:30:11 simplesamlphp DEBUG [134d85d59d] Received SAML2 Response from 'https://sts.windows.net/yyyy-yyyy-yyyy-yyyy-yyyy/'.
Nov 17 13:30:11 simplesamlphp DEBUG [134d85d59d] Has 3 candidate keys for validation.
Nov 17 13:30:11 simplesamlphp DEBUG [134d85d59d] Validation with key #0 failed without exception.
Nov 17 13:30:11 simplesamlphp DEBUG [134d85d59d] Validation with key #1 failed without exception.
Nov 17 13:30:11 simplesamlphp DEBUG [134d85d59d] Validation with key #2 failed without exception.
Nov 17 13:30:11 simplesamlphp DEBUG [134d85d59d] Has 3 candidate keys for validation.
Nov 17 13:30:11 simplesamlphp DEBUG [134d85d59d] Validation with key #0 succeeded.

In both cases, the Signature in the SAML response is formed in the same way:

<Signature xmlns="http://www.w3.org/2000/09/xmldsig#">
  <SignedInfo>
    <CanonicalizationMethod Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#"/>
    <SignatureMethod Algorithm="http://www.w3.org/2001/04/xmldsig-more#rsa-sha256"/>
    <Reference URI="#_52cdf98a-b3d7-4940-a347-f1bf24abe606">
      <Transforms>
        <Transform Algorithm="http://www.w3.org/2000/09/xmldsig#enveloped-signature"/>
        <Transform Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#"/>
      </Transforms>
      <DigestMethod Algorithm="http://www.w3.org/2001/04/xmlenc#sha256"/>
      <DigestValue>ddddddd</DigestValue>
    </Reference>
  </SignedInfo>
  <SignatureValue>vvvv</SignatureValue>
  <KeyInfo>
    <X509Data>
      <X509Certificate>xxxx</X509Certificate>
    </X509Data>
  </KeyInfo>
</Signature>

If anyone has any thoughts on what might be happening here, they would be gratefully received. We're adding more debug tracing into the signature processing, so if that turns up something I'll report back....

[Paul Dixon]

We had the customer recreate the app setup in Azure AD from scratch, and it worked perfectly. So, this was caused by some unknown misconfiguration in AD. Unfortunately, I don't know what that was, but if anyone else experiences the same problem, I would suggest trying this!