Cannot establish a connection to a webserver due to dh key being too small.

Issue

Cannot establish a connection to a webserver. Using curl will give this output:

*   Trying <Ip.addr>... connected
* Connected to hostname.com (ip.addr) port 443 (#0)
* Initializing NSS with certpath: sql:/etc/pki/nssdb
*   CAfile: /path/to/cert.crt
  CApath: none
* NSS error -12173
* Closing connection #0
* SSL connect error
curl: (35) SSL connect error

And when trying to open a connection with openssl s_client --debug, we get:

[...]
139903204869960:error:14082174:SSL routines:SSL3_CHECK_CERT_AND_ALGORITHM:dh key too small:s3_clnt.c:3345:
[...]