Exchange 2003 TLS can't receive emails from Office 365

We've had TLS running on an Exchange 2003 server for a couple of years.  They deal with the State of De and encryption is a must to remain in compliance.  It's been working without issue.  Starting sometime over the last few weeks, anyone hosted by Microsoft's Office 365 can no longer send them email.  There's no NDR or error message, the recipients just don't get the emails.  You can see the connections from the Microsoft servers stacking up in the virtual smtp server until they finally time out at 300 seconds.  I've turned off all anti spam and connection filtering with no difference.  They receive mail properly from seemingly all other sources.

I know it's a TLS issue because I created a temporary virtual smtp server but did NOT attach the certificate to it.  That way, with encryption not being an option, the mail from Microsoft flows fine.  But it stops once I bring up the actual Default SMTP server with the attached certificate.  TLS is not set to be required and they constantly receive email from other servers that are not encrypted.  But, I guess, the MS servers are seeing that certificate and insisting on encryption.  I see the STARTTLS commands in the log, but then they time out.

I've been working with Microsoft for a few days, but they haven't been able to help.  I'm far from an Exchange guru, but feel like I've had to explain what was happening to the Microsoft Engineers.  

I'm not positive that this is related because I can't seem to match up the times exactly, but I'm seeing this error repeated in the event log.

Source: Schannel
Event ID: 36874

An SSL connection request was received from a remote client application, but none of the cipher suites supported by the client application are supported by the server. The SSL connection request has failed.

Any help would be greatly appreciated.
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

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.

JohnBusiness Consultant (Owner)Commented:
Did they suggest any upgrades to Exchange?  This is the third question in 36 hours that Outlook 2013 cannot send to Exchange. Outlook (Office) and Windows 8.1 have had security updates which may have (appears to have) affected this.
FredCredAuthor Commented:
They have not as of yet.  I'm thinking along the same lines as you, but haven't found anything on my own.
Brian MurphyIT ArchitectCommented:
Exchange 2003 on which OS?  2008 R2 64 Bit?  If you are not running at least 2008 R2 then you should advise your Exchange Administrators that a world of hurt is coming.  When we start talking about encryption whether internet or email the industry is starting to enforce TLS 1.2 as the minimum protocol and no support for RC2 and RC4 cipher suites.

Is the certificate new?  You might want to check and see what cipher and protocol it uses.  

I doubt the root cause is TLS.  The issue is more likely Schannel.  I wrote an internal paper on best practices for certificates relative to encryption, cipher suites and protocols.

SSL Labs has what they call a client tool that assesses vulnerability of any given browser but it also provides a list of cipher suites available to it from Microsoft Schannel.

We have disabled SSL 2 and SSL 3 and removed all RC2 and RC4 ciphers.  

Microsoft has alerts out on Schannel vulnerabilities for Server 2003, 2008, 2008R2

SSL\TLS is x509 Certificates.

The RFC 2246 document states the following: “The cryptographic parameters of the session state are produced by the TLS Handshake Protocol, which operates on top of the TLS Record Layer. When a TLS client and server first start communicating, they agree on a protocol version, select cryptographic algorithms, optionally authenticate each other, and use public-key encryption techniques to generate shared secrets.

If you are using Exchange 2003 don't you have to install the certificate on the default SMTP Virtual Server?  For external mail.

If memory serves, the MTA accepts TLS by default for Internal.

Office 365 is external mail.  Unless you did a full integration with your internal Active Directory.  That requires a lot more than simply allowing uses to have external Office 365 accounts.

I've done two 365 migrations and the mail was moved to Office 365 Cloud and internal Exchange Server Site was decommissioned.  If you hosting mail in both locations that would not show up as internal / MTA but use a SMTP Virtual Server.
Big Business Goals? Which KPIs Will Help You

The most successful MSPs rely on metrics – known as key performance indicators (KPIs) – for making informed decisions that help their businesses thrive, rather than just survive. This eBook provides an overview of the most important KPIs used by top MSPs.

