### Bleichenbacher's RSA signature forgery based on implementation error

hal@finney.org ("Hal Finney") Mon, 28 August 2006 11:34 UTC

Received: from [10.91.34.44] (helo=ietf-mx.ietf.org)
by megatron.ietf.org with esmtp (Exim 4.43) id 1GHfOG-0001Aj-UP
for openpgp-archive@lists.ietf.org; Mon, 28 Aug 2006 07:34:52 -0400

Received: from stsc1260-eth-s1-s1p1-vip.va.neustar.com ([156.154.16.129]
helo=chiedprmail1.ietf.org)
by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1GHcCD-0001om-Le
for openpgp-archive@lists.ietf.org; Mon, 28 Aug 2006 04:10:13 -0400

Received: from balder-227.proper.com ([192.245.12.227])
by chiedprmail1.ietf.org with esmtp (Exim 4.43) id 1GHbhz-0001Vj-Bz
for openpgp-archive@lists.ietf.org; Mon, 28 Aug 2006 03:39:00 -0400

Received: from balder-227.proper.com (localhost [127.0.0.1])
by balder-227.proper.com (8.13.5/8.13.5) with ESMTP id k7S6l4JD057279;
Sun, 27 Aug 2006 23:47:04 -0700 (MST)
(envelope-from owner-ietf-openpgp@mail.imc.org)

Received: (from majordom@localhost)
by balder-227.proper.com (8.13.5/8.13.5/Submit) id k7S6l46o057278;
Sun, 27 Aug 2006 23:47:04 -0700 (MST)
(envelope-from owner-ietf-openpgp@mail.imc.org)

X-Authentication-Warning: balder-227.proper.com: majordom set sender to
owner-ietf-openpgp@mail.imc.org using -f

Received: from finney.org (226-132.adsl2.netlojix.net [207.71.226.132])
by balder-227.proper.com (8.13.5/8.13.5) with ESMTP id k7S6l11G057261
for <ietf-openpgp@imc.org>; Sun, 27 Aug 2006 23:47:04 -0700 (MST)
(envelope-from hal@finney.org)

Received: by finney.org (Postfix, from userid 500)
id 70D3457FD3; Sun, 27 Aug 2006 22:42:46 -0700 (PDT)

To: ietf-openpgp@imc.org

Subject: Bleichenbacher's RSA signature forgery based on implementation error

Message-Id: <20060828054246.70D3457FD3@finney.org>

Date: Sun, 27 Aug 2006 22:42:46 -0700 (PDT)

From: hal@finney.org ("Hal Finney")

Sender: owner-ietf-openpgp@mail.imc.org

Precedence: bulk

List-Archive: <http://www.imc.org/ietf-openpgp/mail-archive/>

List-Unsubscribe: <mailto:ietf-openpgp-request@imc.org?body=unsubscribe>

List-ID: <ietf-openpgp.imc.org>

X-Spam-Score: -2.6 (--)

X-Scan-Signature: 3002fc2e661cd7f114cb6bae92fe88f1

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

- Bleichenbacher's RSA signature forgery based on... "Hal Finney"