[gnutls-dev] Original analysis of signature forgery problem
jas at extundo.com
Tue Sep 26 18:18:57 CEST 2006
Hi all, I just got permission to publish the original report about the
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...
Software: GNUTLS (up to 1.4.2)
Kind of vulnerability: Certificate Forgery
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.
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
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
During checking the validity of certificate signature, check if the
parameter field is NULL (05 00). Otherwise, reject the certificate.
- 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
More information about the Gnutls-dev