FredCredAuthor Commented:
I may have not been clear. This is a single Exchange 2003 server.  It is not a hybrid setup.  The office 365 clients that are trying to send mail are not part of this company, just other companies that happen to be hosted by Microsoft.  So they are absolutely coming in on the default virtual smtp server.  It does not support tls by default, but the certificate has been attached and it's been working well.  It's just the Microsoft servers that are not able to send email to it, and that just started this month.

Exchange is currently running on Server 2003 R2 SP2, which I'm sure is at the heart of the problem.  That's being upgraded to an Exchange 2010 setup, but we need to buy a couple more months.

The 2048 bit certificate was issued by godaddy 9/14.  Should I be looking for something in particular on the cert?
FredCredAuthor Commented:
Also, since we're only trying to buy a couple of months and the emails from the office 365 servers flow fine without encryption, is there a way to force their connection to not use encryption, while allowing it for other domains?
Simon Butler (Sembee)ConsultantCommented:
Exchange 2003 doesn't do opportunist TLS. It is either ON or OFF.
Therefore I suspect that the problem is the use of TLS with Exchange 2003 and Office365 trying to do something that Exchange 2003 cannot.

If you only need a couple of months, I would introduce an Exchange 2007 Hub Transport server. Download SP3 and install that on to a new machine. It will run in an evaluation for 120 days. Get that to do all of your SMTP communication as it can do both opportunist and mutual TLS.

Not sure where the comment about Exchange 2003 and Windows 2008 R2 comes in above - Exchange 2003 has never been supported on Windows 2008/2008 R2.


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
Brian MurphyIT ArchitectCommented:
Not sure yet about the certificate, yet.  I needed more background.   In full discloure I don’t work with Exchange on a daily basis.  I can only relate to my own experience with previous migrations.  Server 2008 R2 is very relevant as it pertains to external SMTP relay.   I have seen that error on 2008 R2 and it was due to disabling SSL 3.  I just cannot imagine that Office 365 originating traffic regardless of domain would allow this unless it were not disabled on your server and older server and even new ones are vulnerable because they negotiate from low to high.  Like RC4 cipher, it will try to negotiate the lowest available cipher that exists on the client and server.  Just Google ‘FREAK’.

With that said, you will see commentary with that vulnerability where it was a client side issue.  On 2008 R2, running Exchange 2010 configured as CAS/HT servers.  And there is a way to increase logging for such type events on 2008R2, not sure about 2003 Server. 

Sounds like it might be related to the encryption for TLS relative to 2003 Exchange.  And that brings me to my question about 2008 R2 that left some confused.

Regarding 2008 R2.  Very relevant for SMTP Relay.  You might be better off standing one up for the logging alone.  I've seen scenarios where they had Exchange 2003 but also SMTP Relay on 2008 R2.  If memory serves, the SMTP VIrtual server on 2003 or now 2010.  If you were migrating to Office 365 then a 2008 R2 might make sense as being a SMTP Relay aka IIS SMTP Relay.  I can only speak to what I've done.  Whether 2008 R2 or a SMTP Cloud provider like Mimecast or local hosted Ironport SMTP appliance.

I try not to make assumptions and see big picture as everthing is suspect and then narrow the gap by elimination.  I must also account for things inherited.  There are many bad designs out there and the majority seem to be handed off to someone else.  Your left with a design that works but wrapped by a lot of workaround processes and one change breaks something else.

If your Exchange servers are on-premises you configure an internal relay in Exchange which will not work once the mailbox is migrated.  After all the mailboxes were migrated it would require another type of relay such as aforementioned.  Your SMTP Relay on Exchange would not work for anything hosted external.  

On one migration to Office 365 I encountered Exchange 5.5 for the first time in what must have been 12 years.  I set this up for external mail due to the requirement of data retention, distributed data center, and custom interface for attorneys to find mail quickly.  For internal mail I used Jounaling so that all internal mail would reside in Mimecast as well.

I don’t recall all the specifics other than they had a lot of domains and one Exchange organization.  When you migrate a mailbox the goal was retain free-busy, GAL, and so forth.  This required Federated Services and a couple of Exchange 2010 CAS servers, using Powershell to set all accounts in all domains to having the same primary suffix where in some cases people had 40-50 SMTP addresses for different domains.  In this scenario the primary suffix relative to AD must match the primary SMTP address for every user or SSO fails.

