Forgery against signature using RSAES-PKCS1-v1_5 padding

Question

I wonder what is the security of RSAES-PKCS1-v1_5 under chosen-plaintext attack, in the context of signature verification.

Notations. Let $(N,d)$ be an RSA signing key, and $(N,e)$ the corresponding verification key, with no assumption on $e$ (in particular, I don't assume $e=3$ and consider the general case $e=2^{16}+1$). Let $n$ be the bit-size of $N$.

More specifically, assume that one produces a signature $s$ for a short message $m$ using RSAES-PKCS1-v1_5 padding (bad practice): $$ s = pad(m)^d \bmod{N}, $$ where

pad(m) = 00 || 02 || R || 00 || m

and R contains 8 or more nonzero bytes to make $pad(m)$ as long as the byte-length of $N$. (Note: unlike RSASSA-PKCS1-v1_5, the bytes in R are not fixed to FF.) Also here, the message is not hashed.

I wonder whether universal forgery is possible with only oracle access to the verification oracle $O(s)$, which returns $m$ if $s^e \bmod{N}$ corresponds to a valid padded message, and returns an error otherwise.

In an answer, Thomas Pornin writes that this "type 2" padding yields a weak signature scheme due to malleability of modular exponentiation. I understand that "type 1" (RSASSA-PKCS1-v1_5) is for digital signatures and "type 2" (RSAES-PKCS1-v1_5) for encryption, yet I don't see how malleability can be applied here to break the security.

---

Side question. In another answer poncho wrote that if $x^3 = h \bmod{2^{k}}$, then $y^3 = h \bmod{2^{k+1}}$ for $y=x$ or $y=x+2^k$. Hence here, given a target message $m$, is it easy to construct $s'$ such that $s'^e = m \bmod{2^{n+1}}$ for $n$-bit $N$. Which means that there exists $t$ such that $s'^e = m + t\cdot 2^{n+1}$. The integers $s'$ and $t$ are easily, but can they be leveraged to deduce $s$ such that $s^e = m \bmod{N}$?

Answer 1

Less than satisfactory partial answer, which no longer fits a comment.

With $N$ of $k$ bytes and message of $l$ bytes, a (signature, message) pair with random signature is accepted by the most stringent verification oracle with probability $$2^{-8l-24}\;(2^{8k}/N)\;\left(1-2^{-8}\right)^{k-l-3}$$

For 2048-bit $N$ and small $l$, that's about $2^{-8l-25}$. Probability is higher for an oracle comparing messages as C strings, stopping with the first zero encountered.

That's enough for universal forgery of short messages with about $2^{8l+25}$ queries to the verification oracle or modular exponentiations to the $e$, and existential forgery with about $2^{24}$ modular exponentiations to the $e$. No signing oracle is used.

Malleability allows a small speedup: we pick some $a$ (e.g. $a=2$), compute $b=a^e\bmod N$, then $b^i\bmod N$ for incremental $i$, which we check for acceptable padding (and match with the message for universal forgery). If $b^i$ is accepted, $a^i\bmod N$ is a signature of the message embedded in $b^i$. Each new candidate $b^i$ is obtained with a single modular multiplication by $b$, rather than 16 sqrmod and 1 mulmod for modular exponentiation with $e=2^{16}+1$. Further, modular multiplication by a constant can be appreciably optimized by precomputations.

Independently, malleability allows to obtain $f$ existential forgeries from $f+2$ queries to a textbook-RSA signature oracle. We can efficiently prepare $2f+2$ values $c_i$ with acceptable padding such that $c_0 c_{2j}=c_1 c_{2j+1}$, submit $c_0$, $c_1$, and the $c_{2j}$ for $1\le j\le f$ to the oracle, then compute what it would return for the $c_{2j+1}$. There is a lot of freedom for the messages which forged signature is obtained. The attack still works if the signature oracle checks that what it is asked to sign has correct padding format, but fails if the oracle supplies the R part of the padding.

It remains unclear what The Bear had in mind with the following in his answer:

If you use (this) padding for signatures, then you obtain a very weak signature scheme (because of the malleability inherent to modular exponentiations)