sendmail rejecting some connections with handshake failure: SSL alert number 40

My sendmail server on CentOS 5 started to reject some connections with the following message logged:

error:14094410:SSL routines:SSL3_READ_BYTES:sslv3 alert handshake failure:s3_pkt.c:1092:SSL alert number 40

When I try to connect to it using openssl from CentOS 6 server I get the following error:

$ openssl s_client -starttls smtp -crlf -connect hostname.example.net:smtp
(...)
error:14082174:SSL routines:SSL3_CHECK_CERT_AND_ALGORITHM:dh key too small:s3_clnt.c:3331
(...)
Server Temp Key: DH, 512 bits
(...)

Mail on CentOS 6 server is temporarily rejected with Deferred: 403 4.7.0 TLS handshake failed.

What to do to be able to send mail from CentOS 6 / RHEL 6 to CentOS6 / RHEL5 server?

This is because after a recent update to openssl on CentOS 6, openssl-1.0.1e-30.el6.11.x86_64, programs using this library started to refuse connecting to servers vulnerable to Logjam TLS vulnerability.

You need to configure sendmail to use stronger temporary Diffie–Hellman key — at least 1024 bit. It is not the same key that you use in your TLS certificate, so if your certificate uses 2048 bit key then you can still be vulnerable.

Generate DH parameters file on your server:

openssl dhparam -out /etc/pki/tls/certs/dhparams.pem 1024

Configure sendmail to use this parameters file, and to use only strong ciphers. Add to /etc/mail/sendmail.mc:

LOCAL_CONFIG
O CipherList=HIGH:!ADH
O DHParameters=/etc/pki/tls/certs/dhparams.pem
O ServerSSLOptions=+SSL_OP_NO_SSLv2 +SSL_OP_NO_SSLv3 +SSL_OP_CIPHER_SERVER_PREFERENCE
O ClientSSLOptions=+SSL_OP_NO_SSLv2 +SSL_OP_NO_SSLv3

Then use make -C /etc/mail/ and service sendmail restart.