RSA signing - does EMSA-PKCS1-v1_5 padding need to be verified?
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$.

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&lt;\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&lt;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&gt;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&nbsp;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.