Ooops – some recent openssl update seems to have “broken” things. Well, technically they’re just dismissing weak keys (Logjam), but still – annoying side effect.

TL;DR fix:
openssl dhparam -out /etc/pki/tls/certs/dhparams.pem 1024

Then edit your by adding (if you have old versions – Fedora 10 or similar, comment out the two SSLOptions):
O CipherList=HIGH:!ADH
O DHParameters=/etc/pki/tls/certs/dhparams.pem
O ClientSSLOptions=+SSL_OP_NO_SSLv2 +SSL_OP_NO_SSLv3

run “make” or whatever to re-create your, then restart sendmail.

Quick little test-command:
openssl s_client -starttls smtp -crlf -connect

For more info, see these links: