Exponent 3 damage spreads...

Tue Sep 12 10:43:24 EDT 2006

Jostein Tveit <josteitv at pvv.ntnu.no> writes:

> Anyone got a test key with a real and a forged signature to test
> other implementations than OpenSSL?

There are actually two problems to consider...

First, there is the situation by Bleichenbacher at Crypto 06 and
explained in:

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

That uses the fact that implementation doesn't check for data beyond
the end of the ASN.1 structure.  OpenSSL was vulnerable to this,
GnuTLS was not, see my analysis for GnuTLS on this at:

http://lists.gnupg.org/pipermail/gnutls-dev/2006-September/001202.html

Eric already posted test vectors that trigger this problem.

The second problem is that the "parameters" field can ALSO be used to
store data that may be used to manipulate the signature value into
being a cube.  To my knowledge, this was discovered by Yutaka Oiwa,
Kazukuni Kobara, Hajime Watanabe.  I didn't attend Crypto 06, but as
far as I understand from Hal's post, this aspect was not discussed.
Their analysis isn't public yet, as far as I know.

Both OpenSSL and GnuTLS were vulnerable to the second problem.  My
discussion of this for GnuTLS is in:

http://lists.gnupg.org/pipermail/gnutls-dev/2006-September/001205.html

When I read the OpenSSL advisory, I get the impression that it doesn't
quite spell out the second problem clearly, but if you look at the
patch to correct this:

+		/* Excess data can be used to create forgeries */
+		if(p != s+i)
+			{
+			RSAerr(RSA_F_RSA_VERIFY,RSA_R_BAD_SIGNATURE);
+			goto err;
+			}
+
+		/* Parameters to the signature algorithm can also be used to
+		   create forgeries */
+		if(sig->algor->parameter
+		   && sig->algor->parameter->type != V_ASN1_NULL)
+			{
+			RSAerr(RSA_F_RSA_VERIFY,RSA_R_BAD_SIGNATURE);
+			goto err;
+			}
+

You'll notice that there are two added checks, one check per problem.

Test vectors for this second problem are as below, created by Yutaka
OIWA.

jas at mocca:~/src/gnutls/tests$ cat pkcs1-pad-ok.pem
-----BEGIN CERTIFICATE-----
MIICzTCCAjagAwIBAgIJAOSnzE4Qx2H/MA0GCSqGSIb3DQEBBQUAMDkxCzAJBgNV
BAYTAkpQMRQwEgYDVQQKEwtDQSBURVNUIDEtNDEUMBIGA1UEAxMLQ0EgVEVTVCAx
LTQwHhcNMDYwOTA3MTY0MDM3WhcNMDcwOTA3MTY0MDM3WjBPMQswCQYDVQQGEwJK
UDEOMAwGA1UECBMFVG9reW8xFjAUBgNVBAoTDVRFU1QgMiBDTElFTlQxGDAWBgNV
BAMTD3d3dzIuZXhhbXBsZS5qcDCBnzANBgkqhkiG9w0BAQEFAAOBjQAwgYkCgYEA
vSpZ6ig9DpeKB60h7ii1RitNuvkn4INOfEXjCjPSFwmIbGJqnyWvKTiMKzguEYkG
6CZAbsx44t3kvsVDeUd5WZBRgMoeQd1tNJBU4BXxOA8bVzdwstzaPeeufQtZDvKf
M4ej+fo/j9lYH9udCug1huaNybcCtijzGonkddX4JEUCAwEAAaOBxjCBwzAJBgNV
HRMEAjAAMCwGCWCGSAGG+EIBDQQfFh1PcGVuU1NMIEdlbmVyYXRlZCBDZXJ0aWZp
Y2F0ZTAdBgNVHQ4EFgQUK0DZtd8K1P2ij9gVKUNcHlx7uCIwaQYDVR0jBGIwYIAU
340JbeYcg6V9zi8aozy48aIhtfihPaQ7MDkxCzAJBgNVBAYTAkpQMRQwEgYDVQQK
EwtDQSBURVNUIDEtNDEUMBIGA1UEAxMLQ0EgVEVTVCAxLTSCCQDkp8xOEMdh/jAN
BgkqhkiG9w0BAQUFAAOBgQCkGhwCDLRwWbDnDFReXkIZ1/9OhfiR8yL1idP9iYVU
cSoWxSHPBWkv6LORFS03APcXCSzDPJ9pxTjFjGGFSI91fNrzkKdHU/+0WCF2uTh7
Dz2blqtcmnJqMSn1xHxxfM/9e6M3XwFUMf7SGiKRAbDfsauPafEPTn83vSeKj1lg
Dw==
-----END CERTIFICATE-----

