5.3 Digital signatures

In this section we will provide some information about digital signatures, how they work, and give the rationale for disabling some of the algorithms used.

Digital signatures work by using somebody's secret key to sign some arbitrary data. Then anybody else could use the public key of that person to verify the signature. Since the data may be arbitrary it is not suitable input to a cryptographic digital signature algorithm. For this reason and also for performance cryptographic hash algorithms are used to preprocess the input to the signature algorithm. This works as long as it is difficult enough to generate two different messages with the same hash algorithm output. In that case the same signature could be used as a proof for both messages. Nobody wants to sign an innocent message of donating 1 € to Greenpeace and find out that he donated 1.000.000 € to Bad Inc.

For a hash algorithm to be called cryptographic the following three requirements must hold

1. Preimage resistance. That means the algorithm must be one way and given the output of the hash function H(x), it is impossible to calculate x.
2. 2nd preimage resistance. That means that given a pair x,y with y=H(x) it is impossible to calculate an x' such that y=H(x').
3. Collision resistance. That means that it is impossible to calculate random x and x' such H(x')=H(x).

The last two requirements in the list are the most important in digital signatures. These protect against somebody who would like to generate two messages with the same hash output. When an algorithm is considered broken usually it means that the Collision resistance of the algorithm is less than brute force. Using the birthday paradox the brute force attack takes 2^((hash size) / 2) operations. Today colliding certificates using the MD5 hash algorithm have been generated as shown in [WEGER] (See WEGER.) .

There has been cryptographic results for the SHA-1 hash algorithms as well, although they are not yet critical. Before 2004, MD5 had a presumed collision strength of 2^64, but it has been showed to have a collision strength well under 2^50. As of November 2005, it is believed that SHA-1's collision strength is around 2^63. We consider this sufficiently hard so that we still support SHA-1. We anticipate that SHA-256/386/512 will be used in publicly-distributed certificates in the future. When 2^63 can be considered too weak compared to the computer power available sometime in the future, SHA-1 will be disabled as well. The collision attacks on SHA-1 may also get better, given the new interest in tools for creating them.

5.3.1 Supported algorithms

The available digital signature algorithms in GnuTLS are listed below:

RSA

RSA is public key cryptosystem designed by Ronald Rivest, Adi Shamir and Leonard Adleman. It can be used with any hash functions.

DSA

DSA is the USA's Digital Signature Standard. It uses only the SHA-1 hash algorithm.

The supported cryptographic hash algorithms are:

MD2

MD2 is a cryptographic hash algorithm designed by Ron Rivest. It is optimized for 8-bit processors. Outputs 128 bits of data. There are no known weaknesses of this algorithm but since this algorithm is rarely used and not really studied it should not be used today.

MD5

MD5 is a cryptographic hash algorithm designed by Ron Rivest. Outputs 128 bits of data. It is considered to be broken.

SHA-1

SHA is a cryptographic hash algorithm designed by NSA. Outputs 160 bits of data. It is also considered to be broken, though no practical attacks have been found.

RMD160

RIPEMD is a cryptographic hash algorithm developed in the framework of the EU project RIPE. Outputs 160 bits of data.

5.3.2 Trading security for interoperability

If you connect to a server and use GnuTLS' functions to verify the certificate chain, and get a GNUTLS_CERT_INSECURE_ALGORITHM validation error (see Verifying X.509 certificate paths), it means that somewhere in the certificate chain there is a certificate signed using RSA-MD2 or RSA-MD5. These two digital signature algorithms are considered broken, so GnuTLS fail when attempting to verify the certificate. In some situations, it may be useful to be able to verify the certificate chain anyway, assuming an attacker did not utilize the fact that these signatures algorithms are broken. This section will give help on how to achieve that.

First, it is important to know that you do not have to enable any of the flags discussed here to be able to use trusted root CA certificates signed using RSA-MD2 or RSA-MD5. The only attack today is that it is possible to generate certificates with colliding signatures (collision resistance); you cannot generate a certificate that has the same signature as an already existing signature (2nd preimage resistance).

If you are using gnutls_certificate_verify_peers2 to verify the certificate chain, you can call gnutls_certificate_set_verify_flags with the GNUTLS_VERIFY_ALLOW_SIGN_RSA_MD2 or GNUTLS_VERIFY_ALLOW_SIGN_RSA_MD5 flag, as in:

       gnutls_certificate_set_verify_flags (x509cred,
                                            GNUTLS_VERIFY_ALLOW_SIGN_RSA_MD5);

This will tell the verifier algorithm to enable RSA-MD5 when verifying the certificates.

If you are using gnutls_x509_crt_verify or gnutls_x509_crt_list_verify, you can pass the GNUTLS_VERIFY_ALLOW_SIGN_RSA_MD5 parameter directly in the flags parameter.

If you are using these flags, it may also be a good idea to warn the user when verification failure occur for this reason. The simplest is to not use the flags by default, and only fall back to using them after warning the user. If you wish to inspect the certificate chain yourself, you can use gnutls_certificate_get_peers to extract the raw server's certificate chain, then use gnutls_x509_crt_import to parse each of the certificates, and then use gnutls_x509_crt_get_signature_algorithm to find out the signing algorithm used for each certificate. If any of the intermediary certificates are using GNUTLS_SIGN_RSA_MD2 or GNUTLS_SIGN_RSA_MD5, you could present a warning.