Is it possible to forge a RSA signature with a known public key, hardcoded padding, and unlimited oracle information?

Question

I'm doing vulnerability research and looking at a device that is using some u-boot RSA encryption that they've modified. I've extracted the 4096-bit public key from the flash, it has an exponent of 65537. They simplified the padding to use a hardcoded 480-byte array that's labeled as "PKCS 1.5 paddings as described in the RSA PKCS#1 v2.1 standard"

[ 0x00, 0x01, (458 * 0xFF), 0x00, 0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20 ]

I have the source code for verifying the signature and doing a memcmp on the padding and the sha256 hash. I can recreate the decomp byte-for-byte and create any kind of padding oracle that I would need. I don't have any known ciphertext, unfortunately.

It's probably obvious to most of you but crypto isn't my strong suit. I've successfully done some AES CBC-mode bit flip attacks previously. I'm trying to learn and improve though. I'm looking for guidance in any research material that can help me understand if there is a potential vulnerability here.

I'm interested in being able to forge a signature if possible but almost all of the reference material I've found is only applicable when the exponent is 3.

I did find this previous post (https://crypto.stackexchange.com/a/27512) that linked to some white papers on fixed padding.

Answer 1

Based on the information in your question, the device is using a standard signature verification method which has no known vulnerabilities. PKCS#1v1.5 padding for signatures is secure, and not particularly hard to implement correctly. (There's a risk of side channels on the signature side, but that's not what you're trying to attack.)

In a PKCS#1v1.5 signature, the padding is constant for a given key size and hash algorithm. The fixed string you posted is the padding for a 4096-bit key and a SHA-256 hash as specified by PKCS#1 v2.1 §9.2: the most significant bytes are 0x00 0x01, the least significant bytes are a bit of metadata indicating which hash algorithm is used and then the hash, and the space in between is filled with 0xFF bytes. Even with nonstandard padding, this general approach would be secure as long as the padding reaches the most significant bytes. The choices in PKCS#1v1.5 make the padding more robust against some scenarios, such as using the same key with different hash algorithms (if it happens that $H_1(M_1) = H_2(M_2)$, a valid signature of $M_1$ using $H_1$ can't be used to make $M_2$ accepted by pretending that it's a signature with $H_2$) or using the same key for signature and encryption (a PKCS#1v1.5 encryption padding starts with 0x00 0x02, so the same string cannot be both a valid signature and a valid ciphertext).

The potential weakness in PKCS#1v1.5 verification is if the verification does not check the padding properly. RSA signature verification works by applying the public key to the signature (calculating $s^e \mod n$) and then decoding the result, which is supposed to contain the padded hash. A bad implementation can take the shortcut of just extracting the hash and ignoring most of the padding. This allows a forgery attack: if you want to create a fake signature of $h$, you look for a number $m$ such that $m \lt n$ and $\sqrt[e]{m} = h$. Because the numbers involved are less than $n$, there is no modular exponentiation involved and so the knowledge of the factorisation of $n$ is not needed to calculate a root. This is the Bleichenbacher attack you've read about for $e=3$ (for larger $e$, $m$ would have to be larger than $n$ for real-world sizes). This vulnerability tends to be found in implementations that are flexible in terms of key size and hash algorithm, and takes shortcuts. Given the string you've found in the image, it's highly likely that the code is written for a fixed key size and hash algorithm and checks the padding string. This makes it immune to this attack.

If you want to bypass the signature verification, you're going to have to find a way other than a forgery.