-----BEGIN CERTIFICATE-----
MIICijCCAfOgAwIBAgIJAOSnzE4Qx2H+MA0GCSqGSIb3DQEBBQUAMDkxCzAJBgNV
BAYTAkpQMRQwEgYDVQQKEwtDQSBURVNUIDEtNDEUMBIGA1UEAxMLQ0EgVEVTVCAx
LTQwHhcNMDYwOTA3MTYzMzE4WhcNMDYxMDA3MTYzMzE4WjA5MQswCQYDVQQGEwJK
UDEUMBIGA1UEChMLQ0EgVEVTVCAxLTQxFDASBgNVBAMTC0NBIFRFU1QgMS00MIGd
MA0GCSqGSIb3DQEBAQUAA4GLADCBhwKBgQDZfFjkPDZeorxWqk7/DKM2d/9Nao28
dM6T5sb5L41hD5C1kXV6MJev5ALASSxtI6OVOmZO4gfubnsvcj0NTZO4SeF1yL1r
VDPdx7juQI1cbDiG/EwIMW29UIdj9h052JTmEbpT0RuP/4JWmAWrdO5UE40xua7S
z2/6+DB2ZklFoQIBA6OBmzCBmDAdBgNVHQ4EFgQU340JbeYcg6V9zi8aozy48aIh
tfgwaQYDVR0jBGIwYIAU340JbeYcg6V9zi8aozy48aIhtfihPaQ7MDkxCzAJBgNV
BAYTAkpQMRQwEgYDVQQKEwtDQSBURVNUIDEtNDEUMBIGA1UEAxMLQ0EgVEVTVCAx
LTSCCQDkp8xOEMdh/jAMBgNVHRMEBTADAQH/MA0GCSqGSIb3DQEBBQUAA4GBABsH
aJ/c/3cGHssi8IvVRci/aavqj607y7l22nKDtG1p4KAjnfNhBMOhRhFv00nJnokK
y0uc4DIegAW1bxQjqcMNNEmGbzAeixH/cRCot8C1LobEQmxNWCY2DJLWoI3wwqr8
uUSnI1CDZ5402etkCiNXsDy/eYDrF+2KonkIWRrr
-----END CERTIFICATE-----

jas at mocca:~/src/gnutls/tests$ ../src/certtool -e < pkcs1-pad-ok.pem
Certificate[0]: C=JP,ST=Tokyo,O=TEST 2 CLIENT,CN=www2.example.jp
        Issued by: C=JP,O=CA TEST 1-4,CN=CA TEST 1-4
        Verifying against certificate[1].
        Verification output: Verified.

Certificate[1]: C=JP,O=CA TEST 1-4,CN=CA TEST 1-4
        Issued by: C=JP,O=CA TEST 1-4,CN=CA TEST 1-4
        Verification output: Verified.

