Re: [OpenCA-Devel] Security Alert: Broken RSA Implementations

[Fan H. <fa...@ih...>]

Hi,all 

I just want to know in which cases we would probablely issue exponent 3 
certs. 

Thank you!

On Mon, 18 Sep 2006 01:32:39 +0200, Ives Steglich wrote
> 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
> Ope...@li...
> https://lists.sourceforge.net/lists/listinfo/openca-devel


*-----------------------------------------------------------------*
|FAN,HuaXiang                    Building: 203 Computing Centre   |
|Computing Centre                     Tel: (+86) 10 8823 6837     |
|Institute of High Energy Physics     MSN: Washam.Fan@hostmail    |
|19B Yuquan Road                    Email: Hua...@ih...|
|P.O. Box 918-7                                                   |
|Beijing 100049,China                                             |
*-----------------------