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 euro to Greenpeace and find out that he
donated 1.000.000 euros to Bad Inc.

For a hash algorithm to be called cryptographic the following three
requirements must hold
@enumerate
@item Preimage resistance. That means the algorithm must be one way and given
the output of the hash function @math{H(x)}, it is impossible to
calculate @math{x}.

@item 2nd preimage resistance. That means that given a pair @math{x,y} with @math{y=H(x)} it is impossible
to calculate an @math{x'} such that @math{y=H(x')}.

@item Collision resistance. That means that it is impossible to calculate random @math{x} and @math{x'} such
@math{H(x')=H(x)}.
@end enumerate

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
@iftex
@math{2^{(\rm{hash\ size}) / 2}} 
@end iftex
@ifnottex
@math{2^{((hash size) / 2)}} 
@end ifnottex
operations. Today colliding certificates using the MD5 hash algorithm
have been generated as shown in @xcite{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 @math{2^64}, but it has been showed to
have a collision strength well under @math{2^50}.  As of November
2005, it is believed that SHA-1's collision strength is around
@math{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 @math{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.

@subsection Supported Algorithms
The available digital signature algorithms in @acronym{GnuTLS} are
listed below:

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

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

@end table

The supported cryptographic hash algorithms are:

@table @code
@item 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
several known weaknesses of this algorithm and it should not be used.
Unfortunately some CA certificates signed with RSA-MD2 are still in
use, but this is acceptable because the RSA-MD2 signature is not
involved in certificate validation.

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

@item 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.

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

@end table


@subsection Trading Security for Interoperability

If you connect to a server and use GnuTLS' functions to verify the
certificate chain, and get a @ref{GNUTLS_CERT_INSECURE_ALGORITHM}
validation error (@pxref{Verifying X.509 certificate paths}), it means
that somewhere in the certificate chain there is a certificate signed
using @code{RSA-MD2} or @code{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 @code{RSA-MD2} or @code{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 @ref{gnutls_certificate_verify_peers2} to verify the
certificate chain, you can call
@ref{gnutls_certificate_set_verify_flags} with the
@code{GNUTLS_VERIFY_ALLOW_SIGN_RSA_MD2} or
@code{GNUTLS_VERIFY_ALLOW_SIGN_RSA_MD5} flag, as in:

@example
  gnutls_certificate_set_verify_flags (x509cred,
                                       GNUTLS_VERIFY_ALLOW_SIGN_RSA_MD5);
@end example

This will tell the verifier algorithm to enable @code{RSA-MD5} when
verifying the certificates.

If you are using @ref{gnutls_x509_crt_verify} or
@ref{gnutls_x509_crt_list_verify}, you can pass the
@code{GNUTLS_VERIFY_ALLOW_SIGN_RSA_MD5} parameter directly in the
@code{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 @ref{gnutls_certificate_get_peers} to extract
the raw server's certificate chain, then use
@ref{gnutls_x509_crt_import} to parse each of the certificates, and
then use @ref{gnutls_x509_crt_get_signature_algorithm} to find out the
signing algorithm used for each certificate.  If any of the
intermediary certificates are using @code{GNUTLS_SIGN_RSA_MD2} or
@code{GNUTLS_SIGN_RSA_MD5}, you could present a warning.
