The software I use outputs the following error: "The Diffie-Hellman prime sent by the server is not acceptable (not long enough)" and the connection is terminated.

Answer: The server you have tried to connect negotiates Diffie-Hellman (DH) ciphersuites but offers a small and insecure DH group. This means that any connection data could be decrypted in weeks or even hours by a determined adversary. For that reason GnuTLS will refuse to communicate such servers. To work around the issue disable Diffie-Hellman ciphersuites on the client (by using "NORMAL:-DHE-RSA" as a priority string); this will force connecting using the plain RSA ciphersuites, at the cost of losing perfect forward secrecy.

Note that currently in the NORMAL priority string, the minimum acceptable size of DH group is set to be at 1008 bits. This is a very low size for today's threats but unfortunately there are many popular Internet servers providing such a weak security level. To increase the security level use the SECURE128 or better priority strings, at the risk of a failed connection with an insecure server. To avoid this issue, newer versions of GnuTLS prioritize the elliptic curve DH ciphersuites that have no such issues (since the curve is negotiated as part of the handshake).

"The software I use outputs the following error: "Key usage violation in certificate has been detected." and the connection is terminated.

Answer: The server you have tried to connect has its certificate marked for encryption-only but the server uses it with a ciphersuite that requires signing (or vice-versa). This is either due to an attack, or due to a serious server misconfiguration. Contact the server administrator.

"The server software I use outputs the following error: "Insufficient credentials for that request." after a client connects.

Answer: If the server uses an X.509 certificate with an RSA key, then most probably the server certificate doesn't allow any of the ciphersuites requested by the client (this is related to key-usage-violation). There are three possibilities:

• The server has a priority string that incorrectly restricts the available ciphersuites to the set not allowed by the certificate. Solution: If the server has a certificate with the Key Usage extension and digitalSignature set, make sure that DHE-RSA and ECDHE-RSA key exchange methods are enabled. If the keyEncipherment flag is set, then make sure that the RSA key exchange is enabled.
• The client requires only encryption ciphersuites (i.e., RSA) but the server certificate only allows ciphersuites with signing (e.g., DHE-RSA). Solution: If the server has the Key Usage extension with digitalSignature set, replace or (better) add another server certificate with keyEncipherment set.
• The client requires only signing ciphersuites (e.g., DHE-RSA) but the server certificate only allows ciphersuites with encryption (i.e., RSA). That is the server has the Key Usage extension with keyEncipherment set. Solution: If the server has the Key Usage extension with keyEncipherment set, replace or (better) add another server certificate with digitalSignature set.

Note that while having a single certificate with the Key Usage extension unset, or with both digitalSignature and keyEncipherment flags would solve the issue; it is considered bad practice to use a single key/certificate for both RSA encryption and signatures.

I heard about the backdoor in https://en.wikipedia.org/wiki/Dual_EC_DRBG, does it affect GnuTLS?

Answer: GnuTLS never supported the Dual EC random generator, hence this issue does not affect GnuTLS.