And once you migrate the mailboxes, your SMTP record would resolve to something like  In other words, you would replace ‘office365’ with the domain chosen as the primary suffix and primary SMTP address.  In this case, SMTP was MimeCast cloud for all external mail or non-hosted domains.  

Back to your question on the certificate, I’m not sure yet.  I know support was dropped for 2003 Server just last month.  One of the initiatives I had worked on was helping my current organization migrate to 2008 R2.  When you speak to compliance, the area I work requires TS DoD due to Military contracts and Medicare.  

You stated 2048 Bit so all I’m aware of is anything using RSA and 1024 Bit or less is blocked and that block is native from Windows 8.1, 2012 Server, and so forth.

So my understanding now is that you have a single Exchange Server running on 2003 OS and when you say Microsoft is a reference to Office 365 which could be any customer hosted in their cloud where Office 365 might be an extension of the customer by way of FRS and SSO or might be a hosted solution such as with smaller companies where they have no infrastructure on-premises.  So, if the remote domain is configured to use TLS which Office 365 does offer but not required.  This is a per customer hosted design decision.  

That external mail is not hitting your Exchange Server direct?  You must have a NAT or Virtual IP that forwards traffic, yes?  That would mean your NAT or proxy IP to internal is correct and you have a SPF Record?  

You can send mail out so it is not that you are being blocked by an Exchange Online Protection (EOP) blocklist.

If you setup a 2008 R2 SMTP Relay instead, enable logging in IIS and in the properties of the SMTP Virtual server and choose “NCSA Common Log Format”.   If you do have a NAT then all that is required is changing the translation address.  If you are not comfortable with changing the primary NAT then have a new one created and make sure the SPF and A record is correct.

IIS 7.5 does not automatically groom or delete logs like Exchange does, so turn logging off when you're done troubleshooting.  This should get you quicker answers.
Brian MurphyIT ArchitectCommented:
Look familiar?

Issues with mail flow to and from Office 365
Invalid SSL Certificate

A recent experience I had occurred after creating an Exchange 2013 hybrid environment and then created a new certificate request.  After creating the new SSL cert request and applying the new certificate, mail flow both to and from Office 365 resources stopped.  The following NDRs were being received…
Brian MurphyIT ArchitectCommented:
Basically what it is saying is: remove the old certificate and any associated Intermediate and Root chains.

You can do this by opening new MMC.exe, Certificate snap-in, choose Local Machine.  At top you will see Personal > Double click > Certificates.  Delete the OLD certificate.

Then go to the Trusted Enterprise and delete the OLD certificate chains.

Delete anything having to do with the old certificate and chain.

From simply click on the link that says update intermediate and root CA certificate chain.

It might be a file or a hash that you copy.  Copy the x509 and paste to notepad.  Save as .CER extension.

Use the MMC console to import the new certificate chain.

The problem appears to be replacing the new certificate and not removing the old one.  If you have any firewall rules that might block the certificate chain process I recommend downloading the certificate chain to that server.  If you are blocking CRL checks at FIrewall I recommend downloading the latest CRL as well.

More than likely removing the OLD certificate and OLD CA and Intermediate root chain will resolve your issue.
We are having the exact same issue with our SBS 2003 server not being able to receive emails from Office365 and I noticed the same thing in our logs with the STARTTLS command but don't know how to resolve. We can receive emails from everyone else just fine.
FredCredAuthor Commented:
Really sorry for the lack of replies.  This was one of those emergency jobs that always happen right before your vacation.  

Simon nailed it, simply and concisely.  The TLS implementation in 2003 is not compatible with the Office 365 servers.  There is no work around.  Turn off TLS, or don't get mail from Office 365 (and presumably a growing number of servers).

I threw in an exchange 2010 server and changed the MX record so all incoming mail flows through it.  Verified TLS was functioning.  Problem Solved.

Now that I'm back from vacation, it's time to finish the transfer.

Thanks for all the info!!
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

From novice to tech pro — start learning today.