[gnutls-devel] Prevent MD5 Downgrade in TLS signatures

[Karthikeyan Bhargavan]

Prevent MD5 Downgrade in TLS 1.2 Signatures
-------------------------------------------

GnuTLS does not by default support MD5 signatures. Indeed the RSA-MD5
signature-hash algorithm needs to be explicitly enabled using the
priority option VERIFY_ALLOW_SIGN_RSA_MD5. In the NORMAL and SECURE
profiles, GnuTLS clients do not offer RSA-MD5 in the signature
algorithms extension. However, we find that all GnuTLS clients still
accept RSA-MD5 in the ServerKeyExchange and GnuTLS servers still
accept RSA-MD5 in the ClientCertificateVerify.

To see the bug, connect with GnuTLS to an openssl 1.0.1m server with a
modified ssl/s3_srvr.c (attached) which always signs the
ServerKeyExchange with RSA-MD5.  When gnutls-cli connects to a server,
its signature algorithms extension only advertises signature/hash
algorithms that use the SHA family. Notably, it should not allow any
MD5 signature. However, when our server sends it an RSA-MD5 signature,
NSS does not check that this algorithm is included in the allowed
algorithms and quietly accepts it, hence downgrading the expected
security of the connection. 

The root cause for this bug is that, unlike previous versions, TLS 1.2
allows the signer to choose any combination of signature and hash
algorithm (even ECDSA-MD5 if it so wishes) and it is up to the
verifier to check that the algorithm is acceptable. Notably, the
current TLS 1.3 draft also allows MD5 signatures. This means that
unless a TLS library is careful, it may unexpectedly weaken the
security of signatures when upgrading to TLS 1.2.  This potential bug
has been noted before on the TLS mailing list:
https://www.ietf.org/mail-archive/web/tls/current/msg15270.html

We report that GnuTLS currently allows any signature/hash algorithm
combination defined in the sign_algorithms structure in
algorithms/sign.c, including RSA-MD5 and even RSA-RMD160, even though
these algorithms are never sent in the signature algorithms extension
in the client hello.  Similarly, in the ClientCertificateVerify
message, GnuTLS allows any combination defined in this
structure. However, GnuTLS clients and server will themselves never
generate such signatures, although other TLS libraries may do so.

We do not believe that the bug currently exposes any critical
exploits.  The impact of the bug depends on whether an adversary can
trigger meaningful collisions in TLS client and server
signatures. Folklore about TLS has previously suggested that only
second preimage attacks "break" TLS signatures, but collisions do
not. We challenge this assumption and attach a draft research report
that shows that collision resistance is *essential* for the security
of client and server signatures in TLS. We show how chosen-prefix
collisions in the hash function can be used to forge client signatures
in TLS 1.2 and server signatures in TLS 1.3.  We believe this result
is of independent interest for TLS specialists. In particular,
collisions in any of the handshake hashes (including those used in the
Finished message) in TLS can be translated to man-in-the-middle
attacks. Having said that, our proof-of-concept attacks in the
attached report take several hours on academic hardware and are not
widely exploitable.

We would be happy to provide further tests (such as a test server) and
discuss countermeasures. The straightforward fix is to check that the
signature/hash algorithm in the ServerKeyExchange and
ClientCertificateVerify messages is one of the allowed algorithms,
and that it was sent in the ClientHello.