[gnutls-dev] Bleichenbacher RSA signature forgery attack and GnuTLS

[Simon Josefsson]

You may have heard about a neat attack by Daniel Bleichenbacher,
described in:

http://www.imc.org/ietf-openpgp/mail-archive/msg14307.html

I went over the GnuTLS code to review if it is vulnerable.

Signature verification starts in
lib/x509/verify.c:_pkcs1_rsa_verify_sig, which calls
lib/gnutls_pk.c:_gnutls_pkcs1_rsa_decrypt.  It contains code like
this:

  _gnutls_mpi_print (&edata[1], &esize, res);
...
  ret = GNUTLS_E_DECRYPTION_FAILED;
  switch (btype)
    {
    case 2:
      for (i = 2; i < esize; i++)
	{
	  if (edata[i] == 0)
	    {
	      ret = 0;
	      break;
	    }
	}
      break;
    case 1:
      for (i = 2; i < esize; i++)
	{
	  if (edata[i] == 0 && i > 2)
	    {
	      ret = 0;
	      break;
	    }
	  if (edata[i] != 0xff)
	    {
	      _gnutls_handshake_log ("PKCS #1 padding error");
	      ret = GNUTLS_E_PKCS1_WRONG_PAD;
	      break;
	    }
	}
      break;
    default:
      gnutls_assert ();
      gnutls_afree (edata);
      return GNUTLS_E_INTERNAL_ERROR;
    }
  i++;

  if (ret < 0)
    {
      gnutls_assert ();
      gnutls_afree (edata);
      return GNUTLS_E_DECRYPTION_FAILED;
    }

  if (_gnutls_sset_datum (plaintext, &edata[i], esize - i) < 0)
    {
      gnutls_assert ();
      gnutls_afree (edata);
      return GNUTLS_E_MEMORY_ERROR;
    }

Thus it will save rest of the blob after the FFFF..FFFF00 sequence in
"plaintext".

Now back in _pkcs1_rsa_verify_sig, it calls decode_ber_digest_info on
"plaintext", which in turns call libtasn1 (plaintext==info):

  result = asn1_der_decoding (&dinfo, info->data, info->size, NULL);
  if (result != ASN1_SUCCESS)
    {
      gnutls_assert ();
      asn1_delete_structure (&dinfo);
      return _gnutls_asn2err (result);
    }

The libtasn1 library checks that the decoded data is of the indicated
length, so if "info" contains the correct ASN.1 blob plus some
garbage, the entire decoding will fail.  See the end of
asn1_der_decoding for the check that catches this:

  if (counter != len)
    {
      asn1_delete_structure (element);
      return ASN1_DER_ERROR;
    }

Here, len is the "plaintext" length, and "counter" is the size of the
ASN.1 structure that it computed by parsing the data.

The conclusion is that GnuTLS isn't vulnerable to _exactly_ this
attack.

/Simon