RSA signing - does EMSA-PKCS1-v1_5 padding need to be verified?

Question

I am working with an embedded system that accepts firmware updates only if they are validly signed by a particular 2048-bit RSA private key (the embedded system's bootloader knows the corresponding public key).

On the publishing side, the signature is generated by:

1. computing the SHA-256 hash of the firmware image
2. padding it according to EMSA-PKCS1-v1_5 (which involves prepending a fixed 1792-bit string)
3. signing the concatenated 2048-bit value by exponentiation with the RSA private key

On the embedded side, the signature is verified by:

1. independently (re-)computing the SHA-256 hash of the received firmware image
2. recovering the concatenated 2048-bit value from the signature by exponentiation with the RSA public key
3. verifying that the first 1792 bits of the value exactly match the expected padding string
4. verifying that the last 256 bits of the value (i.e. the SHA-256 hash computed on the publishing system) exactly match the hash computed on the embedded system

So, the question:

Is step #3 (verifying the EMSA-PKCS1-v1_5 padding) important to the security of the system?

(This is a theoretically-motivated question; I want to educate myself. It's not a significant added cost on the embedded side to verify the padding.)

P.S. I've attempted to search for existing questions/answers already, and Attacking RSA signature verification that ignores padding is very close. In that case though, I gather that the implementation basically searched the entire recovered 2048-bit value for a substring matching the recomputed SHA-256 hash; and the possibility of having garbage data after the hash specifically made attacks like this Kindle HDX hack possible.

In this case I'm specifically wondering whether it's a bad idea to simply ignore/remove the first 1792 bits (assumed to be the padding) and only compare the last 256 bits to the expected hash. Does that open the possibility for the same type of attack? Or for different attacks?

Answer 1

Is step #3 (verifying the EMSA-PKCS1-v1_5 padding) important to the security of the system?

Yes. That's paramount for small RSA public exponent $e$.

Lacking this check, for $e\in\{3,5,7\}$, the easily computed integer $s=h^{(e^{-1}\bmod2^{254})}\bmod2^{256}$ is an acceptable signature for any message with an odd SHA-256 hash $h$ (that is about one message out of two). The attack can be extended to $e=9$, and with significant computational effort to $e=11$, by trying multiple messages until $s$ thus computed verifies $s<\sqrt[e]N$. The number of odd $h$ to try is about $2^{256}/\sqrt[e]N$.

That works because by construction of $s$, it holds $s^e<N$, therefore $s^e\bmod N=s^e$. Therefore $(s^e\bmod N)\bmod 2^{256}$, which is what's checked by the question's faulty signature verification procedure, is $h^{(e^{-1}\bmod2^{254})e}\bmod2^{256}$, that is $h$ for odd $h$ (notice such $h$ is coprime to $2^{256}$ and $\lambda(2^{256})=2^{254}$, where $\lambda$ is the Carmichael function, such that $\forall m>0$ and $\forall a$ coprime to $m$, $a^{\lambda(m)}\bmod m=1$).

If there is an attack working for $e\ge13$ for the question's parameters, I want to know. But as the saying attributed¹ to the NSA goes: "Attacks always get better; they never get worse".

The conclusion is that we should fully check RSA signature padding. In my opinion, it's not a sufficient reason to systematically avoid very small $e$, which should only be an extra precaution taken when we can afford the $\approx8$ time penalty in signature verification incurred by using the standard $e=F_4=2^{(2^4)}+1=65537$. Additionally, we should use a padding with an argument of reducibility to the RSA problem like that in RSASSA-PSS, or ISO/IEC 9796-2 scheme 2 or 3.

---

Incorrect verification of PKCS#1 V1.5 type 01 signature at least used to abound. That was first made public by Daniel Bleichenbacher's RSA signature forgery based on implementation error (account by Hal Finney of Crypto 2006 rump session). Among later derived attacks: Ulrich Kühn, Andrei Pyshkin, Erik Tews, Ralf-Philipp Weinmann, Variants of Bleichenbacher’s Low-Exponent Attack on PKCS#1 RSA Signatures; and the BERserk vulnerability. I have always wondered if "never attribute to malice what can be attributed to incompetence" really applies to these faulty implementations.

---

¹ ^{by Bruce Schneier in Applied Cryptography IIRC.}