Hi all,
recently there have been some papers and sample exploit code announced which
can succesfull attack weak public exponent ca-keys.
since openca and openxpki are using the openssl libraries, which are obvoisly
also have a faulty implementation please check the following links and read
carefully:
http://www.openssl.org/news/secadv_20060905.txt
http://www.imc.org/ietf-openpgp/mail-archive/msg14307.html
if you have a proper workflow and checks for your ca-keys there shouldn't be
any real issues with that. but just in case... especially public exponents of
3 are an real issue...
other x.509 implementations may be also effected. fireforx for example has
also released a new release to tackle this issue...
kind regards
ives
http://www.openssl.org/news/secadv_20060905.txt
OpenSSL Security Advisory [5th September 2006]
RSA Signature Forgery (CVE-2006-4339)
=====================================
Vulnerability
-------------
Daniel Bleichenbacher recently described an attack on PKCS #1 v1.5
signatures. If an RSA key with exponent 3 is used it may be possible
to forge a PKCS #1 v1.5 signature signed by that key. Implementations
may incorrectly verify the certificate if they are not checking for
excess data in the RSA exponentiation result of the signature.
Since there are CAs using exponent 3 in wide use, and PKCS #1 v1.5 is
used in X.509 certificates, all software that uses OpenSSL to verify
X.509 certificates is potentially vulnerable, as well as any other use
of PKCS #1 v1.5. This includes software that uses OpenSSL for SSL or
TLS.
OpenSSL versions up to 0.9.7j and 0.9.8b are affected.
The Common Vulnerabilities and Exposures project (cve.mitre.org) has
assigned the name CAN-2006-4339 to this issue.
Recommendations
---------------
There are multiple ways to avoid this vulnerability. Any one of the
following measures is sufficient.
1. Upgrade the OpenSSL server software.
The vulnerability is resolved in the following versions of OpenSSL:
- in the 0.9.7 branch, version 0.9.7k (or later);
- in the 0.9.8 branch, version 0.9.8c (or later).
OpenSSL 0.9.8c and OpenSSL 0.9.7k are available for download via
HTTP and FTP from the following master locations (you can find the
various FTP mirrors under http://www.openssl.org/source/mirror.html):
o http://www.openssl.org/source/
o ftp://ftp.openssl.org/source/
The distribution file names are:
o openssl-0.9.8c.tar.gz
MD5 checksum: 78454bec556bcb4c45129428a766c886
SHA1 checksum: d0798e5c7c4509d96224136198fa44f7f90e001d
o openssl-0.9.7k.tar.gz
MD5 checksum: be6bba1d67b26eabb48cf1774925416f
SHA1 checksum: 90056b8f5e518edc9f74f66784fbdcfd9b784dd2
The checksums were calculated using the following commands:
openssl md5 openssl-0.9*.tar.gz
openssl sha1 openssl-0.9*.tar.gz
2. If this version upgrade is not an option at the present time,
alternatively the following patch may be applied to the OpenSSL
source code to resolve the problem. The patch is compatible with
the 0.9.6, 0.9.7, 0.9.8, and 0.9.9 branches of OpenSSL.
o http://www.openssl.org/news/patch-CVE-2006-4339.txt
Whether you choose to upgrade to a new version or to apply the patch,
make sure to recompile any applications statically linked to OpenSSL
libraries.
Acknowledgements
----------------
The OpenSSL team thank Philip Mackenzie, Marius Schilder, Jason Waddle
and Ben Laurie, of Google Security, who successfully forged various
certificates, showing OpenSSL was vulnerable, and provided the patch
to fix the problems.
References
----------
http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2006-4339
http://www.imc.org/ietf-openpgp/mail-archive/msg14307.html
URL for this Security Advisory:
http://www.openssl.org/news/secadv_20060905.txt
http://www.imc.org/ietf-openpgp/mail-archive/msg14307.html
At the evening rump session at Crypto last week, Daniel Bleichenbacher
gave a talk showing how it is possible under some circumstances to
easily forge an RSA signature, so easily that it could almost be done
with just pencil and paper. This depends on an implementation error,
a failure to check a certain condition while verifying the RSA signature.
Daniel found at least one implementation (I think it was some Java crypto
code, not OpenPGP related) which had this flaw. I wanted to report on
his result here so that other OpenPGP implementers can make sure they
are not vulnerable. Be aware that my notes were hurried as Daniel had
only a few minutes to talk.
The attack is only good against keys with exponent of 3. There are
not too many of these around any more but you still run into them
occasionally. It depends on an error in verifying the PKCS-1 padding
of the signed hash.
An RSA signature is created in several steps. First the data to be
signed is hashed. Then the hash gets a special string of bytes in ASN.1
format prepended, which indicates what hash algorithm is used. This data
is then PKCS-1 padded to be the width of the RSA modulus. The PKCS-1
padding consists of a byte of 0, then 1, then a string of 0xFF bytes,
then a byte of zero, then the "payload" which is the hash+ASN.1 data.
Graphically:
00 01 FF FF FF ... FF 00 ASN.1 HASH
The signature verifier first applies the RSA public exponent to reveal
this PKCS-1 padded data, checks and removes the PKCS-1 padding, then
compares the hash with its own hash value computed over the signed data.
The error that Bleichenbacher exploits is if the implementation does
not check that the hash+ASN.1 data is right-justified within the PKCS-1
padding. Some implementations apparently remove the PKCS-1 padding by
looking for the high bytes of 0 and 1, then the 0xFF bytes, then
the zero byte; and then they start parsing the ASN.1 data and hash.
The ASN.1 data encodes the length of the hash within it, so this tells
them how big the hash value is. These broken implementations go ahead
and use the hash, without verifying that there is no more data after it.
Failing to add this extra check makes implementations vulnerable to a
signature forgery, as follows.
Daniel forges the RSA signature for an exponent of 3 by constructing a
value which is a perfect cube. Then he can use its cube root as the
RSA signature. He starts by putting the ASN.1+hash in the middle of
the data field instead of at the right side as it should be. Graphically:
00 01 FF FF ... FF 00 ASN.1 HASH GARBAGE
This gives him complete freedom to put anything he wants to the right
of the hash. This gives him enough flexibility that he can arrange for
the value to be a perfect cube.
In more detail, let D represent the numeric value of the 00 byte, the
ASN.1 data, and the hash, considered as a byte string. In the case
of SHA-1 this will be 36 bytes or 288 bits long. Define N as 2^288-D.
We will assume that N is a multiple of 3, which can easily be arranged
by slightly tweaking the message if neccessary.
Bleichenbacher uses an example of a 3072 bit key, and he will position
the hash 2072 bits over from the right. This improperly padded version
can be expressed numerically as 2^3057 - 2^2360 + D * 2^2072 + garbage.
This is equivalent to 2^3057 - N*2^2072 + garbage. Then, it turns out
that a cube root of this is simply 2^1019 - (N * 2^34 / 3), and that is
a value which broken implementations accept as an RSA signature.
You can cube this mentally, remembering that the cube of (A-B) is A^3 -
3(A^2)B + 3A(B^2) - B^3. Applying that rule gives 2^3057 - N*2^2072
+ (N^2 * 2^1087 / 3) - (N^3 * 2^102 / 27), and this fits the pattern
above of 2^3057 - N*2^2072 + garbage. This is what Daniel means when
he says that this attack is simple enough that it could be carried out
by pencil and paper (except for the hash calculation itself).
Implementors should review their RSA signature verification carefully to
make sure that they are not being sloppy here. Remember the maxim that in
cryptography, verification checks should err on the side of thoroughness.
This is no place for laxity or permissiveness.
Daniel also recommends that people stop using RSA keys with exponents
of 3. Even if your own implementation is not vulnerable to this attack,
there's no telling what the other guy's code may do. And he is the one
relying on your signature.
Hal Finney
-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
OpenCA-Devel mailing list
OpenCA-Devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/openca-devel
