Exchange Hybrid TLS negotiation failed with error NoCredentials

Recently I ran the Hybrid Configuration Wizard in an Exchange 2016 and Exchange 2019 environment. There were also two Edge Transport servers in this environment. One Exchange 2016 CU12 Edge Transport server is used for internet communication, one Exchange 2019 CU1 Edge Transport server (running on Windows 2019 Server Core) is used for hybrid communication. This server was selected in the Hybrid Configuration Wizard, proper certificate was selected etc. and the Hybrid Configuration Wizard finished successfully.

When the wizard finished the Receive Connector on the Edge Transport server was modified for hybrid mail flow. Validating the Send Connector from Exchange Online to Exchange on-premises revealed no issues, the test message was successfully sent and received in my mailbox.

But message flow from Exchange on-premises to Exchange Online was not working and mail was stuck in the Queue on the Edge Transport server. Looking at the Queue it seems there’s a time-out issue since it says:

LastError : [{LED=451 4.4.395 Target host responded with error. -> 421 4.4.1 Connection timed out};{MSG=};{FQDN=exchangelabsnl-mail-onmicrosoft-com.mail.protection.outlook.com}; {IP=104.47.10.36};{LRT=5/2/2019 6:32:14 AM}]

421 4.4.1 connection timed out

It is not a firewall issue, I can use Telnet to connect on port 25 and send a message to myself (which arrives in the junk mail folder, but it arrives).

Opening the Send Connector protocollog file (enable in on the outbound connector first) shows a different error. When trying to execute the TLS handshake it fails with TLS negotiation failed with error NoCredentials.

TLS Negotiation failed with error NoCredentials

This is strange since the same certificate is used by the Receive Connector (you can check this using https://checktls.com and entering the FQDN of the Exchange server holding the Receive Connector).

The “TLS negotiation failed with error NoCredentials” looks like a private key issue with the certificate (according to Microsoft kb article KB4495258) but PowerShell shows it does have a private key:

Has Private Key

When going back to the protocol logfile you can see the certificate thumbprint in the data field, and this thumbprint didn’t match the thumbprint of the certificate that Get-ExchangeCertificate returned.

Certificate Thumbprint

But, Get-ExchangeCertificate only returns certificates that have a private key, if there isn’t a private key nothing is returned.

When opening the certificate store using PowerShell using the following commands:

CD Cert:
Cd LocalMachine
Set-Location my
Get-ChildItem

All certificates in the store are shown, and when checking the certificate with the thumbprint we got from the protocol log, this one does not have a private key:

Check private key

That explains the NoCredentials error messages. Use the following command to remove the wrong certificate:

Get-ChildItem | ?{$_.Thumbprint -like “B79*”} | Remove-Item

After restarting the Transport service cross-premises mail flow works again.

The main question is of course how this happened. I’m not sure, but I do remember requesting several certificates at the same time (a few weeks ago) and there were a few errors. I didn’t pay too much attention to this since everything seemed to work fine. But in the end it turned out to be not the case, and I didn’t notice in the first place because of inbound SMTP working fine. Sigh…. 😊

 

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s