Exchange 2013 Hybrid Mail Flow Issues: TLS negotiation failed with error NoCredentials

While testing mail flow in a Exchange 2013 hybrid configuration with a new Office 365 tenant, messages between on premise and Office 365 mailboxes were not being received. However, communication between on premise mailboxes worked, as well as, Office 365 mailboxes and to all external recipients. Eventually, the messages in the queue timed out and NDRs were received, such as this…

Remote Server returned '< #4.4.7 smtp;550 4.4.7 QUEUE.Expired; message expired>'


After confirming the external firewall was configured with the correct rule sets using the listed Exchange Online Protection IP addresses, and enabling logging for all on premise send and receive connectors in Exchange 2013, I contacted support.

Through support’s assistance, we quickly resolved the matter of mail flow from the Office 365 mailboxes to on premise mailboxes by enabling ‘Opportunistic TLS’ for the “inbound” connector from the O365 Exchange Admin Center (EAC). However, that setting change did nothing to resolve the mail flow issues from on premise mailboxes to Office 365 mailboxes. Additional investigation needed to be performed.

From the Exchange 2013 server, we reviewed the transport settings (get-transportserver | fl), the certificates (get-exchangecertificate | fl) and set the ‘Outbound to Office 365’ send connector Delivery option to “Route mail through smart hosts” using the address for the MX record provided in your Office 365 DNS management page (i.e. and enabled “Use the external DNS lookup setting on servers with transport roles”. Still, mail flow from on premise to Office 365 did not work.

Next, also from the Exchange 2013 server, we installed the telnet client and successfully confirmed access of the Office 365 SMTP servers via telnet (on port 25) using our MX record address. Additional testing of mail from external senders to Office 365 was received successfully.

In the O365 EAC > Mail Flow > Accepted Domains, the default domain was set from “Authoritative” to “Internal Relay” and, still, mail flow from on premise to Office 365 did not work.

Then, in reviewing the SMTP send logs (C:\Program Files\Microsoft\Exchange Server\V15\TransportRoles\Logs\Hub\ProtocolLog\SmtpSend), the following connection was found repeated many times over with this error “TLS negotiation failed with error NoCredentials“.

2014-12-23T20:08:01.137Z,Outbound to Office 365,08D1ECFA4B38037F,0,,,*,,attempting to connect
2014-12-23T20:08:01.231Z,Outbound to Office 365,08D1ECFA4B38037F,1,,,+,,
2014-12-23T20:08:01.341Z,Outbound to Office 365,08D1ECFA4B38037F,2,,,<,"220 Microsoft ESMTP MAIL Service ready at Tue, 23 Dec 2014 20:07:59 +0000",
2014-12-23T20:08:01.341Z,Outbound to Office 365,08D1ECFA4B38037F,3,,,>,EHLO ex1.domain.local,
2014-12-23T20:08:01.434Z,Outbound to Office 365,08D1ECFA4B38037F,4,,,<, Hello [X.X.X.X],
2014-12-23T20:08:01.434Z,Outbound to Office 365,08D1ECFA4B38037F,5,,,<,250-SIZE 157286400,
2014-12-23T20:08:01.434Z,Outbound to Office 365,08D1ECFA4B38037F,6,,,<,250-PIPELINING,
2014-12-23T20:08:01.434Z,Outbound to Office 365,08D1ECFA4B38037F,7,,,<,250-DSN,
2014-12-23T20:08:01.434Z,Outbound to Office 365,08D1ECFA4B38037F,8,,,<,250-ENHANCEDSTATUSCODES,
2014-12-23T20:08:01.434Z,Outbound to Office 365,08D1ECFA4B38037F,9,,,<,250-STARTTLS,
2014-12-23T20:08:01.434Z,Outbound to Office 365,08D1ECFA4B38037F,10,,,<,250-8BITMIME,
2014-12-23T20:08:01.434Z,Outbound to Office 365,08D1ECFA4B38037F,11,,,<,250-BINARYMIME,
2014-12-23T20:08:01.434Z,Outbound to Office 365,08D1ECFA4B38037F,12,,,<,250 CHUNKING,
2014-12-23T20:08:01.434Z,Outbound to Office 365,08D1ECFA4B38037F,13,,,>,STARTTLS,
2014-12-23T20:08:01.512Z,Outbound to Office 365,08D1ECFA4B38037F,14,,,<,220 2.0.0 SMTP server ready,
2014-12-23T20:08:01.512Z,Outbound to Office 365,08D1ECFA4B38037F,15,,,*,,Sending certificate
2014-12-23T20:08:01.512Z,Outbound to Office 365,08D1ECFA4B38037F,16,,,*,", OU=Domain Control Validated",Certificate subject
2014-12-23T20:08:01.512Z,Outbound to Office 365,08D1ECFA4B38037F,17,,,*,"CN=Starfield Secure Certificate Authority - G2, OU=, O=""Starfield Technologies, Inc."", L=Scottsdale, S=Arizona, C=US",Certificate issuer name
2014-12-23T20:08:01.512Z,Outbound to Office 365,08D1ECFA4B38037F,18,,,*,XXXXXXXXXXXXXX,Certificate serial number
2014-12-23T20:08:01.512Z,Outbound to Office 365,08D1ECFA4B38037F,19,,,*,76CDA7673866A90AF77973AA140621AECE384E66,Certificate thumbprint
2014-12-23T20:08:01.512Z,Outbound to Office 365,08D1ECFA4B38037F,20,,,*,;;,Certificate alternate names
2014-12-23T20:08:01.512Z,Outbound to Office 365,08D1ECFA4B38037F,21,,,*,,TLS negotiation failed with error NoCredentials
2014-12-23T20:08:01.512Z,Outbound to Office 365,08D1ECFA4B38037F,22,,,-,,Local


Then, we reset the “inbound” connector in Office 365 back to “Force TLS” and set the Domain Restriction from “None” to “Restrict domains by certificate” using the assigned certificate to Exchange 2013 “<I>CN=Starfield Secure Certificate Authority – G2, OU=, O=”Starfield Technologies, Inc.”, L=Scottsdale, S=Arizona, C=US<S>, OU=Domain Control Validated“, however, the issue with mail flow was not resolved.

Lastly, we took a deeper look at the SMTP send logs and found a discrepancy with the certificate thumbprint associated with the connection error and the thumbprint of the certificate assigned to the Exchange 2013 server.

2014-12-23T20:08:01.512Z,Outbound to Office 365,08D1ECFA4B38037F,19,,,*,76CDA7673866A90AF77973AA140621AECE384E66,Certificate thumbprint


The thumbprint of the assigned certificate on the Exchange 2013 server is…



This discrepancy appears to have been causing the mail flow issue from on premise to Office 365. With this lead, we reviewed the certificates (from the Exchange 2013 server) via the MMC in Certificates (Local Computer) > Personal > Certificates and found an expired certificate with the invalid thumbprint (40C17C1A4F34D7468D69388B7E99862DF24EC0BC). The expired certificate was then removed and an IISRESET was performed from an elevated command prompt.

As a result, additional mail flow testing from on premise mailboxes to Office 365 mailboxes was successful and all prior test messages were successfully delivered as well.

2014-12-23T20:20:31.254Z,Outbound to Office 365,08D1ECFA4B380387,0,,,*,,attempting to connect
2014-12-23T20:20:31.363Z,Outbound to Office 365,08D1ECFA4B380387,1,,,+,,
2014-12-23T20:20:31.457Z,Outbound to Office 365,08D1ECFA4B380387,2,,,<,"220 Microsoft ESMTP MAIL Service ready at Tue, 23 Dec 2014 20:20:29 +0000",
2014-12-23T20:20:31.457Z,Outbound to Office 365,08D1ECFA4B380387,3,,,>,EHLO d5-ex1.d5.local,
2014-12-23T20:20:31.582Z,Outbound to Office 365,08D1ECFA4B380387,4,,,<, Hello [X.X.X.X],
2014-12-23T20:20:31.582Z,Outbound to Office 365,08D1ECFA4B380387,5,,,<,250-SIZE 157286400,
2014-12-23T20:20:31.582Z,Outbound to Office 365,08D1ECFA4B380387,6,,,<,250-PIPELINING,
2014-12-23T20:20:31.582Z,Outbound to Office 365,08D1ECFA4B380387,7,,,<,250-DSN,
2014-12-23T20:20:31.582Z,Outbound to Office 365,08D1ECFA4B380387,8,,,<,250-ENHANCEDSTATUSCODES,
2014-12-23T20:20:31.582Z,Outbound to Office 365,08D1ECFA4B380387,9,,,<,250-STARTTLS,
2014-12-23T20:20:31.582Z,Outbound to Office 365,08D1ECFA4B380387,10,,,<,250-8BITMIME,
2014-12-23T20:20:31.582Z,Outbound to Office 365,08D1ECFA4B380387,11,,,<,250-BINARYMIME,
2014-12-23T20:20:31.582Z,Outbound to Office 365,08D1ECFA4B380387,12,,,<,250 CHUNKING,
2014-12-23T20:20:31.582Z,Outbound to Office 365,08D1ECFA4B380387,13,,,>,STARTTLS,
2014-12-23T20:20:31.676Z,Outbound to Office 365,08D1ECFA4B380387,14,,,<,220 2.0.0 SMTP server ready,
2014-12-23T20:20:31.676Z,Outbound to Office 365,08D1ECFA4B380387,15,,,*,,Sending certificate
2014-12-23T20:20:31.676Z,Outbound to Office 365,08D1ECFA4B380387,16,,,*,", OU=Domain Control Validated",Certificate subject
2014-12-23T20:20:31.676Z,Outbound to Office 365,08D1ECFA4B380387,17,,,*,"CN=Starfield Secure Certificate Authority - G2, OU=, O=""Starfield Technologies, Inc."", L=Scottsdale, S=Arizona, C=US",Certificate issuer name
2014-12-23T20:20:31.676Z,Outbound to Office 365,08D1ECFA4B380387,18,,,*,27900F8FCB8B12,Certificate serial number
2014-12-23T20:20:31.676Z,Outbound to Office 365,08D1ECFA4B380387,19,,,*,40C17C1A4F34D7468D69388B7E99862DF24EC0BC,Certificate thumbprint
2014-12-23T20:20:31.676Z,Outbound to Office 365,08D1ECFA4B380387,20,,,*,;;;,Certificate alternate names
2014-12-23T20:20:32.082Z,Outbound to Office 365,08D1ECFA4B380387,21,,,*,,Remote certificate
2014-12-23T20:20:32.082Z,Outbound to Office 365,08D1ECFA4B380387,22,,,*,", OU=Forefront Online Protection for Exchange, O=Microsoft, L=Redmond, S=WA, C=US",Certificate subject
2014-12-23T20:20:32.082Z,Outbound to Office 365,08D1ECFA4B380387,23,,,*,"CN=MSIT Machine Auth CA 2, DC=redmond, DC=corp, DC=microsoft, DC=com",Certificate issuer name
2014-12-23T20:20:32.082Z,Outbound to Office 365,08D1ECFA4B380387,24,,,*,689549F000010000DFBE,Certificate serial number
2014-12-23T20:20:32.082Z,Outbound to Office 365,08D1ECFA4B380387,25,,,*,3DFAEC8A810E8BF2D81D646ED4E11E0FFDF6FA55,Certificate thumbprint
2014-12-23T20:20:32.082Z,Outbound to Office 365,08D1ECFA4B380387,26,,,*,;*;*;;,Certificate alternate names
2014-12-23T20:20:32.082Z,Outbound to Office 365,08D1ECFA4B380387,27,,,*,,"TLS protocol SP_PROT_TLS1_0_CLIENT negotiation succeeded using bulk encryption algorithm CALG_AES_128 with strength 128 bits, MAC hash algorithm CALG_SHA1 with strength 160 bits and key exchange algorithm CALG_RSA_KEYX with strength 2048 bits"
2014-12-23T20:20:32.082Z,Outbound to Office 365,08D1ECFA4B380387,28,,,*,,Received certificate
2014-12-23T20:20:32.082Z,Outbound to Office 365,08D1ECFA4B380387,29,,,*,3DFAEC8A810E8BF2D81D646ED4E11E0FFDF6FA55,Certificate thumbprint
2014-12-23T20:20:32.082Z,Outbound to Office 365,08D1ECFA4B380387,30,,,>,EHLO d5-ex1.d5.local,
2014-12-23T20:20:32.223Z,Outbound to Office 365,08D1ECFA4B380387,31,,,<, Hello [X.X.X.X],
2014-12-23T20:20:32.223Z,Outbound to Office 365,08D1ECFA4B380387,32,,,<,250-SIZE 157286400,
2014-12-23T20:20:32.223Z,Outbound to Office 365,08D1ECFA4B380387,33,,,<,250-PIPELINING,
2014-12-23T20:20:32.223Z,Outbound to Office 365,08D1ECFA4B380387,34,,,<,250-DSN,
2014-12-23T20:20:32.223Z,Outbound to Office 365,08D1ECFA4B380387,35,,,<,250-ENHANCEDSTATUSCODES,
2014-12-23T20:20:32.223Z,Outbound to Office 365,08D1ECFA4B380387,36,,,<,250-AUTH LOGIN,
2014-12-23T20:20:32.223Z,Outbound to Office 365,08D1ECFA4B380387,37,,,<,250-8BITMIME,
2014-12-23T20:20:32.223Z,Outbound to Office 365,08D1ECFA4B380387,38,,,<,250-BINARYMIME,
2014-12-23T20:20:32.223Z,Outbound to Office 365,08D1ECFA4B380387,39,,,<,250 CHUNKING,
2014-12-23T20:20:32.223Z,Outbound to Office 365,08D1ECFA4B380387,40,,,*,,sending message with RecordId 4939212390413 and InternetMessageId <>
2014-12-23T20:20:32.223Z,Outbound to Office 365,08D1ECFA4B380387,41,,,>,MAIL FROM:<> SIZE=13207,
2014-12-23T20:20:32.223Z,Outbound to Office 365,08D1ECFA4B380387,42,,,>,RCPT TO:<> ORCPT=rfc822;,
2014-12-23T20:20:32.363Z,Outbound to Office 365,08D1ECFA4B380387,43,,,<,250 2.1.0 Sender OK,
2014-12-23T20:20:32.504Z,Outbound to Office 365,08D1ECFA4B380387,44,,,<,250 2.1.5 Recipient OK,
2014-12-23T20:20:32.504Z,Outbound to Office 365,08D1ECFA4B380387,45,,,>,BDAT 10358 LAST,
2014-12-23T20:20:34.286Z,Outbound to Office 365,08D1ECFA4B380387,46,,,<,"250 2.6.0 <> [InternalId=20199231195942,] Queued mail for delivery",
2014-12-23T20:20:34.286Z,Outbound to Office 365,08D1ECFA4B380387,47,,,>,QUIT,
2014-12-23T20:20:34.379Z,Outbound to Office 365,08D1ECFA4B380387,48,,,<,221 2.0.0 Service closing transmission channel,
2014-12-23T20:20:34.379Z,Outbound to Office 365,08D1ECFA4B380387,49,,,-,,Local


Finally, in the O365 EAC, we set the security option for the “outbound” connector to “Recipient certificate matches domain” and assigned our certificate domain…

<I>CN=Starfield Secure Certificate Authority - G2, OU=, O="Starfield Technologies, Inc.", L=Scottsdale, S=Arizona, C=US<S>, OU=Domain Control Validated


What was eventually determined, is during the original run of the hybrid configuration wizard (HCW) from Exchange 2013 an older (expiring) certificate was used, then a new certificate was assigned to Exchange 2013 with the older one being removed from the Exchange 2013 EAC, and finally the HCW was run again to apply the new certificate. However, the certificate was not removed appropriately during the steps to replace the expiring certificate.


2 thoughts on “Exchange 2013 Hybrid Mail Flow Issues: TLS negotiation failed with error NoCredentials

  1. Thanks!

    I spend a few hours on a call with Microsoft support for this very issue. In my case, I had re-keyed the certificate due to an organizational address change, but the practical outcome was the same: Exchange was using a different certificate and the thumbprint that was being used for the connectors was invalid.

    I should also mention that in Exchange 2013, when using the HCW Standalone application(, the new wizard did change the cert once I deleted the old one from the exchange server and had only the new one installed on the server.

    Your post got me to the bottom of a painful issue!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your 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 )

Google+ photo

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

Connecting to %s