I was trying to get a Gitlab runner working on an old Ubuntu 14.4 box, but the runner was showing gnutls_handshake() failed: Handshake failed - ie. it couldn’t connect to the self-hosted Gitlab instance.

Calling ssh -T git@git.example.com showed a successful connection, but gnutls-cli git.example.com showed:

Resolving 'git.example.com'...
Connecting to '1.2.3.4:443'...
*** Fatal error: A TLS fatal alert has been received.
*** Received alert [40]: Handshake failed
*** Handshake has failed
GnuTLS error: A TLS fatal alert has been received.

This thread on gitlab.com has the answer. Edit your gitlab’s /etc/gitlab/gitlab.rb to have some additional ciphers:

nginx['ssl_ciphers'] = 'ECDHE-RSA-AES256-GCM-SHA384:ECDHE-RSA-AES128-GCM-SHA256:DHE-RSA-AES256-SHA:ECDHE-RSA-AES128-SHA:ECDHE-RSA-AES256-SHA:AES256-SHA:AES128-SHA:DES-CBC3-SHA'

then gitlab-ctl reconfigure and confirm that gnutls-cli git.example.com now connects successfully.