The Problem

About a week ago (early April 2020), a weird thing happened. GMail started bouncing back some emails sent from our altamontco.com domain with a strange message: TLS Negotiation failed, the certificate doesn't match the host." Upon looking at the GMail forums, it appears that many others had the same issue and were equally puzzled - most confusing was the infrequency of failure; about half my messages would go through fine. GMail added some rather generic help messages to their FAQ, but it took me several days (and many wrong solutions chased) to find the actual solution.

What is going on here?

The real issue here is that Google quietly announced they were going to have strict TLS enforcement starting in April 2020. As someone who wears many hats, I was still congratulating myself on getting full DKIM verification up and running a few years ago - now we have some new protocol to enforce?!

TLS

What exactly is TLS? Transport Layer Security is supposed to be the next step in keeping our traffic safe and our identities properly verified. However, nasty people (I blame bored mathematicians) keep coming up with clever ways to steal our data or pretend to be someone they're not. If you want a full explanation of TLS and why TLS 1.3 will save us all, I recommend a different article - I was just trying to send company email. The big takeaway I learned is that Google's implementation of the TLS chain is very strict and is very concerned with authority. I personally think it's aimed at large-scale actors (i.e. nation-states) because the resources required to make use of any of these weaknesses in the chains would be immense. I just want to send my emails....

Our Setup

Altamont (our company) has a fairly simple external network setup. We are running on AWS EC2 instances, with Cloudflare providing the frontend proxy and hosting our own email service, with certificates provided by LetsEncrypt (us and the rest of the internet).

The Red Herrings

The wrong paths I went down:

• Difference in certificate providers. We use Cloudflare's shared certificate for the web frontend, but get our own for the mail daemons. This was almost the problem - it actually ended up being tangentially related. I don't think the differences in certificates ended up mattering in the end, but it certainly led me astray for a while.
  
  
• SMTP Hostnames Some of the comments on the GMail forum suggested that I use smtp.altamontco.com - even that Google required it. This is false. Google doesn't care what the hostname is, as long as it matches the certificate. I changed that hostname all different ways.
  
  
• Outdated Server Software I upgraded, downgraded, sidegraded all my mail services and clients. No dice.
  
  
• Browsers Some people mentioned clearing cookies, cache. I didn't really think that would help, but it's only dumb if it doesn't work. It didn't work.
  
  
• Blaming GMail One of the biggest red herrings was assuming GMail was at fault. While we can argue whether they should have done this from a customer service standpoint, from a technical view, Google basically just did what they said they were going to do - strictly enforce the TLS protocal and authority chain.
  
  

Solution

So what ended up working? Some kind soul in the thread of Google linked a website that helps troubleshoot the entire TLS chain.

This is that wonderful page:
https://www.checktls.com/TestReceiver

Please note: you need to have ZERO errors showing. If you have even one, GMail will reject your messages (and probably your login with Code 0 as well).

In our case, it ended up being several things:

• MX record In Cloudflare, our MX record was set to just altamontco.com, since it had never mattered in the past. Gmail was taking that record and resolving it against the Cloudflare DNS servers. Since nothing was set, the hostname was resolving to whatever edge node Cloudflare happened to respond with at the time. This got me going in the right direction - I actually regenerated the LetsEncrypt certificate for that hostname before realizing how silly that was.
  
  
• Using the fullchain.pem Because of the strict enforcement of the TLS protocol chain, I had inadvertently just used the simpler pem file from LetsEncrypt in postfix. Previously, it had never mattered - with the strict enforcement, it mattered.
  
  

Conclusion

This was a nasty problem to troubleshoot, since it happened intermittently. I could get probably 1 in 4 emails to go through on the first try. What that says to me is that there are quite a few GMail servers that haven't been upgraded to the fully strict model. What I wish Google would have done is provide some insight into the TLS chains or what errors were being encountered rather than their generic error message (and generic help messages). CheckTLS.com was a lifesaver and helped get me on the right path.

Hope this article can help someone else struggling with this change!