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) which had this flaw. I wanted to report on his result here so that other 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 ASN.1+hash 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 --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]