jas at mocca:~/src/gnutls/tests$ cat pkcs1-pad-broken.pem
-----BEGIN CERTIFICATE-----
MIICzTCCAjagAwIBAgIJAOSnzE4Qx2H/MA0GCSqGSIb3DQEBBQUAMDkxCzAJBgNV
BAYTAkpQMRQwEgYDVQQKEwtDQSBURVNUIDEtNDEUMBIGA1UEAxMLQ0EgVEVTVCAx
LTQwHhcNMDYwOTA3MTY0MDM3WhcNMDcwOTA3MTY0MDM3WjBPMQswCQYDVQQGEwJK
UDEOMAwGA1UECBMFVG9reW8xFjAUBgNVBAoTDVRFU1QgMiBDTElFTlQxGDAWBgNV
BAMTD3d3dzIuZXhhbXBsZS5qcDCBnzANBgkqhkiG9w0BAQEFAAOBjQAwgYkCgYEA
vSpZ6ig9DpeKB60h7ii1RitNuvkn4INOfEXjCjPSFwmIbGJqnyWvKTiMKzguEYkG
6CZAbsx44t3kvsVDeUd5WZBRgMoeQd1tNJBU4BXxOA8bVzdwstzaPeeufQtZDvKf
M4ej+fo/j9lYH9udCug1huaNybcCtijzGonkddX4JEUCAwEAAaOBxjCBwzAJBgNV
HRMEAjAAMCwGCWCGSAGG+EIBDQQfFh1PcGVuU1NMIEdlbmVyYXRlZCBDZXJ0aWZp
Y2F0ZTAdBgNVHQ4EFgQUK0DZtd8K1P2ij9gVKUNcHlx7uCIwaQYDVR0jBGIwYIAU
340JbeYcg6V9zi8aozy48aIhtfihPaQ7MDkxCzAJBgNVBAYTAkpQMRQwEgYDVQQK
EwtDQSBURVNUIDEtNDEUMBIGA1UEAxMLQ0EgVEVTVCAxLTSCCQDkp8xOEMdh/jAN
BgkqhkiG9w0BAQUFAAOBgQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAUKJ+eFJYSvXwGF2wxzDXj+x5YCItrHFmrEy4AXXAW+H0NgJVNvqRY/O
Kw==
-----END CERTIFICATE-----

-----BEGIN CERTIFICATE-----
MIICijCCAfOgAwIBAgIJAOSnzE4Qx2H+MA0GCSqGSIb3DQEBBQUAMDkxCzAJBgNV
BAYTAkpQMRQwEgYDVQQKEwtDQSBURVNUIDEtNDEUMBIGA1UEAxMLQ0EgVEVTVCAx
LTQwHhcNMDYwOTA3MTYzMzE4WhcNMDYxMDA3MTYzMzE4WjA5MQswCQYDVQQGEwJK
UDEUMBIGA1UEChMLQ0EgVEVTVCAxLTQxFDASBgNVBAMTC0NBIFRFU1QgMS00MIGd
MA0GCSqGSIb3DQEBAQUAA4GLADCBhwKBgQDZfFjkPDZeorxWqk7/DKM2d/9Nao28
dM6T5sb5L41hD5C1kXV6MJev5ALASSxtI6OVOmZO4gfubnsvcj0NTZO4SeF1yL1r
VDPdx7juQI1cbDiG/EwIMW29UIdj9h052JTmEbpT0RuP/4JWmAWrdO5UE40xua7S
z2/6+DB2ZklFoQIBA6OBmzCBmDAdBgNVHQ4EFgQU340JbeYcg6V9zi8aozy48aIh
tfgwaQYDVR0jBGIwYIAU340JbeYcg6V9zi8aozy48aIhtfihPaQ7MDkxCzAJBgNV
BAYTAkpQMRQwEgYDVQQKEwtDQSBURVNUIDEtNDEUMBIGA1UEAxMLQ0EgVEVTVCAx
LTSCCQDkp8xOEMdh/jAMBgNVHRMEBTADAQH/MA0GCSqGSIb3DQEBBQUAA4GBABsH
aJ/c/3cGHssi8IvVRci/aavqj607y7l22nKDtG1p4KAjnfNhBMOhRhFv00nJnokK
y0uc4DIegAW1bxQjqcMNNEmGbzAeixH/cRCot8C1LobEQmxNWCY2DJLWoI3wwqr8
uUSnI1CDZ5402etkCiNXsDy/eYDrF+2KonkIWRrr
-----END CERTIFICATE-----

jas at mocca:~/src/gnutls/tests$ ../src/certtool -e < pkcs1-pad-broken.pem
Certificate[0]: C=JP,ST=Tokyo,O=TEST 2 CLIENT,CN=www2.example.jp
        Issued by: C=JP,O=CA TEST 1-4,CN=CA TEST 1-4
        Verifying against certificate[1].
        Verification output: Not verified.

Certificate[1]: C=JP,O=CA TEST 1-4,CN=CA TEST 1-4
        Issued by: C=JP,O=CA TEST 1-4,CN=CA TEST 1-4
        Verification output: Verified.
jas at mocca:~/src/gnutls/tests$

If the above commands were used with an older GnuTLS 'certtool', they
would claim that the chain in pkcs1-pad-broken.pem is valid.

For reference, the certificate key: