Exchange 2007/2013 Coexistence Mail Flow Issue

tl;dr - Need to resolve the "TLS negotiation failed with error AlgorithmMismatch" error for successful e-mail flow from Exchange 2007 to Exchange 2013.

Environment
Site 1: 2 Exchange 2013 CA servers, 2 Exchange 2013 MB servers, 2 Exchange 2007 CA servers, 2 Exchange 2007 MB servers
Site 2: 2 Exchange 2013 CA servers, 2 Exchange 2013 MB servers, 1 Exchange 2007 CA server, 1 Exchange 2007 MB server

All Exchange 2007 servers are running on Windows Server 2003 R2 x64.  Exchange 2007 SP3 RU16.
All Exchange 2013 servers are running on Windows Server 2012 R2.  Exchange 2013 CU8.

E-mail flow was working just fine, until the above error started.  This only happens between the 2007 CA servers and the 2013 MB servers in site 1, and only sending from 2007 to 2013.  There are no issues sending from 2013 to 2007, and between sites.  The messages were stuck in Hub Version 15 queue in both 2007 CA servers.  The error message on the Queue Viewer was:
"421 4.4.2 Connection dropped."  Attempted failover to alternate host, but that did not succeed....

Took a whole day to track down the issue, and finally found the error message on both 2013 MB servers' Receive log.

What I tried so far:
Creating a new self-signed certificate on the 2013 MB servers
Importing and assigning the CA certificate on the 2013 MB servers
Creating a new scoped receive connector on the 2013 MB servers and added the 2007 CA servers
Disabling the TLS on the 2013 MB servers' receive connectors

Here's the relevant portion of the receive protocol log:
250-STARTTLS,
250-X-ANONYMOUSTLS,
250-X-EXPS GSSAPI NTLM,
250-8BITMIME,
250-BINARYMIME,
250-CHUNKING,
250-XEXCH50,
250-XRDST,
250 XSHADOWREQUEST,
X-ANONYMOUSTLS,
220 2.0.0 SMTP server ready,
,Sending certificate
,CN=EXCH13MB01,Certificate subject
,CN=EXCH13MB01,Certificate issuer name
,XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX,Certificate serial number
,XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX,Certificate thumbprint
,EXCH13MB01;EXCH13MB01.xxxx.yyyy.com,Certificate alternate names
,TLS negotiation failed with error AlgorithmMismatch
,Local

Open in new window


Thanks.
gumpwareAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Simon Butler (Sembee)ConsultantCommented:
On each server run the following command:

new-exchangecertificate

no further switches or other options.
You will get a message about replacing the default SMTP certificate. Say yes to that message.
Then restart the transport service on each server.
Test again.

That usually resolves it.
If that doesn't then you need to start looking at interference. Firewall or something between the two sites getting in the way with the mail flow.

Have you changed the receive connector configuration at all from the default? A lot of issues I see with mail flow are caused by people making changes there. The default connectors should be left alone - if significant changes are required then new connectors should be used.

Simon.
0
gumpwareAuthor Commented:
Simon,

No joy.  New certificates were generated on each server, but the problem persists.  There were no significant changes made to the receive connectors.  I even created new connectors just for 2007 CA servers earlier, but no luck there.

Thanks.

David
0
gumpwareAuthor Commented:
Answering my own question:

TLS 1.0 was somehow disabled on the two 2013 mailbox servers in site 1.  Windows Server 2003 does not support TLS 1.1 or 1.2, so Exchange 2013 server was unable to complete the TLS handshake.  Once TLS 1.0 was enabled and the server restarted, the mail flow was restored.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
gumpwareAuthor Commented:
Issue was resolved.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Exchange

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.