[gnutls-dev] Original analysis of signature forgery problem

[Simon Josefsson]

Hi all, I just got permission to publish the original report about the
GNUTLS-SA-2006-4 problem.
        
/Simon

Ps. For some reason my first attempt (yesterday) to post this to the
list didn't end up in the archives, let's see if this one does...

================================================================
                      Vulnerability Report                      
================================================================

Software: GNUTLS   (up to 1.4.2)

Kind of vulnerability: Certificate Forgery

Summary:

During examination for sources for CVE-2006-4339, we have found that
gnutls is vunlerable for another kind of certificate forgery attack,
when "e = 3" RSA key is used to sign certificates.

Cause:

ASN.1 syntax for decrypted signatures allows "parameter" field to
contain any kind of data.  Valid contents for this field are depending
on the hash algorithm used, and for the MD5 and SHA-1 hash these
should be NULL.  However, gnutls does not check this field and allows
arbitrary data to be stored here.

This loose implementation allows the following attack:

  The constants show below assume that a CA uses 1024 bit RSA key with
  exponent 3, and uses MD5 algorithm to make a signature.

  (1) Let c = 7908632510826885383110735189539096624229777909395926928727
* 2^144,
      which is the cubic root of an expected value, ceiled up to a
multiple of 2^144.

  (2) For given signature digest value h, find a 144-bit integer h'
      such that (h')^3 mod 2^144 == 0x0410 * 2^128 + h. This is
      possible if h is an odd number.

  (3) Calculate x = c + h'.

When x is decrypted using RSA public exponent e = 3 (i.e. calculating
x^3), the result will be following data.

00 01 FF FF 00 30 79 30 65 06 08 2a 86 48 86 f7 0d 02 05 04 59
[ 89 bytes of garbage ] 04 10 [ 16 bytes of h ].

This is a valid PKCS-1-padded ASN.1 data, except existence of
meaningless parameter field.  As 89 bytes of garbage area is
sufficient to hold value (h')^3, the whole ASN.1 structure, produced
from c, is kept unbroken.

The same attacks are possible for SHA-1 algorithm and for longer RSA
keys, using a different value for c (and other constants).
We verified that GNUTLS 1.4.2 suffers from the same attack, using
certificates using SHA-1 hash algorithm.


Mitigating Factors and/or workarounds:

Avoiding to trust CAs using RSA key with a small exponent, such as
e=3, eliminates this attack.  for a large exponent, this attack is not
possible.


Possible Fix:

During checking the validity of certificate signature, check if the
parameter field is NULL (05 00). Otherwise, reject the certificate.


Notes:

- We suppose that this attack itself might be already known to public,
  as at least one implementation of the TLS protocol is careful about
  the possibility of attacks using the parameter field.  We have
  developped the detail of the real attack and verified.

- We are reporting this issue to IPA and JPCERT/CC in Japan.  This
  means that CERT/CC or other incident response agency may contact
  you later about handling of vulnerabilities.

The address of contact:
  Yutaka Oiwa, Kazukuni Kobara, Hajime Watanabe
    Research Center for Information Security,
    National Institute of
    Advanced Industrial Science and Technology (AIST), Japan.
    Contact E-mail: y.oiwa at aist.go.jp

================================================================