Outlook connectivity test fails / Office365 SMTP - SAML Assertion Invalid Signature

Question

we have developed our own SAML IDP and have configured Office365 for federation to our SAML IDP. We can login to Office365, Teams, etc all with no errors. However, when we try the Outlook connectivity test at https://testconnectivity.microsoft.com, or when we attempt to send an SMTP email through smtp.office365.com, then we are getting a failure. The failure is shown below for the Outlook connectivity test (personal information changed)

X-CalculatedBETarget: MW4PR14MB5440.namprd14.PROD.OUTLOOK.COM X-BackEndHttpStatus: 503 X-RUM-Validated: 1 X-AutoDiscovery-Error: LiveIdBasicAuth:FederatedStsUnreachable:<UNH:<PII.Email:7J+GS+4rufdDUc9R4mr7Ifl48VhyJ296RJq6lQpEsKg=@softexinc.com>><RequestId=7fdb0084-ea19-4729-8290-aa2a663cbaba,ST=23:03:23><UIPH:<PII.IP:aU/9Mm6Oy7mcCIl2kWkA43wQoeRe2WNIcRrp/8UOlNo=>><HitHrd<X-forwarded-for:<PII.IP:aU/9Mm6Oy7mcCIl2kWkA43wQoeRe2WNIcRrp/8UOlNo=>><PTS:False><BA:255,UP:-46840,ExCaught:False,BlockStatus:1><IOOH<IV1OOH<SHIBB-Business-1717ms><SAML_F:T:,M:STSFailure,E:Saml Assertion has invalid signature<?xml version='1.0' encoding='UTF-8'?><SOAP-ENV:Envelope xmlns:SOAP-ENV="http://schemas.xmlsoap.org/soap/envelope/"><SOAP-ENV:Header><ECP:Response xmlns:ECP="urn:oasis:names:tc:SAML:2:0:profiles:SSO:ecp" AssertionConsumerServiceURL="https://login.microsoftonline.com/login.srf" SOAP-ENV:actor="http://schemas.xmlsoap.org/soap/actor/next" SOAP-ENV:mustUnderstand="1" /></SOAP-ENV:Header><SOAP-ENV:Body> <SAML RESPONSE IS HERE> </SOAP-ENV:Body></SOAP-ENV:Envelope>><SAML:AddV2N><FEDERATED><UserType:Federated><LogonFailed-FederatedStsFailed><AS:FederatedStsFailed><Tid=8ccccceb-0040-4e3e-a7bc-733ee9f8ef80><V1; X-DiagInfo: MW4PR14MB5440 X-BEServer: MW4PR14MB5440 X-Proxy-RoutingCorrectness: 1 X-Proxy-BackendServerStatus: 503 X-FirstHopCafeEFZ: DSM X-FEProxyInfo: DS7PR06CA0008.NAMPRD06.PROD.OUTLOOK.COM X-FEEFZInfo: DSM X-FEServer: DS7PR06CA0008 Content-Length: 0 Date: Fri, 09 Sep 2022 05:35:18 GMT Server: Microsoft-IIS/10.0 X-Powered-By: ASP.NET

We get a call into our IDP's SAML ECP SOAP endpoint (ActiveLogOnUri) where we build the SAML Response/Assertion to return and we sign both the Response and Assertion with our SAML signing certificate (same certificate that is set in Office 365 federation as the SigningCertificate). We return successfully from our SAML ECP SOAP endpoint, and then see the error above.

If we take our SAML Response and put it in the SAML Response Validater at https://www.samltool.com/validate_response.php, we see that the response and XML signature is validated. We also wrote a C# code to read the SAML response and validate the signature using the SignedXML class. One note: our SAML response is returned with no extra whitespace/newlines. We sign the SAML response with no extra whitespace/newlines and return the response from the SAML ECP SOAP endpoint the same way, so we don't think this is related to whitespace.

We can not figure out why Office365 returns this SAML Invalid Signature error ONLY when the SAML ECP SOAP endpoint is invoked via the Outlook connectivity test or SMTP email sending. Any help is appreciated.